Lab 6 Goals:

• Learn to read and trace through the execution of IA32 assembly code
• Practice using gdb and ddd

Contents:

• The Backstory
• Details
• Writeup
• Getting Files and maze Program
• Hints, Tips, and Resources
• Submit

You've 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 get out of the building in time for your first class. Due to construction, there is no stairwell that connects more than two floors, so you need to travel along each floor to find the next open stairwell. Watch out for obstacles along your path that can trip you up and impede your progress, forcing you to return back to the roof to try again.

In this assignment, you will receive a binary executable file for a maze program. The maze has 5 phases, one for each floor of Parrish Hall (from the roof to the front door). Each floor is a puzzle that needs to be solved to move on to the next floor. To solve each puzzle you need to enter a passphrase to standard input. If you type the correct string, the puzzle is solved and you proceed to the next floor. If not, you "trip up" and the program terminates. The goal is to solve all phases/floors of the maze, limiting the number of times you trip up along the way. Note that floor 5 is extra credit.

This lab is graded out of 66 points (with 5 possible extra credit points):

1. The first 4 puzzles are worth 10 points each (40pts total)
2. The 5th puzzle is worth 5 points (this is not required, and you must include in your writeup a description of how you solved it to receive all 5 points).
3. Your writeup of how you solved each floor is worth 16 points (4 points for each floor). Your writeup should be in the file maze_how_we_solved_it.
4. The checkpoint is worth 10 points.

You can lose up to 5 points for trip-ups. You lose a point for each 4th trip-up (number 4, 8, 12, ...), so you get a few for free.

You must run your maze on one of the lab machines; the maze will always trip-up if run elsewhere. There are several other tamper-proofing devices built into the maze. 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.

The best tools to help you escape the maze are ddd and gdb, which let you step through the disassembled binary instructions.

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, we 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 prevent you from accidentally tripping up on a previously solved floor. For example:

$ ./maze soln.txt 

will read the input lines from soln.txt and then use stdin for the remaining input. 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 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.

Edit the file maze_how_we_solved_it to include a short explanation of how you solved each floor. It's okay if you used some amount of "guess and check" to solve a floor, but you should still describe what you saw in the assembly code or the state of the running program that inspired your guessing strategy.

Describe at a high-level what you suspect the original C code was doing for each floor. 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 level of explanation. Something like "moves the value at %ebp-8 into register %eax" is too specific.

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). We recommend doing the writeups for each floor as you solve them.

If you are unable to solve a floor, you can still receive partial credit by describing what you have determined about that floor in the writeup.

Here are the new partnerships. The course webpage has a section on expectations for working with partners.

Both you and your partner should:

1. On the CS system, cd into your cs31/labs subdirectory

     $ cd ~/cs31/labs
   

2. Get your Lab6 ssh-URL from the GitHub server for our class: CS31-s18
3. Clone a local copy of your shared repo in your private cs31/labs subdirectory:

     git clone [your_Lab6_URL]
   

4. cd into your Lab6-you-partner subdirectory.

     $ cd Lab6-you-partner
     $ ls
     QUESTIONNAIRE  maze_how_we_solved_it
   

5. Next one partner should get a maze:
   1. Using firefox on a CS machine, navigate to this url:

      http://water.cs.swarthmore.edu:8000
      

   2. Enter your username, and click Submit.
   3. Choose to save the mazeX.tar file.
   4. Edit maze_how_we_solved_it to make note of your maze number (the X in mazeX.tar).
   5. Move the .tar file into your Lab6-you-partner directory:

        $ mv ~/mazeX.tar .
      

   6. Extract the compressed files:

        $ tar xvf mazeX.tar
      

   7. Add, commit, and push the new files and the changed maze_how_we_solved_it file.
   8. The other partner should then to a git pull.

Maze files:

main.c: contains the maze program's main function. You can open main.c in your favorite editor and see what the code is doing.
maze: the maze program binary executable that you need to solve.

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):

water.cs.swarthmore.edu:8000/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 20 seconds. Reload the page to see the latest information.

There are many ways to solve the maze. You could examine it in great detail without ever running the program, and figure out exactly what it does. However it's probably easier to run the program through a debugger to identify the instructions that determine whether the passphrase is correct, and work backwards from there. The debugger lets you examine what is stored in registers and in memory as the program runs.

Do not use brute force, i.e. don't write a program that tries every possible input string to find the right one. This is a bad approach for several reasons:

1. You lose 1/4 point (up to a max of 5 points) every time you guess incorrectly and the maze trips up.
2. Every time you guess wrong, a message is sent to the maze lab server. You could very quickly saturate the network with these messages, and cause the system administrators to revoke your computer access.
3. 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 would have 26^80 guesses for each floor. This would take a very, very long time to run, and you would not get the answer before the assignment is due.

You may see some x86 instructions in your maze assembly that are not on the IA32 cheatsheet. In this case, look at some of the IA32 Documentation and References for information about that instruction. The wikipedia page may be most useful.

• One instruction that you may see is cmov, which is a conditional move instruction that uses the condition codes to either move or not. The encoding is similar to the conditional jump instructions. For example, cmovge performs a move when jge would have performed a jump.
• Another is sarl with only one argument. This does a shift by 1: sarl %eax is equivalent to sarl $1, %eax

There is an art to determining how deep to trace through assembly code execution. You will need to trace into some function calls, but can also first try to see what happens before and after the call. You may also assume that C library functions like scanf do what you think they do--tracing into the scanf function, for example, will not help you figure out the solution to a level.

Tools and Resources

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.

• week 8 lab session: resources for examining binary files

• Debugging IA32 gdb and ddd overview.

• The 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.

  One note about the x command in gdb: its formatting is sticky, so if you want to print out the contents of different memory addresses for different sized values and types, you need to specify the format for each difference. For example:

  x/s 0x1234     # print as a string what is stored at memory address 0x1234
  x   0x5678     # also prints as a string (x's formatting is sticky)
  x/wd 0x5678    # to print as an int what is stored at memory address 0x5678
                 # after printing as a string, need to specify the width and type
                 #   w: 4 bytes, d: print as decimal int  
                 # (x/wx) would print the 4-byte value in hex
  x/a 0x9abc     # will print what is at memory address 0x9abc as an address
  

  See the gdb guide above for more examples of using the x command, including the different formatting options.

• 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.

• Also, look at the IA32 Documentation and References for information about particular instructions, registers, the call stack, etc.

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

Here is some more information on man and reading manual pages: man

There is a QUESTIONNAIRE file for you to fill out and submit with your lab solution. Your answers to the questionnaire will not affect your grade.

For the checkpoint, you don't need to submit anything. We will check the scoreboard at the checkpoint date to verify that you've solved at least the first two levels. For the final due date you should push your changes to the following files:

1. maze_how_we_solved_it: your writeup
2. soln.txt: your maze solution
3. QUESTIONNAIRE