fu(zz)tex: targeted fuzzing of futexes

The complexity of futexes, their non-trivial interactions and semantics, very much serve as a good candidate for applying fuzzy testing techniques to them. In general futex code is poorly understood and audited, both at a kernel implementation level and by the respective userland callers, normally trying to implement some sort of locking primitive. Unsurprisingly, bugs related to this call will often be subtle and nasty, sometimes with security implications. Specifically for futexes, all system call fuzzers use generic and completely randomized inputs, which has only limited usefulness. This is even the case for Dave Jones' trinity program, which has been extremely good at finding kernel bugs (and ruining my weekends more than once ;). Much of the success and popularity of this program is because not all the inputs are random and meaningful parameters are passed for many of the exercised syscalls. This is called targeted fuzzing, and has been proven to find more bugs than blindly random inputs, which in turn is more likely to produce logic that makes the kernel actually do something related to the call, as opposed to quickly erroring out due to some trivial bogus scenario. A nice example is the perf_event_open(2) call, which was studied for targeted fuzzy testing with very good results.

Reusing the already proven-to-work machinery of trinity. and extend it for futex ad-hoc work, is the obvious step for improving coverage, in the hope to tackle some of the issues previously described. While reading the code is always the definite answer, having a man-page that is up-to-par with the call is quite essential; if we want programmers to make correct use of the tools we provide, that is. Fortunately, Michael Kerrisk has been doing a nice job of rewriting the current futex.2 page, which is so surprisingly crappy and incomplete, it's sad. This makes the task correctly setting the input parameters following a certain purpose a little less tedious and error-prone:

 SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
     struct timespec __user *, utime, u32 __user *, uaddr2, u32, val3)

 -- just imagine if mmap.2 were barely documented and stale.

There are two immediately obvious op flags that are not being exercised at all (with the exception of randomly bumping into them, which is quite unlikey and badly controllable):

The whole purpose of PI futexes are to address priority inheritance issues for systems with real time requirements. Randomly changing a processes priority will therefore better stress the system call instead of always using the default nice value, exercising priority boosting code in the kernel.

Fault/error injections

Perhaps the single most important argument that we can pass to the syscall is the user address (uaddr, or 'the futex'), which will govern everything the kernel attempts to do with it, being private or shared address space. As such, it is not very useful to blindly feed it random addresses, even if trinity is setup by default, these inputs will sometimes be picked by previously mmap-created shared memory playgrounds. However, at a futex level, this does not matter unless we are doing blocking calls (WAIT).

So this has been reworked such that trinity now creates a number of locks in shared memory at startup, which has the owner PID and the actual futex. Upon a call, both fields of uaddr get either a random lock or a random address from the mmap playground, each with a 50% chance. The locks follow very simple semantics, where a successful cmpxchg will allow the caller to acquire the lock without the kernel being involved (fastpath), otherwise we need to wait/block through the futex call.

Because of how trinity is structured with callbacks for pre/post syscall invocation, there are a number of racy windows between when the lock is dealt (ie considered contended) with and when the fuzzer actually calls futex(2). As such, this must be taken with a grain of salt, but does exercise lots of real world situations, nonetheless.

Choosing operations

The idea is to randomly perform different operations on the selected futex, such that combinations of wake, wait, requeue are done (both for regular and PI futexes). While passing informed, not-so-random, parameters to the system call reduces the chance of shallow fuzzing, choosing the futex operation will determine the kind of work to be done on the uaddress. As such this part can further determine the usefulness of trinity regarding futexes. However, one cannot get too strict here as reducing the randomness will also limit the usefulness. For now the layout is a 25% chance when performing lock operations. Oh the other hand, for the case of mmap selected uaddress, the operation is left up to trinity to decide.

Evaluation and future work

This work was done as part of SUSE Hackweek 13, which allowed me to finally allocate some time to focus on this (although this writing is much overdue). So as always, lots of thanks to my employer.