Machine-Level Programming IV: x86-64 Procedures, Data
Machine-Level Programming IV: x86-64 Procedures, Data
Machine-Level Programming IV: x86-64 Procedures, Data
1
Today
Procedures (x86-64)
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structures
Allocation
Access
2
x86-64 Integer Registers:
Usage Conventions
%rax Return value %r8 Argument #5
4
x86-64 Registers
Arguments passed to functions via registers
If more than 6 integral parameters, then pass rest on stack
These registers can be used as caller-saved as well
Other Registers
6 callee saved
2 caller saved
1 return value (also usable as caller saved)
1 special (stack pointer)
5
x86-64 Locals in the Red Zone
swap_a:
/* Swap, using local array */
movq (%rdi), %rax
void swap_a(long *xp, long *yp)
movq %rax, -24(%rsp)
{
movq (%rsi), %rax
volatile long loc[2];
movq %rax, -16(%rsp)
loc[0] = *xp;
movq -16(%rsp), %rax
loc[1] = *yp;
movq %rax, (%rdi)
*xp = loc[1];
movq -24(%rsp), %rax
*yp = loc[0];
movq %rax, (%rsi)
}
ret
7
Interesting Features of Stack Frame
Allocate entire frame at once
All stack accesses can be relative to %rsp
Do by decrementing stack pointer
Can delay allocation, since safe to temporarily use red zone
Simple deallocation
Increment stack pointer
No base/frame pointer needed
12
Today
Procedures (x86-64)
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structures
Allocation
Access
14
Structure Allocation
struct rec {
int a[3]; Memory Layout
int i; a i n
struct rec *n;
}; 0 12 16 20
Concept
Contiguously-allocated region of memory
Refer to members within structure by names
Members may be of different types
15
Structure Access
r r+12
struct rec {
int a[3];
int i; a in
struct rec *n;
}; 0 12 16 20
16
Generating Pointer to Structure Member
r r+idx*4
struct rec {
int a[3];
a i n
int i;
struct rec *n; 0 12 16 20
};
17
struct rec {
int a[3];
Following Linked List int i;
struct rec *n;
C Code };
void set_val
(struct rec *r, int val) a i n
{ 0 12 16 20
while (r) {
int i = r->i; Element i
r->a[i] = val;
r = r->n; Register Value
} %edx r
}
%ecx val
.L17: # loop:
movl 12(%edx), %eax # r->i
movl %ecx, (%edx,%eax,4) # r->a[i] = val
movl 16(%edx), %edx # r = r->n
testl %edx, %edx # Test r
jne .L17 # If != 0 goto loop
18
Today
Procedures (x86-64)
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structures
19
Basic Data Types
Integral
Stored & operated on in general (integer) registers
Signed vs. unsigned depends on instructions used
Intel ASMBytes C
byte b 1 [unsigned] char
word w 2 [unsigned] short
double word l 4 [unsigned] int
quad word q 8 [unsigned] long int (x86-64)
Floating Point
Stored & operated on in floating point registers
Intel ASMBytes C
Single s 4 float
Double l 8 double
Extended t 10/12/16 long double
20
Array Allocation
Basic Principle
T A[L];
Array of data type T and length L
Contiguously allocated region of L * sizeof(T) bytes
char string[12];
x x + 12
int val[5];
x x+4 x+8 x + 12 x + 16 x + 20
double a[3];
x x+8 x + 16 x + 24
char *p[3]; IA32
x x+4 x+8 x + 12
x86-64
x x+8 x + 16 x + 24
21
Array Access
Basic Principle
T A[L];
Array of data type T and length L
Identifier A can be used as a pointer to array element 0: Type T*
int val[5]; 1 5 2 1 3
x x+4 x+8 x + 12 x + 16 x + 20
zip_dig ut = { 7, 8, 7, 1, 2 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };
zip_dig ut; 7 8 7 1 2
16 20 24 28 32 36
zip_dig mit; 0 2 1 3 9
36 40 44 48 52 56
zip_dig ucb; 9 4 7 2 0
56 60 64 68 72 76
int get_digit
(zip_dig z, int dig)
{
return z[dig];
} Register %edx contains
starting address of array
IA32 Register %eax contains
# %edx = z array index
# %eax = dig Desired digit at
movl (%edx,%eax,4),%eax # z[dig] 4*%eax + %edx
Use memory reference
(%edx,%eax,4)
24
Array Loop Example (IA32)
void zincr(zip_dig z) {
int i;
for (i = 0; i < ZLEN; i++)
z[i]++;
}
# edx = z
movl $0, %eax # %eax = i
.L4: # loop:
addl $1, (%edx,%eax,4) # z[i]++
addl $1, %eax # i++
cmpl $5, %eax # i:5
jne .L4 # if !=, goto loop
25
Pointer Loop Example (IA32)
void zincr_v(zip_dig z) {
void zincr_p(zip_dig z) { void *vz = z;
int *zend = z+ZLEN; int i = 0;
do { do {
(*z)++; (*((int *) (vz+i)))++;
z++; i += ISIZE;
} while (z != zend); } while (i != ISIZE*ZLEN);
} }
# edx = z = vz
movl $0, %eax # i = 0
.L8: # loop:
addl $1, (%edx,%eax) # Increment vz+i
addl $4, %eax # i += 4
cmpl $20, %eax # Compare i:20
jne .L8 # if !=, goto loop
26
Nested Array Example
#define PCOUNT 4
zip_dig pgh[PCOUNT] =
{{1, 5, 2, 0, 6},
{1, 5, 2, 1, 3 },
{1, 5, 2, 1, 7 },
{1, 5, 2, 2, 1 }};
zip_dig
1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1
pgh[4];
int A[R][C];
A A A A A A
[0] • • • [0] [1] • • • [1] • • • [R-1] • • • [R-1]
[0] [C-1] [0] [C-1] [0] [C-1]
4*R*C Bytes
28
Nested Array Row Access
Row Vectors
A[i] is array of C elements
Each element of type T requires K bytes
Starting address A + i * (C * K)
int A[R][C];
A A A A A A
[0] • • • [0] • • • [i] • • • [i] • • • [R-1] • • • [R-1]
[0] [C-1] [0] [C-1] [0] [C-1]
A A+i*C*4 A+(R-1)*C*4
29
Nested Array Row Access Code
int *get_pgh_zip(int index) #define PCOUNT 4
{ zip_dig pgh[PCOUNT] =
return pgh[index]; {{1, 5, 2, 0, 6},
} {1, 5, 2, 1, 3 },
{1, 5, 2, 1, 7 },
{1, 5, 2, 2, 1 }};
# %eax = index
leal (%eax,%eax,4),%eax # 5 * index
leal pgh(,%eax,4),%eax # pgh + (20 * index)
Row Vector
pgh[index] is array of 5 int’s
Starting address pgh+20*index
IA32 Code
Computes and returns address
Compute as pgh + 4*(index+4*index)
30
Nested Array Row Access
Array Elements
A[i][j] is element of type T, which requires K bytes
Address A + i * (C * K) + j * K = A + (i * C + j)* K
int A[R][C];
A A A A A
[0] • • • [0] • • • • • • [i] • • • • • • [R-1] • • • [R-1]
[0] [C-1] [j] [0] [C-1]
A A+i*C*4 A+(R-1)*C*4
A+i*C*4+j*4
31
Nested Array Element Access Code
int get_pgh_digit
(int index, int dig)
{
return pgh[index][dig];
}
movl 8(%ebp), %eax # index
leal (%eax,%eax,4), %eax # 5*index
addl 12(%ebp), %eax # 5*index+dig
movl pgh(,%eax,4), %eax # offset 4*(5*index+dig)
Array Elements
pgh[index][dig] is int
Address: pgh + 20*index + 4*dig
= pgh + 4*(5*index + dig)
IA32 Code
Computes address pgh + 4*((index+4*index)+dig)
32
Multi-Level Array Example
zip_dig ut = { 7, 8, 7, 1, 2 };
Variable univ denotes
zip_dig mit = { 0, 2, 1, 3, 9 }; array of 3 elements
zip_dig ucb = { 9, 4, 7, 2, 0 }; Each element is a pointer
#define UCOUNT 3
4 bytes
int *univ[UCOUNT] = {mit, ut, ucb}; Each pointer points to array
of int’s
ut
7 8 7 1 2
univ
16 20 24 28 32 36
160 36 mit
0 2 1 3 9
164 16
168 56 ucb 36 40 44 48 52 56
9 4 7 2 0
56 60 64 68 72 76
33
Element Access in Multi-Level Array
int get_univ_digit
(int index, int dig)
{
return univ[index][dig];
}
Computation (IA32)
Element access Mem[Mem[univ+4*index]+4*dig]
Must do two memory reads
First get pointer to row array
Then access element within array
34
Array Element Accesses
Nested array Multi-level array
int get_pgh_digit int get_univ_digit
(int index, int dig) (int index, int dig)
{ {
return pgh[index][dig]; return univ[index][dig];
} }
Mem[pgh+20*index+4*dig] Mem[Mem[univ+4*index]+4*dig]
35
N X N Matrix Code #define N 16
typedef int fix_matrix[N][N];
/* Get element a[i][j] */
int fix_ele
Fixed dimensions (fix_matrix a, int i, int j)
Know value of N at {
compile time return a[i][j];
}
#define IDX(n, i, j) ((i)*(n)+(j))
Variable dimensions, /* Get element a[i][j] */
explicit indexing int vec_ele
Traditional way to (int n, int *a, int i, int j)
implement dynamic {
arrays return a[IDX(n,i,j)];
}
37
n X n Matrix Access
Array Elements
Address A + i * (C * K) + j * K
C = n, K = 4
38
Optimizing Fixed Array Access
a j-th column
#define N 16
typedef int fix_matrix[N][N];
39
Optimizing Fixed Array Access
Optimization /* Retrieve column j from array */
Compute ajp = &a[i][j] void fix_column
Initially = a + 4*j (fix_matrix a, int j, int *dest)
{
Increment by 4*N int i;
for (i = 0; i < N; i++)
Register Value
dest[i] = a[i][j];
%ecx ajp }
%ebx dest
%edx i
.L8: # loop:
movl (%ecx), %eax # Read *ajp
movl %eax, (%ebx,%edx,4) # Save in dest[i]
addl $1, %edx # i++
addl $64, %ecx # ajp += 4*N
cmpl $16, %edx # i:N
jne .L8 # if !=, goto loop
40
Optimizing Variable Array Access
Compute ajp = &a[i][j]
Initially = a + 4*j /* Retrieve column j from array */
Increment by 4*n void var_column
(int n, int a[n][n],
Register Value int j, int *dest)
{
%ecx ajp int i;
%edi dest for (i = 0; i < n; i++)
%edx i dest[i] = a[i][j];
}
%ebx 4*n
%esi n
.L18: # loop:
movl (%ecx), %eax # Read *ajp
movl %eax, (%edi,%edx,4) # Save in dest[i]
addl $1, %edx # i++
addl $ebx, %ecx # ajp += 4*n
cmpl $edx, %esi # n:i
jg .L18 # if >, goto loop
41
Summary
Procedures in x86-64
Stack frame is relative to stack pointer
Parameters passed in registers
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structures
Allocation
Access
42
Malicious Use of Buffer Overflow
Stack after call to gets()
void foo(){
foo stack frame
bar(); return
... address
} A B
void call_echo() {
echo();
}
unix>./bufdemo
Type a string:1234567
1234567
unix>./bufdemo
Type a string:12345678
Segmentation Fault
unix>./bufdemo
Type a string:123456789ABC
Segmentation Fault
44
Avoiding Overflow Vulnerability
/* Echo Line */
void echo()
{
char buf[4]; /* Way too small! */
fgets(buf, 4, stdin);
puts(buf);
}
45
System-Level Protections
Randomized stack offsets unix> gdb bufdemo
At start of program, allocate random amount (gdb) break echo
(gdb) run
(gdb) print /x $ebp
Nonexecutable code segments $2 = 0xffffbb08
In traditional x86, can mark region of memory
(gdb) run
as either “read-only” or “writeable” (gdb) print /x $ebp
Can execute anything readable $3 = 0xffffc6a8
X86-64 added explicit “execute” permission
46
Stack Canaries
Idea
Place special value (“canary”) on stack just beyond buffer
Check for corruption before exiting function
GCC Implementation
-fstack-protector
-fstack-protector-all
unix>./bufdemo-protected
Type a string:1234
1234
unix>./bufdemo-protected
Type a string:12345
*** stack smashing detected ***
47
Protected Buffer Disassembly echo:
804864d: 55 push %ebp
804864e: 89 e5 mov %esp,%ebp
8048650: 53 push %ebx
8048651: 83 ec 14 sub $0x14,%esp
8048654: 65 a1 14 00 00 00 mov %gs:0x14,%eax
804865a: 89 45 f8 mov %eax,0xfffffff8(%ebp)
804865d: 31 c0 xor %eax,%eax
804865f: 8d 5d f4 lea 0xfffffff4(%ebp),%ebx
8048662: 89 1c 24 mov %ebx,(%esp)
8048665: e8 77 ff ff ff call 80485e1 <gets>
804866a: 89 1c 24 mov %ebx,(%esp)
804866d: e8 ca fd ff ff call 804843c <puts@plt>
8048672: 8b 45 f8 mov 0xfffffff8(%ebp),%eax
8048675: 65 33 05 14 00 00 00 xor %gs:0x14,%eax
804867c: 74 05 je 8048683 <echo+0x36>
804867e: e8 a9 fd ff ff call 804842c <FAIL>
8048683: 83 c4 14 add $0x14,%esp
8048686: 5b pop %ebx
8048687: 5d pop %ebp
8048688: c3 ret
48
Setting Up Canary
Before call to gets /* Echo Line */
void echo()
Stack Frame {
for main char buf[4]; /* Way too small! */
gets(buf);
puts(buf);
Return Address }
Saved %ebp %ebp
Saved %ebx
Canary
[3] [2] [1] [0] buf
Stack Frame
echo:
for echo
. . .
movl %gs:20, %eax # Get canary
movl %eax, -8(%ebp) # Put on stack
xorl %eax, %eax # Erase canary
. . .
49
Checking Canary
Before call to gets /* Echo Line */
void echo()
Stack Frame {
for main char buf[4]; /* Way too small! */
gets(buf);
puts(buf);
Return Address }
Saved %ebp %ebp
Saved %ebx
Canary
[3] [2] [1] [0] buf
Stack Frame
echo:
for echo
. . .
movl -8(%ebp), %eax # Retrieve from stack
xorl %gs:20, %eax # Compare with Canary
je .L24 # Same: skip ahead
call __stack_chk_fail # ERROR
.L24:
. . .
50
Canary Example
Before call to gets Input 1234
Stack Frame Stack Frame
for main for main