るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

パイプラインモデルを用いたシンボリックテイント解析の高速化

AdventCalendar Security

この記事は情報セキュリティ系論文紹介 Advent Calendar 2015 - Adventar9日の記事です。



TaintPipe: Pipelined Symbolic Taint Analysis [Ming,et al. USENIX SEC' 15]
https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-ming.pdf
を通してテイント解析の高速化事情について見ていく。


昨今、テイント解析はソフトウェアテストやマルウェア解析などを主とし、様々な場面で活用されている。
しかしテイント解析には問題点も多く、特にパフォーマンス面では解析対象の実行速度が6~30倍まで落ちるなど、あまり実用的ではないとされてきた。
ところが驚くことに、本論文におけるパイプラインキャッシュモデルおよびシンボリックテイント解析による並列モデルを用いた場合、実行速度を2.4倍の減速で抑える事ができ、実製品に充分組み込めるパフォーマンスになる。これはかなり革新的と言える。

TaintPipeの説明に入る前に、そもそもテイント解析がなぜそこまでしてパフォーマンスに影響するのか見てみる。



Dynamic Taint Analysis
Dynamic Taint Analysis(以下DTA)はIntel Pin[1]やValgrind[2]などのDBI(Dynamic Binary Instrumentation)フレームワークを用い、解析対象を動作せさながら動的にテイント伝搬を行っていくものだ。BitBlaze,BuzzFuzzなどが有名所だろう。プログラムを実際に動作させるため正確な情報を得ることができるが、複数の実行パスを通ることが難しかったり、DBIを使う際のオーバーヘッドが大きいなどの欠点がある。



Static Taint Analysis
一方Static Taint Analysis(以下STA)はプログラムのパフォーマンスへの影響が無く、複数の実行パスを選択できるがunder taintingやover taintingなど、正確性に欠けるゆえテイントの誤伝搬が発生しやすい[5]。Sun microによるParfait[3]やFlowDroid[4]などがある。

さてDTAはSTAより正確なテイントが可能だが大量の実行パスに向いておらずまたパフォーマンスが6~30倍まで落ちる。これまでパフォーマンス改善のために、ハードウェア支援機構を利用したり、ShadowReplica[6]などのようにDBIを用いたsoftware onlyな手段で最適化を行うといった取り組みがされてきている。

またテイント解析部分のロジックをアプリケーション本体から分離することで並列化を行うアプローチもある。
しかしこれはruntime valueをスレッド間で頻繁にやり取りする必要があり、またアプリケーションの実行と同期を取る必要があるためオーバーヘッドが大きかった。ShadowReplicaはDTA用にあらかじめ(staticに)アプリケーションのロジックを最適化する事で同期情報を減らし、劇的なパフォーマンス改善をもたらしたがこのような"primary & secondary"モデルでは限界があった。
そもそもstaticな最適化はマルウェアが難読化されている場合などに実現が困難なのは明白だろう。



TaintPipe
以上の問題点をふまえ本論文にて新たに提案されたのがTaintPipeである。
TaintPipeは新しい並列化技法であるpipelined symbolic taint analysisを用いており区分としてはDTAのsoftware onlyな手法にあたる。pipeline framework部分にPin,symbolic taint analysis部分にBAPを使用している。

f:id:RKX1209:20151210013827p:plain

vs Inlined Analysis(DBI)
DBIではレジスタの退避などのコンテキスト切り替えで余分な命令が生じパフォーマンスが落ちていたのに対し、TaintPipeはハードウェアのパイプラインモデルを使う事でこれを回避している。
キーとなるのはsymbolic taint analysis(以下STA)だ。
徒来のテイント解析ロジックの分離はアプリケーション実行部分とデータの関連度が強かったため並列化は難しいとされてきた。
しかしSTAはテイント情報がまだ分からない場合、一旦テイントタグをシンボルとしておいた状態で解析を進め、実際のデータが到着した際にテイントタグ情報に更新する事でこれらのデータ依存問題を一気に解決した。



vs “Primary & Secondary” Model
TaintPipeにおけるアプリケーションスレッドとテイント解析用スレッド間では極力少ないデータのやり取りで済ますようにしている。アプリケーションサイドはcontrol flow informationの計算のみを行うようにしている。



設計と実装
では実際の設計を見ていこう。

  • まずTaintPipeはtaint seeds(つまりstdioからの入力データやファイル,ネットワークI/O)を入力としてスレッド上でアプリケーション実行を始める。

この際軽量なcontrol flow informationのロギングも行う。ロギングはPinベースである

  • ロギングした情報をメモリバッファに記録するために第2スレッドが動きバッファが満杯になった時点でpipelined taint analysisを行う。このバッファにはN-wayバッファリングモデルが用いられており極力アプリケーションが実行を続けられるように工夫されている。

ロギングされる情報は、アプリケーションをbasic blockとよばれる分岐命令ごとのブロックにわけた物である。(正確にはこれを軽量化したDetailed Execution Profileモデルだが)

  • N-wayバッファのうち一つが満杯になった時点でセグメントを結合してコードを復元する。
  • 復元されたストレートなコードをテイント解析用命令に変換するこれにはBAP ILが用いられる。
  • テイント解析用命令から実際のsymbolic taint analysisを行う。これはOCamlによってBAP moduleベースなモジュールとして実装されている。

f:id:RKX1209:20151210013830p:plain


おわりに
テイント解析の並列化手法について現在最良と思われる手法を紹介した。パフォーマンス面では非常に期待されるがシンボリックにテイント伝搬する性質上、実際の攻撃が起こるまで伝搬が起こらないといった問題点もある。またシンボルの状態での伝搬にはパフォーマンス上まだまだ改善の余地がありこれからの発展に期待したい。



参考文献

[1] Pin - A Dynamic Binary Instrumentation Tool
https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool

[2] Valgrind
http://valgrind.org/

[3] Parfait – Designing a Scalable Bug Checker
http://llvm.org/pubs/2008-06-SAW-Parfait.html

[4] Steven Arzt, et al. PLDI'14
FlowDroid: Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps
http://www.abartel.net/static/p/pldi2014-FlowDroid.pdf

[5] Slowinska, et al. NDSS’11
A dynamic excavator for reverse engineering data structures
http://www.cs.vu.nl/~herbertb/papers/dde_ndss11-preprint.pdf

[6] Jee, et al. CCS’13
ShadowReplica: Efficient parallelization of dynamic data flow tracking
https://www.cs.columbia.edu/~angelos/Papers/2013/shadowreplica.pdf