Carnegie Mellon
Machine-Level Programming V: Advanced Topics
15-213/18-213/15-513: Introduction to Computer Systems 9th Lecture, June 5, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
Carnegie Mellon
Today
Memory Layout
Buffer Overflow ▪ Vulnerability
▪ Protection Unions
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2
Carnegie Mellon
x86-64 Linux Memory Layout
not drawn to scale
Shared Libraries
Stack
Heap
Data
Text
Stack
▪ Runtime stack (8MB limit) ▪ e.g., local variables
00007FFFFFFFFFFF
(= 247–1)
00007FFFF0000000
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
▪ Executable machine instructions ▪ Read-only
Hex Address Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
400000
000000
3
8MB
Carnegie Mellon
Memory Allocation Example
not drawn to scale
00007FFFFFFFFFFF
Shared Libraries
Stack
Heap
Data
Text
char big_array[1L<<24]; /* 16 MB */
char huge_array[1L<<31]; /* 2 GB */
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 */
/* Some print statements ... */
}
Where does everything go?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4
Carnegie Mellon
x86-64 Example Addresses
address range ~247
not drawn to scale
Shared Libraries
Stack
Heap
Heap
Data
Text
local phuge1 phuge3 psmall4 psmall2 big_array huge_array main() useless()
0x00007ffe4d3be87c
0x00007f7262a1e010
0x00007f7162a1d010
0x000000008359d120
0x000000008359d010
0x0000000080601060 0x0000000000601060
0x000000000040060c
0x0000000000400590
(Exact values can vary)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
000000
Carnegie Mellon
Runaway Stack Example
00007FFFFFFFFFFF
not drawn to scale
Shared Libraries
Stack
int recurse(int x) {
int a[1<<15]; // 4*2^15 = 128 KiB printf("x = %d. a at %p\n", x, a); a[0] = (1<<14)-1;
a[a[0]] = x-1;
if (a[a[0]] == 0)
return -1;
return recurse(a[a[0]]) - 1;
}
Functions store local data on in stack frame
Recursive functions cause deep nesting of frames
8MB
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
./runaway 67
x = 67. a at 0x7ffd18aba930 x = 66. a at 0x7ffd18a9a920 x = 65. a at 0x7ffd18a7a910 x = 64. a at 0x7ffd18a5a900 ...
x = 4. a at 0x7ffd182da540
x = 3. a at 0x7ffd182ba530
x = 2. a at 0x7ffd1829a520 Segmentation fault (core dumped)
Carnegie Mellon
Today
Memory Layout
Buffer Overflow ▪ Vulnerability
▪ Protection Unions
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
Carnegie Mellon
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) -> fun(1) -> fun(2) -> fun(3) -> fun(6) -> fun(8) ->
3.1400000000 3.1400000000 3.1399998665 2.0000006104
Stack smashing detected Segmentation fault
▪ Result is system specific
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
8
Carnegie Mellon
Memory Referencing Bug Example
typedef struct {
int a[2];
double d;
} struct_t;
Explanation:
fun(0) ->
fun(1) ->
fun(2) ->
fun(3) ->
fun(4) ->
fun(8) ->
8
7
6
5
4
3
2
1
0
3.1400000000 3.1400000000 3.1399998665 2.0000006104 Segmentation fault 3.1400000000
???
Critical State
Critical State
Critical State
Critical State
d7 … d4
d3 … d0
a[1]
a[0]
struct_t
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
9
Location accessed by
fun(i)
Carnegie Mellon
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
▪ #1 overall cause is social engineering / user ignorance
Most common form
▪ Unchecked lengths on string inputs
▪ Particularly for bounded character arrays on the stack
▪ sometimes referred to as stack smashing
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
10
Carnegie Mellon
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 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11
Carnegie Mellon
Vulnerable Buffer Code
/* Echo Line */
void echo()
{
char buf[4]; /* Way too small! */ gets(buf);
puts(buf);
}
void call_echo() {
echo();
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12
unix>./bufdemo-nsp
Type a string:01234567890123456789012 01234567890123456789012
BTW, how big is big enough?
unix>./bufdemo-nsp
Type a string:012345678901234567890123 012345678901234567890123
Segmentation Fault
Carnegie Mellon
Buffer Overflow Disassembly echo:
000000000040069c
40069c: 48 4006a0: 48 4006a3: e8 4006a8: 48 4006ab: e8 4006b0: 48 4006b4: c3
83ec18 89 e7
a5 ff
89 e7
50 fe
83 c4
sub $0x18,%rsp
mov %rsp,%rdi
callq 40064d
callq 400500
retq
call_echo:
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
13
ff ff
ff ff 18
4006b5: 48 83 ec 08 4006b9: b8 00 00 00 00 4006be: e8 d9 ff ff ff 4006c3: 48 83 c4 08 4006c7: c3
sub $0x8,%rsp mov $0x0,%eax callq 40069c
Carnegie Mellon
Buffer Overflow Stack Example
Before call to gets
Stack Frame for call_echo
Return Address (8 bytes)
20 bytes unused
[3]
[2]
[1]
[0]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14
buf %rsp
/* Echo Line */ void echo()
{
char buf[4]; /* Way too small! */
gets(buf);
puts(buf);
}
echo:
subq $0x18, %rsp movq %rsp, %rdi call gets
…
Carnegie Mellon
Buffer Overflow Stack Example
Before call to gets
Stack Frame for call_echo
00 00 00 00
Return Address
00
(480byt0e6s)
c3
20 bytes unused
[3]
[2]
[1]
[0]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
void echo() {
char buf[4]; gets(buf); .. .
}
buf %rsp
call_echo:
echo:
subq $0x18, %rsp movq %rsp, %rdi call gets
…
…
4006be: callq 4006cf
Carnegie Mellon
Buffer Overflow Stack Example #1
After call to gets
void echo() {
char buf[4]; gets(buf); .. .
}
echo:
subq $0x18, %rsp movq %rsp, %rdi call gets
…
Stack Frame for call_echo
0R0etu0r0n A0dd0res0s0
00
(480byt0e6s)
c3
00
32
31
30
39
38
37
36
3250 b3yt4es u3n3use3d2
31
30
39
38
37
36
35
34
33
32
31
30
call_echo:
…
4006be: callq 4006cf
buf %rsp
unix>./bufdemo-nsp
Type a string:01234567890123456789012 01234567890123456789012
“01234567890123456789012\0”
Overflowed buffer, but did not corrupt state
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
Carnegie Mellon
Buffer Overflow Stack Example #2
After call to gets
Stack Frame for call_echo
00 00 00 00
Return Address
00
(480byt0e6s)
00
33
32
31
30
39
38
37
36
3250 b3yt4es u3n3use3d2
31
30
39
38
37
36
35
34
33
32
31
30
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
void echo() {
char buf[4]; gets(buf); .. .
}
call_echo:
buf %rsp
echo:
subq $0x18, %rsp movq %rsp, %rdi call gets
…
…
4006be: callq 4006cf
unix>./bufdemo-nsp
Type a string:012345678901234567890123 012345678901234567890123
Segmentation fault
Program “returned” to 0x0400600, and then crashed.
Carnegie Mellon
Stack Smashing Attacks
return address A
Stack after call to gets()
P stack frame
void P(){
Q();
…
}
A→S AB
pad
int Q() {
char buf[64];
gets(buf);
…
return …;
}
data written by gets()
Q stack frame
void S(){
/* Something
unexpected */
…
}
Overwrite normal return address A with address of some other code S WhenQexecutesret,willjumptoothercode
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
18
Carnegie Mellon
Crafting Smashing String
Stack Frame for call_echo
00 00 007 0F0F
Return Address
0F0F
(4F80Fbyt0Ae6Bs)
c830
33
32
31
30
39
38
37
36
3250 b3yt4es u3n3use3d2
31
30
39
38
37
36
35
34
33
32
31
30
Attack String (Hex)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
int echo() {
char buf[4];
gets(buf);
…
return …;
}
%rsp
24 bytes
Target Code
void smash() {
printf(“I’ve been smashed!\n”); exit(0);
}
00000000004006c8
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
Carnegie Mellon
Smashing String Effect
Stack Frame for call_echo
00 00 007 0F0F Return Address
0F0F
(4F80Fbyt0Ae6Bs)
c880
33
32
31
30
39
38
37
36
3250 b3yt4es u3n3use3d2
31
30
39
38
37
36
35
34
33
32
31
30
%rsp
Target Code
void smash() {
printf(“I’ve been smashed!\n”); exit(0);
}
Attack String (Hex)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
20
00000000004006c8
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
Carnegie Mellon
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
21
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
Carnegie Mellon
Code Injection Attacks
BA
AB
pad
exploit code
void P(){
Q();
…
}
return address A
Stack after call to gets()
P stack frame
int Q() {
char buf[64];
gets(buf);
…
return …;
}
data written by gets()
Q stack frame
B
Input string contains byte representation of executable code
Overwrite return address A with address of buffer B WhenQexecutesret,willjumptoexploitcode
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22
Carnegie Mellon
How Does The Attack Code Execute?
…
BA AB
pad
exploit code
Stack
Shared Libraries
Heap
Data
Text
rip
void P(){
Q();
… }
ret ret
rsp rsp rsp
rip rip
int Q() {
char buf[64]; gets(buf); // A->B …
return …;
}
rip rip
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23
Carnegie Mellon
What to Do About Buffer Overflow Attacks Avoid overflow vulnerabilities
Employ system-level protections
Have compiler use “stack canaries”
Lets talk about each…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
24
Carnegie Mellon
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
25
Carnegie Mellon
2. System-Level Protections Can Help
main
Application Code
B?
pad
exploit code
Randomized stack offsets
Stack base
Random allocation
▪ At start of program, allocate random amount of space on stack
▪ Shifts stack addresses for entire program
▪ Makes it difficult for hacker to predict beginning of inserted code
▪ e.g., 5 executions of memory allocation code
local
0x7ffe4d3be87c 0x7fff75a4f9fc 0x7ffeadb7c80c 0x7ffeaea2fdac 0x7ffcd452017c ▪ Stack repositioned each time
program executes
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
B?
26
Carnegie Mellon
2. System-Level Protections Can Help
Nonexecutable code segments
▪ In traditional x86, can mark region of memory as either “read-only” or “writeable”
Stack after call to gets()
P stack frame
B
pad
exploit code
▪ Can execute anything readable
▪ x86-64 added explicit “execute” permission
▪ Stack marked as non- executable
Any attempt to execute this code will fail
data written by gets()
B
Q stack frame
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
27
Carnegie Mellon
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 ***
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28
Carnegie Mellon
Protected Buffer Disassembly echo:
40072f: sub $0x18,%rsp
400733: mov %fs:0x28,%rax 40073c: mov %rax,0x8(%rsp) 400741: xor %eax,%eax 400743: mov %rsp,%rdi 400746: callq 4006e0
400758: xor
400761: je
400763: callq 400580 <__stack_chk_fail@plt> 400768: add $0x18,%rsp
40076c: retq
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
0x8(%rsp),%rax
%fs:0x28,%rax
400768
Aside: %fs:0x28
• Read from memory using
segmented addressing
• Segment is read-only
• Value generated randomly
every time program runs
Carnegie Mellon
Setting Up Canary
Before call to gets
/* Echo Line */
void echo()
{
char buf[4]; /* Way too small! */
gets(buf);
puts(buf);
}
Stack Frame for call_echo
Return Address (8 bytes)
20 bytes unused Canary
(8 bytes)
[3]
[2]
[1]
[0]
buf %rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30
echo: …
mov %fs:0x28, %rax # Get canary
mov %rax, 0x8(%rsp) # Place on stack xor %eax, %eax # Erase register …
Carnegie Mellon
Checking Canary
After call to gets
/* Echo Line */
void echo()
{
char buf[4]; /* Way too small! */
gets(buf);
puts(buf);
}
Stack Frame for main
Return Address
Return Address (8 bytes)
Saved %ebp Saved %ebx
20 bytes unused Canary
Canary (8 bytes)
[3] 00
[2] 36
[1] 35
[0] 34
33
32
31
30
Input: 0123456 buf %rsp
Some systems:
LSB of canary is 0x00 Allows input 01234567
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
echo: …
mov 0x8(%rsp),%rax
xor %fs:0x28,%rax
je .L6
call __stack_chk_fail # FAIL
# Retrieve from stack # Compare to canary
# If same, OK
Carnegie Mellon
Quiz Time!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32
Carnegie Mellon
Return-Oriented Programming Attacks
Challenge (for hackers)
▪ Stack randomization makes it hard to predict buffer location
▪ Marking stack nonexecutable makes it hard to insert binary code
Alternative Strategy ▪ Use existing code
▪ e.g., library code from stdlib
▪ String together fragments to achieve overall desired outcome ▪ Does not overcome stack canaries
Construct program from gadgets
▪ Sequence of instructions ending in ret
▪ Encoded by single byte 0xc3
▪ Code positions fixed from run to run ▪ Code is executable
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33
Carnegie Mellon
Gadget Example #1
long ab_plus_c
(long a, long b, long c)
{
return a*b + c;
}
00000000004004d0
4004d0: 48 0f af fe imul %rsi,%rdi
4004d4: lea (%rdi,%rdx,1),%rax 4004d8: retq
48 8d 04 17 c3
Use tail end of existing functions Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
34
raxrdi + rdx
Gadget address = 0x4004d4
Carnegie Mellon
Gadget Example #2
void setval(unsigned *p) {
*p = 3347663060u;
}
Encodes movq %rax, %rdi
4004d9: c7 07 d4 movl $0xc78948d4,(%rdi) 4004df: retq
48 89 c7
c3
Repurpose byte codes
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
35
rdi rax
Gadget address = 0x4004dc
Carnegie Mellon
ROP Execution
Stack
%rsp
Gadget n code
c3
Gadget 2 code
c3
Gadget 1 code
c3
Triggerwithretinstruction ▪ Will start executing Gadget 1
Final ret in each gadget will start next one
▪ ret: pop address from stack and jump to that address
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
36
Carnegie Mellon
Crafting an ROP Attack String Gadget #1
Stack Frame for call_echo
00 00 00 00
Return Address
00
(480byt0e4s)
dc
00 00 00 00
Return Address
00
(480byt0e4s)
d04
33
32
31
30
39
38
37
36
3250 b3yt4es u3n3use3d2
31
30
39
38
37
36
35
34
33
32
31
30
%rsp
▪ 0x4004d4 Gadget #2
▪ 0x4004dc
raxrdi + rdx rdirax
Attack String (Hex)
buf
Combination rdirdi + rdx
30 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 30 31 32 33 d4 04 40 00 00 00 00 00 dc 04 40 00 00 00 00 00
Multiple gadgets will corrupt stack upwards
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37
Carnegie Mellon
What Happens When echo Returns?
Stack Frame for call_echo
00 00 00 00
Return Address
00
(480byt0e4s)
dc
00 00 00 00 Return Address
00
(480byt0e4s)
d4
33
32
31
30
39
38
37
36
3250 b3yt4es u3n3use3d2
31
30
39
38
37
36
35
34
33
32
31
30
%rsp
1.
2.
3.
Echo executes ret ▪ Starts Gadget #1
Gadget #1 executes ret ▪ Starts Gadget #2
Gadget #2 executes ret ▪ Goesoffsomewhere…
buf
Multiple gadgets will corrupt stack upwards
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
38
Carnegie Mellon
Today
Memory Layout
Buffer Overflow ▪ Vulnerability
▪ Protection Unions
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
39
Carnegie Mellon
Union Allocation
Allocate according to largest element
Can only use one field at a time
sp+0 sp+4 sp+8 sp+16 sp+24
union U1 {
char c;
int i[2];
double v;
} *up;
c
i[0]
i[1]
v
up+0
up+4
up+8
struct S1 {
char c;
int i[2];
double v; } *sp;
c
3 bytes
i[0]
i[1]
4 bytes
v
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40
Carnegie Mellon
Using Union to Access Bit Patterns
Same as (float) u ? Same as (unsigned) f ? Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41
u
f
0
4
typedef union { float f;
unsigned u;
} bit_float_t;
float bit2float(unsigned u)
{
bit_float_t arg; arg.u = u; return arg.f;
}
unsigned float2bit(float f) {
bit_float_t arg;
arg.f = f;
return arg.u;
}
Carnegie Mellon
Byte Ordering Revisited
Idea
▪ Short/long/quad words stored in memory as 2/4/8 consecutive bytes
▪ Which byte is most (least) significant?
▪ Can cause problems when exchanging binary data between machines
Big Endian
▪ Most significant byte has lowest address ▪ Sparc, Internet
Little Endian
▪ Least significant byte has lowest address ▪ Intel x86, ARM Android and IOS
Bi Endian
▪ Can be configured either way ▪ ARM
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42
Carnegie Mellon
Byte Ordering Example
union {
unsigned char c[8]; unsigned short s[4]; unsigned int i[2]; unsigned long l[1];
} dw;
Memory addresses growing
32-bit
How are the bytes inside short/int/long stored?
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
s[0]
s[1]
s[2]
s[3]
i[0]
i[1]
l[0]
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
s[0]
s[1]
s[2]
s[3]
i[0]
i[1]
l[0]
64-bit
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43
Carnegie Mellon
Byte Ordering Example (Cont).
int j;
for (j = 0; j < 8; j++)
dw.c[j] = 0xf0 + j;
printf("Characters 0-7 == [0x%x,0x%x,0x%x,0x%x,0x%x,0x%x,0x%x,0x%x]\n",
dw.c[0], dw.c[1], dw.c[2], dw.c[3], dw.c[4], dw.c[5], dw.c[6], dw.c[7]);
printf("Shorts 0-3 == [0x%x,0x%x,0x%x,0x%x]\n", dw.s[0], dw.s[1], dw.s[2], dw.s[3]);
printf("Ints 0-1 == [0x%x,0x%x]\n", dw.i[0], dw.i[1]);
printf("Long 0 == [0x%lx]\n", dw.l[0]);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44
Carnegie Mellon
Byte Ordering on IA32 Little Endian
f0
f1
f2
f3
f4
f5
f6
f7
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
s[0]
s[1]
s[2]
s[3]
i[0]
i[1]
l[0]
Output:
LSB
MSB LSB MSB
Print
Characters 0-7 == [0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7] Shorts 0-3 == [0xf1f0,0xf3f2,0xf5f4,0xf7f6]
Ints 0-1 == [0xf3f2f1f0,0xf7f6f5f4]
Long 0 == [0xf3f2f1f0]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
Carnegie Mellon
Byte Ordering on x86-64 Little Endian
f0
f1
f2
f3
f4
f5
f6
f7
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
s[0]
s[1]
s[2]
s[3]
i[0]
i[1]
l[0]
LSB
Output on x86-64:
MSB
Characters 0-7 == [0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7] Shorts 0-3 == [0xf1f0,0xf3f2,0xf5f4,0xf7f6]
Ints 0-1 == [0xf3f2f1f0,0xf7f6f5f4]
Long 0 == [0xf7f6f5f4f3f2f1f0]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46
Print
Carnegie Mellon
Byte Ordering on Sun Big Endian
f0
f1
f2
f3
f4
f5
f6
f7
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
s[0]
s[1]
s[2]
s[3]
i[0]
i[1]
l[0]
MSB
Output on Sun:
LSB MSB LSB
Print
Characters 0-7 == [0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7] Shorts 0-3 == [0xf0f1,0xf2f3,0xf4f5,0xf6f7]
Ints 0-1 == [0xf0f1f2f3,0xf4f5f6f7]
Long 0 == [0xf0f1f2f3]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47
Carnegie Mellon
Summary of Compound Types in C
Arrays
▪ Contiguous allocation of memory
▪ Aligned to satisfy every element’s alignment requirement ▪ Pointer to first element
▪ No bounds checking
Structures
▪ Allocate bytes in order declared
▪ Pad in middle and at end to satisfy alignment
Unions
▪ Overlay declarations
▪ Way to circumvent type system
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
Carnegie Mellon
Summary
Memory Layout
Buffer Overflow ▪ Vulnerability
▪ Protection
▪ Code Injection Attack
▪ Return Oriented Programming
Unions
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
Carnegie Mellon
Exploits Based on Buffer Overflows
Buffer overflow bugs can allow remote machines to execute arbitrary code on victim machines
Distressingly common in real programs
▪ Programmers keep making the same mistakes
▪ Recent measures make these attacks much more difficult
Examples across the decades ▪ Original “Internet worm” (1988)
▪ “IM wars” (1999)
▪ Twilight hack on Wii (2000s) ▪ ... and many, many more
You will learn some of the tricks in attacklab
▪ Hopefully to convince you to never leave such holes in your programs!!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50
Carnegie Mellon
Example: the original Internet worm (1988) Exploited a few vulnerabilities to spread
▪ Early versions of the finger server (fingerd) used gets() to read the argument sent by the client:
▪ finger droh@cs.cmu.edu
▪ Worm attacked fingerd server by sending phony argument:
▪ finger “exploit-code padding new-return- address”
▪ exploit code: executed a root shell on the victim machine with a direct TCP connection to the attacker.
Once on a machine, scanned for other machines to attack ▪ invaded ~6000 computers in hours (10% of the Internet☺)
▪ see June 1989 article in Comm. of the ACM ▪ the young author of the worm was prosecuted... ▪ and CERT was formed... still homed at CMU
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
51
Carnegie Mellon
Example 2: IM War
July, 1999
▪ Microsoft launches MSN Messenger (instant messaging system).
▪ Messenger clients can access popular AOL Instant Messaging Service (AIM) servers
MSN server
MSN client
AIM server
AIM client
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52
AIM client
Carnegie Mellon
IM War (cont.)
August 1999
▪ Mysteriously, Messenger clients can no longer access AIM servers ▪ Microsoft and AOL begin the IM war:
▪ AOL changes server to disallow Messenger clients
▪ Microsoft makes changes to clients to defeat AOL changes ▪ At least 13 such skirmishes
▪ What was really happening?
▪ AOL had discovered a buffer overflow bug in their own AIM clients
▪ They exploited it to detect and block Microsoft: the exploit code returned a 4-byte signature (the bytes at some location in the AIM client) to server
▪ When Microsoft changed code to match signature, AOL changed signature location
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53
Carnegie Mellon
Date: Wed, 11 Aug 1999 11:30:57 -0700 (PDT) From: Phil Bucking
Mr. Smith,
I am writing you because I have discovered
might find interesting because you are an Internet security expert with experience in this area. I have also tried to contact AOL but received no response.
I am a developer who has been working on a revolutionary new instant messaging client that should be released later this year.
…
It appears that the AIM client has a buffer overrun bug. By itself this might not be the end of the world, as MS surely has had its share. But AOL is now *exploiting their own buffer overrun bug* to help in its efforts to block MS Instant Messenger.
….
Since you have significant credibility with the press I hope that you can use this information to help inform people that behind AOL’s friendly exterior they are nefariously compromising peoples’ security.
Sincerely,
Phil Bucking
Founder, Bucking Consulting philbucking@yahoo.com
It was later determined that this
email originated from within
Microsoft!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
54
in their own software!
something that I think you
Carnegie Mellon
Aside: Worms and Viruses
Worm: A program that
▪ Can run by itself
▪ Can propagate a fully working version of itself to other computers
Virus: Code that
▪ Adds itself to other programs ▪ Does not run independently
Both are (usually) designed to spread among computers and to wreak havoc
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
55