確率的並行ファジング
本稿は、自作OS AdC 2019の12/21兼IQ1 AdC 12/24の記事です（ポストが遅れてしまい申し訳ございません）。
並行プログラムの実装で問題になる並行バグを対象とする自動検知の手法として、並行ファジングと呼ばれる手法があります[1,2,3,4,5]。本稿では、そのうちのPCT（Probabilistic Concurrency Testing）と呼ばれる、確率保証付きで並行バグを検知するファジング[2]を紹介します。
並行バグ
並行バグ（concurrency bug）とは、 並行プログラムにおいて特定のスレッドスケジュールでのみ発現するバグです。典型的な並行バグとして図1の3種類の並行バグがあります（論文[2]のFigure 1を引用）。図1(a)は順序違反（order violation）と呼ばれる並行バグで、Thread 1が変数tを初期化する前にThread 2がtの値を読むというスレッドスケジュールで発現します。図1(b)は原子性違反（atomicity violation）と呼ばれる並行バグで、Thread 2がif文の条件判定でxの値がnullでないと判定した直後にThread 1がxにnullを代入し、その後Thread 2がx->print()を実行するというスケジュールで発現します。図1(c)はデッドロック（deadlock）と呼ばれる並行バグで、Thread 1がThread 2より先にロックaを獲得し、かつ、Thread 2がThread 1より先にロックbを獲得するというスケジュールで発現します。
並行バグは一般に再現性が低く、発見と修正が困難な厄介なバグとして知られています。並行バグを含む並行プログラムに対し同じ入力を与えて複数回実行した場合、スレッドスケジュールは一般に実行のたびに変化します。その結果、プログラムのテスト時に観測される多くのスケジュールで並行バグが発現せず、ディプロイ後に稀に生じる特定のスケジュールでのみ並行バグが発現する、ということが起きます。
現実の多くの並行プログラムに対し、上記の3種を含む様々な並行バグが報告されており、ソフトウェアのテストとデバッグの研究分野では並行バグの調査と分類が行われています[0]。
並行ファジング
並行ファジング（concurrency fuzzing）は、並行バグの検知を目的とするスレッドスケジューリングです。通常のスレッドスケジューリングの目的が何らかの指標での並行処理の効率化であるのに対し、並行ファジングのスケジューリングは効率ではなく並行処理のバグの検出を目的とします。言い換えると、並行ファジングは並行バグを発現させるスレッドスケジュールを意図的に合成する手法です。並行ファジングの前提として、検査対象の並行プログラムの実行に必要な入力は予め用意されているものとします。
例えば、図1の各種の並行バグを考えます。これらの並行バグを検知するために、並行ファジングは数多のスレッドスケジュールの中から、図中の黒矢印の順序でThread 1とThread 2の各式/文を実行するスケジュールを見つけ出そうとします。通常のスレッドスケジューリングでは図中の矢印の順序が稀にしか実行されない場合に対して、並行ファジングは意図的にこれらのスレッド実行順序を引き起こそうとします。
並行ファジングにも様々な方式があります。以下に代表的な方式を挙げます。
1．ヒューリスティクスに基づくスケジューリング
この方式はまず、対象プログラムの実行時監視（動的解析）によって、（正常な）実行トレースから並行バグに関係しそうな挙動を捉えます。例えば、複数スレッドによる共有変数アクセスやロック獲得は並行バグの要因となり得る挙動です。次に、捉えた疑わしき挙動に焦点を当て、独自のスケジューラによって、並行バグが発現するよう各スレッドの共有変数アクセス順序やロック獲得順序を意図的に調整します。その結果、意図した通りにスレッドスケジュールを合成・実行できた場合、それを並行バグとして報告します。
2．システマティックなスケジューリング
この方式は、可能な限り多くの異なるスレッドスケジュールを限られた予算内で、あるいは、特定の上限（例えばスレッド切り替えの回数）に達するまで、網羅的に列挙して実行しようとする方式です。実際に網羅実行されたスケジュール中に各種の並行バグの条件を満たすものがあれば、それらを並行バグとして報告します。
3．ランダムなスケジューリング
この方式は、OSやランタイムによる各スレッドの実行スケジューリングに対し、ランダムに遅延を加えたり、スレッド切り替えやスレッド優先度変更をランダムに引き起こすことで、通常のスレッドスケジュールとは異なるランダム性の増したスケジュールを合成します。それによって、膨大なスケジュール空間に潜む並行バグをランダムにあぶり出します。
確率的並行ファジング
前述のランダムスケジューリングに属する手法として、確率保証付きで並行バグを検知するファジング手法があります[2]。この手法はPCT（Probabilistic Concurrency Testing）と呼ばれるもので、スレッド数がnで全スレッドの総実行命令数がkである並行プログラムに対し、1回の実行につき深さdの並行バグを少なくとも1/(nk^(d-1))の確率で検知します。ここで、並行バグの深さdとは、あるスレッドの実行命令aの後に別のスレッドの実行命令bが実行されるというスレッド間の命令実行順序に関する制約a→bの個数を意味します。例えば、図1(a)の順序違反の深さは1、図1(b)の原子性違反の深さは2、図1(c)のデッドロックの深さは2です。図中で各黒矢印はスレッド間の命令実行順序の制約に対応し、各並行バグの深さdは黒矢印の本数に対応します。
1．PCTアルゴリズムの概要
深さdの並行バグdを検知するために、PCTはまず、検査対象である並行プログラムのn個のスレッドの各々に対し、優先度d, d+1, ..., d+n-1から値を1つ選んで割り当てます（値の大きい優先度を持つスレッドの実行が優先）。次に、PCTはn個のスレッドによる長さkの実行命令列上にd-1箇所の優先度変更点を設置します。これらの優先度変更点には低い優先度を割り当てます。具体的には、i番目の優先度変更点に優先度d-iを割り当てます。このように各スレッドと各優先度変更点に対応する命令のそれぞれに優先度を設定した上で、PCTは優先度の高いスレッドから順に実行して行きます。実行中に特定のスレッドがi番目の優先度変更点を通過した際に、PCTはそのスレッドの優先度をd-iに下げます。ここで、PCTは優先度の高いスレッドを、ロック獲得待ちになるなどしてブロック状態に入るまで実行し続けます。その間、優先度の低いスレッドは実行されません。
2．PCTアルゴリズムの直観
図1の各種並行バグに対し、PCTが有効に機能する例を図2に示します（論文[2]のFigure 6を引用）。 図2では、Thread 1とThread 2に対してPCTが最初に割り当てる優先度を白丸の数値で表現しています。例えば、図2(b)では、PCTはThread 1に優先度2を、Thread 2に優先度3を割り当てています。また、図中の黒丸の位置および数値は、PCTが検査対象の並行プログラムの命令列上に設置した優先度変更点の位置および優先度を表現しています。例えば、図2(b)では、PCTはif文の条件判定式に対応する最後の命令に優先度変更点を設置し、変更点を通過したスレッドに割り当てる優先度を1に設定しています。このように各スレッドと各優先度変更点の優先度を設定したうえで、PCTは優先度の高いスレッドから順に実行を進めます。例えば、図2(b)では、PCTは初めに優先度3のThread 2から実行を開始し、if文の条件判定式に対応する最後の命令まで実行したところ（優先度変更点）でThread 2の優先度を1に下げます。この時点でThread 1の優先度2がThread 2の優先度1より高くなるため、PCTは次にThread 1の実行を開始します（x = nullが実行される）。最後に、Thread 1の実行が終了またはブロックした後でPCTはThread 2の実行を再開します（x->print()が実行されSegmentation Faultが起きる）。このようにして、PCTは図2(b)の原子性違反を検知します。図2(a)の順序違反の検知と図2(c)のデッドロックの検知も同様に機能します。
PCTが各実行につき1/(nk^(d-1))の確率で並行バグを検知できる理由を図2(b)の原子性違反（d=2）の検知の例に基づき説明します。まず、PCTがこの原子性違反を検知するには、d-1個（=1個）の優先度変更点をif文の条件判定式の最終命令上に設置する必要がありますが、命令列の長さがkであるため、この設置の確率は1/kです。更に、初期状態としてPCTはThread 2に対しThread 1よりも高い優先度を割り当てる必要がありますが、これはThread 1にn個のスレッドの中で最も低い優先度を割り当てることで実現でき、その確率は1/nです。結果として、PCTがこの原子性違反を検知できる確率は1/nkです。上記の議論における確率は、最悪のケースでの下限の確率を想定しています。しかし、現実には優先度変更点の設置個所は1命令に限定されず、ある範囲内の命令であれば良いケースもあります。例えば、図2(c)のデッドロックを検知するには、PCTはThread 1のlock(a)とlock(b)の間にあるいずれかの命令に優先度変更点を設置すれば十分です。このような理由から、現実にはPCTは対象の並行プログラムの各実行につき1/(nk^(d-1))より良い確率で並行バグの検知が可能であることが実験的に示されています[2]。PCTによる並行バグの検知確率保証に関する証明および現実の並行プログラムを対象とする並行バグ検知実験の詳細については論文[2]を参照してください。
並行ファジングの最近の研究動向
本稿で紹介した並行ファジングはPCTですが、この手法は2010年に発表されたもので、その後も並行ファジングの研究は進んでいます。例えば、2012年に発表されたヒューリスティクスベースの並行ファジング手法であるMaple[3]はPCTよりも並行バグの検知性能が高いという実験結果が得られています。また、PCTのアイデアを分散システムのバグ検知に拡張したPCTCP[4]という手法も2018年に発表されています。更に、2019年には洗練されたヒューリスティクスと遅延挿入等により並行バグをより効率的に発見するTSVD[5]と呼ばれる手法も提案されています。PCTCPとTSVDはそれぞれOOPSLAとSOSPというプログラミング言語とシステムソフトウェアの著名会議のBest Paperにも選出されており当該分野での注目を集めています。
参考文献
[0] Learning from Mistakes — A Comprehensive Study on Real World Concurrency Bug Characteristics [ASPLOS'08]
[1] Finding and Reproducing Heisenbugs in Concurrent Programs [OSDI'08]
[2] A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs [ASPLOS'10]
[3] Maple: A Coverage-Driven Testing Tool for Multithreaded Programs [OOPSLA'12]
[4] Randomized Testing of Distributed Systems with Probabilistic Guarantees [OOPSLA'18]
[5] Efficient Scalable Thread-Safety-Violation Detection [SOSP'19]
「分散並行バグ検査の基礎と実装」の付録
技術書典7 す04D バイナリイーターによる新刊
「分散並行バグ検査の基礎と実装」のサポートページ（主に以下の内容などを随時公開予定）
・本文/サンプルコードの正誤表
・サンプルコードのより詳細な説明
・動作環境構築手順
「動的バイナリ解析の基礎 with Intel Pin」の付録
技術書典６ え１１ バイナリイーターによる
「動的バイナリ解析の基礎 with Intel Pin」の付録として
「動的バイナリ計装に基づく動的記号実行」を随時掲載予定
付録目次
A1. 動的バイナリ計装に基づく動的記号実行
A1.1. 記号実行
A2.1.1. パス制約
A2.1.2. 記号状態
A2.1.3. 制約解消
A2.1.4. 静的記号実行の課題
A2.1.4.1. 制約解消系の限界
A2.1.4.2. パス選択の現実化
A2.2. 動的記号実行
A2.2.1. 動的記号実行の動機
A2.2.2. パス制約と記号状態の部分的具体化
A2.2.3. パス選択の具体化
A2.3. 動的バイナリ計装に基づく動的記号実行の実装
A2.3.1. パス制約の動的収集の実装
A2.3.2. 記号状態の動的管理の実装
A2.3.3. 制約解消の動的実行の実装
A2.3.4. PinとZ3を用いた網羅的バッファオーバフロー検出の実装
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で合成できる文法は限られています．これらの諸問題を実験的に明かしつつそれらの解決をはかる挑戦は，ちゃっく君の良き先輩であるところのななめ先輩（東工大権藤研）が修士研究で取り組んでおり面白い成果を出してくれています．来年のアドベントカレンダーでは，ななめ先輩の研究成果の国際会議発表バージョンを紹介できればいいな⭐⭐⭐（おしまい）
