Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 200910thLecture, Feb. 12thInstructors:Gregory Kesden and Markus PüschelCarnegie MellonLast Time Structures Alignment Unionsstruct rec {int i;int a[3];int *p;};Memory Layouti a p0 4 1620c i[0] i[1] v3 bits 4 bitsp+0p+4 p+8 p+16 p+24struct S1 {char c;int i[2];double v;} *p;union U1 {char c;int i[2];double v;} *up;up+0 up+4 up+8ci[0] i[1]vCarnegie MellonLast Time Floating point x87 (getting obsolete) x86-64 (SSE3 and later) Vector mode and scalar mode%st(0)%st(1)%st(2)%st(3)128 bit = 2 doubles = 4 singles+%xmm15%xmm0+addpsaddssCarnegie MellonToday Memory layout Buffer overflow, worms, and viruses Program optimization Overview Removing unnecessary procedure calls Code motion/precomputation Strength reduction Sharing of common subexpressions Optimization blocker: Procedure callsCarnegie MellonIA32 Linux Memory Layout Stack Runtime stack (8MB limit) Heap Dynamically allocated storage When call malloc(), calloc(), new() Data Statically allocated data E.g., arrays & strings declared in code Text Executable machine instructions Read-onlyUpper 2 hex digits = 8 bits of addressFF00StackTextDataHeap088MBnot drawn to scaleCarnegie MellonMemory Allocation Examplechar big_array[1<<24]; /* 16 MB */char huge_array[1<<28]; /* 256 MB */int beyond;char *p1, *p2, *p3, *p4;int useless() { return 0; }int main(){p1 = malloc(1 <<28); /* 256 MB */p2 = malloc(1 << 8); /* 256 B */p3 = malloc(1 <<28); /* 256 MB */p4 = malloc(1 << 8); /* 256 B *//* Some print statements ... */}FF00StackTextDataHeap08not drawn to scaleWhere does everything go?Carnegie MellonIA32 Example Addresses$esp 0xffffbcd0p3 0x65586008p1 0x55585008p4 0x1904a110 p2 0x1904a008&p2 0x18049760beyond 0x08049744big_array 0x18049780huge_array 0x08049760main() 0x080483c6useless() 0x08049744final malloc() 0x006be166address range ~232FF00StackTextDataHeap0880not drawn to scalemalloc() is dynamically linkedaddress determined at runtimeCarnegie Mellonx86-64 Example Addresses$rsp 0x7ffffff8d1f8p3 0x2aaabaadd010p1 0x2aaaaaadc010p4 0x000011501120 p2 0x000011501010&p2 0x000010500a60beyond 0x000000500a44big_array 0x000010500a80huge_array 0x000000500a50main() 0x000000400510useless() 0x000000400500final malloc() 0x00386ae6a170address range ~24700007F000000StackTextDataHeap000030not drawn to scalemalloc() is dynamically linkedaddress determined at runtimeCarnegie MellonC operatorsOperators Associativity() [] -> . left to right! ~ ++ -- + - * & (type) sizeof right to left* / % left to right+ - left to right<< >> left to right< <= > >= left to right== != left to right& left to right^ left to right| left to right&& left to right|| left to right?: right to left= += -= *= /= %= &= ^= != <<= >>= right to left, left to right -> has very high precedence () has very high precedence monadic * just belowCarnegie MellonC Pointer Declarations: Test Yourself!int *p p is a pointer to intint *p[13] p is an array[13] of pointer to intint *(p[13]) p is an array[13] of pointer to intint **p p is a pointer to a pointer to an intint (*p)[13] p is a pointer to an array[13] of intint *f() f is a function returning a pointer to intint (*f)() f is a pointer to a function returning intint (*(*f())[13])() f is a function returning ptr to an array[13]of pointers to functions returning intint (*(*x[3])())[5] x is an array[3] of pointers to functions returning pointers to array[5] of intsCarnegie MellonC Pointer Declarations (Check out guide)int *p p is a pointer to intint *p[13] p is an array[13] of pointer to intint *(p[13]) p is an array[13] of pointer to intint **p p is a pointer to a pointer to an intint (*p)[13] p is a pointer to an array[13] of intint *f() f is a function returning a pointer to intint (*f)() f is a pointer to a function returning intint (*(*f())[13])() f is a function returning ptr to an array[13]of pointers to functions returning intint (*(*x[3])())[5] x is an array[3] of pointers to functions returning pointers to array[5] of intsCarnegie MellonAvoiding Complex Declarations Use typedef to build up the declaration Instead of int (*(*x[3])())[5] :typedef int fiveints[5];typedef fiveints* p5i;typedef p5i (*f_of_p5is)();f_of_p5is x[3]; x is an array of 3 elements, each of which is a pointer to a function returning an array of 5 intsCarnegie MellonToday Memory layout Buffer overflow, worms, and viruses Program optimization Overview Removing unnecessary procedure calls Code motion/precomputation Strength reduction Sharing of common subexpressions Optimization blocker: Procedure callsCarnegie MellonInternet Worm and IM War November, 1988 Internet Worm attacks thousands of Internet hosts. How did it happen?Carnegie MellonString Library Code Implementation of Unix function gets() No way to specify limit on number of characters to read Similar problems with other Unix functions strcpy: Copies string of arbitrary length scanf, fscanf, sscanf, when given %s conversion specification/* 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;}Carnegie MellonVulnerable Buffer Codeint main(){printf("Type a string:");echo();return 0;}/* Echo Line */void echo(){char buf[4]; /* Way too small! */gets(buf);puts(buf);}unix>./bufdemoType a string:12345671234567unix>./bufdemoType a string:12345678Segmentation Faultunix>./bufdemoType a string:123456789ABCSegmentation FaultCarnegie MellonBuffer Overflow Disassembly080484f0 <echo>:80484f0: 55 push %ebp80484f1: 89 e5 mov %esp,%ebp80484f3: 53 push %ebx80484f4: 8d 5d f8 lea 0xfffffff8(%ebp),%ebx80484f7: 83 ec 14 sub $0x14,%esp80484fa: 89 1c 24 mov %ebx,(%esp)80484fd: e8 ae ff ff ff call 80484b0 <gets>8048502: 89 1c 24 mov %ebx,(%esp)8048505: e8 8a fe ff ff call 8048394 <puts@plt>804850a: 83 c4 14 add $0x14,%esp804850d: 5b pop %ebx804850e: c9 leave 804850f: c3 ret 80485f2: e8 f9 fe ff ff call 80484f0 <echo>80485f7: 8b 5d fc mov 0xfffffffc(%ebp),%ebx80485fa: c9 leave 80485fb: 31 c0 xor %eax,%eax80485fd: c3 retCarnegie MellonBuffer Overflow Stackecho:pushl %ebp # Save %ebp on stackmovl %esp, %ebppushl %ebx # Save %ebxleal -8(%ebp),%ebx # Compute buf as
View Full Document
Unlocking...