The Computer as a State Machine
A note on abstraction
Section titled “A note on abstraction”Alfred Aho once said:
Computer science is a science of abstraction—creating the right model for a problem and devising the appropriate mechanizable techniques to solve it.
Computers are incredibly complex machines. If you go down the supply chain far enough, you’ll find some very talented engineers fighting with quantum tunneling in RAM chips. That said though, if we spend all day thinking about how circuit design prevents electrons from teleporting and messing with our adder cicruit, we’ll never get anywhere building the next great web app.
One of the most important concepts in computer science then is to choose the right abstraction for the problem. Web designers will think of the computer differently than an embedded developer, and both will think of it very differently than a mathmatician who is trying to prove a theorem.
So what is the correct abstraction for an exploit developer?
What state is a program in?
Section titled “What state is a program in?”Let’s build our abstraction.
In States and Transitions, we could predict what a fare gate would do by knowing whether it was locked and what input it received. The same push had two different results, depending on the state we started in.
We can do this with a computer too, although “the browser is running” isn’t going to tell us much. The browser could be loading a page, playing a video, or waiting for you to remember a password. Even “loading a page” covers a lot of different things it might be doing. To predict its next step, we’ll need to describe its state in more detail.
A running program is called a process. To describe what it’s doing, we’ll use three parts:
- a flat memory space
- registers
- and the CPU executing its instructions.
Memory and registers hold the values the program is working with, including where it is in its execution. Those contents are our state, and the CPU changes them as it carries out instructions.
Representing memory and registers
Section titled “Representing memory and registers”Let’s start with memory. Memory can be thought of as one long sequence of byte-sized locations, each with:
- an address telling us where it is
- and contents telling us what’s stored there.
The program’s instructions, application data, and stack all have addresses along that line. That’s what we mean by a flat memory space.
Next to memory, put the registers. These are small storage locations in the CPU.
There are many different kinds of computer architecture, and they each have different register names. We’ll be working with x86-64 for this course since it is the most popular, although it is under heavy competition from ARM.
Registers hold values, just like memory addresses. The main difference is that registers are much faster to access, so the CPU prefers to keep data there. There are also some kinds of operations that are only able to be performed on registers, so data must be loaded from memory into a register before acting upon it.
STATE = memory contents + register contents
Memory
Addresses and bytes in hexadecimal.
| Address | Stored bytes |
|---|---|
0x401000 | 48 8b 03 |
| ⋮ | |
0x600000 | 07 00 00 00 00 00 00 00 |
0x600008 | 41 |
| ⋮ | |
0x7fff0000 | 05 00 00 00 00 00 00 00 |
0x7fff0008 | 20 10 40 00 00 00 00 00 |
Registers
A selection, not the complete set.
rax5rbx0x600000rcx3rdx0rsi0x600008rdi0x600000rbp0rip0x401000rsp0x7fff0000- Flags
0x202
Illustrative snapshots, not debugger output. Gaps are not to scale; omitted addresses need not be mapped.
For an example of how these storage units can work together, find 0x600000 in the Address column. The eight bytes to its right represent the integer 7 in little-endian notation: the least-significant byte, 07, is stored at the lowest address.
Now look at rbx: it contains 0x600000. Even though the register itself contains only a number (that is all it is able to do), looking at memory address 0x600000 shows us the value rbx is pointing to. Registers can also hold values directly, such as rax holding the number 5; assembly calls a constant written into an instruction an immediate value.
Because of virtual addressing each process gets a very large uninterrupted address space to work with. For example, on most Linux systems a process can write anywhere between 0x0000000000000000 and 0x00007FFFFFFFFFFF.
Taken together, the memory and register contents describe our state. If rax held 6 instead of 5, we’d have a different state even if the program’s window looked exactly the same.
Based on the state of the memory and registers, the CPU will take one deterministic step and modify that state. It then looks at the new state, modifies it again, and continues so on and so forth.
With the fare gate, we could give each state a convenient name: locked or unlocked. We could technically do that here too, because a fixed amount of storage has a finite number of possible arrangements. That said, I wouldn’t recommend trying to draw them all unless you have nothing going on between now and the heat death of the universe. Throughout this course we’ll focus on just the area we’re interested in and work with that.
Let the CPU take one step
Section titled “Let the CPU take one step”So, what does the CPU do with these values? Before it can do anything, it needs to know which instruction to execute.
That’s the job of the instruction pointer, called rip here. It holds the address of the instruction the CPU is about to execute. The CPU reads the bytes at that address and carries out the operation they specify, so our position in the program is stored in a register just like the other values we’re using.
In our example, rip holds 0x401000. Look up that address in the memory table and you’ll find 48 8b 03. Together, those three bytes encode one instruction: copy the eight-byte value at the address in rbx into rax.
We already followed rbx to 0x600000 and found 7 there, so that’s what gets copied into rax, replacing the 5. Copying a value from memory into a register is called a load. Notice that the CPU used two different addresses: rip told it where to find the instruction, and rbx told it where to find the value that instruction would copy.
Press Next to execute the load and observe the register values.
The same illustrative process as the first snapshot. Only registers relevant to this instruction are shown; unshown state stays unchanged.
Before mov rax, [rbx]
Selected memory · addresses labelled individually
7
Live registers
- rax
- 5
- rbx
- 0x600000
- rip
- 0x401000
- Flags
- 0x202
The load copies the source; it does not empty memory. rip advances past the three instruction bytes.
Blue underlines mark changed values; dashed outlines mark current sources or destinations. Byte addresses increase left to right. Unshown values are omitted, not zero.
rax now contains 7, and rip has advanced from 0x401000 to 0x401003, ready for the next instruction. The source in memory still contains 7, while rbx still holds its address.
The diagram also shows the CPU’s status flags, which record properties of earlier results for later instructions to test. This load does not change them, so they remain 0x202. We won’t need to interpret the individual flag bits here.
That’s one transition: the CPU followed an instruction and left us with a new set of register contents. If the source had contained a different value, we’d have loaded that value instead. Different instruction bytes could have told the CPU to do something else, and a different rip could have sent it to another instruction altogether. We need the instruction pointer as well as the application data to work out what happens next.
There’s a useful difference from the fare gate here. The gate waited for a fare or a push from outside, but the CPU found both its instruction and the value to copy in memory. It can carry on with the next instruction without waiting for us to press anything. Programs still receive outside input, of course; they just don’t need a new input before every instruction.
The MOV entry in Volume 2 of the Intel architecture manuals documents the copy operation used here.
The program is in memory too
Section titled “The program is in memory too”Where was the program in all of that? We just executed part of it: the three bytes at 0x401000. Its instructions are stored in memory alongside the values they work on.
The other bytes in memory aren’t necessarily numbers the program intends to do arithmetic with, either. They might represent text, an image, or a pointer to some other location. A memory dump shows the bit patterns as numbers, but it doesn’t tell us by itself what the program uses them for.
For example, look at 0x600008. The byte there is 41 in hexadecimal, or 65 in decimal. Read it as ASCII text and it’s the letter A; use it as an integer and it’s 65. Nothing about the stored byte changed between those interpretations. In the same way, the CPU interprets our instruction bytes according to its instruction set when it executes them.
All the things a program keeps in memory
Section titled “All the things a program keeps in memory”Now imagine we’re looking inside a text editor. It has to keep the document’s text somewhere, remember where the cursor is, and hang on to enough information to undo an edit. Where would we find those things?
Everything the program can work on directly has to be represented in memory or registers. A file on disk, for example, becomes available to these instructions after the program reads some of its bytes into memory. Memory itself is a series of byte-sized locations, each holding a number from 0 to 255 at a defined address.
STATE = memory contents + register contents
Memory
Addresses and bytes in hexadecimal.
Scroll sideways to read the bytes and their uses.
| Address | Stored bytes | Use in this example |
|---|---|---|
0x401000 | 48 8b 03 | Instructions · the load we followed |
| ⋮ | ||
0x600000 | 07 00 00 00 00 00 00 00 | Program data · value 7 |
0x600008 | 41 | Program data · character A |
| ⋮ | ||
0x800000 | 48 65 6c 6c 6f | Heap · file buffer containing “Hello” |
| ⋮ | ||
0x7fff0000 | 05 00 00 00 00 00 00 00 | Stack frame · saved value |
0x7fff0008 | 20 10 40 00 00 00 00 00 | Stack frame · return address |
Registers
A selection, not the complete set.
rax5rbx0x600000rcx3rdx0rsi0x600008rdi0x600000rbp0rip0x401000rsp0x7fff0000- Flags
0x202
Illustrative snapshots, not debugger output. Gaps are not to scale; omitted addresses need not be mapped. The frame shows two example slots, not a required layout for every function.
At 0x800000, we have five bytes spelling “Hello”, the contents of our file buffer. The 7 at 0x600000 could count edits to the document, which would give the load we followed a reason to copy it into a register. Farther down, at 0x7fff0000, the outlined stack frame holds a saved value and a return address. The stack pointer, rsp, points into that frame.
Notice that “file buffer” and “heap allocation” can name the very same bytes. One tells us what the editor is using them for, while the other tells us how it obtained the storage. A variable can live in a stack frame for the same reason: we’re describing a value and where it’s kept, not two competing kinds of memory.
When the editor changes a character or updates the cursor position, instructions change the stored values. A function call needs to preserve a return address too. There’s more to follow than in our single load, but we can still stop at an instruction, read the relevant memory and registers, and work out what it changes.
Try the transition yourself
Section titled “Try the transition yourself”Return to the first snapshot. Keep the instruction bytes and every address the same, but replace the eight-byte source value at 0x600000 with 9 (09 00 00 00 00 00 00 00). This is a fresh starting state; rax is back to 5 and rip is back to 0x401000.
Follow the load once with the new value. Which register receives 9, which
address selects the next instruction, and do the source bytes change?
To check: rax becomes 9, rip advances to 0x401003, and the source still
contains 9. If you copied the address into rax, follow rbx to the contents
at that address. A scratch sketch is optional.
Knowledge check
Question 1 of 3
Practice complete
You've checked the key ideas. Revisit any explanation you need, then continue when it makes sense.
Next we’ll look more closely at the anatomy of a stack frame and how computers use a specific data structure in memory to store a function’s context.