Assignment #3: Bomb Lab (due on Thu, Oct 3, 2024 by 11:59pm)

Introduction

This assignment gives you a binary program containing “bombs” which trigger a ping to our server (and make you lose points) if their inputs are wrong. Your goal is to set breakpoints and step through the binary code using gdb to figure out the program inputs that defuse the bombs (and make you gain points).

The binary program consists of 8 phases. Each phase expects you to type a particular string on stdin:

  • You start a phase by passing its number to the bomb program; for example, ./bomb 1 starts phase 1.
  • If you type the correct string, then the phase is defused, our server is notified, and the solution is written to a text file (for example, sol1.txt for phase 1).
  • Otherwise, the bomb explodes by printing “BOOM!!!” and notifies our server.

Although phases get progressively harder to defuse, the expertise you gain as you move from phase to phase should offset this difficulty. However, the last phase will challenge even the best students, so please don’t wait until the last minute to start.

To avoid accidentally detonating the bomb, you will need to learn how to single-step through the assembly code and how to set breakpoints. You will also need to learn how to inspect both registers and memory. One of the nice side-effects of doing the lab is that you will get very good at using a debugger. This is a crucial skill that will pay big dividends for the rest of your career.

Logistics

This is an individual project. All handins are electronic. Clarifications and corrections will be posted on the course Piazza page.

Remember that:

  • You are not allowed to search for help online!
  • You are not allowed to ask other students for help, show them your solution, or discuss its specifics.
  • Reconsideration requests must be made within one week of our release of grades for the assignment.

Be aware that you may be asked to explain your solution to a member of our course staff.

Handout Instructions

Similarly to the previous assignment, we will create a private GitHub repository for this assignment and share it with you. Be sure to clone the GitHub repository inside the programming server.

Defusing the Bomb

You must complete the assignment using the programming server. The bomb program will connect to our server when it explodes or when a phase is defused.

The best way to defuse your bomb is to use gdb to step through its disassembled binary.

You can start the debugger with:

$ gdb bomb
GNU gdb (Debian 10.1-1.7)

(gdb) layout asm

Then, you can move between the two parts of the screen by pressing CTRL+x and then o. Notice that:

  • When the focus is on the upper half of the screen, the UP/DOWN keys scroll through the disassembled code.
  • When the focus in on the lower half of the screen, the same keys move through the history of previous commands.

You can set a breakpoint using the b command:

(gdb) b phase1
Breakpoint 1 at 0x400f1f
(gdb)

Make sure to set breakpoints on the routine that causes a bomb explosion. (It’s up to you to guess its name in the assembly code.) You can start running the bomb program inside gdb with the command run 1 (for phase 1); to step through its instructions use ni or si (pressing ENTER repeats the previous command).

When the program reads input from the console, you can type the solution (which you should figure out by inspecting the assembly code and memory/registers). We suggest you to follow the execution of the program on your solution by entering ni multiple times (or pressing ENTER). Phases return 0 in %eax if the input string is correct, and 1 if the input is wrong.

If you enter the correct solution to a phase, the bomb program will save it in a text file named sol1.txt for phase 1, sol2.txt for phase 2, and so on. You must commit these files and push them to your repository:

$ git add sol1.txt
$ git commit -m "Solved phase 1"
$ git push

You can solve multiple phases and commit/push these text files together, at the end. The push time of your solution files will be used to count late days.

IMPORTANT: The solution files will be used to compute your score, which will be different from the output of ./grade if you cheated by modifying register values with gdb (instead of just printing them) or by sending counterfeit messages to our server. We are asking you to find the correct inputs!

Evaluation

When the bomb explodes, it notifies our server and you lose points in the final score. Nonetheless, you will always gain points for completing a phase regardless of how many times the bomb has exploded.

These are the precise rules:

  • There are a total of 34 points (1, 1, 3, 5, 5, 5, 7, 7 points for phases 1-8, respectively).
  • There are 2 free explosions (no points lost) for each phase.
  • Each additional explosion costs you 0.5 points.
  • These penalty points are not removed from your score until you complete the phase! When you complete the phase, you receive the maximum between 0.5 * phase_points and phase_points - penalty_points.

This means that:

  • Losing points on the next phase does not affect your current score.
  • When you complete the next phase, you always get at least 50% of the points.
  • You get more points if you used fewer explosions to complete the phase.

For example:

  • If you incur 13 or more explosions before you solve phase 1, but later solve it successfully, you still gain 0.5 points.
  • If you have 4 explosions while working on phase 3, and then solve it, you get 2 points for that phase (2 free explosions and 2 explosion costing you 1 point).

Finally: keep in mind that you can avoid all explosions by setting breakpoints on “bomb explosion functions” using gdb.

Autograding Your Work

Run ./grade to check your current score.

Hand-In Instructions

You must commit and push your solution files sol1.txt through sol8.txt to GitHub. Assignment collection will be automatic: after the assignment deadline, our grading system will fetch the most recent commit on the master branch of your repository.

Be sure to run ./grade and verify that we recorded your solutions. You can also check your solution files before submitting them with

mv sol1.txt s1.txt
gdb bomb
gdb> run 1 < s1.txt

and so on (but also set breakpoints not to trigger explosions!).

If you want to use late days, make a push after the deadline: we will use the push date (not the commit date) to determine your late days.

Hints

There are many ways of defusing your bomb. You can examine it in great detail without ever running the program, and figure out exactly what it does. This is a useful technique, but it not always easy to do. You can also run it in a debugger, watch what it does step by step, and use this information to defuse it. This is probably the fastest way of solving the assignment.

We do make one request: Please do not use brute force! You could write a program that tries every possible key to find the right one. But this is not good for several reasons:

  • You could lose points every time you guess incorrectly and the bomb explodes.
  • Every time you guess wrong, a message is sent to our server. You could very quickly saturate the network with these messages, and cause the system administrators to revoke our server’s access.
  • We haven’t told you how long the strings are, nor have we told you what characters are in them. Even if you made the (incorrect) assumptions that they all are less than 80 characters long and only contain letters, then you will have $26^{80}$ guesses for each phase. This will take a very long time to run, and you will not get the answer before the assignment is due.

There are many tools which are designed to help you figure out both how programs work, and what is wrong when they don’t work. Here is a list of some of the tools you may find useful in analyzing your bomb, and hints on how to use them.

  • The GNU debugger (gdb), is a command-line debugger tool available on virtually every platform. You can trace through a program line by line, examine memory and registers, look at both the source code and assembly code (we are not giving you the source code for your bomb), set breakpoints, set memory watch points, and write scripts. The CS:APP web site has a very handy single-page gdb summary that you can print out and use as a reference.
  • objdump -t will print out the bomb’s symbol table. The symbol table includes the names of all functions and global variables in the bomb, the names of all the functions the bomb calls, and their addresses. You may learn something by looking at the function names!
  • objdump -d will disassemble all the code in the bomb. You can also just look at individual functions. Reading the assembler code can tell you how the bomb works. Keep in mind that, although objdump -d gives you a lot of information, it doesn’t tell you the whole story: calls to system-level functions are displayed in a cryptic form. For example, a call to sscanf might appear as: 8048c36: e8 99 fc ff ff call 80488d4 <_init+0x1a0>. To determine that the call was to sscanf, you would need to disassemble within gdb.
  • strings will display the printable strings in your binary program.

Acknowledgements. This lab was developed by the authors of the course textbook and their staff. It has been customized for use by this course.