who3411のブログ

情報系の勉強やイベントの参加に関するブログ(をしたい)です。

SecHack365 2019参加記

はじめに

色々と辛いことがあって1年以上ブログを投稿していませんでしたが、2019年度のSechack365の表現駆動コースに参加しました。後々話していくのですが、私は最終的に以下の2つの成果物に参加していました。

  • クエッーション ~ 位置情報 x 質問 ~
  • ぼったくりガード 〜ぼったくり被害を防ぐためのシステム〜

2019年度の成果物は下のリンクにあるので、よろしければご覧ください。

sechack365.nict.go.jp

参加してみて、色々と思ったこと・後悔していることがあるので、それもまとめて書いてみようと思います。この記事が公開される頃には、既に2020年度の応募の最中ではありますが、応募しようとしている人、どのコースに参加しようかなどを考えている人は、よろしければご一読ください。

なお、SecHack365に関する詳しい説明などは公式サイトをご覧ください。リンクを下に貼っておきます。

sechack365.nict.go.jp

注意点

  • 全てメモや写真を頼りにこのブログを書いているので、色々とうろ覚えの箇所があるとは思いますがご了承ください。
  • 正直どこまで書いていいのかわからないので、簡単な内容は書きますが、実際に行ったことの詳細は書かないようにしています。
  • 参加を悩んでいる状態でこの記事を読んでいる方は、「参加を悩んでいる方へ」を読むことをお勧めします。それ以外の方は、「参加を悩んでいる方へ」を読み飛ばしてもらって構いません。

参加を悩んでいる方へ

SecHack365 2020では、どうやら昨年と同様に5つのコースがあります。詳しくは、以下のリンクをご確認ください。

sechack365.nict.go.jp

リンク先を見る限り、各コースによって様々な特色があると思いますが、コースを選択する際は十分に考えた上で選択するようにしましょう。「何当たり前のことを言ってるんだ」と思われるかもしれませんが、私はコース選択を誤って、応募時点でやりたかったことを何一つできないままSecHack365 2019が終了しました。そもそも1人で開発しようと思っていたにも関わらず、コース概要をよく読まずに(詳しくは「応募」に書きますが)表現駆動コースを選択してしまいました。

ただ、コース選択を誤ったからといって全く楽しくなかったわけではありません。結局複数人で開発を行いましたが、私は普段1人でしか開発を行ってこなかったので、複数人で開発するという経験はかなり新鮮なものでした。また、SecHack365自体に関しても、様々なアイデア・課題を元にものづくりを取り組んでいて、多くの刺激をもらえる場所だと思います。

長くなりましたが、結局言いたいこととしては、

  • 「とりあえず応募してみよう」はやめた方がいい。
  • 応募するならちゃんと考えた上でコースを選択した方が良い。
  • もしコースを誤ったら、誤ったなりに楽しめるよう努力する。

くらいでしょうか。ちなみに、「興味あるならとりあえず応募しよう!」とよく言われるかもしれませんが、SecHack365において、個人的にそれはオススメできません。私みたいに、「コース選択ミスって最初にやりたいこと何1つできなかった」となっても良いならとりあえず応募しても良いとは思いますが…

1年の主な流れ

1年間何をやってきたか、各イベントごとに振り返ろうと思います。

応募

元々2018年度にも応募していたのですが、落ちてしまったので、改めて応募しました。この時、コース概要のような専用のページはなく、本当に一言説明みたいなものが開催概要ページにあり、詳しい概要は応募後に送られてくる課題フォームにありました。

とりあえず概要を見て、2018年度は3コースだったのに対して、2019年度は5コースになっていました。それで改めてコースを選びなおしていたのですが、修了生の方やトレーナーの方、指導教員などから意見を聞き、数日間考え抜いた結果、開発駆動コースに行こうと考えました。そして課題フォームに個人情報を書いてから愕然としました。私のやりたかった分野にマッチするトレーナーが開発駆動コースにはいませんでした。(2020年度のコース概要の開発駆動コースに書いてあるような内容が、2019年度は課題フォームの個人情報入力後にありました。個人情報を書かないと読めない場所に書くの本当にやめてほしいです)

多分この時点で応募締め切りまで残り1〜2日だったと思います。結局焦って、2018年度のSecHack365のイメージを持ったまま表現駆動コースに応募しました。(記憶通りであれば2018年度は個人での開発も行えたはず…)神奈川回後で指摘されたのですが、この時課題フォームに書かれていたらしい「グループワークで行う」という記載を完全に見逃していました。

応募で言えることとしては、

  • 過去に応募したことのある人は、再度コース概要を見返した方が良い。
  • 今年はコース概要ページがあるので良いが、本当にコース概要はちゃんと見た方が良い。

と言った感じです。ほんと1年前の自分に言えることなら言ってやりたいです…。

結局、なんだかんだあった応募ですが、結局合格して参加することとなりました。

神奈川回(5/17〜5/19)

合格してしばらくしてオンライン上で今後に関する話などもあり、神奈川へ向かいました。ちなみに、表現駆動コースでは前もってオンライン上で集まってグループワークがありました。グループワークの内容としては、複数のテーマから1つを選択して、それに対する課題と、解決するためのサービス・システムを提案するというものです。オンライン上で集まってグループワークを行うのは初めてで、またこれまで使用したことのないツールを使用したので、色々と新鮮だった記憶があります。

今までオンライン上でしか認知してなかった人たちを現地で見ると、「ようやく始まったなぁ」なんてことを思ってました。結局3日間は、主に以下のようなことをやったと思います。

多分アイデアソンなどは他の方が書かれていると思うので、コースワークについて書きます。アイデアソンに関して言えることがあるとすれば、あまり知識のない状態でグループの方と話をしてしまった申し訳ない気持ちになったくらいです。コースワークでは、予めオンライン上でグループワークを行った内容を発表するものでした。課題や解決策がチームによって違っていましたが、「あーそういう考え方もあるんだなぁ」と思いながら聞いていました。

あと記憶に残っていることとしては、神奈川回に表現駆動コース内で、「最終的に3人以上のグループで開発を行うこと」と言われたことですね。この時に私は絶望したと同時に、SecHackに対するモチベがマイナスくらいまで下がったことを鮮明に覚えています。今思えば、このせいで北海道回以降に多数の方へご迷惑をおかけしたと思います。本当に申し訳ありませんでした。

まとめとしては、以下のような感じです。

  • SecHack365始まったな感じがした。
  • 初めてのコースワークなどはそれなりに楽しめた。
  • 楽しんだ後、表現駆動コースを選択したことに対して(勝手に)絶望した。

北海道回(6/28〜6/30)

f:id:who3411:20200605155147j:plain

そんなこんなで完全にモチベをなくした状態になったまま北海道回へ。北海道回では、グループをシャッフルした状態で、もう一度神奈川回までと同じようなグループワークを行いました。流石にグループの方々に迷惑だと思いモチベをある程度取り戻してはいたのですが、この時のグループの皆様には本当に多大なご迷惑をおかけしたと思います。

グループワークでもかなり無理くりな課題を設定してしまい、更にはその解決策も滅茶苦茶になってしまいました。今となっては本当に反省しています。この経験から、福岡回以降はかなりアイデア出しなどに関して消極的になりましたが、今思えばそれはそれで反省しています。

北海道回の3日間は、主に以下のようなことをやったと思います。

1日目のデータセンター見学はかなり記憶に残っています。データセンターのメモを見返してみたら、メモ欄が全て埋まっていて、更に残りの白い部分もかなり埋まっていました。詳しくは書かない方が良さそうなので省略しますが、とにかくすごかったです。

あと、2日目にワークショップが開かれたと思います。ワークショップではトレーナーの方々が用意した内容から、自分の受けたい内容を選択するものでした。私はネットワークや低レイヤーが好きなのでその関連を1つと、未だになれないプロジェクト開発関連のものを1つ選択しました。どちらもかなり面白かったと思います。

コースワークですが、基本的には神奈川回と同じことを違うグループで行うというものでした。ただ、その時に発表方法を意識したり、ポスターを用意したりと神奈川回とは違うこともいくつかありました。2分という短い時間で課題や解決策に関する発表を行うのはかなり難しかった記憶があります。

まとめとしては、以下のような感じです。

  • コースワークですごい反省した。
  • データセンターの見学楽しかった。
  • コースワークは神奈川回と同じ内容を違うグループで行った。

福岡回(8/21〜8/23)

f:id:who3411:20200605155104j:plain

福岡回でも、オンラインではこれまでと同様、グループを変更して新しく課題/解決を考えました。ここまでくると、思っていたより新しい課題を見つけるのが大変だった記憶があります。あと、福岡回は中間発表があるので、他コースではこれまでの進捗を元に色々と準備されていたようですが、表現駆動コースは北海道回後から福岡回までの内容だけで中間発表を行いました。

ただ、表現駆動コースでは、福岡回からは3人以上のグループを自分たちで作って、そグループを元に成果発表まで開発を行っていくことになります。なので、それぞれがどのような課題を元にグループを作るのか、そもそも仲間外れになったらどうしようか、みたいな話が流れてたりしました。

福岡回の3日間は、主に以下のようなことをやったと思います。

  • 1日目: 株式会社ヌーラボの見学
  • 2日目: 中間発表
  • 3日目: コースワーク

1日目のヌーラボさんの見学は、失礼を承知で言ってしまうと実はあまり記憶に残っていません。というか、正確にはヌーラボさん自身ではなく、発表内容の方が記憶に残っています。話の中では、運用中に受けたという攻撃の話もあって、個人的には特にそこが新鮮でした。演習でそのようなことはやったのですが、やはり運用中に実際に受けたという攻撃の話は面白いです。

2日目の中間発表は、ようやく他のコースの人たちが何をやっているのかがわかるようになるので、非常に面白かったです。(この辺りにならないと他のコースの人たちが何やってるかがわからないのは正直どうかと思いますが…)5コースの内容を聞いていて、個人的には学習駆動コースや開発駆動コースに憧れを持ちました。低レイヤーの話とか出てくると面白く感じてしまう奴です。あと、改めてコース選択ミスったなぁと思いました。

コースワークでは、成果発表まで課題に取り組むためのグループ作りがありました。おそらく、この時点で一度グループが決まったら、少し移動はあるかもしれませんが、基本的にはそのまま最終発表まで行く形になると思います。今思えば、何が何でもこの時点で自分のやりたいことを元にグループを集めるべきでした。が、結局コース内に同じ課題に興味を持ちそうな人がおらず(実際誰も興味を示しませんでした。多分今その話をしても覚えてない人のが多いと思います。)、色々とあってクエッーションとぼったくりガードに参加することになりました。つまり、私のやりたいことは一切できないことが確定した瞬間でもあります。

まとめとしては、以下のような感じです。

  • ヌーラボさんの発表が興味深かった。
  • 中間発表で5コースの話を聞けて面白かった。
  • 成果発表まで2つのグループで取り組むことになった。

宮城回(10/4〜10/6)

f:id:who3411:20200605155021j:plain

2つのグループで取り組むことになったわけですが、宮城回時点ではそこまで忙しくありませんでした。というのも、ぼったくりガードはすでに課題や解決策がほぼ決まっていて、あとはそれに沿ってサービスを作成するのが主な作業になったからです。そんなわけで、私はクエッーションの方に積極的に参加していました。

この時点では、まだ何をやりたいかも明確に決まっておらず、ぼんやりと「地方と教育とITを掛け合わせた何かをやりたい」といった感じでした。それがいつの間にか色々と変化していき、最終的には位置情報と質問をベースにしたシステムを作りたいと考えるようになっていきました。気づいたらグループの方がクエッーションという名前とロゴを作ってくださり、なんだかんだやる気になって来たところで宮城回に入ったと記憶しています。

宮城回の3日間は、主に以下のようなことをやったと思います。

この辺りまで来ると、コースワークや発表が中心になって来て、他の方の発表をみては焦る状態だったと思います。焦る原因は明らかに自分たちの進捗が遅れているからなのですが、自分たちは福岡回から、他コースの方は神奈川回から、それぞれ続けているから仕方ないかなぁなんて楽観視してました。(もちろん他コースの方も色々と苦戦しているのだと思っていたのですが、楽観視でもしないと焦りにやられてしまいそうだったので…)

宮城回時点では、私の参加していた2つのグループはそれぞれ以下のような状態でした。

  • ぼったくりガード: 簡単なPoCもできていて、少なくとも見た目は見せられる状態
  • クエッーション: アイデアだけできていて、まだイメージを図にしていただけの状態

クエッーションが明らかに恐ろしい状態であることがわかると思います。「正直これ最終発表までにシステムが完成するのか…?」と思っていました。また、このタイミングでクエッーションのアイデアに関して、トレーナーの方にアイデア出しを手伝ってもらっていたのですが、それでアイデアが発散してしまいました。それで、また一からアイデア出しを行う状態に戻ったのですが、それもあってさらに焦っていました。今思えば、当時はアイデアがうまく形になっていなかったから発散して当然か…と感じています。

あと、これは(悪い意味で)一番印象に残っているのですが、宮城回ではNight Challengeなるものがありました。表現駆動コースを2つのグループに分けて、それぞれで1つの制作物を宮城回中に作成する、というものです。結果、表現駆動コースのほぼ全員がホテルのロビーで徹夜する羽目になったのですが、なぜこのようなイベントがあるのか、今になっても理解できません。あれのせいで私は家に帰ってから体調崩して1週間以上寝込んでました。あれだけは本当に許さない。

まとめとしては、以下のような感じです。

  • 他コースの人の発表をみて焦る。
  • オフラインでも発表が増えて来て焦る。
  • 思っていたよりもクエッーションが遅れていることを知る。

愛媛回(11/29〜12/1)

f:id:who3411:20200605154902j:plain

宮城回でただでさえ他トレーニーよりも遅れている状態で、さらにアイデアが発散してしまった状態で、この時期から沖縄回までは焦りに焦っていたと記憶しています。グループ内でも流石にやばいのではないかとなり、この頃からは1週間に2回集まってアイデアを固めていたと思います。なんか表現するというか思索してる気がする…

愛媛回では、スライドとポスターの両方を提出する必要があり、これらを提出するためにはアイデアが固まりきっていないのでアイデア出しを多く行っていたのですが、なんだかんだまとめて行けたと思います。(締切駆動開発になっていることは今更です…)あと私事ですが、この時期は学会に参加していた時期なので、あまりSechack365側に参加できていませんでした。申し訳ありません。

愛媛回の3日間は、主に以下のようなことをやったと思います。

  • 1日目: デモ+ポスター発表
  • 2日目: スライド発表
  • 3日目: コースワーク

1日目と2日目に発表があることから分かる通り、もう愛媛回まで来ると、本来であれば自身の制作物をまとめる状態に来ています。(実際、愛媛回は沖縄回での発表練習と言われます。)そのような状態で、私の参加しているグループは、

  • ぼったくりガード: 宮城回で指摘された内容を治して、かついくつか機能を追加した状態
  • クエッーション: アイデアが完全にはまとまっておらず、簡単なPoCだけできている状態

といった感じでした。どうみてもクエッーションやばいですね…。とはいえ、宮城回ではアイデアをかなりボコボコにされていたのですが、愛媛回ではあまり色々と言われなかったので、アイデアがまとまって来たのかなぁと感じました。(優しくされただけの可能性もありますが…)

あと、主な内容には書いていないのですが、個人的には2日目の夜にあった落語がすごく面白かったです。普通の落語とは違い、PCなどを使っていたのですが、かなり新鮮でした。多分愛媛回で一番楽しかった時間だと思います。

まとめとしては、以下のような感じです。

  • クエッーションやばい。
  • 2日間の発表で、いよいよ成果発表が近づいていることを感じ始める。
  • 落語楽しかった。

沖縄回(1/31〜2/2)

f:id:who3411:20200605154811j:plain

ここまで来ると、多分普通は成果発表に向けての最終調整とかスライドの手直しだと思うのですが、相変わらずクエッーションは大変なことになってました。また、この時にぼったくりガードの方も少し慌ただしくなってきて、両方を並行して行うので大変だった記憶があります。

クエッーションは、最終的に今思い描いている実装を成果発表までに全て行うのが難しいという判断となり、とりあえずコンセプトが伝わる範囲での作成をしました。また、これまでうやむやにしていた部分の内容も詳しく考え直し、実装とスライド作りに追われていました。

ぼったくりガードは、実装する内容が増えたので、基本的にはそれに対応できるように機能を追加・修正していたと思います。ただ、作品紹介ページを見てもらえば分かると思いますが、ぼったくりガードは8人グループだったこともあり、途中から私のやった内容がどのようにグループ内の実装に影響を与えていたのかがわかっていないという状況にありました。

そんなこんなで色々と大変だった沖縄回前でしたが、沖縄回の3日間は、主に以下のようなことをやったと思います。

沖縄回では2日連続で成果発表がありました。中間発表では1作品5分だったのですが、成果発表では1作品20分も時間があって、自作品についてはじっくりと話すことができ、他作品についてはかなりじっくりと話を聞くことができました。作品によって見せ方や発表方法に工夫があるように見えて、正直かなり面白かったし刺激になりました。多分正確なイメージではないのですが、個人的にはかなりふんわりとした学会みたいなイメージを持ちました。

成果発表後の3日目には、レクリエーションとして斎場御嶽(せーふぁーうたき)に行きました。ここでようやく沖縄にいるような暑さを感じることができたました。(成果発表中の施設は、沖縄とは思えないくらい涼しかったです)一通り回って、かなりリフレッシュになったと思います。

まとめとしては、以下のような感じです。

  • 2日間かけて成果発表を話したり聞いたりした。
  • どの作品も様々な方面で工夫が見られて面白かった。
  • 成果発表を聞くだけでもかなり刺激になった。

成果発表会

本当は沖縄回の後に一般公開用の成果発表会もあったのですが、残念ながら開催延期になってしまいました。こんなご時世なので仕方ないですね…。ちなみに作品一覧のポスターは成果発表会に向けて作成したもので、結局見せることのないままSecHack365 2019としての事業は終了した感じです。

SecHack365を終えて(?)

f:id:who3411:20200605203957j:plain

成果発表会も延期となってしまい、なんだか終了したという実感の湧かないまま時間が過ぎていますが、私にとってSecHack365が終わったかというと、あまりそういうイメージもありません。というのも、いまだにクエッーションは制作を続けています。期間中は1週間に2回ほど行っていたオンラインでのミーティングは1週間に1回となり、クエッーションメンバー全員何かと忙しいので、かなりゆっくりですが…。

まだまだ延期になった成果発表会もあるので、これからもゆっくりと時間の許す限りは作り続けて行きたいと思います。

あといくつかリアルやtwitterなどを経由して質問されたことがあるので、この場で答えておきます。

旅行楽しい?

そもそも旅行感全くないです。確かにいろんな場所に行っている感じはありますが、別に行ったからといって観光できるわけでもないです。強いて言えばご当地名物食べてお土産が買えるくらいでしょうか。旅行目的で応募しようと思ってるなら応募しない方が良いと思います。

どのコースがお勧め?

人によるのでなんとも言えませんが、とりあえずチーム開発したくないなら表現駆動コース以外で、チーム開発をしたいなら表現駆動コースです。

セキュリティ強くなった?

正直応募前とほとんど変わらないと思います。元々セキュリティ系の研究室なのと、情報処理安全確保支援士試験を合格しているので、知識だけはあると思います。(実装力はないので詳しい話になるとさっぱりですが…)ただ明確に変わった部分として、法律面はそれなりに変わったと思います。詳しくは言えませんが、法律に関するセキュリティのお話もSecHack365内でありました。

技術力ないとダメ?

これはコースによると思いますが、チーム開発であればマネージャーのような役割をこなすことができるのではないでしょうか。また、研究駆動コースのような方面であれば、実装よりも仮説検証などがメインになると思う(研究駆動コースを受けてないのでこれはかなり適当な考えです)ので、絶対にこれだけ技術力がないとダメ!みたいなものはないと思います。結局、必要になればやらざるを得ないので、人に意見を聞きながらでも学習できるような意欲があればいいのではないかと思います。

おわりに

すごいざっくりと、そしてだらだらと1年間を振り返って見ましたが、やはり後悔が大きいですね。特にコースの選択を間違えたことはいまだに後悔していて、できることなら去年からコースを選択し直してやり直してみたいくらいです。とはいえ、表現駆動コースが悪かったというわけではなくて、表現駆動コースだったからこそ、そもそもやろうと思っていなかった複数人の開発ができたという面はあるので、そういう意味では貴重な時間を過ごすことができたと思います。単に私と表現駆動コースの相性が悪かっただけだと思ってます。

1年間という長い時間を学業や仕事と並行して行う必要があるので、もちろん大変ではあるのですが、やりたいことがあって、なおかつSecHack365に興味があれば応募してみると良いと思います。ただ、コース選択はくれぐれもお気をつけください…。

これまで調べてきたファジングの話

この記事は静大情報LT大会(IT) Advent Calendar 2018の21日目の記事になります。

adventar.org

はじめに

今年度は、静大情報LTで情報危機管理コンテストやボゴソートの話をしていたものです。

最近はまともなアウトプットを一切行っていなかったので、この機会にファジングに関する話をしようと思います。また折角ブログとして投稿するので、5分では語りきれないような内容について書こうと思います。

ちなみに、この記事にプログラムはほとんど出てきません。プログラムを読みたい、という方がいらっしゃいましたら、先日ブログに書いた、こちらの記事を読むことをお勧めします。

who3411.hatenablog.com

注意

注意深く調べてはいますが、この記事の情報が必ずしも全て正しいわけではありません。予めご了承した上で読んでいただければと思います。

ファジング

ファジングとは、プログラムに対して自動的に生成した大量のデータを送ることで、データを送ったプログラム側の応答や挙動を確認する、脆弱性診断やテスト手法の1つです。また、ファジングを行うためのソフトウェアやツールのことを、ファザーと言います。ファザーには、American Fuzzy LoplibFuzzerなどがあり、多くの脆弱性が発見されたりしています。

近年の出来事だと、あらかじめ用意されたプログラムの脆弱性を発見・パッチ記述・攻撃コード作成といった流れを自動化するコンテストであるDARPA Cyber Grand Challengeにおいて、決勝まで進出したDrillerAFLFastなどがファジングを使用しています。またファジングと機械学習を組み合わせることで、ファジングの性能をあげる研究も行われています。

このようなファジングに関して、今回は歴史や動向を話すことができたらと思います。

ファジングの歴史

1990年にMillerらによって発表された論文時点では、大量に生成したデータを用いて、クラッシュやハングを検出するのみでした。大量のデータを生成するプログラムと、対話型プログラム用に記事デバイスファイルを作成するプログラムを使用することで、様々なプログラムに対してファジングを実施するというものでした。1995年の論文では、GUIベースのツールや、ネットワーク、システムライブラリなどに対してファジングをかけた結果が記載されました。

1998年、フィンランドのオウル大学でPROTOSプロジェクトが行われました。このプロジェクトでは、プロトコル脆弱性に関するファジングを行うもので、多くの脆弱性を発見することに成功しました。PROTOSプロジェクトは、2002年にCodenomiconという商用のファジングに関する会社の設立まで行く様になりました。Codenomicon社は、OpenSSLに含まれていた脆弱性であるHeartbleedを検出するなど、多くの活躍をしています。

Codenomicon社が設立された2002年、Dave AitelがSPIKEという、オープンソースプロトコルのファジングを行うことができるツールを開発・公表しました。SPIKEでは、ブロックサイズ情報を記録しておくことで、多くのヘッダがネストされるネットワークのようなシステムに対しても、ファジングを行うことができる様になっています。またDave Aitelは、sharefuzzという環境変数に対するファジングも公表しました。初期にはプログラムの入力のみ対象にしていたファジングが、ネットワークやプロトコル環境変数など、だんだん範囲が広がって行く様になりました。

その後、ファイルやブラウザなど、だんだんと対象とする範囲が広がっていきながら、多くのファジングが登場する様になっていきます。

ファジングの分類

ファジングでは、主に3つの視点での分類が存在します。

  1. 入力をどの様に生成するか
  2. プログラムに入力する際の構造を認識しているか
  3. プログラム自体の構造を認識しているか

以降、それぞれの視点での説明を行っていきます。

入力の生成方法

入力の生成方法では、主に以下の2つが存在します。

  • 突然変異ベース: 入力の元となるようなデータであるシードを突然変異させて行くことで、その突然変異したものを入力データとして利用する方法(ex: シード"hello" →突然変異→ "hellm")。この方法の場合、シードの中身にあるデータによって、脆弱性の発見率が左右する場合があります。
  • 生成ベース: 何も情報がない状態か、入力のモデル(最初の2バイトは数字、続く4バイトは文字列…といった情報が続いたもの)がある状態から入力データを生成する方法。この方法の場合、突然変異ベースのシードを必要としないので、脆弱性の発見率を左右するようなものはありません。

また場合によっては、突然変異ベースと生成ベースを組み合わせた手法も存在します。

プログラムに入力する構造の認識

プログラムに入力する構造の認識の有無によって、以下の2つに分かれます。

  • smart fuzzer(スマートファザー): 入力のモデル(最初の2バイトは数字、続く4バイトは文字列…といった情報が続いたもの)を使用しながらファジングを行う手法。ヘッダが多く使用されるネットワークプロトコルなどに対しては有効な手法ですが、プログラムごとに入力モデルを用意する必要があり、コストがかかります。
  • dumb fuzzer(ダムファザー?): 入力モデルを使用せずにファジングを行う手法。入力モデルがない分、有効となる入力を生成できる可能性は低くなりますが、汎用的にファジングを行うことができます。

プログラム自体の構造の認識

プログラム自体の構造の認識では、主に以下の3つが存在します。

  • ホワイトボックス: プログラムの内部構造を知っている状態で行うファジング。到達しにくい場所にある脆弱性を発見することもできますが、プログラムの分析自体に時間がかかる可能性が高いです。
  • グレーボックス: プログラムの内部構造は不明だが、プログラムの動作などを監視して情報を収集しながら行うファジング。ホワイトボックスと違って内部構造はわかりませんが、プログラムの動作を介して、ある程度プログラムにあった入力を生成することができます。
  • ブラックボックス: プログラムの内部構造を全く知らない状態で行うファジング。グレーボックスと違って情報収集も行わないので、完全にランダムな入力データの生成を行いますが、並列化や高速化が可能です。

様々なファジング

近年、様々なファジングが提案・発表されています。ここでは、その一部について見ていこうと思います。

オープンソース・製品

オープンソースや製品化されているファザーは多く存在しますが、4つのファザーについて話したいと思います。

Taof

Windows上で動作する、HTTPサーバやFTPサーバといったネットワークを介するファジングを行います。クライアントとサーバの間に立ってデータ収集を行うことで、情報を収集します。

Peach

ソフトウェア全般に対してファジングを行うことができます。XMLファイルを用いて、ファジングの対象となる値の形式などを決めることで入力モデルを作成し、そのモデルに沿った値を生成していきます。こうすることで、ヘッダのような、予め形式の決まっているプログラムに対してのファジングを行うことが可能となっています。

AFL(American Fuzzy Lop)

ファジングを行うプログラムのコンパイル時に計測用のコードを埋め込み、ファジングの実行時には、埋め込んだ計測用コードによって情報を収集します。計測用コードでは、「どの計測用コードからどの計測用コードへ移動したか」を見ることで、新しい遷移があったかを検出します。(ex: これまではA→Bの遷移しかなかったが、新しく生成した入力ではA→Cへ遷移した)

AFLの簡単な動作説明は以下の通りです。

  1. シードとなる値を複数用意し、その中から1つ選択する。
  2. 選択したシードを突然変異させ、プログラムへの入力する。
  3. プログラム実行後、新しい場所へ遷移した入力などがあれば、その入力をシードに追加する。

libFuzzer

libFuzzerは、AFLと同様、遷移に関する情報を利用したカバレッジベースのファジングを行います。またAFLとの互換性もあり、例えばAFLである程度プログラムに対してファジングを行った後で、libFuzzerで同じプログラムのファジングを途中から行うことができます。

libFuzzerでは、通常のファジングだけでなく、特定の関数のみを対象としたファジングを行うことができます。この手法はメモリ内ファジング(In Memory Fuzzing)と呼ばれており、特定の関数をテストするには持ってつけの機能と言えます。

AFLの派生

AFLでは、AFLを利用した多くのファザーが存在します。ここでは、そのようなファザーについて話していきます。

ちなみに、AFLはC言語で記述されているのですが、様々な言語で使えるようになっているようです。例えば、KelinciはAFLをJavaで使えるようにしたもので、afl.rsはAFLをRustで使える様にしたものです。

AFLFast

AFLでは、1つのシードを選択すると、そのシードを元に突然変異を複数回実行します。またシードはキュー(FIFO)の構造になっているため、後ろの方に脆弱性を発見しやすいようなシードがあったとしても、選ばれるのはかなり先のことになってしまいます。

AFLFastでは、まずシードを選択してから突然変異を実行する回数を調整するようにしました。基本的にはAFLよりも突然変異回数を少なくなるにしており、6種類の実行回数の計算式が存在します。またシードの選択方法は、他のシードが遷移していない場所に遷移しているパスや、選択回数の少ないシードを優先的に選択するようにしました。

結果として、AFLFastは前期のDARPA CGCで決勝まで進出していることからも、この方法は有効だったと言えます。

AFLGo

AFLGoでは、現在地にとなる場所と目的地となる場所の距離を求めることで、目的地まで到達することを目標としたものです。関数の呼び出し関係を表すコールグラフや、プログラムの全経路をグラフ化した制御フローグラフなどを用いることで、距離の計算を行います。

aflpin

aflpinは、計測用コードを埋め込んでいない実行ファイルに対して、Intel Pinを利用することでAFLの様にファジングを実行しようというものです。ですが、近年ではaflpinがうまく動かないことが増えてきて、代わりにafl-pinを使用する必要が出てきました。

CollAFL

CollAFLは、AFLで収集する情報をより正確に提供し、シード選択時ポリシーを改良したファザーです。実は、AFLでは、対象となるプログラムによっては100%正確な遷移情報を収集することができません。この問題は、情報収集時にハッシュ衝突が発生するからです。

それに対して、CollAFLでは、貪欲法を用いることで、全てのハッシュが衝突しないようにしておきます。またシード選択については、AFLのキュー形式ではなく、メモリアクセス操作が多い入力などを優先して選択する様にしています。

他解析手法との組み合わせ

シンボリック実行やテイント解析など、他の解析手法と組み合わせたファザーが存在します。ここでは、それらを紹介していきます。なおシンボリック実行とテイント解析については、以下の通りです。

  • シンボリック実行: プログラムの変数や入力を一つのシンボルとして扱うことで、実行パスの制約を維持する手法です。シンボリック実行やコンコリック実行については、このスライドが凄く分かりやすかったです。なおコンコリック実行は、シンボリック実行で求めた制約を元に、実際に値を生成・入力する手法です。
    • 下の図のように、プログラムをパスとして考えてみましょう。右図の緑の部分にいきたいとします。その時、それぞれの緑の部分に行くために必要となる論理式は緑の部分に記述されています。この論理式通りの値を出力することができたら、全ての箇所に遷移することができます。
    • 注意点として、シンボリック実行やコンコリック実行では、時間がかかることはもちろん、条件式が多すぎるとパスが多くなりすぎるという問題もあります。

f:id:who3411:20181221193915p:plain
プログラムとパスの関係

  • テイント解析: パケットやファイル、標準入力といった外部から入力される値が格納されているメモリ番地を、「汚染された」状態とみなして、その伝搬を追跡する手法です。
    • 「汚染された」データと「汚染されていない」データを計算した時、計算結果も「汚染された」データとなっていきます。
    • 「汚染された」データ周りの命令が脆弱性に繋がりそうか確認すれば、入力データ周りの情報収集を行うことができます。

Driller

Drillerは、ファジングとコンコリック実行を交互に行うことで、深い位置にある脆弱性を発見するためのファザーです。具体的な手順は以下の通りになっています。

  1. テストケースを入力
  2. ファジングを実施し、新たな遷移が不可能となった時に手順3へ
  3. 不可能となった区間に対してコンコリック実行を実施
  4. 手順3の実行結果から得られた値をファジングの入力へ
  5. 手順2から手順4を繰り返す

BuzzFuzz

BuzzFuzzは、動的テイント解析を使用したファザーです。初期準備として、シードの値を入力としてプログラムを実行し、その際に動的テイント解析を利用することで、影響を与える入力バイトを記録します。そして、この時に得た入力バイトの位置を記憶しておくことで、ファジングによって変化させる値の位置を決定します。

VUzzer

VUzzerは、静的解析と動的解析を行うことで、効率的に入力データを生成するファザーです。具体的な手順は以下の通りです。

  1. 実行ファイルを静的解析する。
    • アセンブリの"cmp"命令や"lea"命令に当たる部分を調査する。
  2. これまで得た情報を元に入力を生成し、実行ファイルを実行する。
  3. 手順2の実行時に得られた情報を元に、次に実施する変異戦略などを求めるための計算を行う。
  4. 手順2に戻る

Munch

Munchは、ファジングとシンボリック実行を組み合わせたファザーです。ファジング→シンボリック実行の順に実行するFSモードと、シンボリック実行→ファジングの順に実行するSFモードの2つが存在します。

fFuzz

fFuzzは、ファジングとシンボリック実行を組み合わせたファザーです。fFuzzでは、以下の2つの最適化手法を用いることで、脆弱性の発見を最適化します。

  1. 冗長なテストケースの破棄
  2. パス爆発の発生を抑える選択的シンボリック実行エンジン

QSYM

QSYMは、ファジングと組み合わせることを前提として、コンコリック実行のパフォーマンスのボトルネックとなる部分を分析し、ファジングのサポートに適したコンコリック実行の作成を行っています。具体的には、命令レベルでシンボリック実行を行ったり、繰り返し実行しているブロックを検出して、その部分をコンコリック実行の対象から取り除いたりします。

その他の手法

ファジングでは、上であげた以外にも、様々な種類が存在します。ここでは、その他の手法を記載していきます。

kAFL

kAFLは、カーネルのファジングを可能としたファザーです(AFLの派生なのですが、カーネル関係として記述しています)。KVM上でファジングを行う対象となるカーネルを起動させて、QEMU上でファジングを実行します。入力した動作をトレースする方法として、Intel PTを使用しています。

正しく理解するには必要となる知識が多いのですが、今回は省略しています。わからない専門用語などがある方は「カーネルもファジングできるんだ〜」くらいに思っておいてもらえば幸いです。「カーネルって何?」という人がいれば調べてみましょう。

SlowFuzz

SlowFuzzは、脆弱性といったものを見つけるのではなく、実行速度が低下するような入力を見つけ出すファジングです。実行速度を遅くするため、シードを選択する際の方法としても、実行速度の遅くなるようんあものを優先的に追加するようにしています。SlowFuzzについては、先日あげた記事(「はじめに」と同じ記事です)で、AFLとIntel Pinを組み合わせた実装を行いましたので、よろしければそちらもご覧いただけると、より理解が深まるかと思います。

SemFuzz

SemFuzzは、gitログやCVEといった脆弱性に関係した情報を収集することで、攻撃用の入力を自動的に生成するファザーです。具体的な手順は以下の通りです。

  1. CVEとgitログを、自然言語処理を使って分析し、影響のあるバージョン、脆弱性の種類・機能、重要な変数、システムコールなどを抽出します。
  2. 対象のバージョンとなる仮想マシンを起動し、ファジング環境を準備します。
  3. 手順1で抽出した情報を利用して、シード入力を生成してファジングを実行します。

SSFuzzer

SSFuzzerは、AFLのような遷移情報や、Vuzzerのような比較命令に焦点を当てた方法とは異なり、関数呼び出しやメモリアクセスなどといった情報を利用することでファジングを行います。情報収集の際、プログラムをデコンパイルすることで、どのような関数が呼び出されているか、などを判定します。CVEの多い関数呼び出しを行っているもの、メモリアクセスの頻度が多いものなどは点数を大きくして、エラーハンドリングが行われているものは点数を小さくします。

Skyfire

Skyfireは、XMLファイルのような高度な構造化が必要とされるファイルを入力とするプログラムに対して、効率的なシードを生成する手法です。ファジングそのものではないのですが、入力生成まで行っていること、最終的にSkyfireとAFLを組み合わせた実験などを行っていることなどから、この場で紹介します。この手法では、確率文脈依存文法(PCSG)と呼ばれるものに学習を行わせて、学習した内容にしたがって入力を生成します。

ここでは、PCSGに代わって、ディープラーニングといった学習アルゴリズムを適用できる可能性をあげています。実際に機械学習を用いたファジングが出てきている現状では、Skyfireは改良できるかもしれません。

IOTFUZZER

IOTFUZZERは、IoTファームウェアのメモリ破損に関する脆弱性検出に特化したファジングです。モバイルアプリケーションでのやり取りを確認することで、ファジングを行います。IOTFUZZERの具体的な手順は以下の通りです。

  1. IoTのモバイルアプリケーションのうち、ネットワーク送信イベントをトリガします。
  2. 送信しているメッセージの中から、プログラム実行に関連する値を見つけ出します。
    • 実行ごとに変化している値などがあれば、その値をファジングによって変えることで脆弱性を発見できる可能性があります。
  3. 独自に定義したポリシーに従って手順2で見つけた値を突然変異させて、ファジングの対象とするデバイスに対して送信します。

FUZE

FUZEは、Use-After-Free(UAF)と呼ばれる脆弱性を評価するためのフレームワークで、内部的にファジングを使用しています。FUZEの実行途中において、UAFを引き起こすシステムコールを見つけ出す必要があるのですが、その時点でファジングが使用されます。

Angora

Angoraは、シンボリック実行を用いてパス制約を解決していた各手法に対して、シンボリック実行を用いずにパス制約を解決するものです。

関数呼び出しの引数を考慮(func(input[0])とfunc(input[1])を区別する)したり、条件文に使用される入力バイトを識別したりすることによって、ファジングとシンボリック実行を組み合わせる際の、シンボリック実行の代替となるようなシステムの開発を行っています。

T-Fuzz

T-Fuzzは、ファジングが調べることが難しい「str == ".PNG"」のような、いわゆるサニティチェックの条件文を取り除くことでファジングを行います。

実は、ファジングでは「str == ".PNG"」のような固定値との比較は非常に困難です。画像ファイルを処理するようなプログラムでは、画像のヘッダで使用されるマジックバイト(ファイルの先頭にある、その画像ファイルの種類を示す値)のチェック(サニティチェック)などが行われますが、ファジングはここを通るのが非常に難しいです。そこで、そのような部分は取り除いてしまおうというのが、T-Fuzzの考え方です。

ちなみにプログラムの取り除き方ですが、条件分岐を反転させることで取り除いています。

MoonShine

MoonShineは、プログラムからシステムコールのトレース結果を収集・抽出することで、プログラムにあったシードを自動的に生成する手法です。ファジングそのものではないのですが、ファジングに使用するシードは、ファジングの結果に大きく左右されるため、この場で紹介します。 MoonShineの主な手順は以下の通りです。

  1. トレースするプログラムを実行し、カバレッジ情報の記録やシステムコールのキャプチャを行う。
  2. 手順1で収集した情報からトレース結果を出力する。
  3. 手順2のトレース結果、および手順1のカバレッジ情報から、シードの蒸留を行います。
  4. 手順3で蒸留したシードをファジング実行時のシードとします。

Hawkeye

Hawkeyeは、AFLGoのような静的解析とファジングを組み合わせた手法について、望ましいと思われる特性を実現するための解決策を提案しています。

まず静的解析を用いてコールグラフと制御フローグラフを生成します。そこから、隣接する関数の距離、基本ブロック間の距離、目標位置に到達可能な関数などを計算します。

次にファジングを実施します。具体的な手順は以下の通りです。

  1. 静的解析で収集した情報やシードの優先順位に基づいて、突然変異するシードを選択します。
  2. シードの変異回数、変異戦略といったファジングを行うために必要な情報を決定したのち、突然変異を行います。
  3. 変異した値をプログラムの入力値として、目的のプログラムを実行します。
  4. 目標位置までとの距離などを計算し、シードの優先順位を決定します。
  5. 手順1に戻ります。

おわりに

まだまだ紹介したいものもあったのですが、残りは自分で調べてもらえると幸いです。(アドベントカレンダーの期限まで時間がなかった…)

今回は、詳しい中身を知らずとも、ある程度理解できる様に書いたつもりですが、わかりづらかったらすみません…。

ファジングは、海外では活発なイメージがあるのですが、なぜか日本ではあまり知られていないように思えます。私としては、もっと国内でファジングが流行ってくれたらなぁと思います。

12/21の本記事投稿時点で、次の記事は12/22のhi97_ia16さんによる記事です。お楽しみに!

American Fuzzy LopとIntel Pinを組み合わせたい

この記事はセキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2018の18日目の記事になります。

adventar.org

はじめに

セキュリティキャンプ全国大会2017で参加させていただいたwho3411です。最近ファザーであるAmerican Fuzzy Lopに、動的解析を組み合わせようとわちゃわちゃしていました。この記事は、最終的にAmerican Fuzzy Lopと動的バイナリ計測ツールであるIntel Pinを組み合わせて遊びたいと思います。なお、American Fuzzy Lopのコードリーディング時に使用していたhackmdを公開します。American Fuzzy Lopのコードリーディングをする方の助けになればと思います。(する方がいればの話ですが…)

AFL解析中…解析中 - HackMD

ファジング

American Fuzzy Lop(以下、AFLと呼ぶ)は、簡単に言うと、ファジングを行うための軽量なファザーです。この時点で、「ファジング?」「ファザー?」となると思うので説明しておくと、

  • ファジング: プログラムに対して自動的に生成した大量のデータを送って、送られたプログラム側の応答や挙動を確認することで、脆弱性診断やテストを行う手法
  • ファザー: ファジングを行うためのソフトウェア、またはツール

です。ファジングにはブラックボックス,グレーボックス、ホワイトボックスなど、様々な種類のファジングがありますが、AFLはグレーボックスになります。雑に説明すると、

  • ブラックボックス: プログラムの中身がわからない状態
  • グレーボックス: プログラムの中身はわからないけど、計測などを行って情報を収集する
  • ホワイトボックス: プログラムの中身がわかっている状態

みたいな感じです。AFLは、後述しますが、ファジングをかけるプログラム側に計測用のアセンブリを入れ込んで計測を行います。

動的バイナリ計測(Dynamic Binary Instrumentation)

Intel Pinは、簡単に言うと、動的バイナリ計測(Dynamic Binary Instrumentation, DBI)を行うことができるツールです。DBIは、実行中のプログラムに対してコードを挿入する技術ですが、Intel Pinでは、プログラムの実行中だけではなく、ロード時点でもコードを挿入することができます。

Intel Pinの、プログラムの実行中にコードを挿入する方法では、命令単位、基本ブロック単位、トレース単位の3種類があり、トレース単位が最も大きい単位になっています。なので、トレース単位は複数の基本ブロック単位を含んでいる可能性があり、また基本ブロック単位は複数の命令単位を含んでいる可能性があります。

Intel Pinは、多くのマニュアルコードがあり、例えばプログラム全体で実行された命令数をカウントするプログラムや、読み書きされたメモリアドレスをファイルに出力するプログラムなどがあります。詳しくは、Intel Pinのサイトを見ることをお勧めします。

AFLとIntel Pinを組み合わせる手順

今回は、AFLがプログラム中に入れ込んでいる計測用のアセンブリだけではなく、Intel Pinで収集した情報も含めてファジングを行うようにすることをゴールとしていきます。そのために、以下のような手順で進めていこうと思います。

  1. AFLがファジングを実行するまでの流れを知る
  2. AFLとIntel Pinを組み合わせる方法を探る
  3. 実際に組み合わせてみる

AFLがファジングを実行するまでの流れ

AFLでは、AFL用のコンパイラであるafl-gccコンパイルを行い、ファジング本体であるafl-fuzzでファジングを行います。afl-gccを読んで見ると、色々とコンパイルオプションをつけた上でgccコンパイルしているようでした。その中で重要なのが -B オプションで、これはgcc内部で実行されるプログラムである cppcc1 or cc1plusasldディレクトリを指定するオプションです。このオプションで、afl-gccはカレントディレクトリを指定しています。AFLディレクトリ直下をみてみると、 as が存在しています。これは、AFL用のアセンブラであるafl-asのシンボリックリンクで、つまりafl-asを見れば良さそうです。

afl-asの計測用コードの内容

afl-asを見てみると、計測用のコードを挿入した上で、オプションをいくつかつけて本来の as を実行していました。計測用コードは、複数箇所挿入されていました。計測用コードにはいくつかの条件がありますが、基本的には j + m 以外の命令( jejl などの条件分岐)の手前に挿入します。

また、計測用コードは以下のような手順になっています。(詳しく読まなくてもいいという人は、以下の箇条書き部分を飛ばしてください)

  • いくつかのレジスタを保存し __afl_maybe_log に遷移する。この時、 rcxid(乱数 % MAPSIZE) を格納しておく。なお乱数は、アセンブリコード挿入時点で確定しているため、ファジング実行ごとに変化する訳ではない。(MAPSIZEは、65536である)
  • AHにフラグを保存し、__afl_global_area_ptr の値を確認し、0であれば __afl_setup に遷移する。また0でなければ __afl_store に遷移する。
    • __afl_store では prev_id ^ id を行い rcx に格納した後、 prev_id__afl_prev_loc に格納し1ビットシフトする。最後に、 __afl_prev_loc の該当する位置をインクリメントし、そのまま __afl_return へ入る。
    • __afl_return では、保存したフラグを復帰したのち、ret命令を行う
  • __afl_setup_failure が0でなければ、 __afl_return に遷移する。
  • __afl_setup_failure が0であれば、 __afl_global_area_ptr の値を取り出しテストを行ったのち、 __afl_setup_first に遷移する
  • 様々なレジスタを保存したのち、 r12 にスタックポインタを保存して rsp を0x10減算したのち、 rsp の下位4ビットを0にする。
    • 減算して下位4ビットを0にするのは、スタックは16bit境界であることを前提としているため
  • .AFL_SHM_ENV環境変数を取得し、 結果が0であれば __afl_setup_abort へ遷移する
    • __afl_setup_abort では、保存したレジスタを復帰したのち、 __afl_return へ遷移する
  • 結果が0でなければ、結果を atoi で数値に変換する。
  • その後、 shmat で共有メモリを作成する。この時、 shmat の結果が-1であれば __afl_setup_abort へ遷移する。
  • shmat の結果である共有メモリアドレスを __afl_area_ptr および __afl_global_area_ptr に保存し、 rdx へ格納しておく。そしてそのまま __afl_forkserver へ入る。
  • 2度 rdx をプッシュしたのち、 FORKSRV_FD + 1 のファイルディスクリプタに対してデータを write する。戻り値が4でなければ __afl_fork_resume へ遷移する。
    • __afl_fork_resume では、共有メモリのクローズ、スタック領域からレジスタへの復帰を行い、 __afl_store へ遷移する。
  • 戻り値が4であった場合、そのまま __afl_fork_wait_loop へ入る。
  • FORKSRV_FD のファイルディスクリプタに対してファイルを read する。戻り値が4でなければ __afl_die へ遷移する。
    • __afl_die では、 exit(0) に相当する命令が実行される。
  • 4であれば、 fork() を行う。この時、戻り値が0未満であれば __afl_die へ遷移し、0であれば __afl_fork_resume へ遷移する。
    • この時、 FORKSRV_FD および FORKSRV_FD + 1 がクローズされるため、生成された子プロセスは通常のプログラム実行へと遷移していく。(main関数の最初に __afl_maybe_log が実行されるため)
  • 次に __afl_fork_pid へ戻り値である子プロセスIDを格納し、子プロセスIDを FORKSRV_FD + 1 のファイルディスクリプタに対して write する。
  • その後、子プロセスIDに対して waitpid を実行し、戻り値が0以下であれば __afl_die へ遷移する。そうでなければ、waitpid で取得した status を子プロセスに対して FORKSRV_FD + 1 を経由して write する。
  • 最後に __afl_fork_wait_loop へ遷移することで、ループ処理となる。

上記の内容を簡単にまとめると、こんな感じになります。

  1. 最初に計測コードに入ったら、環境変数 SHM_ENV_VAR から共有メモリ用の値を取得し、その値を利用して共有メモリにアタッチする。
  2. 後述するAFLのforkserver用の受信用ディスクリプタである FORKSRV_FD + 1 に対して、4バイトのデータを write する。
  3. 後述するAFLのforkserver用の送信用ディスクリプタである FORKSRV_FD から4バイトのデータを read する。
  4. fork を行い、子プロセスは本来のプログラムを実行し、親プロセスは FORKSRV_FD + 1 から子プロセスidを write し、 waitpidによって子プロセスの終了を待つ。
    • 子プロセスは、今後計測用コードに入るたびに、「どの計測用コードからどの計測用コードへ遷移したのか」という情報を、ステップ1でアタッチした共有メモリに追加していく。
    • 共有メモリは64KBあるため、計測用コードを識別するidは16ビットになっている。
    • 遷移前の計測用コードのidを prev_id 、遷移先の計測用コードのidを cur_id 、共有メモリを trace_bits とした時、 trace_bits[(prev_id >> 1) ^ cur_id] を加算することで、遷移情報を記録している。
  5. 子プロセスの終了後、 FORKSRV_FD + 1 から waitpid の引数である statuswrite し、ステップ3へ戻る。

一言で言ってしまえば、プログラム中の遷移情報を計測している、というだけです。あと面白いのは、fork を行い、AFL本体とやり取りを行うための親プロセスを常駐させている点です。(これのおかげで、プログラムを実行するごとに shmat などを行う必要がなくなっています)ちなみに、AFL本体では共有メモリ trace_bits の情報を使用することで、効率的にファジングを行うようにしています。

計測用コードとファジングの関係性

前記の計測用コードでは、 FORKSRV_FDFORKSRV_FD + 1 を用いてAFL本体とのやり取りを行っていました。やり取りの際、どのようなデータを送っているか、またAFL本体ではどのような処理を行っているのかを知る必要があります。その部分を知るために、ファジングを行うafl-fuzzを見て、流れを確認しようと思います。なおafl-fuzzのコードリーディングでは、以下のサイトが非常に参考になりました。

shimasyaro.hatenablog.com

afl-fuzzでは、forkserverと呼ばれる仕組みが用意されています。計測用コードの説明でも何度か出てきましたが、forkserverは、前記の計測用コードの親プロセスに当たります。つまり、

  • afl-fuzz: forkserverとやり取りを行い、プログラムを実行してもらう。
  • forkserver: afl-fuzzとやり取りを行い、 fork によってプログラムを実行する。

という感じです。forkserverの設定は、afl-fuzzの init_forkserver 関数を読むと書いてあります。 init_forkserver では、 fork を行い、子プロセスから execv によって計測用コードを埋め込んだプログラムを実行しています。最後に、forkserverから4バイトのデータを受け取ることができたら init_forkserver を終了します。

次にforkserverが出てくるのは、afl-fuzzの run_taget 関数です。 run_taget では、forkserverとやり取りをすることで、プログラムを実行してもらいます。まずafl-fuzzからforkserverに向けて、4バイトのデータを write します。次にforkserverから子プロセスidを受け取り、最後にforkserverから子プロセスの終了ステータスを受け取ります。

AFLとIntel Pinを組み合わせる方法

AFLとIntel Pinを組み合わせるには、以下のようなことをすれば良さそうです。

  • ファジングの対象となるプログラムを実行するより前に、共有メモリ trace_bits を用意しておく。
    • 環境変数 SHM_ENV_VAR の値を利用して、 shmat によって共有メモリをアタッチする。
  • ファジングの対象となるプログラムの実行直前に、forkserverにあたるコードを実行する。
    • 「afl-asの計測用コードの内容」でまとめたステップ2から5にあたるコードを実行する。
  • trace_bits[(prev_id >> 1) ^ cur_id] を加算して遷移情報を記録する部分を作成する。
    • 条件分岐命令の手前に trace_bits[(prev_id >> 1) ^ cur_id]++ にあたるコードを挿入する。

という感じに、色々と読んだ上でやり方を考えていたら、こんなリポジトリを発見しました。

github.com

どうやら、やろうと思っていたことが全部含まれているようです。このリポジトリでは、以下のような処理を行うコードが用意されています。

  • forkserver.cstartForkServer 関数では、forkserverに関する部分を一括して請け負っている。
  • startForkServer 関数は、ファジングの対象となるプログラムを読み込んだ時、Intel Pinで main の最初の命令の手前に startForkServer を実行している。
    • ファジングの対象となるプログラムの main 関数の最初の命令実行後、 PIN_Detach() によって、解析対象プログラムから離れる
    • 以上の動作により、forkserverをintel PINの使用により解決している。
  • ブロック遷移では、 ret 命令ではなく、条件分岐命令かつ分岐先アドレスが命令ポインタからのオフセットか即値でない部分(メモリやレジスタからの値)の場合に trace_bits[(prev_id >> 1) ^ cur_id]++ にあたるコードを実行するようになっている。
    • 乱数 % MAP_SIZE であった id は、分岐先のアドレスを使用することで代用している。

これによって、AFLとIntel Pinを組み合わせたファジングを行うことができるようになりました。

新たな情報を収集したファジングを行う

何を作ろうかと考えた結果、ACM CCS 2017で発表されたSlowFuzzを、AFLとIntel Pinを組み合わせて作ることにしました。通常、ファジングは脆弱性を発見するために用いられますが、SlowFuzzでは実行時間の長くなるような入力を発見します。その際に用いられる情報は、プログラムの命令実行数です(SlowFuzzの実装と正確には違うのですが、今回はより正確な命令実行数を取得するため、「検討」と書かれていた正確な命令追跡を行いました)。なぜ命令実行数にしているか、という点が気になった方がいれば、論文の5.6節を見ることをお勧めします。

さて、上記の通り、SLowFuzzでは命令実行数が必要となります。今回は、Intel Pinを使って命令実行数を取得し、その情報をAFLと共有させるようにしてみましょう。共有する方法ですが、共有メモリである trace_bits を4バイト拡張して、そこに命令実行数を格納するようにしました。共有メモリを拡張するには、afl-fuzzの setup_shm 関数にある shmget の第2引数を、 MAPSIZE から MAPSIZE + 4 にすればできます。拡張した4バイトには、基本ブロック単位で命令実行数を加算していくようにします。

最終的に出来上がったAFLとIntel Pinのコードは、それぞれ以下にあります。

github.com

github.com

プログラムを正常に実行できた場合、以下のような画面が出るはずです。このafl-pin-slowfuzzでは、実際のSlowFuzzとは異なりますが、AFL本来の機能に加えて、命令実行数の多い入力を生成しやすいように設計してあります。

f:id:who3411:20181218053219p:plain
afl-pin-slowfuzzの実行画面

おわりに

今書いた記事を見返してみて雰囲気しか伝わらなさそうな気がしてます

いかがだったでしょうか。おそらく、この記事を読んだ大半の方が、最初に「ファジング」という用語を聞いて、どのようなものか理解できなかったのではないかと思います。ファジングは海外では結構認知度があるように感じられるのですが、どうも日本ではあまり話題を聞かない気がします。

今回はIntel Pinを組み合わせましたが、他にもシンボリック実行ツールを組み合わせたものや、テイント解析を組み合わせたものなど、様々な種類が存在します。また発見したい入力についても、脆弱性の発生するもの、速度が遅くなるものなど、様々です。

そういえば、最近[1812.00140] Fuzzing: Art, Science, and Engineeringという、ファジングに関する調査論文が出たようです。(恥ずかしながら、まだ読めていません…)この論文のFig. 1を見ると、IEEE S&P 2018で発表されたCollAFLやAngoraなど、最新のものまで紹介されているようです。 ACM CCS 2018で発表されたHawkeyeはないので、そこまで最新のものはないのかもしれません。(近日、別のアドベントカレンダーで、いくつかのファジングの論文について話そうと思っていたのですが、どうしましょう…)

もっと日本でファジングに関する話が活発に聞けたらなぁと思う今日この頃です。というところで、技術的な内容が多くて理解できない部分があったかもしれませんが、本記事は以上となります。明日はmoppoi5168さんのBadUSB関係のお話です。お楽しみに!

SANS NetWars トーナメント 2018に参加しました。

はじめに

8月18日(土)に、SANS NetWars トーナメント 2018に参加しました。

SANS NetWars トーナメント 2018については、以下の公式サイトに詳しく書いてあります。

SANS NetWarsトーナメント2018 / 情報セキュリティのNRIセキュア

注意点

トーナメントの内容や解説については公開禁止だそうなので、「こういう感じだった」みたいなものを書いていこうと思います。

参加したきっかけ

去年の時点でSANS NetWarsのことを知ったのですが、某キャンプ参加後の復習と、東京まで行くための交通費や宿泊費を考えて面倒になってしまいました。今思えば、なんで「応募しなかったのか…」という感じです。

今年は某ハックや某キャンプのチューターに悉く落選していたところに、twitterのタイムラインに今回のトーナメントの募集があるというツイートが流れてきて、応募することを決めました。

当日までの流れ

応募した時点では「受かったらいいなぁ」くらいの気持ちだったのですが、今年は倍率が低かったらしく当選しました。

私は東京の近くに住んでいるわけではないため、どうしても交通費や宿泊費が頭の中をよぎります。できる限り宿泊費や交通費を節約しながら東京へ向かうことして調べた結果、深夜バスに乗ってイベント当日に東京へ向かい、イベントが終わった夜に深夜バスで帰ることにしました。 めちゃくちゃ疲れたのでしばらくはこんなことやりたくないと思いました

あとは荷造りをしたり、PCに指定されたソフトをインストールしたくらいです。正直トーナメントのために勉強したとかは一切していません。というのも、そもそもトーナメント前日まで「去年みたいにトレーニングがあってからトーナメントがあるんだろうなぁ」と思っていたからです。 日程見れば一瞬でトレーニングがないことぐらいわかるのに、なぜこんなことを思っていたのか…

当日

移動も含めた当日の流れは以下の通りでした。

  • 6:10 夜行バスで東京へ到着
  • 9:00 SANS NetWars トーナメント 2018 会場に到着
  • 9:30 SANS NetWars トーナメント 2018 開始
  • 19:00 SANS NetWars トーナメント 2018 終了
  • 24:00 夜行バスで地元へ帰る

以下、トーナメントおよび懇親会について書いていきます。

トーナメント

注意点にも書いた通り、内容や解説を公開することはできないので、どんな感じだったかを書いていきます。

一番の感想としては「英語わからん」でした…。「〇〇形式の問題が出たら解答の最初に『A: 』と書いてくださいね」と注意書きがあるのに、〇〇形式の問題ではないにも関わらず解答の最初に『A: 』と書いて「え?なんで間違ってるの?自分の解き方が悪い?」と30〜40分くらい悩んでる人を想像してみてください。はい、それが私です。

会場のみなさんが順調に問題を解いてる中、スコアボードを確認した時点での私は下から片手で数えられるくらいの順位でした。どうしてもわからずにスタッフや隣にいた人に聞いて何とか1問目を解き終えました。

その後からは頑張って一時期10位台までいきましたが、最終的には前面に出された中にはいませんでした。(同氏のツイートしている中間報告には辛うじている程度でした)

懇親会

トーナメント後に懇親会が行われ、何人かと話をしました。途中主催している会社の方のプレゼンがあったりもしました。お酒も結構あったので、飲めなかったのが残念です。(夜行バス帰りということを考えて飲むのをやめました。)SANS NetWarsの懇親会だったはずが、気づいたら同時期に開催されていた某キャンプの話になりました。 恐るべしキャンプ

おわりに

内容すら全く知らない状態で突撃したので、「前もってある程度調べていればよかった」という感じです。あと夜行バスで全然ねれなかったので、ちゃんと体調管理した状態で望むべきでした。

トーナメント自体について、いくつか不満もありましたが、全体的に面白い内容でした。(「StarWarsみてない人はわかりづらい部分もある」というのだけは本当にどうにかしてくれませんかね…。)おそらく「セキュリティに興味あるけど勉強とかはあまりしていない」という人でも楽しくトーナメントをすることができるのではないかと思います。個人的には「英語を勉強しないと…」ということと「来年リベンジしたい」という2点を感じました。

最後に、トーナメント後のお話で「復習を〜」という話があったのですが、(復習を促すということはトーナメントのページは見れるのかな)と思っていた私を恨んでいます。

これまで受けた情報処理技術者試験の話

はじめに

これまで7つほどの国家試験を受けてきたので、どのように勉強したのかを話していきたいと思っています。自分自身、受験するときに「どう勉強すればいいの?」という疑問があってWebを探し回った記憶があるので、そのような人の助けになれば幸いです。

なお何を行っただけ見たい人は「おわりに」だけ見てもらえば問題ありません。

注意点

  1. いくつかの試験は数年前に受験したものなので、結構記憶が曖昧だったりします。特に勉強期間や点数は、記憶に残っていないものも多いです。
  2. 自分が勉強した期間を記していますが、あくまで参考程度にしておいたほうがいいと思います。
  3. 書いてから気づきましたが、半分ぐらいポエムになってしまっています…。

受けた試験

受けた試験を時系列順に記述していきます。

基本情報

1回目

基本情報の1回目は、高校1年生の秋に受験しました。

"1回目"と書いてある時点でお察しとは思いますが、1回目は午前も午後も点数が足りずに落ちました。(画像などはありませんが、午後は59.50点という絶妙な点数だったことは覚えています。)

勉強については、午前と午後の過去問を解いて、午前で間違えた選択肢のみを調べ直していただけです。今思い返せば、高校に入って情報系の勉強を始めたので、全然勉強しない状態で落ちるのは必然だったと思います。

2回目

基本情報の2回目は、高校2年生の春に受験しました。

1回目に落ちたことをきっかけに、今度は真面目に勉強しました。今度は午前で間違えた問題だけではなく、解いた過去問の選択肢全てを調べなおしました。そして用語は全てメモ書きとしてノートに書いていきました。どれくらい勉強したかというと、B罫の6mm×35行のノートの半分は用語だけでびっしりと埋まったくらいです。

次に、午後問題対策として、SQLや擬似アルゴリズム等を勉強しました。勉強方法は午前と同様、過去問に出てきたものを調べたぐらいです。ちなみに午後のプログラム問題の選択ですが、当時の私はCOBOL以外の言語を触ったことがなかったので、表計算を選択しました。

おかげで午前午後ともに、ある程度余裕を持って基本情報に合格することが出来ました。勉強期間は、1回目と2回目をあわせて2ヶ月でした。

応用情報

応用情報は高校2年生の秋に受験しました。

応用情報は基本情報と同様、午前の過去問の選択肢全てを調べなおし、用語をメモ書きとしてノートに記述、午後問題対策として過去問の内容を調べなおす、ということをしていました。今回は基本情報よりも用語を多くノートに書いたため、結果として32ページが用語の勉強として埋まりました。

午後問題対策としては、記述式の「○文字以内で答えよ。」みたいなところを、以下にして文字数を少なく記述するかを自分なりにまとめていました。

試験の2週間後には大会が差し迫っていたため、そちらの大会と並行して勉強していましたが、ギリギリで合格できました。確か午後が62か63点だったと思います。勉強期間は1ヵ月半でした。

ITパスポート

ITパスポートは高校2年生の冬に受験しました。

なぜ基本情報と応用情報の次にITパスポートを受験したかというと、後輩が受ける際の付き添いとして、ついでに受験しました。この時点で基本情報と応用情報は合格していたので、ITパスポートの勉強はあまりしておらず、過去問を数回解いて終わりました。

受験した結果、70%ぐらいの正答率で合格した記憶があります。勉強期間は半月でした。

データベーススペシャリスト

1回目

データベーススペシャリストの1回目は、高校3年生の春に受験しました。

スペシャリストからは、参考書を使用して勉強を行いました。使用した参考書は以下の参考書の2014年度版です。

また正規化がいまいち良く分かっていなかったので、Webを漁って正規化について調べていました。最終的には、「正規化がパズルを解くみたいで楽しい」と感じるようになっていました。今でも正規化を行う問題を解くと楽しいです。

結構勉強していたのですが、結局1回目は午後Ⅱが4点足りずに落ちてしまいました。原因としては、問題文が長すぎて2時間で問題を理解し切れなかったことです。やはり文章読解スペシャリストでは…。

2回目

データベーススペシャリストの2回目は、大学2年生の春に受験しました。

今回は、過去問を重点的に解こうと思い、以下のURLの2016年度版を参考書として使用しました。

情報処理教科書 データベーススペシャリスト 2018年版

情報処理教科書 データベーススペシャリスト 2018年版

今回は、1回目の受験時から2年経過していたので、1回目時点の勘を取り戻しながら、過去問を解いていました。記憶が正しければ、過去8年分の過去問を全て解いた記憶があります。

後は午前Ⅰを勉強しなければいけなかったので、応用情報の午前の過去問を解いていました。こちらも過去8年分ほど解いて、昔作成した応用情報用のノートを見返しました。

受験した結果、午後Ⅱがギリギリですが合格することが出来ました。

f:id:who3411:20180623181328j:plain

勉強期間は、1回目と2回目をあわせて2ヶ月半でした。

ネットワークスペシャリスト

ネットワークスペシャリストは、大学2年生の秋に受験しました。

今回も参考書を使用しました。使用した参考書は、データベーススペシャリストの2回目に使用した参考書のネットワークスペシャリストverです。なお購入したのは以下のURLの2016年度版でした。

情報処理教科書 ネットワークスペシャリスト 2018年版

情報処理教科書 ネットワークスペシャリスト 2018年版

勉強内容としては、参考書に書いてある内容を要約したノートを作成して、午前と午後の過去問を解きました。正直な話、ネットワークスペシャリストは範囲が広すぎて、参考書だけでは上手く勉強できなかった感があります。(いい勉強法が良く分かりませんでした)

受験した結果、午後Ⅰがギリギリですが合格することが出来ました。

f:id:who3411:20180623181321j:plain

勉強期間は、1ヶ月でした。

情報処理安全確保支援士試験

情報処理安全確保支援士試験は、大学3年生の春に受験しました。

ネットワークスペシャリスト時に買った参考書の情報処理安全確保支援士試験verを、参考書として使用しました。なお購入したの以下のURLの2017年度版でした。

情報処理教科書 情報処理安全確保支援士 2018年版

情報処理教科書 情報処理安全確保支援士 2018年版

勉強内容としては、参考書に書いてある内容で重要そうな部分をマーカーで引き、午前と午後の過去問を解きました。個人的には覚えることが多くて面倒なイメージがありましたが、よくよく見たら大半は基本情報や応用情報で学んだことを深堀りしていただけでした。

受験した結果、午前Ⅱと午後Ⅱがギリギリですが合格することが出来ました。なおツイートでは「名乗れる」と記述していますが、登録セキスペはしていません。

勉強期間は、1ヶ月でした。

エンベデッドシステムスペシャリスト

エンベデッドシステムスペシャリストは、大学4年生の春に受験しました。

情報処理安全確保支援士試験時に買った参考書のエンベデッドシステムスペシャリストverを、参考書として使用しました。なお購入したの以下のURLのものです。

情報処理教科書 エンベデッドシステムスペシャリスト 2017~2018年版

情報処理教科書 エンベデッドシステムスペシャリスト 2017~2018年版

この時は、大学3年の後期に講義でCPUを作成していたこともあり、参考書に書いてある大半の内容を理解していたため、勉強期間を短めにして勉強していました。しかし後々情報危機管理コンテストの一次予選と日程が被ってしまい、かなり面倒なことになってしまいました。(コンテストの話は以下にブログを書いています)

who3411.hatenablog.com

受験した結果、午後Ⅱがギリギリですが合格することができました。

勉強期間は、2週間でした。

おわりに

色々とグダグダ書きましたが、基本的には以下の内容を行っていただけです。

  • 参考書を読む。
  • 過去問を解く
  • 過去問の選択肢にある分からない用語をノートにまとめる。

ちなみに過去問を解くに当たっては、(特に午前は)○○ドットコムを主に使用させていただきました。(○○には「基本情報技術者試験」などが入ります。)

今後受けようと思っている人は、ぜひぜひ頑張ってみてください。

第13回情報危機管理コンテストに参加しました

はじめに

5/24(木)〜5/26(土)の3日間で、第13回情報危機管理コンテストにチーム「sawayaka-sec」として参加しました。

情報危機管理コンテストの内容については、以下の公式サイトに詳しく書いてあります。

第13回情報危機管理コンテスト | 第22回サイバー犯罪に関する白浜シンポジウム&第13回情報危機管理コンテスト

注意点

どこまで公開していいかわからないので、具体的なこと(「コンテストで使用するサーバの〇〇というソフトウェアが〜」など)は述べないようにします。ただしネットで少し検索すればわかるような内容については記述しようと思います。

参加したきっかけ

2年ぐらい前から参加したかったものの、学内でセキュリティに興味があり(まずここで大半がいなくなる)、かつ参加してくれそうな人がいなかったので、「出たいなぁ」と思ってるだけでした。

今年度は、学内でセキュリティキャンプ参加者が自分を含めて複数人いたこと、指導教員からの許可をもらえそうだったことなどもあり、参加することを決意しました。(参加してくれた2人に「情報危機管理コンテスト出てみない?」と聞いたのは、応募締め切り1日前でした。本当に参加してくれてありがとう!そして締め切り直前に言ってごめんなさい…)

一次予選

一次予選までにやったこと

参加を決めてから、まずは一次予選がどのようなものかを確認しました。一次予選については問題が公開されているような状態なので、基本的にはそこを眺める感じでした。以下のページからリンクを辿っていけば、問題を見れるはずです。

第一次予選 | 第22回サイバー犯罪に関する白浜シンポジウム&第13回情報危機管理コンテスト

あとは、実際に始まった時にどうやるかを決めました。具体的に決めたのは以下の2点です。

  1. 集まってやる時間と場所
  2. どういった手順で問題を解いていくか

一次予選中の話

一次予選中は、あらかじめ決めていた「問題を解く手順」に従って考えていきました。結局2日間ぐらい深夜まで問題について考えたりして、かなり疲れました…。「問題を解く」というよりは「与えられた文面から考える」という考察の面が強かったと個人的には思うので、普段使わない頭を回すのは新鮮でした。最後の方には文面の粗探しみたいな状態になってきて、めちゃくちゃ辛かった記憶があります。

結局2日間で作成する文章を決めて、1日で分担した箇所について文章を作成するようにしました。なんとか文章を作成し終わり、私はコンテスト最終日と被ってしまったエンベデッドシステムスペシャリストの受験にいきました。(2人には重ね重ね申し訳ない…)

二次予選

一次予選から数日後、一次予選突破を受けて、本格的に二次予選へと足を運ぶ形になりました。

二次予選までにやったこと

二次予選では実践形式でトラブル対応を行うため、まずは使用するOSやソフトについて調べました。中には聞いたことすらないソフトウェアもあり、かなり焦ったりもしました。更に、私は普段サーバを弄ったりしているような人間ではないため、トラブル発生時の対応なども知識としてあるだけで、実践はゼロです。なので、時間を見つけては調べた内容をhackmdにまとめて、本番に備えていました。

また二次予選からは具体的な情報が少ないため、記事、参加者のブログやスライドなどを眺めてどのような問題が出るかを調べました。学校によっては過去に情報危機管理コンテストへ参加した学生もいるかもしれませんが、弊学では私の知っている限り参加した学生はいないため、完全に手探り状態でした。正直二次予選が近づくにつれて焦りが増えていました。

あとは役割分担を(簡単にですが)決めました。結局決めた役割を厳密に守ることはなかった(障害対応役が原因究明したり、進行役が原因究明したり、原因究明役が障害対応したり…)のですが、ある程度決めておくといいかもしれません。

二次予選中の話

二次予選は、開始早々skypeが繋がらなかったりチームメンバーがVPNにアクセスできなかったりと、かなり最悪な状態からスタートしました。競技の内容は詳しく言えないので省略しますが、「sawayaka-sec」は2つのシナリオを解いて、3つ目のシナリオの原因が分かったところで終了しました。1つ1つに時間をかけた影響で、3つ目のシナリオが解けなかったのが残念です。

終わったあとは運営側と少し話をしましたが、「慣れてるように感じた」のような評価をいただけて嬉しかったです。

勝戦

二次予選も終わり、まさか決勝戦へ行けるとは思っていなかったので、突破した時はかなり驚いてました。(実は、応募時には先ほど述べたように情報が全然なかったので、二次予選で落ちると思っていました)

勝戦までにやったこと

とりあえずは「二次予選と同じ環境で決勝戦が行われるのではないか」という想定の元、二次予選で調べた内容を引き続き調べなおしていました。

あとは白浜までの道を調べて、どの電車に乗るか決めたり持っていくケーブルなどをかき集めていました。

個人的に辛かったのは院応募の願書の提出期限が、コンテスト期間中と一部被ったことです。コンテストの調べ物を一時中断して、願書を書いていました。

ちなみに情報危機管理コンテストは2〜4人のチームで行われますが、「sawayaka-sec」は二次予選まで3人チームでした。4人目を加えないか聞かれましたが、ここまで3人でやってきたので、3人で突撃することにしました。

1日目

新幹線と特急くろしおを使って白浜まで向かいました。5チーム中4番目に到着し、1時間ぐらい後に行われる競技の説明の前に昼飯を食べました。自分以外のチームメンバーは、昼飯の後に大急ぎで企業展示を見に行ってました。

競技の説明などを受けた後にはホテルに向かいましたが、ホテルの環境がすごいよくてびっくりしました。どれくらい良かったかというと、明日に向けて行う予定だった作戦会議が、中止になる可能性が出たほどです。(結局作戦会議はしましたが、開始予定時間は大幅に遅れました)

長時間の移動による疲れもたまっていたため、その日は12時ぐらいにチームメンバーに「棺桶」と言われた布団で寝ました。(本を読んだまま寝落ちしてしまい、更にその本が頭にかぶさっていたため、「本当に棺桶みたいだった」と後で言われて面白かったです)

2日目

起床試験に成功し、無事にバイキング形式の朝食をいただきました。その後は準備をして、競技会場行きのバスへ乗り込みました。

競技会場へ向かって最後の準備を行い、競技が始まりました。(相変わらず詳しい内容はかけませんが、情報危機管理コンテストのTwitterアカウントをみると大まかな流れは書いてあります)

twitter.com

「sawayaka-sec」自体は、午前に1問も解けず(後少しで1問目が解けたところで終了)無事爆死して、心が折れながら昼飯を食べて、午後にある程度挽回(?)しました。午後は、最初に発生した問題の原因が2分程度で気づけたのが良かったです。(問題が発生するたびに原因になりそうなファイルを確認していたので、それが良かったのかも…)

競技終了後はディナー会場へ向かい、またもバイキング形式のご飯をいただきました。ホテルに帰ってきてからは、企業交流会なるものに参加させていただきました。普段話せないような方々と話せたのは楽しかったです。(ここで名刺を持っておらず、企業の方と交換できないことに気づく…)

全て終わってからは、疲れていたのか風呂に入ってしばらくしたら寝てしまいました。

3日目

朝の4時半ごろに起きて、朝風呂に入ってきました。そのあとは帰りの電車で読もうと思っていた論文をダウンロードしたりアニメ見たりしていました。そのあとは前日と同じバイキングを食べて、会場行きのバスへ乗り込みました。

結果発表の前に時間があったので、昨日話した企業のところへ向かい、お話を伺ったりしていました。その後は別会場へ向かい、表彰式がありました。

各チームの賞は以下の通りです。( http://www.riis.or.jp/symposium22/crisismanagement/final/の決勝戦結果発表の内容のうち、個人名が入る賞を省略して貼り付けています。個人名を省略したのは、個人の名前をブログに載せるのが少し違和感を感じたためです。)

上記の通り、「sawayaka-sec」は文部科学大臣賞を受賞させていただきました。

表彰式のあとは、とれとれ市場へ行って昼飯を食べたりお土産を買ったりしてから電車に乗って帰りました。

おわりに

あれ?今後参加したい人に向けて大まかな流れを書いたつもりが、なんかふわふわしたものしか書けていない気が…

まずは、3人チームで決勝戦まで、そして文部科学大臣賞まで受賞できるとは思っていませんでした。チームメンバーの2人は本当に感謝しています。また色々と迷惑をかけてしまい、本当に申し訳ありません。

競技の話に移りますが、競技全体を通して、これまで経験したことのない競技ばかりだったので、個人的にはとても新鮮で楽しい時間を過ごすことができました。また使用させていただいた機器についても、普段では触らないものばかりで、色々と勉強になりました。

競技全体に関する疑問点として、個人的に気になったのは以下の2点です。

  1. 3人チームの進行役でもきつかったのに、4人チームの進行役って本当にどうやってやってるんだろう…?
  2. 各チームが、どの点で良い評価を得られて、どの点で悪い評価を得たのかがよくわからない

競技以外の話としては、企業展示や交流会など、普段では体験できないような時間を過ごせて良かったです。またホテルもとても良く、良い2泊3日を過ごすことができました。ちなみに、3日間で、以下のようなものをいただきました。ありがとうございました。

最後に、情報危機管理コンテストを行うにあたり、ホテルの宿泊費や交通費などといった費用を出していただいた運営の皆さま、本当にありがとうございました。

来年は4人チームでリベンジしたいです。

P.S.

賞状を貰った祝いに、研究室の先生にさわやかを奢って貰いました!本当にありがとうございます!

拡張BNFを用いたLL1文法の判定器を作った話

はじめに

今回、GitHubの勉強も兼ねてタイトルの通りのプログラムを作成してみました。

使い方や記述方法については、リンク先のREADME.mdに書かれているので、このブログでは「そもそもLL1って何?」とかの話も軽く話していきたいと思います。なお本ブログを読むにあたって、拡張BNFやLL1の話はかなり砕いて説明をしているので、詳しく知りたい方は他サイトや書籍を探して読むことをオススメします。

拡張BNFとは

拡張BNFは、BNF記法を拡張したものです。「じゃあBNFって何?」というと、文脈自由文法の定義などに用いられるものです。文脈自由文法は、正規表現よりも記述できる範囲が拡張された文法です。例えば「(1 * (2 + 3) )」のような括弧が混じった数式における"("と")"の対応を正規表現では記述することが出来ませんが、文脈自由文法では記述することが可能です。(BNFの記述方法については、ググってもらえば、分かりやすい解説が大量にあるので検索してみてください)

拡張BNFでは、BNF記法に加えて「繰り返し」が存在します。そのためBNF記法で繰り返しを表現したい場合、BNF記法では再帰的に定義することで擬似的に「繰り返し」を表現する必要があります。

例として、括弧を含めた加算を行う数式を表現する場合を、BNF記法の場合と拡張BNF記法の場合で表します。

BNF記法の場合

<DIGIT>  ::= ( "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" )
<DIGITS> ::= <DIGIT> <DIGITS> | <DIGIT>
<EXPR>   ::= <DIGITS> "+" <DIGITS> | "(" EXPR ")" | <DIGITS>

拡張BNF記法の場合

DIGIT  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
DIGITS ::= DIGIT { DIGIT }
EXPR   ::= DIGITS { "+" DIGITS } | "(" EXPR ")"

このとき、DIGIT、DIGITS、EXPRのように"::="の前にある記号のことを非終端記号といいます。また"0"、"("、"+"のように"::="の後ろにしかない記号のことは終端記号といいます。

LL1文法とは

LL1文法は、1つ先読みすることで構文を決定できる文法の事を指します。この場合の「1つ先読み」とは「1トークン先読み」のことを指しており、つまり「1トークンを先読みすることで、構文を決定・解析できるような文法」を指しています。

つまり今回作成した「拡張BNFを用いたLL1文法の判定器」とは、「拡張BNFで記述されたものがLL1文法であるかどうかを判定する」ことが目的のプログラムになっています。

ではLL1文法を判定するためにどのようにすればよいのでしょうか。ここで必要となってくるのがFirst集合、Follow集合、Director集合という3つの集合です。それぞれについて説明していきます。

First集合

First集合とは、非終端記号と終端記号からなる記号列に対して、記号列から生成される先頭の終端記号の集合を現します。例えば「拡張BNFとは」で説明した文法について説明すると、非終端記号はDIGIT、DIGITS、EXPRの3つ、終端記号は"0"~"9"、"+"、"("、")"の12つです。

このとき、終端記号から生成される「先頭の終端記号」とは、自身を示しています。そのためFirst("0") = { "0" }、First("1") = { "1" }…のように、自身の終端記号のみを生成します。

それに対して非終端記号から生成される「先頭の終端記号」とは、First(DIGIT) = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }、First(DIGITS) = First(DIGIT)、First(EXPR) = First(DIGITS) + { "(" }のように、各記号列の先頭に出る終端記号の集合を生成します。

Follow集合

Follow集合とは、非終端記号に対して、非終端記号の後ろに現れる可能性のある終端記号の集合を現します。例えばDIGITの後ろにはDIGITと"+"と")"が発生する可能性があるのでFollow(DIGIT) = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "+", ")" }となります。

First集合とFollow集合についての注意事項として、First集合では終端記号も求める必要がありますが、Follow集合では求める必要がありません。これはDirector集合で意味が分かると思うので、今は省略します。

Director集合

Director集合とは、非終端記号Nとその非終端記号から生成される可能性のある記号列Sを使用します。このときDirector集合はDirector(N, S)のように記述します。Director(N, S)は、Sが空文字でなければFirst(S)を、空文字であればFollow(N)を返します。

今回、空文字を使用していなかったため、Follow(N)となる例を見せることは出来ませんが、README.mdでは実行例を表示しているので見てみてください。

LL1文法の判定方法

LL1の判定方法は、結構簡単でNから生成される可能性のある記号列S1とS2(S1≠S2)のDirector集合の積集合Director(N, S1)∩Director(N, S2)が全て空集合であるかどうかで判定します。このとき、全てが空集合であればLL1であり、一つでも空集合でなければLL1ではありません。

プログラムの作成方法

さて、本題であるプログラムの作成方法について記述していきます。手順は以下の通りです。

  1. 拡張BNFトークンごとに分解する。
  2. 分解した拡張BNFが正しい記法であるかをチェックする。このとき、正しい文法でなければエラー又は警告を出力する。
  3. チェックが終了した状態の拡張BNFを出力する。
  4. 非終端記号のFirst集合を求めて出力する。
  5. Follow集合を求めて出力する。
  6. Director集合を求めて出力する。
  7. 拡張BNFがLL1かどうかをDirector集合を用いて判定・出力する。

各工程について説明していきます。

拡張BNFの分解

まず拡張BNFトークンに分解するにあたり、どのような構文にするかを定めます。この際に定めた構文は、README.mdの「拡張BNF記述ルール」を見てください。

次に定めたルールに従って、Tokenizerを作成していきます。今回のTokenizerでは、単純に以下の4種類に分解します。

  1. 文字と数値の組み合わせ
  2. ":"と"="の組み合わせ
  3. EOF
  4. その他

分解したトークンが、どのような情報を持つトークンであるかを、別に用意したルールを利用して情報ごとに分類します。つまり一つのトークンには「トークンの文字列」と「トークンの持つ意味」の2つを格納しています。この時点で、終端記号と非終端記号の分類は行っていません。どちらも「分類していない記号」として情報を格納しています。

分解した拡張BNFのチェック

ここでは、「分類していない記号の分類」と「拡張BNFのチェック」を行います。「分類していない記号の分類」は言葉の通りで、「分類していない記号」を終端記号であるか非終端記号であるかを確認します。

「拡張BNFのチェック」では、"("と")"の数が一致しない、"A ( ) B"のように必要のない括弧があるなど、LL1であるかどうかを判定するのに必要でない括弧の除去などを行っていきます。このとき、プログラムで直せる範囲であれば警告、直せない範囲であればエラーとして出力します。

「拡張BNFのチェック」で、プログラム側が利用者の記述した拡張BNFを修正する可能性あるため、この工程が終了する時点でプログラム側が今後利用していく拡張BNFを出力します。

First集合の求め方

自身の非終端記号を持つ列を見つけ、その非終端記号のFirst集合を求めます。求め終わった後に、全て出力します。

Follow集合の求め方

拡張BNFの右辺("::="の右側)から、非終端記号を見つけ、その非終端記号のFollow集合を求めます。求め終わった後に、全て出力します。

Director集合の求め方

非終端記号とその非終端記号が生成する可能性のある記号列、これまで求めてきたFirst集合とFollow集合を用いて、空文字があればFollow集合を、空文字がなければFirst集合をDirector集合として利用します。求め終わった後に、全て出力します。

LL1の判定

同じ非終端記号から求めたDirector集合を用いて、LL1であるかの判定を行います。LL1の判定を行い、LL1でなければ空集合とならなかった積集合を出力します。

おわりに

雑な説明でしたが、以上が今回作成したプログラムの全貌になります。LL1が作れると何が良いかなどは、各自調べていただければ幸いです。(私は勉強目的ですが、自作言語をしたい方は勉強するといいかもしれません。)