This lab should be done with your lab 6 partner: Lab 6 Partners

Expectations for Working with Partners

Lab 6 Goals:

• reading and tracing through the execution of IA32 assembly
• understanding how IA32 translates to C instructions, data structure access, and function calls
• practice with tools for examining binary files
• gain expertise in gdb

Contents:

• Getting Starting Point Files and maze program
• Assignment Overview
• Assignment Details
• Write-up
• Hints, Tips, and Resources
• Lab Questionnaire
• Submitting your Lab

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 lab6 solution in two parts:

Part 1: The Checkpoint (due Thursday Nov. 2 (after the midterm)):

• getting past the first two floors of your maze.

Part 2: The complete solution (due Tuesday Nov 7 ):

• getting past the first four floors of the maze and out the door.
• submitting (via git push) 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.
• 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.

Lab 6 Starting point git repo:

Both you and your partner should do:

1. Get your Lab06 ssh-URL from the GitHub server for our class: CS31-F17
2. On the CS system, cd into your cs31/labs subdirectory

   cd ~/cs31/labs
   

3. Clone a local copy of your shared repo in your private cs31/labs subdirectory:

   git clone [your_Lab06]
   

   Then cd into your Lab06-you-partner subdirectory.

     $ ls
     README.md  QUESTIONNAIRE  maze_ID  maze_how_we_solved_it  soln.txt
   

4. Next, one of your or your partner should get a maze:
   1. In firefox on the CS system, one of you or your partner should enter this url:

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

   2. Enter your user name on the CS system, and choose Submit.
   3. Choose to save the mazeX.tar file in the dialog box that pops up.
   4. move the file into your labs/ directory:

      mv ~/Desktop/mazeX.tar ~/cs31/Labs/Lab06-you-partner/.
      

   5. cd into your Labs/Lab06-you-partner directory, and add the mazeX.tar file to your git repo and commit and push it:

      cd ~/cs31/Labs/Lab06-you-partner/.
      ls
        mazeX.tar
      git add mazeX.tar
      git commit 
      git push
      

      Your partner should then to a git pull to get the copy of the mazeX.tar file.

      cd ~/cs31/Labs/Lab06-you-partner/.
      git pull
      ls 
        mazeX.tar
      

5. both you and your partner can untar the mazeX.tar file in your private labs/ subdirectory:

   cd ~/cs31/Labs/Lab06-you-partner
   ls  # you should see your mazeX.tar file
   tar xvf mazeX.tar
   

tar extracts 3 files (none of these three files should be added to your git repo)

6. if you run ls in your repo, you will see these 3 new files extracted from your mazeX.tar file:

   ls
   README  maze*  main.c
   

Do not run the maze program yet!

Maze files:

main.c: contains the maze program's main function. You can open main.c in vim (or another text editor) and see what the code is doing.
maze: contains the maze program binary. This is binary contains a IA32 maze (described below), that you need to solve for this lab.

You must run the maze lab and the browser connecting to the scoreboard from a CS lab machine. If you want to work on this from home, then ssh into a cs lab machine to run both. See the CS lab help remote access page for information about how to do this.

From firefox running on a CS lab machine, enter this url (you cannot connect to this url from outside our network):

almond.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. Re-load the page to see the latest information.

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

1. Solving the first 4 puzzles are each worth 10 points (40pts total)
2. 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).
3. 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 Lab06-you-partner subdirectory.
4. The checkpoint is worth 10 points.

In addition, I will take up to 5 points off total for trip-ups. You 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.

Edit the file cs31/Labs/Lab06-you-partner/maze_how_we_solved_it in vim (or another text editor) 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.

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

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

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 if greater than or equal to.

There is a bit of an art in 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 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. And refer to the week04 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 6 Thursday Lab pages also have information about using gdb. And Figure 3.30 in the textbook is a nice summary of some useful commands.

• 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

With every lab assignment is a file named QUESTIONNAIRE for you to fill out and submit with your lab solution. In this file you will answer some questions about the lab assignment. You should fill this out and submit it with your lab solution.

What to submit

The maze floors you have solved and your number of trip-ups are automatically submitted to the maze server by running 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 need to push your changes to the following files:

1. maze_how_we_solved_it: the write-up part for your maze.
2. soln.txt: your maze's solution input file: ./mazeX soln.txt
3. maze_ID: this file just lists your maze ID
4. QUESTIONNAIRE: the lab questionnaire

You do not need to submit your binary maze file (we have a copy of it). 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.

Before the Due Date

Only one of you or your partner needs to push your solution from one of your local repos to the GitHub remote repo. (it doesn't hurt if you both push, but the last pushed version before the due date is the one we will grade, so be careful that you are pushing the version you want to submit for grading):

From one of your local repos (in your ~you/cs31/labs/Lab6-partner1-partner2 subdirectory)

git push

Troubleshooting

If git push fails, then there are likely local changes you haven't committed. Commit those first, then try pushing again, for example:

git add QUESTIONNAIRE
git commit
git push

Another likely source of a failed push is that your partner pushed, and you have not pulled their changes. Do a git pull. Compile and test that your code still works. Then you can add, commit, and push.

If that doesn't work, take a look at the "Troubleshooting" section of the Using git page. You may need to pull and merge some changes from master into your local. If so, this indicates that your partner pushed changes that you have not yet merged into your local. Anytime you pull into your local, you need to check that the result is that your code still compiles and runs before submitting.