use Any;
use Display;
use PathBuf;
use FuzzerEvent;
use crate PoolStorageIndex;
use crate SubValueProvider;
/**
A [`Mutator`] is an object capable of generating/mutating a value for the purpose of
fuzz-testing.
For example, a mutator could change the value
`v1 = [1, 4, 2, 1]` to `v1' = [1, 5, 2, 1]`.
The idea is that if `v1` is an “interesting” value to test, then `v1'` also
has a high chance of being “interesting” to test.
Fuzzcheck itself provides a few mutators for `std` types as well as procedural macros
to generate mutators. See the [`mutators`](crate::mutators) module.
## Complexity
A mutator is also responsible for keeping track of the
[complexity](crate::Mutator::complexity) of a value. The complexity is,
roughly speaking, how large the value is.
For example, the complexity of a vector could be the sum of the complexities
of its elements. So `vec![]` would have a complexity of `1.0` (what we chose as
the base complexity of a vector) and `vec![76]` would have a complexity of
`9.0`: `1.0` for the base complexity of the vector itself + `8.0` for the 8-bit
integer “76”. There is no fixed rule for how to compute the complexity of a
value. However, all mutators of a value of type MUST agree on what its
complexity is within a fuzz-test. In other words, if we have the following
mutator for the type `(u8, u8)`:
```ignore
struct MutatorTuple2<M1, M2> where M1: Mutator<u8>, M2: Mutator<u8> {
m1: M1, // responsible for mutating the first element
m2: M2 // responsible for mutating the second element
}
```
then the submutators `M1` and `M2` must always give the same complexity
for all values of type `u8`.
## Global search space complexity
The search space complexity is, roughly, the base-2 logarithm of the number of
possible values that can be produced by the mutator. Note that this is distinct
from the complexity of a value. If we have a mutator for `usize` that can only
produce the values `89` and `65`, then the search space complexity of the
mutator is `1.0` but the complexity of the produced values could be `64.0`. If a
mutator has a search space complexity of `0.0`, then it is only able to
produce a single value.
## [`Cache`](Mutator::Cache)
In order to mutate values efficiently, the mutator is able to make use of a
per-value *cache*. The [`Cache`](Mutator::Cache) contains information associated
with the value that will make it faster to compute its complexity or apply a
mutation to it. For a vector, its cache is its total complexity, along with a
vector of the caches of each of its element.
## [`MutationStep`](Mutator::MutationStep)
The same values will be passed to the mutator many times, so that it is
mutated in many different ways. There are different strategies to choose
what mutation to apply to a value. The first one is to create a list of
mutation operations, and choose one to apply randomly from this list.
However, one may want to have better control over which mutation operation
is used. For example, if the value to be mutated is of type `Option<T>`,
then you may want to first mutate it to `None`, and then always mutate it
to another `Some(t)`. This is where [`MutationStep`](Mutator::MutationStep)
comes in. The mutation step is a type you define to allow you to keep track
of which mutation operation has already been tried. This allows you to
deterministically apply mutations to a value such that better mutations are
tried first, and duplicate mutations are avoided.
It is not always possible to schedule mutations in order. For that reason,
we have two methods: [`random_mutate`](crate::Mutator::random_mutate) executes
a random mutation, and [`ordered_mutate`](crate::Mutator::ordered_mutate) uses
the [`MutationStep`](Mutator::MutationStep) to schedule mutations in order.
The fuzzing engine only ever uses [`ordered_mutate`](crate::Mutator::ordered_mutate)
directly, but the former is sometimes necessary to compose mutators together.
If you don't want to bother with ordered mutations, that is fine. In that
case, only implement [`random_mutate`](crate::Mutator::random_mutate) and call it from
the [`ordered_mutate`](crate::Mutator::ordered_mutate) method.
```ignore
fn random_mutate(&self, value: &mut Value, cache: &mut Self::Cache, max_cplx: f64) -> (Self::UnmutateToken, f64) {
// ...
}
fn ordered_mutate(&self, value: &mut Value, cache: &mut Self::Cache, step: &mut Self::MutationStep, _subvalue_provider: &dyn SubValueProvider, max_cplx: f64) -> Option<(Self::UnmutateToken, f64)> {
Some(self.random_mutate(value, cache, max_cplx))
}
```
## Arbitrary
A mutator must also be able to generate new values from nothing. This is what
the [`random_arbitrary`](crate::Mutator::random_arbitrary) and
[`ordered_arbitrary`](crate::Mutator::ordered_arbitrary) methods are for. The
latter one is called by the fuzzer directly and uses an
[`ArbitraryStep`](Mutator::ArbitraryStep) that can be used to smartly generate
more interesting values first and avoid duplicates.
## Unmutate
It is important to note that values and caches are mutated
*in-place*. The fuzzer does not clone them before handing them to the
mutator. Therefore, the mutator also needs to know how to reverse each
mutation it performed. To do so, each mutation needs to return a token
describing how to reverse it. The [unmutate](crate::Mutator::unmutate)
method will later be called with that token to get the original value
and cache back.
For example, if the value is `[[1, 3], [5], [9, 8]]`, the mutator may
mutate it to `[[1, 3], [5], [9, 1, 8]]` and return the token:
`Element(2, Remove(1))`, which means that in order to reverse the
mutation, the element at index 2 has to be unmutated by removing
its element at index 1. In pseudocode:
```
use fuzzcheck::Mutator;
# use fuzzcheck::subvalue_provider::EmptySubValueProvider;
# use fuzzcheck::DefaultMutator;
# let m = bool::default_mutator();
# let mut value = false;
# let mut cache = m.validate_value(&value).unwrap();
# let mut step = m.default_mutation_step(&value, &cache);
# let max_cplx = 8.0;
# fn test(x: &bool) {}
// value = [[1, 3], [5], [9, 8]];
// cache: c1 (ommitted from example)
// step: s1 (ommitted from example)
let (unmutate_token, _cplx) = m.ordered_mutate(&mut value, &mut cache, &mut step, &EmptySubValueProvider, max_cplx).unwrap();
// value = [[1, 3], [5], [9, 1, 8]]
// token = Element(2, Remove(1))
// cache = c2
// step = s2
test(&value);
m.unmutate(&mut value, &mut cache, unmutate_token);
// value = [[1, 3], [5], [9, 8]]
// cache = c1 (back to original cache)
// step = s2 (step has not been reversed)
```
When a mutated value is deemed interesting by the fuzzing engine, the method
[`validate_value`](crate::Mutator::validate_value) is called on it in order to
get a new Cache and MutationStep for it. The same method is called when the
fuzzer reads values from a corpus to verify that they conform to the
mutator’s expectations. For example, a [`CharWithinRangeMutator`](crate::mutators::char::CharWithinRangeMutator)
will check whether the character is within a certain range.
Note that in most cases, it is completely fine to never mutate a value’s cache,
since it is recomputed by [`validate_value`](crate::Mutator::validate_value) when
needed.
## SubValueProvider
The method `ordered_mutate` takes a [`&dyn SubValueProvider`](crate::SubValueProvider)
as argument. The purpose of a sub-value provider is to provide the mutator with
subvalues taken from the fuzzing corpus. If you are familiar with fuzzing
terminology, then think of the sub-value provider as the structure-aware replacement
for the “crossover” mutation and the dictionary. Here is how it works:
For each value in the fuzzing corpus, the mutator iterates over each subpart of the
value by calling [`self.visit_subvalues(value, cache, visit_closure)`](Mutator::visit_subvalues).
For example, for the value
```
struct S {
a: usize,
b: Option<bool>,
c: (Option<bool>, usize)
}
let x = S {
a: 887236,
b: None,
c: (Some(true), 10372)
};
```
the `visit_subvalues` method will call the `visit` closure with each subvalue
and its complexity. For the value `x` above, it will be called with the
following arguments:
```ignore
(&x.a , 64.0) // 887236
(&x.b , 1.0) // None
(&x.c , 66.0) // (Some(true), 10372)
(&x.c.0 , 2.0) // Some(true)
(&x.c.1 , 64.0) // 10372
(&x.c.0.unwrap(), 1.0) // true
```
The fuzzer builds a data structure keeping track of these subvalues and pass it
to the mutator as a `&dyn SubValueProvider`. The mutator could then use it as
follows:
```ignore
fn ordered_mutate(&self, value: &mut S, cache: &mut Self::Cache, step: &mut Self::Step, subvalue_provider: &dyn SubValueProvider, max_cplx: f64) -> Option<(Self::UnmutateToken, f64)>
{
// let's say we want to replace the value x.c.1 with something taken from the subvalue provider
if let Some((new_xc1, new_xc1_cplx)) = subvalue_provider.get_subvalue(TypeId::of::<usize>(), &mut idx, max_xc1_cplx) {
let new_xc1 = new_xc1.downcast_ref::<usize>().unwrap().clone(); // guaranteed to succeed
value.x.c.1 = new_xc1;
// etc.
}
}
```
**/
/// A [Serializer] is used to encode and decode test cases into bytes.
///
/// It is used to transfer test cases between the corpus on the file system and the fuzzer’s storage.
/// A [CorpusDelta] describes how to reflect a change in the pool’s content to the corpus on the file system.
///
/// It is used as the return type to [`pool.process(..)`](CompatibleWithObservations::process) where a test case along
/// with its associated sensor observations is given to the pool. Thus, it is always implicitly associated with
/// a specific pool and test case.
/**
A [Sensor] records information when running the test function, which the
fuzzer can use to determine the importance of a test case.
For example, the sensor can record the code coverage triggered by the test case,
store the source location of a panic, measure the number of allocations made, etc.
The observations made by a sensor are then assessed by a [Pool], which must be
explicitly [compatible](CompatibleWithObservations) with the sensor’s observations.
*/
/// A trait implemented by the [statistics of a pool](crate::Pool::Stats)
///
/// The types implementing `Stats` must be displayable in the terminal and must be
/// [convertible to CSV fields](crate::ToCSV). However, note that at the moment some pools
/// choose to produce empty CSV values for their statistics. Consequently, their statistics
/// will not be available in the `fuzz/stats/<id>/events.csv` file written by fuzzcheck
/// at the end of a fuzz test.
///
/// Some pools may choose not to display their statistics in the terminal.
/// An object safe trait that combines the methods of the [`Sensor`], [`Pool`], and [`CompatibleWithObservations`] traits.
///
/// While it's often useful to work with the [`Sensor`] and [`Pool`] traits separately, the
/// fuzzer doesn't actually need to know about the sensor and pool individually. By having
/// this `SensorAndPool` trait, we can give the fuzzer a `Box<dyn SensorAndPool>` and get rid of
/// two generic type parameters: `S: Sensor` and `P: Pool + CompatibleWithObservations<S::Observations>`.
///
/// This is better for compile times and simplifies the implementation of the fuzzer. Users of
/// `fuzzcheck` should feel free to ignore this trait, as it is arguably more an implementation detail
/// than a fundamental building block of the fuzzer.
///
/// Currently, there are two types implementing `SensorAndPool`:
/// 1. `(S, P)` where `S: Sensor` and `P: Pool + CompatibleWithObservations<S::Observations>`
/// 2. [`AndSensorAndPool`](crate::sensors_and_pools::AndSensorAndPool)
/**
Describes how to save a list of this value as a CSV file.
It is done via two methods:
1. [self.csv_headers\()](ToCSV::csv_headers) gives the first row of the file, as a list of [CSVField].
For example, it can be `time, score`.
2. [self.to_csv_record\()](ToCSV::to_csv_record) serializes the value as a CSV row. For example, it
can be `16:07:32, 34.0`.
Note that each call to [self.to_csv_record\()](ToCSV::to_csv_record) must return a list of [CSVField]
where the field at index `i` corresponds to the header at index `i` given by [self.csv_headers()](ToCSV::csv_headers).
Otherwise, the CSV file will be invalid.
*/
/**
A [`Pool`] ranks test cases based on observations recorded by a sensor.
The pool trait is divided into two parts:
1. [`Pool`] contains general methods that are independent of the sensor used
2. [`CompatibleWithObservations<O>`] is a subtrait of [`Pool`]. It describes how the pool handles
observations made by the [`Sensor`].
*/
/**
A subtrait of [Pool] describing how the pool handles observations made by a sensor.
This trait is separate from [Pool] because a single pool type may handle multiple different kinds of sensors.
It is responsible for judging whether the observations are interesting, and then adding the test case to the pool
if they are. It communicates to the rest of the fuzzer what test cases were added or removed from the pool via the
[`CorpusDelta`] type. This ensures that the right message can be printed to the terminal and that the corpus on the
file system, which reflects the content of the pool, can be properly updated.
*/
/// A trait for types that want to save their content to the `stats` folder which is created after a fuzzing run.