2 진 폭탄 - 4 단계

Question

다음과 같은 2 진 폭탄에 대한 어셈블리 코드를 추적하는 데 매우 어려움을 겪고 있습니다. (폭탄을 제거해야하는 학교의 과제 인이 폭탄은 모두 6 개의 단계로 구성되어 있으며 모두 1 개의 올바른 입력을 진행합니다 다음 단계로). 저는 현재 phase_4에 있으며 func4라는 재귀 함수가 있습니다. 나는 입력이 두 개의 정수 인 "% 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 : 나는 phase4는 첫 번째 숫자는 범위에 0 .. 14 포함 (참조 라인 +44 것을 확인하는 것이 분명 희망

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

.. +57) 그런 다음 세 개의 인수 (0 및 14)를 입력하여 func4을 호출합니다 (줄 +62 .. +85). 그 다음에 라인 +90 반환 값은 0x25 (37 진수) 인 것을 확인하고, 입력 된 번호는 제 37 (라인 +95)

가요는 func4로 이동하자있다. 저는 세 가지 인자 인 x, low 및 high을 호출 할 것입니다. 처음에는 그들이 무엇인지 물론 알지 못합니다. 라인 +23 .. +34 계산 (high - low)/2. 추한 혼란은 컴파일러가 0으로 잘라내어 음수를 처리하는 코드를 생성하기 때문입니다. 우리는 어떤 음수도 보지 않을 것입니다. 라인 +36은 단지 더할 나위없이 좋은 결과 일 뿐이므로 ebx에는 low + (high - low)/2이 있습니다. 이는 두 숫자의 평균이라고도합니다. 코드는이 평균을 첫 번째 인수로 제공된 숫자 x과 비교합니다. +43. +62x < average이면 실행되고 그들은 func4(x, low, average - 1)을 호출하고 평균에 반환 된 값을 추가합니다. 마찬가지로, .. +89x > 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보다 작아야합니다. 따라서 세 번째 추측은 27과 합계가 10이되도록 더한 것입니다. 숫자가 10임을 의미합니다.

TL; DR : 올바른 입력 10 및 37