RULF: Rust Library Fuzzing via API Dependency Graph Traversal

As Rust surges into popularity, many bugs of projects written in Rust have been reported and analyzed, such as those collected in Advisory-DB and Trophy-Case. A special characteristic of these bugs is that most of them are located in libraries [11]. Note that testing libraries is very different from testing executable programs. For library testing, developers should compose their use cases of library APIs before testing them or base the testing on unit tests. Since there could be different ways or contexts of using an API, library testing is more challenging.

Figure 1(a) demonstrates a library bug³³3Issue link: https://github.com/casey/just/issues/363 found in a Rust crate just. The term crate represents the minimal compilation unit in Rust. In this paper, we call a Rust library a crate. The bug lies in the method justfile(), which is defined on a struct Parser. The method justfile() uses a third-party data structure PutBack to store tokens. In the buggy code, the first two statements fetch two tokens, and the next two statements put the two tokens back via put_back(). However, put_back() can put only one single item back each time. If putting two items back, the first item will be overwritten. As a result, justfile() may parse an input string incorrectly and panic the application. The patch simply replaces the struct PutBack with another one PutBackN that allows putting back multiple items.

This bug had existed in the crate for over 10 versions before it was found by a fuzzing tool. Reproducing the bug requires composing a testing program for justfile() and some specific test cases. To this end, the testing program should create a Parser object via Parser::new(&str, Vec<Token>), and Vec<Token> can be created by calling Lexer::lex(). Figure 1(b) presents a sample testing program based on the analysis. Specifying “export AA” as the value of input would crash the program.

To fuzz a library program, we need a set of testing programs as fuzz targets. Such testing programs are similar to those discussed in Figure 1. However, how to automatically generate such testing programs is a challenging problem. Note that there could be dozens or even hundreds of APIs for a library program, and the fuzz targets should consider each API.

Taking the library in Figure2(a) as an example. The crate toylib has two structs (S1 and S2) and five public APIs (f1 to f5). We may design one specific fuzz target for each API, or a large target that covers all APIs, or two potential fuzz targets (Figure 2(b) and Figure 2(c)) that can cover all APIs using each API only once. Such options are essential factors affecting the effectiveness and efficiency of library fuzzing.

Below, we discuss four objectives for the fuzz target generation problem.

• •

  Validity: The synthesized fuzz targets should be able to be successfully compiled, i.e., all the parameters of each API should be correctly settled. RULF achieves this objective by traversing the API dependency graph.

• •

  API coverage: For a library program, each of APIs has a potential to contain bugs. Therefore, the set of generated fuzz targets should cover as many APIs as possible.

• •

  Efficiency: The set of generated fuzz targets should be efficient for fuzzing. On the one hand, the number of fuzz targets should be manageable since fuzzing each target generally requires several hours. On the other hand, we should avoid employing the same precedent APIs in different fuzz targets if possible because fuzzing the same API multiple times may not be helpful.

• •

  Effectiveness: The generated targets should be friendly to fuzzing tools for bug hunting. In order to fuzz an API effectively, the generated program should be small. Otherwise, the fuzzing effort would be wasted on the testing program or other APIs rather than the target API.

If the return value of one API and the parameter of another API are of the same type, we can synthesize a valid program that call the second API with the return value of the first API as the parameter. In other words, we say there is one possible data flow dependency between the two APIs. Informally, an API dependency graph is a directed graph that captures all such possible data flow dependencies among the APIs of a crate.

Formally, we define an API dependency graph as a directed graph $G=(FN_{m},PAR_{n},PE_{p},CE_{q})$ over a set of APIs $\Sigma$, where:

• •

  $FN_{m}$ (API nodes) corresponds to all $m$ APIs in $\Sigma$;

• •

  $PAR_{n}$ (parameter nodes) corresponds to a subset of API parameters in $\Sigma$ excluding those of primitive types. We do not consider primitive types because they can be provided by fuzzer engines.

• •

  $PE_{p}$ (producer edges) $\subseteq$ $FN_{m}\times PAR_{n}$, where an edge $fn_{i}\to par_{j}$ implies $fn_{i}$ returns a value of type (or can be inferred as type) $par_{j}$.

• •

  $CE_{q}$ (consumer edges) $\subseteq$ $PAR_{n}\times FN_{m}$, where an edge $par_{i}\to fn_{j}$ implies $par_{i}$ is a non-primitive parameter for $fn_{j}$. The edge is weighted if $fn_{j}$ requires multiple $par_{i}$s as its parameters.

We introduce parameter nodes into the graph to better distinguish two types of dependencies: 1) an API requires two parameters returned by both two APIs ($fn_{i}\to par_{j}\&fn_{i+1}\to par_{j+1}$), and 2) an API requires one parameter returned by either of the two APIs ($fn_{i}\to par_{j}|fn_{i+1}\to par_{j}$). Figure 3 demonstrates the API dependency graph for toylib discussed in Figure 2(a). The graph contains five API nodes $FN_{5}=\{$f1,f2,f3,f4,f5$\}$ and two parameter nodes $PAR_{2}=\{$s1,s2$\}$. s1 and s2 are two non-primitive type parameters required to call f4; s2 is one non-primitive type that can be produced by either f2 or f3.

We further define two kinds of special API nodes: start node that consumes no non-primitive parameters and end node that returns no non-primitive values. In Figure 3, f1, f2, f3 are start nodes and f5 is an end node. f4 is neither a start node nor an end node. Besides, an API node can be both a start node and an end node.

On an API dependency graph, an API node is reachable if and only if it is a start node or all its required parameter nodes are reachable and the weights of consumer edges are satisfied. Similarly, a parameter node is reachable if at least one API node that can produce the parameter is reachable.

We say an API sequence $fn_{0},...,fn_{k}$ is valid if $fn_{0}$ is a start node and each $fn_{i}(0<i\leq k)$ is reachable given the subsequences of $fn_{0},...,fn_{i-1}$. This is an essential requirement for synthesizing valid fuzz targets. For example, {f2,f5} is a valid sequence in Figure 3; {f1,f4} is invalid because s2 is not reachable for reaching f4.

Note that our definition of a valid API sequence does not enforce a precedence relationship between each pair of adjacent API nodes. In this way, a sequence with duplicated subsequences (or duplicated APIs) or with multiple end nodes can also be valid. This is essential to deal with the move semantics in Rust. Briefly, move semantics mean the return value can be used only once. If an API has two parameters of the same type, we may call f1 twice to serve the two parameters. Therefore, {f1,f1} is also a valid sequence.

We generate valid API sequences by traversing the API dependency graph. According to the objective of fuzz target generation discussed in Section II-B. The algorithm should meet three objectives: API coverage, efficiency, and effectiveness. To this end, we first employ BFS with pruning to obtain a set of API sequences that can cover the maximum number of APIs given a length threshold; next, we backward search valid sequences for uncovered APIs with lengths larger than the BFS threshold. Finally, we merge the two sets as one and further refine it to remove redundancies.

We construct an API dependency graph in two stages.

First, we extract all public API signatures from the source code. We base RULF on an existing tool, rustdoc [22], which is an official doc tool to generate API documentation for Rust projects. Internally, rustdoc calls rust compiler to compile the crate and extract API information from the compilation results. We directly add our codes into librustdoc.

After we extract all public API signatures, we infer dependencies among APIs based on type inference to build dependency graph. We define call type for type inference. If there is a call type from type A to type B, A and B are the same type or A can be converted to B. All call types can be seen in Table I. Note that call types can be nested, e.g., there is a call type from Option<T> to &T, which is Borrowed reference (Unwrap option).

Call types defined in Table I can be divided into two categories. The first seven are general call types (from Direct call to Dereference raw pointer). The last three are specific call types for two types, Result and Option (from Unwrap result to To option). Result and Option are two heavily-used enumeration types in Rust. Result is used to return recoverable errors. Option indicates a value that may be empty. These two types are used to wrap a normal type, e.g., u8 is an 8-bit integer type, while Option<u8> can be a normal u8 or None. We can get the real u8 type by unwrapping Option<u8> if it is not None. If these two types are not specially treated, it will greatly affect the validity of type inference.

More wrapper types can be treated specially, e.g., Box. Special treatment of these types helps infer dependencies more accurately. RULF can support this by adding a new call type.

After we construct an API dependency graph, we generate valid sequences by traversing the graph. The main approach is mentioned in the previous section. Here are more details.

API dependency graph can only capture all possible data flow dependencies, but this is not enough for generating all possible sequences. Figure 5 demonstrates such a case. Since the return value of toylib::f4 is never used, this sequence will be removed by $RedundancyTest$ in previous section. However, toylib::f5 uses the variable mutated by f4. So, toylib::f4 is not a redundant API.

To deal with this case, we integrate $EndNodeTest$ and $RedundancyTest$ with mutation analysis. If an API has no return value or returns a primitive type, it is an end node according to the definition in the previous section. However, if the API can mutate the value of a variable (like setter methods in Java), it is not appropriate that we treat this API as an end node. The $EndNodeTest$ is based on the fact that the API behind an end node can exchange orders with other end nodes. This fact does not hold if the end node can mutate the value. So we redefine an API that satisfies the following two requirements as an end node: 1) The API has no return value or returns a primitive type. 2) The API does not mutate the value of any variable that another API returns.

We modify $RedundancyTest$ similarly: if neither the return value of an API nor variables whose values are mutated by this API are used by other APIs, this API can be called a dead node. Sequences containing such a dead node are redundant and can be filtered.

Determining whether an API can mutate a value in Rust programs is easy. Rust has a keyword mut. Only if the parameter of an API is modified with the keyword mut, the API has the ability to mutate a value (e.g., toylib::f4 can mutate the value of s2). After modifying the definitions of $EndNodeTest$ and $RedundancyTest$, we can still use the algorithms in the previous section. Interior mutability in Rust, allowing unsafe code in a function to mutate the value of a parameter even if the parameter is not modified with mut, may affect the effectiveness of mutation analysis. However, interior mutability does not affect the validity of sequences generated by RULF. So we ignore the limitation in the current implementation of RULF.

To generate sequences that can pass the compiler’s check, we take Rust’s language features into account. Ownership is Rust’s most unique feature. In Rust, each value has only one variable as its owner which has the exclusive ownership of the value. The ownership can be transferred among variables, which is called move. If a variable transfers the ownership, the variable cannot visit the value anymore. Figure 6 demonstrates a simple move case. s1 defined in line 1 is used by toylib::f4 in line 3. s1 transfers the ownership in line 3. We cannot use s1 in line 4 any more otherwise it will report a compilation error.

Passing a value to a function may result in the value moved or copied, so we should distinguish between moving and copying cases. If a value is moved, we add a tag to the variable which owns the value and do not use this variable in the following statements. Whether a value moves depends on the combination of call type and variable type. Considering that there are many call types (call types can be nested) and variable types, it is not easy to distinguish moving and copying cases correctly. In practice, we adopt a conservative strategy. We select some combinations of variable types and call types that we think are commonly used in API calls and mark these combinations as copying cases if they do be. For example, if the variable type is immutable reference and the call type is Direct Call, we will mark this case as a copying case. Except for several cases marked as copying cases, we assume that all other cases are moving cases.

Reference is also carefully dealt with. Variables without ownership can visit a value by having a reference. There are two categories of reference, immutable reference (shared reference) and mutable reference (exclusive reference). To avoid data race, immutable reference and mutable reference of the same value cannot coexist. Multiple mutable references of the same value are not allowed to coexist too. We add a tag to variables that have a reference to make sure that the rules about references are correctly followed. Currently, we do not take special treatment to the lifetime bounds of references, which may result in generating invalid sequences. We will add check of lifetime in our following work.

We synthesize Rust programs ready to compile from valid sequences. We implement several stages in RULF to pass the check of the compiler, e.g., adding mut tag, adding import statements and so on. In this section, we focus on our method to deal with primitive types.

We get all primitive parameters from the input buffer of fuzz targets. We split this buffer into slices of different sizes. Then we convert each slice to a primitive value. This conversion relies on a series of template functions we write in advance. We currently do not support some primitive types, e.g., string with static lifetime or array with a static length that cannot be provided by the fuzzer engine.

To decide how to split the input buffer, we divide all primitive types into two categories. One is with a fixed length, such as u8 and char. The other is with a dynamic length, such as string and slice. We first assign a slice from the buffer to each fixed-length variable. The remaining part of the buffer will be divided equally among all dynamic-length variables.

When we merge and refine the sequences after backward search, we skip sequences without primitive parameters as input since fuzzing these sequences is useless. We also give preference to sequences with primitive parameters of dynamic length. These sequences have larger input space to search and intuitively are more likely to contain errors.

We select 14 popular and high-quality Rust crates for fuzzing experiments, including eleven from crates.io and three from GitHub. All these crates have been downloaded over ten million times or received more than 4000 stars. Meanwhile, all these crates have well-written unit tests and stable releases. All these crates manage their dependencies by cargo, i.e., running cargo build for these crates will return success without manually downloading dependencies. We avoid selecting certain libraries due to our current limitations (see Section V-E), e.g., libraries containing many asynchronous APIs. We download their latest version for our experiments. Table II lists the names of these crates. Their API numbers vary a lot, ranging from 12 to 212.

When generating fuzz targets with BFS, we choose three as the threshold of sequence length. The threshold cannot be large due to path explosion. For instance, the running time to generate fuzz targets on a crate time will exceed one hour if we set the threshold to four. Meanwhile, the threshold cannot be too small because we cannot explore different API combinations in a very short sequence. Three is a best practice according to the code samples in Trophy-Case to reproduce bugs. We find that most bugs can be reproduced by calling library APIs within three times.

Before fuzzing each fuzz target, we generate 500 random inputs and execute the target with each input. If all inputs lead to program crashes, the fuzz target is considered as an invalid target and removed. The rest inputs will be employed as seeds for further fuzzing.

We use afl.rs from rust-fuzz [23] to compile and fuzz these targets. afl.rs is a Rust binding for AFL++ [19], which is AFL with community patches. We set the environmental variable AFL_EXIT_WHEN_DONE = 1, so the fuzzing process will exit automatically when all branches are visited. We set AFL_NO_AFFINITY = 1, so we can fuzz more targets parallel than the number of our cores. All other environmental variables are set with default values. We fuzz each crate for 24 hours unless AFL itself terminates. After that, we obtain a set of crashes and refine the result with afl-tmin and afl-cmin. In particular, these tools can merge crash reports with equivalent edge coverage.

We manually check each crash report to determine whether it is a real API bug. To this end, we reproduce each crash to analyze why the crash happens. If a crash is caused by an explicit panic function call or is documented as a known panic case, we do not treat it as a bug. Otherwise, the crash should indicate a bug.

All our experiments are conducted on a Dell T640 server with 2 Intel Xeon Gold 6242R 3.10GHz 20-core CPUs and 256GB memory.

We discuss the performance of RULF with respect to the objectives of validity, API coverage, efficiency, and effectiveness.

The basic goal of our algorithm is to generate a set of valid sequences to cover all APIs. Three optimization goals are (1) to minimize the set size (2) to maximize producer edge coverage (3) to avoid repeatedly visiting the same API.

Combining BFS with backward search enables us to cover all APIs efficiently. It takes less than 30 seconds to generate targets for each library if the library is compiled.

Our pruning and refining algorithms reduce the size of the sequence set. As shown in Table V, the number of sequences greatly decreases after we integrate pruning and refining algorithms into BFS. The ratio of sequences generated by BFS to fuzz targets after refining ranges from 28 to 3241, i.e., we achieve equivalent API coverage with a much smaller set. We can avoid fuzzing the same API too many times.

Backward search is efficient for covering deep-APIs. The longest sequence we generate by backward search is of length seven. It is hard for only BFS to generate this long sequence due to path explosion. On our server, we cannot generate this long sequence with only BFS before running out of memory. Besides, we cannot determine which API cannot be covered with only BFS. Backward search can cover 26 more APIs in 5 out of 14 libraries after BFS. This number (26) is much smaller comparing to total API numbers (1435), which confirms our previous observation that only a few APIs cannot be covered by BFS. Among all 30 bugs we found, one bug is reproduced by calling four library APIs. We cannot find this bug without backward search.

BFS is useful to combine APIs in different ways. A possible algorithm to cover all APIs is to only leverage backward search to generate sequences from an empty sequence. For each unvisited API, backward search tries to find dependency for each parameter of the API from already-generated sequences. Table IV compares backward search, backward search with refining and RULF on the quality of generated targets based on our three optimizing goals. To cover all APIs, backward search requires generating more targets and visiting the same API repeatedly for more times. Besides, backward search can cover fewer producer edges. Even after performing our refining method on the results of backward search to remove redundant targets, RULF performs better. We limit our use of backward search to only a few deep-APIs to ensure the quality of generated targets. The reason is that BFS generates all possible short sequences. When we refine the result, we have more sequences to select from. So we can obtain targets with higher quality.

There is no available fuzz target generator on Rust now. The closest one is Fudge [18]. We select Fudge as our first baseline. Fudge can generate fuzz targets for C/C++ libraries automatically. Fudge has earned great success and led to hundreds of bug fixes. Fudge extracts code snippets as targets by finding the minimum data flow and control flow dependencies of library APIs in client codes. Fudge extracts code snippets from the whole Google code bases. Since we cannot visit Google code bases, we adopt Fudge’s algorithm on two available code bases: (i). ten client libraries with most downloads on crates.io using APIs from the libraries to fuzz (FLC) and (ii). the unit tests from the library to fuzz (FLUT). We extract codes manually with Fudge’s algorithm and drop duplicate targets with the same API call sequences.

We also implement random walk as our second baseline. One possible alternative to generating targets is random walk. Random walk starts from an empty sequence. For each step, we pick up a random sequence from previously-generated sequences and a random API from all library APIs. If the API can be added to the sequence to generate a valid sequence, we generate a new sequence. We perform random walk until we generate the same number of targets as generated by RULF.

For RULF, we fuzz each crate by a threshold of 6 hours. For other methods, we ensure the total time threshold to fuzz a library is the same as RULF. We compare RULF with other methods on the effectiveness of bug finding. The results can be seen in Table VI.

The comparison results can be seen in Table VI. Among four methods, random walk performs most poorly. Randomly-generated targets usually cover the same APIs and paths, so fuzzing these targets leads to the fewest bug findings. FLC behaves better than random walk but still poorly. We find that client codes usually limit their usage of library APIs to some most common ones, so we can only extract very few targets. Client codes tend to use APIs with complex logic which are more error-prone to some extent. So FLC can find more bugs than random walk. FLUT achieves higher API coverage and finds more bugs than the first two methods. Library unit tests combine library APIs in different ways to ensure APIs behave properly. The codes in unit tests cover most error-prone cases. FLUT can find some bugs beyond the capacity of the current version of RULF, e.g., bugs involving third-party APIs and advanced Rust features like closure. However, similar to client codes, unit tests emphasize more on the combination of commonly-used APIs. So, FLUT fuzzes commonly-used APIs repeatedly while missing bugs in other rarely-used APIs. To improve the performance of Fudge-like methods, we require better code bases to capture the usage of library APIs. RULF behaves best for we directly generate targets to achieve high API coverage from library source codes. We will not miss any API that may go wrong.

RULF still has some limitations, and we leave these issues as our future work.

Firstly, the API coverage of RULF can be further improved by supporting polymorphic APIs. These APIs involve polymorphic types, such as generics and trait object. Since we infer dependencies only according to concrete types, we cannot infer dependencies for polymorphic APIs now. We will consider supporting typical usage patterns of polymorphic APIs in the future, such as trait object or generics with trait bound by exhausting all possible types defined in the crate.

Secondly, the current version of RULF only considers functions or methods as library APIs for fuzzing. It cannot support macro APIs. We will consider supporting macro in the future. RULF currently also does not support asynchronous APIs. The execution of asynchronous APIs depends on a specific runtime, such as async-std or Tokio [25]. We will investigate how asynchronous APIs influence the effectiveness of fuzzing in our following work.

Finally, RULF only supports general fuzzing tools like AFL and honggfuzz. We cannot support in-process fuzzers like libFuzzer because we introduce std::process::exit in our template functions to simplify current implementation of RULF. We will consider replacing the use of std::process::exit to support in-process fuzzers. Besides, general fuzzing tools are inefficient to deal with highly structured inputs [26] [27]. We will investigate how RULF performs when we fuzz programs with different fuzzers.