TL;DR

FloatZone is a redzone-based memory sanitizer to efficiently detect buffer overflows (and use-after-frees) by means of floating-point underflows.

Memory Sanitizers

Memory sanitizers are powerful tools to detect spatial and temporal memory errors, such as buffer overflows and use-after-frees. Fuzzers and software testers often rely on these tools to discover the presence of bugs.

For example, with Address Sanitizer (ASan), it’s possible to detect the use-after-free bug present in this snippet:

#include <stdlib.h>
int main() {
  char *x = (char*)malloc(16 * sizeof(char*));
  free(x);
  return x[5];
}

$ clang -fsanitize=address -O3 -fno-omit-frame-pointer use-after-free.c -o use-after-free
$ ./use-after-free
==1027189==ERROR: AddressSanitizer: heap-use-after-free on address 0x607000000025 at pc 0x56119d5b8eeb bp 0x7ffcbe664bf0 sp 0x7ffcbe664be8
...

This detection capability comes at the price of slowing down the execution time by almost ~2x. For use cases such as fuzzing this heavily impacts the throughput (execution/s), slowing down bug finding.

The main component of this slowdown is caused by the pervasive instrumentation that verifies if all loads and stores are performed on valid addresses. In the example above, ASan will add the following pseudo-code check:

if (lookup(&x[5]) == VALID) {
  return x[5];
} else {
  abort();
}

Basically, this check access a big Look-Up-Table (shadow memory) that specifies for every address if it’s valid or not. This instrumentation incurs an expected significant overhead, and from a CPU perspective, these checks are particularly demanding for multiple reasons:

Loads from shadow memory can evict application cache lines and TLB entries
Frequent comparisons pollute the branch prediction buffers and can result in branch mispredictions
Bottlenecks caused by the competition for execution units (i.e., load, branch, and address management units)

Speeding up Sanitizers via FP additions

In FloatZone, we demonstrate how to reduce sanitizers overhead by offloading these checks to the Floating Point Unit (FPU). This is done by using a trick to express comparisons as floating point addition.

Exceptions can be seen as comparison. For example, integer divisions implement an implicit check:

if(y != 0) {
  res = x/y;
} else {
  abort_division_by_zero();
}

We took this idea and adapted it to our needs to implement a memory sanitizer. With the magic number 0x0b8b8b8a, we can implement a branch-less equality check with one of the fastest operation the processor can execute: a floating point addition.
This number has the unique property that when added to all the possible 2^32 floating point values, it causes an exception only with two of them:

//A simple FP addition
res = float(0x0b8b8b8a) + float(y)

//Is actually
if( y == 0x8b8b8b8b || y == 0x8b8b8b89 ) {
  fp_underflow_exception();
} else {
  res = float(0x0b8b8b8a) + float(y)
}

But how can we use this trick to detect buffer overflows (and underflows)? Simply by surrounding objects with 0x8b redzones:

In more details, for spatial memory error detection, we add and remove redzones on object allocation and de-allocation respectively.

Moreover, for temporal memory error detection, we mark objects as invalid (with 0x8b redzones) upon free and place them in a quarantine (a common technique used also by ASan). Objects are actually freed only when the quarantine size exceeds a predetermined threshold.

Evaluation

Using our findings, we built two sanitizers: FloatZone and FloatZoneExt. The only difference between them is that FloatZoneExt offers better partial-overflow detection capabilities at the cost of increased overhead.

Our evaluation shows that FloatZone significantly outperforms existing systems, with just 37% runtime overhead on SPEC CPU2006 and CPU2017. Moreover, we measure an average 2.87x increase in fuzzing throughput compared to the state of the art. Finally, we confirm that FloatZone offers detection capabilities comparable with ASan on the Juliet test suite and a collection of OSS-Fuzz bugs.

Papers

Acknowledgements

We thank the anonymous reviewers for their feedback. We also thank Johannes Blaser for his valuable support with LLVM. This work was supported by Intel Corporation through the “Allocamelus” project, the Dutch Ministry of Economic Affairs and Climate through the AVR program (“Memo” project), the Dutch Science Organization (NWO) through projects “TROPICS”, “Theseus”, and “Intersect”

vusec

FloatZone