CS31 Mini Lab 6: Binary Maze: The great escape from Parrish Hall

Gain experience reading and tracing through the execution of x86_64 assembly instructions.

Practice with tools for examining binary files.

Put your GDB skills to work to solve an assembly code puzzle.

maze_ID : a file into which you will add your maze ID (maze number).

how_we_solved.txt : a file into which you will add your description of how you solved each phase of your maze.

soln.txt: a file into which you will add the solution to each maze phase, one solution per line. You can use this file as input to your maze program. If you enter your answer on one line, make sure to hit <enter> at the end to introduce the newline character so that your solution is parsed correctly.

First, cd into your cs31/labs/Lab6-userID1-userID2 subdirectory.

Next, only one of you and your partner will follow these steps to get your maze.

At this point, your partner can remotely copy your mazeX.tar file so that you each have the same one. From the one of you who has the file’s account run scp to copy the file from your account to your partner’s account (scp file_name <username>@<machinename>:.). For example, to copy to user’s tnas account on the machine oil I’d do the following (and you can use oil too, or any other lab machine name):

scp mazeX.tar tnas@oil:.  # replace tnas partner's user name, X with your maze num

(partner@oil) Password:

mv ~/mazeX.tar .     # replace X with your maze num
git add mazeX.tar
git commit -m "my maze"
git push

Next, you and your partner should open your how_we_solved_it.txt file and add the following information:

At this point both you and your partner can add your mazeX.tar and how_we_solved_it.txt to your repos (replacing X with your maze number):

$ git add mazeX.tar how_we_solved_it.txt # replace X with your maze number
$ git commit -m "our maze"
$ git push

Next, you and your partner will untar your maze tar file:

$ cd ~/cs31/labs/Lab6-userID1-userID2
$ ls                  # NOTE: your mazeX.tar file will have a different number
maze1.tar
$ tar xvf maze1.tar   # NOTE: put your maze number here instead of mine
README
maze
main.c
$ ls
maze*  maze1.tar  maze.c  README

### DO NOT RUN THE MAZE PROGRAM YET! ###

You must run your maze on one of the CS lab machines.

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 gdb to step through the execution of 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: Make sure to hit <enter> at the end to introduce the newline character so that your solution is parsed correctly.

./maze soln.txt

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!

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

strings maze: display the printable strings in your maze.

objdump: objdump may provide some information that is helpful, but gdb will be your most useful tool

endbr64: You can ignore this instruction in any code that appears in this lab. It helps to ensure that jump instructions (including function calls) change the PC to valid locations in a program. It provides one mechanism to prevent attackers from hijacking control of a program, but it won’t affect the behavior of your maze in a way that you need to account for (i.e., it doesn’t change register values or memory that you care about). For more information, see: control flow integrity.

lea — Load effective address: This instruction computes a memory address without actually accessing memory at the location of the address. It’s really deceiving, since it looks like a memory access (it puts parentheses around a register), but it’s really just computing the address that would be accessed via the same displacement(register) syntax. See the "Load Effective Address" section of the textbook for more information.

Instructions that reference parts of registers. You may see code sequences that reference the lower half or lower quarter of a register. For example:

mov    %al,-0xa1(%rbp)

Stack canary code. You may see some odd code sequences around function return code that includes an instruction that looks like this: sub %fs:0x28,%rax. For example:

0x56556a53 <+100>:    sub    %fs:0x28,%rax
0x56556a5a <+107>:    jne    0x401723 <func+117>
< function return instructions here>
0x56556a61 <+117>:    call   0x401240 <__stack_chk_fail@plt>