Detecting Buffer Overflows and Stale Pointers with Guard Pages

AuthorKevin Nygaard
Published

Strategically placed around around memory allocations, inaccessible guard pages leverage the processor's virtual memory system to detect common memory-based errors: buffer overflows and underflows, and null and stale pointer dereferences. Accessing a guard page immediately halts program execution, pinpointing the error for correction.

Contents

1 Physical Memory

In the early days of computing, memory was scarce and expensive: 64 kilobytes1 was respectable, and 1,024 kilobytes was the luxurious maximum. As technology advanced to 32-bit processors, memory quickly surpassed megabytes into gigabytes, holding 10,000 to 100,000 times more data their predecessors. 4 billion, the largest value of a 32-bit word, set the memory ceiling to 4 gigabytes.2

With today's 64-bit processors, memory ranges between 8 to 64 gigabytes, with maximums in the terabyte range. However, even a trillion bytes is dwarfed in comparison to the maximum value of a 64-bit word: 18 quintillion, 18,000,000 trillion. With 64-bit addresses, 1 terabyte only uses 0.00001% of the potential address space.3

Imagine if computers had enough memory to fill that space; finding a place to put any chunk of data would be easy. However, you don't need to imagine: programs already live in this fantasy world.

2 Virtual Memory

For security and efficiency, each program runs in its own virtual address space, an entire 64-bit region which the operating system (OS), with help from the processor's memory management unit (MMU), maintains and translates on-the-fly to the physical address space. This virtual space is byte addressable, but maintained in larger units called pages (typically 4 to 16 kB).

For example, a program requests two new pages of memory. The OS finds an unmapped region in the program's virtual address space and marks two virtual pages as accessible, but defers assigning physical memory resources to them. When the program writes data to the first page, the OS receives a page fault, whereupon it finds and associates a free physical page for the virtual one. If a free page is unavailable, the OS finds an infrequently accessed one (a cold page) and saves its contents to disk (called swapping), allowing it to be safely repurposed elsewhere.

In this way, the program believes it lives in a world of practically endless contiguous bytes. The OS maintains the illusion by juggling the limited number of physical pages between the programs and the disk. This translation mechanism is also advantageous for another purpose: finding bugs.

3 Guard Pages

When a program accesses an unmapped region, the OS raises an exception and halts the program. Furthermore, programs can modify the permissions of mapped pages, making the readable, readable and writable, inaccessible, etc. Intentionally inaccessible pages (guard pages) strategically placed pinpoint hard-to-find memory corruption bugs like buffer overflows and stale pointer dereferences.4

3.1 For Bounds Checking

Bookending an array with guard pages catches accesses immediately before and after the allocation – underflows and overflows respectively:

Three diagrams the position of allocations relative to guard pages
Figure: Page layouts of memory allocations and guard pages

Above shows three different regions of virtual memory, each a sequence of 6 pages with addresses increasing from left to right. The grey first and last segments are part different regions: they may or may not be accessible. The red guard pages are inaccessible, causing a segmentation violation or bus error whenever accessed. The green allocation region in between is the requested array size: the user receives a pointer to the left edge of this region, the beginning of the array.

In the first two cases, the array is a non-multiple of the page size, roughly 1.25 pages. However, due to the page-based nature of virtual memory, the array is over-allocated to 2 pages, leaving a grey waste region. Accessing this waste region is valid, but undesirable; venturing beyond the allocation but stopping short of the guard page is an undetectable error. However, by sliding the allocation to the left or right, the waste moves after or before it respectively, biasing which error condition is immediately detected. Furthermore, running the program twice with the same input, once in each configuration, detects both errors cumulatively.

In the first case with the left-aligned allocation, underflows are immediately detected against the beginning guard page. In the second case with the right-aligned allocation, overflows are immediately detected against the ending guard page. In the third case with the page-aligned allocation, both underflows and overflows are immediately detected.

The code below implements this technique:

#include <sys/mman.h>
#include <unistd.h>
void *Alloc(int Size, int PreferOverflowChecks) {
    int PageSize    = getpagesize();
    int PageCount   = (Size + PageSize - 1) / PageSize;
    int RoundedSize = PageSize * PageCount;
    int TotalSize   = PageSize + RoundedSize + PageSize;
    char *Memory    = mmap(0, TotalSize,
        PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
    char *Ret = Memory + PageSize;
    mprotect(Ret, RoundedSize, PROT_READ | PROT_WRITE);
    if (PreferOverflowChecks) {
        Ret += RoundedSize - Size;
    }
    return Ret;
}

getpagesize(3) returns the system's page size (16 kB on Arm Macs). Rounding up the requested allocation size, Size, to the nearest page boundary gives PageCount. RoundedSize is PageCount in bytes, and TotalSize adds space for two guard pages. From the system, mmap(2) requests TotalSize bytes of memory in a contiguous chunk, which is inaccessible by default by the PROT_NONE flag. mprotect(2) enables access to the middle pages for data, but leaves the first and last page inaccessible as guard pages.5 With PreferOverflowChecks, the requested allocation butts up against the end guard page; otherwise, it starts flush against the beginning guard page.

See the resources on mmap() and mprotect() for more details. For Windows systems, see the resources on VirtualAlloc() and VirtualProtect().

3.2 For Memory Allocators

The example above can be extended to a general purpose memory allocator, detecting underflow, overflow, and use-after-free errors. Marking an allocation as inaccessible when it is freed catches stale pointer dereferences:

void Free(void *User, int Size, int PreferOverflowChecks) {
    int PageSize    = getpagesize();
    int PageCount   = (Size + PageSize - 1) / PageSize;
    int RoundedSize = PageSize * PageCount;
    int TotalSize   = PageSize + RoundedSize + PageSize;
    char *Memory    = User - PageSize;
    if (PreferOverflowChecks) {
        Memory -= RoundedSize - Size;
    }
    mprotect(Memory, TotalSize, PROT_NONE);
    madvise(Memory, TotalSize, MADV_FREE);
}

Given the initial arguments and return value from Alloc(), Free() finds the initial value returned by mmap() by reversing the arithmetic. mprotect() the marks the entire region as inaccessible, and madvise(2) frees the underlying resources while keeping the region mapped as inaccessible. munmap(2) is similar, but also unmaps the region – an undesirable behavior. This permits partial or full reuse of the region, undermining the goal of catching memory bugs.

See the resources on madvise() and munmap() for more details. For Windows systems, see the resources on VirtualFree().

4 Limitations

Guard pages are a powerful development tool for catching memory bugs early, but they waste half a page of memory on average, and significantly more with many small allocations. The page-sized and alignment restrictions also weaken the detection effectiveness of a single run, reducing confidence in complex, non-deterministic systems where repeatable runs are difficult or impossible. Furthermore, the extra memory reduces locality and increases aliasing, yielding poor cache utilization and slow performance. Exercise prudence when considering use in production code.

For the general purpose memory allocator, leaking address spaces is insignificant except for long running programs with large and frequent memory allocation patterns – however, exhausting a 64-bit address space indicates deeper problems.

Thanks for reading; I hope this brief overview on virtual memory and guard pages has been helpful. Feedback and corrections are welcome via email. ✚

See Also

Footnotes

  1. ↑ Unless stated otherwise, the magnitude prefixes k-, M-, T-, etc are binary (1,024) rather than decimal (1,000). In IEC 60027-2, the International Electrotechnical Commission defined kibibytes (KiB), mibibytes (MiB), etc for binary-based magnitudes, redefining the de facto kilobytes (kB), megabytes (MB), etc for decimal-based magnitudes, creating needless confusion in the name of pedantry.
  2. ↑ Relating processor width to memory gives a sense of scale, but it's an oversimplification. An n-bit processor natively operates on n-bit words, but data is sent into and out of the chip in d-bit words with a-bit addresses on a bus interface. These figures are related, but need not be identical. For example, the Zilog Z80 is an 8-bit processor with an 8-bit data bus and 16-bit address bus, giving 64 kB of address space; the Intel 8086 is a 16-bit processor with a 20-bit address bus, giving 1 MB of address space. However, the address bus width sets the theoretical memory size; hardware and software limitations determine the actual amount.
  3. ↑ This too is an oversimplification for scale. 64-bit processors use less than 64 bits for addressing. Using between 48 to 56 bits gives an address range between 256 TB to 4 PB; regardless, the space is still largely unused. (However, techniques like pointer tagging store application-specific data in these unused bits, efficiently storing metadata with the pointer itself, like data type, allocation size, reference count, etc.)
  4. ↑ According to MITRE's Common Weakness Enumeration (CWE) report, the top 25 "most dangerous, common, and impactful software weaknesses" include: number 1, out-of-bounds writes; number 5, out-of-bounds reads; and number 7, use after free.
  5. ↑ An equivalent, but inferior, method: request a read/write region, then mark the first and last pages as PROT_NONE. This approach has two drawbacks: 1) it requires an additional mprotect() system call, and 2) it returns an accessible region should mprotect() fail. (Both mprotect() and mmap() need error handling, but explicit region access, rather than explicit region denial, is better defensive programming.)

Further Resources