命令のランダム性に基づくプログラム難読化の評価尺度
二村阿美 (1151093)


近年，不正行為を目的としたプログラム解析を防ぐために，様々なプログラム難読化法が提案されてきたが，
その評価に関する研究はほとんど行われていない．
本論文では，命令のランダム性に基づくプログラム難読化の評価尺度を提案する．
基本アイデアとしては，各命令が全くランダムにプログラム中に出現する場合，すなわち，
(1)各命令の出現頻度が等しく，かつ，(2)その並びに規則性がない場合に，
プログラム解析が最も困難な状態であると考える．
前者はエントロピー，後者はコルモゴロフ複雑性の概念を用いて定量化する．

評価尺度の有用性を確認するために，AES暗号によるデータ復号プログラムを難読化し，評価を行った．
その結果，既存の難読化法はエントロピーを増大できておらず，
難読化後のプログラムには，解析の手がかりとなり得る出現頻度の低い命令が存在することが分かった．
また，コルモゴロフ複雑性に基づく尺度により，特定の難読化の実装方法の問題点（命令列のパターンが多数生じる）を発見できた．

さらに，プログラムの長さとコルモゴロフ複雑性の関係について実験を行った．
プログラムの長さに基づく平均的なコルモゴロフ複雑性を算出し，コルモゴロフ複雑性の値から，
平均的なプログラムより理解しやすいか，理解しにくいかという評価を行った．
その結果，難読化前のプログラムは平均より理解しやすいプログラムであったが，
命令順序のパターンを消去する難読化によって，平均より理解しにくいプログラムとなった．

また，攻撃者によって動的解析が行われることを考慮し，実行系列を対象に難読化の効果を評価した．
実験の結果，静的な難読化のみを行っても，命令のランダム性という観点については効果がほとんどないことが分かった．
動的解析を防ぎたい場合，ループ文などの繰り返し部分にランダム要素を導入することの必要性が示唆された．