Out-of-Bounds Reads

Bug Classes and PrimitivesLesson 3 of 860 minutesLessonNo lab next

The check that was doing all the work

In Logic Bugs you asked the depot for locker 99 and it said no. That refusal was the only thing keeping a locker number pointing at lockers.

We’ll keep the sign-in command and locker display, but remove the range check. The contents are also stored inline now: each locker occupies thirty-two consecutive bytes, rather than holding a pointer to text elsewhere. That gives us a simple distance to follow when an index takes us past the last locker. This listing starts from the depot without the ownership repair.

The depot, rebuilt

In the Ubuntu terminal, create the working directory if needed and move into it:

mkdir -p ~/underdunn-course/bug-classes ~/underdunn-course/notes
cd ~/underdunn-course/bug-classes

Save the complete program below as manifest.c. Keep the terminal in this directory for the build commands; no source file from an earlier lesson is needed.

/*
 * The depot again, with the contents stored inline and the range check gone.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LOCKERS 6

static char contents[LOCKERS][32] = {
    "(empty)",
    "parcel 8841, for Nadia",
    "parcel 8842, for Omar",
    "(empty)",
    "depot master key",
    "parcel 8843, for Priya",
};

static char night_note[32] = "relief courier code 4417";
static char van_note[32]   = "van 12 keypad 9930";

static char courier[32] = "";

static void open_locker(int n)
{
    if (courier[0] == '\0') {
        puts("  denied: not signed in");
        return;
    }
    printf("  locker %d: %s\n", n, contents[n]);
}

int main(void)
{
    char line[128];

    setvbuf(stdout, NULL, _IONBF, 0);
    puts("Parcel depot. Commands: signin <name>, open <n>, quit");

    while (fgets(line, sizeof line, stdin)) {
        line[strcspn(line, "\n")] = '\0';

        if (strncmp(line, "signin ", 7) == 0) {
            snprintf(courier, sizeof courier, "%s", line + 7);
            printf("  signed in as %s\n", courier);
        } else if (strncmp(line, "open ", 5) == 0) {
            open_locker(atoi(line + 5));
        } else if (strcmp(line, "quit") == 0) {
            break;
        } else if (line[0] != '\0') {
            puts("  unknown command");
        }
    }
    return 0;
}

gcc -g -O0 -fno-omit-frame-pointer -Wall -Wextra manifest.c -o manifest

Run ./manifest and enter:

signin sam
open 4
quit

  signed in as sam
  locker 4: depot master key

Six lockers, numbered zero to five. What does the program do when we ask for locker 6?

Six lockers, and the ones after that

for n in 5 6 7 8 9 10; do
  printf 'signin sam\nopen %d\nquit\n' "$n" | ./manifest | sed -n '3p'
done

  locker 5: parcel 8843, for Priya
  locker 6: relief courier code 4417
  locker 7: van 12 keypad 9930
  locker 8: ?U?qMq
  locker 9: sam

Locker 5 is the last real one. Lockers 6 and 7 are the two notes declared after the array, which the depot never offered a way to read. Locker 8 is whatever bytes happen to sit in the gap after them.

Locker 9 appears to contain the sign-in name. We can test that interpretation by choosing a name we won’t mistake for the depot’s own text. Run ./manifest and enter:

signin ZANZIBAR
open 9
quit

The last line is the one to compare:

  locker 9: ZANZIBAR

That’s the courier buffer, holding the name you signed in with. The locker number stopped meaning “which locker” the moment the check came off. It means “how many thirty-two byte steps from the start of contents”, and the things it steps onto are whatever the linker put there.

Checking the arithmetic

You don’t have to take the mapping on trust. The symbols are in the binary:

for s in contents night_note van_note courier; do
  printf '%-12s %s\n' "$s" "$(nm ./manifest | awk -v s=$s '$3==s{print $1}')"
done

contents     0000000000004020
night_note   00000000000040e0
van_note     0000000000004100
courier      0000000000004140

Each row of contents is thirty-two bytes, so subtract the base and divide:

Symbol	Address	Index it appears at
`contents`	`0x4020`	0
`night_note`	`0x40e0`	6
`van_note`	`0x4100`	7
`courier`	`0x4140`	9

(0x40e0 - 0x4020) / 32 is 6, which is where the night note showed up. The gap at index 8 is alignment padding between van_note and courier, and it holds nothing the program put there.

None of that ordering is promised by C. Separate objects at file scope can be laid out in whatever order the toolchain likes, and this one happened to keep them in declaration order. The reason to read nm rather than the source is that the source is not the authority here.

The tool earns its place

Ask AddressSanitizer about locker 6:

gcc -g -O0 -fsanitize=address manifest.c -o manifest-asan

Run ./manifest-asan and enter:

signin sam
open 6
quit

==13418==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5e04beb9a0e0
READ of size 1 at 0x5e04beb9a0e0 thread T0
0x5e04beb9a0e0 is located 0 bytes after global variable 'contents' defined in 'manifest.c:10:13' (0x5e04beb9a020) of size 192
0x5e04beb9a0e0 is located 32 bytes before global variable 'night_note' defined in 'manifest.c:19:13' (0x5e04beb9a100) of size 32

The report locates a one-byte read immediately after the 192-byte contents array. It describes the first invalid access detected, not the whole string the unsanitized run happened to print.

Notice where night_note went, too. It is now another thirty-two bytes away: the instrumented build inserted a protected gap, so this read did not land on the note as it did in the plain build.

We have two useful measurements of different binaries:

The plain build’s symbol table explains where its printed text came from.
The instrumented build’s report identifies the object boundary the read crossed.

Their offsets needn’t agree, because adding the instrumentation changed the layout.

One tool speaks and the other doesn’t

The ownership violation in Logic Bugs didn’t require an invalid memory access. This one does, so try the same request under Valgrind’s Memcheck:

printf 'signin sam\nopen 6\nquit\n' | valgrind -q --error-exitcode=9 ./manifest > /dev/null
echo "exit $?"

exit 0

Still nothing, and still not a malfunction. The tools learn about boundaries differently:

Memcheck watches heap blocks being allocated. But contents is a global, present in the file and placed by the linker before the program starts. There was no heap allocation to tell it where this array ends.
AddressSanitizer has help from the compiler, which put padding around the globals at build time and told it where they are.

So the quiet run doesn’t contradict the detected overflow. The tools aren’t enforcing the same boundaries here.

What this actually gives you

Compare what happens at these other indices:

for n in 100 200 -100 -1000; do
  printf 'signin sam\nopen %d\nquit\n' "$n" | ./manifest > /dev/null 2>&1
  printf 'open %-6s exit %d\n' "$n" "$?"
done

open 100    exit 0
open 200    exit 139
open -100   exit 0
open -1000  exit 139

Negative indices work as readily as positive ones, because nothing checks the sign either. Far enough in either direction the read leaves mapped memory and the process dies, which puts the boundary somewhere between 100 and 200 forward on this build.

The index chooses a starting address in thirty-two-byte steps from contents, forward or backward.

From there, %s keeps reading until a zero byte; it has no thirty-two-byte limit. A short string may disclose very little, while missing termination can take the read across further objects or into inaccessible memory. The stride limits where we can start, not how many bytes can be printed.

The base is contents, wherever the loader put it, which we did not choose. This is a relative read: we supply a displacement rather than a complete address. There is no write through this index in the supplied program.

Knowledge check

Question 1 of 3

Valgrind reports nothing for open 6, and AddressSanitizer reports a global-buffer-overflow. What explains the difference?

Memcheck doesn't track this global's boundary; AddressSanitizer gets it from the compilerValgrind needs the --track-globals option, which was omitted hereThe read is legal, and AddressSanitizer is reporting a false positive

When the results don’t match

If locker 6 prints something other than the night note, read your own nm output and rebuild the index table. Your toolchain may have ordered the globals differently, and your numbers are the ones to use for the rest of the lesson.
If every index prints an empty line, check that signin came first. The sign-in check is still there and still works.
If AddressSanitizer reports nothing, confirm -fsanitize=address reached the compiler and that you ran ./manifest-asan rather than ./manifest.
If the process survives far larger indices than the transcript shows, that is a difference in how memory happens to be mapped in your run and not an error. Check the boundary you observed.

To recover a known state, rebuild from the listing. The depot keeps nothing between runs.

Check your understanding

For a fresh layout, suppose each row were sixteen bytes and a separate string began forty-eight bytes after contents. Which index would start at that string? Would the smaller row size also limit how much %s could print? Explain both answers without running the example.

Compare your reasoning

In the changed layout, index 3 begins forty-eight bytes from the base. It changes the stride, not the string operation: %s still reads until a zero byte or an invalid access, rather than stopping automatically at the row boundary.

Using the index for a write

The depot never writes through that index. contents[n] appears once, inside a printf.

A program that writes through an index nobody checked is the same bug with the arrow reversed, and the interesting question stops being what is near the array and becomes what is near it that the program will later act on. That turns out to depend on decisions the compiler makes without telling you.