Computer Systems Practice/Study Guide

Buffer overflow The next problem concerns the following C code, excerpted from Dr. Evil’s best-selling autobiography, “World Domination My Way”. He calls the program NukeJr, his baby nuclear bomb phase. /* * NukeJr - Dr. Evil’s baby nuke */ #include <stdio.h> int overflow(void); int one = 1; /* main - NukeJr’s main routine */ int main() { int val = overflow(); val += one; if (val != 15213) printf("Boom!\n"); else printf("Curses! You’ve defused NukeJr!\n"); _exit(0); /* syscall version of exit that doesn’t need %ebp */ } /* overflow - writes to stack buffer and returns 15213 */ int overflow() { char buf[4]; int val, i=0; while(scanf("%x", &val) != EOF) buf[i++] = (char)val; return 15213; } Page 2 of 7 Buffer overflow (cont) Here is the corresponding machine code for NukeJr when compiled and linked on a Linux/x86 machine: 00000000004005d6 <overflow>: 4005d6: 53 push %rbx 4005d7: 48 83 ec 20 sub $0x20,%rsp 4005db: bb 00 00 00 00 mov $0x0,%ebx 4005e0: eb 0e jmp 4005f0 <overflow+0x1a> 4005e2: 48 63 c3 movslq %ebx,%rax 4005e5: 8b 54 24 0c mov 0xc(%rsp),%edx 4005e9: 88 54 04 1c mov %dl,0x1c(%rsp,%rax,1) 4005ed: 8d 5b 01 lea 0x1(%rbx),%ebx 4005f0: 48 8d 74 24 0c lea 0xc(%rsp),%rsi 4005f5: bf d4 06 40 00 mov $0x4006d4,%edi 4005fa: b8 00 00 00 00 mov $0x0,%eax 4005ff: e8 ac fe ff ff callq 4004b0 <__isoc99_scanf@plt> 400604: 83 f8 ff cmp $0xffffffff,%eax 400607: 75 d9 jne 4005e2 <overflow+0xc> 400609: b8 6d 3b 00 00 mov $0x3b6d,%eax 40060e: 48 83 c4 20 add $0x20,%rsp 400612: 5b pop %rbx 400613: c3 retq 0000000000400614 <main>: 400614: 48 83 ec 08 sub $0x8,%rsp 400618: e8 b9 ff ff ff callq 4005d6 <overflow> 40061d: 03 05 25 0a 20 00 add 0x200a25(%rip),%eax # 601048 <one> 400623: 3d 6d 3b 00 00 cmp $0x3b6d,%eax 400628: 74 0c je 400636 <main+0x22> 40062a: bf d7 06 40 00 mov $0x4006d7,%edi 40062f: e8 5c fe ff ff callq 400490 <puts@plt> 400634: eb 0a jmp 400640 <main+0x2c> 400636: bf e0 06 40 00 mov $0x4006e0,%edi 40063b: e8 50 fe ff ff callq 400490 <puts@plt> 400640: bf 00 00 00 00 mov $0x0,%edi 400645: e8 76 fe ff ff callq 4004c0 <exit@plt> 40064a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) Page 3 of 7 Problem 1. (18 points): This problem uses the NukeJr program to test your understanding of the stack discipline and byte ordering. Here are some notes to help you work the problem: • Recall that Linux/x86 machines are Little Endian. • The scanf("%x", &val) function reads a whitespace-delimited sequence of characters from stdin that represents a hex integer, converts the sequence to a 32-bit int and assigns the result to val. The call to scanf returns either 1 (if it converted a sequence) or EOF (if no more sequences on stdin). For example, calling scanf three times on the input string "0 ff" would have the following result: – 1st call to scanf: val=0x0 and scanf returns 1. – 2nd call to scanf: val=0xff and scanf returns 1. – 3rd call to scanf: val=? and scanf returns EOF. A. (6 points) After the sub instruction at address 0x4005d7 in function overflow completes, the stack contains a number of objects which are shown in the table below. Determine the address of each object as a byte offset from buf[0]. Question part Stack object Address of stack object i return address &buf[0] + _______ ii stored (pushed) %rbx &buf[0] + _______ iii buf[2] &buf[0] + _______ buf[1] &buf[0] + 1 buf[0] &buf[0] + 0 B. (12 points) You will now design an input string that will defuse NukeJr by causing the call to overflow to return to address 0x400623 instead of 40061d. As described above, your input will consist of typed characters, which will be interpreted as hex integers. We will call these hex ints. Your hex ints will be separated from each other by spaces, and each in turn will be scanned by scanf and assigned to val. The next questions will refer to the hex ints in your solution input string. Please make your solution input string as short as it can possibly be. Note: Your solution can trash the contents of %rbx stored on the stack. Once you have designed your solution input, proceed! i. (2) How many hex ints (each separated by spaces) are in your solution input string? Remember your input string should be as short as possible to accomplish the described defusing “attack”. ii. (2) How many hex ints in your solution input string could be anything? In other words, how many of your hex ints could be changed without impacting the success of the defusing “attack” on the NukeJr program? We will call these filler hex ints. iii. (2) How many hex ints in your solution input string must be precisely correct for NukeJr to be defused? We will call these precise hex ints iv. (2) Which comes first in your solution input string, the filler hex ints or the precise hex ints? v. (4) Give the precise hex ints exactly as they would be included in your input string. To ensure proper grading: 1) don’t include a leading 0x, 2) include only a single space between consecutive hex ints, 3) use only uppercase letters in your hex, and 4) don’t include any leading 0’s in your hex ints. Page 4 of 7 This next problem will test your understanding of stack frames. It is based on the following recursive C function: long silly(long n, long *p) { long val, val2; if (n > 0) val2 = silly(n - 1, &val); else val = val2 = 0; *p = val + val2 * n; return val - val2; } This yields the following machine code: silly: pushq %rbp pushq %rbx xorl %eax, %eax xorl %ecx, %ecx movq %rsi, %rbp subq $24, %rsp testq %rdi, %rdi jg .L7 movq %rcx, 0(%rbp) addq $24, %rsp popq %rbx popq %rbp ret .L7: movq %rdi, %rbx leaq 8(%rsp), %rsi leaq -1(%rdi), %rdi call silly imulq %rax, %rbx movq 8(%rsp), %rdx leaq (%rbx,%rdx), %rcx subq %rax, %rdx movq %rdx, %rax movq %rcx, 0(%rbp) addq $24, %rsp popq %rbx popq %rbp ret Page 5 of 7 Problem 2. (8 points): A. i Is the variable val stored on the stack? ii If so, at what byte offset (relative to the value of %rsp at the point of the testq instruction) is it stored? iii If so, why is it necessary to store it on the stack? B. i Is the variable val2 stored on the stack? ii If so, at what byte offset (relative to the value of %rsp at the point of the testq instruction) is it stored? iii If so, why is it necessary to store it on the stack? C. What (if anything) is stored at 32(%rsp) at the point of the recursive call (i.e., the program has run to the point of the call)? D. What (if anything) is stored at 40(%rsp) at the point of the recursive call (i.e., the program has run to the point of the call)?? Page 6 of 7 The following series of problems concerns the following low-quality code. void foo(int x) { int a[3]; char buf[4]; a[0] = 0xF0F1F2F3; a[1] = x; gets(buf); printf("a[0] = 0x%x, a[1] = 0x%x, buf = %s\n", a[0], a[1], buf); } In a program containing this code, procedure foo has the following disassembled form on an x86-64 ma- chine: 0000000000400586 <foo>: 400586: 48 83 ec 18 sub $0x18,%rsp 40058a: c7 44 24 04 f3 f2 f1 movl $0xf0f1f2f3,0x4(%rsp) 400591: f0 400592: 89 7c 24 08 mov %edi,0x8(%rsp) 400596: 48 89 e7 mov %rsp,%rdi 400599: b8 00 00 00 00 mov $0x0,%eax 40059e: e8 bd fe ff ff callq 400460 <gets@plt> 4005a3: 8b 4c 24 08 mov 0x8(%rsp),%ecx 4005a7: 8b 54 24 04 mov 0x4(%rsp),%edx 4005ab: 49 89 e0 mov %rsp,%r8 4005ae: be 68 06 40 00 mov $0x400668,%esi 4005b3: bf 01 00 00 00 mov $0x1,%edi 4005b8: b8 00 00 00 00 mov $0x0,%eax 4005bd: e8 ae fe ff ff callq 400470 <__printf_chk@plt> 4005c2: 48 83 c4 18 add $0x18,%rsp 4005c6: c3 retq For the following questions, recall that: • gets is a standard C library routine. • x86-64 machines are little-endian. • C strings are null-terminated (i.e., terminated by a character with value 0x00). • Characters ‘0’ through ‘9’ have ASCII codes 0x30 through 0x39. Page 7 of 7 Problem 3. (11 points): Consider the case where procedure foo is called with argument x equal to 0xE3E2E1E0, and we type “123456789” in response to gets. A. (2 points)) Fill in the following table indicating where on the stack the following program values are located. Express these as decimal offsets (positive or negative) relative to register %rsp: Question Part Program Value Decimal Offset i a ii a[2] iii buf iv buf[3] B. (3 points) Fill in the following table indicating which program values are/are not corrupted by the response from gets, i.e., their values were altered by some action within the call to gets. Question Part Program Value Corrupted? (Y/N) i a[0] ii a[1] iii a[2] C. (6 points) What will the printf function print for the following: i a[0] (hexadecimal): ________________________ ii a[1] (hexadecimal): ________________________ iii buf (ASCII characters): ________________________ Page 8 of 7 Problem 4. (12 points): The following table gives the parameters for a number of different caches, where m is the number of physical address bits, C is the cache size (number of data bytes), B is the block size in bytes, and E is the number of lines per set. For each cache, determine the number of cache sets (S), tag bits (t), set index bits (s), and block offset bits (b). Cache m C B E S t s b 1. 32 512 8 4 2. 43 2048 4 128 3. 32 1024 8 1 4. 51 4096 8 64 5. 32 256 32 2 6. 64 65536 64 4 Page 9 of 7 Problem 5. (10 points): Consider the following 4-way set associative cache (E = 4). It has 4 sets(S = 4), and a block size of 4 bytes (B = 4). Addresses in the system are 8 bits wide. Memory accesses are to 1-byte words. The following diagram shows the contents of the cache. Set 0 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 - 0 - - - - 1 5 1 A4 F0 DA 74 2 A 1 16 A3 77 49 3 6 1 79 48 10 53 Set 1 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 1 1 0B ED 47 88 1 - 0 - - - - 2 C 0 33 67 25 02 3 - 0 - - - - Set 2 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 E 1 E8 55 6B BD 1 6 0 06 AA 59 14 2 C 1 BA 08 FF 21 3 - 0 - - - - Set 3 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 F 0 07 13 51 A4 1 3 1 26 1C B0 9B 2 - 0 - - - - 3 1 0 FC 7B 38 7D Please answer the following questions about this cache. A. What is the total size, in bytes, of this cache? B. Consider a read to the memory address 0x3C. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. C. Consider a read to the memory address 0xA1. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. D. Consider a read to the memory address 0x68. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. E. Consider a read to the memory address 0x7A. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. Page 10 of 7 Buffer overflow The next problem concerns the following C code, excerpted from Dr. Evil’s best-selling autobiography, “World Domination My Way”. He calls the program NukeJr, his baby nuclear bomb phase. /* * NukeJr - Dr. Evil’s baby nuke */ #include <stdio.h> int overflow(void); int one = 1; /* main - NukeJr’s main routine */ int main() { int val = overflow(); val += one; if (val != 15213) printf("Boom!\n"); else printf("Curses! You’ve defused NukeJr!\n"); _exit(0); /* syscall version of exit that doesn’t need %ebp */ } /* overflow - writes to stack buffer and returns 15213 */ int overflow() { char buf[4]; int val, i=0; while(scanf("%x", &val) != EOF) buf[i++] = (char)val; return 15213; } Page 2 of 7 Buffer overflow (cont) Here is the corresponding machine code for NukeJr when compiled and linked on a Linux/x86 machine: 00000000004005d6 <overflow>: 4005d6: 53 push %rbx 4005d7: 48 83 ec 20 sub $0x20,%rsp 4005db: bb 00 00 00 00 mov $0x0,%ebx 4005e0: eb 0e jmp 4005f0 <overflow+0x1a> 4005e2: 48 63 c3 movslq %ebx,%rax 4005e5: 8b 54 24 0c mov 0xc(%rsp),%edx 4005e9: 88 54 04 1c mov %dl,0x1c(%rsp,%rax,1) 4005ed: 8d 5b 01 lea 0x1(%rbx),%ebx 4005f0: 48 8d 74 24 0c lea 0xc(%rsp),%rsi 4005f5: bf d4 06 40 00 mov $0x4006d4,%edi 4005fa: b8 00 00 00 00 mov $0x0,%eax 4005ff: e8 ac fe ff ff callq 4004b0 <__isoc99_scanf@plt> 400604: 83 f8 ff cmp $0xffffffff,%eax 400607: 75 d9 jne 4005e2 <overflow+0xc> 400609: b8 6d 3b 00 00 mov $0x3b6d,%eax 40060e: 48 83 c4 20 add $0x20,%rsp 400612: 5b pop %rbx 400613: c3 retq 0000000000400614 <main>: 400614: 48 83 ec 08 sub $0x8,%rsp 400618: e8 b9 ff ff ff callq 4005d6 <overflow> 40061d: 03 05 25 0a 20 00 add 0x200a25(%rip),%eax # 601048 <one> 400623: 3d 6d 3b 00 00 cmp $0x3b6d,%eax 400628: 74 0c je 400636 <main+0x22> 40062a: bf d7 06 40 00 mov $0x4006d7,%edi 40062f: e8 5c fe ff ff callq 400490 <puts@plt> 400634: eb 0a jmp 400640 <main+0x2c> 400636: bf e0 06 40 00 mov $0x4006e0,%edi 40063b: e8 50 fe ff ff callq 400490 <puts@plt> 400640: bf 00 00 00 00 mov $0x0,%edi 400645: e8 76 fe ff ff callq 4004c0 <exit@plt> 40064a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) Page 3 of 7 Problem 1. (18 points): This problem uses the NukeJr program to test your understanding of the stack discipline and byte ordering. Here are some notes to help you work the problem: • Recall that Linux/x86 machines are Little Endian. • The scanf("%x", &val) function reads a whitespace-delimited sequence of characters from stdin that represents a hex integer, converts the sequence to a 32-bit int and assigns the result to val. The call to scanf returns either 1 (if it converted a sequence) or EOF (if no more sequences on stdin). For example, calling scanf three times on the input string "0 ff" would have the following result: – 1st call to scanf: val=0x0 and scanf returns 1. – 2nd call to scanf: val=0xff and scanf returns 1. – 3rd call to scanf: val=? and scanf returns EOF. A. (6 points) After the sub instruction at address 0x4005d7 in function overflow completes, the stack contains a number of objects which are shown in the table below. Determine the address of each object as a byte offset from buf[0]. Question part Stack object Address of stack object i return address &buf[0] + _______ ii stored (pushed) %rbx &buf[0] + _______ iii buf[2] &buf[0] + _______ buf[1] &buf[0] + 1 buf[0] &buf[0] + 0 B. (12 points) You will now design an input string that will defuse NukeJr by causing the call to overflow to return to address 0x400623 instead of 40061d. As described above, your input will consist of typed characters, which will be interpreted as hex integers. We will call these hex ints. Your hex ints will be separated from each other by spaces, and each in turn will be scanned by scanf and assigned to val. The next questions will refer to the hex ints in your solution input string. Please make your solution input string as short as it can possibly be. Note: Your solution can trash the contents of %rbx stored on the stack. Once you have designed your solution input, proceed! i. (2) How many hex ints (each separated by spaces) are in your solution input string? Remember your input string should be as short as possible to accomplish the described defusing “attack”. ii. (2) How many hex ints in your solution input string could be anything? In other words, how many of your hex ints could be changed without impacting the success of the defusing “attack” on the NukeJr program? We will call these filler hex ints. iii. (2) How many hex ints in your solution input string must be precisely correct for NukeJr to be defused? We will call these precise hex ints iv. (2) Which comes first in your solution input string, the filler hex ints or the precise hex ints? v. (4) Give the precise hex ints exactly as they would be included in your input string. To ensure proper grading: 1) don’t include a leading 0x, 2) include only a single space between consecutive hex ints, 3) use only uppercase letters in your hex, and 4) don’t include any leading 0’s in your hex ints. Page 4 of 7 This next problem will test your understanding of stack frames. It is based on the following recursive C function: long silly(long n, long *p) { long val, val2; if (n > 0) val2 = silly(n - 1, &val); else val = val2 = 0; *p = val + val2 * n; return val - val2; } This yields the following machine code: silly: pushq %rbp pushq %rbx xorl %eax, %eax xorl %ecx, %ecx movq %rsi, %rbp subq $24, %rsp testq %rdi, %rdi jg .L7 movq %rcx, 0(%rbp) addq $24, %rsp popq %rbx popq %rbp ret .L7: movq %rdi, %rbx leaq 8(%rsp), %rsi leaq -1(%rdi), %rdi call silly imulq %rax, %rbx movq 8(%rsp), %rdx leaq (%rbx,%rdx), %rcx subq %rax, %rdx movq %rdx, %rax movq %rcx, 0(%rbp) addq $24, %rsp popq %rbx popq %rbp ret Page 5 of 7 Problem 2. (8 points): A. i Is the variable val stored on the stack? ii If so, at what byte offset (relative to the value of %rsp at the point of the testq instruction) is it stored? iii If so, why is it necessary to store it on the stack? B. i Is the variable val2 stored on the stack? ii If so, at what byte offset (relative to the value of %rsp at the point of the testq instruction) is it stored? iii If so, why is it necessary to store it on the stack? C. What (if anything) is stored at 32(%rsp) at the point of the recursive call (i.e., the program has run to the point of the call)? D. What (if anything) is stored at 40(%rsp) at the point of the recursive call (i.e., the program has run to the point of the call)?? Page 6 of 7 The following series of problems concerns the following low-quality code. void foo(int x) { int a[3]; char buf[4]; a[0] = 0xF0F1F2F3; a[1] = x; gets(buf); printf("a[0] = 0x%x, a[1] = 0x%x, buf = %s\n", a[0], a[1], buf); } In a program containing this code, procedure foo has the following disassembled form on an x86-64 ma- chine: 0000000000400586 <foo>: 400586: 48 83 ec 18 sub $0x18,%rsp 40058a: c7 44 24 04 f3 f2 f1 movl $0xf0f1f2f3,0x4(%rsp) 400591: f0 400592: 89 7c 24 08 mov %edi,0x8(%rsp) 400596: 48 89 e7 mov %rsp,%rdi 400599: b8 00 00 00 00 mov $0x0,%eax 40059e: e8 bd fe ff ff callq 400460 <gets@plt> 4005a3: 8b 4c 24 08 mov 0x8(%rsp),%ecx 4005a7: 8b 54 24 04 mov 0x4(%rsp),%edx 4005ab: 49 89 e0 mov %rsp,%r8 4005ae: be 68 06 40 00 mov $0x400668,%esi 4005b3: bf 01 00 00 00 mov $0x1,%edi 4005b8: b8 00 00 00 00 mov $0x0,%eax 4005bd: e8 ae fe ff ff callq 400470 <__printf_chk@plt> 4005c2: 48 83 c4 18 add $0x18,%rsp 4005c6: c3 retq For the following questions, recall that: • gets is a standard C library routine. • x86-64 machines are little-endian. • C strings are null-terminated (i.e., terminated by a character with value 0x00). • Characters ‘0’ through ‘9’ have ASCII codes 0x30 through 0x39. Page 7 of 7 Problem 3. (11 points): Consider the case where procedure foo is called with argument x equal to 0xE3E2E1E0, and we type “123456789” in response to gets. A. (2 points)) Fill in the following table indicating where on the stack the following program values are located. Express these as decimal offsets (positive or negative) relative to register %rsp: Question Part Program Value Decimal Offset i a ii a[2] iii buf iv buf[3] B. (3 points) Fill in the following table indicating which program values are/are not corrupted by the response from gets, i.e., their values were altered by some action within the call to gets. Question Part Program Value Corrupted? (Y/N) i a[0] ii a[1] iii a[2] C. (6 points) What will the printf function print for the following: i a[0] (hexadecimal): ________________________ ii a[1] (hexadecimal): ________________________ iii buf (ASCII characters): ________________________ Page 8 of 7 Problem 4. (12 points): The following table gives the parameters for a number of different caches, where m is the number of physical address bits, C is the cache size (number of data bytes), B is the block size in bytes, and E is the number of lines per set. For each cache, determine the number of cache sets (S), tag bits (t), set index bits (s), and block offset bits (b). Cache m C B E S t s b 1. 32 512 8 4 2. 43 2048 4 128 3. 32 1024 8 1 4. 51 4096 8 64 5. 32 256 32 2 6. 64 65536 64 4 Page 9 of 7 Problem 5. (10 points): Consider the following 4-way set associative cache (E = 4). It has 4 sets(S = 4), and a block size of 4 bytes (B = 4). Addresses in the system are 8 bits wide. Memory accesses are to 1-byte words. The following diagram shows the contents of the cache. Set 0 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 - 0 - - - - 1 5 1 A4 F0 DA 74 2 A 1 16 A3 77 49 3 6 1 79 48 10 53 Set 1 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 1 1 0B ED 47 88 1 - 0 - - - - 2 C 0 33 67 25 02 3 - 0 - - - - Set 2 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 E 1 E8 55 6B BD 1 6 0 06 AA 59 14 2 C 1 BA 08 FF 21 3 - 0 - - - - Set 3 Line No. Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 F 0 07 13 51 A4 1 3 1 26 1C B0 9B 2 - 0 - - - - 3 1 0 FC 7B 38 7D Please answer the following questions about this cache. A. What is the total size, in bytes, of this cache? B. Consider a read to the memory address 0x3C. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. C. Consider a read to the memory address 0xA1. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. D. Consider a read to the memory address 0x68. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. E. Consider a read to the memory address 0x7A. If this is a hit, indicate the byte that is returned. If it is a miss, your answer should be M. Page 10 of 7