Fuzzing APIs¶

So far, we have always generated system input, i.e. data that the program as a whole obtains via its input channels. However, we can also generate inputs that go directly into individual functions, gaining flexibility and speed in the process. In this chapter, we explore the use of grammars to synthesize code for function calls, which allows you to generate program code that very efficiently invokes functions directly.

Prerequisites

• You have to know how grammar fuzzing work, e.g. from the chapter on grammars.
• We make use of generator functions, as discussed in the chapter on fuzzing with generators.
• We make use of probabilities, as discussed in the chapter on fuzzing with probabilities.

Fuzzing a Function¶

Let us start with our first problem: How do we fuzz a given function? For an interpreted language like Python, this is pretty straight-forward. All we need to do is to generate calls to the function(s) we want to test. This is something we can easily do with a grammar.

As an example, consider the urlparse() function from the Python library. urlparse() takes a URL and decomposes it into its individual components.

You see how the individual elements of the URL – the scheme ("http"), the network location ("www.fuzzingbook.com"), or the path ("//html/APIFuzzer.html") are all properly identified. Other elements (like params, query, or fragment) are empty, because they were not part of our input.

To test urlparse(), we'd want to feed it a large set of different URLs. We can obtain these from the URL grammar we had defined in the "Grammars" chapter.

This way, we can easily test any Python function – by setting up a scaffold that runs it. How would we proceed, though, if we wanted to have a test that can be re-run again and again, without having to generate new calls every time?

Synthesizing Code¶

The "scaffolding" method, as sketched above, has an important downside: It couples test generation and test execution into a single unit, disallowing running both at different times, or for different languages. To decouple the two, we take another approach: Rather than generating inputs and immediately feeding this input into a function, we synthesize code instead that invokes functions with a given input.

For instance, if we generate the string

we can execute this string as a whole (and thus run the test) at any time:

To systematically generate such calls, we can again use a grammar:

This grammar creates calls in the form urlparse(<url>), where <url> comes from the "imported" URL grammar. The idea is to create many of these calls and to feed them into the Python interpreter.

We can now use this grammar for fuzzing and synthesizing calls to urlparse):

Just as above, we can immediately execute these calls. To better see what is happening, we define a small helper function:

If urlparse() were a C function, for instance, we could embed its call into some (also generated) C function:

Synthesizing Oracles¶

In our urlparse() example, both the Python as well as the C variant only check for generic errors in urlparse(); that is, they only detect fatal errors and exceptions. For a full test, we need to set up a specific oracle as well that checks whether the result is valid.

Our plan is to check whether specific parts of the URL reappear in the result – that is, if the scheme is http:, then the ParseResult returned should also contain a http: scheme. As discussed in the chapter on fuzzing with generators, equalities of strings such as http: across two symbols cannot be expressed in a context-free grammar. We can, however, use a generator function (also introduced in the chapter on fuzzing with generators) to automatically enforce such equalities.

Here is an example. Invoking geturl() on a urlparse() result should return the URL as originally passed to urlparse().

In a similar way, we can also check individual components of the result:

The use of generator functions may feel a bit cumbersome. Indeed, if we uniquely stick to Python, we could also create a unit test that directly invokes the fuzzer to generate individual parts:

Using such a unit test makes it easier to express oracles. However, we lose the ability to systematically cover individual URL elements and alternatives as with GrammarCoverageFuzzer as well as the ability to guide generation towards specific elements as with ProbabilisticGrammarFuzzer. Furthermore, a grammar allows us to generate tests for arbitrary programming languages and APIs.

Synthesizing Data¶

For urlparse(), we have used a very specific grammar for creating a very specific argument. Many functions take basic data types as (some) arguments, though; we therefore define grammars that generate precisely those arguments. Even better, we can define functions that generate grammars tailored towards our specific needs, returning values in a particular range, for instance.

Integers¶

We introduce a simple grammar to produce integers.

If we need integers in a specific range, we can add a generator function that does right that:

Floats¶

The grammar for floating-point values closely resembles the integer grammar.

Strings¶

Finally, we introduce a grammar for producing strings.

Synthesizing Composite Data¶

From basic data, as discussed above, we can also produce composite data in data structures such as sets or lists. We illustrate such generation on lists.

Lists¶

Our list generator takes a grammar that produces objects; it then instantiates a list grammar with the objects from these grammars.

Generators for dictionaries, sets, etc. can be defined in a similar fashion. By plugging together grammar generators, we can produce data structures with arbitrary elements.

Lessons Learned¶

• To fuzz individual functions, one can easily set up grammars that produce function calls.
• Fuzzing at the API level can be much faster than fuzzing at the system level, but brings the risk of false alarms by violating implicit preconditions.

Next Steps¶

This chapter was all about manually writing test and controlling which data gets generated. In the next chapter, we will introduce a much higher level of automation:

• Carving automatically records function calls and arguments from program executions.
• We can turn these into grammars, allowing to test these functions with various combinations of recorded values.

With these techniques, we automatically obtain grammars that already invoke functions in application contexts, making our work of specifying them much easier.

Background¶

The idea of using generator functions to generate input structures was first explored in QuickCheck [Claessen et al, 2000]. A very nice implementation for Python is the hypothesis package which allows writing and combining data structure generators for testing APIs.

Exercises¶

The exercises for this chapter combine the above techniques with fuzzing techniques introduced earlier.

Exercise 1: Deep Arguments¶

In the example generating oracles for urlparse(), important elements such as authority or port are not checked. Enrich URLPARSE_ORACLE_GRAMMAR with post-expansion functions that store the generated elements in a symbol table, such that they can be accessed when generating the assertions.

Exercise 2: Covering Argument Combinations¶

In the chapter on configuration testing, we also discussed combinatorial testing – that is, systematic coverage of sets of configuration elements. Implement a scheme that by changing the grammar, allows all pairs of argument values to be covered.

Exercise 3: Mutating Arguments¶

To widen the range of arguments to be used during testing, apply the mutation schemes introduced in mutation fuzzing – for instance, flip individual bytes or delete characters from strings. Apply this either during grammar inference or as a separate step when invoking functions.