Lecture 3 reduced code injection to three requirements. Every defense in this lecture attacks one of them, or the path the attacker takes to reach it:
Switch the defenses on one at a time, against the same stack overflow you exploited in the 1A lab. Watch what each one costs the attacker, and what it does not cost them.
Defensive coding
The cheapest defense is not to write the bug, and it needs no compiler flag, no kernel feature and no runtime: pay attention to loops, state the size of the destination buffer rather than trusting the source, and prefer a library that takes a length.
The functions that do not take a length
Four C library functions write into a destination without being told how big it is. They copy until the source ends, which means the attacker chooses how much is written:
| Unbounded, no length parameter | Bounded | The catch nobody mentions |
|---|---|---|
| strcpy(char *dest, const char *src) | strncpy | On truncation it does not write a terminating NUL, so the next strlen runs off the end. |
| strcat(char *dest, const char *src) | strncat | Its n is the number of bytes to append, not the size of the buffer. Passing sizeof(dst) is itself the bug. |
| gets(char *s) | fgets | No catch. gets cannot be used safely at all and was deleted from the language in C11. |
| sprintf(char *str, const char *format, ...) | snprintf | Returns the length it would have written, not the length it did. Using the return value as an index walks past the buffer. |
The right-hand column is the reason this is a practice and not a fix. Swapping in the bounded call moves the bug rather than removing it, unless you also read what the bounded call promises. The safest of the four is the one that was removed outright.
One that is not in the table belongs here too: scanf("%s", buf), the one that broke the 1A lab program. It has a bounded form, %49s, where the number is the buffer size minus one for the NUL. Off by one there and the practice has failed silently.
The general shape: every one of these fixes asks a human to write a number that agrees with a declaration somewhere else. That is exactly the agreement a compiler could check and does not.
Tools that read the code for you
If the practice depends on a human never slipping, automate the reading. Two different kinds of tool get named in the same breath, and it is worth keeping them apart, because they fail in opposite directions:
Flawfinder {{ cite.flawfinder }} matches patterns. It looks each call up in a database of dangerous names and ranks what it finds. It cannot tell a guarded strcpy from an unguarded one, because it never looks at what guards it.
Infer {{ cite.infer }} reasons instead. It summarises what each procedure does to memory and composes the summaries across call sites, so it can report a null dereference on a path through three functions that no single file contains.
Both see every line, including the ones your tests never reach, and neither sees the input. Expect false alarms, more of them from the cheaper tool.
AddressSanitizer {{ cite.asan }}. The compiler instruments every load and store and surrounds every object with poisoned redzones, and a touch inside one aborts with the exact line.
Almost no false alarms, and it only ever sees the paths your input actually took. Roughly 2× slower, so it is a testing tool, not a shipping one.
The lecture slides file AddressSanitizer under static analysis. It is worth being precise here, because the difference is the whole trade-off: ASan is a compile-time instrumentation with a runtime check. It knows an access was out of bounds because it watched it happen, which is why it is nearly always right and why it can only speak about the run you just did.
None of this is enforcement. A scanner that finds nine bugs out of ten ships the tenth, and a practice followed by four developers out of five is a practice the attacker only has to beat once. Everything from here on assumes the bug is still in the binary.
Stack canaries
The mechanism and its limits belong to Lecture 1A: the secret between the locals and the saved return address, the check before ret, and the third state, where an attacker who never crosses the secret walks straight past it.
The implementation is less familiar. The compiler emits four instructions, the secret value comes from a specific place, and the word “canary” covers three different designs {{ cite.stackguard }}.
What the compiler emits
The textbook picture is a constant pushed on entry and compared on exit:
push 0x63873633 ; on entry: lay the canary down ... call scanf ; the vulnerable write happens in here ... cmp [esp], 0x63873633 ; before ret: is it still what we wrote? jnz .abort ret
Real code does not hard-code the value, for the obvious reason: a constant in the binary is a constant the attacker can read. Compile any function with a character array in it, disassemble it, and you get this instead. Four instructions carry the whole mechanism, and they are marked:
$ gcc -o demo demo.c $ objdump -d demo
000000000040059d <main>: 40059d: 55 push %rbp 40059e: 48 89 e5 mov %rsp,%rbp 4005a1: 48 81 ec b0 00 00 00 sub $0xb0,%rsp 4005a8: 89 bd 5c ff ff ff mov %edi,-0xa4(%rbp) 4005ae: 48 89 b5 50 ff ff ff mov %rsi,-0xb0(%rbp) 4005b5: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax ; 1. fetch the secret 4005be: 48 89 45 f8 mov %rax,-0x8(%rbp) ; 2. lay it just under the saved rbp 4005c2: 31 c0 xor %eax,%eax 4005c4: 48 8b 85 50 ff ff ff mov -0xb0(%rbp),%rax 4005cb: 48 83 c0 08 add $0x8,%rax 4005cf: 48 8b 10 mov (%rax),%rdx 4005d2: 48 8d 85 60 ff ff ff lea -0xa0(%rbp),%rax 4005d9: 48 89 d6 mov %rdx,%rsi 4005dc: 48 89 c7 mov %rax,%rdi 4005df: e8 8c fe ff ff callq 400470 <strcpy@plt> ; the unbounded copy 4005e4: 48 8b 45 f8 mov -0x8(%rbp),%rax 4005e8: 64 48 33 04 25 28 00 xor %fs:0x28,%rax ; 3. compare: zero iff intact 4005f1: 74 05 je 4005f8 <main+0x5b> 4005f3: e8 88 fe ff ff callq 400480 <__stack_chk_fail@plt> ; 4. abort 4005f8: c9 leaveq 4005f9: c3 retq
Two details do the real work. The secret lives at %fs:0x28, in the thread control block, which the ELF loader fills with fresh random bytes per process, so it is not in the file and not on the stack the overflow is walking. And the check is an xor rather than a cmp: it leaves zero exactly when the two agree, and it destroys the copy in the register on the way, so the value is not left lying in %rax for a later leak to find.
Compile the same file with -fno-stack-protector and all four marked lines disappear. That flag is not a curiosity: it is the first flag in the 1A lab build line, and this is what it was switching off.
$ gcc -o demo demo.c # canary present, on by default $ gcc -fno-stack-protector -o demo demo.c # no fetch, no xor, no __stack_chk_fail
Three flavors of secret
\0 \n \r \xff, not random at all. Every one of them terminates one of the string functions, so a strcpy cannot write past it without stopping. Public, and useless against a copy that does not care about terminators, such as memcpy.
Nothing in Req 1, 2 or 3, and that is what makes it the weakest thing in this lecture. A canary removes no requirement. It makes one route to Req 3 unreliable, and 1A already worked through which route that is and which ones it misses. What is new is where that puts it: a heuristic on a path rather than a policy on a property, which is exactly why it will turn out to have no band at all in the taxonomy this lecture closes on.
Guard pages and DEP
Both of these are the same idea spent twice: the hardware already checks a permission bit on every page it touches, so make the page table say what the attacker must not do. Guard pages forbid access, DEP forbids execution.
Guard pages
Place a page with no read, no write and no execute permission on each side of a region worth protecting. A linear overflow walking out of the region hits the guard, the MMU faults, and the process dies at the moment of the overflow instead of long afterwards in some unrelated place.
$ cat /proc/<chrome_pid>/smaps 24000000-24001000 ---p Size: 4 kB Rss: 0 kB VmFlags: mr mw me ac sd 24001000-24002000 rw-p Size: 4 kB Rss: 4 kB VmFlags: rd wr mr mw me ac sd 24002000-24004000 ---p Size: 8 kB Rss: 0 kB VmFlags: mr mw me ac sd
The middle mapping is a real allocation, rw-p and four resident kilobytes. Its neighbors read ---p: no permission of any kind, and Rss: 0 kB, meaning not one byte of physical memory is behind them. A guard page costs address space and a page-table entry, not RAM, which is why a browser can afford thousands of them {{ cite.partitionalloc }}.
A guard page works only if the attacker writes linearly, and only if the values written are never used as addresses to dereference. Both halves fail routinely.
An attacker who controls an index rather than a length writes at base + i for an i of their choosing and simply steps over the guard. The unlink primitive from 1B is exactly that: it does not walk anywhere, it writes one chosen value to one chosen address.
DEP, also written W⊕X
Every page gets an NX bit. Pages that hold data are writable and not executable, and pages that hold code are executable and not writable. No page is both, which is what the name says: writable exclusive-or executable.
This one is different from everything else in Part A, because it does not guard a route. It deletes Req 2 outright. The attacker can still write the payload wherever they like and can still divert control to it. The CPU refuses to decode it. Shellcode on the stack is finished.
$ execstack -s demo # mark the stack executable again: DEP off for this binary $ execstack -q demo X demo # X = executable stack. '-' would mean DEP is on
Req 2, completely. And the answer is the cleanest example in this lecture of why these defenses are called partial: if your payload may not be executable, stop bringing a payload. Code reuse chains fragments of the program's own already-executable code, and return-oriented programming makes that chaining general. DEP did not get weaker. The attack stopped needing the thing DEP takes away.
The exception that keeps DEP honest: a JIT compiler writes machine code at runtime and must then execute it. Every JIT is a hole in W⊕X that has to be closed by hand, one mapping at a time.
Address space layout randomization
Every exploit so far has written down an address: the address of the shellcode, of system, of the first gadget. ASLR attacks that sentence. If the layout is different in every run, the attacker cannot know the number to write.
Notice what it concedes before it begins. ASLR assumes the attacker can write to arbitrary places and makes no attempt to stop them. It removes the one thing that makes an arbitrary write useful, which is knowing where to point it.
At load time the kernel picks a fresh base for the stack, the heap, the executable (when it is built position-independent), each shared library and the bss {{ cite.pax_aslr }}. The heap moves again as it grows at runtime.
$ setarch -R ./demo buf @ 0x7fffffffe250 $ setarch -R ./demo buf @ 0x7fffffffe250 $ setarch -R ./demo buf @ 0x7fffffffe250
$ ./demo buf @ 0x7ffd4a1c7690 $ ./demo buf @ 0x7ffc9e2b3120 $ ./demo buf @ 0x7fff08d45a10
The left column is the world every lab in this course runs in, and it is deliberate. Address discovery is a separate problem that needs its own tools, and removing it leaves the part of the exploit worth practicing. The system-wide switch is /proc/sys/kernel/randomize_va_space, and setarch -R turns it off for one command.
It is all about the entropy
ASLR is the only defense here whose strength is a number, and the number is how many bits of the address the attacker has to guess. On 32-bit Linux the mmap base got 16 bits. Sixteen bits is 65,536 possibilities, and against a server that forks a fresh worker after each crash you can simply try them: Shacham and colleagues took a real Apache installation in a little over 200 seconds {{ cite.aslr_effective }}. Sixty-four-bit address spaces are the reason ASLR is still worth having, not any change in the idea.
Guessing is the route of last resort, and three others skip it entirely.
Leak one pointer. Only the base of each region is randomized. Distances inside a region are fixed at build time, so one leaked address, from a format string, an uninitialised read, Heartbleed, gives the attacker the base and therefore every other address in that region. This is why an information leak is worth an exploit chain of its own.
Overwrite part of an address. The low twelve bits of an address are the page offset and are never randomized. An attacker who can edit only the last byte or two of a pointer moves it a controlled distance without ever knowing where it points.
Find the piece that did not move. A binary not built as position-independent is loaded at its fixed link-time address, randomization or not, and its code is enough to build a chain. Whether the main executable participates in ASLR is still a per-binary build decision.
Not Req 3 itself, but the knowledge Req 3 needs. That is a genuinely different kind of defense from the three before it, and it has a matching weakness: knowledge can be leaked, and one leak undoes the whole region at once. Notice also that ASLR and DEP are the pair that made ROP necessary and then made it hard, which is why the two are almost always deployed together.
What a reference monitor is
A reference monitor is code that sees every reference to an object and decides whether it is allowed. You have used one: the system-call interface is a reference monitor for the kernel's objects, and it works because it sits at a hardware privilege boundary the program cannot step over.
That boundary is also its limit. The kernel sees open and write. It does not see the store instruction that just corrupted a return address, and it could not afford to: a trap per memory access is not a program, it is a stall. An inline reference monitor moves the checks into the program, by compiler or by binary rewriting, so a check costs a few instructions instead of a context switch, and can watch things the kernel never sees.
Program
│ syscall
─────┼───── privilege
▼
RM
│
Kernel
Protected by hardware. Coarse: only sees what crosses the line.
┌─────────┐
│ Program │
│ +RM │
└────┬────┘
─────┼───── privilege
Kernel
Fine-grained and cheap. Protected by nothing at all.
The policies you might inline
The technique is one thing and the policy is another. The same machinery enforces very different promises, and they are not equally strong:
| Policy | The promise |
|---|---|
| Complete memory safety | Access memory objects only in the intended way. The strongest, and the subject of Lecture 5. |
| Fault isolation | Each module touches only its own pre-determined data and code. Section 06. |
| No foreign code | Execute only code that was there at build time. DEP in software. |
| Control-flow integrity | Control transfers land only on legitimate targets. Section 07. |
| System-call sandboxing | Reach only a chosen subset of system calls. |
| Pointer and data integrity | Code pointers, or chosen data, always hold values they were given legitimately. |
| Data-flow integrity | Every read gets a value from a write the compiler said could reach it. |
Inlining the monitor put the checker and the attacker at the same privilege level, in the same address space. The syscall monitor was safe because the program could not reach it. This one is a few instructions and a few bytes of data sitting in memory the attacker is already corrupting.
So every design in Part B has to answer the same question: what stops the attacker from editing the check, jumping over it, or rewriting the data it consults? Software fault isolation answers with a dedicated register and an external verifier, control-flow integrity with a secret tag and a shadow stack that is itself sandboxed.
Software fault isolation
The policy is fault isolation, also called address sandboxing: confine every read and write of an untrusted module to one region M. Inside M the attacker may do whatever they like. Outside it they may do nothing. Take M to be [0xbe00, 0xbeff], so every legal address is one that starts with 0xbe.
The obvious implementation, and why it is not used
mov (ebp), eax
call (InRange(ebp)) jz error_label mov (ebp), eax
(ebp) is a register-indirect access: the address is whatever the register happens to hold. That is precisely the value an attacker controls, and precisely what the monitor has to constrain.
Correct, and a call plus a branch on every memory access in the program. That is not a tax anybody pays.
Coerce rather than check
Wahbe and colleagues made one move that changed the cost from a branch to two arithmetic instructions {{ cite.sfi }}. Do not ask whether the address is in M. Make it be in M: clear every bit above the region, then set the bits that name the region.
No branch, no call, nothing to predict wrong. The write still happens, it just lands somewhere harmless.
Where it breaks, and the fix
Recall the structural problem: the attacker is inside this address space and controls where execution goes. The three instructions are a sequence, and nothing says they must be entered at the top. Land directly on the mov, with a register the attacker filled, and the sandbox was never applied:
and ebp, 0x00ff
or ebp, 0xbe00
──▶ mov (ebp), eax ; jump straight here: ebp is whatever the attacker set
The fix is to make the coercion impossible to skip rather than impossible to reach. Reserve a dedicated register, call it reg1, and impose two rules on the whole module:
- Every memory access goes through
reg1. reg1is written only by the two coercing instructions.
The same attack, against a module that obeys them:
and reg1, 0x00ff
or reg1, 0xbe00
──▶ mov (reg1), eax ; jump straight here: reg1 still holds whatever the
; last coercion left in it, and that was inside M
Rule 2 says the only instructions that write reg1 are the coercing pair. So every value reg1 can hold is the result of (x AND 0x00ff) OR 0xbe00 for some x. That expression lands in 0xbe00–0xbeff for every x whatsoever: the AND throws away everything above the low byte, and the OR stamps the region bits back on. So the set of values reg1 can ever hold is a subset of M. reg1 always holds an address in M, by construction, not because a check passed.
Rule 1 says every memory access goes through that register. Put the two together and you get the property: at every load and store, on every path, the address is in M.
Read the argument again and notice what it never mentions: control flow. It does not care which instruction ran last, whether the block was entered at the top, or where the attacker aimed the program counter. That is exactly why it survives an adversary who owns the program counter, and it is why the earlier version, which relied on the three instructions running in order, did not.
What the attacker keeps is worth stating too, because it is not nothing. The x above is theirs, so the low byte is theirs, so they choose where in M they write. And the module pays a standing cost: a register is out of circulation for its entire lifetime, which on a machine with eight of them is a real price rather than a bookkeeping one.
And then do not trust the compiler either
Those two rules share a decisive property: they can be checked by reading the binary. You do not have to trust the compiler that produced the code, or the person who ran it. A separate verifier walks the instructions and confirms three things:
- The coercing instructions are present before every memory access.
- Every memory access uses the dedicated register.
- The dedicated register is written only by coercing instructions.
Minimize the trusted computing base, and separate the verifier from the enforcer. The trusted computing base (TCB) is everything that has to be correct for the security property to hold, and the smaller it is, the better the design. Here the SFI compiler can be enormous, buggy, or written by your adversary, and none of that matters, because nothing trusts its output: the compiler is not in the TCB. The TCB is the verifier, a few hundred lines that read instructions and answer yes or no.
This is the same shape as a proof that is hard to find and easy to check, and you will meet it again in every sandbox worth the name.
Req 1, but only outside M. SFI does not stop the buffer overflow, it makes the blast radius equal to the sandbox. That is why it is the right tool for running someone else's module inside your process, and the wrong tool for protecting a program from its own bugs. Chrome's Native Client shipped SFI to browsers on exactly this reasoning {{ cite.nacl }}, and WebAssembly's linear memory is the same bargain with the masking hidden in the design.
Control-flow integrity
Every attack in Lecture 3 ended the same way: an indirect transfer went somewhere the programmer never wrote. A return went to a gadget, a function pointer went to system, a vtable entry went to a fake object. CFI states the policy that forbids exactly this: every control transfer at runtime must follow an edge of the control-flow graph the compiler computed {{ cite.cfi }}.
Direct calls and jumps are already fine, their targets are baked into the instruction. The policy is only about the indirect transfers: computed jumps, calls through function pointers, and returns.
First attempt: compare against the answer
If a computed jump has exactly one legal destination, the check writes itself:
; before jmp ecx ; computed jump, target from memory ; after cmp ecx, 0x80480aa ; is it the one address we allow? jne error_label jmp ecx
This does not survive contact with real code. A function pointer that can reach four implementations needs four comparisons, and a return instruction can have hundreds of legal destinations.
Second attempt: label the destinations
Turn it around. Instead of listing the allowed addresses at the jump, put a tag at the start of each block that is allowed to be jumped to, and have the jump check the tag it lands on. If a site may reach g and h, then g and h carry the same tag. Cost: four instructions, and no list to walk.
cmp [ecx], 0x12345678 ; the tag word at the destination jne error_label ; wrong class, refuse the transfer lea ecx, [ecx+4] ; step over the tag word jmp ecx ; jump to the real first instruction
The tag must be a wide random value fixed at build time, like the 0x12345678 above, so that an attacker can neither guess one nor find the bytes lying around inside existing code. The small numbers below, 17, 23 and 55, are the equivalence-class names from the original paper's figure {{ cite.cfi }}, written short so that a person can read the picture.
Returns are the hard case
A tag says "this is a legal destination". A return needs something stronger: not just a legal return point, but the one this call came from. Tagging every call site in the program with one tag would let any function return into any caller, which is most of what ROP wants anyway.
When the set of callers is small, instrument the return like a computed jump. When it is not, keep a shadow stack: a second stack that holds return addresses and nothing else. It is written at exactly two moments in the program’s life.
on call push the return address onto the ordinary stack (the CPU does this)
push the same address onto the shadow stack too
on return compare the two copies
equal → return, as normal
differ → the ordinary copy was overwritten, abort
Nothing else is ever stored there: no locals, no arguments, no buffers, nothing an overflow can run into. That is the entire idea, and it is what makes the next sentence safe to say. The return address on the ordinary stack may be corrupted freely. It is still there, it is still read, it is simply not the copy that is believed.
return address 0x41414141 saved rbp 0x41414141 buf[16] AAAAAAAAAAAAAAAA
return address 0x004017a2
nothing else is kept here,
so nothing can reach it
Two designs hide behind the word “compared”, and they answer different questions. Detect: compare the copies and abort on a mismatch, which turns the hijack into a crash. Repair: ignore the ordinary copy and return to the shadow one, which leaves the program running and denies the attacker even the crash. The first is what hardware shipped. The second costs nothing extra once the second copy exists.
The shadow stack is memory in the attacker's address space, so what protects it? The classical answer is software fault isolation. Put the shadow stack outside the sandbox and let the coercion keep every one of the program's writes inside it. The two techniques are not alternatives, they compose, and neither is sufficient alone.
Powerful in theory
If the CFG were exact, CFI would end control-flow hijacking as a bug class. Every exploit in Lecture 3 needs a transfer that is not in the graph, and there would be no such transfer to be had.
Take four functions and the call sequences the program can actually produce:
A → C → D
A → B → C
A → D
Collect the edges the legitimate sequences imply, and you get five: A→B, A→C, B→C, B→D, C→D. Both bad sequences now fail, and it is worth seeing exactly where. A→D is not an edge, so it is refused at the first step. A→C→B→D gets through A→C and then dies on C→B, which never occurs in any legitimate run. Only B→C does, and edges have a direction.
Both sequences were caught because each contained a transfer that is not an edge. That is a property of this example, not a theorem. CFI is stateless: it checks each transfer against the graph and never against the path taken to reach it. A sequence built entirely out of legal edges passes, however impossible that sequence is in a real run. An attacker who can assemble one is working inside the policy rather than around it.
The CFG is not exact. Building it means answering, for every function pointer in the program, which functions it might point to, and that is pointer analysis: undecidable in general, and in practice a hard approximation over a large C++ program with indirect calls through vtables, callbacks and dynamically loaded libraries. Every analysis must therefore over-approximate, because a missing edge would break a correct program. Every extra edge is a transfer the attacker is permitted to make.
That gap is the entire attack surface of deployed CFI. Coarse-grained schemes collapse the graph down to a handful of equivalence classes, and once a class contains enough useful functions, an attacker can build a chain without ever leaving it. Carlini and Wagner showed that against several deployed CFI systems, with call-preceded gadgets and a return-oriented chain that stays inside the permitted set throughout {{ cite.ropstill }}.
None of which stopped it shipping. What runs on your machine today sits in two places.
In the compiler. Clang's -fsanitize=cfi checks indirect calls against types rather than a whole-program CFG {{ cite.clang_cfi }}. Microsoft's Control Flow Guard, which the Visual Studio compiler emits under /guard:cf, keeps a bitmap of valid call targets and checks it before every indirect call {{ cite.cfguard }}.
In the silicon. Both halves of this section eventually became hardware. Intel CET gives the CPU a real shadow stack it enforces itself, plus indirect branch tracking, where an indirect jump must land on an endbr64 instruction, which is a one-bit tag. Arm ships the same two ideas as pointer authentication and BTI. Look for endbr64 at the top of functions the next time you read a modern disassembly: that is this section, compiled in.
Req 3, restricted to the edges of an over-approximated graph. Strictly the strongest thing in this lecture, and still partial for a reason that has nothing to do with the idea and everything to do with the analysis: the policy is only as tight as the CFG, and the CFG is a guess that has to err on the generous side.
The eternal war
Szekeres and colleagues did something worth copying: rather than listing defenses, they drew the attack as a graph and asked which edge each defense cuts {{ cite.eternalwar }}. Every exploit in this course is a path down these six stages, and it succeeds if any path to the bottom is open.
Read downward. Every defense in Part A and Part B is a cut on one edge, low in the graph, long after the bug has already happened. The pointer went out of bounds at stage 1 in every single case, and nothing here was watching stage 1.
Two of them do not appear on any edge. Stack canaries and guard pages have no band in this diagram, and that is not an oversight. They do not enforce a property at all. They make one particular route between stages 2 and 3, the contiguous walk through adjacent memory, unreliable for the attacker. That is genuinely useful, it is why both are switched on by default, and it is also why both are stepped around by any primitive that writes at a chosen address rather than walking to one.
Cut an edge and the graph reroutes: DEP cut stage 6 and the answer was ROP, ASLR cut stage 4 and the answer was an information leak, CFI cut stage 5 and the answer was the imprecision of the CFG. The war is eternal because the bug at stage 1 was never addressed. Lecture 5 goes there.