Memory Management III: Perils and pitfalls Mar 13, 2001C operatorsC pointer declarationsMemory-related bugsDereferencing bad pointersReading uninitialized memoryOverwriting memorySlide 8Slide 9Slide 10Slide 11Buffer overflow attacksSlide 13Slide 14Referencing nonexistent variablesFreeing blocks multiple timesReferencing freed blocksFailing to free blocks (memory leaks)Slide 19Dealing with memory bugsDealing with memory bugs (cont.)Debugging mallocDebugging malloc (cont.)Slide 24Slide 25Memory Management III:Perils and pitfallsMar 13, 2001Topics•Memory-related bugs•Debugging versions of mallocclass16.ppt15-213“The course that gives CMU its Zip!”CS 213 S’01– 2 –class16.pptC 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 rightNote: Unary +, -, and * have higher precedence than binary formsCS 213 S’01– 3 –class16.pptC pointer declarationsint *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 intsCS 213 S’01– 4 –class16.pptMemory-related bugsDereferencing bad pointersReading uninitialized memoryOverwriting memoryReferencing nonexistent variablesFreeing blocks multiple timesReferencing freed blocksFailing to free blocksCS 213 S’01– 5 –class16.pptDereferencing bad pointersThe classic scanf bugscanf(“%d”, val);CS 213 S’01– 6 –class16.pptReading uninitialized memoryAssuming that heap data is initialized to zero/* return y = Ax */int *matvec(int **A, int *x) { int *y = malloc(N*sizeof(int)); int i, j; for (i=0; i<N; i++) for (j=0; j<N; j++) y[i] += A[i][j]*x[j]; return y;}CS 213 S’01– 7 –class16.pptOverwriting memoryAllocating the (possibly) wrong sized objectint **p;p = malloc(N*sizeof(int));for (i=0; i<N; i++) { p[i] = malloc(M*sizeof(int));}CS 213 S’01– 8 –class16.pptOverwriting memoryOff-by-oneint **p;p = malloc(N*sizeof(int *));for (i=0; i<=N; i++) { p[i] = malloc(M*sizeof(int));}CS 213 S’01– 9 –class16.pptOverwriting memoryOff-by-one reduxint i=0, done=0;int s[4];while (!done) { if (i > 3) done = 1; else s[++i] = 10;}CS 213 S’01– 10 –class16.pptOverwriting memoryForgetting that strings end with ‘/0’char t[7];char s[8] = “1234567”;strcpy(t, s);CS 213 S’01– 11 –class16.pptOverwriting memoryNot checking the max string sizechar s[8];int i;gets(s); /* reads “123456789” from stdin */ Basis for classic buffer overflow attacks• 1988 Internet worm• modern attacks on Web serversCS 213 S’01– 12 –class16.pptBuffer overflow attacksDescription of hole:•Servers that use C library routines such as gets() that don’t check input sizes when they write into buffers on the stack.•The following description is based on the IA32 stack conventions. The details will depend on how the stack is organized, which varies between machines64 bytesfor bufferreturn addrSaved regs. and Local varsproc a() { b(); # call procedure b}proc b() { char buffer[64]; # alloc 64 bytes on stack gets(buffer); # read STDIN line into stack buf}Stack frame for proc a%ebpStack frame for proc b%ebpCS 213 S’01– 13 –class16.pptOverwriting memoryReferencing a pointer instead of the object it points toint *BinheapDelete(int **binheap, int *size) { int *packet; packet = binheap[0]; binheap[0] = binheap[*size - 1]; *size--; Heapify(binheap, *size, 0); return(packet);}CS 213 S’01– 14 –class16.pptOverwriting memoryMisunderstanding pointer arithmeticint *search(int *p, int val) { while (*p && *p != val) p += sizeof(int); return p;}CS 213 S’01– 15 –class16.pptReferencing nonexistent variablesForgetting that local variables disappear when a function returnsint *foo () { int val; return &val;}CS 213 S’01– 16 –class16.pptFreeing blocks multiple timesNasty!x = malloc(N*sizeof(int));<manipulate x>free(x);y = malloc(M*sizeof(int));<manipulate y>free(x);CS 213 S’01– 17 –class16.pptReferencing freed blocksEvil! x = malloc(N*sizeof(int));<manipulate x>free(x);...y = malloc(M*sizeof(int));for (i=0; i<M; i++) y[i] = x[i]++;CS 213 S’01– 18 –class16.pptFailing to free blocks(memory leaks)slow, long-term killer! foo() { int *x = malloc(N*sizeof(int)); ... return;}CS 213 S’01– 19 –class16.pptFailing to free blocks(memory leaks)Freeing only part of a data structurestruct list { int val; struct list *next;};foo() { struct list *head = malloc(sizeof(struct list)); head->val = 0; head->next = NULL; <create and manipulate the rest of the list> ... free(head); return;}CS 213 S’01– 20 –class16.pptDealing with memory bugsConventional debugger (gdb)•good for finding bad pointer dereferences•hard to detect the other memory bugsDebugging malloc (CSRI UToronto malloc)•wrapper around conventional malloc•detects memory bugs at malloc and free boundaries–memory overwrites that corrupt heap structures–some instances of freeing blocks multiple times–memory leaks•Cannot detect all memory bugs–overwrites into the middle of allocated blocks–freeing block twice that has been reallocated in the interim–referencing freed blocksCS 213 S’01– 21 –class16.pptDealing with memory bugs (cont.)Binary translator (Atom, Purify)•powerful debugging and analysis technique•rewrites text section of executable object file•can detect all errors as debugging malloc•can also check each individual reference at runtime–bad pointers–overwriting–referencing outside of allocated blockGarbage collection (Boehm-Weiser Conservative GC)•let the system free blocks instead of the programmer.CS 213 S’01– 22 –class16.pptDebugging mallocmymalloc.h:#define malloc(size) mymalloc(size, __FILE__, __LINE__)#define free(p)
View Full Document