Reaching a Weird State

Bug Classes and PrimitivesLesson 1 of 845 minutesLessonNo lab next

A till that disagrees with itself

A till keeps a list of prices and a running total. Those should describe the same sales, but the one below can finish a sale, print the wrong total, and exit as though nothing happened. We don’t need to make it jump anywhere to cause trouble; getting the arithmetic wrong is quite enough for a till.

In States and Transitions we described an exploit this way:

An exploit is an input, or a sequence of inputs, chosen to drive a machine into a state or along a transition its designer did not intend.

That leaves us a useful question: what makes the till’s wrong total a state its designer didn’t intend? After all, its total and list of prices also disagree briefly during an ordinary sale, while it updates one before the other. We’ll follow both cases and see where they part company.

Learning objectives

By the end of this lesson

• Distinguish the machine a program is meant to be from the machine that runs it.
• Tell a state that is merely halfway through an update from one the program has no description for.
• Say what a bug hands you, separately from what you then do with it.
• Describe the till’s results in terms of the capability and its observed effects.

A program that checks its own arithmetic

Create ~/underdunn-course/bug-classes/till.c:

Use the isolated course VM for these intentionally vulnerable programs. Create the working directory first, then keep your shell there when building the examples:

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

/*
 * A till that keeps a running total and can check its own arithmetic.
 */
#include <stdio.h>
#include <string.h>

struct till {
    char label[16];
    int  total;
    int  count;
    int  prices[8];
};

static void ring_up(struct till *t, const char *item, int price)
{
    strcpy(t->label, item);
    t->prices[t->count] = price;
    t->count++;
    t->total += price;
}

/* The till's own description of a state that makes sense. */
static int consistent(const struct till *t)
{
    int sum = 0;

    if (t->count < 0 || t->count > 8)
        return 0;
    for (int i = 0; i < t->count; i++)
        sum += t->prices[i];
    return sum == t->total;
}

static void report(const struct till *t)
{
    printf("  %-22s count %-3d total %-8d %s\n",
           t->label, t->count, t->total,
           consistent(t) ? "consistent" : "INCONSISTENT");
}

int main(void)
{
    struct till t = {0};
    char name[64];

    setvbuf(stdout, NULL, _IONBF, 0);

    ring_up(&t, "apple", 40);
    report(&t);
    ring_up(&t, "bread", 115);
    report(&t);
    ring_up(&t, "coffee", 260);
    report(&t);

    puts("Name for the fourth item:");
    if (fgets(name, sizeof name, stdin)) {
        name[strcspn(name, "\n")] = '\0';
        ring_up(&t, name, 300);
        report(&t);
    }

    return 0;
}

strcspn finds the newline left by fgets so the next line can replace it with a string terminator. setvbuf disables output buffering, which keeps each report visible immediately when the program is driven through a pipe. Those are conveniences for this interface, not part of the overflow.

The interesting function is consistent. Most programs carry a rule like this somewhere, usually in a comment or in the head of whoever wrote it. This one has written its rules down and can check them:

• The total has to be the sum of the prices actually recorded.
• The count has to be a number of items the till could hold.

Build it with the same command the rest of the course has used, and sell four things:

gcc -g -O0 -fno-omit-frame-pointer till.c -o till
echo "dates" | ./till

  apple                  count 1   total 40       consistent
  bread                  count 2   total 155      consistent
  coffee                 count 3   total 415      consistent
Name for the fourth item:
  dates                  count 4   total 715      consistent

Four sales, four consistent reports. Now give it a longer name and watch what happens to the report:

python3 -c "print('A'*17)" | ./till

  AAAAAAAAAAAAAAAAm     count 4   total 365      INCONSISTENT

The till says its own arithmetic is wrong, and then exits normally with status 0.

label holds sixteen bytes. strcpy copied the seventeen A characters and then their terminating zero, so two bytes landed in total. It’s the overflow from Stack Overflows and Return Addresses, with a different neighbour beside the buffer.

The stray m after the A’s comes from the report reading past the end of an unterminated label and into total. The same write has damaged the arithmetic and the text the till prints.

The same bug, one variable, three different outcomes

Compare the results at different name lengths, watching which column changes first:

for n in 15 16 17 19 20 21 22 25; do
  python3 -c "print('A'*$n, end='')" | ./till >/dev/null 2>&1
  printf '%2d chars : exit %d\n' "$n" "$?"
done

Name length	Reaches	Result	Exit
15	nothing outside label	consistent	0
16	the low byte of total	INCONSISTENT, total 556	0
17	two bytes of total	INCONSISTENT, total 365	0
19	all of total	INCONSISTENT, total 4276845	0
20	into count	INCONSISTENT, count 1	0
21	further into count	INCONSISTENT, count 66	0
22 and up	count entirely	segmentation fault	139

Increasing the name length carries the same write through different fields:

• While it only reaches total, the till can still check the sale and print its report, even though the arithmetic is wrong.
• Once it reaches count, the damage also changes where the next price will be stored.

Making the input longer can change more than the size of the wrong total.

The fault at 22 characters is worth looking at, because it isn’t the buffer that kills it:

python3 -c "print('A'*24)" | gdb -q -batch -ex run -ex 'printf "count was %d\n", t.count' ./till

0x0000555555555248 in ring_up (t=0x7fffffffdf00, item=0x7fffffffdf40 'A' <repeats 24 times>, price=300) at till.c:17
count was 1094795585

The GDB command ptype /o struct till, used later if your layout differs, prints each structure member with its offset. It lets you compare the compiled layout with the distances these inputs reached.

Line 17 is t->prices[t->count] = price. The strcpy finished without complaint. What crashed was the till’s own perfectly ordinary code, using a counter that no longer meant anything.

Two machines, and only one of them has these states

In States and Transitions you drew a fare gate with two states and worked out what happened for every input. A program is that kind of machine too, and till.c is a fairly small one: a count, a total, a list of prices, and a rule saying how they relate.

The CPU running it is a different machine. Its state includes registers and memory, where 1094795585 fits quite comfortably in an int. There is no sensible interpretation of that value as the number of prices in this eight-item till, but the CPU doesn’t know what a till is. It can keep executing instructions using that count until an access faults.

Thomas Dullien’s Weird Machines, Exploitability, and Provable Unexploitability describes this relationship as a program implementing an intended machine on a more detailed underlying machine. It distinguishes three kinds of state:

• Valid states represent states of the intended machine.
• Transitory states are the temporary states needed to move between valid ones.
• Weird states fit neither category.

For the till, that means distinguishing corrupted bookkeeping from bookkeeping that simply isn’t finished yet. Let’s look at an ordinary sale before blaming every disagreement on a bug.

An unfinished sale isn’t a corrupted one

Break on the assignment inside ring_up and step through a single, entirely ordinary sale:

gdb -q -batch \
  -ex 'break till.c:17' -ex 'run' \
  -ex 'printf "before prices[count] = price : count=%d total=%d consistent=%d\n", t->count, t->total, consistent(t)' \
  -ex 'next' -ex 'next' \
  -ex 'printf "after  count++               : count=%d total=%d consistent=%d\n", t->count, t->total, consistent(t)' \
  -ex 'next' \
  -ex 'printf "after  total += price        : count=%d total=%d consistent=%d\n", t->count, t->total, consistent(t)' \
  ./till </dev/null

before prices[count] = price : count=0 total=0 consistent=1
after  count++               : count=1 total=0 consistent=0
after  total += price        : count=1 total=40 consistent=1

The middle line is the first sale of the day, with nothing wrong anywhere. count has been incremented and total hasn’t caught up yet, so the till’s own rule is false for one statement. It is false for one statement during every sale, including the three that reported consistent.

The relationship checked by consistent is an invariant: a rule intended to hold whenever a sale is complete. So “the invariant does not hold” isn’t enough to call a state weird. If it were, this program would be in a weird state several times a second while working perfectly.

A transitory state is one the program is passing through on its way between two states the design does describe, and it gets to be inconsistent on the way.

What separates the 17-character run isn’t that the rule was broken. It’s that the program had finished ring_up, had nothing left to do about it, and the rule was still broken. There was no state of the till that the CPU was on its way to.

Key concept

Check the rule at the end of the update

When reading the variables at a breakpoint, check where you stopped as well as what they contain. A half-finished update still has work to do; a completed one should already satisfy the till’s rule.

What the bug handed you, and what you did with it

We know the long name can leave the till inconsistent. We haven’t yet established how precisely we can choose the resulting total, or what another part of a larger program might do with it.

Reaching a weird state is one achievement. Making the weird state do something you want is a second, separate one. In the till, the first is a name longer than fifteen characters. The second would be choosing which of total, count or the memory past them to change, and to what.

The useful question about a bug, then, is what it gives you to work with. For the till: a write, starting at a fixed place, running forward as far as you care to take it, with bytes you choose. Where it lands is a question of distance.

Look back at what you already did with that same description. In Stack Overflows and Return Addresses the write started in a buffer and you took it as far as the saved return address. Here it starts in label and reaches total at sixteen bytes and count at twenty. It is the same kind of bug both times, and the interesting difference is what happened to be sitting in range.

That forward write is an example of a primitive: a capability we can obtain from a bug and use as a building block. Its description separates two kinds of choice:

• We choose the bytes and how far the copy runs.
• The program determines where the copy begins.

Other bugs divide up that control differently:

What the bug gives you	Meaning
Relative read or write	From a fixed starting point, at an offset you control
Absolute read or write	At an address you choose outright
Constrained value	The operation limits what value can be written, such as a count or a terminating zero
Controlled reuse	You influence what occupies storage that an old reference can still reach

These descriptions can overlap. A write can be relative and limited to one zero byte, for example. For now, the till gives us the relative starting point and forward direction; the later examples will let us compare those constraints with operations that take a complete address from the input.

Knowledge check

Question 1 of 3

During an ordinary sale, consistent() returns 0 for one statement. What does that establish?

The till is passing through a transitory state during an unfinished updateThe till reaches a weird state whenever its consistency rule becomes falseThe consistency check is defective because ordinary sales should never fail it

Check answer

When the results don’t match

• If every length reports consistent, check that the copy is still strcpy and that the input contains the intended number of As. This program removes the trailing newline before copying, so that newline does not count toward the name length.
• If the crash arrives earlier or later than 22 characters, compare your struct layout with gdb -q -batch -ex 'ptype /o struct till' ./till. Member order is fixed, but padding and what memory is mapped can affect the result; use the layout and faulting instruction from your own build.
• If consistent isn’t available inside GDB, confirm you built with -g -O0. An optimising build can discard a static function that nothing outside the file calls.
• If the fourth report doesn’t appear at all, fgets received no line. Send one with echo or printf rather than closing the input.

To recover a known state, rebuild with the command above. Nothing you type at the prompt changes the source or the executable.

Check your understanding

Compare what a bug gives you with what you use it for:

• Describe the till’s capability in one sentence, without using the words “buffer overflow”.
• Use the till’s results above to separate what the bug gave you from what happened in each run. Identify the write the bug allows, then the particular value that changed in this run.

Compare your thinking

For the till, something close to: a forward write of chosen bytes, beginning at a known offset inside the structure, continuing as far as the input is long.

The descriptions may start to repeat. The earlier stack-overflow examples began with a relative write, but differed in what was within reach and which protections stood in the way. The till uses that same kind of write to damage bookkeeping instead of a return address.

Repeated descriptions are expected where the underlying write was the same. Keep any additional requirement, such as a leak, separate from the write itself so you can see what the mitigation changed.

Without corrupting memory

The till and the earlier stack-overflow examples wrote somewhere they shouldn’t have. That’s one way to reach a weird state, and it isn’t the only one.

In Logic Bugs, the unwanted result comes from an ordinary request that the program should have refused. The buffers can remain intact while an access rule is broken.