Lab 7: Runtime stack

Lab sessions Tue May 22 to Sat May 26

Lab written by Julie Zelenski

Learning goals

This lab is designed to give you a chance to:

  • learn some new gdb tricks (just in time for bomb!)
  • observe and understand the correct operation of the runtime stack
  • diagnose symptoms of stack mismanagement

Find an open computer and somebody new to sit with. Introduce yourself and talk about the summer adventures you have planned.

Get started

Clone the lab7 repo by using the command below.

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

Open the lab checkoff form.

Lab exercises

1) Leveling up with gdb

Gdb is your go-to when defusing the infamous binary bomb. Share your most productive gdb tips with your labmates and let's try to get a few new tricks into everyone's repertoire!

Examining stack frames

A quick refresher of some gdb commands we previously introduced:

  • Use backtrace to display all of the stack frames 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

Printing registers, auto-display

The info reg command displays current values for all integer registers. Use 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 asm instructions to execute

Shrewd use of display can approximate a poor man's version of tui (minus the flakiness and garbled display).

Pro-tip: 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 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

Set a breakpoint on line 192. Now add commands to that breakpoint to insert a correct allocation, jump over the buggy line, and continue from there.

(gdb) break 192
Breakpoint 1 at 0x400a8d: file program.c, line 192.
(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

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 if needing protection from a hair-trigger explosive device...)

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, set up these auto-display expressions:
    (gdb) display/4gx $rsp        // top 4 entries on stack
(gdb) display/3i $rip         // next 3 asm instructions

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 value are passed/returned using registers, 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 I once helped a novice student resolve. Their code was "working fine" until they added 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 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 fact program runs a classic recursive factorial function.

  • Run ./fact 5 6 7 8 9 to compute some small factorials. Try some larger values: ./fact 10 11 12 13 14 15 16. Something fishy seems to be going on. The factorial function grows at alarming rate -- it doesn't take long before overflowing the range of integer!
  • Look over the code for factorial and trace out what you think will happen if you try to compute the factorial of a negative number. Now try it: ./fact -1. Did you get what you expected? I may have once said that a segmentation fault can only come from memory mismanagement and use of bad numbers isn't usually catastrophic? How then is an invalid number causing a memory problem? Run fact under gdb and and run 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 the %rsp. Each pushq and callq instruction copies an 8-byte value to the stack and decrements %rsp. The %rsp can also be explicitly moved to open up space for local variables or scratch results. (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 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. This estimates the maximum stack depth for factorial. Try factorial of -1 under gdb again. When it crashes, use backtrace 10 and backtrace -10 to see stack top and bottom and subtract frame numbers 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 fact: 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 ./fact -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".

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?

Love thy neighbor. The clear_array function in buggy.c has the wrong bounds of 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 at the shell. It never seems to complete. Hmmm.
  • Run it under gdb. Interrupt the program and see where it is executing. Continue the program, then interrupt again. Where is 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...)

gets, the root of all evil. The standard C library function gets has an inherently awful design. It is intended to read a single line of text from stdin, 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 Don Knuth. 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!)

Check off with TA

Before you leave, be sure to submit your checkoff sheet and have your lab TA come by and confirm so you will be properly credited. If you don't finish everything before lab is over, we strongly encourage you to finish the remainder on your own. Double-check your progress with self check.