コラッツの問題を用いた難読化は脅威なのか

TL;DR:

　ソフトウェアの多くは外部からの入力に依存する実行パス（trigger-based code）をもつ．
　これを記号的実行（symbolic execution, シンボリック実行）などの解析手法から隠蔽する手法として，コラッツの問題を用いた線型難読化（linear obfuscation）がある[1]．
　本稿ではしかし，線型難読化されたコードはコンパイラ最適化によってある程度除去できることを示す．

コラッツの問題

　コラッツの問題は数論の未解決問題のひとつである．
　任意の1でない自然数nに対して，nが偶数ならば2で割り，nが奇数ならば3倍して1を足す．この操作を繰り返していくと，どのような自然数nから出発しても，有限回の操作のうちに必ず1に到達する．
　この定理は経験則的に正しいと考えられているが，いまだ証明はなされていない．

線型難読化

　たとえば次のプログラムtr.cは外部からの入力に依存する実行パスをもつ．

1
2
3
4
5
6
7
8
9
10
11
// tr.c
#include <stdio.h>

int main(int argc, char *argv[])
{
    int x=argc;
    if(x==2)
        printf("triggered!\n");

    return 0;
}

　LLVM bitcodeレベルでのtr.cの制御フローグラフは次のようになる．

1
# clang -emit-llvm -c -g tr.c
# opt tr.bc -dot-cfg > /dev/null
# dot -Tpng cfg.main.dot > tr.png

　この単純なプログラムにたいして，コラッツの問題にもとづくループを挿入する．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// tr2.c
#include <stdio.h>

int main(int argc, char *argv[])
{
    int x = argc;
    int y = x + 1000;

    while(y > 1)
    {
        if(y % 2 == 1)
            y = 3 * y + 1;
        else
            y = y / 2;

        if((x - y > 0)&&(x + y < 4))
        {
            printf("triggered!\n");
            break;
        }
    }

    return 0;
}

　変数yは必ず1に到達する，いわば偽の変数である．
　難読化されたtr2.cの制御フローグラフは次のようになる．

　ループが挿入されたことによって実行パスが複雑化していることが見て取れる．

記号的実行

　では，線型難読化がどれほど記号的実行にたいして効力をもつか見てみよう．
　今回はLLVM bitcodeを扱う記号的実行ツールKLEEを用いる．
　まず次のコードを解析対象のソースに追記する必要がある．これは，変数xにたいして記号的実行を適用するという意味である．

1
@@ -3,6 +3,7 @@
 int main(int argc, char *argv[])
 {
     int x=argc;
+    klee_make_symbolic(&x, sizeof(x), "x");
     if(x==2)
         printf("triggered!\n");

　次に，LLVM bitcodeを生成する．

1
# clang -emit-llvm -c -g tr.c
tr.c:6:5: warning: implicit declaration of function 'klee_make_symbolic' is
      invalid in C99 [-Wimplicit-function-declaration]
    klee_make_symbolic(&x, sizeof(x), "x");
    ^
1 warning generated.

　警告が出るが，気にしてはいけない．この関数呼び出しがKLEEにトラップされることになるのだ．
　ソースコードのないマルウェアなどを分析するにあたっては，IDAなどのデコンパイラでソースを出力し，型情報やシグナルハンドラなどの記述を整えたのち上記のようなコードを挿入するか，あるいはS2EやPANDAといった動的解析環境を頼ることになるだろう．
　それはさておき，KLEEを動かしてみよう．少し前までKLEEをビルドして動かすのはとても面倒だったが，いまではDocker Imageが提供されている．

1
# sudo docker pull klee/klee
# sudo docker run --rm -ti klee/klee

　線型難読化をおこなう前のtr.cについて記号的実行をおこなった結果を示す．

1
klee@4d625535c122:~$ time klee tr.bc
KLEE: output directory is "/home/klee/klee-out-1"
KLEE: WARNING: undefined reference to function: printf
KLEE: WARNING ONCE: calling external: printf(39707328)
triggered!

KLEE: done: total instructions = 17
KLEE: done: completed paths = 2
KLEE: done: generated tests = 2

real    0m0.032s
user    0m0.009s
sys     0m0.012s

　パスは2つしか存在しないため，32msecで解析が終わっている．
　ならば，線型難読化を施した後のtr2.cについてはどうか．

1
klee@4d625535c122:~$ time klee tr2.bc
KLEE: output directory is "/home/klee/klee-out-2"
KLEE: WARNING: undefined reference to function: printf
KLEE: WARNING ONCE: calling external: printf(49859696)
triggered!
triggered!
triggered!
triggered!
triggered!
...

KLEE: done: total instructions = 285809
KLEE: done: completed paths = 158
KLEE: done: generated tests = 158

real    6m11.933s
user    3m56.240s
sys     2m14.245s

　さきほどに比べ，実行パスは158に増加し，解析に11622.9倍（！）もの時間がかかっている．
　今回の単純なプログラムでさえこのようになるならば，複数の入出力に依存する実行パスに線型難読化が施されたらどうなることか．

コンパイラ最適化

　難読化とはえてしてコンパイラ最適化の逆写像である．
　KLEEがLLVMにもとづいているということもあって，LLVMの最適化が線型難読化を除去できるかどうか興味をもった．検証してみよう．

1
# opt -O3 tr2.bc -o tr3.bc

　-O3をもって最適化した後の制御フローグラフは次のようになる．

　最初のtr.cほどではないが，いくらか単純になっていることがわかる．printf()もputs()に変換されている．
　では，実行パスは減少しているだろうか．記号的実行をおこなった結果は次の通り．

1
klee@4d625535c122:~$ time klee tr3.bc
KLEE: output directory is "/home/klee/klee-out-4"
KLEE: WARNING: undefined reference to function: puts
KLEE: WARNING ONCE: calling external: puts(32090720)
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!

KLEE: done: total instructions = 3383
KLEE: done: completed paths = 10
KLEE: done: generated tests = 10

real    0m2.845s
user    0m2.490s
sys     0m0.357s

　実行パスは10とさきほどのtr2.cよりも減少している．実行時間はtr.cの88.9倍であった．

おわりに

　線型難読化は脅威ではないことがわかった—少なくとも提唱者の思惑ほどには．
　塵も積もれば山となるように，線型難読化を多数の箇所に施せばその効力は増すだろう．しかしそれはクラスタリングなどの手法で対処される可能性を高めるだけである．もちろん，どれほどの範囲で難読化を適用すれば効果的かという閾値を探ることに価値はある．
　LLVMの-O3最適化は複数の最適化パスを組み合わせ，再帰的に適用することによっておこなわれる．どのパスが線型難読化の除去にもっとも寄与しているか調べてみるとおもしろいかもしれない（やる気がない）．

参考文献