pub trait Mutator<Value: Clone + 'static>: 'static {
type Cache: Clone;
type MutationStep: Clone;
type ArbitraryStep: Clone;
type UnmutateToken;
Show 15 methods
// Required methods
fn initialize(&self);
fn default_arbitrary_step(&self) -> Self::ArbitraryStep;
fn is_valid(&self, value: &Value) -> bool;
fn validate_value(&self, value: &Value) -> Option<Self::Cache>;
fn default_mutation_step(
&self,
value: &Value,
cache: &Self::Cache,
) -> Self::MutationStep;
fn global_search_space_complexity(&self) -> f64;
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,
subvalue_provider: &dyn SubValueProvider,
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 visit_subvalues<'a>(
&self,
value: &'a Value,
cache: &'a Self::Cache,
visit: &mut dyn FnMut(&'a dyn Any, f64),
);
}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.
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):
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
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 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 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, _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 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
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, &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 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.
§SubValueProvider
The method ordered_mutate takes a &dyn 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).
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:
(&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) // trueThe 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:
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.
}
}Required Associated Types§
Sourcetype Cache: Clone
type Cache: Clone
Accompanies each value to help compute its complexity and mutate it efficiently.
Sourcetype MutationStep: Clone
type MutationStep: Clone
Contains information about what mutations have already been tried.
Sourcetype ArbitraryStep: Clone
type ArbitraryStep: Clone
Contains information about what arbitrary values have already been generated.
Sourcetype UnmutateToken
type UnmutateToken
Describes how to reverse a mutation
Required Methods§
Sourcefn initialize(&self)
fn initialize(&self)
Must be called after creating a mutator, to initialise its internal state.
Sourcefn default_arbitrary_step(&self) -> Self::ArbitraryStep
fn default_arbitrary_step(&self) -> Self::ArbitraryStep
The first ArbitraryStep value to be passed to ordered_arbitrary
Sourcefn is_valid(&self, value: &Value) -> bool
fn is_valid(&self, value: &Value) -> bool
Quickly verifies that the value conforms to the mutator’s expectations
Sourcefn validate_value(&self, value: &Value) -> Option<Self::Cache>
fn validate_value(&self, value: &Value) -> Option<Self::Cache>
Verifies that the value conforms to the mutator’s expectations and, if it does,
returns the Cache associated with that value.
Sourcefn default_mutation_step(
&self,
value: &Value,
cache: &Self::Cache,
) -> Self::MutationStep
fn default_mutation_step( &self, value: &Value, cache: &Self::Cache, ) -> Self::MutationStep
Returns the first MutationStep associated with the value
and cache.
Sourcefn global_search_space_complexity(&self) -> f64
fn global_search_space_complexity(&self) -> f64
The log2 of the number of values that can be produced by this mutator, or an approximation of this number (e.g. the number of bits that are needed to identify each possible value).
If the mutator can only produce one value, then the return value should be equal to 0.0
Sourcefn max_complexity(&self) -> f64
fn max_complexity(&self) -> f64
The maximum complexity that a value can possibly have.
Sourcefn min_complexity(&self) -> f64
fn min_complexity(&self) -> f64
The minimum complexity that a value can possibly have.
Sourcefn complexity(&self, value: &Value, cache: &Self::Cache) -> f64
fn complexity(&self, value: &Value, cache: &Self::Cache) -> f64
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.
Sourcefn ordered_arbitrary(
&self,
step: &mut Self::ArbitraryStep,
max_cplx: f64,
) -> Option<(Value, f64)>
fn ordered_arbitrary( &self, step: &mut Self::ArbitraryStep, max_cplx: f64, ) -> Option<(Value, f64)>
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)
Sourcefn random_arbitrary(&self, max_cplx: f64) -> (Value, f64)
fn random_arbitrary(&self, max_cplx: f64) -> (Value, f64)
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)
Sourcefn 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)>
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)>
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.
Sourcefn random_mutate(
&self,
value: &mut Value,
cache: &mut Self::Cache,
max_cplx: f64,
) -> (Self::UnmutateToken, f64)
fn random_mutate( &self, value: &mut Value, cache: &mut Self::Cache, max_cplx: f64, ) -> (Self::UnmutateToken, f64)
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.
Sourcefn unmutate(
&self,
value: &mut Value,
cache: &mut Self::Cache,
t: Self::UnmutateToken,
)
fn unmutate( &self, value: &mut Value, cache: &mut Self::Cache, t: Self::UnmutateToken, )
Undoes a mutation performed on the given value and cache, described by
the given UnmutateToken.
Implementors§
impl Mutator<AST> for ASTMutator
grammar_mutator only.