Wednesday, November 10, 2021

ARM CoreSightを用いた効率的なBinary-only Fuzzing

英語版はこちら: ARMored CoreSight: Towards Efficient Binary-only Fuzzing

著者:

はじめに

わたしたちRicerca Securityはファジングの研究開発に取り組んでいます。このたび、その一環として開発したAFL++ CoreSight modeをOSSとして公開しました。これは、ファジングツールのデファクトスタンダードであるAFL++に対して、CoreSightという一部のARMプロセッサで有効なCPU機能を活用したフィードバック機構を追加したものです。

ファジングとは、プログラムの入力に変異を施し、その脆弱性を自動的に発見する技術です。一般に、プログラムのソースコードが手元にない場合のファジング (Binary-only Fuzzing) では、QEMUなどによるバイナリへのinstrumentationを通じてプログラムの実行をトレースする必要があります。今回開発した手法では、QEMUの代わりにCoreSightをinstrumentationに用いることで、より高速なBinary-only Fuzzingを実現できました。

AFL++ CoreSight modeは以下のリポジトリで公開しています。

本記事では、AFL++ CoreSight modeの概要と開発の経緯を紹介します。

ARMにおけるBinary-only Fuzzing

ファジングツールの代表例として知られるAFLや、その高機能版forkであるAFL++は、Coverage-Guided Fuzzingと呼ばれる手法を用いています。これはファジング対象Program Under Test (PUT) 実行時にカバレッジをフィードバックとして取得し、新しい分岐に遷移してカバレッジが拡大するような入力を探索する手法です。

PUTのソースコードが手元にある場合、ファジングツールはそのビルド時にフィードバック取得用のコードをinstrumentします。一方で、PUTのソースコードがなくバイナリのみが手元にある場合、すなわちBinary-only Fuzzingでは、ファジングツールはbinary instrumentation toolやbinary rewriting toolを用いたinstrumentationを行います。Binary-only Fuzzingよりもソースコードありのファジングの方が効率的ですが、プロプライエタリソフトウェアや、特にファームウェアの解析においてはBinary-only Fuzzingが前提となってくることが多いです。

さて、Binary-only Fuzzingにおけるinstrumentationの方式には、図1のように静的な方式と動的な方式の2種類が存在します。前者は、e9patchなどを用いてPUTのバイナリにパッチを当て、静的に書き換える方式です (図1 (a))。後者は、QEMUやDynamoRIOなどを用いてPUTのバイナリの実行時にフィードバック取得用のコードをinstrumentationする方式です(図1 (b))。Binary-only Fuzzingのデファクトスタンダードとして知られるAFL++ QEMU modeもこの方式に該当します。残念ながら、前者の方式はARMバイナリに対応しておらず、後者の方式は低速であるという問題があります。そのため、これまでARMにおけるBinary-only FuzzingはQEMUによる低速なinstrumentationに頼らざるを得ませんでした。

図1. Fuzzingのinstrumentationにおいて静的な方式と動的な方式
図1. Fuzzingのinstrumentationにおいて静的な方式と動的な方式

わたしたちは、この制限を打破する手がかりとして、ARMベースのSystem on Chip (SoC) の一部で実装されているCoreSightというCPU機能に着目しました。CoreSightは分岐命令の実行を捕捉する機能であり、QEMUなどの代替として利用できると考えたのです。すでに、Intelプロセッサ版のCoreSightともいえるIntel Processor Trace (Intel PT) は、kAFLをはじめとしてBinary-only Fuzzingに活用されています。そこで、わたしたちはIntel PTとARM CoreSightの差分を整理し、前者を活用した手法の優れた点をCoreSight向けに取り入れることをめざしました。図2に示すように、CoreSightを用いたinstrumentationはQEMUを用いた手法同様に、実行時にinstrumentationを行います。QEMUを用いた手法 (図2 (b-1)) ではPUTをVM上で実行し、フィードバックの生成を各ベーシックブロックの遷移時に同期的に実行するため低速ですが、CoreSightを用いた手法 (図2 (b-2)) ではPUTはCPU上でネイティブに実行され、フィードバックの生成は非同期に行われるため、QEMUを用いた手法よりも高速です。

図2. QEMU modeとCoreSight mode
図2. QEMU modeとCoreSight mode

CoreSight概説

CoreSightやIntel PTは、デバッグやパフォーマンス計測を目的とした、CPUの挙動を実行時にトレースするしくみです。両者はいずれもファジングに必要な分岐先情報などのフィードバックを得るのに十分な機能を備えています。しかし、CoreSightはIntel PTと比較して仕様上定義されている機能が豊富である点、Intel PTでは機能全体が統合されて1つの機能として提供されているものの、CoreSightは複数種類のハードウェアコンポーネントの組み合わせとして提供されている点が異なります。

CoreSightのコンポーネント構成はSoCの設計時に決定され、どのようなコンポーネントがどのように接続されているかはSoCによって大きく異なります。ただし、共通的なコンポーネントとしてTrace Source、Trace Sink、Trace Linkの3種類が存在します。Trace Sourceはトレースの生成元となるコンポーネントであり、Trace Sinkはトレースを保存または転送するコンポーネントです。Trace LinkはTrace SourceとTrace Sinkを仲介するコンポーネントです。CoreSightではトレースをパケットと呼ばれるビット列で表現し、一連のパケットをまとめてトレースデータと呼称します。トレースデータからプログラムの挙動を復元するには、各パケットをデコードする必要があります。

より詳細なCoreSightの紹介は、以下のようなARM公式ドキュメントを参照してください。

かいつまんでまとめると、CoreSightからフィードバックを得るには、その各コンポーネントを制御するトレーサと、トレーサが生成したパケットのデコーダを実装しなければなりません。

AFL++ CoreSight mode

今回のAFL++ CoreSight modeでは、トレーサとデコーダをそれぞれcoresight-traceとcoresight-decoderというsubmoduleとして新たに開発しました。coresight-traceの特徴は、CoreSightの操作を含むすべての動作をユーザー空間で行っており、LinuxカーネルのCoreSightデバイスドライバに依存していないことです。これにより、Device Treeなどにコンポーネントが登録されておらずLinuxカーネルがCoreSightを認識できないシステムでもトレースを取得可能となっています。 coresight-decoderの特徴は、フィードバックにAFLが用いるカバレッジ表現であるエッジカバレッジと、PTrixというIntel PT向けのカバレッジ圧縮手法を転用したパスカバレッジの2種類が選択できること、複数のキャッシュ機構を備えトレーサと並列に動作し高速化を図っていることです。ハードウェアトレーサを使ったファジングではデコード処理がボトルネックになるため、Intel PTにおけるプラクティスを踏まえた形です。

トレーサとデコーダは以下のリポジトリで公開しています。

以降の章ではCoreSightをファジングに利用する上で解決した技術的課題について、トレーサとデコーダの2つのコンポーネントの観点から解説します。

トレーサ

トレーサはPUTプロセスを監視してフィードバックに必要なトレースを過不足なく取得できるようにCoreSightコンポーネントを制御する役割を担います。トレーサはPUTプロセスが作られるとトレースを開始、終了したらトレースを停止・取得してデコーダにそのデコードを依頼します。

今回開発したトレーサは、実体としてはafl-proxyをベースとしたプロキシアプリケーションとして実装されています。オリジナルのAFLで指摘されているように、PUTの実行に際して大量のfork+execを行うとexecのオーバーヘッドによるパフォーマンス低下が知られています。このため、PTrixの実装と同様にexecを回避するfork server modeを実装しています。

AFL++ CoreSight modeの動作フローを図3に示します。このモードはAFLファザー、プロキシアプリケーション、PUTから構成されます。プロキシアプリケーションはトレーサとデコーダから構成されており、トレーサとデコーダは独立したスレッドで非同期にトレースとデコードをします。

図3. AFL++ CoreSight modeの動作フロー
図3. AFL++ CoreSight modeの動作フロー


トレーサを実装する過程で、CoreSightの仕様に起因する数々の技術的課題にアプローチする必要がありました。本章の以降の節では@retrageがその工夫を解説します。

トレースのフィルタリング

フィードバックの生成に必要なトレースを得るにあたって、PUTプロセスのトレースのみを出力するためのフィルタを設定する必要があります。広く知られている方法は、CONTEXTIDRレジスタに設定されるPIDの値を比較して対象のPIDのプロセスのみフィルタする方法です。しかし、ファジングループのたびにPIDが変動することから、この方法ではそれに応じてその都度フィルタを再設定する必要があるため、結果としてパフォーマンスの低下を招きます。今回実装したfork server modeでは、fork先のPUTのプロセスのアドレスレイアウトは変化しないことに注目し、初回に単一のアドレス範囲のみをフィルタに設定することでこの問題を回避しています。

Embedded Trace Routerを使ったDRAMへのトレースの保存

先に説明したようにCoreSightではTrace Sinkという種類のコンポーネントがトレースデータを保存または転送します。典型的なアプリケーションのファジングでは、ひとつのプロセスの開始から終了までのすべてをトレースするため、Trace Sinkは十分な容量のバッファを持っていることが望ましいです。加えて、ファジングでは高速に動作することが求められるため、トレースデータの転送速度も重要です。しかし、CoreSightではどのようなTrace SinkがあるかはSoCによって大きく異なり、安価なSoCでは十分な容量と転送速度を持ったTrace Sinkを持っていない場合があります。 比較的安価なSoCに多いCoreSightの構成例を図4に示します。

図4. ETBにトレースを保存するCoreSightの構成例 (ID010111 Revision r0p1 Figure 1-4をもとに作成)
図4. ETBにトレースを保存するCoreSightの構成例 (ID010111 Revision r0p1 Figure 1-4をもとに作成)


この例ではEmbedded Trace Buffer (ETB) というTrace Sinkが持つSRAMにトレースを保存します。複数の各Trace Sourceが出力したトレースはFunnelと呼ばれるTrace Linkで統合されてからETBに送られます。ETBは専用のSRAMをバッファとするため低遅延という利点がありますが、バッファの容量が小さいという欠点があります。たとえば、libxml2の実行では450KB程度のトレースが生成されるのに対し、ETBのバッファは4KBから64KB程度しかなく、トレースを記録するのに十分な容量がありません。このような環境でのファジングでは、定期的にPUTを一時停止させてトレースを退避する必要が生じます。しかし、PUTの規模が大きくなるとともにトレース退避の頻度は高くなるため、ETBでは実用的な実行速度を得ることができません。

そこで、一部のSoCで実装されているEmbedded Trace Router (ETR) を利用します。ETRはIntel PTのようにDRAMにトレースを保存するTrace Sinkです。ETBではSRAMバッファの容量は固定である一方、ETRは最大4GBまで動的にDRAMの領域を確保します。 ETRを備えたCoreSightの構成例を図5に示します。

図5. ETFを経由してETRでDRAMにトレースを保存するCoreSightの構成例 (ID010111 Revision r0p1 Figure 1-8をもとに作成)
図5. ETFを経由してETRでDRAMにトレースを保存するCoreSightの構成例 (ID010111 Revision r0p1 Figure 1-8をもとに作成)


ETRはDRAMを使うため大容量である一方で、ほかの優先度の高いDRAMへのアクセスがあった場合には遅延が発生するという欠点があります。そこでEmbedded Trace FIFO (ETF) をFIFOバッファとして利用することで遅延発生時にトレースが失われないように構成されています。この例では、ETFはReplicatorと呼ばれるTrace Linkを介してETRに転送します。ETRはETBと比較して遅延があるものの、次に示すようにJetson TX2を使った簡単な実験ではETRを使った方が高スループットである、ということが判明しています(ここでのETBは厳密にはETFですが、ETFは後述するモード指定によってETBとして利用できるためこのような表示としています)。

Size (KB) Read (MB/sec)
ETB 32 23.3
ETR 1024 65.8

今回開発したcoresight-traceはこのようなCoreSightのハードウェア上の制約から、現在は図5のような構成のシステムを前提としています。

Overflow Packetの扱い

Trace Sinkには複数の動作モードがあり、どのように使うかによって指定するモードが異なります。ユーザーのトレース読み出し先のTrace SinkはCircular Buffer modeというリングバッファとして使うモードを指定します。このモードではバッファが溢れるとオーバーフローを示すステータスレジスタのビットが立つため、実行時に容易にトレースデータの欠損が検知できます。

一方、図5のETFのようにTrace SinkをFIFOバッファとして使う場合、Trace SinkをHardware FIFO modeというモードに設定します。このような中間にあるTrace Sinkはバッファが溢れそうになると後方に配置されているコンポーネントに対してその旨を通知します。これをBack Pressureといい、Back Pressureが通知されるとTrace SourceはOverflow Packetという特別なパケットを送信してからオーバーフローが解消されるまで待機します。ETFにおいてBack Pressure発生時の挙動を図6に示します。

図6. ETFにおけるBack Pressure発生時の動作
図6. ETFにおけるBack Pressure発生時の動作


パケットの送信が中断されている間もCPUの実行は続行しているため、トレースは欠損している可能性があります。このため、Overflow Packetを含むトレースデータは厳密には不完全であるため破棄すべきであるとされています。しかし、実験では高い頻度でOverflow Packetが見られ、厳密にOverflow Packetを含むトレースを破棄して再実行する方法では現実的な実行速度を得られないことが判明しました。ここで、ファジングでは新しい実行パスを検出するまでに何回もPUTの実行を繰り返し、かつ生じた欠損はトレース全体で見た場合にごくわずかであることから、トレースが欠損した期間の実行は高い確率で既知の実行パスであり、欠損により新しい実行パスが検出できない可能性は低いと考えられます。そこで、この仮定のもとOverflow Packetが検出されてもトレースを破棄せずあえてそのままデコードする方法を採用することにしました。この方式はCoreSight利用上の指針には反するものの、この方法でも新しい実行パスを検出できることを実験的に確かめています。

以上、PTrix準拠のアーキテクチャ採用、トレースのフィルタリング、ETRの利用、Overflow Packetの扱いの工夫を通じて、CoreSightの利点を最大限に活用するトレーサを作り込みました。

デコーダ

デコーダはトレーサが取得したトレースデータを受け取り、ファジングのフィードバックを生成する役割を担います。今回開発したデコーダcoresight-decoderは、ライブラリとしてトレーサに提供されています。

デコーダはハードウェアトレーサを用いたファジングにおけるボトルネックとなりうる箇所であるため、高速化のための工夫を要します。本章の以降の節では@mmxsrupがその工夫を解説します。

デコーダ概説

デコーダの目的は、トレースデータから実行履歴を復元し、ファジングのフィードバックとして利用するカバレッジを計算することです。CoreSightやIntel PTなどのハードウェアトレーサは完全な実行履歴を保存せず、部分的な情報のみをパケットの形式でエンコードしてトレースバッファに保存します。これにより、トレースのパフォーマンスは向上するものの、トレースデータのみを利用してPUTの実行履歴を復元できなくなります。たとえば、間接分岐命令の実行が記録される場合、トレースデータにはその分岐命令で分岐したかどうかの情報しか記録されず、分岐先アドレスは記録されません。分岐先アドレスを得るには、デコーダからPUTのバイナリを解析する必要があります。

実際に、下の図7で示すアセンブリコードとそのアセンブリコードを含むプログラムバイナリのトレース結果をもとに、デコードの手順を説明します。以下のアセンブリコードは0x71cから始まるループ構造を含むコードと、0x900から始まるそれを呼び出すためのコードから構成されています。トレース結果には、分岐情報を示すパケットであるAddressパケットとAtomパケットが記録されています。Addressパケットは間接分岐で分岐した先のアドレスの情報を記録するパケットです。Atomパケットは直接分岐命令の結果を示すもので、その分岐で分岐した場合、E(taken)が記録され、分岐しなかった場合、N(not-taken)が記録されます。 また、パケットの圧縮効率などのために、1つのAtomパケットに複数の分岐情報が含まれることもあります。例えば、AtomのEEENは、3回連続で分岐し、4回目は分岐しなかったことを示します。

1番目に記録されているAddressパケットは、トレースの開始アドレスを示すものです。つまり、この例ではアドレス 0x0000aaaaceaa0900 から実行が開始されたことを示しています。Addressパケットが示すアドレス情報は実アドレスであるため、実際にプログラムバイナリのどこを実行しているか知るためには、テスト対象のプログラムのメモリマップ情報が必要になります。メモリマップ情報から実際の位置を計算すると、アセンブリコードの0x900から実行が開始されたことを特定できます。次に記録されているパケットはAtomパケットであり、分岐命令で分岐したことを示しています。アセンブリコードの 0x900 から順方向にコードを見ていくと、0x908 に直接分岐命令である bl があります。つまり、このAtomパケットはこの分岐命令で分岐し、0x71c に制御フローが変わったことを示しています。3つ目のパケットはAtomパケットであり、分岐命令で3回分岐し4回目に分岐しなかったことを示しています。アセンブリコードの 0x71c から順方向にコードを見ていくと、0x730 に直接分岐命令である b.ne があります。これはこの分岐命令による分岐が発生し、制御フローが 0x72c に変わったことを示してい、ます。同様にアセンブリコードの 0x71c から順方向にコードを見ていくと0x730b.ne があり、この命令で残り2回分岐し、最後に分岐せず制御フローが 0x734 に変わったことがわかります。続いて4つ目のパケットはAtomパケットであり、次の分岐で分岐したことを示しています。アセンブリコードの 0x734 から順方向にコードを見ていくと、0x73c に間接分岐命令である ret があり、この分岐命令で分岐したことを示しています。間接分岐命令の場合、Atomパケットとアセンブリコードの情報のみでは分岐先アドレスを特定できず、分岐先アドレスの情報を特定するために、後続に続くAddressパケットが使われます。このため間接分岐命令のトレースの場合、AtomとAddressパケットが出力されます。この例では、間接分岐命令で 0x0000aaaaceaa090c に分岐し、アセンブリファイルの 0x90c に制御が戻ったことを意味します。

図7. デコーダの動作
図7. デコーダの動作


Addressパケットに記録されているアドレスは実アドレスです。そのため、同じコントロールフローをたどる実行であっても、ファジングキャンペーン毎にAddressパケットの中身は変化することがありえます。そこで、エッジカバレッジの計算には、実アドレスではなくELFファイル上のオフセットを用いています。さらに、トレース対象のプログラムバイナリが複数ある場合、それぞれを区別するために、プログラムバイナリの識別子を用いています。

Intel PTとCoreSight間で、デコード手順の違いはほとんどありません。CoreSightのAtomパケットはIntel PTのTNTパケットに、AddressパケットはTIPパケットにそれぞれ対応します。また、CoreSightが生成するトレースデータは各コアから得たトレースデータを集約して記録します。そのため、上述のデコードの前処理として実際に必要なトレースのみをトレースデータから取り出す作業が必要です。

高速化

前節では、CoreSightのトレースデータからエッジカバレッジを復元するデコード手法を示しました。ファジングでは繰り返しPUTを実行します。つまり、トレースデータのデコードはPUTの実行回数分だけ発生します。よって、デコード処理にかかる時間がハードウェアトレースを用いたファジングのボトルネックとなりえます。残念ながら、予備実験を行ったところ、前述の単純なデコード手法はパフォーマンスの観点で実用に足らないことがわかりました。そこで、デコードの平行実行と、2つのソフトウェアキャッシュレイヤの導入により、さらなる高速化を図りました。

デコードの平行実行の目的は、トレースからデコードまでの一連の実行時間のレイテンシを小さくし、ファジングの1サイクルを高速化することです。トレース処理がすべて完了した後に、デコードの処理を開始すると、ファジングの1サイクルにかかる時間が長くなります。そこで、トレースの処理が一部終わるごとに、デコード処理を開始・再開できるようにしました。つまり、トレースとデコードを非同期に並列実行できるような工夫を設けました。これにより、トレース処理の開始からデコード処理の完了までにかかる実行時間が短くなり、ファジング全体の高速化が実現できます。断片的なトレースデータに対しても、デコード処理を実現できるようにしています。

キャッシュレイヤの目的は、ファジングサイクル中に反復的に行われる作業の結果を記録・再利用可能にし、デコード処理を高速化することです。ファジングでは、同じPUTのバイナリに対してトレースデータを複数回デコードし、エッジカバレッジを計算します。1回あたりのファジングサイクルごとに得られるカバレッジはほとんど同じであることが多いため、ファジングサイクルごとにディスアセンブルするプログラムバイナリの領域やトレースデータ自体はほぼ同一です。また、ループを含むようなプログラムの場合も同じ領域を複数回ディスアセンブルすることになります。要するに、ファジングではPUTを繰り返し実行する過程で同じ処理を繰り返すことが多いため、そうした作業結果をキャッシュすることで高速化が図れる、ということです。

実際に、Intel PT用のデコーダであるlibxdcも、ソフトウェアキャッシュを用いることで、デコード処理を高速化しています。本プロジェクトでも、libxdcと同様の方法で、2つのキャッシュレイヤを導入し、デコード処理を高速化しています。ただし、libxdcのコードベースはわたしたちにとって不要な箇所を多く含むことから、libxdcを参考にしつつもフルスクラッチでデコーダを開発しています。

1つ目のキャッシュレイヤはプログラムバイナリのディスアセンブル結果を保存し、無駄なプログラムバイナリの解析を省くために使われます。前節で例示したように、条件分岐のトレースを表すAtomパケットには分岐先のアドレスが記録されていません。そのため、デコーダはプログラムバイナリをディスアセンブル、分岐命令を発見し、分岐先のアドレスを解析する必要があります。同じプログラム領域に対するこの一連の作業は、ファジングサイクル中に何度も実行されます。そこで、この一連の作業の結果をキャッシュし、不必要なプログラムバイナリの解析処理を省いています。キャッシュはハッシュテーブルとして実装され、キーは開始アドレス、データはその開始アドレスから最も近くにある分岐命令の分岐先アドレスとしています。

2つ目のキャッシュレイヤはエッジカバレッジの計算結果を保存し、無駄なAtomパケットの解析を省くために使われます。前章で説明したように、1つのAtomパケットは複数の分岐履歴を含む場合があります。この場合、Atomパケットに保存されているEN列をもとに、それぞれの分岐先アドレスを解析し、エッジカバレッジを計算します。トレースデータ自体が同じである場合は多いため、この一連の作業はファジングサイクル中に何度も実行されます。仮にキャッシュレイヤ1があったとしても、ハッシュテーブルに保存されているデータを使いながら、エッジカバレッジを復元する作業を繰り返し行う必要があります。そこで、この一連の作業の結果をキャッシュし、不必要なAtomパケットの解析を省いています。キャッシュはハッシュテーブルとして実装され、キーは開始アドレスとAtomパケットで、データはエッジカバレッジの計算結果です。

実際に、この2つのキャッシュの動作について、下の図8を用いて説明します。この例では先程説明した単純なデコードした結果がキャッシュに保存されており、2回目のファジングキャンペーンで図8に示すパケットが得られた場合に、どのようにデコードが行われるかを示しています。① 0x900 から開始するトレースでAtomのEが記録されている場合に、その時のエッジカバレッジが1段階目のキャッシュに保存されていないか検索します。② キャッシュヒットし、即座にエッジカバレッジを得ることができます。③ 0x71c から開始するトレースでAtomのEEENが得られた場合に、その時のエッジカバレッジが1段階目のキャッシュに保存されていないか検索します。④ キャッシュヒットし、即座にエッジカバレッジを得ることができます。⑤ 0x71c から開始するトレースでAtomのEが得られた場合に、その時のエッジカバレッジが1段階目のキャッシュに保存されていないか検索します。⑥ キャッシュミスしたため、2段階目のキャッシュに対して、0x71c 以降の最初の分岐命令の分岐先アドレスが保存されているか検索します。⑦キャッシュヒットし、分岐がTakenの場合の分岐先アドレスが 0x72c だと分かり、エッジカバレッジが計算できます。この例のように、仮に同じコントロールフローをたどるトレースであっても、割り込みなどの外的要因によりトレースデータが一致するとは限りません。このような場合に、2段階目のキャッシュが役立ちます。⑧ 1段階目のキャッシュにデコード結果を追加し、キャッシュを更新します。⑨ 0x750 から開始するトレースでAtomのEが得られた場合に、その時のエッジカバレッジが1段階目のキャッシュに保存されていないか検索します。⑩ キャッシュミスしたため、2段階目のキャッシュに対して、0x750 以降の最初の分岐命令の分岐先アドレスが保存されているか検索します。⑪ 再びキャッシュミスしたため、 ターゲットバイナリをディスアセンブルし、0x750 から順に一命令ずつ確認し、分岐命令を探します。⑫ 分岐命令 b.ne 780 を見つけ、分岐先アドレスを特定し、エッジカバレッジが計算できます。⑬ 1段階目のキャッシュと2段階目のキャッシュにデコード結果を追加し、キャッシュを更新します。

図8. 2つのキャッシュを利用したデコーダの動作
図8. 2つのキャッシュを利用したデコーダの動作


以上、Intel PTにおけるプラクティスをCoreSight向けに再現することで、デコーダのボトルネックの解消を図りました。

PTrixスタイルのパスカバレッジの設計と実装

本節ではPTrixで提案されているIntel PT向けの実行パスに敏感なフィードバックをCoreSight向けに実装したPTrixスタイルのパスカバレッジの設計と実装について解説します。

前節で説明したように、Intel PTのトレースを用いたエッジカバレッジの生成には、Intel PTのトレースだけでなくバイナリのディスアセンブルも必要です。このことから、PTrixの論文ではIntel PTのトレースから従来のAFLで利用されているエッジカバレッジを生成する手法は非効率であると指摘されています。そこで元のバイナリのディスアセンブル結果を使わずにトレースのデコード結果から直接フィードバックとなるビットマップを生成する手法を提案しています。この手法ではTNTパケットとTIPパケットからハッシュを計算し、得られたハッシュをエンコードしてビットマップを更新します。ハッシュ値はこれまでのトレースパケットの履歴を表現しているため、実質的にパスカバレッジとみなすことができます。PTrixの論文ではこのフィードバック表現によりエッジカバレッジよりも実行パスをよりよくとらえることができるとしています。

今回PTrixスタイルのパスカバレッジのCoreSight向け実装ではTNTパケットがAtomパケットに相当し、TIPパケットがAddressパケットに相当することを踏まえてハッシュを計算するように実装しました。また、AtomパケットのEN列を”0”と”1”の文字列として扱うことによりハッシュ計算の高速化を図りました。

以降の節でパスカバレッジの有効性を検証します。

ベンチマーク

以上、数々の高速化を取り入れてきましたが、その効果はどれほどのものでしょうか。ベンチマークを取得しました。

今回のベンチマーク取得では、AFL++ LTO mode(ソースコードのビルド時にinstrumentationを行うモード)、AFL++ QEMU mode、AFL++ CoreSight mode(エッジカバレッジを取得する設定)、AFL++ CoreSight mode(パスカバレッジを取得する設定)の4種類のファザーを用いました。また、void main(void) {}のような非常に簡単なアプリケーションをPUTとし、各ファザーを用いて60秒間実行した回数を比較しました。PUTを簡単なアプリケーションとしている理由は、そのパスの性質にファザーが左右されないようにするためです。

# of exec exec/sec
LTO mode 169169 2819.5
QEMU mode 64307 1071.8
CoreSight mode (Edge cov.) 96490 1608.2
CoreSight mode (Path cov.) 99744 1662.4

結果として、CoreSight modeはエッジカバレッジとパスカバレッジどちらの設定でもQEMU modeより高速でした。また、エッジカバレッジよりもPTrixに準拠したパスカバレッジを用いた方がやや速い結果となりました。この結果は、PTrixの論文で示されている実験結果とも一致します。残念ながら、Binary-only Fuzzingはソースコードありのファジングの速度を越えることはできませんでした。これは、CoreSightを扱う処理のオーバーヘッドによるものだと考えられます。しかし、ARM向けバイナリ、ことファームウェアの解析においてソースコードを入手できる機会はまれであり、実用上QEMUより速いBinary-only Fuzzingの効果は十分に見込めるものと考えています。

パスカバレッジモードの有効性

次にパスカバレッジモードの有効性を検証しました。前節で用いた4種類のファザーについて、次のようなアプリケーションをPUTとして最初にクラッシュを観測するまでの実行回数と生成されたシード数を比較しました。このPUTは標準入力から入力を受け取り、その先頭10文字を比較してaaaaabbbbbと一致すればcrash()に到達してクラッシュするように作られており、到達するにはその実行パスが重要となります。このPUTはPTrixの実装から参照しました。

  read(0, src, SIZE);

  for (int i = 0; i < SIZE; i++) {
    if (src[i] == 'a') {
      dst[i] = src[i];
      continue;
    }
    if (src[i] == 'b') {
      dst[i] = src[i];
      continue;
    }
    break;
  }

  if (!strncmp(dst, "aaaaabbbbb", 10)) {
    crash(0);
  }

得られた結果を次の表に示します。

# of exec # of seeds
LTO mode 153260 11
QEMU mode 144645 12
CoreSight mode (Edge cov.) 146844 16
CoreSight mode (Path cov.) 135308 98

この結果では、LTO modeとQEMU mode、CoreSight modeでのエッジカバレッジはほぼ同じとなりました。一方、CoreSight modeのパスカバレッジは最も少ない実行回数でクラッシュに到達しています。シード数では、パスカバレッジはより多くのシードを生成しており、意図した通りに実行パスの違いにエッジカバレッジより敏感なフィードバックであることを示唆しています。

おわりに

本記事では、Binary-only Fuzzingの高速化のためにCoreSightを活用する取り組みを紹介しました。この取り組みにより、ARMにおける高速なBinary-only Fuzzingの実現可能性に一定の答えを見いだせたと思っています。わたしたちRicerca Securityは、オフェンシブセキュリティの新たな価値を開拓するべく、今後もファジングの研究開発を多方面から積極的に進めてまいります。その検討を加速化するために、システムプログラミングに対する理解や最新の研究にキャッチアップするスキルのある方を募集しています。ご興味のある方は採用情報をご覧ください。

謝辞

本研究は防衛装備庁令和3年度安全保障技術研究推進制度委託事業 (JPJ004596) の一環として実施したものです。また本システムのプロトタイプ開発に携わった大塚馨氏に感謝いたします。