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