Solving Bomb Lab Phase 2

A kind-of-clever, show-offy solution

There are already many walkthroughs for CMU’s famous/infamous Bomb Lab on the web, but I’m going to share my solution to Phase 2 because I haven’t seen others that played with positive overflow. When it was time to turn in the assignment, I solved the phase with one positive and six negative numbers.

The assembly code

Phase 2 is all about how comparison and jump instructions create loops in Assembly.

`Dump of assembler code for function phase_2:   0x0000000000400fb9 <+0>: push   %rbp   0x0000000000400fba <+1>: mov    %rsp,%rbp   0x0000000000400fbd <+4>: push   %r12   0x0000000000400fbf <+6>: push   %rbx   0x0000000000400fc0 <+7>: sub    \$0x20,%rsp   0x0000000000400fc4 <+11>: lea    -0x30(%rbp),%rsi   0x0000000000400fc8 <+15>: callq  0x4016eb <read_six_numbers>   0x0000000000400fcd <+20>: cmpl   \$0x0,-0x30(%rbp)   0x0000000000400fd1 <+24>: jns    0x400ffa <phase_2+65>   0x0000000000400fd3 <+26>: callq  0x4016b5 <explode_bomb>   0x0000000000400fd8 <+31>: jmp    0x400ffa <phase_2+65>   0x0000000000400fda <+33>: mov    %ebx,%eax   0x0000000000400fdc <+35>: add    -0x4(%r12),%eax   0x0000000000400fe1 <+40>: cmp    %eax,(%r12)   0x0000000000400fe5 <+44>: je     0x400fec <phase_2+51>   0x0000000000400fe7 <+46>: callq  0x4016b5 <explode_bomb>   0x0000000000400fec <+51>: add    \$0x1,%ebx   0x0000000000400fef <+54>: add    \$0x4,%r12   0x0000000000400ff3 <+58>: cmp    \$0x6,%ebx   0x0000000000400ff6 <+61>: jne    0x400fda <phase_2+33>   0x0000000000400ff8 <+63>: jmp    0x401005 <phase_2+76>   0x0000000000400ffa <+65>: lea    -0x2c(%rbp),%r12   0x0000000000400ffe <+69>: mov    \$0x1,%ebx   0x0000000000401003 <+74>: jmp    0x400fda <phase_2+33>   0x0000000000401005 <+76>: add    \$0x20,%rsp   0x0000000000401009 <+80>: pop    %rbx   0x000000000040100a <+81>: pop    %r12   0x000000000040100c <+83>: pop    %rbp   0x000000000040100d <+84>: retq   End of assembler dump.`

This phase takes six numbers and runs a test on five of them in a loop. From this assembler code, there are four important points to remember in order to pull of this trick with negative integers:

#1: This phase checks if each number after the first is equal to the previous number plus the current iteration. In pseudocode, the procedure is:

`SET counter to 1FOR each number in answers after the first    IF number DOES NOT EQUAL previous number + counter        CALL explode_bomb    END IF    INCREMENT counterEND FOR`

#2: Only the first number has to be nonnegative. Instructions from `0x400fcd` to `0x400fd3` will call `explode_bomb` if the first number is less than zero. Since the loop body runs from `0x400fda` to `0x401ff8`, the function never again checks if user input is nonnegative.

#3: The compared values are integers. The instruction at `0x400fe1` compares `%eax`, which stores up to 32-bit values, and not one of the media registers. So the input values should be type `int`.

#4: The compared integers are represented in two’s complement. While some jump instructions indicate whether values are signed or unsigned, this procedure does not use them. To figure out the range of acceptable values, it is necessary to inspect the assembler code for `read_six_numbers.`

`Dump of assembler code for function read_six_numbers: 0x00000000004016eb <+0>: push %rbp 0x00000000004016ec <+1>: mov %rsp,%rbp 0x00000000004016ef <+4>: sub \$0x10,%rsp 0x00000000004016f3 <+8>: mov %rsi,%rdx 0x00000000004016f6 <+11>: lea 0x4(%rsi),%rcx 0x00000000004016fa <+15>: lea 0x14(%rsi),%rax 0x00000000004016fe <+19>: mov %rax,0x8(%rsp) 0x0000000000401703 <+24>: lea 0x10(%rsi),%rax 0x0000000000401707 <+28>: mov %rax,(%rsp) 0x000000000040170b <+32>: lea 0xc(%rsi),%r9 0x000000000040170f <+36>: lea 0x8(%rsi),%r8 0x0000000000401713 <+40>: mov \$0x402a41,%esi 0x0000000000401718 <+45>: mov \$0x0,%eax 0x000000000040171d <+50>: callq 0x400cb0 <__isoc99_sscanf@plt> 0x0000000000401722 <+55>: cmp \$0x5,%eax 0x0000000000401725 <+58>: jg 0x40172c <read_six_numbers+65> 0x0000000000401727 <+60>: callq 0x4016b5 <explode_bomb> 0x000000000040172c <+65>: leaveq  0x000000000040172d <+66>: nopl (%rax) 0x0000000000401730 <+69>: retq End of assembler dump.`

This function is calls `sscanf`, which parses user input based on the format passed to it from a character string. The address of this format string is passed to `sscanf` through `%esi`. An inspection of address `0x402a41` reveals the string is `"%d %d %d %d %d %d”`. This conversion specifier reads an optionally signed decimal integer (see `man sscanf`)

Using positive overflow

Let A = (m, n, o, p, q, r), representing the six values input by the user. Since input values can be represented in two’s complement, must be “greater” than the previous one, and the first one has to be nonnegative, m can be set to the largest value a 32-bit word can represent in two’s complement, a.k.a TMax.

Hence, m = 2³¹–1 = 2,147,483,647.

This phase will expect n = m + 1, o = n+ 2, … , r = q + 5. We can assume that the phase will compute these values following this principle for two’s-complement addition.

Following this principle, n, turns out to be TMin, the minimum value representable with two’s complement for this word size. The following values — o, p, q, and r —follow familiar rules of addition.

m = 2,147,483,647
n = m + 1 – 2³² = -2,147,483,648
o = n + 2 = -2,147,483,646
p = o + 3 = -2,147,483,643
q = p + 4 = -2,147,483,639
r = q + 5 = -2,147,483,634

Therefore, this was my final answer:

`2147483647 -2147483648 -2147483646 -2147483643 -2147483639 -2147483634`

Citations

Bryant, Randal E., and David R. O’Hallaron. Computer Systems: A Programmer’s Perspective. Boston: Pearson, 2016. Print.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.