Lab 7: Runtime Stack

Lab sessions Tue Feb 26 to Thu Feb 28

Lab written by Julie Zelenski, with modifications by Nick Troccoli

Learning Goals

This lab is designed to give you a chance to:

  1. Become more familiar with useful GDB commands and tricks when working with assembly
  2. observe and understand the correct operation of the runtime stack
  3. diagnose symptoms of stack mismanagement

Find an open computer and somebody new to sit with. Share with them anything fun you did over the weekend!

Get Started

Clone the repo by using the command below to create a lab6 directory containing the project files.

git clone /afs/ir/class/cs107/repos/lab7/shared lab7

Open the lab checkoff form.

Note: there will be compiler warnings when you make this starter project - this is expected for some of the exercises!

Exercises

1) GDB Tips and Tricks

Gdb is an indispensible tool when working on assignment 6, particularly for Binary Bomb. Share your most productive gdb tips with your labmates to get a few new tricks into everyone's repertoire!

Examining Stack Frames

Here is a reminder of some commands introduced in previous labs, assignments and lectures:

  • Use backtrace to display all of the stack frames from the current point of execution back to main. With an argument N, backtrace N shows only the N innermost frames and backtrace -N shows only the N outermost.
  • The up, down, and frame n commands allow you to change the selected frame. These commands don't change the state of program execution (the execution remains where it stopped in the topmost frame), but they allow you to examine the runtime state from the perspective of another stack frame. For example, changing to the frame main allows to print the variables/parameters that are visible only in that scope.
  • The info frame command tells you the story about this stack frame. The info args and info locals provide information about the parameters and local variables, respectively.
  • You can view data on the stack using the x command on $rsp
    (gdb) x/4gx $rsp   // 4 quadwords, in hex, read from top of stack

Auto-display and Printing Registers

The info reg command displays current values for all integer registers. Use e.g. p $rax to print value from a single register. In gdb, remember that access to a register is via $name instead of the more familiar %name.

A register is treated as an untyped 8-byte value and when you ask gdb to print it, it shows a decimal integer or hex address. You can dictate how to interpret the value by adding a /fmt to the print command or by using a C typecast, e.g.

(gdb) p $rax
$1 = 4196128
(gdb) p/t $rax
$2 = 10000000000011100100000
(gdb) p (char *)$rax
$3 = 0x400720 "Hello, world!\n"

The handy gdb command display sets up an expression to be repeatedly evaluated and printed as you single-step. For example, try these display expressions:

(gdb) display/2gx $rsp     // 2 quadwords read from stack top
(gdb) display/3i $rip      // next 3 assembly instructions to execute

Type display with no arguments to list all of the currently-set expressions to display, and undisplay X to stop displaying expression X in the list shown by display. Clever use of the display command can provide similar benefits to the tui GUI-like gdb interface, minus the flakiness and garbled display.

Conditional Breakpoints

You can set breakpoints to only trigger when certain conditions in your code are true. For instance, say you have the following loop in your code:

1    for (int i = 0; i < count; i++) {
2        ...
3    }

If you wanted to step through the code inside the loop just the last time the loop executed, with a normal loop you may have to skip over many program breaks before you get to the part you want to examine. However, gdb lets you add an optional condition (in C code syntax) for when the breakpoint should be stopped at:

(gdb) break 2 if i == count - 1

The format is [BREAKPOINT] if [CONDITION]. Now this breakpoint will only be hit the last time around the loop! You can even use local variables in your expression, as shown above with i and count. Experiment to see what other useful conditions you might use.

Breakpoint Commands

You can set up a sequence of commands for gdb to execute each time a particular breakpoint is reached. Any valid gdb command is fair game -- get a backtrace, enable/disable other breakpoints, evaluate a C expression, change the value in a register, and so on. You can even use breakpoint commands to temporarily patch buggy code from within the debugger!

Let's say a buggy line 192 allocates one fewer byte than needed:

 192   s = malloc(strlen(t));         // oops, supposed to be len + 1

First, we set a breakpoint on line 192.

(gdb) break 192
Breakpoint 1 at 0x400a8d: file program.c, line 192.

Next, we add commands to that breakpoint to insert a correct allocation, jump over the buggy line, and continue from there. We can do this with command; if we run this, it will prompt us for what commands to execute for the most recently-added breakpoint. It will continue allowing us to type until we type end:

(gdb) commands
Type commands for breakpoint(s) 1, one per line.
End with a line saying just "end".
print s = malloc(strlen(t)+1)
jump 193
continue
end

Thus, each time line 192 is about to be executed, the breakpoint commands intervene to automatically insert the correct allocation, skip over the buggy statement, and continue execution. Neat! (and perhaps quite useful for certain explosive devices...)

2) Stack Mechanics

Let's practice some of these new commands in gdb while examining the mechanics of the runtime stack. Open stack.c in your editor and peruse the C code for the various functions.

  • Run the stack program under gdb. Set a breakpoint on kermit and when at the breakpoint (note that you won't be able to set these before running the program), set up these auto-display expressions - the first displays the top 4 entries on the stack, and the second displays the next 3 assembly instructions to execute:
    (gdb) display/4gx $rsp
(gdb) display/3i $rip

Now use stepi to single-step by assembly instruction. Walk through the kermit function, including the calls made to dinky/binky. Observe how control is transferred from caller to callee and back. The auto-display instructions show you what is happening on the stack and how $rip and $rsp are changing.

x86 has a mere handful of registers and they are in high demand; the compiler works hard to maximize their use. Parameters and return values are passed/returned using registers, and local variables will be kept in registers whenever possible. The compiler will prefer use of "scratch registers" (e.g. callee-owned registers) where possible so as to avoid having to save/restore the caller's data (as is required if using the caller-owned registers).

  • At the start of kermit function, it pushes the values from the caller-owned registers %rbp and %rbx to the stack and at the end, it pops them back off. This is consistent with the requirement that if a callee wants to use a caller-owned register it must preserve its value and restore when done. What does kermit use those registers for? Why must it use caller-owned registers? Why would a callee-owned register not work in this case?
  • The bigbird declares a fairly long list of local variables. The array it declares is stored on the stack, but it juggles the other variables in the callee-owned registers without needing to write those to the stack. Why is it able to do this? Single-step through the bigbird function and use info locals to see which variables are accessible at each step.

3) "Channeling" Information Between Functions

The channel program was inspired by a bug encountered in a past offering of CS107. The code in question was "working fine" until adding a print statement, which caused a incommensurate amount of grief. Removing the print statement "fixed" the problem - very mysterious!

  • Review the code in channel.c. The init_array and sum_array function each declare a stack array. The init function sets the array values, the sum function adds the array values. Neither init nor sum takes any arguments. There is a warning from the compiler about sum_array, what is it?
  • The program calls init_array() then sum_array(). Despite no explicit pass/return between the two calls, the array seems to be magically passed as intended. How are these functions communicating? The term for this is "channeling".
  • The program's second attempt to channel the array from init to sum fails. What is different about this case?

Tell your partner a story about a previous situation where your program's behavior was reproducibly yet inexplicably altered by adding/removing/changing some innocent and seemingly unrelated code -- does this exercise shed light on a possible explanation?

4) Recursion

The factorial program runs a classic recursive factorial function, similar to the example shown in lecture on Monday. Let's review it and take a closer look at the assembly level to understand how it works.

  • Run ./factorial 5 6 7 8 9 to compute some small factorials. Try some larger values: ./factorial 10 11 12 13 14 15 16. Something fishy seems to be going on. The factorial function grows at an alarming rate -- it doesn't take long before overflowing the range of an integer!
  • Look over the code for the factorial function and trace out what you think will happen if you try to compute the factorial of a negative number. Now try it: ./factorial -1. Did you get what you expected? How is an invalid number causing a memory problem? Run factorial under gdb on argument -1. Use backtrace to find out where the program was executing at the time of the crash. Does this shed some light on what has gone wrong?

  • Get into gdb and figure out how big each factorial stack frame is. Here are two different strategies; try both!

    • Disassemble factorial and scan its instructions. You are looking for those instructions that change %rsp. Each pushq and callq instruction copies an 8-byte value to the stack and decrements %rsp. %rsp can also be explicitly moved to open up space for local variables or scratch results. (In this case, however, factorial exhibits no manual adjustment of %rsp. The only data stored in its frame are saved registers placed there by push/call instructions.) Count the push/call instructions in factorial and and multiply by 8 to get the total number of bytes used per stack frame.
    • Set a breakpoint on factorial, let a few calls through, and then use the gdb commands info frame 1 and info frame 2 to examine the top two stack frames. Look for the frame addresses labeled Stack frame at and subtract the two to compute the size of a single frame.
    • These two approaches should give you the same answer. Do they?

  • In the OS on myth, the stack segment is configured at program start to a particular fixed limit and cannot grow beyond that. The bash shell built-in ulimit -a (or limit for csh shells) displays various process limits. What does it report is the process limit for stack size?

  • Divide the stack limit by the size of a factorial frame (info: 1 Megabyte = 1024 Kilobytes, 1 Kilobyte = 1024 Bytes). This estimates the maximum stack depth for factorial. Try factorial of -1 under gdb again. When it crashes, use backtrace -10 to see stack top to determine the stack depth. How close is that depth to the maximum you estimated?
  • Edit the Makefile to change the optimization level used to compile the program. Find the line that reads factorial: CFLAGS += -Og. The current setting is -Og, a relatively modest level of optimization. Change -Og to -O2 to apply more aggressive optimizations. Make clean and make, then run ./factorial -1again. Woah! What happened? Did the compiler "fix" the infinite recursion? Disassemble the optimized factorial to see what the compiler did with the code. This fancy optimization is called "tail-recursion elimination". (Note: gdb may not work as well with higher optimization levels, so you may have trouble e.g. setting breakpoints in the optimized version).

5) Debugging Stack Misuses

What happens when a function creates chaos within its stack frame? What are the observed symptoms? How do we debug these kinds of errors?

Stomping Around

The clear_array function in buggy.c has the wrong bounds on its loop. It's a common-enough bug, especially to programmers unaccustomed to C's zero-based array indexing, but it has a surprising consequence in this context.

  • Before you try executing the program, first discuss with your partner: what do you expect to be the consequence?
  • Run the program. It never seems to complete. Hmmm.
  • Run it under gdb. Interrupt the program using Ctl-C and see where it is executing. Continue the program, then interrupt again. Where is it executing now?
  • Interrupt again and then step from here. Why is the loop taking so darn long? Just what is happening with the value of i?

The value of i is changing as a result of code that doesn't directly assign to it. These kind of bugs are calling "stomping" or "clobbering" memory. A variable can be stomped on due to an under/overrun of a neighboring region, using a pointer into a deallocated stack frame, referring to freed heap memory, or using an uninitialized pointer. These errors are difficult to debug since the variable is not named in the code that affects it and the stomping may go unnoticed until much later, making it difficult to connect cause and effect. Whereas Valgrind is awesome about reporting when you write to an invalid address, it cannot detect that you wrote to a valid address for the wrong reason. We need another strategy/tool to find this kind of error.

Let's learn how to use a gdb watchpoint . The gdb watch command is given an expression or a memory location to watch. gdb sets up a special kind of breakpoint that stops your program whenever there is a change in the value of that expression or a write to that memory location. Here are some examples:

(gdb) watch myvar           // report when myvar changes
(gdb) watch *0x608502       // report if write to memory location
  • Run under gdb, set a breakpoint on clear_array and once hit, set up a watchpoint to monitor changes to i.
  • Continue from here and gdb will stop on each change to i. The watchpoint will alert you to each increment of the counter in the loop: from 0 to 1, 1 to 2 and so on, but it also will report when i gets stomped on.
  • What code is responsible for clobbering i?

Watchpoints can be a useful tool for tracking down those bugs that make mysterious changes to memory (and may be a useful tool in reverse engineering a bomb, too. Hmm...)

Don't Gets Me Started

The standard C library function gets has an inherently awful design. It is intended to read a single line of text from stdins, stopping at the first newline character, and writing the read characters into the client's buffer. The fatal flaw of gets is that its only argument is the starting address of the buffer, with no indication of that buffer's length. Without the length, gets cannot tell when it should stop writing characters to avoid overflowing the buffer. There is absolutely no way to use gets safely. Its use has long been deprecated in favor of the properly-constrained fgets function, but for reasons of backward compatibility, gets lives on in the standard library.

  • First read the BUGS section of man gets for harsh words against the function and hints of the security problems therein. When you compile the smash program, you'll get a variety of warnings from the compiler and linker that try to further dissuade you from using gets. Let's observe the consequences if we proceed past the warnings and use the function anyway.

The smash.c program calls gets to read the user's input into a buffer of size 12. Any input longer than 12 will write past the end of the stack-allocated buffer. The consequence ranges from silent to catastrophic depending on how many excess bytes are written.

  • Run the smash program and when prompted for your name, enter G. Hopper. This name fits in 12, no problem. Now enter John Hennessy. Just a little long is ok? Now enter Marc Tessier-Lavigne. Definite overrun, but still getting away with it? Push it to John Jacob Jingleheimer Schmidt and we finally get the crash we deserve. Run the program under gdb and enter this same long name. At the point of the crash, use backtrace. Woah, what the heck has happened to the stack? Let's see if we can figure that out.
  • Disassemble the greet function and sketch a diagram of its stack frame with your partner. Be sure to note the location of the buffer and its relationship to neighboring data.
  • For any input longer then 12, the characters read by gets will overflow the buffer. What is the immediate neighbor of the buffer? What is the consequence of overwriting it?
  • What is the critical data that when overwritten, will cause the program to crash? How long must the input be to reach this critical data? What if the input is 1 byte too long? 2 bytes? 4 bytes? even longer?
  • The crash does not occur at the time when the data is overwritten; it is later when the corrupted data is used that is the problem. Identify the assembly instruction in the greet function at which the crash occurs and explain what is happening in that instruction.
  • Run the program again. When prompted, enter this exact input: meghan duchess of sussex. Pluto? How did we end up there? The function pluto isn't even called from anywhere in the program. This outcome is most surprising! Go back to your stack diagram and see if you can work out how this happened. When greet finished, instead of resuming in main, it "resumed" in pluto . What was the resume address of the instruction in main? How did the intended resume address change into an address in pluto?

Fun followup reading: Peter van der Linden's book Expert C Programming: Deep C Secrets summarizes the most famous gets exploit in the early bird gets() the Internet Worm. (To access the book content on Safari Books, you will need to authenticate with your SUNet id and may have to wait if there are too many concurrent users. The entire Expert C book is available and chock full of fascinating information -- I highly recommend it for its illuminating and comprehensive coverage of all things C!)

6) Extra: Function Pointers in Assembly

One last assembly-related detail that may be useful on your assignment 6 (hint hint) is how funtion pointers. As mentioned in lecture, you can have a jmp or call instruction with an operand that is either the label you would like to jump to, which is hardcoded in the instruction itself, or the location of where the address is we should jump to. For instance, if the jump location is stored in %rax, then we could say jmp *%rax or call *%rax to jump to or call the function at the address stored in %rax. This is useful, because a function pointer is really just storing the address of where a function's first instruction lives. Take a look at function_pointers.c, which contains the gfind_max generic function from lab4, as well as some code that calls it. Step through the assembly code for the gfindmax function to find where the compare_function parameter is referenced. What assembly instruction calls the function pointer? Print out the value of the compare_function parameter, and then put a breakpoint at the start of the cmp_alpha function and resume until you hit it. Then, print out the value of the %rip register. These two approaches should give you the same value printed out. Do they?

Challenge Problem

The previous problem about stack smashing with pluto was a well-crafted example that only worked because of the way pluto was written. Experiment with writing your own functions that exhibit buffer overflow issues and experiment with how you can craft cases that let you jump to arbitrary functions, or even arbitrary parts of functions. What do you find?

Check off with TA

At the end of the lab period, submit the checkoff form and ask your lab TA to approve your submission so you are properly credited for your work. It's okay if you don't completely finish all of the exercises during lab; your sincere participation for the full lab period is sufficient for credit. However, we highly encourage you to finish on your own whatever is need to solidify your knowledge. Also take a chance to reflect on what you got what from this lab and whether you feel ready for what comes next! The takeaways from lab6 should be understanding the gdb commands to dig around in the stack frames and being able to relate the contents of the stack to the runtime program state - both valuable when debugging. Here are some questions to verify your understanding and get you thinking further about these concepts:

  • Why are the registers used for function parameters completely fixed, yet no conventions apply to where locals are stored?
  • Explain the rules for caller-owned versus callee-owned register use. What is the advantage of this arrangement relative to a simpler scheme such treating all registers as caller-owned or callee-owned?
  • Explain how insertion/deletion of a seemingly unrelated printf statement could make a difference in a program's behavior.
  • What are the signs in gdb that help you diagnose a stack overrun has trashed the return address?