Unit 1e – Procedures and Stack

Local Variables and Arguments

 
xxxxxxxxxx
4
1
void b (int a0, int a1) {
2
  int l0 = 0;
3
  int l1 = 1;
4
}

• Can l0, l1, a0, a1 be allocated statically?

  • In other words, can their static address by determined at compilation time?
  • What about recursion?

Local Variables and Recusion

• How many different version of n are there?

 
xxxxxxxxxx
5
1
void a (int n) {
2
  if (n == 0) return;
3
  a(n - 1);
4
  printf("%d\n", n);
5
}

• What if there is no apparent recursion?

 
xxxxxxxxxx
4
1
void b (int n) {
2
  int l = n * n;
3
  c(l - 1);
4
}

• What if c() calls b()?

Life of a Local Variable / Argument

• Scope

  • Local variables are only accessible within declaring procedure
  • Each execution has its own private copy

• Lifetime

  • Allocated when procedure starts
  • "Freed" when procedure returns (in most languages)

Procedure Activation

• Activation: execution of a procedure

  • Starts when procedure is called, ends when it returns
  • There can be many activations of same procedure alive at once

• Activation Frame

  • Memory that stores activation's state
  • Includes local variables and arguments

• Should we allocate activation frames from the heap?

  • Call malloc() to create frame on procedure call?
  • Call free() on procedure return?

Heap vs Allocation Frames

• Order of frame allocation and deallocation is special

  • freed in reverse order of allocation

• Simple allocation for frames:

  • Reserve big chunk of memory for all frames
  • Initial address is known
  • Simple, cheap allocation: add or subtract from a pointer

• Questions

  • What data structure is this like?
  • What restriction do we place on lifetime of local variables?

Runtime Stack

• Stack of activation freames

  • Stored in memory, grows up from bottom

• Stack pointer

  • General purpose register (we will use r5)
  • Stores base address (address of first byte) of current frame

• Current frame is the "top" of the stack

• First activation is the "bottom" or "base" of the stack

  • Local variables of initial function (e.g., main)
  • Offset from stack pointer is static

• Each frame is like a struct

  • Base of frame is in r5 (stack pointer)
  • Each variable in procedure is a member of the struct

What is Stored in the Activation Frame?

• Local variables

• Arguments

  • Some architectures use registers for arguments

• Return address

  • Register r6 works for one call, but not for multiple calls
  • Saved only if needed (i.e., only function calls other functions)

• Other save registers

  • Called function may change register values
  • Values that must be kept after call are saved

Stack Frame Layout

• Order of storage

  • Decided by the compiler
  • Based on order convenient for stack creation
  • Static offset to any member from its base (frame pointer)

• Example:

   
  xxxxxxxxxx
  5
  1
  void b (int a0, int a1) {
  2
    int i0 = 0;
  3
    int i1 = 1;
  4
    c();
  5
  }
  

  

Accessing a Local Variable or Argument

• Frame is stored and accessed similarly to a struct

  • Base is in r5
  • Offset is known statically

• Example:

   
  xxxxxxxxxx
  4
  1
  int i0 = 0;
  2
  int i1 = 1;
  3
  i0 = a0;
  4
  i1 = a1;
  

  

Some Implications

• What is the value of l in foo when it is active?

 
xxxxxxxxxx
2
1
void goo() { int x = 3; }       goo();
2
void foo() { int l; }           foo();

• What is wrong with this?

 
xxxxxxxxxx
4
1
int *foo() {
2
  int l;
3
  return &l;
4
}

Procedure Prologue

• Code that executes just before procedure starts

  • Part in caller before call
  • Part in callee at beginning of call
  • Generated by the compiler for procedure call

• Allocates activation frame and changes stack pointer

  • Subtract frame size from stack pointer r5

• Possibly saves register values

• Assigns values to arguments

• Code that executes when procedure ends

  • Part in callee just before return
  • Part in caller just after return

• Deallocates activation frame and restores stack pointer

  • Add frame size to stack pointer r5

• Possibly restores some saved register values

Division of Labour

• Caller prologue (before call)

  • Allocate stack space for arguments
  • Save actual argument values to stack

• Callee prologue (start of function code)

  • Allocate stack space for return address and local variables
  • Save return address to stack, if needed

• Callee epilogue (end of function code)

  • Load return address from stack if stored there
  • Deallocate stack space of return address and local variables

• Caller epilogue (after return from call)

  • Deallocate stack space of arguments

Example

 
xxxxxxxxxx
9
1
void foo() {
2
  b(0, 1);
3
}
4
​
5
void b(int a0, int a1){
6
  int i0 = a0;
7
  int i1 = a1;
8
  c();
9
}

Creating the Stack

• Every program thread starts with a hidden procedure

  • Name varies, usually start, sometimes crt0

• The start procedure

  • Allocates memory for stack
  • Initializes the stack pointer
  • Calls the thread's first procedure (e.g., main())

Question

• What is the value of r5 in three(), assuming a call to foo()?

Arguments

• Number and size of arguments is statically determined

• Value of arguments is dynamically determined

• Compiler may choose to put arguments on the stack

  • Caller pushes argument values onto stack, callee reads arguments from stack

• Sometimes compiler chooses to use registers for arguments

  • Often used in Intel-based programs
  • Caller places argument values in pre-determined registers, callee reads arguments from these registers
  • Why is this done? When is it a good idea? When is this not a good idea?

Return Value and Optimizations

• Return value

  • in C and Java, procedures / methods can return only a single value
  • C compilers use a designated register (r0) for this

• Return address does not always need to be saved to the stack

  • When is this possible?

• Local variables sometimes don't need to be in the stack

  • Why? When is this possible?

 
xxxxxxxxxx
7
1
int s;
2
void foo() {
3
  s = add(1, 2);
4
}
5
void add(int a, int b) {
6
  return a + b
7
}

Summary: Local Variables

• Stack is managed by code generated by compiler

  • Grows from bottom up, allocated by subtracting stack pointer
  • Local variables and arguments accessed with static offset from stack pointer

• Caller prologue

  • Allocates space on stack (or registers) for arguments, stores their values

• Callee prologue

  • Allocates space on stack for local variables and saved registers

• Callee epilogue

  • Deallocates stack frame, restores saved registers

• Caller epilogue

  • Deallocates arguments on stack, get return value from r0.

Vulnerability in Buffer Overlow

The Buffer Overflow Bug

• If the position of the first '.' in str is more than 10 bytes from the beginning of str, this loop will write portions of str into memory beyond the end of buf
• If an attacker can provide the input, it can determine what values are written into memory beyond the end of buf

Changing the Return Addresss

• The return address is

  • stored in memory on the stack
  • the address of instruction that executes after return
  • changing it changes the program's control flow

• Attacker's goal

  • introduce code into the program from outside
  • trick program into running it

• Changing the return address

  • allows attackers to change control flow
  • if it points to data, then that data becomes the program

Stack-Smash Attack String

• Hard parts

  • determining location of return address in attack string
  • determining address to change return address to

• Making it easier

  • approximate return address value

  • start attack string with many copies of return address

  • follow it with long list of nop instructions

    • aka "nop slide", "nop sled" or 'nop ramp'

  • finally include the code for the worm

• Works if return address guess within nop slide

Protecting from Buffer Overflow

• Buffer boundary check

• What if stack grew down?

  • Active frame at the highest addresses