Repository files navigation

LowFat is a new bounds checking system for thex86-64 based on the idealow-fat pointers. LowFat is designed to detect objectout-of-boundserrors (OOB-errors), such as buffer overflows (or underflows), that are acommon source of crashes, security vulnerabilities, and other programmisbehavior. LowFat is designed to have low overheads, especially memory,compared to other bounds checking systems.

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

• Memory Usage: Since object bounds information is stored directly inpointers (and not is some other meta data region), the memory overheads ofLowFat is very low.
• Compatibility: Since low-fat pointers are also ordinary pointers, LowFatachieves 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 spaceinto several largeregions, where each region is responsible for theallocation of objects of a given fixed size range, as illustrated by thediagram below.

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

    p = malloc(10);

The LowFat system will allocatep = 0x8997f2820 (or similar value).Under the default LowFat configuration, addresses0x800000000-0xfffffffffare reserved for objects of size1-16 bytes (the original allocation size of10bytes is "rounded up" to 16bytes, as is common practice withmallocimplementations).

Given the pointerq = p + 5 = 0x8997f2825, we can reconstruct the size andbase of the object pointed to byq by working backwards:

• Sinceq is within the range (0x800000000..0xfffffffff) we know that theallocation size of the object pointed to byq is 16bytes.
• Sinceq - (q mod 16) = 0x8997f2820 we know that the base address ofthe object pointed to byq is0x8997f2820.

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 thefollowing:

    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 thesize andbase operations are implemented as described above. Ifwe consider the function callget(q, 20), then this will be detected as anOOB-error since the read object is outside the object bounds(0x8997f2820..0x8997f282f). LowFat will report the error and abort theprogram:

    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 andglobal objects. The description above is only a very high-level overview. Inreality there are many other issues and technical details, see [1] and [2] formore information.

To build LowFat from source just run thebuild.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 amodified LLVM-4.0 system. Ifclang-4.0 is not already installedthe build script will attempt to bootstrap a version.

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

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

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

LowFat is implemented as a modified version ofclang-4.0. To compile aprogram (prog.c) with LowFat instrumentation enabled, simply compile asfollows:

    $ /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 theclang 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 pointerpointer-to-int escapes
• -lowfat-no-check-escape-insert: Do not OOB-check pointer vector insertescapes
• -lowfat-no-check-fields: Do not OOB-check field access (reduces thenumber of checks)
• -lowfat-check-whole-access: OOB-check the whole pointer accessptr..ptr+sizeof(*ptr) as opposed to justptr(increases the number and cost of checks).
• -lowfat-no-replace-malloc: Do not replace malloc() with LowFatmalloc() (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 thefunctions/modules specified inblacklist.txt
• -lowfat-no-abort: Do not abort the program if an OOB memory erroroccurs

The LowFat distribution also includes a (lowfat-ptr-info) tool that canprint 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

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 forsoftware hardening, i.e., preventing bufferoverflows in production software. To do this it is important to optimize theoverhead versus protection ratio, since the default overhead of 64% isgenerally too costly for many applications. We can enable several options thatlower the overheads of LowFat at the expensive of also lowering runtimeprotections:

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

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

Note that optimized LowFat can even make some benchmarks go faster. This isbecause the LowFat heap allocator happens to be faster than the defaultmalloc for these examples. The overhead can also be further reduced byforcing object sizes to be powers-of-two, meaning that LowFat can usebit-masking operations to calculate an object's base address as opposed to thedefault fixed point arithmetic. However, enabling this mode requires arecompilation:

    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 metadata, the memory overheads of LowFat are very low (~3%) for SPEC2006 [2]. Ifpowers-of-two sizes are used, memory overhead increases to (~12%).

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 theend of the object will be unused "padding". LowFat protects allocation boundsonly, and thus cannot detect overflows into this unused padding. SimilarlyLowFat offers no protection against sub-object bounds overflows and anyrelated attacks.
• Escaping Pointers:By default, LowFat prevents OOB-pointers beingaccessed (written to or readfrom) orescaping (passed to another function, returned, stored in memory,or cast to an integer). Escaping pointers are disallowed since they candisguise OOB-errors, e.g. reading from an OOB-pointer passed to anotherfunction. 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 thedynamic linker does not supportsection directives and the linker scriptsrequired to place global objects in the correct LowFat positions.(Note that the program will still compile and run, only that overflows insuch globals will not be detected.)Another caveat is that LowFat must move global objects outside of the first4GB of the virtual address space. To support this, the executable must becompiled using thelarge code model (-mcmodel=large), which usually incursa performance penalty. Thelarge code model is automatically enabledwhenever the-fsanitize=lowfat option is passed toclang. LowFat alsodoes not protect globals with exotic linkage, custom section, or annotatedwith 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 leftas future work.
• Operating System: The current LowFat implementation supports Linux only.In principle, LowFat could be ported to other systems such as Windows, butthis requires some developer effort, and thus is not supported by thecurrent release.
• Modern 64bit CPUs:In order to run "full" LowFat you need a reasonably modern 64bit CPU thatsupportslzcnt,bmi andbmi2.
• Stack Object Ordering:Some programs assume stack objects are ordered, i.e., more recently allocatedobjects occur at lower addresses than older objects (for stack-grows-down).LowFat will break these assumptions.Note that the low-fat stack allocator can be disabled by the(-mllvm -lowfat-no-replace-alloca) command-line options.
• Custom Stacks:Custom stacks (e.g.,sigaltstack or somepthread_create configurations)are not currently supported by LowFat instrumented code.
• Fork and Clone:The LowFat stack uses shared memory as an optimization (see [2] for details).This also causes a problem withfork andclone meaning that the parent andchild will share the same stack memory (usually leading to a crash). Toprevent this, the LowFat runtime interceptsfork and manually copies thestack, which makes LowFatfork somewhat slower than nativefork. Also,programs that callclone directly or any otherfork-like functions are notcurrently supported.
• UglyGEPs:Theclang optimization pipeline may create OOB-pointers that are detectedby LowFat. To prevent false positives, such pointers are currently ignoredfor pointer-to-integer escape instrumentation.A better solution to this problem is left as future work.
• LowFat Runtime Hardening: The LowFat runtime itself has not been hardened.By design, some internal tables may overflow (read) for large invalid pointervalues.
• Spectre:LowFat cannot prevent OOB-reads due to speculative execution on vulnerableCPUs. For more information, see theSpectre paper. We believe this bugsimilarly affects other bounds-check instrumentation systems.
• Low Level Hacks:The LowFat runtime system uses a few very low-level hacks to try and implementnecessary functionality, such as moving the program stack and cleaning up stackson thread exit. These hacks are likely fragile. Finding better solutionsis left as future work.

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

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

A: Yes is does. LowFat handles this case by always "rounding up" object sizesby 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 trickwas "borrowed" from the Boehm conservative garbage collector, which must alsohandle such pointers to avoid erroneously collecting live objects.

Q: Can LowFat protect global variables?

A: Yes, forstatically allocated globals. Support for globals was onlyadded after the publication of [1] and [2]. For more details regardingglobals, 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 detectOOB-memory errors. The main difference between the two tools is theunderlying technology, and each approach has its pros and cons.
AddressSanitizer inserts "poisoned redzones" between objects and detectsoverflows into these zones. The main advantages of AddressSanitizer overLowFat are:

• Better at detecting off-by-one errors (LowFat does not detect overflowsinto padding).
• Can also detect use-after-free errors.

The main disadvantages of AddressSanitizer over LowFat are:

• High performance and very high memory overheads.
• Overflows that "skip" redzones cannot be detected.

The latter makes AddressSanitizer less suitable for program hardening forcases 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 detectsub-object bounds overflows, something which LowFat does not do directly(however, see below). However, both SoftBound and MPX havecompatibility problems, namely by changing the ABI (SoftBound) and withmulti-threaded code (shared state in contention).

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

• Accurate (i.e., no "rounding up") object bounds overflows
• Sub-object bounds overflows
• Use-after-free, or
• Type confusion errors?

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

• D. Song et el,SoK: Sanitizing for Security, 2019:This survey paper independently measures the overhead of LowFat'slegacy mode for older CPUs at ~85%. Legacy mode is known to be slower,and is not officially supported.
• R. Gil et al,There's a Hole in the Bottom of the C: On the Effectivenessof Allocation Protection, 2018:This paper claims "pointer stretching" (a.k.a.sub-object overflows)as an attack against LowFat.However, LowFat never claimed to detect sub-object bounds errors,which areexplicitly out-of-the-scope (seeCaveats above).Sub-object bounds errorscan however be detected by LowFat extensions,specificallyEffectiveSan.

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 thatLowFat has been built withlzcnt support, and (2) compile your program withthe 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].

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

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

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

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

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

[2] Gregory J. Duck, Roland H. C. Yap, Lorenzo Cavallaro,Stack BoundsProtection 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 andApplications, Technical Report, 2018.