Special instruction challenge チュートリアル

(特殊命令の解析)

■ 乱数を取得してみる

次に乱数命令を実行して,乱数を取得してみましょう.
乱数取得の命令は,random_value() で利用されています.

まず Blackfin での,random_value() の呼び出されかたを見てみます.
Blackfin の逆アセンブル結果を見ると,random_get_value()という関数から 以下のようにして呼び出されています.

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>;
    15ba:       66 6c           SP += 0xc;              /* ( 12) */
    15bc:       27 01           RETS = [SP++];
    15be:       10 00           RTS;
レジスタR0にゼロを設定してから CALL 命令で random_value() を 呼び出しています.
また呼び出し時には,レジスタR0にゼロを設定して呼び出すようです.

さらに動的解析で,乱数取得の命令の出力を見てみましょう.

乱数取得のための乱数命令は,random_value()という関数内の 0x1578 というアドレスにある「0e c6 00 00」という命令だということが すでにわかっています.

これを,強制的に実行してみます.
まず最初からやりなおすためにGDBを一旦終了し,再接続します.

(gdb) quit
$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote 127.0.0.1:10000
Remote debugging using 127.0.0.1:10000
0x00001400 in start ()
(gdb) 
乱数取得用の乱数命令にブレークポイントを設定して実行開始します.
乱数取得は乱数命令の初期化後に呼び出されているので, random_XXX_default()による初期化処理も実行されるはずです.
(gdb) break *0x1578
Breakpoint 1 at 0x1578
(gdb) continue
Continuing.

Breakpoint 1, 0x00001578 in random_value ()
(gdb) layout asm
いったんブレークポイントを解除します.
これをやっておかないと,ステップ実行直後にまたブレークしたりして, どこまで実行されたかよくわからないことになります.
(gdb) disable
レジスタR0はゼロに設定されて呼び出されるようですので, (すでになっているはずですが)いちおうゼロ設定します.
(gdb) print $r0 = 0
$1 = 0
ステップ実行で乱数取得命令を実行し,レジスタの状態を見てみます.
(gdb) stepi
0x0000157c in random_value ()
(gdb) info registers
r0             0x41c67ea6       1103527590
r1             0x1800   6144
r2             0x24     36
r3             0x0      0
...
乱数はなんらかのレジスタに格納されて返されるのだと思われますが, どのレジスタに格納されているのでしょうか.
レジスタの値を見る限り,レジスタR0が乱数っぽいです.
また random_value() は乱数命令の実行後はRTS命令でそのまま戻る ようになっています.
ということは戻り値を返すレジスタR0に乱数が格納されてくれないと, 関数の戻り値として正常に返すことができません.
ということでおそらくレジスタR0に乱数が格納されているのでしょう.

Blackfinは第1引数も戻り値もレジスタR0で渡すことがわかっています.
この乱数命令はレジスタR0から引数(必ずゼロですが)を受け取り, さらにレジスタR0で乱数を返しています.
なので,関数内で乱数命令をただ呼び出せば,自然と関数の第1引数が引数として与えられ, 乱数が戻り値として返されるようになっているわけです.

つまりrandom_value()は,C言語では以下のように書くことができるわけです. (server.zip の server/exec-sim/rnd-bfin-elf.c 参照)
非常にシンプルですね.

unsigned int random_value(unsigned int value)
{
  asm volatile (".short 0xc60e");
  asm volatile (".short 0x0000");
  return value;
}

乱数命令を繰り返し実行し,乱数系列を取得してみましょう.
プログラムカウンタを強制書き換えすることで,実行位置を強制指定して 繰り返し実行します.
※ サーバのリミットが競技時の状態のままの場合,(とくにレジスタへの 代入が多い場合には)うまく実行できないかもしれません. うまくいかない場合には,サーバのリミットを解除して試してください. 実際の競技時は,そうしたリミットをうまく回避しつつ操作することが求められます

(gdb) print $pc = 0x1578
$2 = (void (*)()) 0x1578 <random_value+8>
(gdb) print $r0 = 0
$3 = 0
(gdb) stepi
0x0000157c in random_value ()
(gdb) print/x $r0
$4 = 0x967eb0e7
(gdb) print $pc = 0x1578
$5 = (void (*)()) 0x1578 <random_value+8>
(gdb) print $r0 = 0
$6 = 0
(gdb) stepi
0x0000157c in random_value ()
(gdb) print/x $r0
$7 = 0x2781e494
(gdb) print $pc = 0x1578
$8 = (void (*)()) 0x1578 <random_value+8>
(gdb) print $r0 = 0
$9 = 0
(gdb) stepi
0x0000157c in random_value ()
(gdb) print/x $r0
$10 = 0xc46b9b3d
(gdb)
このようにして得られた乱数系列は,以下です.
0x41c67ea6
0x967eb0e7
0x2781e494
0xc46b9b3d
0xf94bdf32
0x95fb7483
0xd9e2b600
0x9cfbae39

■ 乱数命令の仕様を推定する

パラメータやシードを様々に変えて乱数取得してみることで, 乱数命令の仕様を推定してみましょう.

まずパラメータ0をデフォルト値に設定している random_set_param0_default()の逆アセンブル結果を見てみましょう.

00001580 <_random_set_param0_default>:
    1580:       67 01           [--SP] = RETS;
    1582:       a6 6f           SP += -0xc;             /* (-12) */
    1584:       00 60           R0 = 0x0 (X);           /*              R0=0x0( 0) */
    1586:       ff e3 dd ff     CALL 0x1540 <_random_param0>;
    158a:       66 6c           SP += 0xc;              /* ( 12) */
    158c:       27 01           RETS = [SP++];
    158e:       10 00           RTS;
レジスタR0にゼロを設定し,random_param0()を呼んでいます.
random_param0()では,パラメータ0を設定する特殊命令を呼び出すだけです.
ということはこの特殊命令はレジスタR0でパラメータ0を受け取るが, レジスタR0がゼロになっているときはデフォルト値が使われる, という仕様のようです.

実はパラメータ1とシードも同様になっています.

パラメータ0に1,パラメータ1に1,シードに1を指定して, 乱数取得をしてみましょう.
gdbを一旦終了し,以下のように最初からやりなおしてみます.

$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ0の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ1の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
(gdb) print $pc = 0x1578
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
(gdb) print $pc = 0x1578
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
...
このようにすると,以下のような乱数系列が得られます. (全然乱数になっていませんが)
2, 3, 4, 5, ...
パラメータ0を1,パラメータ1を2,シードを1にすると以下のようになります.
3, 5, 7, 9, ...
等差数列になっていますね.
差分は2です.パラメータ1がそのまま差分になっているようです.

パラメータ0を2,パラメータ1を1,シードを1にすると以下のようになります.

3, 7, 15, 31, ...

パラメータ1が加算されることを考えると,前の数を2倍してパラメータ1が 加算されている,と考えるとつじつまが合います.
パラメータ0の値が2ですから,パラメータ0をかけ算して,パラメータ1を 加算しているのでしょうか.

その他にも,パラメータやシードをいろいろ変更して試してみてください.
これらを考えると,どうやら以下のような計算式で乱数が得られているようです.

value = value * param0 + param1;
ここまででわかった特殊命令の仕様を,まとめてみましょう.
(実際の実装内容は微妙に異なるのですが,以下のような動作がおおまかに推定され, これらがわかれば攻略できます)

特殊命令 機械語コードやること(推定)
パラメータ0の設定0e c6 00 80 param0 = r0 ? r0 : default_param0;
パラメータ1の設定0e c6 00 c0 param1 = r0 ? r0 : default_param1;
シードの設定 0e c6 00 40 value = r0 ? r0 : default_seed;
乱数の取得 0e c6 00 00 value = value * param0 + param1; r0 = value;

■ パラメータやシードのデフォルト値の推定

ここまでわかれば,パラメータやシードのデフォルト値も推定できます.
乱数の計算式は,以下のようになっています.

value = value * param0 + param1;
まずパラメータ0を1,シードを1,パラメータ1はデフォルト値指定として 乱数を取得してみましょう.
(パラメータ0とシードにゼロを設定したいところですが, ゼロを指定するとデフォルト値が使われてしまうため,1を指定します)

パラメータやシードにデフォルト値を使うためには,レジスタR0にゼロを 設定して特殊命令を呼び出します.やってみましょう.

$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ0の設定)
(gdb) print $r0 = 1       (1を指定)
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ1の設定)
(gdb) print $r0 = 0       (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 1       (1を指定)
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
$9 = 0x303a
このようにして得られた値は 0x303a です.10進数だと 12346 です.
パラメータ0とシードに1を指定しているので,以下のような計算が行われていると 推測できます.
パラメータ1のデフォルト値は 12345 のようです.
1 * 1 + 12345 → 12346
次にパラメータ0のデフォルト値を推定してみましょう.
パラメータ0をデフォルト値指定,パラメータ1を1,シードを1として 乱数を取得します.
$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ0の設定)
(gdb) print $r0 = 0       (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ1の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
$9 = 0x41c64e6e
得られた値は 0x41c64e6e で,10進数だと1103515246です.
ということはパラメータ0のデフォルト値は1103515245で, 以下のような計算が行われているのでしょう.
1 * 1103515245 + 1 → 1103515246
最後にシードのデフォルト値の推定です.
パラメータ0とパラメータ1に1を指定して, シードはデフォルト値として乱数取得してみます.
$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ0の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ1の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 0       (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
$9 = 0x2
得られた値は2です.
ということはシードのデフォルト値は1で, 以下のような計算が行われているのでしょう.
1 * 1 + 1 → 2

デフォルト値がわかったのでその部分を追加してまとめると, 以下のようになります.

特殊命令 機械語コードやること(推定)
パラメータ0の設定0e c6 00 80 param0 = r0 ? r0 : 1103515245;
パラメータ1の設定0e c6 00 c0 param1 = r0 ? r0 : 12345;
シードの設定 0e c6 00 40 value = r0 ? r0 : 1;
乱数の取得 0e c6 00 00 value = value * param0 + param1; r0 = value;

■ おしまい