Lab 6: Runtime stack

Lab sessions Mon May 09 to Thu May 12

Lab written by Julie Zelenski

Learning goals

This lab is designed to give you a chance to:

  1. use gdb to dissect the runtime stack
  2. observe and understand the correct operation of the runtime stack
  3. observe and understand the symptoms of stack mismanagement

Find an open computer and somebody new to sit with. Introduce yourself and celebrate/commiserate how things went for you on last week's midterm.

Lab exercises

  1. Get started. Clone the starter project using the command

    hg clone /afs/ir/class/cs107/repos/lab6/shared lab6

    This creates the lab6 directory which contains source files and a Makefile.

    Pull up the online lab checkoff and have it open in a browser so you'll be able to jot down things as you go. At the end of the lab period, you will submit that sheet and have the TA check off your work.

  2. Dissecting the stack. Use gdb to make some observations about the runtime stack. Open stack.c in your editor and peruse the C code for the various *inky functions. Build the stack program and run gdb on it.

    • Set a breakpoint on dinky and run the program. When the breakpoint is hit, use gdb command backtrace to see the current frames on the runtime stack.
    • 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, you change to the frame for winky or main, you will then be able 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. Try changing frames and using the various info commands to see results in different contexts.

    • You can dump the raw memory from the stack using the x command.

      (gdb) x/4gx $rsp                examines 4 hex quadwords from stack starting at current rsp
(gdb) display/4gx $rsp          will auto-display top 4 quadwords on stack as you step

    • Disassemble some of the *inky functions to see coordination between the caller and callee for a function call. Trace through the caller setup (parameters passing, call), callee prolog (push saved registers, make space on stack if needed), callee epilog (restore saved registers, return), and caller resume.

    • Parameters and local variables will generally be stored in registers whenever possible, but there are some cases where the stack memory has to be used. Let's take a look at some of those situations:

      • You can see in the x86-64 one-page reference that there are registers reserved for the first 6 arguments. What happens when a function takes more that 6 arguments? Examine the disassemble for main and binky to see how/where the extra parameters are communicated from caller to callee.
      • In the assembly for binky, one of the register-based parameters is copied to the stack. Which one? Why?
      • Consider a parameter is too big to fit in a register, such as the struct coord. Examine the disassembly for slinky, dinky, and winky to see how a struct is passed as an argument. What about when passing a pointer to the struct?
      • Where are local arrays stored? Examine the init_array function to see.
      • Examine winky to learn how local variables of struct type are stored. The disassembly for winky shows adjusting the stack pointer to make space for 16 bytes of locals, yet the function declares two structs, each 16 bytes. What is going on?

    • The main function prints the address of its stack frame when run. Run the program a few times from the shell and note the addresses that are printed--- is the stack always being placed in the same location or not? Now run the program multiples times under gdb, is the stack always being placed in the same location when running under gdb?

  3. Parameter passing by "channeling". The code in the channeling function in stack.c is based on a bug I once helped a novice student with.

    • The channeling function calls the init_array function to initialize an array followed by a call to sum_array to sum the values. Run the program and execute channeling. Answer no when it asks if you'd like to print a debug statement. You'll see that the code seems to work just fine despite the fact that neither function takes any parameters and init doesn't anything! Just exactly how are these functions communicating?
    • Execute channeling again, and this time, answer yes about the debug print statement. Now what happens? How can you explain the change in outcome?

    Perhaps this exercise will help you make sense of some previous situation where your program's behavior was reproducibly yet inexplicably altered by adding/removing/changing some innocent and seemingly unrelated code!

  4. Recursion. The factorial function in stack.c is a classic recursive formulation to compute factorial.

    • First, scan the code and see what you have. Run the program and use it to calculate the factorials of some small numbers: 3, 4, 5. Enter successively larger numbers (you'll want to scale up quickly!). What is the first value of n where the result from factorial(n) becomes erroneous? Why does that happen?
    • Let's push things a bit further. Predict the outcome for entering -1 and then try it. Didn't I once tell you that a segmentation fault can only come from memory mismanagement and use of bad numbers isn't nearly as catastrophic... How is this bad number then causing a memory problem? Run in gdb and check the backtrace at the time of the crash. Does this shed some light?
    • Figure out how big each factorial stack frame is. Do this two different ways: examine the disassembly for factorial (to see how/where %rsp is adjusted, count uses of push/call to add values to stack) and again by setting a breakpoint on factorial and print $rsp in gdb to see change between successive calls. Multiply the size of the frame by the number of frames to get an estimate of the maximum possible size of the runtime stack. What is the maximum value factorial you can attempt to compute before you seem to run out of stack space?
    • The csh shell built-in ulimit -a (or limit for csh shells) reports the process limits, including the stack size. Does the stack size reported by the shell match up with the calculation you did above?

    • Change the process limit on stack size using the command shown below. (use limit stacksize 100000 for csh shells). Re-run the program, what changes?

      ulimit -s 100000

    • Edit the Makefile to change the optimization level used to compile the program. Search for the comment "EDIT HERE" to find the line that begins stack.o: CFLAGS += -Og which is specifying the compiler flags for compiling the stack program. The current setting is -Og, a relatively modest level of optimization. Change -Og to -O2 to apply more aggressive optimizations. Re-compile, run again, and enter -1. Woah! What happened? Did it actually "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. Overrunning and stack smashing. What happens when a function writes outside the bounds of its stack frame? The overrun_array function in stack.c writes past the end of the local array. Run the program and when asked, try overrunning the array by 1 position, then 2, and so on. There is no observed symptom for a small overrun, but eventually there is a catastrophic consequence. What happens and why? Now edit the body of the loop to instead change the array value like this nums[i] += 97. Recompile and run the program again and test overrunning the array again. How does the observed behavior change? What is happening?

    • The overrun_array function deliberately and obviously writes off the end of the array. Most stack smashing problems are more subtle. The check_name function in attack.c shows an all-too-common bug of reading into a stack-allocated buffer naively assuming the buffer will also be big enough for what is being read.
    • Compile the attack program. The compiler warns about "gets being dangerous" (we will ignore this for now, but will soon realize why we should heed gcc's advice...) Run the program and when it asks for your name, enter "Pat". Run again and try entering "Leland". So far so good. Now run again and respond that your name is "John Jacob Jingleheimer Schmidt". What happens?
    • Run attack under gdb, enter the very long name to reproduce the crash and examine the backtrace---how odd and unhelpful! Set a breakpoint on the check_name function. Run the program and when it stops at this breakpoint, use print $rsp to show current value of stack pointer, the result will be assigned to the gdb convenience variable $1. Examine the return address on top of the stack using x/1gx $1. Use next to walk through the gets call, enter the long name, then examine the return address again x/1gx $1. What happened? Try x/s $1 to get a different view of it. What has happened to the return address? What will now happen when check_name tries to return?
    • The version of gcc on the myths has an option to enable/disable a form of stack protection against this kind of bug. Let's find out how this safety net can help. Search the Makefile for "EDIT HERE" to find the line that begins attack.o: CFLAGS += and change -fnostack-protector to -fstack-protector. Recompile and re-run. Now what happens when you enter a long name? The stack protector is a special bit of code that halts the program on stack buffer overruns. Have you ever run into this message before?
    • What is the right fix for this bug? (Hint: it is NOT to make the buffer larger!) The danger is inherent in gets -- read its man page for advice on what to use instead.

  6. Optional extra challenge for those curious about stack-smashing evilware. Poorly-written functions like check_name can be exploited by malicious programs in a buffer overrun attack. The basic idea is to supply just the "right" input when overflowing an unprotected stack-allocated buffer.

    • You can make the program crash by entering a too-long string. A more subtle exploit is to enter a too-long string, but not with any old characters, but characters carefully chosen to overwrite the stack housekeeping in such a way to take control of the execution. Reading the source, you can see that it is intended to give only students named Leland an A grade, everyone else gets a C. You would like an A, yet don't plan on changing your name. What's a criminal to do?
    • Look carefully at the disassembly for main. Where is the code supposed to return after a call to check_name? Where would you rather it return instead? What kind of input could you supply to check_name that could get the program to return to that location instead?
    • Sneaky Guy has worked out a sample input that raises his grade. For Sneaky's attack to work, attack must be compiled without stack protection (In the Makefile around "EDIT HERE", be sure the line reads attack.o: CFLAGS += -fnostack-protector and recompile). Feed Sneaky's input to the program like this ./attack < sneaky_input. How does Sneaky Guy manage to get an A? It may help to use od -t x1 sneaky_input to see a raw dump of the file contents.
    • A truly evil attack loads the buffer with a sequence of binary-encoded instructions and overwrites the return address to jump to these instructions. The instructions are written to stage a system attack, e.g. gain access to a root shell. A modern OS has various security defenses against these buffer overrun attacks. The memory used for the stack may be marked with a "no-execute" permission, so that an attempt to execute instructions from the stack area fails with a protection violation. In the days of yore, the runtime stack was always started at the same address, and thus you could reliably predict the stack address at a particular point in the code execution. Recent versions of Linux use address space layout randomization (ASLR) which places the stack and heap at random locations, which makes it harder to return to code loaded on the stack since it isn't reliably at the same location.
    • Please note that we are in no way encouraging you to develop malware. Our purpose is to show how and why you must write your programs to avoid being exploitable. Using a buffer overrun attack to knowingly gain unauthorized access or to cause damage to other people's computers provides a maximum penalty of 10 years in prison for a first offense. See information on the Computer Fraud and Abuse Act.

Check off with TA

Before you leave, be sure to submit your checkoff sheet (in the browser) and have lab TA come by and confirm so you will be properly credited for lab 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.