[解決済み】バイナリーボム - フェーズ4

質問

次のバイナリ爆弾のアセンブリコードをトレースするのに非常に苦労しています（爆弾を解除しなければならない学校の課題で、この爆弾には6つのフェーズがあり、次のフェーズに進むにはすべて1つの正しい入力が必要です）。私は現在フェーズ4におり、func4と呼ばれる再帰的な関数を持っています。入力は "%d %d" で、これは2つの整数であることを確認した。しかし、すべてのステップですべてのレジスタの情報を取得しても、func4が何をしているのかがよくわかりません。

フェーズ_4です。

    (gdb) disas
Dump of assembler code for function phase_4:
=> 0x08048e24 <+0>: sub    $0x2c,%esp
   0x08048e27 <+3>: lea    0x1c(%esp),%eax
   0x08048e2b <+7>: mov    %eax,0xc(%esp)
   0x08048e2f <+11>:    lea    0x18(%esp),%eax
   0x08048e33 <+15>:    mov    %eax,0x8(%esp)
   0x08048e37 <+19>:    movl   $0x804a7f1,0x4(%esp)
   0x08048e3f <+27>:    mov    0x30(%esp),%eax
   0x08048e43 <+31>:    mov    %eax,(%esp)
   0x08048e46 <+34>:    call   0x80488d0 <__isoc99_sscanf@plt>
   0x08048e4b <+39>:    cmp    $0x2,%eax
   0x08048e4e <+42>:    jne    0x8048e5d <phase_4+57>
   0x08048e50 <+44>:    mov    0x18(%esp),%eax
   0x08048e54 <+48>:    test   %eax,%eax
   0x08048e56 <+50>:    js     0x8048e5d <phase_4+57>
   0x08048e58 <+52>:    cmp    $0xe,%eax
   0x08048e5b <+55>:    jle    0x8048e62 <phase_4+62>
   0x08048e5d <+57>:    call   0x8049470 <explode_bomb>
   0x08048e62 <+62>:    movl   $0xe,0x8(%esp)
   0x08048e6a <+70>:    movl   $0x0,0x4(%esp)
   0x08048e72 <+78>:    mov    0x18(%esp),%eax
   0x08048e76 <+82>:    mov    %eax,(%esp)
   0x08048e79 <+85>:    call   0x8048dbb <func4>
   0x08048e7e <+90>:    cmp    $0x25,%eax
   0x08048e81 <+93>:    jne    0x8048e8a <phase_4+102>
   0x08048e83 <+95>:    cmpl   $0x25,0x1c(%esp)
   0x08048e88 <+100>:   je     0x8048e8f <phase_4+107>
   0x08048e8a <+102>:   call   0x8049470 <explode_bomb>
   0x08048e8f <+107>:   add    $0x2c,%esp
   0x08048e92 <+110>:   ret    
    End of assembler dump.

func4:

Breakpoint 2, 0x08048dbb in func4 ()
(gdb) disas
Dump of assembler code for function func4:
=> 0x08048dbb <+0>: sub    $0x1c,%esp
   0x08048dbe <+3>: mov    %ebx,0x14(%esp)
   0x08048dc2 <+7>: mov    %esi,0x18(%esp)
   0x08048dc6 <+11>:    mov    0x20(%esp),%eax
   0x08048dca <+15>:    mov    0x24(%esp),%edx
   0x08048dce <+19>:    mov    0x28(%esp),%esi
   0x08048dd2 <+23>:    mov    %esi,%ecx
   0x08048dd4 <+25>:    sub    %edx,%ecx
   0x08048dd6 <+27>:    mov    %ecx,%ebx
   0x08048dd8 <+29>:    shr    $0x1f,%ebx
   0x08048ddb <+32>:    add    %ebx,%ecx
   0x08048ddd <+34>:    sar    %ecx
   0x08048ddf <+36>:    lea    (%ecx,%edx,1),%ebx
   0x08048de2 <+39>:    cmp    %eax,%ebx
   0x08048de4 <+41>:    jle    0x8048dfd <func4+66>
   0x08048de6 <+43>:    lea    -0x1(%ebx),%ecx
   0x08048de9 <+46>:    mov    %ecx,0x8(%esp)
   0x08048ded <+50>:    mov    %edx,0x4(%esp)
   0x08048df1 <+54>:    mov    %eax,(%esp)
   0x08048df4 <+57>:    call   0x8048dbb <func4>
   0x08048df9 <+62>:    add    %eax,%ebx
   0x08048dfb <+64>:    jmp    0x8048e16 <func4+91>
   0x08048dfd <+66>:    cmp    %eax,%ebx
   0x08048dff <+68>:    jge    0x8048e16 <func4+91>
   0x08048e01 <+70>:    mov    %esi,0x8(%esp)
   0x08048e05 <+74>:    lea    0x1(%ebx),%edx
   0x08048e08 <+77>:    mov    %edx,0x4(%esp)
   0x08048e0c <+81>:    mov    %eax,(%esp)
   0x08048e0f <+84>:    call   0x8048dbb <func4>
   0x08048e14 <+89>:    add    %eax,%ebx
   0x08048e16 <+91>:    mov    %ebx,%eax
   0x08048e18 <+93>:    mov    0x14(%esp),%ebx
   0x08048e1c <+97>:    mov    0x18(%esp),%esi
   0x08048e20 <+101>:   add    $0x1c,%esp
   0x08048e23 <+104>:   ret    
End of assembler dump.

解決方法は？

というのは明らかでしょう。 phase4 は、最初の数字が範囲内にあるかどうかをチェックしています。 0 .. 14 を包含する（行を参照 +44 .. +57 ) そして、次のように起動します。 func4 を、最初に入力された数値の3つの引数で指定します。 0 と 14 (行 +62 .. +85 ). 次に、その戻り値が 0x25 (10進数37)の行で +90 であり、2番目に入力された数字も 37 (行 +95 )

に移ろう。 func4 . ここでは、3つの引数を x , low と high . もちろん最初はそれらが何であるかはわからない。行数 +23 .. +34 計算する (high - low) / 2 . この醜い混乱は、コンパイラが負の数をゼロに切り捨てて処理するコードを生成するためです。しかし、私たちは負の数を見ることはない。行 +36 は単なる派手な足し算なので ebx となります。 low + (high - low) / 2 これは、2つの数値の平均としても知られています。このコードでは、この平均と、次の数値とを比較します。 x は、第一引数として与えられた。行数 +43 .. +62 が実行されると x < average を起動し func4(x, low, average - 1) を作成し、返された値を平均値に加算する。同様に、行 +70 .. +89 が実行されると x > average を計算し average + func4(x, average + 1, high) . もし x == average の場合、平均値そのものが返されます。

基本的には2値探索を行い、その都度推測したものを合計しているのです。区間が15要素であるとすると、最大で4つの推測が必要になります。最初の推測は 7 という結果を得るには 37 が必要です。 30 を増やします。あと最大3回の試行で、すべての推測は7より小さいか大きいかのどちらかになります。 7 * 3 = 21 となり、これでは 30 ということは、7より大きい数字でなければならないということです。 (8 + 14) / 2 = 11 となり、合計が 18 と 19 あと少し もしこの数字が11以上だったら、目標をオーバーシュートしたことになるので、7以上11未満であることが必要です。3つ目の推測はこうだ。 (8 + 10) / 2 = 9 となり、合計で 27 と 10 はあと1回で終わりなので、つまりは数字が 10 .

TL;DR: 正しい入力は次のようになります。 10 と 37