[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Xen-devel] [RFC v2] Proposal: Fuzzing the Hypervisor


here a new version of my proposal for fuzzing the hypervisor. The original can be found here: [1].

1. Motivation and Description
Fuzzing is a recent trend for systematic testing of interfaces by trying more or less random inputs and iterating over them. A subset of fuzzers uses code-coverage as feedback when permuting and choosing inputs, among them the popular user-space fuzzer American Fuzzy Lop. Recently there have been attempts to port fuzzers to the kernel and in a similar manner should now the hypercall-interface of Xen be tested.

While this is overall a very comprehensive problem, this project will help to develop a better understanding of the problem space and make at least first advances of the source tree into the necessary direction. A generic mechanism will be implemented allowing fuzzers to obtain feedback on code-coverage. In the next step this output will be further processed in order to actually run a fuzzer (in particular AFL), although there might not be sufficient time to commit this to the source tree.

2. Fuzzing user-space programs vs. fuzzing a hypervisor
An iteration in the fuzzing-cycle normally involves the following:

1. Fuzzer creates new test case based on tracing output 
2. Fuzzer starts binary with a test case
3. Test case is executed and program counters are traced into shared memory with fuzzer
4. Repeat from 1.

Being not a user-space program, it is however not possible to instrument the binary using the methods applied by AFL. Instead, program counters need to be extracted manually and post-processed into the form expected by AFL. As Xen doesn't just take binary input there further needs to be some other format for test cases and executing them.

In order to fuzz the hypervisor, at least the following steps are required:

1. Let the fuzzer create a new test case
2. Drive a domU to execute the test cases of the fuzzer and trace execution path
3. Parse the execution path into a format consumable by a user-space fuzzer
4. Repeat from 1.

In comparison to AFL, the notion of a test case when fuzzing the hypervisor is different. In AFL, the program is restarted for every test case (or at least the initial state is restored using the fork-server), while in Xen, all hypercalls are made on the same hypervisor (at least until it crashes), such that even though AFL might run multiple times, the test case would be the collection of all hypercalls made since booting.

Also, domains can only have a single vCPU as determinism is needed in tracing output. For the same reason, there will initially also only be a single AFL-instance run at a time. However, this can easily be extended later on.

3. Implementation Plan

3.1 Tracing
The tracing has mostly already been implemented in [2] and has been discussed in the original version of this proposal [1].

The approach is similar to KCOV, a coverage collection tool in the Linux kernel and is well-summarised in the following description from the original patch [3]:
kcov does not aim to collect as much coverage as possible. It aims
to collect more or less stable coverage that is function of syscall
inputs. To achieve this goal it does not collect coverage in
soft/hard interrupts and instrumentation of some inherently
non-deterministic or non-interesting parts of kernel is disbled
(e.g. scheduler, locking).
Some adjustments in regard to what to include are still to be made based on more extensive testing. Originally supposed to happen on a directory-level, that turned out to be not granular enough, sucht that coverage was instead restricted to certain files in the common/-directory.

3.2 Distinction between executor and fuzzer
Xen doesn't take any binary input directly, so in order to fuzz the hypercall-interface a middle-program needs to created, fed with the test cases produced by the fuzzer and making hypercalls. This is done by a Xen-guest. In order to increase determinism (by not making hypercalls that weren't explicitly instructed) and speed (by being lean) XTF was chosen. If a little more features were needed Mini-OS could be chosen, but for now this isn't necessary.

As mentioned, test cases are not actually separated in this setup. It would thus not be helpful to actually have separate XTF files for every iteration of AFL. Further, it would reduce speed by forcing recompilation in every iteration. AFL would have troubles with producing valid C syntax anyways, so this approach isn't taken. Instead, the executor is a server, waiting for input from the fuzzer about which hypercalls to make with which arguments, parsing a custom syntax.

3.3 Fuzzer
The idea is to create some dictionary from which the fuzzer builds test cases, each line looking like :

<function name> arguments

Also, the test cases need to be written to a file before actually being applied in order to survive a crash. As pointed out by Andy, the file system should have caching disabled.

The binary of the fuzzer also needs to be adjusted in order to accommodate the fact that not the usual binary is instrumented. The particular code here for AFL is all found in afl-fuzz.c. The function run_target() is normally responsible for starting the binary, but instead will have to communicate with the executor. The buffer trace_bits has to be filled with the binary tracing output.

The fuzzer will initially be run in deterministic mode.

3.4 Executor
The executor will then try to read out hypercalls and execute them. It will also need some encoded information about the arguments expected for each hypercall, such that it can pass on valid buffers (if it wants to, one could also imagine that a test case is to pass in completely invalid data).

3.5 Communication between executor and fuzzer
Fuzzer and executor need to communicate at least test cases and tracing output. For this it was considered to have a shared memory region as in the original AFL for the tracing output (using grant tables) and to execute the test case from a file. Signals could be used via event-channels to inform the executor of the arrival of a new test case and the fuzzer of an ended test case, allowing a nice event-driven approach without polling. As XTF doesn't support any of this, this idea was overthrown in favour of just using the Xen console, which still should allow both.

4 Flow diagram
+-----------------------------------------+                                        +------------------------------------+
|                                         |                                        |                                    |
|               Dom X                     |            +--------+                  |               Dom Y                |
|                                         |            |  Test  |                  |                                    |
|  +-----------------------------------+  | +--------->+ cases  +-------------->   | +-------------------------------+  |
|  |                                   |  |            | SAVED  |                  | |                               |  |
|  |                                   |  |            +--------+                  | |                               |  |
|  |                                   |  |                                        | |                               |  |
|  |              Fuzzer               |  |                                        | |         Executor              |  |
|  |                                   |  |                                        | |                               |  |
|  |                                   |  |                                        | |                               |  |
|  |                                   |  |                                        | |                               |  |
|  |                                   |  |                                        | |                               |  |
|  +-----------------------------------+  | <----------------------------------+   | +-----+----------+--------------+  |
|                                         |                                        |       ^          |                 |
|                                         |            Tracing (binary)            |Tracing|          |                 |
|                                         |                                        |(program      Hypercalls            |
|                                         |                                        |counters)         |                 |
+-----------------------------------------+                                        +-------+----------------------------+
                                                                                           |          |
|                                                                                                                       |
|                                                                                                                       |
|                                                 Xen Hypervisor                                                        |
|                                                                                                                       |
|                                                                                                                       |
5. References
[3] KCOV patch for Linux kernel: https://lwn.net/Articles/671640/

Any comments appreciated,

Xen-devel mailing list



Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.