The Synthetix project [18, 1, 2, 24] introduced a notion called ``quasi-invariants.'' Quasi-invariants are state properties that hold true for a while, but may change without notice. Quasi-invariants are used to specify optimistic specializations: code optimizations that are valid only while the quasi-invariants hold. We have extended this work to treat return addresses on the stack as quasi-invariant during the activation lifetime of the function. The return address is read-only (invariant) while the function is active, thus preventing effective buffer overflow against the stack.
MemGuard [3] is a tool developed
to help debug optimistic specializations by locating code statements that
change quasi-invariant values. MemGuard provides fine-grained memory protection:
individual words of memory (quasi-invariant terms) can be designated as
read-only, except when explicitly written via the MemGuard API. We have
used MemGuard to produce a more secure, if less performant, version of
the StackGuard compiler.
push a push b move 164 into a move arg[0] into b trap 0x80 pop b pop aFigure 5: Function Prologue Code: Protecting the Return Address With MemGuard
MemGuard is used to prevent buffer overflow attacks by protecting a return address when a function is called, and un-protecting the return address when the function returns. The protection and un-protection occur in precisely the same places as the canary placement and checks described in Section 3.1: the function_prologue and function_epilogue functions. Figure 5 shows the prologue code sequence for MemGuard. The epilogue code sequence is identical, but uses system call 165 instead of 164.
MemGuard is implemented by marking virtual memory pages containing quasi-invariant terms as read-only, and installing a trap handler that catches writes to protected pages, and emulates the writes to non-protected words on protected pages. The cost of a write to a non-protected word on a protected page is approximately 1800 times the cost of an ordinary write. This is an acceptable cost when quasi-invariant terms are in quiet portions of the kernel's address space, and when MemGuard is primarily used for debugging.
This cost is not acceptable when the protected words are located near the top of the stack, next to some of the most frequently written words in the program. MemGuard was originally designed to protect variables within the kernel. To protect the stack, MemGuard had to be extended in several ways:
We use these registers as a cache of the most recently protected return addresses. The goal is to eliminate the need for the top-most page of the stack to be read-only, to eliminate page faults resulting from writes to variables at the top of the stack. Because of the locality behavior of stack variables, restoring write privileges to the top of the stack should handle most of the writes to stack variables.
It is only probabilistically true that protecting the four most recent return addresses will capture all protection needs for the top of the stack. However, if the compiler is adjusted to emit stack frames with a minimum size of 1/4 of a page, then it is always true that 4 registers will cover the top page. The time/space trade-off implied by this approach can be continuously adjusted, reducing the minimum size of stack frames to reduce space consumption, and also increasing the probability that the top page of the stack actually will require MemGuard protection, with its associated costs.