IQ1からの必死のパッチで機械学習×文法ベース入力ファジング
お詫び
この記事はちゃっく君のIQ1アドベントカレンダーの21日目の記事です．
また，当初予定していたkriw君のCTFアドベントカレンダーの24日目の記事の執筆が遅れそうなため，執筆完了までの期間この記事を紹介させて頂きます（24日目の記事が完成したら置き換えます 🙏 ）．
IQ1からの必死のパッチで機械学習×文法ベース入力ファジング
この記事では，文法構造を持つ入力を処理するプログラム（e.g. パーサ）の脆弱性解析の有力手法である文法ベース入力ファジング（Grammar-based Input Fuzzing）について，2017年に発表された機械学習ベースの新手法Learn&Fuzzを紹介します．記事の話の流れはだいたいこんな感じです👇
- Webブラウザでも実行されるPDFパーサはセキュリティ脆弱性💀の温床．
- 文法構造をもつ入力データ（e.g. PDFファイル）の解析プログラム（e.g. PDFパーサ）を対象とする脆弱性検査の手法～文法ベース入力ファジングとその問題点．
- 機械学習に基づく文法ベース入力ファジングとその効果．
- まとめと将来の研究の方向性．
1. PDFパーサはセキュリティ脆弱性💀の温床
Webブラウザでも実行されるPDFパーサはセキュリティ脆弱性💀の温床として知られています．実際，某社のセキュリティ掲示板を覗いてみると，PDFパーサに関連する脆弱性は，現在までに発見済みであるものに限定しても，多数報告されています:
上記の掲示板にあるCVE-2018-*****というIDが割り振られた脆弱性が発見された脆弱性1つに対応します．2018年の1年間だけでも致命的（Critical）な脆弱性がざっくざく報告されていて，PDFパーサの脆弱性やばすぎ💀，という現状がすぐに理解できます．
この某社に限らず，他の某社のEdgeブラウザで使用されるPDFパーサでも開発段階から多数の脆弱性が発見されていることはMicrosoft社の研究者ら自身が研究論文等で報告済みです．
PDFパーサにセキュリティ脆弱性があると何が恐いかと言うと，我々が日常的に使用しているWebブラウザで特定のPDFファイルを開いただけで，最悪の場合，そのPDFファイルに仕込まれた攻撃者の悪意あるコードが実行され以下のような危険な状況に陥ってしまいます:
- PC上の機密情報/個人情報が攻撃者に漏洩する．
- PC上の重要データが破損する．
- 自分のPCが他の攻撃の踏み台として悪用される．
実際，上記の脆弱性掲示板に掲載されている脆弱性CVE-2018-15955に関する記述を覗いてみましょう・・・概要を読むだけで脆弱性の恐ろしさが伝わってきます．
このことから，PDFパーサの脆弱性検査はちゃんとやらないとダメみたいですね，という話になります．
2. 文法ベース入力ファジング（Grammar-based Fuzzing）とその問題点
文法ベース入力ファジングとは，特定の文法に従う入力を解析するプログラム（e.g. PDFパーサ）の脆弱性の検査手法です．従来の文法ベース入力ファジングでは，与えられた入力文法から，文法構造に沿ったテスト入力を自動生成し，生成した多数の入力を対象プログラムに与えて実行することで脆弱性をあぶりだします．これらのテスト入力を自動生成するには，テスト実施者が入力文法を手動で記述する必要がありました．しかし，入力文法を手動で記述する方式には次の2つの大きな問題点があります:
- 入力文法の手動記述は大きな手間がかかり，かつ，誤りが生じやすい．
- 文法を記述しただけでは高いコード網羅率を達成する入力は自動生成できない．
問題点1のせいで，従来の文法ベース入力ファジング技術は実用を敬遠されがちです．実際，PDFの文法はPDFファイルにして1,300ページくらいの分量があって，1,300ページに渡る文法の説明を人間が把握して，文法ベース入力ファジングで扱える形式の文法に正確に書き下すことは至難の業です．
また，問題点2により，既存の文法ベース入力ファジングでは脆弱性を発見できないケースが多々あります．入力文法には従うものの，ありきたりで典型的な入力（e.g. ネットで容易に入手できるような正常なPDFファイル）だけでは，入力解析プログラム（e.g. PDFパーサ）を脆弱性の潜伏する実行パスに誘導することは困難なためです．特に，入力解析プログラムの脆弱性は，イレギュラーな入力（e.g. 異常なPDFファイル）を与えた場合に例外的に実行されるパス（e.g. エラー処理コード）に潜伏するケースも多いため，単に入力文法に準拠するだけの優等生的入力を生成するだけでは有効な脆弱性検査とは言えません．要するに，PDFパーサのような入力解析プログラムの脆弱性を発見しようとすると，入力文法にかっちりと従う正常なPDFファイルをパーサに食わせて検査するだけでは不十分で，ほぼほぼ文法に沿いつつも一部内容が壊れているような異常なPDFファイルも食わせて様々なエラー処理パスも検査する必要がある，ということになります．
3. Learn&Fuzz ～ 機械学習に基づく文法ベース入力ファジング
従来の文法ベース入力ファジングの上記2つの問題点を同時解決する試みとして，2017年にMicrosoft Researchの研究者らが機械学習に基づく新たな文法ベース入力ファジング技術Learn&Fuzzを提案しました:
Learn&Fuzzは次の2つのアイデアにより，従来の文法ベース入力ファジングの問題点のそれぞれを克服しようとしています（LearnしてFuzzなのでLearn&Fuzz（まんま））:
- 機械学習により入力文法を自動獲得する（Learn）．
- 入力文法にほぼ従いつつも部分的にイレギュラーな入力を確率的に生成する（Fuzz）．
アイデア1（Learn）は，テスト実施者に複雑な入力文法を手動記述させるのではなく，大量の入力データセットを用いてニューラルネットを訓練することで入力文法を自動的に獲得（つまり学習）するという考えです．ここでのポイントは「力こそパワー」，すなわち，入力文法に沿う入力データを大量に集めさえすれば，あとはそれらのデータセットでニューラルネットを訓練するだけで入力文法の学習が全自動で完了するという点です．その結果，テスト実施者は文法を手動記述する必要なくお手軽に文法ベース入力ファジングを実施できるようになります．これは手動による文法記述を要した従来の文法ベースファジング技術に比べて大きな進歩です．もうひとつの重要なポイントは，Learn&Fuzzが入力文法を訓練によって学習するモデルはRNNベースの生成モデルであるという点です．これは，学習したモデルの確率分布から訓練データセットには現れない新たな入力データを生成することが可能であることを意味します．このことは次に説明するアイデア2を実現するうえでも重要な役割を果たします．
アイデア2（Fuzz）は，学習した生成モデルの確率分布に基づき新たなテスト入力を生成しつつ，モデルが高い確率で予測し生成した典型的入力の一部を確率的に改竄することで部分的にイレギュラーな入力データを生成するという考えです．従来の文法ベース入力ファジングで生成可能な入力データは，単に入力文法に即しただけの典型的で面白みのない入力データでした．このような典型的（＝正常）な入力データだけでは，異常な入力データがきたときにのみ発動するエラー処理パスを実行できず，結果として，そのようなエラー処理パスに潜む脆弱性を検出できません．これ対し，Learn&Fuzzでは，Learnフェーズで学習した入力文法に高確率で準拠する新たな入力データを生成しつつ，Fuzzフェーズにより生成した入力データを確率的に改竄することで部分的に異常な入力データを合成します．その結果，従来の文法ベース入力ファジングでは困難であった，異常な入力データに対するエラー処理パスに潜伏する脆弱性を検出することが可能となります．
Learn&Fuzzはこれら2つのアイデアを実装し，Microsoft Edgeブラウザで実行されるPDFパーサを実際に検査する実験を行いました．実験の結果，従来技術に比較して（エラー処理パスを含め）より多くの実行パスを検査できることが判明しています．詳しい実装の詳細と実験結果は元論文を参照しましょう（読みやすい論文でお勧めです！）．
4. まとめと将来の研究の方向性
文法構造を持った入力の解析プログラム（e.g. PDFパーサ）の脆弱性検査は重要ですが，従来の検査手法である文法ベース入力ファジングには（1）手動による文法記述が必要で手間がかかる問題と（2）文法にかっちりと従う典型的入力しか生成できない問題があり，実用が敬遠されかつ脆弱性発見能力も限定的でした．これらの問題を克服する試みとしてLearn&Fuzzが提案され，（1）機械学習による入力文法の自動合成と（2）文法にほぼほぼ従いつつも部分的に異常な入力を確率的に生成する方式により，実用に耐えうるほどお手軽かつより多くの脆弱性の発見が可能となりました．
しかし，Learn&Fuzz自体も完璧な技術には程遠く，元論文の方式ではうまく合成できない文法もあれば発見できない脆弱性もまだまだ多いという状況です．実際，入力をPDFに絞っても，Learn&Fuzzで合成できる文法は限られています．これらの諸問題を実験的に明かしつつそれらの解決をはかる挑戦は，ちゃっく君の良き先輩であるところのななめ先輩（東工大権藤研）が修士研究で取り組んでおり面白い成果を出してくれています．来年のアドベントカレンダーでは，ななめ先輩の研究成果の国際会議発表バージョンを紹介できればいいな⭐⭐⭐（おしまい）
