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 1
FOR each number in answers after the first
IF number DOES NOT EQUAL previous number + counter
CALL explode_bomb
END IF
INCREMENT counter
END 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.

The maximum two’s-complement value for a given word size, w (Bryant, 65)

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.

Two’s-complement addition. x,y = two’s-complement numbers, w = word size (Bryant, 90)

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.