ふるつき

v(*'='*)v かに

SuperCon（スーパーコンピューティングコンテスト）2016の本選に出た

SuperCon本選でチームワークを発揮したので、kingyo（は3位だった。すごいな。

SuperConについて

よくわからなかったが、SuperComputerのすっごい資源をつかって計算させてくれるプログラミングコンテストだと思う。今年は東工大のTSUBAMEというスパコンを使った。

予選

私は予選の問題はさっぱりわからなかったので。チームメイトが去年JOIの本選にでるなど健闘していたのでJavaで解コードを書いてもらい、C言語に移すなどしていた。要項にはANSI Cに準拠すること、とあったが、ANSI CがどんなCか全然わからず、不安のなか移植をした。

枝刈り全探索みたいなコードだったと思う。C言語のよくわからない型挙動に苦戦しつつなんとか動くコードにして、提出した。このときは予選突破があるとは思ってなかった。

それからn日くらいたって予選突破報告がTLに流れ始めたが、我らのチームにはメールが来ず、やはりだめか……と言っていた。しかし本戦出場の意思がないチームがあったのか、なんか一番お尻につっこまれて本選にでられることになった。かなり嬉しかった。

本選

本選では5日間阪大に通った。家からだと2.5時間くらいかかるので移動が長かった。 それはそれとして、とりあえず本選で問題の説明がされたりした。できるだけ良いスコアを出す系の問題だった。

私はそういう問題の対策は山登り法と焼きなまし法しか知らなかったので、焼きなましっぽいのの実装を始めた。チームメイトはランダムではない方法を模索したり、GPUで評価値を求めるプログラムを書いたりしていた。

二日目の終わりくらいにはほとんど焼きなまし完成みたいな感じで、動くコードができていた。手法としては、グラフ中の四点（二点同士が辺で結ばれている、などグラフの正則性を保つような制約つきでランダムに選択したもの）の辺をつなぎ替えるみたいな感じだった。これをtsunaginao_c関数と名づけて、ファイル名をtsunaginao.cとしてうまいじゃんと笑っていたが、後にcudaを導入してtsunaginao.cuになったりした。

あとは重み付けとか、評価関数とかを書いていた。評価関数のワーシャルフロイドをバグらせていたのは笑える。

三日目くらいにはちゃんと動くようになっていた。サンプルの小さいケースを食べて値が出る！　などと無邪気に遊んでいた。この時点では初期グラフの良さがそのまま出力に直結する感じだったので、初期グラフをn回つくれるように改良したりしていた。

提出練習でもそれなりに動いたので手応えを感じていた。チームメイトの一人が行列積のGPU高速化番を作ってくれていたのでそれを使ったら最大ケースで2.5s程度で評価関数が動作していい感じ。本当はもっと早く、10倍くらいにはなるらしい。

4日目は初期グラフをランダムではなく規則的に並べる方針を採用した。初期値は悪いが、焼きなましと相性が良かった。初期グラフが綺麗なのでプログラム名はkireiとなった。

さらに辺の交換ではなくて色の交換を行った。これ自体はあんまり機能しなかったがこれとtsunaginao_cを組み合わせるといい結果がでるケースがあり採用となった。これを用いたプログラムがchimeraとkirei_swapvと名付けられた。

さらに、競技直前に、「ある程度結果を出した後のグラフからもう一回やりたくない？」という話が出てこれの爆速実装を行った。これは初期グラフ生成のかわりにグラフを読み込む処理を加えるだけなのでそんなに難しくはない。しかしここまでで、gpu（これが最初のプログラム）、kirei、chimera、kirei_swapvと四つのプログラムを作ってしまい（それぞれコピーしてディレクトリごとに管理していた）、それらのすべてに手を加えなければならないので大変だった。実際、gpu以外のプログラムでのrestore機能の実装は競技開始してからだった。

四日目なのでお昼すぎから競技だった。だいたい、一つの問題ケースにたいして5minずつ割り当てて、chimeraとkireiをつかって頑張っていた。最初はGPU利用の競合を懸念して一つしかSolverを走らせなかったが、とちゅうから並列で走らせた。ちゃんとプログラムが遅くなって面白かった。

最初は全然振るわなかったkingyoだが、なんか次数がでっかいケースなどつよいのでは？とか適当に考えて6問目を回したところ、1位かそれに準ずる順位を取れて俄然士気が上がった。それぞれの問題で10～6位程度を取れたので、restoreプログラムを活躍させて一回submitしたファイルから計算を再開させるなどしてちょっとずつスコアを改善するちくちく作戦をやっていた。ここでrestoreでは焼きなましが走ってしまいなんかせっかく山に登っていたのに降りやすくなってしまっておもしろかった。kireiに関しては完全に山登りにしたnouseというプログラムをforkして走らせたりしていた。どちらでも結果はそんなに変わらない感じだった。

そんなことをしていると1位を取れる問題がいっこでたので、それのSolverは競技中ずっと走らせていた。

競技終了前の平均得点は4位相当だった。最後の５分も計算させてsubmitし四日目を終えた。

最終日は表彰式があった。なんか最後の5分で4位くらい浮上している問題があり3位だった。

表彰後は懇親会みたいなのがあったのでたこ焼きとフライドポテトを食べながら優勝チームやそうでないチームと話をした。

他のチームのひとの話をきいていると考察がなされていて頭がいいとおもったり、うちの評価関数はめちゃおそいということがわかったりしてもっと戦えたのではと思った。

その他

何かもっと書きたかったかもしれないが忘れたのでいいや。

mixi git challenge に参加した

blogに書くまでが遠足らしいので。

summary

mixi git challengeという催し物がありました。mixiさんが開催している、gitの問題解決コンテストのようなものです。

私はそれに出場しました。

結果、2位でした。

とても楽しかったし学びになりました。部内でgit challengeみたいなものを開きたいな、などと思いました。

summaryじゃないやつ

学校の先輩に紹介されてmixi git challengeというものを知りました。git限定のCTFのようなものだと理解して、早速申し込みました。ちょうどSANS NETWARSの後の日で非常に都合が良かったです。

運良く、行けることになりました。同じ学校、同じ部活から kyumina と mi_24v も参加できることになり非常な幸運でした。

SANS NETWARSに出た次の日、mixi git challengeに行きました。NETWARSでの疲れがでて、当日の朝はちょっと寝坊をして、朝ごはんを食べそびれました。

mixiさんのオフィスにたどり着くと、私達チームのテーブルに案内されました。チーム名はfoxtront。alpha、bravo、charlie……でhotelまでありました。

チームメイトはkyuminaでした。

コンピュータのセッティングをしたりしていると、開会しました。この時点では mi_24v が来ていなかったのが面白かったです。

お昼のタイミングでは、チュータの方（mixiのひとです。宗教はEmacsらしいです）とお話をさせてもらいました。kyuminaと一緒に結構突っ込んだ話などもして、楽しかったです。

さてお昼から3時間半くらい、競技をやりました。簡単なものでは、「昔のコミットメッセージが間違っていたので修正してください」というものや、難しいものでは、大量のブランチとコミットによる地獄をなんとかしろみたいなものがありました。

得点の幅は1 - 6でしたが、圧倒的に2点問題が多かったので、3点、5点、6点が非常に怖くみえました。

私たちはとりあえず1点の問題に着手し、kyuminaがいい感じに点をとってくれました。

その後、やっと最初に手を出した問題を解くことができ、もう一問1点の問題を解いて、さらに、2点問題を2個か3個くらい解いたと思います。これらは、googleと push -f でなんとかなる問題でした。

そんなこんなをしているうちにあっという間に競技時間が終わり、気がつけば2位でした（1位のチームは3点問題を2問解いており、さらに私達が解けなかった2点問題を1問解いていたので、8点もの差がありました）。

2位なので、Octcatをもらったりしました。 その後は懇親会があって、 mixiの人のありがたいお話をきいたり、とにかく楽しい時間を過ごしました。

おわり

SECCON 九州大会に参加した

まとめ

insecureというチームでSECCON九州大会に参加し、見事に優勝をかっさらいました。よかったです。

f:id:Furutsuki:20160717164945j:plain

各チームの机には、小袋や中袋に入った電子機器（っぽいの）や配線キットが並んでいました。内訳は大体つぎのような感じです。

配線キットやテスタもありました。あとラジオペンチとニッパもありました。めっちゃいいやつを貸してもらったらしいのですが、私は触る機会が無くて残念。

さて、これはこれはとやばそうな感じがしてるし、私どこまで戦えるかなーという不安がいっぱいでしたが、いいところまで喰らいついていく自信はありました。チームメイトが強力だったので。

OPENING

今回のSECCON九州大会では、11チーム33名が参加するとのことでした。一人で参加のチームが2つもありやばかったです。あと、CTF for ビギナーズの方々がHIRUMADEとか言ってさらっと飛び入り参加してたのがやばやばでした。

さて、大会の形式ですが、Jeopardyというやつでした。全部で5問各100点で、それぞれの問題のFirst Blood には +10 pts されます。5問しか無いと点差がつきにくく、First Bloodを何個とれるか、というのも重要そうだなぁと思っていました。

ここから、WriteUpのようなものを書くつもりですが、詳しいことは、師匠のブログを見るといいかもしれません。

コンピュータ技術を学んでいくブログ: SECCON 2016 九州大会のWrite Upと感想

1 なんか水道局員になるやつ

関東は干上がっているので水道局員になりIoTで水の流れを制御するらしいです。問題自体は、「回路も機材もやるから、Raspberry Piでモータ動かせ」というようなものでした。師匠が経験と勘とでぼぎょぎょと組んだ回路とプログラムがいい感じに動いて、First Bloodをもらえた問題でした。詳しいことは師匠が書いてくれるはずです。

2 なんか特命を受けるやつ

酒場のような場所（ギルド？）でマイクロチップに入った特命を受けた私たちは……。

マイクロチップとは、ずばり 24LC256 のことです。これは、「EEPROM」という不揮発性のメモリらしいです。8本足の小さなムカデですが、32KBも容量あるらしいです。

ということで、これは、まず特命が何かを知って（ここで100pt）、その特命を果たす（これがまた100pt）という二段組の問題でした。

この問題のFirst Bloodは1時間しか参加しないと言っていたHIRUMADEで、開始40分とかでどこのチームよりも早くポイントを得ていました。

私達も随分あとになって続くことができました。最初は、師匠のPicKit2をつかってデータを吸い出そうとしましたが、これがうまく行かず、いろいろ試行錯誤して、私が持ってきていた、JapaninoというArduino互換機を使いました。

Google先生に尋ねれば、Arduinoで24LC256のデータを吸うような接続の例はたくさんあったので、ちょろっとコードを書いて（これも、ArduinoのエディタもってるテンプレートにEEPROMからデータを吸うものがあり、それを少しいじるだけでした。しかし、実際には、ググったさきで出たコードを使いました）、データを吸いました。

#include <Wire.h>

#define disk1 0x50

void setup()
{
  Serial.begin(9600);
  Wire.begin();
  
   unsigned int address = 0;
  byte b = 0XFF;
  
  int flag = 0;
  while (address < 32 * 1024) {
    b = readEEPROM(disk1, address);
    if (b == 0xFF) {
      flag = 1;
    }
    if (flag != 0) {
      if (b == 0xFF) {
        flag += 1;
        if (flag > 4) {
          break;
        }
      }
      flag = 0;
    }
    Serial.println(b, HEX);
    address++;
  }
}

void loop() {}

byte readEEPROM(int deviceaddress, unsigned int readaddress)
{
  byte rdata = 0xFF;
  Wire.beginTransmission(deviceaddress);
  Wire.send((int)(readaddress >> 8));
  Wire.send((int)(readaddress & 0xFF));
  Wire.endTransmission();
  
  Wire.requestFrom(deviceaddress, 1);
  
  if (Wire.available()) {
    rdata = Wire.receive();
  }
  
  return rdata;
}

256Bytesほどすって file してみると、どうやら tar gz ということがわかり、伸張しようとしましたが、エラーを吐かれました。ちゃんと最後まで取れていなかったようです（というのは後でわかって、しばらくは「こわれた tar.gz からデータを修復する問題に違いない」と思って時間をかけていました）。とはいえ、 xxx.txt というファイルが得られ、最初のフラグ SECCON{assemble this circuit} が得られました。一緒に xxx.jpg というファイルが有るらしいということはわかったのですが、この時点ではデータは得られず、死んでいました。

ずっと後になって、forで256Byte吸っていたのを、while で無限に吸えば 32KB データが出てくることがわかり（このとき、256 Byte しか詰まってないと思っていた。なんか直感的にちっちゃいROMだしそうなのかな、と思っていた）、改めて tar.gz を伸張すると、下のような回路図が xxx.jpg であり、その回路を制御する Raspberry Pi 用のプログラム xxx.py が存在することがわかったのですが、これが終了10分前とかで、回路の作成、Flagの推測が間に合いませんでした。ちなみに、回路は乱数を生成するようなものらしいのですが、詳しくは多分師匠かthrustくんが書いてくれます。

完全に私の落ち度で100pt を失ってしまい、チームメイトには申し訳ないです。

3 Bad USB を拾うやつ

なんか秘密結社のうっかりさんが空港でひっかかって、あやしげなチップを押収したので解析せよとのことでした。これが Attiny13a です。これはどのチームも解いていたのですが、理由は簡単で、配布された資料の手順を愚直に実行すれば（Attiny13aをPCに接続しよう！　プログラムを書き込もう！　どんな動きをするかみてみよう！などが詳しく説明されていました）、FLAGが見える仕組みでした。

Attiny13a用のプログラムを解析する方法もあったようですが、これをやっているチームはいませんでした。

とにかく、ちゃんと手順通りにやって 100pt 入れました。PS/2 ←→ USB をしてくれる機器が不調で、機器を交換してもらってうまくいきました。

4 リモコンを妨害する奴

リモコンが効かなくなる現象を解消するという仕事を受けました。

実際にやることは、Raspberry Piの「赤外線受光モジュール」のようなものを用いて、リモコンを妨害している光を受け取り、それを解析することのようでした。

モジュールが死んでいてたり、回路が難しかったりしましたが、運営のHINTをたくさんうけ、光を解析することには成功していたようです。あとはDecodeだけのようでしたが、どの規格のものかわからず、Decodeできていなかったというのがつらいところです（これは師匠がきっと書いてくれる）。

おわり

というような問題を解いて5時間。スコアボードは以下のようになっていました。

f:id:Furutsuki:20160717210438p:plain

感想

1（First Blood）, 2[a], 3番の問題を解き 310 pts だった我々 insecure は、堂々の優勝となりました。まさか優勝できるとは、まるで思っていなかったので、（もう少しで解ける問題があったと悔しい思いをしながらも）とても嬉しかったです。チームメイトのそれぞれが活躍しており、いいバランスだったと思います。あと5分あれば、もう100点取れていたし、さらに10分もあれば全完できていたな……と思いました。そこは今後の課題ですね。

優勝したので、1月末に開催される SECCON Intercollege に今年度も出場できます。今年は、出場が決まった一番最初のチームになりました。やったー。

さらに、副賞として、Raspberry Piでめっちゃ遊べる本（英語。著者のサイン入り）を頂きました。部活で活用できたらいいな……英語読めないな……。