Testing Configurations¶

The behavior of a program is not only governed by its data. The configuration of a program – that is, the settings that govern the execution of a program on its (regular) input data, as set by options or configuration files – just as well influences behavior, and thus can and should be tested. In this chapter, we explore how to systematically test and cover software configurations. By automatically inferring configuration options, we can apply these techniques out of the box, with no need for writing a grammar. Finally, we show how to systematically cover combinations of configuration options, quickly detecting unwanted interferences.

Prerequisites

• You should have read the chapter on grammars.
• You should have read the chapter on grammar coverage.

Configuration Options¶

When we talk about the input to a program, we usually think of the data it processes. This is also what we have been fuzzing in the past chapters – be it with random input, mutation-based fuzzing, or grammar-based fuzzing. However, programs typically have several input sources, all of which can and should be tested – and included in test generation.

One important source of input is the program's configuration – that is, a set of inputs that typically is set once when beginning to process data and then stays constant while processing data, while the program is running, or even while the program is deployed. Such a configuration is frequently set in configuration files (for instance, as key/value pairs); the most ubiquitous method for command-line tools, though, are configuration options on the command line.

As an example, consider the grep utility to find textual patterns in files. The exact mode by which grep works is governed by a multitude of options, which can be listed by providing a --help option:

All these options need to be tested for whether they operate correctly. In security testing, any such option may also trigger a yet unknown vulnerability. Hence, such options can become fuzz targets on their own. In this chapter, we analyze how to systematically test such options – and better yet, how to extract possible configurations right out of given program files, such that we do not have to specify anything.

Options in Python¶

Let us stick to our common programming language here and examine how options are processed in Python. The argparse module provides a parser for command-line arguments (and options) with great functionality – and great complexity. You start by defining a parser (argparse.ArgumentParser()) to which individual arguments with various features are added, one after another. Additional parameters for each argument can specify the type (type) of the argument (say, integers or strings), or the number of arguments (nargs).

By default, arguments are stored under their name in the args object coming from parse_args() – thus, args.integers holds the integer arguments added earlier. Special actions (actions) allow storing specific values in given variables; the store_const action stores the given const in the attribute named by dest. The following example takes a number of integer arguments (integers) as well as an operator (--sum, --min, or --max) to be applied on these integers. The operators all store a function reference in the accumulate attribute, which is finally invoked on the integers parsed:

Here's how process_numbers() works. We can, for instance, invoke the --min option on the given arguments to compute the minimum:

Or compute the sum of three numbers:

When defined via add_mutually_exclusive_group() (as above), options are mutually exclusive. Consequently, we can have only one operator:

A Grammar for Configurations¶

How can we test a system with several options? The easiest answer is to write a grammar for it. The grammar PROCESS_NUMBERS_EBNF_GRAMMAR reflects the possible combinations of options and arguments:

We can feed this grammar into our grammar coverage fuzzer and have it cover one option after another:

Of course, we can also invoke process_numbers() with these very arguments. To this end, we need to convert the string produced by the grammar back into a list of individual arguments, using split():

Similarly, we can define grammars for any program to be tested; as well as define grammars for, say, configuration files. Yet, the grammar has to be updated with every change to the program, which creates a maintenance burden. Given that the information required for the grammar is already all encoded in the program, the question arises: Can't we go and extract configuration options right out of the program in the first place?

Mining Configuration Options¶

In this section, we try to extract option and argument information right out of a program, such that we do not have to specify a configuration grammar. The aim is to have a configuration fuzzer that works on the options and arguments of an arbitrary program, as long as it follows specific conventions for processing its arguments. In the case of Python programs, this means using the argparse module.

Our idea is as follows: We execute the given program up to the point where the arguments are actually parsed – that is, argparse.parse_args() is invoked. Up to this point, we track all calls into the argument parser, notably those calls that define arguments and options (add_argument()). From these, we construct the grammar.

Tracking Arguments¶

Let us illustrate this approach with a simple experiment: We define a trace function (see our chapter on coverage for details) that is active while process_numbers is invoked. If we have a call to a method add_argument, we access and print out the local variables (which at this point are the arguments to the method).

What we get is a list of all calls to add_argument(), together with the method arguments passed:

From the args argument, we can access the individual options and arguments to be defined:

We see that each argument comes as a tuple with one (say, integers or --sum) or two members (-h and --help), which denote alternate forms for the same option. Our job will be to go through the arguments of add_arguments() and detect not only the names of options and arguments, but also whether they accept additional parameters, as well as the type of the parameters.

A Grammar Miner for Options and Arguments¶

Let us now build a class that gathers all this information to create a grammar.

We use the ParseInterrupt exception to interrupt program execution after gathering all arguments and options:

The class OptionGrammarMiner takes an executable function for which the grammar of options and arguments is to be mined:

The method mine_ebnf_grammar() is where everything happens. It creates a grammar of the form

<start> ::= <option>* <arguments>
<option> ::= <empty>
<arguments> ::= <empty>

in which the options and arguments will be collected. It then sets a trace function (see our chapter on coverage for details) that is active while the previously defined function is invoked. Raising ParseInterrupt (when parse_args() is invoked) ends execution.

The trace function checks for four methods: add_argument() is the most important function, resulting in processing arguments; frame.f_locals again is the set of local variables, which at this point is mostly the arguments to add_argument(). Since mutually exclusive groups also have a method add_argument(), we set the flag in_group to differentiate.

Note that we make no specific efforts to differentiate between multiple parsers or groups; we simply assume that there is one parser, and at any point at most one mutually exclusive group.

The process_arguments() now analyzes the arguments passed and adds them to the grammar:

• If the argument starts with -, it gets added as an optional element to the <option> list
• Otherwise, it gets added to the <argument> list.

The optional nargs argument specifies how many arguments can follow. If it is a number, we add the appropriate number of elements to the grammar; if it is an abstract specifier (say, + or *), we use it directly as EBNF operator.

Given the large number of parameters and optional behavior, this is a somewhat messy function, but it does the job.

The method add_parameter() handles possible parameters of options. If the argument has an action defined, it takes no parameter. Otherwise, we identify the type of the parameter (as int or str) and augment the grammar with an appropriate rule.

The method add_type_rule() adds a rule for parameter types to the grammar. If the parameter is identified by a meta-variable (say, N), we add a rule for this as well to improve legibility.

The method add_group() adds a new mutually exclusive group to the grammar. We define a new symbol (say, <group>) for the options added to the group, and use the required and exclusive flags to define an appropriate expansion operator. The group is then prefixed to the grammar, as in

<start> ::= <group><option>* <arguments>
<group> ::= <empty>

and filled with the next calls to add_argument() within the group.

That's it! With this, we can now extract the grammar from our process_numbers() program. Turning on logging again reveals the variables we draw upon.

Here is the extracted grammar:

The grammar properly identifies the group found:

It also identifies a --help option provided not by us, but by the argparse module:

The grammar also correctly identifies the types of the arguments:

The rules for int are set as defined by add_int_rule()

We can take this grammar and convert it to BNF, such that we can fuzz with it right away:

Each and every invocation adheres to the rules as set forth in the argparse calls. By mining options and arguments from existing programs, we can now fuzz these options out of the box – without having to specify a grammar.

Testing Autopep8¶

Let us try out the option grammar miner on real-world Python programs. autopep8 is a tool that automatically converts Python code to the PEP 8 Style Guide for Python Code. (Actually, all Python code in this book runs through autopep8 during production.) autopep8 offers a wide range of options, as can be seen by invoking it with --help:

Autopep8 Setup¶

We want to systematically test these options. In order to deploy our configuration grammar miner, we need to find the source code of the executable:

Next, we build a function that reads the contents of the file and executes it.

Mining an Autopep8 Grammar¶

We can use the autopep8() function in our grammar miner:

and extract a grammar for it:

This works because here, autopep8 is not a separate process (and a separate Python interpreter), but we run the autopep8() function (and the autopep8 code) in our current Python interpreter – up to the call to parse_args(), where we interrupt execution again. At this point, the autopep8 code has done nothing but setting up the argument parser – which is what we are interested in.

The grammar options mined reflect precisely the options seen when providing --help:

Metavariables like <n> or <line> are placeholders for integers. We assume all metavariables of the same name have the same type:

The grammar miner has inferred that the argument to autopep8 is a list of files:

which in turn all are strings:

As we are only interested in testing options, not arguments, we fix the arguments to a single mandatory input. (Otherwise, we'd have plenty of random file names generated.)

Creating Autopep8 Options¶

Let us now use the inferred grammar for fuzzing. Again, we convert the EBNF grammar into a regular BNF grammar:

And we can use the grammar for fuzzing all options:

Let us apply these options on the actual program. We need a file foo.py that will serve as input: (Note that the following commands will overwrite the file foo.py, if it already exists in the current working directory. Be aware of this, if you downloaded the notebooks and are working locally.)

We see how autopep8 fixes the spacing:

Let us now put things together. We define a ProgramRunner that will run the autopep8 executable with arguments coming from the mined autopep8 grammar.

Running autopep8 with the mined options reveals a surprisingly high number of passing runs. (We see that some options depend on each other or are mutually exclusive, but this is handled by the program logic, not the argument parser, and hence out of our scope.) The GrammarCoverageFuzzer ensures that each option is tested at least once. (Digits and letters, too, by the way.)

Our foo.py file now has been formatted in place a number of times:

We don't need it anymore, so we clean up things:

Classes for Fuzzing Configuration Options¶

Let us now create reusable classes that we can use for testing arbitrary programs. (Okay, make that "arbitrary programs that are written in Python and use the argparse module to process command-line arguments.")

The class OptionRunner is a subclass of ProgramRunner that takes care of automatically determining the grammar, using the same steps we used for autopep8, above.

First, we find the contents of the Python executable:

Next, we determine the grammar using the OptionGrammarMiner class:

The two service methods set_arguments() and set_invocation() help us to change the arguments and program, respectively.

We can instantiate the class on autopep8 and immediately get the grammar:

An OptionFuzzer interacts with the given OptionRunner to obtain its grammar, which is then passed to its GrammarCoverageFuzzer superclass.

When invoking run(), the OptionFuzzer creates a new invocation (using fuzz() from its grammar) and runs the now given (or previously set) runner with the arguments from the grammar. Note that the runner specified in run() can differ from the one set during initialization; this allows for mining options from one program and applying it in another context.

Example: Autopep8¶

Let us apply our newly defined classes on the autopep8 runner:

We can now systematically test autopep8 with these classes:

Example: MyPy¶

We can extract options for the mypy static type checker for Python:

Example: Notedown¶

Here's the configuration options for the notedown Notebook to Markdown converter:

Combinatorial Testing¶

Our CoverageGrammarFuzzer does a good job in covering each and every option at least once, which is great for systematic testing. However, as we also can see in our examples above, some options require each other, while others interfere with each other. What we should do as good testers is not only to cover every option individually, but also combinations of options.

The Python itertools module gives us means to create combinations from lists. We can, for instance, take the notedown options and create a list of all pairs.

There's quite a number of pairs:

Testing every such pair of options frequently suffices to cover all interferences between options. (Programs rarely have conditions involving three or more configuration settings.) To this end, we change the grammar from having a list of options to having a list of option pairs, such that covering these will automatically cover all pairs.

We create a function pairwise() that takes a list of options as occurring in our grammar and returns a list of pairwise options – that is, our original options, but concatenated.

Here's the first 20 pairs:

The new grammar pairwise_notedown_grammar is a copy of the notedown grammar, but with the list of options replaced with the above pairwise option list.

Using the "pairwise" grammar to fuzz now covers one pair after another:

Can we actually test all combinations of options? Not in practice, as the number of combinations quickly grows as the length increases. It decreases again as the number of options reaches the maximum (with 20 options, there is only 1 combination involving all options), but the absolute numbers are still staggering:

Formally, the number of combinations of length $k$ in a set of options of length $n$ is the binomial coefficient $$ {n \choose k} = \frac{n!}{k!(n - k)!} $$

which for $k = 2$ (all pairs) gives us

$$ {n \choose 2} = \frac{n!}{2(n - 2)!} = \frac{n (n - 1)}{2} $$

For autopep8 with its 30 options...

... we thus need 870 tests to cover all pairs:

For mypy with its 140+ options, though, we already end up with 20,000+ tests to be conducted:

Even if each pair takes a second to run, we'd still be done in three hours of testing, though.

If your program has more options that you all want to get covered in combinations, it is advisable that you limit the number of configurations further – for instance by limiting combinatorial testing to those combinations that possibly can interact with each other; and covering all other (presumably orthogonal) options individually.

This mechanism of creating configurations by extending grammars can be easily extended to other configuration targets. One may want to explore a greater number of configurations, or expansions in specific contexts. The exercises, below, have a number of options ready for you.

Lessons Learned¶

• Besides regular input data, program configurations make an important testing target.
• For a given program using a standard library to parse command-line options and arguments, one can automatically extract these and convert them into a grammar.
• To cover not only single options, but combinations of options, one can expand the grammar to cover all pairs, or come up with even more ambitious targets.

Next Steps¶

If you liked the idea of mining a grammar from a program, do not miss:

• how to mine grammars for input data

Our next steps in the book focus on:

• how to parse and recombine inputs
• how to assign weights and probabilities to specific productions
• how to simplify inputs that cause a failure

Background¶

Although configuration data is just as likely to cause failures as other input data, it has received relatively little attention in test generation – possibly because, unlike "regular" input data, configuration data is not so much under control of external parties, and because, again unlike regular data, there is little variance in configurations. Creating models for software configurations and using these models for testing is commonplace, as is the idea of pairwise testing. For an overview, see [Pezzè et al, 2008]; for a discussion and comparison of state-of-the-art techniques, see [J. Petke et al, 2015].

More specifically, [Sutton et al, 2007] also discuss techniques to systematically cover command-line options. Dai et al. [Dai et al, 2010] apply configuration fuzzing by changing variables associated with configuration files.

Exercises¶

Exercise 1: #ifdef Configuration Fuzzing¶

In C programs, the C preprocessor can be used to choose which code parts should be compiled and which ones should not. As an example, in the C code

#ifdef LONG_FOO
long foo() { ... }
#else
int foo() { ... }
#endif

the compiler will compile the function foo() with return typelong if the preprocessor variable LONG_FOO is defined, and with return type int if not. Such preprocessor variables are either set in the source files (using #define, as in #define LONG_FOO) or on the C compiler command line (using -D<variable> or -D<variable>=<value>, as in -DLONG_FOO.

Such conditional compilation is used to configure C programs towards their environment. System-specific code can contain lots of conditional compilation. As an example, consider this excerpt of xmlparse.c, the XML parser that is part of the Python runtime library:

#if defined(_WIN32) && !defined(LOAD_LIBRARY_SEARCH_SYSTEM32)
# define LOAD_LIBRARY_SEARCH_SYSTEM32  0x00000800
#endif

#if !defined(HAVE_GETRANDOM) && !defined(HAVE_SYSCALL_GETRANDOM) \
    && !defined(HAVE_ARC4RANDOM_BUF) && !defined(HAVE_ARC4RANDOM) \
    && !defined(XML_DEV_URANDOM) \
    && !defined(_WIN32) \
    && !defined(XML_POOR_ENTROPY)
# error
#endif

#if !defined(TIOCSWINSZ) || defined(__SCO__) || defined(__UNIXWARE__)
#define USE_SYSV_ENVVARS    /* COLUMNS/LINES vs. TERMCAP */
#endif

#ifdef XML_UNICODE_WCHAR_T
#define XML_T(x) (const wchar_t)x
#define XML_L(x) L ## x
#else
#define XML_T(x) (const unsigned short)x
#define XML_L(x) x
#endif

int fun(int x) { return XML_T(x); }

A typical configuration for the C preprocessor on the above code could be cc -c -D_WIN32 -DXML_POOR_ENTROPY -DXML_UNICODE_WCHAR_T xmlparse.c, defining the given preprocessor variables and selecting the appropriate code fragments.

Since the compiler can only compile one configuration at a time (implying that we can also only test one resulting executable at a time), your task is to find out which of these configurations actually compile. To this end, proceed in three steps.

Part 1: Extract Preprocessor Variables¶

Write a function cpp_identifiers() that, given a set of lines (say, from open(filename).readlines()), extracts all preprocessor variables referenced in #if or #ifdef preprocessor instructions. Apply ifdef_identifiers() on the sample C input above, such that

cpp_identifiers(open("xmlparse.c").readlines())

returns the set

{'_WIN32', 'LOAD_LIBRARY_SEARCH_SYSTEM32', 'HAVE_GETRANDOM', 'HAVE_SYSCALL_GETRANDOM', 'HAVE_ARC4RANDOM_BUF', ...}

Part 2: Derive an Option Grammar¶

With the help of cpp_identifiers(), create a grammar which has C compiler invocations with a list of options, where each option takes the form -D<variable> for a preprocessor variable <variable>. Using this grammar cpp_grammar, a fuzzer

g = GrammarCoverageFuzzer(cpp_grammar)

would create C compiler invocations such as

[g.fuzz() for i in range(10)]
['cc -DHAVE_SYSCALL_GETRANDOM xmlparse.c',
 'cc -D__SCO__ -DRANDOM_BUF -DXML_UNICODE_WCHAR_T -D__UNIXWARE__ xmlparse.c',
 'cc -DXML_POOR_ENTROPY xmlparse.c',
 'cc -DRANDOM xmlparse.c',
 'cc -D_WIN xmlparse.c',
 'cc -DHAVE_ARC xmlparse.c', ...]

Part 3: C Preprocessor Configuration Fuzzing¶

Using the grammar just produced, use a GrammarCoverageFuzzer to

1. Test each processor variable individually
2. Test each pair of processor variables, using pairwise().

What happens if you actually run the invocations?

Exercise 2: .ini Configuration Fuzzing¶

Besides command-line options, configuration files are another important source of configurations. In this exercise, we will consider the very simple configuration language provided by the Python ConfigParser module, which is very similar to what is found in Microsoft Windows .ini files.

The following example for a ConfigParser input file stems right from the ConfigParser documentation:

[DEFAULT]
ServerAliveInterval = 45
Compression = yes
CompressionLevel = 9
ForwardX11 = yes

[bitbucket.org]
User = hg

[topsecret.server.com]
Port = 50022
ForwardX11 = no

The above ConfigParser file can be created programmatically:

and be read in again:

Part 1: Read Configuration¶

Using configparser, create a program reading in the above configuration file and accessing the individual elements.

Part 2: Create a Configuration Grammar¶

Design a grammar that will automatically create configuration files suitable for your above program. Fuzz your program with it.

Part 3: Mine a Configuration Grammar¶

By dynamically tracking the individual accesses to configuration elements, you can again extract a basic grammar from the execution. To this end, create a subclass of ConfigParser with a special method __getitem__:

For a TrackingConfigParser object p, p.__getitem__(key) will be invoked whenever p[key] is accessed:

Using __getitem__(), as above, implement a tracking mechanism that, while your program accesses the read configuration, automatically saves options accessed and values read. Create a prototype grammar from these values; use it for fuzzing.

At the end, don't forget to clean up:

Exercise 3: Extracting and Fuzzing C Command-Line Options¶

In C programs, the getopt() function are frequently used to process configuration options. A call

getopt(argc, argv, "bf:")

indicates that the program accepts two options -b and -f, with -f taking an argument (as indicated by the following colon).

Part 1: Getopt Fuzzing¶

Write a framework which, for a given C program, automatically extracts the argument to getopt() and derives a fuzzing grammar for it. There are multiple ways to achieve this:

1. Scan the program source code for occurrences of getopt() and return the string passed. (Crude, but should frequently work.)
2. Insert your own implementation of getopt() into the source code (effectively replacing getopt() from the runtime library), which outputs the getopt() argument and exits the program. Recompile and run.
3. (Advanced.) As above, but instead of changing the source code, hook into the dynamic linker which at runtime links the program with the C runtime library. Set the library loading path (on Linux and Unix, this is the LD_LIBRARY_PATH environment variable) such that your own version of getopt() is linked first, and the regular libraries later. Executing the program (without recompiling) should yield the desired result.

Apply this on grep and ls; report the resulting grammars and results.

Part 2: Fuzzing Long Options in C¶

Same as Part 1, but also hook into the GNU variant getopt_long(), which accepts "long" arguments with double dashes such as --help. Note that method 1, above, will not work here, since the "long" options are defined in a separately defined structure.

Exercise 4: Expansions in Context¶

In our above option configurations, we have multiple symbols which all expand to the same integer. For instance, the --line-range option of autopep8 takes two <line> parameters which both expand into the same <int> symbol:

<option> ::= ... | --line-range <line> <line> | ...
<line> ::= <int>
<int> ::= (-)?<digit>+
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Once the GrammarCoverageFuzzer has covered all variations of <int> (especially by covering all digits) for one option, though, it will no longer strive to achieve such coverage for the next option. Yet, it could be desirable to achieve such coverage for each option separately.

One way to achieve this with our existing GrammarCoverageFuzzer is again to change the grammar accordingly. The idea is to duplicate expansions – that is, to replace an expansion of a symbol $s$ with a new symbol $s'$ whose definition is duplicated from $s$. This way, $s'$ and $s$ are separate symbols from a coverage point of view and would be independently covered.

As an example, consider again the above --line-range option. If we want our tests to independently cover all elements of the two <line> parameters, we can duplicate the second <line> expansion into a new symbol <line'> with subsequent duplicated expansions:

<option> ::= ... | --line-range <line> <line'> | ...
<line> ::= <int>
<line'> ::= <int'>
<int> ::= (-)?<digit>+
<int'> ::= (-)?<digit'>+
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit'> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Design a function inline(grammar, symbol) that returns a duplicate of grammar in which every occurrence of <symbol> and its expansions become separate copies. The above grammar could be a result of inline(autopep8_runner.ebnf_grammar(), "<line>").

When copying, expansions in the copy should also refer to symbols in the copy. Hence, when expanding <int> in

<int> ::= <int><digit>

make that

``` ::=

<int'> ::= <int'><digit'> ```

(and not <int'> ::= <int><digit'> or <int'> ::= <int><digit>).

Be sure to add precisely one new set of symbols for each occurrence in the original grammar, and not to expand further in the presence of recursion.