This lab should be done with a partner of your choosing.
Note: This lab is being assigned at a
point in the semester when many other activities are happening.
Break begins on October 10th, and your midterm is on October 23rd.
It is only being assigned at this time because it is natural to do so,
given the content being covered in lecture. The lab has been designed
such that you should not need to work on it over break. There is also
ample time between your midterm and the first checkpoint. This is
intended to give you the freedom to decide how to budget your time
toward completing the lab. Please think carefully about how and when
is best for you to work on the lab, given all the other constraints
at this point in time.
Lab 5 Goals:
- Gain experience reading/tracing IA32 assembly instructions
- Understand how IA32 translates to C instructions, data structure
access, and function calls
- Practice with tools for examining binary files
- Gain yet more expertise in gdb
Lab 5 Introduction
You have been sleep walking again, and you wake up on the roof of Parrish
Hall. You need to find your way through its maze of floors and out
of the building in time for your first class. The problem is that
due to construction, there is no stairwell that connects more
than two floors. As a result, you need to travel along each floor to
find the next open stairwell down to the next floor below. However,
there are people or things along your path that can trip you up and
impede your progress, forcing you to run back to the roof to try again.
In this assignment, you and your partner are going to receive a binary
maze program. Your maze has 5 phases, one for each floor of Parrish Hall
(from the roof to out the door). Each floor's phase is a binary puzzle
that needs to be solved to move on
to the next floor. To solve a puzzle you need to enter a
correct phrase on stdin (you can also have your maze read
phrases from a file given as a command line argument).
Your goal is to solve all phases/floors of your maze, limiting the number of
times you trip-up along the way and have to start all over.
Your maze will automatically notify me every time you trip-up and whenever
you have solved a puzzle on a particular floor. In addition, your maze
will only run on one of the CS lab machines.
You will submit your lab5 solution in two parts:
Part 1: The Checkpoint (due Thurs Oct. 30 by 11:59pm):
- Getting past the first two floors of your maze.
Part 2: The complete solution (due Thurs Nov. 6 by 11:59pm):
- Getting past the first four floors of the maze and out the door.
- Submitting (via git) a file containing the 4 (or 5) solution strings
to solve your maze, and a file containing your write-up of how you solved
the puzzle on each floor. The instructions below copy over starting point files
for both of these into your cs31/labs/05/ subdirectory.
- Floor 5 is not required. If you solve it, you
will receive extra credit, but you must also include a description of how you
solved it in your write-up.
Getting Your maze: we will do this together in lab
- The setup procedure for this lab has several important differences
from the setup for previous labs, although many parts will be familiar.
First, both you and your partner should run setup31 to
grab the starting point code for this assignment. Suppose users molly
and tejas which to work together. Molly (mdanner1) can start by running
[~]$ setup31 labs/05 tdanner1
Once the script finishes, Tejas (tdanner1) should run
[~]$ setup31 labs/05 mdanner1
-
For the next step only one partner should copy over the starting code
[~]$ cd ~/cs31/labs/05
[05]$ cp ~lammert/public/cs31/labs/05/* ./
[05]$ ls
README maze_ID maze_how_we_solved_it soln.txt
- Again, only one partner should follow these steps to get your maze:
- In firefox on the CS system, one of you or your partner should enter
this url:
http://chive.cs.swarthmore.edu:15213/
- Enter your user name and email address on our system (username@cs.swarthmore.edu), and choose Submit.
- Choose to save the mazeX.tar file in the dialog box that pops up.
- Move the file into your labs/05 directory, and cd into that directory:
mv ~/Desktop/mazeX.tar ~/cs31/labs/05/.
cd ~/cs31/labs/05
- Untar the mazeX.tar file in your private labs/05 subdirectory:
cd ~/cs31/labs/05
ls # you should see your mazeX.tar file
tar xvf mazeX.tar
- If you cd into your mazeX subdirectory, you will see 3 files:
README maze* main.c
Remove your tar file after extracting the file
rm mazeX.tar
- Now cd up and push the changes to your partner
[mazeX]$ cd ..
[05]$ git add *
[05]$ git commit -m "lab 5 start"
[05]$ git push
- Finally, your partner can now cd into the labs/05 directory
and pull the starting code and maze:
[~]$ cd ~/cs31/labs/05
[05]$ git pull
- Do not run the maze program yet!
Do not run the maze program yet!
Do not run the maze program yet!
Checking the status of your maze
From firefox running on a CS lab machine, enter this url (you cannot
connect to this url from outside our network):
http://chive.cs.swarthmore.edu:15213/scoreboard
You will see your maze in this list. The scoreboard displays
how many stages you have solved, how many total trip-ups you
have had, and your score so far.
This information is updated about every 10 seconds. Re-load the
page to see the latest information.
Details of the maze lab
Introduction
A binary maze is a program that consists of a
sequence of puzzles, one corresponding to each floor of Parrish that you
need to pass through to get out the door. Each puzzle expects you
to type a particular string on stdin. If you type the correct string,
then the puzzle is solved and the maze program proceeds to the next floor.
Otherwise, the maze program issues a trip-up message and terminates.
The maze program is solved when every puzzle on every floor has been solved.
You will be penalized for every trip-up that you let fully happen (1/4
a point for each one), so you need to be careful not to trip-up too many
times.
You can receive up to 71 points out of 66 total for this lab (5 points
are extra credit):
- Solving the first 4 puzzles are each worth 10 points (40pts total)
- Solving the 5th puzzle is worth 5 points (this is not required,
and you must include in your write-up a description of how you
solved it to receive all 5 points).
- Your write-up of how you solved each floor is worth
4 points for each floor (16 points total). Your write-up should be
in the file maze_how_we_solved_it in your
cs31/labs/05 subdirectory.
- The checkpoint is worth 10 points.
In addition, I will take up to 5 points off total for trip-ups.
You will lose a point for each 4th trip-up (number 4, 8, 12, ...),
so you get a few for "free". I will not take off more than 5 points
total for trip-ups, unless it is clear that you are trying a brute
force approach, in which case I will.
Solve Your Maze
You must run your maze on one of the class machines; the maze
will always trip-up if run elsewhere. There are several other
tamper-proofing devices built into the maze binary as well. In particular,
using the gdb
set command while trying to solve your
maze will cause a trip-up.
To kill your maze executable (to make it exit without
tripping-up), type CNTRL-C. This way you can run your maze,
solve a puzzle on a floor, and then exit and come back later to try the
puzzle on the next floor.
You can use many tools to help you solve your maze. Look at
the hints section below for some tips and ideas. The best way is to
use ddd or gdb to step through the disassembled binary.
Although the puzzles on each floor get progressively harder to solve,
the expertise you gain as you move from floor to floor should offset this
difficulty.
Once you have solved the puzzle on a floor, I encourage you to run your
maze with a soln.txt file containing the input phrases for the floors
you have solved. The format of the file should be one phrase per line,
in order of the maze floors. Using an input file will help to prevent
you from accidentally tripping up in the maze on a previously solved floor.
For example:
./maze soln.txt
will read the input lines from soln.txt until it reaches
EOF (end of file), and then switch over to stdin for the remaining
input. This feature is also nice so you don't have to keep
retyping the solutions to floors you have already solved.
The maze ignores blank input lines, both in the file and on stdin.
To avoid accidentally tripping up in the maze, 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 the registers and the
memory states. 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 the rest of your career.
The Write-up
Edit the file cs31/labs/05/maze_how_we_solved_it in vim (or emacs) to
include a short explanation of how you solved each floor and a short
explanation of what the floor is doing.
Describe at a high-level what the original C code is doing for
each floor. For example, is it doing some type of numeric computation,
string processing, function calls, etc. and describe the specific
computation it is doing (i.e. what type of string processing and how is
that being used?).
Do not list registers and assembly code for this part, but describe
what the puzzle on each floor is doing at a higher-level in terms of
C semantics.
You do not need to reverse engineer the IA32 code and translate
every part of it to equivalent C code. Instead, give a rough
idea of equivalent C or pseudo code for the main part of the puzzle on
each floor. For example, something like "uses an if-else to choose
to do X or Y based on the input value Z" is an appropriate right level of
explanation. Something like "moves the value at %ebp-8 into register %eax"
is way too low-level.
This part of the lab should not be onerous; you should be able to
explain each puzzle in
a short paragraph or two (maybe with a few lines of C or pseudo code
to help explain).
I recommend doing the write-ups for each floor as you solve them.
Excessively verbose, low-level descriptions will be penalized,
as will vague descriptions; you want to clearly demonstrate to me that you
figured out what that floor is doing by examining the IA32 code for
each floor in your maze executable.
If you are unable to solve a floor, you can still receive partial credit for
it in the write-up part by telling me what you have determined about that
floor.
Hints
There are many ways of solving your maze. 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 under a debugger, watch what it does step
by step, and use this information to solve it. This is probably the
fastest way of solving it.
We do make one request, please do not use brute force! You could
write a program that will try every possible input string to find
the right one. But this is no good for several reasons:
- You lose 1/4 point (up to a max of 5 points)
every time you guess incorrectly and the maze trips-up.
- Every time you guess wrong, a message is sent to the mazelab server.
You could very quickly saturate the network with these messages, and cause
the system administrators to revoke your computer 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 floor. This will
take a very 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 maze,
and hints on how to use them. And refer to the week05 and week06 weekly
lab pages for information on using gdb and tools for examining binaries:
- weekly lab week 6: resources for examining binary files,
The week 4 and week 5 Thursday Lab pages also have information
about using gdb.
Figure 3.30 in the textbook is a nice summary of some useful commands.
- Professor Newhall's gdb guide has more detailed information about particular gdb commands.
See the print (p) and examine (x) examples in the "Common gdb Commands"
section in particular.
- ddd (or gdb) maze
The GNU debugger will be your most useful tool.
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
maze), set breakpoints, and set memory watch points.
- draw the stack and register contents as you are tracing through
code in gdb, and take notes as you go (this will also help you with
the write-up part of the lab assignment).
- objdump -t maze
This will print out the maze's symbol table. The symbol table includes the
names of all functions and global variables in the maze, the names of
all the functions the maze calls, and their addresses. You may learn
something by looking at the function names.
- objdump -d maze
Use this to disassemble all of the code in the maze. You can also
just look at individual functions. Reading the assembler code can
tell you how the maze works.
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 maze
This utility will display the printable strings in your maze.
Looking for documentation about a particular tool? The
the commands
apropos and
man will
help you find documentation about unix utilities,
and in gdb the
help command will explain gdb commands:
$ man objdump
(gdb) help ni
What to submit
Whether or not you have solved a maze floor, and how many times you
have tripped-up your maze is automatically submitted
to the maze server by your maze program.
Checkpoint:
For the checkpoint, you need do nothing to "submit" it. I'll check
the scoreboard at the due date to verify whether or not you met the
checkpoint.
Complete Solution:
For the complete solution you will use git, as in previous labs, to
submit the contents of your cs31/labs/05 directory. In particular,
make sure that it contains these three files:
- maze_how_we_solved_it: the write-up part for your maze.
- soln.txt: your maze's solution input file: ./mazeX soln.txt
- maze_ID: this file just lists your maze ID
You do not need to submit your binary maze file (I have a copy of it),
but you will not be penalized for doing so. I'll also check the scoreboard
at the due date to determine which floor you solved and how many times
you trip-up in your maze.
Submit
As with Labs 2, 3 and 4, if you are ready to submit your code,
simply commit your changes locally
using git add and git commit. Then run git push while in the
labs/05 directory. Only one partner needs to run the final
push, but make sure both partners have pulled and merged
each others changes. See the section on using a shared repo
on the git help page.