assembly - Bomba Binaria-Fase 4

x86 gdb

Question

Estoy teniendo un momento muy difícil para rastrear el código de ensamblaje para la siguiente bomba binaria (una asignación de la escuela donde se debe desactivar una bomba, esta bomba contiene 6 fases, todas tienen 1 entrada correcta para pasar a la siguiente fase). Actualmente estoy en fase_4 y tiene una función recursiva llamada func4. He identificado que la entrada es "% d% d", que es dos enteros. Sin embargo, no puedo entender qué func4 está haciendo, incluso después de obtener la información en todos los registros a lo largo de cada paso.

Fase_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

Espero que sea obvio que phase4 está comprobando que el primer número está en el rango 0 .. 14 inclusive (ver líneas +44 .. +57 ) Luego invoca func4 con tres argumentos: el primer número ingresado, 0 y 14 (líneas +62 .. +85 ). A continuación, verifica que el valor de retorno sea 0x25 (37 decimal) en la línea +90 y que el segundo número ingresado sea también 37 (línea +95 )

Pasemos a func4 . Llamaré a los tres argumentos x , low y high . Inicialmente no sabes lo que son, por supuesto. Líneas +23 .. +34 calcular (high - low) / 2 . El feo lío se debe a que el compilador genera código para manejar números negativos con truncamiento a cero. Sin embargo, no veremos ningún número negativo. La línea +36 es simplemente una adición elegante, así que en ebx ahora tenemos low + (high - low) / 2 que también se conoce como el promedio de los dos números. El código luego compara este promedio con el número x que se ha proporcionado como primer argumento. Las líneas +43 .. +62 se ejecutan si x < average e invocan func4(x, low, average - 1) y agregan el valor devuelto al promedio. De forma similar, las líneas +70 .. +89 se ejecutan si x > average y calcula el average + func4(x, average + 1, high) . Si x == average , solo se devuelve el promedio.

Básicamente está haciendo una búsqueda binaria y sumando las suposiciones a medida que avanzan. Dado que el intervalo tiene 15 elementos, necesitará como máximo 4 suposiciones. La primera conjetura va a ser 7 , por lo que para obtener el resultado requerido de 37 necesitamos 30 más. Tenemos como máximo 3 intentos más y todas las suposiciones serán menos de 7 o más de 7. Dado que 7 * 3 = 21 y que no pueden darnos 30 significa que el número debe ser mayor que 7. Segundo intento es así va a ser (8 + 14) / 2 = 11 , por lo que nuestra suma 18 con 19 más por recorrer. Si el número era superior a 11 significaría que rebasamos el objetivo, por lo que el número debe ser mayor que 7 y menor que 11. El tercer intento es por lo tanto (8 + 10) / 2 = 9 que eleva la suma a 27 con 10 más para ve y solo una adivinanza, entonces eso significa que el número es 10 .

TL; DR: la entrada correcta debe ser 10 y 37