本:Decompiling Android
Androidアプリをデコンパイルしようとするときに読む本.
この本だけでは,デコンパイルはできないと思われるが,基本的な Dalvik の構成などを理解するとっかかりとしては良い本だと思う.Javaクラスファイルからdexにどのように変換されるのかも説明されている.
なお,PDF版も公開されている(期間限定で公開されていたみたい).
Stigmata
StigmataはJavaの静的バースマークを統一的に扱うためのツールで http://stigmata.sourceforge.jp/ で公開されている.
バースマークは本ブログでも何度か取り上げているが,プログラムの実行に必要不可欠な部分をプログラムの特徴として抽出し,得られた情報を比較することでプログラムの類似性を計測する技術のことである.主に大量のプログラムの中から,盗用されたプログラムを見つけ出すために用いられる.そして,どのような特徴に着目するかにより,様々な種類のバースマークを抽出することができる.
電子透かしと異なり,実行に不可欠な情報を扱うため,予め情報を埋め込んでおく必要がなく,また,複数のバースマークを同時に使うことができるため,非常に簡易に用いることができる.
http://cafebabe.jp/categories/works/birthmarks
このようなバースマーク(のうち,静的解析により得られる静的バースマーク)をStigmataは統一的に扱おうとしており,現在,7種類の静的バースマークをクラスファイルから直接抽出することができる.そして,抽出されたバースマークを総当たりで比較することや,比較結果のフィルタリングすることが可能である.
増分難読化
Dotfuscator や Dash-O に代表される難読化ツールに搭載されている機能の一つで,最近見る難読化ツールにはよく見られる.
難読化はプログラムコードを読みにくく変換する.そして,その変換作業において,プログラムコード上の多くの様々な情報と整合性を持たせて,変換後のプログラムも実行に支障がでないようにする必要がある.そのため,従来の難読化ツールはプログラムの実行に要する全てのファイルを与えられなければ正常に実行できる難読化後のプログラムを得ることはできなかった.
この増分難読化は上記の従来の制限を取り外すもので,難読化ツールにプログラム全体を常に与える必要はないものである.難読化処理にも時間がかかるため,プログラムの規模が大きくなると,毎回全てのプログラムコードを難読化していると,オーバーヘッドが無視できない場合がでてくる.そのため,変更が行われた部分のみを難読化ツールに与えて実行可能なプログラムを得る機構である.
具体的な方法として,名前難読化であれば,名前をどのように変換したのかのマッピング情報を同時に与えることで可能である.この増分難読化の実装はツールに依存し,全ての難読化手法で有効であるとは限らない.
- Incremental Obfuscation (MSDN)
- Incremental Java Obfuscation (Zelix Klass Master)
- Incremental Obfuscation (Smokescreen)
- Incremental Obfuscation (Allatori Java Obfuscator)
自然言語を対象としたバースマーク
あらゆる文章にもその文章の主題や著者特有の言い回しなど,何らかの特徴が出るはずである.そのため,自然言語で書かれた文章からでもバースマークが抽出できるはずである.Yangらはこの考えのもと,自然言語を対象としたバースマークを提案した.
文章は数多くの単語で構成され,それらの単語は名詞や動詞などに分類することが可能である.Yangらはそれら単語の品詞ごとの出現頻度に着目したバースマークを提案している.
ある文章中に存在する全ての名詞のうち,特定の辞書に載っている単語のみを取り出し,その出現頻度を名詞バースマークと定義している.同様に動詞バースマーク,形容詞バースマーク,副詞バースマークを提案している.
k-gramバースマーク
静的バースマークの一つで G. Myles らによって提案された.
クラスファイルから opcode (getfield, invokespecial, invokevirtual, etc.) を取り出して得られたシーケンスから k-gram を抽出する.得られた k-gram の集合から重複したものを取り除いた集合が k-gram バースマークである.
k-gramとは n-gram とも言われ,シーケンスからk個の連続した要素を取り出して,それを一つの新たな要素とする集合のことを指す.例えば「おなかとせなかがくっつくぞ」から4gramを取り出すと,以下の要素を持つ集合が得られる.
- おなかと
- なかとせ
- かとせな
- とせなか
- せなかが
- なかがく
- かがくっ
- がくっつ
- くっつく
- っつくぞ
難読化手法 ― 演算子の変換によるデータ符号化
データを隠すための難読化手法のひとつにデータ(定数値)を予め一次式Sで変換しておき,その定数値が代入された変数の研鑽結果もSを満たすように式を変換する難読化手法.
例えば,定数値c を S = 2 c + 6という一次式で変換し,その変換結果をc'とする.そして,ソースコード中に現れる全てのcをc'にする.しかし,元の値cを含む式S1 = 3 c + 9のcを単純にc'に置き換えただけでは計算結果が本来のものとは異なるため,ソフトウェア全体の動作も異なる恐れがある.そのため,計算結果もSを満たすように式を変換する.変換結果はS1'= 3 c' + 6となり,計算結果は本来の計算結果 r1に対して S の変換を行った値となる.
この難読化手法では計算の途中に元のデータが一切出現しないことがメリットであるが,数値のオーバーフローについては手法として考慮されていないため,オーバーフローを起こる場合は難読化適用者側で int 型を long 型に変換するなどを行う必要がある.また,最終的に値を出力に用いる場合,必ず復号の式(先ほどの例ならば c = (1/2) * c' - 3)が現れるため,適用するときには注意が必要である.
難読化手法 ― If 文をtry-catchに置換
If文を隠すため,If文の代わりにtry-catch節を使う難読化手法.ダミーの例外クラスを作成し,try 節の中で作成した例外クラスを投げる.投げられた例外クラスに応じた catch 節で条件分岐を行う.
作成された例外クラス間の継承関係が複雑なほど,また,どの例外クラスのインスタンスが作成されたのかがわからないほど制御フローがわかりにくくなる.実際に作成される例外クラスはOpaque Predicateで隠すことになるだろう.
例
難読化前
class Example{ public void m(){ int i = 0; if(some condition) i = 3; else i = 0; } }
難読化後
class BranchException extends Exception{ ... } class E1 extends BranchException{ ... } class E2 extends BranchException{ ... } class E3 extends BranchException{ ... } class E4 extends BranchException{ ... } class E5 extends BranchException{ ... } class RIITCBObfuscationExample{ public void m{ int i = 0; try{ BranchException e = new BranchException(); if(opaque predicate 1) e = new E1(); else if(opaque predicate 2) e = new E2(); else if(opaque predicate 3) e = new E3(); else if(opaque predicate 4) e = new E4(); else if(opaque predicate 5) e = new E5(); throw e; } catch(E1 e1){ i = 1; } catch(E2 e2){ i = 2; } catch(E3 e3){ i = 3; } catch(E4 e4){ i = 4; } catch(E5 e5){ i = 5; } catch(BranchException e){ i = 0; } } }
難読化手法 ― オーバーロード誘導 (Overload induction)
PreEmptive Solutions 社が特許を保有する名前難読化の1 アルゴリズム.具体的な実装として,Java言語用の Dash-O と .Net用の Dotfuscatorが存在する.
http://www.freepatentsonline.com/6102966.html
http://www.agtech.co.jp/products/preemptive/dasho/overload_induction.html
http://www.agtech.co.jp/support/faq/PreEmptive/DotfuscatorV1_2/20040123015.html
直感的なアルゴリズムはシンボル名(クラス名,メソッド名,フィールド名,ローカル変数名)にできるだけ同じ名前を使いまわそうというものである.またメソッド間同士でも引数の数と型が異なれば異なるメソッドと判断されるため,同じ名前を使うことが可能である.C#では確認していないが,ローカル変数の場合,バイナリレベルではインデックスのみで参照され,名前は参照されないため,同じ名前を使うことが可能である.
また,拡張オーバーロード誘導という上に記したオーバーロード誘導を拡張したものがある.その拡張とは,同じメソッドか否かを判定するルールに従来は引数の数と型のみに着目していたが,拡張オーバーロード誘導ではメソッドの帰り値も参照する.バイナリレベルでは引数の数と型が同じでも帰り値が異なれば異なるメソッドであると判断されるので,このルールを使うことが可能である.ただし,これは仕様に合致しているかどうかは微妙なところである.
バースマーク (Birthmark)
プログラムの実行に必要不可欠な情報を,プログラムの特徴として抽出し,プログラムを識別するための技術がこのバースマークです.主に盗用されたプログラムを発見するために用いられます.プログラムのどんな情報に注目するか,その情報をどう扱うかによってバースマークの種類が異なります.
バースマークは電子透かしと異なり,予め情報を埋め込んでおく必要はありません.そのため,新たに提案されたバースマークを過去に配布されたプログラムに対して適用することが可能である反面,バースマークが偶然に一致する可能性があるため,盗用であることを証明することは難しくなっています.もちろん,何十何百の種類のバースマークが偶然に一致することは稀であると考えられるので,多くの種類のバースマークを用いれば盗用であることを証明することもできると考えられます.
バースマークは以下のように定義されます.
p, qを与えられたプログラムとする.f(p)をpからある方法fにより抽出された特徴の集合とする.このとき,以下の条件を満たすとき,f(p)をpのバースマークであるという.
- f(p)はプログラムpのみから得られる.
- qがpのコピーならば,f(p)=f(q)である.
また,バースマークは以下の性質を満たすこと望まれます.
- 保存性
- pから任意の投下変換により得られたp\'に対してf(p)=f(p\')を満たす.
- 弁別性
- 同じ仕様を持つpとqに対し,それらが全く独立に実装された場合,f(p) != f(q)となる.
バースマークは具体的には以下のものが提案されています.
- 静的バースマーク
- 変数初期値,継承関係,メソッド呼び出し系列,依存クラス,k-gram,...
- 動的バースマーク
- API呼出系列,API呼出頻度,プログラムパス,実行系列の抽象化,...
難読化手法 ― ダミー命令追加
プログラム中にダミーの命令(bogus code)を追加する難読化手法.手法としては非常に単純で実装も難しいものではない.さらに,プログラムの意味が理解できれば逆難読化もそれほど難しいものではないと思う.しかし,その反面,この難読化手法が電子透かしの破壊やバースマークの改変といった攻撃として使われると,高い効果を出す場合が多い.
この難読化手法は目的によって追加するダミーの命令は異なっているが,良く行われるものとしては,副作用のないメソッドの呼び出しや不要な計算式の追加,必要のないフィールド変数,ローカル変数の宣言とそれらに対する処理などが考えられる.また,ダミーの命令ではなく,ダミーのデータを挿入することも考えられる.