• Course website: https://su21.cs161.org/

• Course textbook: https://textbook.cs161.org/

Overview

Lecture 3: Memory Safety Vulnerabilities

1. Buffer overflow vulnerabilities

2. Integer memory safety vulnerabilities

3. Format string vulnerabilities

4. Heap vulnerabilities

5. Writing robust exploits

Lecture 4: Mitigating Memory Safety Vulnerabilities

1. Memory-safe languages

2. Writing memory-safe code

3. Building secure software

4. Exploiting mitigations

   • Non-executable pages

   • Stack canaries

   • Pointer authentication

   • Address space layout randomization(ASLR)

5. Combing mitigations

Buffer overflow vulnerabilities

As the name indicates, buffer overflow occurs in memory buffer where adjacent memory segments are modified illegally by writing long data into some unbounded memory address.

The lecture begins with an example, imagine travelers entering an airport, suppose the stuff will let the traveler to input his/her name in the terminal so that the ticket class can be found and displayed accordingly.

The vulnerability is that user can input a long enough string to overwrite the ticket class in the next line, and you know what can happen :)

Example in C code:

char name[20];
char instrux[20] = "none";

void vulnerable(void) {
  ...
  gets(name);
  ...
}

The function “gets” doesn’t check the number of input characters, so user can actually make the name overwrite to instrux.

In the graph above, the lower addresses are at the bottom. Remember that blocks in the graph represent 4 bytes(I have no idea why they drew it in this way…). Also note that both instrux and name are global variables, so they’re stored in the way that name is at the lower address than instrux.

BTW, the overflow trick is not necessarily to be done by overwriting char arrays, since C doesn’t check the bound of arrays when you are accessing them, you can perform this kind of overflows on any types of arrays on memory!

The following table shows how important buffer overflow is in the field of security,

Stack smashing – The most common kind of buffer overflow

• Occurs on stack memory

• What are some values on the stack that an attack can overfllow?

  • Local variables

  • Functions arguments

  • Saved frame pointer

  • Return instruction pointer(RIP)

Example (overwriting RIP):

RIP = return instruction pointer, refers to the value stored at the place right below the bottom of the stack(here “below” means having a higher address, sorry about the potential confusion)

void vulnerable(void) {
  char name[20];
  gets(name);
}

Assume that the attacker wants to execute instructions at address 0xdeadbeef, then he/she just need to overflow the stack of function “vulnerable” with the “gets” function, and overwrite RIP with 0xdeadbeef.

writing some garbage input ended with \xef\xbe\xad\xde\0 to “name”, will do the job,

What if we want to execute code that is not in memory?

Place it in memory by yourself! “Shellcode” describes malicious code inserted by the attacker into memory, to be executed using a memory safety exploit.

To make sure of shellcode and put everything together for an attack:

1. Find a memory safety(e.g. buffer overflow) vulnerability

2. Write malicious shellcode at a known memory address

3. Overwrite RIP with the address of the shellcode

4. Return from the function(so that eip will be set to RIP, where your shellcode locates)

Note that it’s also possible to directly write shellcode with the bytes you write to overflow the buffer, like this:

Memory-safe code

It might be tempting to modify the vulnerable code snippet above to the following:

void vulnerable(void) {
  char name[20];
  gets(name);
}

/* modify it to 
 * -------->
 */

void vulnerable(void) {
  char *name = malloc(20);
  gets(name);
}

Guess what, this kind of modification would still lead to overflow in memory! The only difference is that instead of a buffer overflow on the function, the modified code will have a buffer overflow on the heap(which is still a vulnerability).

Just like the example before last one, in which “name” array is defined as a global variable on the heap, this kind of overflow on heap will potentially enable attacker to overwrite other global variables on the heap.

Real solution to “gets” overflow:

Specify the size of input with another function!

void safer(void) {
  char name[20];
  ...
  fgets(name, sizeof(name), stdin);
  ...
}

Vulnerable C library functions

• gets
  • Use fgets instead
• strcpy
  • Use strncpy or strlcpy instead
• strlen
  • Use strnlen instead

Integer memory safety vulnerabilities

Case study:

void func(int len, char *data) {
  char buf[64];
  if (len > 64) return;
  memcpy(buf, data, len);
}

The above code might seem to be bug-free at the first sight, but actually if the attacker input an negative number as len, it will easily pass the if statement check. While for the function memcpy, this -1 will be automatically seen as unsigned integer(that would be a huge one), so that a parameter larger than 64 can be passed and cause trouble!

Another case study:

void func(size_t len, char *data) {
  char *buf = malloc(len + 2);
  if (!buf) return;
  memcpy(buf, data, len);
  buf[len] = '\n';
  buf[len + 1] = '\0';
}

The above code is another example of vulnerability caused by integer variables. To attack it, a len = 0xFFFFFFFF can be provided, so that malloc(len + 2) will overflow the unsigned 32-bit integer and give a result of malloc(1), with that, the memcpy(buf, data, len) below will try to copy a maximum of 0xFFFFFFFF bytes to a memory space of 1 byte, thus causing an overflow on the heap.

To fix these kinds of vulnerabilities related to integer, a straightforward way would be carefully adding bound checks before making use of those variables.

Format string vulnerabilities

Main character: printf function

To show how format string in printf function might cause trouble, we should first recall how printf works:

• int printf(const char *format, ...) is the declaration of printf

• printf takes a flexible amount of input, depends on the format parameter it passes in

• Each format symbol in the format string(such as %d, %c …) corresponds to one following parameter

Here’s an example of how printf is used normally

void func(void) {
  int secret = 42;
  printf("%d\n", 123);
}

The corresponding stack for this function will be

However, what if we delete the 123 in printf function call?

void func(void) {   
  int secret = 42;   
  printf("%d\n"); 
}

The stack would then look like this

As there’s a %d in the formatted string passed to printf function, it will assume that there’s an integer passed for it. But since there isn’t such an integer on the stack, the function will instead get the “secret” variable which is stored as the local variable on the stack of func. In this way, attacker can get the memory stack outside of printf function to be printed!

A typical way to trigger such vulnerability is to blindly pass whatever user input as the first parameter for printf function,

char buf[64];

void vulnerable(void) {
  if(fgets(buf, 64, stdin) == NULL) return;
  printf(buf);
}

Attacker can input strings like “%s %d %s” to attack the program above. Also note that inputs like “100% done!” will also work here as an attack, since “% d” = “%d” in the eyes of compiler when it triggers format symbol.

Another interesting thing to keep in mind is that “%n” in format string will write the number of characters that has been written so far into the address corresponding to this “%n”! That’s saying %n is also an important feature to attack printf since it enables attacker to write into memory.

Heap vulnerabilities

Main ideas:

• Targeting instruction pointers

• Overwrite a pointer that will eventually be jumped to

• Yes, we’ve seen similar ideas in stack smashing, but this heap vulnerability can be applied to function pointers

I’m not gonna go to details in this part, since the attacking strategies for heap vulnerabilities are indeed to similar with those in stack smashing, they’re always about overflow and unbounded r/w.

Writing robust exploits

Believe it or not, exploits can be very brittle, that’s to say:

• A working exploit can depend on operating system, memory layout, time, etc.

• Each machine or program may require its own set of constants(“magic numbers”) to produce a working exploit

NOP sleds

Here’s a related technique for a robust exploit targeting memory vulnerabilities.

The motivation is that sometimes the attacker doesn’t know where exactly his/her malicious code will be loaded in the memory, so how to decide the address to overwrite RIP to ensure that malicious code can be executed?

The trick is that instead of writing only the malicious code, add a lot of “NOP” instructions before it in the memory, NOP stands for “no-operation”, is a supported feature in x86, it literally does nothing.

With those nop instructions, attacker can make the instruction pointer jump to the address that might be close to his/her malicious code, as long as the instruction pointer points to one of the nop before the malicious code, it will eventually slide to the malicious code after executing the following nop’s.

Calling such technique as “NOP sleds” is quite vivid isn’t it? ;)

So far, we’ve seen so many widespread and dangerous memory safety vulnerabilities(if you’re interested in real cases, check the slides provided by CS161, they mentioned those in each lecture), here’re some reasons of why do these vulnerabilities exist,

1. Programming languages aren’t designed well for security.

2. Programmers often aren’t security-aware.

3. Programmers write code without designing security in from the start.

4. Programmers are humans. Humans make mistakes.

Corresponding to these reasons, here’re some possible ways of defending those vulnerabilities,

1. Use safer programming languages.

2. Learn to write memory-safe code.

3. Use tools for analyzing and patching insecure code.

4. Add mitigations that make it harder to exploit common vulnerabilities.

These thoughts bring us to the materials in lecture 4 :)

Memory-safe languages

Why memory-safe languages?

• Memory-safe languages are designed to check bounds and prevent undefined memory accesses.

• By design, memory-safe languages are not vulnerable to memory safety vulnerabilities
  • Using a memory-safe language is the only way to stop 100% of memory safety vulnerabilities
• Examples: Jave, Python, C#, Go, Rust

Drawback of memory-safe languages: Performance!

• It’s quite straightforward to understand.

  • For C and C++: malloc usually runs in (amortized) constant time

  • For Java: With the garbage collector for memory safety, there’s a 10-100ms delay when it randomly cleans up the memory

Aside from the fact that there’re trade offs in performance when using memory-safe languages, the reason why languages like C and C++ are still popular is also sort of legacy reason. Big projects that started in early days with C and C++ are most likely to stick with that language in the future even though there could be alternatives(as a programmer, you know the reason why people hate transforming a huge project from one language to another).

Writing memory-safe code

There are certain things to keep in mind when writing code, which helps to avoid common mistakes related to memory safety.

• Defensive programming: Always add checks in your code just in case

  • Example: Always check a pointer is not null before dereferencing it, even if you’re sure the pointer is going to be valid

  • Relies on programmer discipline

• Use safe libraries

  • Use functions that check bounds

  • Example: Use fgets instead of gets

  • Example: Use strncpy or strlcpy instead of strcpy

  • Example: Use snprintf instead of sprintf

  • Relies on programmer discipline or tools that check your program

• Structure user input

  • Constrain how untrusted sources can interact with the system

  • Implement a reference monitor

  • Example: When asking a user to input their age, only allow digits (0–9) as inputs

• Reason carefully about your code

  • When writing code, define a set of preconditions, postconditions, and invariants that must be satisfied for the code to be memory-safe

  • Very tedious and rarely used in practice, so it’s out of scope for this class

Building secure software

Approaches for building secure software/systems

I’ll just copy what’s on the slides

• Run-time checks

  • Automatic bounds-checking

  • May involve performance overhead

  • Crash if the check fails(it’s always better to stop by crashing instead of letting the attack to keep on execution)

• Monitor code for run-time misbehavior

  • Example: Look for illegal calling sequences

  • Example: Your code never calls execve, but you notice that your code is executing execve

  • Probably too late by the time you detect it ;)

• Contain potential damage

  • Example: Run system components in sandboxes or virtual machines (VMs)

  • Think about privilege separation

• Bug-finding tools

  • Excellent resource, as long as there aren’t too many false bugs

  • Too many false bugs = wasted programmer time

• Code review

  • Hiring someone to look over your code for memory safety errors

  • Can be very effective… but also expensive

• Vulnerability scanning
  • Probe your systems for known flaws
• Penetration testing (“pen-testing”)

  • Pay someone to break into your system

  • Take notes on how they did it

• What makes testing a program for security problems difficult?

  • We’re testing for the absence of vulnerabilities

  • Normal inputs rarely reveal security vulnerabilities

• How can we test programs for memory safety vulnerabilities?

  • Fuzz testing: Random inputs

  • Use tools like Valgrind (tool for detecting memory leaks)

  • Test corner cases

• How do we tell if we’ve found a problem?
  • Look for a crash or other unexpected behavior
• How do we know that we’ve tested enough?
  • Hard to know, but code-coverage tools can help
• Modern software often imports lots of different libraries

  • Libraries are often updated with security patches

  • It’s not enough to keep your own code secure: You also need to keep libraries updated with the latest security patches!

• What’s hard about patching?

  • Can require restarting production systems

  • Can break crucial functionality

  • Management burden (the “patch treadmill” never stops)

Exploit mitigations

What is exploit mitigation?

• Compiler and runtime defenses that make common exploits harder

• Mitigations involve a large back-and-forth arms race :)

  • Security researchers find a new mitigation to make an exploit harder

  • Attackers find a way to defeat the mitigation

  • …

• Mitigations make attacks harder, but not impossible
  • Remember that the only way to prevent all buffer overflow attacks is to use a memory-safe language

To start exploit mitigation, recall how an attack is put together:

1. Find a memory safety vulnerability

2. Write malicious shellcode at a known memory address

3. Overwrite the RIP with the address of the shellcode

4. Return from the function(To jump to the malicious shellcode)

5. Begin execution malicious shellcode

The key idea of exploit mitigation is to make the above steps difficult for the attackers.

Non-executable pages

• Idea: Most programs don’t need memory that is both written to and executed, so make portions of memory either executable or writable but not both

  • Stack, heap, and static data: Writable but not executable

  • Code: Executable but not writable

• Page table entries have a writable bit and an executable bit that can be set to achieve this behavior
  • Implemented in hardware, so effectively 0 overhead!
• Also known as

  • W^X (write XOR execute)

  • DEP (Data Execution Prevention, name used by Windows)

  • No-execute bit (the name of the bit itself)

How might it be attacked?

• Remember that you have library codes that are almost capable of doing anything!(And they have to be executable in memory right? ;) )

  1. Return-to-libc: An exploit technique that overwrites the RIP to jump to a functions in the standard C library (libc) or a common operating system function

  2. Return-oriented programming(ROP): Constructing custom shellcode using pieces of code that already exist in memory

Return-to-libc

• Imagine you’re the attacker who wants to execute command "rm -rf /"

• You want to make use of a function called “system” in the library, which executes a shell command like system("rm -rf /");

• The trick is to overwrite the return address(RIP, which you know should be the memory space 4 addresses higher than EBP during execution) with the address of this system code in library under the help of the memory vulnerability you found(say, buffer overflow).

• For example, you make use of the vulnerability in overflowing gets.

• After you overflowed the stack, it will look like graph below, and the moment this vulnerable returns will be the time when system is executed with "rm -rf /" as parameter.

ROP(Return-Oriented Programming)

• In return-to-libc above, attackers can only make use of the library functions.

• What if they want to customize their attacks?

• They can jump to instead of the beginning of library function, the middle of them.

• They can chain the chunks of functions in library that they need by ROP technique.

• First we’ll introduce gadget:

  • Gadget is a small set of assembly instructions that already exist in memory

  • Gadgets usually end in a ret instruction

  • Gadgets are usually not full instructions

• ROP strategy:

  • Write a chain of return addresses starting at the RIP to achieve the behavior we want

  • Each return address points to a gadget

  • The gadget executes its instructions and ends with a ret instruction

  • The ret instruction jumps to the address of the next gadget on the stack

• ROP example:
  • Say that we want to execute the following two lines of assembly instructions

    • movl $1, %eax

    • xorl %eax, %ebx

  • Suppose we know that the following snippets are in the memory

• ROP example(continued):

  • We then want to chain bar+25 with foo+10 to achieve the attack

  • Still consider the vulnerability we found in gets function

• ROP example(continued):
  • The following is how the stack looks like when attack is being performed

• A large code base is very likely to have imported plenty of library codes that provide enough gadgets for attackers to build their shellcode.

• There’re also tools called ROP compilers(e.g. https://github.com/Speedi13/ROP-COMPILER) that can automatically generate a ROP chain for attackers based on a target binary and desired malicious code.

• ROP was once a high-tech attack, and now it is easy and commonplace.

With return-to-libc and ROP, we can conclude that non-executable pages is not that efficient to stop attackers.

Stack canaries

Why canary:

• When coal miners are about to enter a mine, they’re not sure whether there’s toxic gas.

• They put a canary inside the mine, and figure out whether there’s toxic gas by whether the canary passes out.

• The same idea applies to stack canaries, where a “canary” is place on the stack for the program to keep track of, once it’s modified, the program shall crash since that implies an attack is going on.

How to do that:

• When the program runs, generate a random secret value and save it in the canary storage.

• In the function prologue, place the canary value on the stack right below the SFP/RIP.

• In the function epilogue, check the value on the stack and compare it with the stored canary value, to see whether there’s an attack going on.

One thing to note is that a canary value will have a NULL byte as beginning, since recall that in format string vulnerability, attacker can print the stack by adding %s in the format string he/she gives to printf, while this NULL byte in the head of canary value can then stop the printing process immediately.

Overall, the overhead of such stack canary is not that significant for programs.

How can attackers attack this?

1. Leak the value of the canary: Overwrite the canary with itself.

2. Bypass the value of the canary: Use a random write, not a sequential write.

3. Guess the value of the canary: Brute-force.

Pointer authentication

Reminder: 32-bit and 64-bit processors have different capacity of memory address

• 32-bit processor: integers and pointers are 32 bits long
  • Can address 232 bytes ≈ 4 GB of memory
• 64-bit processor: integers and pointers are 64 bits long

  • Can address 264 bytes ≈ 18 exabytes ≈ 18 billion GB of memory

  • No modern computer can support this much memory

  • Even the best most modern computers only need 242 bytes ≈ 4 terabytes ≈ 4000 GB of memory

  • At most 42 bits are needed to address all of memory

  • 22 bits are left unused (the top 22 bits in the address are always 0)

With those 👆 in mind, we can make use of those redundant 22 bits as authentication when accessing memories. The idea is similar with the stack canary, but the place to store the secret value is instead on the redundant bits in memory pointer!

How to do:

• It’s straightforward, just replace the unused bits in memory pointer with a pointer authentication code(PAC).

• Each time before using the pointer in memory, check if the PAC is valid.

• These PAC can be written to the RIP, SFP, any other pointers on the stack, and any other pointers outside of the stack (e.g. on the heap).

• Each possible address will have its own PAC.

• PAC is kept in CPU instead of on the memory, so only the one who knows CPU’s master secret can generate PAC.

What may attackers do?

1. Find a vulnerability to trick the program to generating a PAC for any address

2. Learn the master secret

   • The operating system has to set up the secrets: What if there is a vulnerability in the OS?

   • Workaround: Embed the master secret in the CPU, which can only be used to generate PACs, never read directly

3. Guess a PAC: Brute-force

   • Most 64-bit systems use 48 bits for addressing, so there are only 22 bits left for the PAC

   • 222 bits ≈ 4 million possibilities, so possibly feasible depending on your threat model

4. Pointer reuse
   • If the CPU already generated another PAC for another pointer, we can copy that pointer and use it elsewhere

BTW, pointer authentication is supported by ARM 8.3, Apple M1 chip takes advantage of such feature(not implemented in x86).

Address space layout randomization(ASLR)

Try to understand the main idea from the graphs below:

• Address space layout randomization (ASLR): Put each segment of memory in a different location each time the program is run
  • The attacker can’t know where their shellcode will be because its address changes every time you run the program
• ASLR can shuffle all four segments of memory

  • Randomize the stack: Can’t place shellcode on the stack without knowing the address of the stack

  • Randomize the heap: Can’t place shellcode on the heap without knowing the address of the heap

  • Randomize the code: Can’t construct a ROP chain or return-to-libc attack without knowing the address of code

  • Within each segment of memory, relative addresses are the same (e.g. the RIP is always 4 bytes above the SFP)

ASLR has effectively no overhead, since we have to do relocation anyway!

What might the attackers do?

• Leak the address of a pointer, whose address relative to your shellcode is known

  • Relative addresses are usually fixed, so this is sufficient to undo randomization!

  • Leak a stack pointer: Leak the location of the stack

  • Leak an RIP: Leak the location of the caller

• Guess the address of your shellcode: Brute-force

  • Randomization usually happens on page boundaries (usually 12 bits for 4 KiB pages)

  • 32-bit: 32 - 12 = 20 bits, 220 possible pages, which is feasibly brute-forced

  • 64-bit (usually 48-bit addressing): 48 - 12 = 36 bits, 236 possible pages

Combining mitigations

• Example: Combining ASLR and non-executable pages

  • An attacker can’t write their own shellcode, because of non-executable pages

  • An attacker can’t use existing code in memory, because they don’t know the addresses of those code (ASLR)

• To defeat ASLR and non-executable pages, the attacker needs to find two vulnerabilities

  • First, find a way to leak memory and reveal the address randomization (defeat ASLR)

  • Second, find a way to write to memory and write a ROP chain (defeat non-executable pages)

Should we enable mitigations?

• Many mitigations (stack canaries, non-executable pages, ASLR) are effectively free today (insignificant performance impact)

• The programmer sometimes has to manually enable mitigations

  • Example: Enable ASLR and non-executable pages when running a program

  • Example: Setting a flag to compile a program with stack canaries

• If the default is disabling the mitigation, the default will be chosen

  • Recall: Consider human factors!

  • Recall: Use fail-safe defaults!