バイナリ爆弾 - フェーズ4

Question

次のバイナリ爆弾のアセンブリコードをトレースするのが非常に困難です（爆弾を爆発させなければならない学校からの譲渡で、この爆弾には6つのフェーズがすべて含まれています。次の段階へ）。私は現在phase_4にあり、func4という再帰関数を持っています。私は入力が2つの整数である "％d％d"であることを確認しました。しかし、私はfunc4が何をしているのか、それぞれのステップですべてのレジスタに関する情報を得た後でも分かりません。

Phase_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. 

Answer 1

私はそれがphase4は最初の数が範囲0であることを確認していることは明らかです願っています。.. 14込み（ライン+44 .. +57を見ます） 次に、3つの引数を持つfunc4を呼び出します。最初に入力した数字は0と14です（行番号+62 .. +85）。次はライン+90に戻り値が0x25（37進）であることをチェックし、入力された第二の数も37（ライン+95）

であるのは、func4に移動しましょうということ。 3つの引数をx,low、highとします。当初、彼らはもちろん彼らが何であるか分からない。ライン+23 .. +34計算(high - low)/2。醜い混乱は、コンパイラが負の数を切り捨てて0にするコードを生成するためです。私たちは負の数字は見ません。線+36はちょっとファンシーなので、にはlow + (high - low)/2があります。これは2つの数値の平均としても知られています。コードは、この平均と最初の引数として提供された番号xを比較します。 +43 .. +62x < averageの場合に実行され、func4(x, low, average - 1)が呼び出され、平均値に戻り値が追加されます。同様に、行+70 .. +89はx > averageの場合に実行され、average + func4(x, average + 1, high)を計算します。 x == averageの場合、平均値だけが返されます。

基本的にはバイナリ検索を行い、推測をまとめています。インターバルに15の要素があるとすれば、最大4つの推測が必要です。最初の推測は7になるので、37の必要な結果を得るには30が必要です。私たちは最大でも3回試してみると、7または7以上のすべての推測が行われます。7 * 3 = 21以降、それは30を与えることはできません。その数は7以上でなければならないことを意味します。 (8 + 14)/2 = 11、合計18を19とすることがさらに重要です。数字が11を超えた場合、目標をオーバーシュートする可能性があるので、数字は7以上で11未満でなければなりません。したがって、3番目の推測はで、合計はになります。10となります。つまり、数字は10です。

TL; DR：正しい入力は、私はまた、intは0より大きくなければならないが、それ以外の私は迷ってしまいましたことを識別することができた10と37