Carving Unit Tests¶

So far, we have always generated system input, i.e. data that the program as a whole obtains via its input channels. If we are interested in testing only a small set of functions, having to go through the system can be very inefficient. This chapter introduces a technique known as carving, which, given a system test, automatically extracts a set of unit tests that replicate the calls seen during the system test. The key idea is to record such calls such that we can replay them later – as a whole or selectively. On top, we also explore how to synthesize API grammars from carved unit tests; this means that we can synthesize API tests without having to write a grammar at all.

Prerequisites

• Carving makes use of dynamic traces of function calls and variables, as introduced in the chapter on configuration fuzzing.
• Using grammars to test units was introduced in the chapter on API fuzzing.

System Tests vs Unit Tests¶

Remember the URL grammar introduced for grammar fuzzing? With such a grammar, we can happily test a Web browser again and again, checking how it reacts to arbitrary page requests.

Let us define a very simple "web browser" that goes and downloads the content given by the URL.

Let us apply this on fuzzingbook.org and measure the time, using the Timer class:

A full web browser, of course, would also render the HTML content. We can achieve this using these commands (but we don't, as we do not want to replicate the entire Web page here):

from IPython.display import HTML, display
HTML(fuzzingbook_contents)

Having to start a whole browser (or having it render a Web page) again and again means lots of overhead, though – in particular if we want to test only a subset of its functionality. In particular, after a change in the code, we would prefer to test only the subset of functions that is affected by the change, rather than running the well-tested functions again and again.

Let us assume we change the function that takes care of parsing the given URL and decomposing it into the individual elements – the scheme ("http"), the network location ("www.fuzzingbook.com"), or the path ("/html/Fuzzer.html"). This function is named urlparse():

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

The interesting thing is that executing only urlparse() is orders of magnitude faster than running all of webbrowser(). Let us measure the factor:

Compare this to the time required by the web browser

The difference in time is huge:

Hence, in the time it takes to run webbrowser() once, we can have tens of thousands of executions of urlparse() – and this does not even take into account the time it takes the browser to render the downloaded HTML, to run the included scripts, and whatever else happens when a Web page is loaded. Hence, strategies that allow us to test at the unit level are very promising as they can save lots of overhead.

Carving Unit Tests¶

Testing methods and functions at the unit level requires a very good understanding of the individual units to be tested as well as their interplay with other units. Setting up an appropriate infrastructure and writing unit tests by hand thus is demanding, yet rewarding. There is, however, an interesting alternative to writing unit tests by hand. The technique of carving automatically converts system tests into unit tests by means of recording and replaying function calls:

1. During a system test (given or generated), we record all calls into a function, including all arguments and other variables the function reads.
2. From these, we synthesize a self-contained unit test that reconstructs the function call with all arguments.
3. This unit test can be executed (replayed) at any time with high efficiency.

In the remainder of this chapter, let us explore these steps.

Recording Calls¶

Our first challenge is to record function calls together with their arguments. (In the interest of simplicity, we restrict ourselves to arguments, ignoring any global variables or other non-arguments that are read by the function.) To record calls and arguments, we use the mechanism we introduced for coverage: By setting up a tracer function, we track all calls into individual functions, also saving their arguments. Just like Coverage objects, we want to use Carver objects to be able to be used in conjunction with the with statement, such that we can trace a particular code block:

with Carver() as carver:
    function_to_be_traced()
c = carver.calls()

The initial definition supports this construct:

\todo{Get tracker from dynamic invariants}

The actual work takes place in the traceit() method, which records all calls in the _calls attribute. First, we define two helper functions:

Finally, we need some convenience functions to access the calls:

Recording my_sqrt()¶

Let's try out our new Carver class – first on a very simple function:

We can retrieve all calls seen...

... as well as the arguments of a particular function:

We define a convenience function for nicer printing of these lists:

This is a syntax we can directly use to invoke my_sqrt() again:

Carving urlparse()¶

What happens if we apply this to webbrowser()?

We see that retrieving a URL from the Web requires quite some functionality:

Among several other functions, we also have a call to urlparse():

Again, we can convert this into a well-formatted call:

Again, we can re-execute this call:

We now have successfully carved the call to urlparse() out of the webbrowser() execution.

Replaying Calls¶

Replaying calls in their entirety and in all generality is tricky, as there are several challenges to be addressed. These include:

1. We need to be able to access individual functions. If we access a function by name, the name must be in scope. If the name is not visible (for instance, because it is a name internal to the module), we must make it visible.

2. Any resources accessed outside of arguments must be recorded and reconstructed for replay as well. This can be difficult if variables refer to external resources such as files or network resources.

3. Complex objects must be reconstructed as well.

These constraints make carving hard or even impossible if the function to be tested interacts heavily with its environment. To illustrate these issues, consider the email.parser.parse() method that is invoked in webbrowser():

Calls to this method look like this:

We see that email.parser.Parser.parse() is part of a email.parser.Parser object (self) and it gets a StringIO object (fp). Both are non-primitive values. How could we possibly reconstruct them?

Serializing Objects¶

The answer to the problem of complex objects lies in creating a persistent representation that can be reconstructed at later points in time. This process is known as serialization; in Python, it is also known as pickling. The pickle module provides means to create a serialized representation of an object. Let us apply this on the email.parser.Parser object we just found:

From this string representing the serialized email.parser.Parser object, we can recreate the Parser object at any time:

The serialization mechanism allows us to produce a representation for all objects passed as parameters (assuming they can be pickled, that is). We can now extend the simple_call_string() function such that it automatically pickles objects. Additionally, we set it up such that if the first parameter is named self (i.e., it is a class method), we make it a method of the self object.

Let us apply the extended call_string() method to create a call for email.parser.parse(), including pickled objects:

With this call involving the pickled object, we can now re-run the original call and obtain a valid result:

All Calls¶

So far, we have seen only one call of webbrowser(). How many of the calls within webbrowser() can we actually carve and replay? Let us try this out and compute the numbers.

About a quarter of the calls succeed. Let us take a look into some of the error messages we get:

We see that:

• A large majority of calls could be converted into call strings. If this is not the case, this is mostly due to having non-serialized objects being passed.
• About a quarter of the calls could be executed. The error messages for the failing runs are varied; the most frequent being that some internal name is invoked that is not in scope.

Our carving mechanism should be taken with a grain of salt: We still do not cover the situation where external variables and values (such as global variables) are being accessed, and the serialization mechanism cannot recreate external resources. Still, if the function of interest falls among those that can be carved and replayed, we can very effectively re-run its calls with their original arguments.

Mining API Grammars from Carved Calls¶

So far, we have used carved calls to replay exactly the same invocations as originally encountered. However, we can also mutate carved calls to effectively fuzz APIs with previously recorded arguments.

The general idea is as follows:

1. First, we record all calls of a specific function from a given execution of the program.
2. Second, we create a grammar that incorporates all these calls, with separate rules for each argument and alternatives for each value found; this allows us to produce calls that arbitrarily recombine these arguments.

Let us explore these steps in the following sections.

From Calls to Grammars¶

Let us start with an example. The power(x, y) function returns $x^y$; it is but a wrapper around the equivalent math.pow() function. (Since power() is defined in Python, we can trace it – in contrast to math.pow(), which is implemented in C.)

Let us invoke power() while recording its arguments:

From this list of recorded arguments, we could now create a grammar for the power() call, with x and y expanding into the values seen:

When fuzzing with this grammar, we then get arbitrary combinations of x and y; aiming for coverage will ensure that all values are actually tested at least once:

What we need is a method to automatically convert the arguments as seen in power_carver to the grammar as seen in POWER_GRAMMAR. This is what we define in the next section.

A Grammar Miner for Calls¶

We introduce a class CallGrammarMiner, which, given a Carver, automatically produces a grammar from the calls seen. To initialize, we pass the carver object:

Initial Grammar¶

The initial grammar produces a single call. The possible <call> expansions are to be constructed later:

A Grammar from Arguments¶

Let us start by creating a grammar from a list of arguments. The method mine_arguments_grammar() creates a grammar for the arguments seen during carving, such as these:

The mine_arguments_grammar() method iterates through the variables seen and creates a mapping variables of variable names to a set of values seen (as strings, going through call_value()). In a second step, it then creates a grammar with a rule for each variable name, expanding into the values seen.

The additional return value var_symbols is a list of argument symbols in the call:

A Grammar from Calls¶

To get the grammar for a single function (mine_function_grammar()), we add a call to the function:

The additionally returned function_symbol holds the name of the function call just added:

A Grammar from all Calls¶

Let us now repeat the above for all function calls seen during carving. To this end, we simply iterate over all function calls seen:

The method mine_call_grammar() is the one that clients can and should use – first for mining...

...and then for fuzzing:

With this, we have successfully extracted a grammar from a recorded execution; in contrast to "simple" carving, our grammar allows us to recombine arguments and thus to fuzz at the API level.

Fuzzing Web Functions¶

Let us now apply our grammar miner on a larger API – the urlparse() function we already encountered during carving.

We can mine a grammar from the calls encountered:

This is a rather large grammar:

Here's the rule for the urlparse() function:

Here are the arguments.

If we now apply a fuzzer on these rules, we systematically cover all variations of arguments seen, including, of course, combinations not seen during carving. Again, we are fuzzing at the API level here.

Just as seen with carving, running tests at the API level is orders of magnitude faster than executing system tests. Hence, this calls for means to fuzz at the method level:

But then again, the caveats encountered during carving apply, notably the requirement to recreate the original function environment. If we also alter or recombine arguments, we get the additional risk of violating an implicit precondition – that is, invoking a function with arguments the function was never designed for. Such false alarms, resulting from incorrect invocations rather than incorrect implementations, must then be identified (typically manually) and wed out (for instance, by altering or constraining the grammar). The huge speed gains at the API level, however, may well justify this additional investment.

Lessons Learned¶

• Carving allows for effective replay of function calls recorded during a system test.
• A function call can be orders of magnitude faster than a system invocation.
• Serialization allows creating persistent representations of complex objects.
• Functions that heavily interact with their environment and/or access external resources are difficult to carve.
• From carved calls, one can produce API grammars that arbitrarily combine carved arguments.

Next Steps¶

In the next chapter, we will discuss how to reduce failure-inducing inputs.

Background¶

Carving was invented by Elbaum et al. [Elbaum et al, 2006] and originally implemented for Java. In this chapter, we follow several of their design choices (including recording and serializing method arguments only).

The combination of carving and fuzzing at the API level is described in [Kampmann et al, 2018].

Exercises¶

Exercise 1: Carving for Regression Testing¶

So far, during carving, we only have looked into reproducing calls, but not into actually checking the results of these calls. This is important for regression testing – i.e. checking whether a change to code does not impede existing functionality. We can build this by recording not only calls, but also return values – and then later compare whether the same calls result in the same values. This may not work on all occasions; values that depend on time, randomness, or other external factors may be different. Still, for functionality that abstracts from these details, checking that nothing has changed is an important part of testing.

Our aim is to design a class ResultCarver that extends CallCarver by recording both calls and return values.

In a first step, create a traceit() method that also tracks return values by extending the traceit() method. The traceit() event type is "return" and the arg parameter is the returned value. Here is a prototype that only prints out the returned values:

Part 1: Store function results¶

Extend the above code such that results are stored in a way that associates them with the currently returning function (or method). To this end, you need to keep track of the current stack of called functions.

Part 2: Access results¶

Give it a method result() that returns the value recorded for that particular function name and result:

class ResultCarver(CallCarver):
    def result(self, function_name, argument):
        """Returns the result recorded for function_name(argument"""

Part 3: Produce assertions¶

For the functions called during webbrowser() execution, create a set of assertions that check whether the result returned is still the same. Test this for urllib.parse.urlparse().

Exercise 2: Abstracting Arguments¶

When mining an API grammar from executions, set up an abstraction scheme to widen the range of arguments to be used during testing. If the values for an argument, all conform to some type T. abstract it into <T>. For instance, if calls to foo(1), foo(2), foo(3) have been seen, the grammar should abstract its calls into foo(<int>), with <int> being appropriately defined.

Do this for a number of common types: integers, positive numbers, floating-point numbers, host names, URLs, mail addresses, and more.