CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 2 of 7 · 3 min read

The bugs

Think of it this way. A hotel gives each guest a key to one room. A guest who walks into the next room, uses a room after check-out, or never returns the key causes the kinds of trouble that follow. The analogy stops in one place: a hotel notices a wrong key at the door, and the C heap has no door. Nothing checks the access.

The six bugs:

  1. Memory leak: a block is never freed, and the last pointer to it is lost.
  2. Heap overflow: a write or read goes past the end (or before the start) of a block.
  3. Use after free: a block is used after free has returned it.
  4. Double free: the same block is freed twice.
  5. Invalid free: free receives a pointer that did not come from malloc, or that points into the middle of a block.
  6. Uninitialised read: a value is read before anything was stored in it. For heap memory, malloc does not clear the block.

In plain words: One small program shows five of these. It allocates 16 bytes, copies "hello" into it, and then does one wrong thing chosen by an argument:

char *p = malloc(16);
strcpy(p, "hello");
switch (which) {
case 1: p[16] = 'x'; break;                      /* write one byte past the end */
case 2: free(p); printf("%c\n", p[0]); return 0; /* use after free */
case 3: free(p); free(p); return 0;              /* double free */
case 4: p = NULL; break;                         /* leak: the only pointer is lost */
case 5: { int x; if (x > 0) puts("positive"); break; }  /* uninitialised */
}
free(p);

The result of a plain run, with no tool:

Case What the program did Visible error
1, overflow by one byte exited normally none
2, use after free printed one byte of garbage none
3, double free printed "free(): double free detected in tcache 2" and aborted yes (exit code 134)
4, leak exited normally none
5, uninitialised read printed "positive" on one run none

Four of the five cases went through silently. Case 1 shows why. A request of 16 bytes gets a block with 24 usable bytes (page 1), so the byte at index 16 was inside the block. The program was wrong, and the allocator happened not to mind. Only the double free was caught, by a check that glibc makes cheaply. The C standard calls the result of these actions undefined behaviour: the program may crash, may give wrong output, or may appear to work, and it may behave differently on another machine or after an unrelated change.

Undefined behaviour

Undefined behaviour is the result of an action for which the C language places no requirement, such as a read past the end of a block or the use of a freed pointer, so the program may crash, give wrong results or appear to work.

Example: writing at index 16 of a 16-byte block ran without error here, because the block had 24 usable bytes, and the same write may corrupt a neighbour with another size.

Common mistake

"It ran without a crash, so it is correct" is false for memory bugs. A bug that does no visible harm today can corrupt data after a small change in sizes or in the order of allocations.

Check yourself: 1. Which of the six bugs is not an access to memory that is outside the allowed range? 2. Why did the one-byte overflow not crash the program? 3. What does the C standard call the result of such a bug?