CSE 351 Upgraded

Memory Address Space Photo

The stack:
-Section of memory that takes up the highest useable addresses and holds local variables and other procedure context
-As the arrow indicates, it “grows” downwards: the stack occupies lower addresses as it allocates more space.

The Stack

-Section of memory that takes up the highest useable addresses and holds local variables and other procedure context

-As the arrow indicates, it “grows” downwards: the stack occupies lower addresses as it allocates more space.

-end/"top" of the stack is indicated by the current address stored in the stack pointer (%rsp)

-as %rsp is manipulated, the conceptual end of the stack will move with it (i.e., the addresses < Reg[rsp] are not considered part of the stack). This makes %rsp a very useful reference point.

Stack Manipulation: 
-can be changed directly via subq (for allocation) and addq (for deallocation) instructions, but note that this does not affect any of the data in memory, just which data are considered part of the stack.
-We can also transfer data to and from the stack using the push src and pop dst instructions.
push will:

1. decrement %rsp and then

2. copy the data from the source operand into the newly-allocated space.
   
   pop will:

   1. copy the data that %rsp points to into the destination operand and then

   2. increment %rsp to deallocate that space.

x86-64 Procedure Calling Conventions

calling conventions are the established set of rules to guarantee that procedures can properly pass data and control to one another.

-When describing one procedure calling another, we will call the procedure doing the calling the caller and the procedure being called the callee.

return address: address of the caller’s next instruction to execute. Indicate how to return to the caller and we do this by storing a return address on the stack

Procedure Calls/Returns/Passing

Procedure Call (call)
To pass control to another procedure we use the call label instruction. This will:

1. Automatically push the return address onto the stack and then

2. Update the program counter (%rip) to the address of the specified label.

Procedure Return (ret)
When a procedure wants to return control, it uses the ret instruction. This will:

1. Automatically pop the return address off of the stack and then

2. Update the program counter (%rip) to the popped address.

Procedure Data Passing
To pass arguments, the first six must be placed in the following registers in order: %rdi, %rsi, %rdx, %rcx, %r8, and %r9
               Diane’s   Silk        Dress       Cost    $8              9.”
All additional arguments must be placed on the stack in reverse order (i.e., the 7th argument is pushed last so that it is closest to the return address).

The return value must be placed in %rax. For return values larger than a word size, we instead return a pointer to the return value in %rax.

Stack

we conceptually divide our stack into stack frames, which hold the local state of each procedure instantiation so that we can support multiple simultaneous instantiations of individual procedures (recursion). 


Any space allocated during the execution of the procedure must be deallocated in a parallel manner to ensure that ret correctly pops off the return address and completely deallocates the stack frame. This process of managing stack frames properly is known as stack discipline.

consequences of the stack’s last in-first out (LIFO) operation −− the caller’s stack frame cannot be deallocated until its callee’s stack frame is. Old data in a deallocated stack frame should NOT be used because it is likely going to be overwritten by a different stack frame later!


Picture Explanation:
In the example shown below, main first calls a function foo, which in turn calls a function bar. After foo returns, main then calls another function baz, which then overwrites parts of foo's old stack frame (and possibly bar’s, depending on the frame size): ret 

Stack Frame Details

Layout:

1. The return address, which is pushed onto the stack by the call instruction, marks the beginning of the stack frame.

2. Older assembly code used %rbp as the frame pointer, an indicator of the beginning of the current stack frame. The old value of %rbp would need to be saved if it is being used as a frame pointer, but this is considered optional in x86-64.

3. Old register values that needed to be saved would be pushed, followed by allocated space for local variables that aren’t being stored solely in registers.

   • Made up of by Callee + Caller

   • callee-saved register values are typically close to the return address because they must be saved before the procedure can use those registers

   • caller-saved register values will come after the local variables, because they are only saved when a procedure call is made.

4. If this procedure calls another procedure, it may need to push more register values and then arguments 7+ onto the stack.

Every stack frame is organized the same way, though each frame can be a different size and will omit parts that it doesn’t need since accessing the stack (in memory) is much slower than registers.
If the callee procedure in the diagram had more than six arguments, arguments 7+ would be part of the caller’s argument build area just above the stored return address.

Stack Frame Contents

In an “ideal” case, our minimal stack frame contains just a return address −− this means all of the procedure’s work is being done in the registers, which are much faster to access than memory.


A procedure needs to grow its stack frame in the following situations:

• It has too many local variables to hold in caller-saved registers −− will save old values of callee-saved registers it uses.

• It has local variables that can’t fit in registers (e.g., arrays or structs) −− these must have space allocated for them in the stack.

• It uses the address-of operator (&) to compute the address of a local variable −− registers don't have addresses.

• It calls another function that takes more than 6 arguments −− additional registers are pushed to the stack in the argument build area.

• It uses data in caller-saved registers across (i.e., needed before and after) a procedure call.

• It modifies/uses callee-saved registers.

Register Saving Conventions

Part of the calling conventions that describe how we should deal with register reuse to avoid accidentally destroying another procedure’s data.

Since procedures have access to all of the general-purpose registers during their execution, there are registers designated as callee-saved or caller-saved.

Register values can be saved by pushing them onto the stack (caller saved) OR copying them into a register of the opposite type (callee saved)

Callee-saved Registers

It is the callee’s responsibility to save the old value before using/manipulating the register. The callee then restores the old value before returning to the caller. 

The saving is one of the first things done by the callee and the restoring is one of the last (just before ret) 

From the perspective of the caller, it assumes that the values it has in the callee-saved registers will remain the same when control is passed back to it. 

**When you need to save multiple caller- or callee-saved registers, it is important maintain proper ordering. For example, if you pushq %rcx followed by pushq %rdx, you will need to popq %rdx before popq %rcx −− remember LIFO!**

Caller-saved Registers

It is the caller’s responsibility to save the old value (if the caller needs it later) before passing it to the callee.

The caller then restores the old value after the callee returns. The saving is done right before calling the callee (but before the argument build, if it is used) and the restoring is done right after the call.

From the perspective of the callee, it assumes that it has free reign to change the values of the caller-saved registers without worrying about their old values. 

**When you need to save multiple caller- or callee-saved registers, it is important maintain proper ordering. For example, if you pushq %rcx followed by pushq %rdx, you will need to popq %rdx before popq %rcx −− remember LIFO!**

Recursion

What are the 4 phases of building and running an executable?

1. Compiling

2. Assembling

3. Linking

4. Loading

(Mnemonic: CALL)

Which of the "CALL" phases are part of "building" an executable?

• Compiling

• Assembling

• Linking

Buffer Overflow

Buffer: region of memory(usually an array) used to temporarily store data. 

Buffer overflow: writing data past the end of a buffer and overwriting adjecent memory locations, which is achievable since there is no automatic bounds checking in c. 

-Can be innocuous or can cause program execution to break depending on whats overwritten

Stack Smashing

-Form of buffer overflow focus on in CSE 351

-Defined as writing past the end of the local array in the stack.

-Array elements are laid out in increasing address order which means buffer overflow naturally moves towards higher addresses.

-However, since stack grows downward, stack smashing eventually leads to overwriting the return address in the current stack frame and data in previous stack frames.

-ret instruction pops off the word of data current found at %rsp into %rip, modifying the stored return address can cause our program to jump to unexpected places.

-Sometimes results in segfaults, sometimes not

Code Injection ATTACKS

Takes advantage of the fact that everything in a computer is stored as data in memory to use buffer overflow to write instructions into the buffer and then modify the return address to execute the injected code. This is know as code injection ATTACCKKKU

Typical Procedure:

1. Designed exploit code is compiled to its binary/machine code representation and put at the beginning of the buffer.

2. Based on the space available, any necessary padding is added to reach the current frame’s stored return address.

3. The address of the beginning of the buffer is used to replace the return address.

When done successfully, the ret instruction will pop the address of the buffer into %rip instead of the return address to the caller and the program will begin executing the exploit code!
-Even though the exploit code is no longer part of the stack, that data remains there until it is overwritten by future stack frames.

-This attack relies on knowledge of the address of the buffer on the stack and the amount of space allocated between the array and the return address.