Tavor
CategoryTesting
SubcategoryFuzzing and delta-debugging/reducing/shrinking
Stars248
Generic fuzzing and delta-debugging framework
About Tavor
This large README is shown as a plain-text preview. Read the full README at the source
# Tavor [](https://godoc.org/github.com/zimmski/tavor) [](https://travis-ci.org/zimmski/tavor) [](https://coveralls.io/r/zimmski/tavor?branch=master)
Tavor ([Sindarin](https://en.wikipedia.org/wiki/Sindarin) for woodpecker) is a framework for easily implementing and using [fuzzing](#fuzzing) and [delta-debugging](#delta-debugging). Its [EBNF-like notation](#format) allows you to define file formats, protocols, and other structured data without the need to write source code. Tavor relaxes on the definitions of fuzzing and delta-debugging to enable the usage of its algorithms universally for keyword-driven testing, model-based testing, simulating user-behavior and genetic programming. Tavor is also well-suited for researching new methods without reimplementing basic algorithms.
### <a name="quick-example"></a>A quick example
We want to test a service which processes an XML structure. The structure can contain groups and items. A group contains other groups or items. An Item consists of an attribute `name` with an alphanumeric value. The item's value contains a number. This structure sounds simple but allows an enormous variety of possible outcomes. It is therefore hard to test since a tester has to think about every important possibility if the generation of the test data is done manually. Doing this manually is cumbersome and error-prone. Tavor can be used to automate the generation.
The described structure can be defined using the following [Tavor format](#format):
```tavor
START = Entity |
Entity = Group | Item
Group = "<group>" +(Entity) "</group>"
Item = "<item name=\"" +([\w]) "\">" +([0-9]) "</item>"
```
This file called `basic.tavor` can be downloaded [from here](examples/quick/basic.tavor).
Tavor can then be used to [fuzz](#fuzzing) the format by issuing the following command:
```bash
tavor --format-file basic.tavor fuzz
```
This command prints on every call a random generation of the given structure. Here are some example generations:
```xml
<item name="k">2</item>
```
```xml
<group><item name="kO">37</item></group>
```
```xml
<group><item name="V">37</item><group><item name="S">88</item></group></group>
```
Generating data like this is just one example of the capabilities of Tavor. Please have a look at [the complete example](#complete-example) with a broader overview over the basic features or keep reading to find out more about the background and capabilities of Tavor.
Additionally you can find official Tavor format files and fuzzer applications at [https://github.com/zimmski/fuzzer](https://github.com/zimmski/fuzzer). Announcements<sup>[1](https://groups.google.com/forum/#!msg/golang-nuts/uI6hkmYyaAU/UPz5ccT5_ZgJ)</sup> of the project's progress also include explanations, examples and roadmap information.
## <a name="table-of-content"></a>Table of content
- [What is fuzzing?](#fuzzing)
- [What is delta-debugging?](#delta-debugging)
- [What does Tavor provide and how does it work?](#tavor-provides)
+ [What are tokens?](#token)
+ [What are fuzzing strategies?](#fuzzing-strategy)
+ [What are fuzzing filters?](#fuzzing-filter)
+ [What are reduce strategies?](#reduce-strategy)
+ [Why are loops unrolled?](#unrolling)
- [The Tavor format](#format)
- [A complete example for fuzzing, executing and delta-debugging](#complete-example)
- [Where are the precompiled binaries?](#precompiled)
- [How do I build Tavor?](#build)
- [How do I use Tavor?](#use)
- [The Tavor binary](#binary)
+ [General options](#binary-general)
+ [Command: `fuzz`](#binary-fuzz)
+ [Command: `graph`](#binary-graph)
+ [Command: `reduce`](#binary-reduce)
+ [Command: `validate`](#binary-validate)
+ [Bash Completion](#bash-completion)
- [How do I develop applications with the Tavor framework?](#develop)
+ [Token structures](#develop-token-structures)
+ [Fuzzing filters](#develop-fuzzing-filters)
+ [Fuzzing strategies](#develop-fuzzing-strategies)
+ [Reduce Strategies](#develop-reduce-strategies)
- [How do I extend the Tavor framework?](#extend)
+ [Fuzzing filters](#extend-fuzzing-filters)
+ [Fuzzing strategies](#extend-fuzzing-strategies)
+ [Reduce strategies](#extend-reduce-strategies)
+ [Tokens](#extend-tokens)
+ [Token attributes](#extend-token-attributes)
+ [Typed tokens](#extend-typed-tokens)
- [How stable is Tavor?](#stability)
- [Missing features](#missing-features)
- [Can I make feature requests and report bugs and problems?](#feature-request)
## <a name="fuzzing"></a>What is fuzzing?
> Fuzz testing or fuzzing is a software testing technique, often automated or semi-automated, that involves providing invalid, unexpected, or random data to the inputs of a computer program. The program is then monitored for exceptions such as crashes, or failing built-in code assertions or for finding potential memory leaks. Fuzzing is commonly used to test for security problems in software or computer systems.
> <br/>-- <cite>[https://en.wikipedia.org/wiki/Fuzz_testing](https://en.wikipedia.org/wiki/Fuzz_testing)</cite>
Although this is the common definition of fuzzing, it is nowadays often just one view on capabilities of fuzzing tools. In general, fuzzing is just the generation of data and it does not matter if it is invalid or valid and what the type of data (e.g. files, protocol data) is. The use case of the data itself is also often broadly defined as it can be used to test algorithms, programs or hardware but it can be practically used everywhere where data is needed.
Fuzzing algorithms can be categorized into the following two main categories:
**Mutation-based fuzzing**
Mutation-based fuzzing takes existing data and simply changes it. This often leads to invalid data, as most techniques are not obeying rules nor constraints of the underlying data.
Some common techniques for mutation-based fuzzing are:
- Bit flipping: Random chosen bits of the data are flipped.
- Prepending/Appending: New data is prepended/appended to the given data.
- Repeating: Random chosen parts of the given data are repeated.
- Removal: Random chosen parts of the given data are removed.
**Generation-based fuzzing**
Generation-based algorithms have one big advantage over mutation-based algorithms in that they have to understand and obey the underlying rules and constraints of the data itself. This property can be used to generate valid as well as invalid data. Another property is that generation-based algorithms can generate data from scratch which eliminates the need for gathering data and keeping it up to date.
There are no common techniques for generation-based fuzzing but most algorithms choose a graph as underlying representation of the data model. The graph is then traversed and each node outputs a part of the data. Traversal algorithms and the complexity and abilities of the data model such as constraints between nodes or adding nodes during the traversal distinguish generation-based fuzzers and contributes in general to their mightiness.
## <a name="delta-debugging"></a>What is delta-debugging?
> The Delta Debugging algorithm isolates failure causes automatically - by systematically narrowing down failure-inducing circumstances until a minimal set remains.
> <br/>-- <cite>[https://en.wikipedia.org/wiki/Delta_Debugging](https://en.wikipedia.org/wiki/Delta_Debugging)</cite>
Data which fails the execution of a program can be reduced by using delta-debugging. The reduction of the data is handled by software heuristics (semi-)automatically. The obvious advantage of this method, besides being done (semi-)automatically, is that it is not necessary to handle unrelated parts of the data while debugging the problem. This makes it possible to focus on the important parts which actually lead to the failure.
> **Note:** Literature and the computer science community do not agree on one common name for delta-debugging.
>
> Besides `delta-debugging` the following names are fairly common for the same technique:
>
> - Since data is reduced it is also called `reducing`.
> - Since data is shrinking it is also called `shrinking`.
Delta-debugging consists of three areas:
- **Search**
Decide which part of the data will be reduced next.
- **Reduction**
Remove repetitions and optional data or replace data with something else e.g. replace an uninteresting complex function with a constant value.
- **Testing**
Test if the reduced data still provokes the original failure.
Although delta-debugging is described as method to isolate failure causes, it can be also used to isolate anything given isolating constraints. For instance a solution may be reduced to its optimum e.g. smallest formula.
## <a name="tavor-provides"></a>What does Tavor provide and how does it work?
Tavor combines both fuzzing and delta-debugging by allowing all implemented methods to operate on one internal model-based structure represented by a graph. This structure can be defined and generated by programming or by using a format file. Out of the box Tavor comes with its own [format](#format) which covers all functionality of the framework.
Tavor's generic fuzzing implementation is not fixed to one technique. Instead different fuzzing techniques and heuristics can be implemented and executed independently as [Tavor fuzzing strategies](#fuzzing-strategy). The same principle is used for delta-debugging where so called [Tavor reduce strategies](#reduce-strategy) can be implemented and used. Both types of strategies operate on the same internal structure independent of the format. This structure is basically a graph of nodes which are called [tokens](#token) throughout the Tavor framework. The structure itself is not fixed to a static definition but can be changed by so called [fuzzing filters](#fuzzing-filter) to perform additional tasks like boundary-value analysis of ranges.
Even though Tavor provides a lot of functionality out of the box, it is not considered as complete. A list of missing but planed features can be found in the [missing features section](#missing-features). For feature requests please have a look at the [feature request section](#feature-request).
### <a name="token"></a>What are tokens?
Tavor's tokens differ from *lexical analysis tokens* in the following way. They represent not just a group of characters but different kinds of data with additional properties and abilities. Tokens can be constant integers and strings of all kind but also dynamic data like integer ranges, sequences and character classes. Furthermore, tokens can encapsulate other tokens to not only group them together but to create building blocks that can be reused to, for example, repeat a group of tokens. Tokens can have states, conditions and logic. They can create new tokens dynamically and can depend on other tokens to generate data. Tavor's tokens are basically the foundation of the framework and every algorithm for fuzzing, parsing and delta-debugging is using them.
If you want to know more about Tavor's tokens you can read through [Tavor's format definition](#format) or you can read about them in depth in the [developing](#develop) and [extending](#extend) sections.
### <a name="fuzzing-strategy"></a>What are fuzzing strategies?
Each fuzzing strategy represents one fuzzing technique. This can be a heuristic for walking through the internal structure, how tokens of the structure are fuzzed or even both. Tavor currently distinguishes between two techniques of token fuzzing. One is to deterministically choose one possible permutation of the token the other is choosing randomly out of all permutations of a token.
An example for a fuzzing strategy is the [random fuzzing strategy](https://godoc.org/github.com/zimmski/tavor/fuzz/strategy#RandomStrategy) which is Tavor's default. This fuzzing strategy traverses through the whole internal structure and randomly permutates each token.
Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/fuzz/strategy) for an overview of all officially available fuzzing strategies of Tavor.
### <a name="fuzzing-filter"></a>What are fuzzing filters?
Fuzzing filters mutate the internal structure and can be applied after the structure is ready for fuzzing thus after creating it e.g. after parsing and unrolling. This can be associated to [mutation-based fuzzing](#fuzzing) where not the generating structure but the data itself is mutated.
An example use-case for fuzzing filters is the [boundary-value analysis](https://en.wikipedia.org/wiki/Boundary-value_analysis) software testing technique. Imagine a function which should be tested having one integer parameter. The parameter's valid values range from 1 to 100. This would lead to 100 possible values which have to be tested just for this one integer and thus to at least 100 permutations of the internal structure. Boundary-value analysis reduces these permutations to e.g. 1, 50 and 100 so just three instead of 100 cases. This is exactly what the [PositiveBoundaryValueAnalys is fuzzing filter](https://godoc.org/github.com/zimmski/tavor/fuzz/filter#PositiveBoundaryValueAnalysisFilter) does. This fuzzing filter traverses the whole internal structure and replaces every range token with at most five boundary values.
Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/fuzz/filter) for an overview of all officially available fuzzing filters of Tavor.
### <a name="reduce-strategy"></a>What are reduce strategies?
Reduce strategies are strongly comparable to fuzzing strategies. Each reduce strategy represents one reduce/delta-debugging technique. This can be a heuristic for walking through the internal structure, how tokens of the structure are reduced or even both. The reduction method is depending on the token type. For example a constant integer cannot be reduced any further but a repetition of optional strings can be minimized or even left out.
Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/reduce/strategy) for an overview of all officially available reduce strategies of Tavor.
### <a name="unrolling"></a>Why are loops unrolled?
Although the internal structure allows loops in its graph, Tavor currently unrolls loops for easier algorithm implementations and usage. A future version will supplement this by allowing loops.
This graph for example loops between the states `Idle` and `Action`:
Unrolling this example results in the following graph given a maximum of two repetitions:
## <a name="format"></a>The Tavor format
The Tavor format documentation has its own [page which can be found here](/doc/format.md).
## <a name="complete-example"></a>A complete example for fuzzing, executing and delta-debugging
The complete example has its own [page which can be found here](/doc/complete-example.md).
## <a name="precompiled"></a>Where are the precompiled binaries?
You can find all precompiled binaries on the [release page](https://github.com/zimmski/tavor/releases). Currently only 32 and 64 bit Linux binaries are provided. Other architectures are currently not supported, but might work. Please have a look at the [feature request section](#feature-request) if you need them to work or if you want more binaries for different architectures.
## <a name="build"></a>How do I build Tavor?
If you do not want to use the [precompiled binaries](#precompiled) but instead want to compile Tavor from scratch, just follow the these steps:
> **Note:** All steps must execute without any errors.
1. Install and configure Go
At least version 1.4 must be used. Your distribution will most definitely have some packages or you can be brave and just install it yourself. Have a look at [the official documentation](http://golang.org/doc/install). Good luck!
2. Go-get Tavor
```bash
go get github.com/zimmski/tavor/
```
3. Make Tavor
```bash
cd $GOPATH/src/github.com/zimmski/tavor
make
```
You now have a binary `tavor` in your `$GOPATH/bin` folder (or if set `$GOBIN` folder) which can be used without any further actions.
## <a name="use"></a>How do I use Tavor?
Tavor can be used in three different ways:
- [Using the binary](#binary) which makes everything officially provided by the Tavor framework available via the command line.
- [Developing applications with the Tavor framework](#develop) by implementing the internal structure via code and doing everything else like fuzzing and delta-debugging via code too.
- [Extending the Tavor framework](#extend) because of research or missing features.
## <a name="binary"></a>The Tavor binary
The [Tavor binary](#precompiled) provides fuzzing and delta-debugging functionality for Tavor format files as well as some other commands. Sane default arguments should provide a pleasant experience.
Since the binary acts on Tavor format files, the `--format-file` argument has to be used for every non-informational action. E.g. the following command fuzzes the given format file with the default fuzzing strategy:
```bash
tavor --format-file file.tavor fuzz
```
In contrast listing all available fuzzing strategies does not require the `--format-file` argument:
```bash
tavor fuzz --list-strategies
```
To learn more about available arguments and commands, you can invoke the help by executing the binary without any arguments or with the `--help` argument.
Here is a complete overview of all arguments, commands and their options:
```
Usage:
tavor [options] <command> [command options]
General options:
--debug Debug log output
--help Show this help message
--verbose Verbose log output
--version Print the version of this program
Global options:
--seed= Seed for all the randomness
--max-repeat= How many times loops and repetitions should be repeated (2)
Format file options:
--check Just check the syntax of the format file and exit
--format-file= Input tavor format file
--print Prints the AST of the parsed format file
--print-internal Prints the internal AST of the parsed format file
Available commands:
fuzz Fuzz the given format file
graph Generate a DOT file out of the internal AST
reduce Reduce the given input file
validate Validate the given input file
[fuzz command options]
--exec= Execute this binary with possible arguments to test a generation
--exec-exact-exit-code= Same exit code has to be present (-1)
--exec-exact-stderr= Same stderr output has to be present
--exec-exact-stdout= Same stdout output has to be present
--exec-match-stderr= Searches through stderr via the given regex. A match has to be present
--exec-match-stdout= Searches through stdout via the given regex. A match has to be present
--exec-do-not-remove-tmp-files If set, tmp files are not removed
--exec-do-not-remove-tmp-files-on-error If set, tmp files are not removed on error
--exec-argument-type= How the generation is given to the binary (stdin)
--list-exec-argument-types List all available exec argument types
--script= Execute this binary which gets fed with the generation and should return feedback
--exit-on-error Exit if an execution fails
--filter= Fuzzing filter to applyFrequently Asked Questions
What is Tavor?
Tavor is a Testing library for the Go programming language. Generic fuzzing and delta-debugging framework
How do I install Tavor?
Install Tavor with the Go module system using `go get zimmski/tavor`. Check the repository for the current installation instructions.
What category does Tavor belong to?
Tavor is listed under Testing, specifically Fuzzing and delta-debugging/reducing/shrinking.