Depth vs width in syscall fuzzing: Syzkall grouping suggestion

The motivation for this blog post is to make a suggestion about how corpus management could possibly be improved in Syzkaller and to introduce an optional new feature, which would be called something like Syzkall grouping. Before I describe this feature for which I built a prototype, I would like to elaborate on some terms and summarize how Syzkaller’s generation/mutation of inputs works currently to have a basis for the points I want to make.

Syzkaller’s input generation

Syzkaller, like any other coverage-guided fuzzer runs in a loop that roughly works like this:

1. Generate an input or select one from the corpus and mutate it
2. Feed the input to the target (in the case of Syzkaller execute syscalls with randomized arguments)
3. Collect coverage feedback and make a decision whether to keep the input or discard it.

Let’s go a little bit deeper into what a generated Syzkaller input actually looks like. Syzkaller will choose a random amount of random system calls (there is a bias towards system calls with complex arguments). Syzkaller then generates random but structured arguments for the system calls and executes them in the order they were chosen in.

An input in the serialized form for a Linux kernel could then look like this:

open(&(0x7f0000000000)='./file0\x00', 0xbc0, 0xa09a214393baae7c)
r0 = creat(&(0x7f0000000000)='./file0\x00', 0x0)
newfstatat(0xffffffffffffff9c, &(0x7f0000000040)='./file0\x00', &(0x7f0000000100)={0x0, 0x0, 0x0, 0x0, <r1=>0x0}, 0x0)
setuid(r1)
write$cgroup_type(r0, &(0x7f00000020c0)='threaded\x00', 0x9)

What you are looking at are random system calls mixed together with some random arguments.

The mutator simply takes such an input and then can apply the following mutators to it:

• splicing: take a random amount of system calls from another input and insert them a ta random index into the input to be mutated
• squashing: replace a structured argument, such as a struct, with a random binary blob
• argument mutation: chose a random amount of arguments and mutate them
• insertion/deletion: insert or delete a random system call somewhere into/from the program (with a bias towards the end)

We can see the probabilities for each of these mutations occuring when looking at the highest level of the mutation function:

for stop, ok := false, false; !stop; stop = ok && len(p.Calls) != 0 && r.oneOf(3) {
   switch {
      case r.oneOf(10):
         // Not all calls have anything squashable,
         // so this has lower priority in reality.
         ok = ctx.squashAny()
      case r.nOutOf(1, 100):
         ok = ctx.splice()
      case r.nOutOf(20, 31):
         ok = ctx.insertCall()
      case r.nOutOf(10, 11):
         ok = ctx.mutateArg()
      default:
         ok = ctx.removeCall()
       }
}

With this knowledge in mind, I want to focus the rest of the blog post on talking about the choice of system calls to be inserted when the insertion mutator is applied and the resulting consequences for splice mutations.

The kernel as a hierarchy of subsystems

We have established that the kernel chooses random system calls and as of right now only takes the complexity of their arguments into account when building an input. This results in inputs containing system calls that may not be related logically or programmatically to other subsystems.

As an example, a Bluetooth driver and a USB driver do not really affect each other’s states, at least on a high level of abstraction.

Yet, there is a higher probability of Syzkaller generating inputs containing system calls that have no relationship to each other than it does generating inputs that directly affect a shared object or state, such as for example a file they both modify and read from. An example of the latter would be an input containing multiple inputs related to changing the state of a Bluetooth driver.

With this in mind, let’s look at this amazing Linux kernel subsystem map:

In this abstraction, there are multiple subsystems such as the memory, networking, storage subsystem, etc, as well as a hierarchy of layers for each of these subsystems.

With this abstraction in front of us, we can visualize how Syzkaller will over time generate inputs that will cover deeper aspects of the different subsystems, thanks to coverage feedback. Let’s talk about the process of the fuzzer exploring these subsystems and what exactly I mean when I mentioned width and depth in the context of corpus management.

Width vs Depth

When Syzkaller mixes a number of random system calls into an input, there is a high probability that most of these system calls will mostly be unrelated to each other, as there are hundreds of them, maybe even thousands if you consider for example driver-specific ioctl() calls as their own system call in the context of fuzzing.

This means a single input will probably not go very deep on a single subsystem, but rather explore the surface of more than one subsystem when using coverage as a measurement as to which subsystems are explored. This means the code covered by a single input could, for example, be illustrated as in the following image, where red lines stand for the sub-components of the kernel that are touched.

Depth and combinations of system calls

The above image showed an example of how a newly generated input with random system calls covers multiple aspects of the kernel, but none of them in depth. Let’s assume that this is the only input in the corpus right now. Over time, the fuzzer will mutate the arguments of the system calls and go deeper into each subsystem, since arguments are mutated and new code paths discovered. This could happen for example when the cmd argument of an ioctl() call changes and sets a previously unused option of a driver.

However, there is a limit as to how much code a single system call related to a subsystem or for example a driver or a file-system can cover, no matter how many times the arguments to it are mutated. At a certain point, the fuzzer will only uncover new code paths by combining system calls in some way that leads to solving previously unsolved challenges.

Let’s take fuzzing a file-system as an example.

An input that fuzzes a file-operation of a specific mount would usually have the following system calls:

1. mount() of the file-system
2. open() of a file-backed by the mounted file-system
3. some file operation, such as for example ioctl() or write()

Syzkaller could over time insert new file operations on a file backed by the file-system to be fuzzed. It will then get new coverage feedback for all the different file operations the file-system supports. However, there is a case to be made that deeply rooted bugs in a kernel component, in this example a file-system driver, are to be found in code paths that can only be covered if a combination of system calls in a specific order is made.

As an example, let’s assume that Syzkaller were to generate an input that mounts a file-system and then mmap() ‘s a file backed by it. It then calls write() on the same file and finally writes to the memory mapping of the file. The final call of the input is fsync().

With this combination, the fsync() call has to deal with the file having been written to on disk and a page being dirtied, which it only has to do if such a combination occurred.

Now imagine if the mount() arguments were mutated as well and suddenly different mount options would change the behavior of the above combination. There are endless states a subsystem can be in, given a subsystem has a large enough number of system calls and/or complex enough arguments to those system calls that affect the subsystem’s state.

This example of an input calling a combination of system calls on a file-system to cover new code paths opens up the discussion to two problems:

1. Assisting Syzkaller in finding combinations of inputs that lead to new inputs
2. The limitations of coverage when fuzzing state-machines

Diving-deep: Assisting Syzkaller in finding combinations faster

I made the assumption that a newly generated Syzkaller input will probably consist of system calls that mostly have no direct relationship to each other. I also made a claim that code paths deep within a subsystem or component can only be discovered if a combination of system calls relating to that subsystem or component is made in some order.

Now, it is intuitive to assume that Syzkaller due to its nature as a coverage guided fuzzer should over time end up with inputs finding these deep paths. The logic behind this assumption is that an input of diverse system calls is mutated and by chance, a system call that has some sort of relationship with another system call in the input is inserted and new coverage discovered, thus the input will be kept. Over time, more and more system calls with a relationship to each other will be inserted into the input as a result of new code paths being covered.

Although coverage feedback definitely can work for many combinations of system calls, it might not work for all cases. An example where coverage guided feedback works when a combination of system calls is made would be, to continue the previous example of a file-system, a combination of mount() and umount(). When calling umount() without ever having mounted anything, only the error paths of umount() will be explored, but only if a mount() was performed earlier, the actual code responsible for unmounting is covered.

However, here is an example that shows the limitation of coverage:

Let’s assume Syzkaller is launched with a clean working directory and no inputs have yet been generated. In this case, Syzkaller will generate new inputs. To pick up the example of fuzzing a file-system from earlier, let’s assume a target file-system supports all the standard file-operations (e.g. open(), poll(), read() etc.) Then, let’s assume Syzkaller generates multiple, completely unique inputs each of which contains one file operation related to the target file-system.

In this case, the code coverage of each file operation as much as it is possible to discover without combining this system call with another system call that is related.

At some point, two file-operations which could have already been fuzzed and thus the code coverage explored to some degree, would be combined into one input through splicing or insertion. Even though these two file operations can, in fact, lead to new code paths being discovered when combined, they must be combined in a certain order and with certain arguments. Here is an example of poll() and write() combined:

poll() can be used to wait for events on a file-descriptor. Here is the declaration:

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

where a struct pollfd is defined as follows:

 struct pollfd {
    int   fd;         /* file descriptor */
    short events;     /* requested events */
    short revents;    /* returned events */
};

Essentially, you would pass a list of file-descriptors and events that should be waited for, for each file descriptor. An example of an event to wait for would be POLLIN. This event occurs when data can be read from the file backed by the file-descriptor. This means that if an input was generated that first calls poll() on a file and waits for this event and then calls write() on the same file, new code could be covered.

However, what if the combination of poll() and write() was in the correct order, but some other event than POLLIN was requested. In this case, although a new combination of two system calls that are related to each other could be discarded as there might not be new coverage. It could then take millions of executions until this combination occurs again and it might not have the correct arguments again.

The difficulty of detecting such combinations becomes increasingly difficult due to the following factors:

1. there are hundreds, possibly thousands, of possible system calls to choose from and Syzkaller has no knowledge of which system calls relate to each other
2. the right order of the combination of one or more system calls has to be chosen
3. the right arguments need to be set

It is possible to aid Syzkaller with the first 2 problems I listed above, by making Syzkaller aware of system calls that are related to each other.

Syzkaller grouping

I propose an extension to the Syzlang with a new keyword, something along the line of group.

A group definition could look something like the following:

group ABC_GROUP
syscall_a()
syscall_b()
syscall_c()
endgroup

With this kind of grouping block, it would be possible to inform Syzkaller that the system calls within the group block are in some way related to each other.

We can then increase the probability of Syzkaller combining these system calls by modifying the insertion mutator in the following way: If the input contains one or more system calls belonging to a group, have a bias towards inserting a new system call from that group instead of a completely random system call.

With Syzkaller being aware of which system calls are related to each other, we can also encourage Syzkaller to detect a new order of system calls of that group it has not seen before and save it back to the corpus, regardless if new coverage has been discovered or not.

This does not solve the problem of detecting if the combination of two arguments has lead to a previously unexplored state being discovered, but it is a step into the right direction and at least increases the probability of combinations happening massively.

This kind of grouping would make inputs less diverse over time, as there is a bias towards inserting system calls that are related to each other. This means a single input is more likely to go deeper into a subsystem. An advantage of this would be that the splice mutator would then be more likely to combine two deep aspects of the kernel, for example the process and virtual memory subsystems, and might find deeply rooted bugs this way that have previously not been found.