cafebabe.jp 日々のよしなしごとをのたまうブログ.

194月/110

増分難読化

DotfuscatorDash-O に代表される難読化ツールに搭載されている機能の一つで,最近見る難読化ツールにはよく見られる.

難読化はプログラムコードを読みにくく変換する.そして,その変換作業において,プログラムコード上の多くの様々な情報と整合性を持たせて,変換後のプログラムも実行に支障がでないようにする必要がある.そのため,従来の難読化ツールはプログラムの実行に要する全てのファイルを与えられなければ正常に実行できる難読化後のプログラムを得ることはできなかった.

この増分難読化は上記の従来の制限を取り外すもので,難読化ツールにプログラム全体を常に与える必要はないものである.難読化処理にも時間がかかるため,プログラムの規模が大きくなると,毎回全てのプログラムコードを難読化していると,オーバーヘッドが無視できない場合がでてくる.そのため,変更が行われた部分のみを難読化ツールに与えて実行可能なプログラムを得る機構である.

具体的な方法として,名前難読化であれば,名前をどのように変換したのかのマッピング情報を同時に与えることで可能である.この増分難読化の実装はツールに依存し,全ての難読化手法で有効であるとは限らない.

 
184月/110

自然言語を対象としたバースマーク

あらゆる文章にもその文章の主題や著者特有の言い回しなど,何らかの特徴が出るはずである.そのため,自然言語で書かれた文章からでもバースマークが抽出できるはずである.Yangらはこの考えのもと,自然言語を対象としたバースマークを提案した.

文章は数多くの単語で構成され,それらの単語は名詞や動詞などに分類することが可能である.Yangらはそれら単語の品詞ごとの出現頻度に着目したバースマークを提案している.

ある文章中に存在する全ての名詞のうち,特定の辞書に載っている単語のみを取り出し,その出現頻度を名詞バースマークと定義している.同様に動詞バースマーク形容詞バースマーク副詞バースマークを提案している.

 
174月/110

k-gramバースマーク

静的バースマークの一つで G. Myles らによって提案された.

クラスファイルから opcode (getfield, invokespecial, invokevirtual, etc.) を取り出して得られたシーケンスから k-gram を抽出する.得られた k-gram の集合から重複したものを取り除いた集合が k-gram バースマークである.

k-gramとは n-gram とも言われ,シーケンスからk個の連続した要素を取り出して,それを一つの新たな要素とする集合のことを指す.例えば「おなかとせなかがくっつくぞ」から4gramを取り出すと,以下の要素を持つ集合が得られる.

  • おなかと
  • なかとせ
  • かとせな
  • とせなか
  • せなかが
  • なかがく
  • かがくっ
  • がくっつ
  • くっつく
  • っつくぞ
 
164月/110

難読化手法 ― 演算子の変換によるデータ符号化

データを隠すための難読化手法のひとつにデータ(定数値)を予め一次式Sで変換しておき,その定数値が代入された変数の研鑽結果もSを満たすように式を変換する難読化手法.

例えば,定数値cS = 2 c + 6という一次式で変換し,その変換結果をc'とする.そして,ソースコード中に現れる全てのcc'にする.しかし,元の値cを含む式S1 = 3 c + 9cを単純にc'に置き換えただけでは計算結果が本来のものとは異なるため,ソフトウェア全体の動作も異なる恐れがある.そのため,計算結果もSを満たすように式を変換する.変換結果はS1'= 3 c' + 6となり,計算結果は本来の計算結果 r1に対して S の変換を行った値となる.

この難読化手法では計算の途中に元のデータが一切出現しないことがメリットであるが,数値のオーバーフローについては手法として考慮されていないため,オーバーフローを起こる場合は難読化適用者側で int 型を long 型に変換するなどを行う必要がある.また,最終的に値を出力に用いる場合,必ず復号の式(先ほどの例ならば c = (1/2) * c' - 3)が現れるため,適用するときには注意が必要である.

 
154月/110

難読化手法 ― 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; }
  }
}
 
144月/110

難読化手法 ― オーバーロード誘導 (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#では確認していないが,ローカル変数の場合,バイナリレベルではインデックスのみで参照され,名前は参照されないため,同じ名前を使うことが可能である.

また,拡張オーバーロード誘導という上に記したオーバーロード誘導を拡張したものがある.その拡張とは,同じメソッドか否かを判定するルールに従来は引数の数と型のみに着目していたが,拡張オーバーロード誘導ではメソッドの帰り値も参照する.バイナリレベルでは引数の数と型が同じでも帰り値が異なれば異なるメソッドであると判断されるので,このルールを使うことが可能である.ただし,これは仕様に合致しているかどうかは微妙なところである.

 
124月/110

難読化手法 ― ダミー命令追加

プログラム中にダミーの命令(bogus code)を追加する難読化手法.手法としては非常に単純で実装も難しいものではない.さらに,プログラムの意味が理解できれば逆難読化もそれほど難しいものではないと思う.しかし,その反面,この難読化手法が電子透かしの破壊やバースマークの改変といった攻撃として使われると,高い効果を出す場合が多い.

この難読化手法は目的によって追加するダミーの命令は異なっているが,良く行われるものとしては,副作用のないメソッドの呼び出しや不要な計算式の追加,必要のないフィールド変数,ローカル変数の宣言とそれらに対する処理などが考えられる.また,ダミーの命令ではなく,ダミーのデータを挿入することも考えられる.

 
94月/110

難読化手法 ― Opaque Predicate

難読化に用いられたり,電子透かしを入れる場所を確保するために使われたりする技術.常に真(もしくは偽)となる条件文を加え,実行されない部分にダミーのコードを入れておく手法.

ソースコード上でこのような条件文を加えると最適化で削除される可能性がある.そのため,バイナリに直接条件文とダミーコードを挿入したり,静的に真偽が判断できないような条件にしたりと色々考えられている.

この Opaque Predicate でよく使われるのは以下のような実数の特徴を用いたものである.

(v + (v + 1)) / 2 == 0
ある整数とそれに1を足した数を足し合わせると必ず奇数になる.そのため,この条件は常に偽となる.
(v * v) >= 0
ある整数の2乗はかならず正の数となる.そのため,この条件は常に真となる.

参考文献

  • Geneviève Arboit, "A Method for Watermarking Java Programs via Opaque Predicates," In The Fifth International Conference on Electronic Commerce Research (ICECR-5), 2002
  • Christian Collberg, Clark Thomborson, Douglas Low, "Obfuscation techniques for enhancing software security," United States Patent 6,668,325, June 1998, Published: December 20, 2003. http://www.freepatentsonline.com/6668325.html
 
84月/110

難読化手法 ― 名前難読化

プログラム中の名前の定義部分を変更し,意味のない名前に変更する.例えば,maxという変数名をv1のような名前に変更する.このアルゴリズムは,現在発表されている難読化ツールのほとんどが実装しており,変換後の名前の決め方に各難読化ツールの特色が表われている.

例えば,Dash-ODotfuscator には オーバーロード誘導 (Overload induction) というアルゴリズムが採用されている.これはオブジェクト指向のオーバーロードを巧みに利用しており,変換後の名前空間が最小になるように多くのメソッドにオーバーロードの関係を持たせる.

他にも,変換後の名前を予約語にしたり,また,非印字文字にする方法も考えられる.実際の難読化ツールの例では,個人的には,数値の連番か,文字の連番(aaa, aab, aac, ...)が多いように思う.

 
74月/110

難読化手法 ― 文字列暗号化

プログラム中に現われる文字列リテラルを予め暗号化しておき,実行時に復号することで,プログラム中から解析の手掛かりを隠す難読化手法である.

この手法は実装が簡単であるため,多くの難読化ツールで実現されている.バイナリをダンプしただけでは意味のないデータしか出てこないため,カジュアルハッキングを防止するためにも有効であろう.

 
1 / 212