KAIST - CS230

Machine-Level Programming V:
Advanced
Spring, 2023

class11.ppt Introduction to Computer Systems, CMU (Authors’) CS 230 S ‘23

Today
Memory Layout
Buffer Overflow
 Vulnerability
 Protection
x86-64 Linux Memory Layout
not drawn to scale

00007FFFFFFFFFFF
Shared
Stack (= 247–1)
Libraries
00007FFFF0000000
 Runtime stack (8MB limit) Stack
 E. g., local variables 8MB

Heap
 Dynamically allocated as needed
 When call malloc(), calloc(), new()

Data
 Statically allocated data
 E.g., global vars, static vars, string constants

Text / Shared Libraries Heap

 Executable machine instructions
Data
 Read-only Text
Hex Address 400000
000000
not drawn to scale
Memory Allocation00007FFFFFFFFFFF
Example
Shared
char big_array[1L<<24]; /* 16 MB */ Libraries
char huge_array[1L<<31]; /* 2 GB */ Stack

int global = 0;

int useless() { return 0; }

int main ()
{
void *phuge1, *psmall2, *phuge3, *psmall4;
int local = 0;
phuge1 = malloc(1L << 28); /* 256 MB */
psmall2 = malloc(1L << 8); /* 256 B */
phuge3 = malloc(1L << 32); /* 4 GB */
psmall4 = malloc(1L << 8); /* 256 B */ Heap
/* Some print statements ... */
} Data
Text
Where does everything go?
not drawn to scale
x86-64 Example Addresses Shared
address range ~247 Libraries
Stack

local 0x00007ffe4d3be87c
phuge1 0x00007f7262a1e010
phuge3 0x00007f7162a1d010
psmall4 0x000000008359d120 Heap
psmall2 0x000000008359d010
big_array 0x0000000080601060
huge_array 0x0000000000601060
main() 0x000000000040060c
useless() 0x0000000000400590

Heap

(Exact values can vary)

Data
Text
000000
Runaway Stack Example not drawn to scale

00007FFFFFFFFFFF
Shared
int recurse(int x) { Libraries
int a[1<<15]; // 4*2^15 = 128 KiB
Stack
printf("x = %d. a at %p\n", x, a);
a[0] = (1<<14)-1; 8MB
a[a[0]] = x-1;
if (a[a[0]] == 0)
return -1;
return recurse(a[a[0]]) - 1;
}

Functions store local data on ./runaway 67

in stack frame x = 67. a at 0x7ffd18aba930
x = 66. a at 0x7ffd18a9a920
x = 65. a at 0x7ffd18a7a910
Recursive functions cause x = 64. a at 0x7ffd18a5a900
. . .
deep nesting of frames x = 4. a at 0x7ffd182da540
x = 3. a at 0x7ffd182ba530
x = 2. a at 0x7ffd1829a520
Segmentation fault (core dumped)
Today
Memory Layout
Buffer Overflow
 Vulnerability
 Protection
Recall: Memory Referencing Bug
Example
typedef struct {
int a[2];
double d;
} struct_t;

double fun(int i) {
volatile struct_t s;
s.d = 3.14;
s.a[i] = 1073741824; /* Possibly out of bounds */
return s.d;
}

fun(0) -> 3.1400000000

fun(1) -> 3.1400000000
fun(2) -> 3.1399998665
fun(3) -> 2.0000006104
fun(6) -> Stack smashing detected
fun(8) -> Segmentation fault

 Result is system specific

Memory Referencing Bug Example
typedef struct { fun(0) -> 3.1400000000
int a[2]; fun(1) -> 3.1400000000
double d; fun(2) -> 3.1399998665
} struct_t;
fun(3) -> 2.0000006104
fun(4) -> Segmentation fault
fun(8) -> 3.1400000000

??? 8
Explanation: Critical State 7
Critical State 6
Critical State 5
Critical State 4
d7 ... d4 3 Location accessed by
fun(i)
d3 ... d0 2
struct_t
a[1] 1
a[0] 0
Such problems are a BIG deal
Generally called a “buffer overflow”
 when exceeding the memory size allocated for an array

Why a big deal?

 It’s the #1 technical cause of security vulnerabilities

Most common form

 Unchecked lengths on string inputs
 Particularly for bounded character arrays on the stack
 sometimes referred to as stack smashing
String Library Code
Implementation of Unix function gets()
/* Get string from stdin */
char *gets(char *dest)
{
int c = getchar();
char *p = dest;
while (c != EOF && c != '\n') {
*p++ = c;
c = getchar();
}
*p = '\0';
return dest;
}
 No way to specify limit on number of characters to read

Similar problems with other library functions

 strcpy, strcat: Copy strings of arbitrary length
 scanf, fscanf, sscanf, when given %s conversion
specification
Vulnerable Buffer Code
/* Echo Line */
void echo()
{
char buf[4]; /* Way too small! */  btw, how big
gets(buf); is big enough?
puts(buf);
}

void call_echo() {
echo();
}

unix>./bufdemo-nsp
Type a string:01234567890123456789012
01234567890123456789012

unix>./bufdemo-nsp
Type a string:012345678901234567890123
012345678901234567890123
Segmentation Fault
Buffer Overflow Disassembly
echo:
000000000040069c <echo>:
40069c: 48 83 ec 18 sub $0x18,%rsp
4006a0: 48 89 e7 mov %rsp,%rdi
4006a3: e8 a5 ff ff ff callq 40064d <gets@plt>
4006a8: 48 89 e7 mov %rsp,%rdi
4006ab: e8 50 fe ff ff callq 400500 <puts@plt>
4006b0: 48 83 c4 18 add $0x18,%rsp
4006b4: c3 retq

call_echo:
4006b5: 48 83 ec 08 sub $0x8,%rsp
4006b9: b8 00 00 00 00 mov $0x0,%eax
4006be: e8 d9 ff ff ff callq 40069c <echo>
4006c3: 48 83 c4 08 add $0x8,%rsp
4006c7: c3 retq
Buffer Overflow Disassembly
echo:
000000000040069c <echo>:
40069c: 48 83 ec 18 sub $0x18,%rsp
4006a0: 48 89 e7 mov %rsp,%rdi
4006a3: e8 a5 ff ff ff callq 40064d <gets@plt>
4006a8: 48 89 e7 mov %rsp,%rdi
4006ab: e8 50 fe ff ff callq 400500 <puts@plt>
4006b0: 48 83 c4 18 add $0x18,%rsp
4006b4: c3 retq

call_echo:
4006b5: 48 83 ec 08 sub $0x8,%rsp
4006b9: b8 00 00 00 00 mov $0x0,%eax
4006be: e8 d9 ff ff ff callq 40069c <echo>
4006c3: 48 83 c4 08 add $0x8,%rsp
4006c7: c3 retq
Buffer Overflow Stack Example
Before call to gets
Stack Frame
for call_echo

/* Echo Line */
Return Address void echo()
(8 bytes) {
char buf[4]; /* Way too small! */
gets(buf);
puts(buf);
20 bytes unused }

[3] [2] [1] [0] buf %rsp

echo:
subq $0x18, %rsp
movq %rsp, %rdi
call gets
. . .
Buffer Overflow Stack Example
Before call to gets
void echo() echo:
Stack Frame { subq $0x18, %rsp
for call_echo char buf[4]; movq %rsp, %rdi
gets(buf); call gets
. . . . . .
00 00 Address
Return 00 00 }
00 (8
40bytes)
06 c3
call_echo:
. . .
20 bytes unused 4006be: callq 4006cf <echo>
4006c3: add $0x8,%rsp
. . .
[3] [2] [1] [0] buf %rsp
Buffer Overflow Stack Example #1
After call to gets
void echo() echo:
Stack Frame { subq $0x18, %rsp
for call_echo char buf[4]; movq %rsp, %rdi
gets(buf); call gets
. . . . . .
00 00 Address
Return 00 00 }
00 (8
40bytes)
06 c3
00 32 31 30 call_echo:
39 38 37 36 . . .
35 34 unused
20 bytes 33 32 4006be: callq 4006cf <echo>
31 30 39 38 4006c3: add $0x8,%rsp
37 36 35 34 . . .
33 32 31 30 buf %rsp
unix>./bufdemo-nsp
Type a string:01234567890123456789012
01234567890123456789012

“01234567890123456789012\0”
Overflowed buffer, but did not corrupt state
Buffer Overflow Stack Example #2
After call to gets
void echo() echo:
Stack Frame { subq $0x18, %rsp
for call_echo char buf[4]; movq %rsp, %rdi
gets(buf); call gets
. . . . . .
00 00 Address
Return 00 00 }
00 (8
40bytes)
06 00
33 32 31 30 call_echo:
39 38 37 36 . . .
35 34 unused
20 bytes 33 32 4006be: callq 4006cf <echo>
31 30 39 38 4006c3: add $0x8,%rsp
37 36 35 34 . . .
33 32 31 30 buf %rsp
unix>./bufdemo-nsp
Type a string:012345678901234567890123
012345678901234567890123
Segmentation fault

Program “returned” to 0x0400600, and then crashed.

Stack Smashing Attacks
void P(){ Stack after call to gets()
Q(); return
... address
} A P stack frame
int Q() {
char buf[64]; AB
S
gets(buf);
...
return ...; data written
} by gets() pad
Q stack frame
void S(){
/* Something
unexpected */
...
}
Overwrite normal return address A with address of some other
code S
When Q executes ret, will jump to other code
Crafting Smashing String
int echo() {
Stack Frame char buf[4];
for call_echo gets(buf);
...
return ...;
00 07 00
FF
00 Address
Return 00 }
00 40
FF (8 06
AB c3
FFbytes) 80 %rsp Target Code
33 32 31 30
void smash() {
39 38 37 36
printf("I've been smashed!\n");
35 34 unused
20 bytes 33 32 exit(0);
24 bytes
31 30 39 38 }
37 36 35 34
33 32 31 30 00000000004006c8 <smash>:
4006c8: 48 83 ec 08
Attack String (Hex)
30 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 30 31 32 33
c8 06 40 00 00 00 00 00
Smashing String Effect
Stack Frame
for call_echo

00 07 00
FF
00 Address
Return 00
00 40
FF (8 06
AB c8
FFbytes) 80 %rsp Target Code
33 32 31 30
void smash() {
39 38 37 36
printf("I've been smashed!\n");
35 34 unused
20 bytes 33 32 exit(0);
31 30 39 38 }
37 36 35 34
33 32 31 30 00000000004006c8 <smash>:
4006c8: 48 83 ec 08
Attack String (Hex)
30 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 30 31 32 33
c8 06 40 00 00 00 00 00
Performing Stack Smash
linux> cat smash-hex.txt
30 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 30 31 32 33 c8 06 40 00 00 00 00 00
linux> cat smash-hex.txt | ./hexify | ./bufdemo-nsp
Type a string:012345678901234567890123?@
I've been smashed!

Put hex sequence in file smash-hex.txt

Use hexify program to convert hex digits to
characters
 Some of them are non-printing

Provide as input to vulnerable program

void smash() {
printf("I've been smashed!\n");
exit(0);
}

30 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 30 31 32 33
c8 06 40 00 00 00 00 00
Code Injection Attacks
Stack after call to gets()

void P(){
P stack frame
Q(); return
... address
} A BB
A

int Q() { data written pad

char buf[64]; by gets()
gets(buf);
... exploit Q stack frame
return ...; code
B
}

Input string contains byte representation of executable code

Overwrite return address A with address of buffer B
When Q executes ret, will jump to exploit code
How Does The Attack Code
Execute?
rip Stack

rsp
…
void P(){ rsp
Q(); BB
A
rsp
...
} pad

rip
ret ret exploit
int Q() { Shared code
rip
char buf[64]; Libraries
gets(buf); // A->B
...
return ...;
} Heap
Data
rip
rip Text
What To Do About Buffer Overflow Attacks
Avoid overflow vulnerabilities

Employ system-level protections

Have compiler use “stack canaries”

Lets talk about each…

1. Avoid Overflow Vulnerabilities in
Code (!)
/* Echo Line */
void echo()
{
char buf[4];
fgets(buf, 4, stdin);
puts(buf);
}

For example, use library routines that limit string

lengths
 fgets instead of gets
 strncpy instead of strcpy
 Don’t use scanf with %s conversion specification
 Use fgets to read the string
 Or use %ns where n is a suitable integer
2. System-Level Protections can
help
Randomized stack offsets Stack base

 At start of program, allocate

random amount of space on
Random
stack allocation
 Shifts stack addresses for
entire program
main
 Makes it difficult for hacker
to predict beginning of Application
inserted code Code
 E.g.: 5 executions of
memory allocation code B?
pad
 Stack repositioned each exploit
time program executes code
B?
2. System-Level Protections can
help Stack after call to gets()
Nonexecutable code
segments
P stack frame
 In traditional x86, can
mark region of memory
as either “read-only” or B
“writeable”
 Can execute anything data written pad
readable by gets()
 x86-64 added explicit exploit Q stack frame
“execute” permission code
B
 Stack marked as non-
executable

Any attempt to execute this code will fail

3. Stack Canaries can help
Idea
 Place special value (“canary”) on stack just beyond buffer
 Check for corruption before exiting function

GCC Implementation
 -fstack-protector
 Now the default (disabled earlier)
unix>./bufdemo-sp
Type a string:0123456
0123456

unix>./bufdemo-sp
Type a string:012345678
*** stack smashing detected ***
Protected Buffer Disassembly
echo:
Aside: %fs:0x28
40072f: sub $0x18,%rsp • Read from memory using
400733: mov %fs:0x28,%rax
40073c: mov %rax,0x8(%rsp) segmented addressing
400741: xor %eax,%eax • Segment is read-only
400743: mov %rsp,%rdi • Value generated randomly
400746: callq 4006e0 <gets@plt> every time program runs
40074b: mov %rsp,%rdi
40074e: callq 400570 <puts@plt>
400753: mov 0x8(%rsp),%rax
400758: xor %fs:0x28,%rax
400761: je 400768 <echo+0x39>
400763: callq 400580 <__stack_chk_fail@plt>
400768: add $0x18,%rsp
40076c: retq
Setting Up Canary
Before call to gets
/* Echo Line */
Stack Frame void echo()
for call_echo {
char buf[4]; /* Way too small! */
gets(buf);
Return Address puts(buf);
(8 bytes) }

20 bytes unused
Canary
(8 bytes)

[3] [2] [1] [0] buf %rsp

echo:
. . .
mov %fs:0x28, %rax # Get canary
mov %rax, 0x8(%rsp) # Place on stack
xor %eax, %eax # Erase register
. . .
Checking Canary
After call to gets
/* Echo Line */
void echo()
Stack Frame {
for main char buf[4]; /* Way too small! */
gets(buf);
Return Address puts(buf);
Return Address
(8 bytes) }
Saved %ebp
Saved %ebx
Some systems:
20 bytes unused
Canary LSB of canary is 0x00
Input: 0123456
(8Canary
bytes) Allows input 01234567
[3]
00 [2]
36 [1]
35 [0]
34
33 32 31 30 buf %rsp
echo:
. . .
mov 0x8(%rsp),%rax # Retrieve from stack
xor %fs:0x28,%rax # Compare to canary
je .L6 # If same, OK
call __stack_chk_fail # FAIL
Summary
Memory Layout
Buffer Overflow
 Vulnerability
 Protection
 Code Injection Attack