LowFat

LowFat: Lean C/C++ Bounds Checking with Low-Fat Pointers

LowFat is a new bounds checking system for the x86-64 based on the idea low-fat pointers. LowFat is designed to detect object out-of-bounds errors (OOB-errors), such as buffer overflows (or underflows), that are a common source of crashes, security vulnerabilities, and other program misbehavior. LowFat is designed to have low overheads, especially memory, compared to other bounds checking systems.

The basic idea of low-fat pointers is to encode bounds information (size and base) directly into the native bit representation of a pointer itself. This bounds information can then retrieved at runtime, and be checked whenever the pointer is accessed, thereby preventing OOB-errors. Low-fat pointers have several advantages compared to existing bounds checking systems, namely:

• Memory Usage: Since object bounds information is stored directly in pointers (and not is some other meta data region), the memory overheads of LowFat is very low.
• Compatibility: Since low-fat pointers are also ordinary pointers, LowFat achieves high binary compatibility.
• Speed: Low-fat pointers are fast relative to other bounds-checking systems.

The LowFat system uses the low-fat pointer encoding described in papers [1] and [2]. The basic idea is to subdivide the programs virtual address space into several large regions, where each region is responsible for the allocation of objects of a given fixed size range, as illustrated by the diagram below.

The first region contains the programs text, data, bss, etc., segments as usual. The subsequent regions are used for low-fat pointer allocation. For example, region #1 is used for allocations of size 1-16bytes, region #2 for allocations of size 17-32bytes, etc. Furthermore, all LowFat allocated objects are aligned to allocation-size boundaries. Using these properties, the object's bounds information can be reconstructed based on the pointer value. As an example, consider the allocation:

    p = malloc(10);

The LowFat system will allocate p = 0x8997f2820 (or similar value). Under the default LowFat configuration, addresses 0x800000000-0xfffffffff are reserved for objects of size 1-16 bytes (the original allocation size of 10bytes is "rounded up" to 16bytes, as is common practice with malloc implementations).

Given the pointer q = p + 5 = 0x8997f2825, we can reconstruct the size and base of the object pointed to by q by working backwards:

• Since q is within the range (0x800000000..0xfffffffff) we know that the allocation size of the object pointed to by q is 16bytes.
• Since q - (q mod 16) = 0x8997f2820 we know that the base address of the object pointed to by q is 0x8997f2820.

Next, consider the following (trivial) function:

    char get(char *q, int i)
    {
        return q[i];
    }

The LowFat system will instrument the function into something like the following:

    char get(char *q, int i)
    {
        char *q_base = base(q);
        size_t q_size = size(q);
        char *r = q + i;
        if (r = q_base + q_size)
            report_oob_error();
        return *r;
    }

Here the size and base operations are implemented as described above. If we consider the function call get(q, 20), then this will be detected as an OOB-error since the read object is outside the object bounds (0x8997f2820..0x8997f282f). LowFat will report the error and abort the program:

    LOWFAT ERROR: out-of-bounds error detected!
            operation = read
            pointer   = 0x8997f2825 (heap)
            base      = 0x8997f2820
            size      = 16
            overflow  = +20

In addition to heap objects, the LowFat system can also protect stack and global objects. The description above is only a very high-level overview. In reality there are many other issues and technical details, see [1] and [2] for more information.

Building

To build LowFat from source just run the build.sh script.

    $ tar xvfz lowfat-src.tar.gz
    $ cd lowfat-src
    $ ./build.sh

Note that building LowFat may take some time since it seems to build a modified LLVM-4.0 system. If clang-4.0 is not already installed the build script will attempt to bootstrap a version.

After the build is complete, LowFat can be used by invoking a modified version of clang-4.0 in the build/bin/ sub-directory:

    build/bin/clang
    build/bin/clang++

Note that the modified clang can be invoked directly. There is no need to install it on your system (but you can if you want to).

Usage

LowFat is implemented as a modified version of clang-4.0. To compile a program (prog.c) with LowFat instrumentation enabled, simply compile as follows:

    $ /path/to/lowfat/build/bin/clang -fsanitize=lowfat -O2 -o prog prog.c

C++ is also supported:

    $ /path/to/lowfat/build/bin/clang++ -fsanitize=lowfat -O2 -o prog prog.cpp

LowFat supports several command line options that are listed below. Note that to pass an option to LowFat it must be preceded by -mllvm on the clang command-line, e.g. (-mllvm -lowfat-no-check-reads), etc.

• -lowfat-no-check-reads: Do not OOB-check reads
• -lowfat-no-check-writes: Do not OOB-check writes
• -lowfat-no-check-escapes: Do not OOB-check pointer escapes (of any kind)
• -lowfat-no-check-memset: Do not OOB-check memset
• -lowfat-no-check-memcpy: Do not OOB-check memcpy or memmove
• -lowfat-no-check-escape-call: Do not OOB-check pointer call escapes
• -lowfat-no-check-escape-return: Do not OOB-check pointer return escapes
• -lowfat-no-check-escape-store: Do not OOB-check pointer store escapes
• -lowfat-no-check-escape-ptr2int: Do not OOB-check pointer pointer-to-int escapes
• -lowfat-no-check-escape-insert: Do not OOB-check pointer vector insert escapes
• -lowfat-no-check-fields: Do not OOB-check field access (reduces the number of checks)
• -lowfat-check-whole-access: OOB-check the whole pointer access ptr..ptr+sizeof(*ptr) as opposed to just ptr (increases the number and cost of checks).
• -lowfat-no-replace-malloc: Do not replace malloc() with LowFat malloc() (disables heap protection)
• -lowfat-no-replace-alloca: Do not replace stack allocation (alloca) with LowFat stack allocation (disables stack protection)
• -lowfat-no-replace-globals: Do not replace globals with LowFat globals (disables global variable protection)
• -lowfat-no-check-blacklist blacklist.txt: Do not OOB-check the functions/modules specified in blacklist.txt
• -lowfat-no-abort: Do not abort the program if an OOB memory error occurs

The LowFat distribution also includes a (lowfat-ptr-info) tool that can print information about a given pointer value. For example:

    $ /path/to/lowfat/build/bin/lowfat-ptr-info 0x8997f2825
    ptr    = 0x8997f2825
    type   = heap
    region = #1 (0x800000000)
    base   = 0x8997f2820
    size   = 16 (0x10)
    magic  = 1152921504606846977 (0x1000000000000001)
    offset = 5

Experiments

We experimentally evaluate LowFat against the SPEC2006 benchmark suite. The results for the default configuration are shown below.

Overall we see that LowFat introduces a 64% performance overhead.

We can also optimize LowFat for software hardening, i.e., preventing buffer overflows in production software. To do this it is important to optimize the overhead versus protection ratio, since the default overhead of 64% is generally too costly for many applications. We can enable several options that lower the overheads of LowFat at the expensive of also lowering runtime protections:

• -lowfat-no-check-reads: Most (but not all) security exploits require a memory write operation. We can significantly lower overheads by not bounds checking memory reads.
• -lowfat-no-check-escapes: Most (but not all) OOB-pointer escapes occur in conjunction with an OOB-memory access. We can lower overheads by not bounds checking pointer escapes.
• -lowfat-no-check-fields: OOB-errors due to (non-array) field access are less common than those caused by array/buffer overflows. We can lower overheads by only bounds checking array/buffer access.

After applying these optimizations, we see that overall overhead LowFat is significantly reduced to ~9.8% overall:

Note that optimized LowFat can even make some benchmarks go faster. This is because the LowFat heap allocator happens to be faster than the default malloc for these examples. The overhead can also be further reduced by forcing object sizes to be powers-of-two, meaning that LowFat can use bit-masking operations to calculate an object's base address as opposed to the default fixed point arithmetic. However, enabling this mode requires a recompilation:

    rm -rf build/
    ./build.sh sizes2.cfg 32

The overhead further drops to ~7.8% overall.

Since LowFat does not explicitly store bounds information in separate meta data, the memory overheads of LowFat are very low (~3%) for SPEC2006 [2]. If powers-of-two sizes are used, memory overhead increases to (~12%).

Caveats

There are a few caveats with the LowFat system, and are listed below:

• Sub-Object versus Object versus Allocation Bounds: During allocation, LowFat may "round-up" the requested allocation size (a.k.a. object size) to some larger value (allocation size). The space left at the end of the object will be unused "padding". LowFat protects allocation bounds only, and thus cannot detect overflows into this unused padding. Similarly LowFat offers no protection against sub-object bounds overflows and any related attacks.
• Escaping Pointers: By default, LowFat prevents OOB-pointers being accessed (written to or read from) or escaping (passed to another function, returned, stored in memory, or cast to an integer). Escaping pointers are disallowed since they can disguise OOB-errors, e.g. reading from an OOB-pointer passed to another function. Bounds checking of pointer escapes can be disabled using the (-mllvm -lowfat-no-check-escapes) options.
• Global Variables: LowFat can only protect global variables that occur in the main executable, and not any that occur in dynamically linked libraries. This is because the dynamic linker does not support section directives and the linker scripts required to place global objects in the correct LowFat positions. (Note that the program will still compile and run, only that overflows in such globals will not be detected.) Another caveat is that LowFat must move global objects outside of the first 4GB of the virtual address space. To support this, the executable must be compiled using the large code model (-mcmodel=large), which usually incurs a performance penalty. The large code model is automatically enabled whenever the -fsanitize=lowfat option is passed to clang. LowFat also does not protect globals with exotic linkage, custom section, or annotated with an incompatible alignment attribute.
• NULL overflows: Currently LowFat does not protect against NULL pointer overflows, e.g. NULL[idx] can access any address. There are some ideas but this is left as future work.
• Operating System: The current LowFat implementation supports Linux only. In principle, LowFat could be ported to other systems such as Windows, but this requires some developer effort, and thus is not supported by the current release.
• Modern 64bit CPUs: In order to run "full" LowFat you need a reasonably modern 64bit CPU that supports lzcnt, bmi and bmi2.
• Stack Object Ordering: Some programs assume stack objects are ordered, i.e., more recently allocated objects occur at lower addresses than older objects (for stack-grows-down). LowFat wi