Trait fuzzcheck::Mutator[−][src]

pub trait Mutator<Value: Clone>: 'static {
    type Cache: Clone;
    type MutationStep: Clone;
    type ArbitraryStep: Clone;
    type UnmutateToken;
    type RecursingPartIndex: Clone;
    fn default_arbitrary_step(&self) -> Self::ArbitraryStep;

    fn validate_value(
        &self, 
        value: &Value
    ) -> Option<(Self::Cache, Self::MutationStep)>;

    fn max_complexity(&self) -> f64;

    fn min_complexity(&self) -> f64;

    fn complexity(&self, value: &Value, cache: &Self::Cache) -> f64;

    fn ordered_arbitrary(
        &self, 
        step: &mut Self::ArbitraryStep, 
        max_cplx: f64
    ) -> Option<(Value, f64)>;

    fn random_arbitrary(&self, max_cplx: f64) -> (Value, f64);

    fn ordered_mutate(
        &self, 
        value: &mut Value, 
        cache: &mut Self::Cache, 
        step: &mut Self::MutationStep, 
        max_cplx: f64
    ) -> Option<(Self::UnmutateToken, f64)>;

    fn random_mutate(
        &self, 
        value: &mut Value, 
        cache: &mut Self::Cache, 
        max_cplx: f64
    ) -> (Self::UnmutateToken, f64);

    fn unmutate(
        &self, 
        value: &mut Value, 
        cache: &mut Self::Cache, 
        t: Self::UnmutateToken
    );

    fn default_recursing_part_index(
        &self, 
        value: &Value, 
        cache: &Self::Cache
    ) -> Self::RecursingPartIndex;

    fn recursing_part<'a, T, M>(
        &self, 
        parent: &M, 
        value: &'a Value, 
        index: &mut Self::RecursingPartIndex
    ) -> Option<&'a T>
    where
        T: Clone + 'static,
        M: Mutator<T>;
}
Expand description

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 module.

Complexity

A mutator is also responsible for keeping track of the complexity of a value. The complexity is, roughly speaking, how large the value is.

If the complexity is 0.0, then it means the mutator can only produce one value.

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”. But there is no fixed rule for how to compute the complexity of a value, and it is up to you to judge how “large” something is.

Cache

In order to mutate values efficiently, the mutator is able to make use of a per-value cache. The 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

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 comes in. The mutationstep 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 executes a random mutation, and ordered_mutate uses the MutationStep to schedule mutations in order. The fuzzing engine only ever uses 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 and call it from the ordered_mutate method.

ⓘ
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, 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 and ordered_arbitrary methods are for. The latter one is called by the fuzzer directly and uses an ArbitraryStep that can be used to smartly generate more interesting values first and avoid duplicates.

Unmutate

Finally, 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 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;

//  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, 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 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 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 when needed.

Associated Types

Accompanies each value to help compute its complexity and mutate it efficiently.

Contains information about what mutations have already been tried.

Contains information about what arbitrary values have already been generated.

Describes how to reverse a mutation

Required methods

The first ArbitraryStep value to be passed to ordered_arbitrary

Verifies that the value conforms to the mutator’s expectations and, if it does, returns the Cache and first MutationStep associated with that value.

The maximum complexity that a value can possibly have.

If the maximum complexity is 0, it means that the mutator can only produce one value.

The minimum complexity that a value can possibly have.

If the minimum complexity is 0, then the maximum complexity must also be 0. It means that the mutator can only produce one value.

Computes the complexity of the value.

The returned value must be greater or equal than 0. It is only allowed to return 0 if the mutator cannot produce any other value than the one given as argument.

Generates an entirely new value based on the given ArbitraryStep.

The generated value should be smaller than the given max_cplx.

The return value is None if no more new value can be generated or if it is not possible to stay within the given complexity. Otherwise, it is the value itself and its complexity, which should be equal to self.complexity(value, cache)

Generates an entirely new value.

The generated value should be smaller than the given max_cplx. However, if that is not possible, then it should return a value of the lowest possible complexity.

Returns the value itself and its complexity, which must be equal to self.complexity(value, cache)

Mutates a value (and optionally its cache) based on the given MutationStep.

The mutated value should be within the given max_cplx.

Returns None if it no longer possible to mutate the value to a new state, or if it is not possible to keep it under max_cplx. Otherwise, return the UnmutateToken that describes how to undo the mutation, as well as the new complexity of the value.

Mutates a value (and optionally its cache).

The mutated value should be within the given max_cplx. But if that is not possible, then it should mutate the value so that it has a minimal complexity.

Returns the UnmutateToken that describes how to undo the mutation as well as the new complexity of the value.

Undoes a mutation performed on the given value and cache, described by the given UnmutateToken.

Implementors