- Due Friday 10/8 11:59pm EDT (1 day later for DCE)
- Each student gets their own bomb.
- This assignment is self-grading. There is no explicit need to store your binary bomb in your Git repository, though it wouldn’t hurt.
- Collaboration policy: Academic honesty is expected, as always. For this assignment, academic honesty requires that you solve your bomb, and that you not disable the connection the bomb makes to our checking server. If you appear to have disabled this connection we will interpret your results as cheating. You may as usual discuss your work with other students in the class, but do not tell people how to solve their bombs or exactly what your phases were.
Introduction
A coronavirus has planted roughly 200 “binary bombs” on our class server, and if we don’t defuse them, that’s it for the economy.
A binary bomb is a program that consists of a sequence of phases. Each phase
reads a line from the standard input. If the line is correct, then the phase
is defused and the bomb proceeds to the next phase. Otherwise, the bomb
explodes by printing "BOOM!!!"
, deducting points from your problem set
grade, and then terminating. The bomb is defused when every phase has been
defused.
There are too many bombs for us to deal with, so we are giving each student a different bomb to defuse. Your mission, which you have no choice but to accept, is to defuse your bomb before the due date. Good luck!
Download
Obtain your bomb by pointing your Web browser here:
http://cs61.seas.harvard.edu:15213/
Enter a username and your grading
server email address and hit
Submit. The server will return your bomb in a tar file called
bomb
k
.tar
, where k
is the unique number of your bomb.
Save the bomb
k
.tar
file to a 64-bit Linux host, such as Docker. Move
the file to the directory you want to do your work. Then run tar -xvf bomb
k
.tar
. This will create a directory called ./bomb
k
with the
following files:
README.md
: Identifies the bomb and its owners.bomb
: The executable binary bomb.bomb.cc
: Source file with the bomb’s main routine.
If you lose the bomb, no problem; just go back to http://cs61.seas.harvard.edu:15213/ and request it again.
If you are using a Mac with Apple silicon (an M1 processor), see below. Check your chip by running
arch
in a terminal window: if it saysarm64
, you are on Apple silicon.
Defuse
Before running your bomb, read the entire assignment!
Your job is to defuse your bomb. This involves supplying it with just the
right input. But though there is a bomb.cc
file, it doesn’t actually contain
the code for the various phases. You’re going to defuse the bomb by interpreting
assembly language, lucky you.
The bombs are tamper-proofed in a couple ways. For one, they can only be defused when the computer is connected to the Internet. Running the bomb on a machine without Internet connectivity won’t do anything.
You can use many tools to help you defuse your bomb. Probably the best way is to use your favorite debugger to step through the disassembled binary.
Each time your bomb explodes you lose points (up to a max of 20 points) in the final score for the problem set. So there are consequences to exploding the bomb. Be careful!
The first four phases are worth 10 points each. Phases 5 through 7 are a little more difficult, so they are worth 15 points each. The maximum score you can get is 85 points.
The phases mostly get harder to defuse. The expertise you gain as you move from phase to phase should offset this difficulty, but please don’t wait until the last minute to start.
The bomb ignores blank input lines. If you run your bomb with a command line argument, for example,
./bomb sol.txt
then it will read the input lines from sol.txt
until it reaches the end,
and then switch over to stdin. Make sure to include a newline at the end of
the file!
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 state. (One of the intended effects of the lab is that you will get very good at using a debugger.)
Hint: The initialize_bomb
function will never explode the bomb.
Turnin
The bomb notifies us automatically of your progress as you work on it. You can keep track of how you are doing, and compare (anonymously) with everyone else, by looking at the class scoreboard at: http://cs61.seas.harvard.edu:15213/scoreboard
This web page is kept updated to show the progress for each bomb. It may take up to a minute for new explosions and defusings to show up on the scoreboard. Also, the scoreboard displays time in UTC, so do not be alarmed if it appears that your bomb is reporting status for the future!
Hints
There are many ways of defusing your bomb. Hypothetically, you could even
figure out the bomb without ever running the program, just from the machine
code. But it’s much easier to use tools. run the bomb under a debugger,
watch what it does step by step, and reverse-engineer the input it wants.
Examine the binary using objdump
or strings
. Here are some hints we have
found useful in analyzing bombs.
Understanding assembly instructions
There are lots of ways to puzzle out instruction meanings: lecture,
the book, even the examples distributed as part of our lectures.
(For example, if you’re curious about the leaq
instruction, go to
the cs61-lectures repositories, and try “grep leaq */*.s
”.
Also try searching for the instruction name on Google: “movq instruction
”. But be
careful. There are two syntaxes used for x86-64 assembly language. We
use “AT&T syntax” in class and in the book, but many online
references use “Intel syntax,” which switches the order of arguments
and is different in other annoying ways. For instance, Intel calls
the %rax
register rax
(no percent). Read about the differences
in syntaxes in the Aside on p177 of CS:APP3e, or
here or
here.
Docker
Our Docker setup comes with support for gdb
, lldb
, and objdump
, and you
can run your bomb there. Please check that you have the latest version of our
Docker environment by typing cs61-docker-version
at Docker shell prompt. It
should say 11
or 11.arm64
. If it does not, pull from a cs61-lectures
or
cs61-psets
directory and build your Docker environment again (cd cs61-XXX/docker; ./cs61-build-docker
).
gdb
The GNU debugger 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 most of your bomb), set breakpoints, set memory watch points, and write scripts. The CS:APP3e web site has a handy two-page gdb summary (TXT) that you can print out and use as a reference. Here are some other tips for using gdb:
-
To keep the bomb from blowing up every time you type in a wrong input, you’ll want to learn how to set breakpoints.
-
Some critical gdb commands for this pset are
r
(of course),c
,b
,disas
,x
(for instance, tryx/5i $pc
andx/20xw $rax
—gdb names registers with initial dollar signs), andsi
. Thes
command is sometimes useful and sometimes dangerous. Many of the related commands on these pages might also be useful. Check out, for example,finish
,info reg
, anddisplay
. And do read the manual for these commands! It contains lots of helpful time-saving hints. To exit gdb useq
. -
Many students really like the TUI interface obtained by running
gdb -tui bomb
. Read up about the TUIlayout
command. Some people also like to run gdb under gdb-mode in emacs. -
Consider creating a file called
.gdbinit
in yourBOMBDIR
.gdb
automatically executes all commands listed in this file every time it starts up. The commandset confirm off
is useful here (if you get tired of questions like “Quit anyway? (y/n)”). For this lab, a breakpoint or two would be super useful too! But thanks to a security precaution, yourBOMBDIR/.gdbinit
is likely not to be loaded by default. (Check this by reading gdb’s startup messages. If you see an error about “auto-loading has been declined
,” then yourBOMBDIR/.gdbinit
was not loaded.) To get around this, create a file named.gdbinit
in your home directory containing “add-auto-load-safe-path [BOMBDIR]
”. (More on auto-load-safe-path) (Versions 3 and up of our Docker environment come with the correct~/.gdbinit
.) -
For online documentation, type “help” at the gdb command prompt, or type “man gdb” or “info gdb” at a Unix prompt.
objdump -d
(or objdump -S
)
Use this to disassemble all of the code in the bomb. You can also just look at individual functions.
objdump -t
This 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!
strings
This utility will display the printable strings in your bomb.
man ascii
A handy table of character encodings.
For more, don’t forget your friends the commands man
and info
, and
the amazing Google and Wikipedia. In particular, info gas
has more
than you might ever want to know about assembler.
Apple silicon (ARM64 processors)
Newer Macs (and some other computers) ship with processors not compatible with
Intel. You cannot use gdb
to run the bomb on these machines, and our
original Docker configuration does not work either.
You can download a virtual machine emulator, such as UTM (free) or Parallels ($). Unfortunately, VMware Fusion is not currently available for Apple-silicon Macs. We are developing setup instructions for UTM.
We also have an improved Docker configuration that runs the bomb pretty effectively (although not quite as nicely as on native Intel processors). Here’s how it works. (Steps 1–4 should only be required once. Steps 5–9 are required every time you start a bomb defusing session.)
-
Update your
cs61-f21-psets-YOURNAME
repository (cs61-psets
for short) withgit pull handout main
. This should update several files, including a filepset2/bomb.gdb
. -
Open the terminal and change to the
cs61-psets/docker
subdirectory. Run./cs61-build-docker -a
to build an ARM64 Docker environment. -
Copy your bomb contents into
cs61-psets/pset2
. That directory should look like this:kohler@Eddies-MacBook-Pro:pset2$ ls bomb bomb.cc bomb.gdb
-
Create a file
cs61-psets/pset2/sol.txt
to contain your bomb solution. (You will not be able to type input directly into the bomb. All input will go insol.txt
.) -
Change to the
cs61-psets/pset2
subdirectory and run../cs61-run-docker -a
. -
From within Docker, type
cs61-docker-version
. It should report:cs61-user@7e3ad29d8888:~/cs61-psets/pset2$ cs61-docker-version 11.arm64
If it just gives a number like
11
, you left off the-a
argument tocs61-run-docker
. -
Run
gdb -ix bomb.gdb
. -
At the prompt, type
run-bomb
orrb
. This will start up the bomb, but pause it at an implicit breakpoint well before running any code. You should see something like this:cs61-user@65c7eeb7f370:~/cs61-psets/pset2$ gdb -ix bomb.gdb GNU gdb (Ubuntu 9.2-0ubuntu1~20.04) 9.2 Copyright (C) 2020 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Type "show copying" and "show warranty" for details. This GDB was configured as "aarch64-linux-gnu". Type "show configuration" for configuration details. For bug reporting instructions, please see: <http://www.gnu.org/software/gdb/bugs/>. Find the GDB manual and other documentation resources online at: <http://www.gnu.org/software/gdb/documentation/>. For help, type "help". Type "apropos word" to search for commands related to "word". The target architecture is assumed to be i386:x86-64 (gdb) rb 0x0000004000802100 in ?? () (gdb)
The bomb has stopped well before its first instruction. It will do this every time you restart it with
rb
. (Note that the normalr
(run
) command is not available in this mode.) -
Type
c
to continue into the bomb’s actual contents (after setting some useful breakpoints first).(Note: If the bomb reaches the end of
sol.txt
before you pass all its phases, it will printError: Premature EOF
and exit. This is not an explosion and won’t take off points from your grade.) -
To try different solutions, edit
sol.txt
, save it, and typerb
at the(gdb)
prompt.
As you work, you may get tired of entering c
after rb
every time. Add the
following line to your .gdbinit
to automatically c
ontinue after rb
:
set $run_bomb_continue = 1
Please report any problems with this Docker setup to us via Edboard.
This lab has been modified extensively from CMU’s CS:APP course version.