CompOrg Binary Bomb Squad

Due Date: Oct 31st at 11:59PM.
Autograded.

Late Penalty: 100% (grading script turned off at due date, absolutely, no exceptions, don't ask!)

This counts for two homeworks!

Assignment

You have been selected to be a member of an elite group of cyber-techno-digi-gurus who are needed to defuse some binary bombs. Your have been selected due to your expertise in IA32 assmembly language, your knowledge of data representation and computer arithmetic, and your extensive knowledge of how to read an ASCII reference chart.

You will be given a "binary bomb" which you must defuse. If you are not capable of defusing the bomb, one of two possible things will happen:

1. You will get a bad grade on this assignment.
2. The world will end.

I can't remember which will actually happen... feel free to use whichever one provides you with more motivation.

Binary Bomb

A binary bomb is an executable program (Linux executable) that consists of six phases. Each phases expects the user to enter a particular string (via stdin). If the expected string is entered, the phase has been defused and the progam moves on to the next phase. If the expected string is not entered, the program explodes (prints "BOOM" and quits). Your job is to defuse as many phases as possible.

Each phase tests a different aspect of machine language programs:

Phase 1:	comparison
Phase 2:	loops
Phase 3:	conditionals/switches
Phase 4:	recursive calls and the stack discipline
Phase 5:	pointers
Phase 6:	linked lists/pointers/structs

There is also a challenging "secret phase"... (but it's a secret)

Each student will get a unique bomb, the solution to your bomb (the sequence of expected strings) is different than everyone else's. Feel free to help each other with general concepts (you can work together), but you are not allowed to submit solutions to your bomb unless you determined the solutions. In other words - if you need help, feel free to ask Dave or the TAs or anyone else to help you get started, but you must have a complete understanding of how to figure out what the solution is (you will certainly need this ability on a test!).

The phases are ordered in (roughly) increasing difficulty, so don't underestimate the project just because you can solve the first phase - the subsequent phases get harder!

How to get your bomb

Bombs are available on the web, you can pick up a bomb using either of the links below:

BSD

Linux

Your bomb will be sent in a zip file that includes:

• The actual executable program named bomb .

• A file named ID that identifies your bomb. You need this to check the status of your bomb grade. Your bomb ID must be unique, it is not acceptable for multiple people to submit solutions to the same bomb!

• A file named bomb.c. This is the actual C code for the main program. You don't really need this, but it may be helpful to understand what the main program is doing. You don't get the C code for the actual phases, the point of this assignment is that you need to determine what they are doing just by looking at the assembly language code (which you can get by disassembling the executable program).

We assume that you can handle a zip file! Under Windows you can use WinZip (available at www.winzip.com). Under Unix you can use unzip to unzip a zip file.

NOTE: The "bomb server" that sends you a binary bomb will make sure that your bomb is not available to anyone else! It is not acceptable that two students use the same bomb - everyone needs to download a unique bomb (with a unique solution!). Each student needs only one bomb, so please don't download lots of them (there are a fixed number of bombs pre-made, and if the server runs out this will inconvience other students who have not yet received one bomb!). Although every bomb is different, they are all comparable in difficulty, so there is no reason to get more than one bomb.

How to submit

Your bomb includes spyware that will automatically tell us whenever you solve a phase or explode your bomb. You don't need to do submit anything for this assignment. You can check the status of your bomb grade by visiting the : Bomb Status Page.

IMPORTANT!!!! If you are using your own Linux machine, you must be using an account with the same username as your CS username on monica. If you don't do this you won't get credit for this assignment!!!!!

Grading

Grades will be determined by the number of phases you are able to solve:

• Phases 1-4 are worth 20 points each.
• Phases 5 and 6 are worth 10 points each.
• 10 points extra credit for anyone who can solve the "secret phase".

Explosions will be shown on the HW3 status page, but don't count toward your grade (you don't lose any points for explosions).

HINTS:

• There are lots of helpful tools available on Unix:

  • The strings command.
  • The objdump command.
  • gdb (the GNU debugger).
  • emacs (actually emacs probably won't help, but I like it so much I wanted to include it)

  The book describes how to use objdump and gdb to dissasemble code and (in the case of gdb) debug assembly language programs. Complete documentation on gdb is available online at http://sources.redhat.com/gdb/current/onlinedocs/. There is also a downloadable PDF version of the manual and a quick reference card (all available via the same link).

  Below are some example GDB commands.

  • Printing a register (%edx): print $edx (note that you need to use '$', not '%').

  • Display a register (automatically prints out the value of the register after every instruction): display $edx

  • Step one instruction: stepi or si

  • Set one instruction, but treat a subroutine call as a single instruction (like stepi, but does not go into subroutines that are called).

  • Tell GDB to display the next instruction each time it executes an instruction: display/i $eip (very useful!)

    eip is the register that holds the address of the next instruction to be executed.

  • Examine memory at an asolute memory address: x/4x 0xbfbff0d4c will display 4 words (as hex) starting at address 0xbfbff0d4c, x/s $edx will display the string (ASCII chars terminated by a null) starting at the address in register %edx.

  • Disassemble an entire subroutine: disas subname. For example you could disassemble main like this: disas main.

  • print information about the current stack frame: info frame

  • Print information about all currently active stack frames: backtrace

• You may find that you need to look up ASCII character values, here is an ASCII reference table that shows hex values and corresponding ASCII characters:

  | 00 nul| 01 soh| 02 stx| 03 etx| 04 eot| 05 enq| 06 ack| 07 bel| | 08 bs | 09 ht | 0a nl | 0b vt | 0c np | 0d cr | 0e so | 0f si | | 10 dle| 11 dc1| 12 dc2| 13 dc3| 14 dc4| 15 nak| 16 syn| 17 etb| | 18 can| 19 em | 1a sub| 1b esc| 1c fs | 1d gs | 1e rs | 1f us | | 20 sp | 21 ! | 22 " | 23 # | 24 $ | 25 % | 26 & | 27 ' | | 28 ( | 29 ) | 2a * | 2b + | 2c , | 2d - | 2e . | 2f / | | 30 0 | 31 1 | 32 2 | 33 3 | 34 4 | 35 5 | 36 6 | 37 7 | | 38 8 | 39 9 | 3a : | 3b ; | 3c < | 3d = | 3e > | 3f ? | | 40 @ | 41 A | 42 B | 43 C | 44 D | 45 E | 46 F | 47 G | | 48 H | 49 I | 4a J | 4b K | 4c L | 4d M | 4e N | 4f O | | 50 P | 51 Q | 52 R | 53 S | 54 T | 55 U | 56 V | 57 W | | 58 X | 59 Y | 5a Z | 5b [ | 5c \ | 5d ] | 5e ^ | 5f _ | | 60 ` | 61 a | 62 b | 63 c | 64 d | 65 e | 66 f | 67 g | | 68 h | 69 i | 6a j | 6b k | 6c l | 6d m | 6e n | 6f o | | 70 p | 71 q | 72 r | 73 s | 74 t | 75 u | 76 v | 77 w | | 78 x | 79 y | 7a z | 7b { | 7c | | 7d } | 7e ~ | 7f del|

• Once you get a phase completed, you can store the solution in a file (each phase as a single line of text). You can run your bomb, telling it to first read strings from this file, and to then (once it hits the end of the file) to read from stdin - just give the bomb program the name of the file on the command line:

  ./bomb partial-solution.txt

  Be careful, since if you have blank lines at the end of the file they will be treated as guesses for the subsequent phases (make sure there are no blank lines at the end of the file).

  When running your bomb in gdb, you can also feed it partial solutions from a file, by using the command "run partial-solution.txt" (this assumes that "partial-solution.txt" is the name of your file).