Home

Awesome

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:

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.

<p align="center"> <img src="images/layout.png" width="60%" alt="LowFat memory layout" border="1"> </p>

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:

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 || 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.

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.

<p align="center"> <img src="images/results.png" width="60%" alt="LowFat SPEC2006 timings"> </p>

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:

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

<p align="center"> <img src="images/results_opt.png" width="60%" alt="Optimized LowFat SPEC2006 timings"> </p>

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:

Most of these caveats (such as NULL overflows, the operating system, custom stacks, clone, runtime hardening and low-level hacks) are implementation issues that may be addressed by future updates.

FAQ

Q: Does LowFat handle one-past-end-of-the-array pointers allowable under the C standard?

A: Yes is does. LowFat handles this case by always "rounding up" object sizes by at least one byte, meaning that the pointer to the end of an object (a.k.a. one-past-end-of-the-array) is always within the allocation bounds. This trick was "borrowed" from the Boehm conservative garbage collector, which must also handle such pointers to avoid erroneously collecting live objects.

Q: Can LowFat protect global variables?

A: Yes, for statically allocated globals. Support for globals was only added after the publication of [1] and [2]. For more details regarding globals, see our technical report [3].

Q: Why do we need LowFat when we already have AddressSanitizer?

LowFat and AddressSanitizer are similar tools in that both can detect OOB-memory errors. The main difference between the two tools is the underlying technology, and each approach has its pros and cons.
AddressSanitizer inserts "poisoned redzones" between objects and detects overflows into these zones. The main advantages of AddressSanitizer over LowFat are:

The main disadvantages of AddressSanitizer over LowFat are:

The latter makes AddressSanitizer less suitable for program hardening for cases where the attacker can control the offset.

Q: Why do we need LowFat when we already have SoftBound/MPX?

A: Both SoftBound and MPX have the advantage that they are designed to detect sub-object bounds overflows, something which LowFat does not do directly (however, see below). However, both SoftBound and MPX have compatibility problems, namely by changing the ABI (SoftBound) and with multi-threaded code (shared state in contention).

Q: Can LowFat detect other types of errors, such as:

A: Yes with suitable extensions. See our paper "EffectiveSan: Type and Memory Error Detection using Dynamically Typed C/C++" that was published at PLDI'2018. We plan to release EffectiveSan sometime in 2018 (see here: https://github.com/GJDuck/EffectiveSan).

Follow-up Work

Versions

The released version of LowFat differs from the prototype evaluated in [1] and [2]. To replicate the results of [2] as closely as possible, (1) ensure that LowFat has been built with lzcnt support, and (2) compile your program with the following options:

    -fsanitize=lowfat -O2 -mllvm -lowfat-no-replace-globals

With these options enabled, the performance overhead of LowFat reduces to 59%, which is comparable to the (+alias) results reported in [2].

Thanks

This research was partially supported by a grant from the National Research Foundation, Prime Minister's Office, Singapore under its National Cybersecurity R&D Program (TSUNAMi project, No. NRF2014NCR-NCR001-21) and administered by the National Cybersecurity R&D Directorate.

This research was partially supported by the UK EPSRC research grant EP/L022710/1.

Bugs

LowFat should be considered beta quality software. It has not yet been extensively tested on software other than the SPEC2006 benchmark suite.

Please submit bug reports to https://github.com/GJDuck/LowFat/issues.

Bibliography

[1] Gregory J. Duck, Roland H. C. Yap, Heap Bounds Protection with Low Fat Pointers, International Conference on Compiler Construction, 2016

[2] Gregory J. Duck, Roland H. C. Yap, Lorenzo Cavallaro, Stack Bounds Protection with Low Fat Pointers, The Network and Distributed System Security Symposium, 2017

[3] Gregory J. Duck, Roland H. C. Yap, An Extended Low Fat Allocator API and Applications, Technical Report, 2018.