<commit_before># Tavor [![GoDoc](https://godoc.org/github.com/zimmski/tavor?status.png)](https://godoc.org/github.com/zimmski/tavor) [![Build Status](https://travis-ci.org/zimmski/tavor.svg?branch=master)](https://travis-ci.org/zimmski/tavor) [![Coverage Status](https://coveralls.io/repos/zimmski/tavor/badge.png)](https://coveralls.io/r/zimmski/tavor)

Tavor ([Sindarin](https://en.wikipedia.org/wiki/Sindarin) for "woodpecker") is a [fuzzing](#fuzzing) and [delta-debugging](#delta-debugging) platform, which provides a framework and binary to not only implement and do everyday fuzzing and delta-debugging but to also do research on new methods without implementing basic algorithms again. A [EBNF-like notations](#format) allows the definition of data (e.g. file formats and protocols) without the need of programming. Tavor also relaxes on the definitions of fuzzing and delta-debugging allowing the user to utilize implemented techniques universally e.g. for key-driven testing, model-based testing, simulating user-behavior and genetic programming.

### <a name="quick-example"></a>A quick example

Imagine a vending machine which ejects a product after receiving 100 worth of credits. It is possible to input 25 and 50 credit coins into the machine. After receiving enough credits the machine ejects a product and resets the credit counter to zero. To keep it simple, we specify that the machine does not handle credit overflows. A representation of the states and actions of the machine could look like this:

![Basic states and actions](examples/quick/basic.png "Basic states and actions")

This state machine can be defined using the following [Tavor format file](#format):

```
START = Credit0

Credit0   = "Credit0"   "\n" ( Coin25 Credit25 | Coin50 Credit50 | )
Credit25  = "Credit25"  "\n" ( Coin25 Credit50 | Coin50 Credit75 )
Credit50  = "Credit50"  "\n" ( Coin25 Credit75 | Coin50 Credit100 )
Credit75  = "Credit75"  "\n" Coin25 Credit100
Credit100 = "Credit100" "\n" Vend Credit0

Coin25 = "Coin25" "\n"
Coin50 = "Coin50" "\n"

Vend = "Vend" "\n"
```
(Please note that the new line escape sequences "\n" are just defined to make the output prettier)

You can download this file called [<code>basic.tavor</code> from here](examples/quick/basic.tavor).

Now we can use Tavor to [fuzz](#fuzzing) the format by issuing the following command:

```bash
tavor --format-file basic.tavor fuzz
```

On every call this command outputs random paths through the defined graph. Here are some example outputs:

```
Credit0
```

```
Credit0
Coin50
Credit50
Coin50
Credit100
Vend
Credit0
```

```
Credit0
Coin25
Credit25
Coin50
Credit75
Coin25
Credit100
Vend
Credit0
```

Generating data like this is just one example of the capabilities of Tavor. Please have a look [here](#bigexample) if you like to see a bigger example with a complete overview over the basic features or keep reading to find out more about the background and capabilities of Tavor.

## <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.
> -- <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. Fuzzing is in general 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 two areas:

- **mutation-based**

	Mutation-based fuzzing takes existing data and simply changes it. This often leads to invalid data, as most techniques are not obeying constraints nor rules of the underlying data.

	Some common technique 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**

	Generation-based algorithms have one big advantage over mutation-based in that they have to understand and obey the underlying constraints and rules of the data itself. This property can be used to generate valid as well as invalid data. Another property is that generation-based algorithms 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. The traversal algorithms and the complexity and abilities of the data model like constraints between nodes or adding nodes during the traversal distinguish generation-based fuzzers and contribute 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.
> -- <cite>[https://en.wikipedia.org/wiki/Delta_Debugging](https://en.wikipedia.org/wiki/Delta_Debugging)</cite>

E.g. we feed a given data to a program which fails on executing. By delta-debugging this data we can reduce it to its minimum while still failing the execution. 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 we do not need to handle uninteresting parts of the data while debugging the problem, we can focus on the important parts which actually lead to the failure.

**Note**: Since delta-debugging reduces data it is also called <code>reducing</code>.

Delta-debugging consists of three areas:
- A heuristic has to decide which parts of the data will be reduced next
- The reduction itself e.g.
	- Remove repetitions
	- Remove optional data
	- Replace data with something else e.g. replace an uninteresting complex function with a constant value
- Testing the new resulting data concerning the failure

Although delta-debugging is described as method to isolate failure causes, it can be also used to isolate anything given isolating constraints. For example we could reduce an input for a program which leads to a positive outcome to its minimum.

## How does Tavor work and what does it provide?

Tavor combines both fuzzing and delta-debugging into one platform by allowing all implemented methods to operate on one internal model-based structure represented by a graph. This structure can be defined and generated programmatically or by using a format file. Out of the box Tavor comes with its own [format](#format) which covers all functionality of the Tavor framework itself.

Tavor's fuzzing implementation is generically and not fixed to one technique nor format. 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.

Even tough Tavor provides loads of functionality out of the box a lot is still missing. A list of missing but planed features can be found in the [missing features section](#missing-features). For feature request please have a look at the [feature request section](#feature-request).

### <a name="token"></a>What are tokens?

TODO mention in "How does Tavor work and what does it provide?" tokens

TODO write about tokens

### Unrolling loops

Although the internal structure allows loops in its graph, Tavor currently unrolles loops for easier usage. This is a trade-off that is currently in place but will be eliminated in future versions of Tavor.

E.g. This graph loops between the states <code>Idle</code> and <code>Action</code>:

![Looping](/doc/images/README/unroll-loop.png "Looping")

Will result in the following internal graph given a maximum of two repetitions:

![Unrolled](/doc/images/README/unroll-unrolled.png "Unrolled")

## <a name="format"></a>The Tavor format file

TODO -> put this in its own .md and do not skimp on examples<br/>
TODO explain every aspect. basics first<br/>

## <a name="use"></a>How do I use Tavor?

Tavor can be used in three different ways:
- [Using the binary](#binary) which makes everything provided officially by the Tavor project available via the command line backed by the [Tavor format file](#format) to create the internal structure.
- [Programmatically](#programmatically) by implementing the internal structure via code using the Tavor framework and doing everything else like fuzzing and delta-debugging too.
- [Programmatically extending Tavor](#extend) because of missing features or strategies.

### <a name="fuzzing-filter"></a>What are fuzzing filters?

Fuzzing filters mutate the internal structure and can be applied after the internal structure is ready for fuzzing thus after creating it e.g. after parsing and unrolling. In contrast to [mutation-based fuzzing](#fuzzing) they do not mutate the output data itself, instead they focus solely on the internal structure which then can be used to generate data.

An example use-case for fuzzing filters is the [boundary-value analysis](https://en.wikipedia.org/wiki/Boundary-value_analysis) software testing technique. Imagine an integer which has valid values from 1 to 100. This would lead to 100 possible values 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 [PositiveBoundaryValueAnalysis fuzzing filter](https://godoc.org/github.com/zimmski/tavor/fuzz/filter#PositiveBoundaryValueAnalysisFilter) does. It traverses the whole internal structure and replaces every range integer with its boundary values.

Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/fuzz/filter) for an overview of all available fuzzing filters of Tavor.

### <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 kinds of token fuzzing. One is to deterministically set one possible permutation of the token the other is choosing randomly one permutation out of all permutations of a token. Strategies can even mix these two kinds or implement their own.

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. It traverses through the whole internal structure and randomly permutes each token.

Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/fuzz/strategy) for an overview of all available fuzzing strategies of Tavor.
<commit_msg>token section<commit_after># Tavor [![GoDoc](https://godoc.org/github.com/zimmski/tavor?status.png)](https://godoc.org/github.com/zimmski/tavor) [![Build Status](https://travis-ci.org/zimmski/tavor.svg?branch=master)](https://travis-ci.org/zimmski/tavor) [![Coverage Status](https://coveralls.io/repos/zimmski/tavor/badge.png)](https://coveralls.io/r/zimmski/tavor)

Tavor ([Sindarin](https://en.wikipedia.org/wiki/Sindarin) for "woodpecker") is a [fuzzing](#fuzzing) and [delta-debugging](#delta-debugging) platform, which provides a framework and binary to not only implement and do everyday fuzzing and delta-debugging but to also do research on new methods without implementing basic algorithms again. A [EBNF-like notations](#format) allows the definition of data (e.g. file formats and protocols) without the need of programming. Tavor also relaxes on the definitions of fuzzing and delta-debugging allowing the user to utilize implemented techniques universally e.g. for key-driven testing, model-based testing, simulating user-behavior and genetic programming.

### <a name="quick-example"></a>A quick example

Imagine a vending machine which ejects a product after receiving 100 worth of credits. It is possible to input 25 and 50 credit coins into the machine. After receiving enough credits the machine ejects a product and resets the credit counter to zero. To keep it simple, we specify that the machine does not handle credit overflows. A representation of the states and actions of the machine could look like this:

![Basic states and actions](examples/quick/basic.png "Basic states and actions")

This state machine can be defined using the following [Tavor format](#format):

```
START = Credit0

Credit0   = "Credit0"   "\n" ( Coin25 Credit25 | Coin50 Credit50 | )
Credit25  = "Credit25"  "\n" ( Coin25 Credit50 | Coin50 Credit75 )
Credit50  = "Credit50"  "\n" ( Coin25 Credit75 | Coin50 Credit100 )
Credit75  = "Credit75"  "\n" Coin25 Credit100
Credit100 = "Credit100" "\n" Vend Credit0

Coin25 = "Coin25" "\n"
Coin50 = "Coin50" "\n"

Vend = "Vend" "\n"
```
(Please note that the new line escape sequences "\n" are just defined to make the output prettier)

You can download this file called [<code>basic.tavor</code> from here](examples/quick/basic.tavor).

Now we can use Tavor to [fuzz](#fuzzing) the format by issuing the following command:

```bash
tavor --format-file basic.tavor fuzz
```

On every call this command outputs random paths through the defined graph. Here are some example outputs:

```
Credit0
```

```
Credit0
Coin50
Credit50
Coin50
Credit100
Vend
Credit0
```

```
Credit0
Coin25
Credit25
Coin50
Credit75
Coin25
Credit100
Vend
Credit0
```

Generating data like this is just one example of the capabilities of Tavor. Please have a look [here](#bigexample) if you like to see a bigger example with a complete overview over the basic features or keep reading to find out more about the background and capabilities of Tavor.

## <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.
> -- <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. Fuzzing is in general 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 two areas:

- **mutation-based**

	Mutation-based fuzzing takes existing data and simply changes it. This often leads to invalid data, as most techniques are not obeying constraints nor rules of the underlying data.

	Some common technique 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**

	Generation-based algorithms have one big advantage over mutation-based in that they have to understand and obey the underlying constraints and rules of the data itself. This property can be used to generate valid as well as invalid data. Another property is that generation-based algorithms 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. The traversal algorithms and the complexity and abilities of the data model like constraints between nodes or adding nodes during the traversal distinguish generation-based fuzzers and contribute 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.
> -- <cite>[https://en.wikipedia.org/wiki/Delta_Debugging](https://en.wikipedia.org/wiki/Delta_Debugging)</cite>

E.g. we feed a given data to a program which fails on executing. By delta-debugging this data we can reduce it to its minimum while still failing the execution. 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 we do not need to handle uninteresting parts of the data while debugging the problem, we can focus on the important parts which actually lead to the failure.

**Note**: Since delta-debugging reduces data it is also called <code>reducing</code>.

Delta-debugging consists of three areas:
- A heuristic has to decide which parts of the data will be reduced next
- The reduction itself e.g.
	- Remove repetitions
	- Remove optional data
	- Replace data with something else e.g. replace an uninteresting complex function with a constant value
- Testing the new resulting data concerning the failure

Although delta-debugging is described as method to isolate failure causes, it can be also used to isolate anything given isolating constraints. For example we could reduce an input for a program which leads to a positive outcome to its minimum.

## How does Tavor work and what does it provide?

Tavor combines both fuzzing and delta-debugging into one platform by allowing all implemented methods to operate on one internal model-based structure represented by a graph. This structure can be defined and generated programmatically or by using a format file. Out of the box Tavor comes with its own [format](#format) which covers all functionality of the Tavor framework itself.

Tavor's generic fuzzing implementation is not fixed to one technique nor format. 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 platform.

Even tough Tavor provides loads of functionality out of the box, a lot is still missing. A list of missing but planed features can be found in the [missing features section](#missing-features). For feature request 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 that they represent not just a group of characters but different kind 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 whole platform and every algorithm for fuzzing, parsing and delta-debugging uses 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 [programming](#programmatically) and [extending](#extend) sections.

### Unrolling loops

Although the internal structure allows loops in its graph, Tavor currently unrolles loops for easier usage. This is a trade-off that is currently in place but will be eliminated in future versions of Tavor.

E.g. This graph loops between the states <code>Idle</code> and <code>Action</code>:

![Looping](/doc/images/README/unroll-loop.png "Looping")

Will result in the following internal graph given a maximum of two repetitions:

![Unrolled](/doc/images/README/unroll-unrolled.png "Unrolled")

## <a name="format"></a>The Tavor format

TODO -> put this in its own .md and do not skimp on examples<br/>
TODO explain every aspect. basics first<br/>

## <a name="use"></a>How do I use Tavor?

Tavor can be used in three different ways:
- [Using the binary](#binary) which makes everything provided officially by the Tavor project available via the command line backed by the [Tavor format](#format) to create the internal structure.
- [Programmatically](#programmatically) by implementing the internal structure via code using the Tavor framework and doing everything else like fuzzing and delta-debugging too.
- [Programmatically extending Tavor](#extend) because of missing features or strategies.

### <a name="fuzzing-filter"></a>What are fuzzing filters?

Fuzzing filters mutate the internal structure and can be applied after the internal structure is ready for fuzzing thus after creating it e.g. after parsing and unrolling. In contrast to [mutation-based fuzzing](#fuzzing) they do not mutate the output data itself, instead they focus solely on the internal structure which then can be used to generate data.

An example use-case for fuzzing filters is the [boundary-value analysis](https://en.wikipedia.org/wiki/Boundary-value_analysis) software testing technique. Imagine an integer which has valid values from 1 to 100. This would lead to 100 possible values 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 [PositiveBoundaryValueAnalysis fuzzing filter](https://godoc.org/github.com/zimmski/tavor/fuzz/filter#PositiveBoundaryValueAnalysisFilter) does. It traverses the whole internal structure and replaces every range integer with its boundary values.

Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/fuzz/filter) for an overview of all available fuzzing filters of Tavor.

### <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 kinds of token fuzzing. One is to deterministically set one possible permutation of the token the other is choosing randomly one permutation out of all permutations of a token. Strategies can even mix these two kinds or implement their own.

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. It traverses through the whole internal structure and randomly permutes each token.

Please have a look at [the documentation](https://godoc.org/github.com/zimmski/tavor/fuzz/strategy) for an overview of all available fuzzing strategies of Tavor.

{'fraction_non_alphanumeric': 0.06521027655048274, 'fraction_numerical': 0.009245622647684503, 'mean_word_length': 4.810553838840028, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 73, 'https://': 32, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3416706', 'n_tokens_mistral': 6481, 'n_tokens_neox': 6056, 'n_words': 3279}