Special instruction challenge チュートリアル

Special instruction challenge チュートリアル
(静的解析してみる)

■ 各種アーキテクチャの実行ファイルの実行確認

では，いよいよ本格的に解いてみましょう．

まずはダウンロードした各種アーキテクチャの実行ファイルを実行してみましょう．
これらは競技のインフォメーションページによれば，キーワードをデコードするプログラムのようです．
実際にデコードできるでしょうか．

以下のようにして，GDB付属のエミュレータを用いて実行してみてください．
(多種アーキテクチャの開発環境が，/usr/local/cross-gcc494 にインストールされているとして説明します)
※ BlackfinとMIPS64は，実行時にオプションが必要なことに注意してください．

(Blackfin) (システムコール実行のため，userモード指定で実行)

$ /usr/local/cross-gcc494/bin/bfin-elf-run --environment user bfin-elf.x
program stopped with signal 4 (Illegal instruction).

(MSP430)

$ /usr/local/cross-gcc494/bin/msp430-elf-run msp430-elf.x
Fault: PC(0x1) is less than 0x10

(MN10300)

$ /usr/local/cross-gcc494/bin/mn10300-elf-run mn10300-elf.x
program stopped with signal 4 (Illegal instruction).

(V850)

$ /usr/local/cross-gcc494/bin/v850-elf-run v850-elf.x
Illegal instruction at address 0x17f0
program stopped with signal 4 (Illegal instruction).

(MIPS64) (0x100000付近のメモリがマップされていないので，マッピングして実行)

$ /usr/local/cross-gcc494/bin/mips-elf-run mips64-elf.x
mips-core: 4 byte read to unmapped address 0x100000 at 0x100000
program stopped with signal 10 (Bus error).

$ /usr/local/cross-gcc494/bin/mips-elf-run --memory-region 0x100000,0x10000 mips64-elf.x
ReservedInstruction at PC = 0x00100388
program stopped with signal 4 (Illegal instruction).

不正命令で実行中断しています．

実行ファイルは独自の特殊命令を利用しています．
しかしここで実行のために利用しているのは，オリジナルのGDBに付属している各種アーキテクチャのエミュレータです．
当然ながらそのような特殊命令にエミュレータが対応していないので，不正命令となります．

■ デバッガで実行してみる

デバッガ(GDB)を利用して実行してみましょう．
まずは Blackfin でやってみます．Blackfinの実行ファイルを指定して， Blackfin用にビルドされたGDBを起動します．

$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
GNU gdb (GDB) 7.12.1
...
(gdb)

以下のようにすると，デバッガであるGDBに内蔵されたエミュレータ上でプログラムが実行開始され，デバッグできます．
エミュレータでの実行時に指定するオプションがあれば， target sim コマンドの引数として指定します．
(この場合は bfin-elf-run での実行時に指定した「--environment user」を指定しています)

(gdb) target sim --environment user
Connected to the simulator.
(gdb) load
Loading section .text, size 0x230 lma 0x1400
Loading section .rodata, size 0x18 lma 0x1630
Loading section .data, size 0x28 lma 0x1800
Start address 0x1400
Transfer rate: 4992 bits in <1 sec.
(gdb) run
Starting program: /home/hiroaki/seccon/bfin-elf.x

Program received signal SIGILL, Illegal instruction.
0x00001548 in random_param0 ()
(gdb)

random_param0()という関数内の，アドレス0x00001548という位置で不正命令実行で停止していることがわかります．

以下のようにして，停止位置のアセンブラを表示してみます．

(gdb) layout asm

layout asm を実行すると，以下のように表示されます．
(カーソルキーの上を押すことで，上にスクロールできます)

    0x1540 <random_param0>          NOP;
    0x1542 <random_param0+2>        NOP;
    0x1544 <random_param0+4>        NOP;
    0x1546 <random_param0+6>        NOP;
  > 0x1548 <random_param0+8>        ILLEGAL;
    0x154a <random_param0+10>       R0 = [P0 ++ P0];
    0x154c <random_param0+12>       RTS;

不正命令実行で停止した0x00001548というアドレスを見てみると，ILLEGALとあります．
特殊命令が解釈できずにILLEGALと表示されているようです．つまり不正命令扱いです．
random_param0()という関数内にあるので，乱数関係の特殊命令でしょうか．

ステップ実行で特殊命令を実行してみましょう．

(gdb) stepi

Program received signal SIGILL, Illegal instruction.
0x00001548 in random_param0 ()
(gdb)

やはり実行できないようです．
特殊命令に対応していない，オリジナルのGDBを利用しているので，当然のことです．

■ 静的解析してみる

以下のようにして実行ファイルを逆アセンブルできます．

$ /usr/local/cross-gcc494/bin/bfin-elf-objdump -d bfin-elf.x

まずはプログラムの全体像を見てみましょう．main()関数を探してみます．

000015ec <_main>:
    15ec:       67 01           [--SP] = RETS;
    15ee:       26 6e           SP += -0x3c;            /* (-60) */
    15f0:       06 6f           SP += -0x20;            /* (-32) */
    15f2:       ff e3 c7 ff     CALL 0x1580 <_random_set_param0_default>;
    15f6:       ff e3 cd ff     CALL 0x1590 <_random_set_param1_default>;
    15fa:       ff e3 d3 ff     CALL 0x15a0 <_random_set_seed_default>;
    15fe:       46 30           R0 = SP;
    1600:       60 64           R0 += 0xc;              /* ( 12) */
    1602:       41 e1 00 00     R1.H = 0x0;             /* (  0)        R1=0x1644(5700) */
    1606:       01 e1 00 18     R1.L = 0x1800;          /* (6144)       R1=0x1800 <_key>(6144) */
    160a:       22 61           R2 = 0x24 (X);          /*              R2=0x24( 36) */
    160c:       ff e3 da ff     CALL 0x15c0 <_decrypt>;
    1610:       08 60           R0 = 0x1 (X);           /*              R0=0x1(  1) */
    1612:       4e 30           R1 = SP;
    1614:       61 64           R1 += 0xc;              /* ( 12) */
    1616:       22 61           R2 = 0x24 (X);          /*              R2=0x24( 36) */
    1618:       ff e3 34 ff     CALL 0x1480 <_nputs>;
    161c:       08 60           R0 = 0x1 (X);           /*              R0=0x1(  1) */
    161e:       41 e1 00 00     R1.H = 0x0;             /* (  0)        R1=0x1800 <_key>(6144) */
    1622:       01 e1 44 16     R1.L = 0x1644;          /* (5700)       R1=0x1644(5700) */
    1626:       ff e3 35 ff     CALL 0x1490 <_puts>;
    162a:       00 60           R0 = 0x0 (X);           /*              R0=0x0(  0) */
    162c:       ff e3 00 ff     CALL 0x142c <_exit>;

Blackfinのアセンブリは初見かもしれませんが，あまり深く読む必要はありません．
こういうときは関数呼び出しだけにしぼって見るといいでしょう．
見たところ関数呼び出しには，CALLという命令が用いられているようです．
そこだけ抜き出してみると，以下のように見えてきます．

000015ec <_main>:
    ...
    15f2:       ff e3 c7 ff     CALL 0x1580 <_random_set_param0_default>;
    15f6:       ff e3 cd ff     CALL 0x1590 <_random_set_param1_default>;
    15fa:       ff e3 d3 ff     CALL 0x15a0 <_random_set_seed_default>;
    ...
    160c:       ff e3 da ff     CALL 0x15c0 <_decrypt>;
    ...
    1618:       ff e3 34 ff     CALL 0x1480 <_nputs>;
    ...
    1626:       ff e3 35 ff     CALL 0x1490 <_puts>;
    ...
    162c:       ff e3 00 ff     CALL 0x142c <_exit>;

先頭付近でrandom_XXX_default()という関数を呼んでいます．ということはこれが乱数の初期化処理でしょうか．デフォルト値で初期化しているようです．
次にdecrypt()という関数が呼ばれています．これはキーワードのデコード処理でしょう．
そして nputs() や puts() というのが呼ばれています．デコードしたキーワードを表示しているように思えます．
最後は exit() で終了です．

要するに，単に乱数命令を呼び出すための初期設定をして，キーワードのデコードをして，表示をして終了，というだけのプログラムのようです．

次に，特殊命令に注目して見てみましょう．

特殊命令があるのはrandom_param0()という関数内の，アドレス0x00001548という位置だということがわかっています．
見てみると，以下のようになっています．

00001540 <_random_param0>:
        ...
    1548:       0e c6           ILLEGAL;
    154a:       00 80           R0 = [P0 ++ P0];
    154c:       10 00           RTS;
        ...

ILLEGALとなっているのは２バイトの命令ですが，その後にもよくわからない命令があります．
そしてRTS(おそらくリターン命令)となっています．
なのでILLEGALの２バイトと，さらに後続の２バイトも含んだ４バイトが，今回問題となっている特殊命令のようです．
(ただ逆アセンブラがやはり特殊命令に対応していないので，２バイトの不正命令と，後続の２バイト命令として逆アセンブルされています)

つまり「0e c6 00 80」という機械語コードが，特殊命令のようです．

同様にして ILLEGAL となっている箇所を探すと，以下の４つがあります．

00001540 <_random_param0>:
        ...
    1548:       0e c6           ILLEGAL;
    154a:       00 80           R0 = [P0 ++ P0];
    154c:       10 00           RTS;
        ...

00001550 <_random_param1>:
        ...
    1558:       0e c6           ILLEGAL;
    155a:       00 c0 10 00     A1 = R2.L * R0.L, A0 = R2.L * R0.L;
        ...

00001560 <_random_seed>:
        ...
    1568:       0e c6           ILLEGAL;
    156a:       00 40           R0 >>>= R0;
    156c:       10 00           RTS;
        ...

00001570 <_random_value>:
        ...
    1578:       0e c6           ILLEGAL;
    157a:       00 00           NOP;
    157c:       10 00           RTS;
        ...

random_param1()は後続が４バイト命令と解釈されてしまって， RTS(機械語コードは「10 00」)とくっついてしまっている点に注意してください．

また逆アセンブル結果から関数の呼び出し元を探すと，以下のような部分があります．
random_param0()/random_param1()/random_seed()はそれぞれ random_XXX_default() という関数を経由してmain()の先頭付近から呼ばれています．

000015ec <_main>:
    15ec:       67 01           [--SP] = RETS;
    15ee:       26 6e           SP += -0x3c;            /* (-60) */
    15f0:       06 6f           SP += -0x20;            /* (-32) */
    15f2:       ff e3 c7 ff     CALL 0x1580 <_random_set_param0_default>;
    15f6:       ff e3 cd ff     CALL 0x1590 <_random_set_param1_default>;
    15fa:       ff e3 d3 ff     CALL 0x15a0 <_random_set_seed_default>;
    ...

ということはこれらは乱数命令を使うための初期化処理でしょう．
名前から察するに，パラメータ０と１の設定と，乱数の種(シード)の設定でしょうか．

またrandom_value()は，random_get_value()を経由してdecrypt()という関数から呼び出されています．

000015b0 <_random_get_value>:
    15b0:       67 01           [--SP] = RETS;
    15b2:       a6 6f           SP += -0xc;             /* (-12) */
    15b4:       00 60           R0 = 0x0 (X);           /*              R0=0x0(  0) */
    15b6:       ff e3 dd ff     CALL 0x1570 <_random_value>;
    ...

000015c0 <_decrypt>:
    ...
    15d2:       6f 98           R7 = B[P5++] (X);
    15d4:       ff e3 ee ff     CALL 0x15b0 <_random_get_value>;
    15d8:       f8 59           R7 = R0 ^ R7;
    15da:       27 9a           B[P4++] = R7;
    ...

decrypt()は名前から察するに，おそらく乱数によるデコード処理でしょう．
ということは random_value() にあるのは，乱数を取得する命令だと想像できます．
どうも乱数命令によって取得された乱数を元データにxorでかけあわせることで，キーワードをデコードしているようです．

これらを考慮して４つの関数とそこで使われている特殊命令をまとめると，以下のようになります．
設定可能なパラメータを２つ持つ乱数アルゴリズムのようです．

関数名特殊命令のアドレス特殊命令の機械語コード関数名や呼び出しもとから推測される，特殊命令の意味

random_param0() 1548 0e c6 00 80 乱数のパラメータ０の設定

random_param1() 1558 0e c6 00 c0 乱数のパラメータ１の設定

random_seed() 1568 0e c6 00 40 乱数のシードの設定

random_value() 1578 0e c6 00 00 乱数の取得

関数名	特殊命令のアドレス	特殊命令の機械語コード	関数名や呼び出しもとから推測される，特殊命令の意味
random_param0()	1548	0e c6 00 80	乱数のパラメータ０の設定
random_param1()	1558	0e c6 00 c0	乱数のパラメータ１の設定
random_seed()	1568	0e c6 00 40	乱数のシードの設定
random_value()	1578	0e c6 00 00	乱数の取得