fuzzcheck_traits/
lib.rs

1#![feature(arc_new_cyclic)]
2use std::rc::{Rc, Weak};
3
4/**
5 A [Mutator] is an object capable of mutating a value for the purpose of
6 fuzz-testing.
7
8 For example, a mutator could change the value
9 `v1 = [1, 4, 2, 1]` to `v1' = [1, 5, 2, 1]`.
10 The idea is that if v1 is an “interesting” value to test, then v1' also
11 has a high chance of being “interesting” to test.
12
13 ## Complexity
14
15 A mutator is also responsible for keeping track of the
16 [complexity](crate::Mutator::complexity) of a value. The complexity is,
17 roughly speaking, how large the value is.
18
19 For example, the complexity of a vector is the complexity of its length,
20 plus  the sum of the complexities of its elements. So `vec![]` would have a
21 complexity of `0.0` and `vec![76]` would have a complexity of `9.0`: `1.0`
22 for  its short length and `8.0` for the 8-bit integer “76”. But there is no
23 fixed rule for how to compute the complexity of a value, and it is up to you
24 to judge how “large” something is.
25
26  ## Cache
27
28 In order to mutate values efficiently, the mutator is able to make use of a
29 per-value *cache*. The Cache contains information associated with the value
30 that will make it faster to compute its complexity or apply a mutation to
31 it. For a vector, its cache is its total complexity, along with a vector of
32 the cache of each of its element.
33
34  ## MutationStep
35
36 The same values will be passed to the mutator many times, so that it is
37 mutated in many different ways. There are different strategies to choose
38 what mutation to apply to a value. The first one is to create a list of
39 mutation operations, and choose one to apply randomly from this list.
40
41 However, one may want to have better control over which mutation operation
42 is used. For example, if the value to be mutated is of type `Option<T>`,
43 then you may want to first mutate it to `None`, and then always mutate it
44 to another `Some(t)`. This is where `MutationStep` comes in. The mutation
45 step is a type you define to allow you to keep track of which mutation
46 operation has already been tried. This allows you to deterministically
47 apply mutations to a value such that better mutations are tried first, and
48 duplicate mutations are avoided.
49
50 ## Unmutate
51
52 Finally, it is important to note that values and caches are mutated
53 *in-place*. The fuzzer does not clone them before handing them to the
54 mutator. Therefore, the mutator also needs to know how to reverse each
55 mutation it performed. To do so, each mutation needs to return a token
56 describing how to reverse it. The [unmutate](crate::Mutator::unmutate)
57 method will later be called with that token to get the original value
58 and cache back.
59
60 For example, if the value is `[[1, 3], [5], [9, 8]]`, the mutator may
61 mutate it to `[[1, 3], [5], [9, 1, 8]]` and return the token:
62 `Element(2, Remove(1))`, which means that in order to reverse the
63 mutation, the element at index 2 has to be unmutated by removing
64 its element at index 1. In pseudocode:
65
66 ```ignore
67 value = [[1, 3], [5], [9, 8]];
68 cache: c1 (ommitted from example)
69 step: s1 (ommitted from example)
70
71 let unmutate_token = self.mutate(&mut value, &mut cache, &mut step, max_cplx);
72
73 // value = [[1, 3], [5], [9, 1, 8]]
74 // token = Element(2, Remove(1))
75 // cache = c2
76 // step = s2
77
78 test(&value);
79
80 self.unmutate(&mut value, &mut cache, unmutate_token);
81
82 // value = [[1, 3], [5], [9, 8]]
83 // cache = c1 (back to original cache)
84 // step = s2 (step has not been reversed)
85 ```
86
87**/
88pub trait Mutator<Value: Clone>: Sized {
89    type Cache: Clone;
90    type MutationStep: Clone;
91    type ArbitraryStep: Clone + Default;
92    type UnmutateToken;
93
94    /// Compute the cache for the given value
95    fn cache_from_value(&self, value: &Value) -> Self::Cache;
96    /// Compute the initial mutation step for the given value
97    fn initial_step_from_value(&self, value: &Value) -> Self::MutationStep;
98    /// The maximum complexity of an input of this type
99    fn max_complexity(&self) -> f64;
100    /// The minimum complexity of an input of this type
101    fn min_complexity(&self) -> f64;
102    fn complexity(&self, value: &Value, cache: &Self::Cache) -> f64;
103
104    fn ordered_arbitrary(&self, step: &mut Self::ArbitraryStep, max_cplx: f64) -> Option<(Value, Self::Cache)>;
105    fn random_arbitrary(&self, max_cplx: f64) -> (Value, Self::Cache);
106
107    fn ordered_mutate(
108        &self,
109        value: &mut Value,
110        cache: &mut Self::Cache,
111        step: &mut Self::MutationStep,
112        max_cplx: f64,
113    ) -> Option<Self::UnmutateToken>;
114
115    fn random_mutate(&self, value: &mut Value, cache: &mut Self::Cache, max_cplx: f64) -> Self::UnmutateToken;
116
117    fn unmutate(&self, value: &mut Value, cache: &mut Self::Cache, t: Self::UnmutateToken);
118}
119
120/**
121 * A Serializer is used to encode and decode values into bytes.
122 *
123 * One possible implementation would be to use `serde` to implement
124 * both required functions. But we also want to be able to fuzz-test
125 * types that are not serializable with `serde`, which is why this
126 * Serializer trait exists.
127*/
128pub trait Serializer {
129    type Value;
130    fn is_utf8(&self) -> bool;
131    fn extension(&self) -> &str;
132    fn from_data(&self, data: &[u8]) -> Option<Self::Value>;
133    fn to_data(&self, value: &Self::Value) -> Vec<u8>;
134}
135
136#[derive(Clone)]
137pub enum RecursingArbitraryStep<AS> {
138    Default,
139    Initialized(AS),
140}
141impl<AS> Default for RecursingArbitraryStep<AS> {
142    fn default() -> Self {
143        Self::Default
144    }
145}
146
147pub struct RecursiveMutator<M> {
148    pub mutator: Rc<M>,
149}
150impl<M> RecursiveMutator<M> {
151    pub fn new(data_fn: impl FnOnce(&Weak<M>) -> M) -> Self {
152        Self {
153            mutator: Rc::new_cyclic(data_fn),
154        }
155    }
156}
157
158pub struct RecurToMutator<M> {
159    reference: Weak<M>,
160}
161impl<M> From<&Weak<M>> for RecurToMutator<M> {
162    fn from(reference: &Weak<M>) -> Self {
163        Self {
164            reference: reference.clone(),
165        }
166    }
167}
168
169impl<T, M> Mutator<T> for RecurToMutator<M>
170where
171    M: Mutator<T>,
172    T: Clone,
173{
174    type Cache = <M as Mutator<T>>::Cache;
175    type MutationStep = <M as Mutator<T>>::MutationStep;
176    type ArbitraryStep = RecursingArbitraryStep<<M as Mutator<T>>::ArbitraryStep>;
177    type UnmutateToken = <M as Mutator<T>>::UnmutateToken;
178
179    fn cache_from_value(&self, value: &T) -> Self::Cache {
180        self.reference.upgrade().unwrap().cache_from_value(value)
181    }
182
183    fn initial_step_from_value(&self, value: &T) -> Self::MutationStep {
184        self.reference.upgrade().unwrap().initial_step_from_value(value)
185    }
186
187    fn max_complexity(&self) -> f64 {
188        std::f64::INFINITY
189    }
190
191    fn min_complexity(&self) -> f64 {
192        0.0 // not right, but easy hack for now
193    }
194
195    fn complexity(&self, value: &T, cache: &Self::Cache) -> f64 {
196        self.reference.upgrade().unwrap().complexity(value, cache)
197    }
198
199    fn ordered_arbitrary(&self, step: &mut Self::ArbitraryStep, max_cplx: f64) -> Option<(T, Self::Cache)> {
200        match step {
201            RecursingArbitraryStep::Default => {
202                let mut inner_step = <_>::default();
203                let result = self
204                    .reference
205                    .upgrade()
206                    .unwrap()
207                    .ordered_arbitrary(&mut inner_step, max_cplx);
208                *step = RecursingArbitraryStep::Initialized(inner_step);
209                result
210            }
211            RecursingArbitraryStep::Initialized(inner_step) => self
212                .reference
213                .upgrade()
214                .unwrap()
215                .ordered_arbitrary(inner_step, max_cplx),
216        }
217    }
218
219    fn random_arbitrary(&self, max_cplx: f64) -> (T, Self::Cache) {
220        self.reference.upgrade().unwrap().random_arbitrary(max_cplx)
221    }
222
223    fn ordered_mutate(
224        &self,
225        value: &mut T,
226        cache: &mut Self::Cache,
227        step: &mut Self::MutationStep,
228        max_cplx: f64,
229    ) -> Option<Self::UnmutateToken> {
230        self.reference
231            .upgrade()
232            .unwrap()
233            .ordered_mutate(value, cache, step, max_cplx)
234    }
235
236    fn random_mutate(&self, value: &mut T, cache: &mut Self::Cache, max_cplx: f64) -> Self::UnmutateToken {
237        self.reference.upgrade().unwrap().random_mutate(value, cache, max_cplx)
238    }
239
240    fn unmutate(&self, value: &mut T, cache: &mut Self::Cache, t: Self::UnmutateToken) {
241        self.reference.upgrade().unwrap().unmutate(value, cache, t)
242    }
243}
244
245impl<T, M> Mutator<T> for RecursiveMutator<M>
246where
247    M: Mutator<T>,
248    T: Clone,
249{
250    type Cache = <M as Mutator<T>>::Cache;
251    type MutationStep = <M as Mutator<T>>::MutationStep;
252    type ArbitraryStep = <M as Mutator<T>>::ArbitraryStep;
253    type UnmutateToken = <M as Mutator<T>>::UnmutateToken;
254
255    fn cache_from_value(&self, value: &T) -> Self::Cache {
256        Rc::as_ref(&self.mutator).cache_from_value(value)
257    }
258
259    fn initial_step_from_value(&self, value: &T) -> Self::MutationStep {
260        Rc::as_ref(&self.mutator).initial_step_from_value(value)
261    }
262
263    fn max_complexity(&self) -> f64 {
264        std::f64::INFINITY
265    }
266
267    fn min_complexity(&self) -> f64 {
268        Rc::as_ref(&self.mutator).min_complexity()
269    }
270
271    fn complexity(&self, value: &T, cache: &Self::Cache) -> f64 {
272        Rc::as_ref(&self.mutator).complexity(value, cache)
273    }
274
275    fn ordered_arbitrary(&self, step: &mut Self::ArbitraryStep, max_cplx: f64) -> Option<(T, Self::Cache)> {
276        Rc::as_ref(&self.mutator).ordered_arbitrary(step, max_cplx)
277    }
278
279    fn random_arbitrary(&self, max_cplx: f64) -> (T, Self::Cache) {
280        Rc::as_ref(&self.mutator).random_arbitrary(max_cplx)
281    }
282
283    fn ordered_mutate(
284        &self,
285        value: &mut T,
286        cache: &mut Self::Cache,
287        step: &mut Self::MutationStep,
288        max_cplx: f64,
289    ) -> Option<Self::UnmutateToken> {
290        Rc::as_ref(&self.mutator).ordered_mutate(value, cache, step, max_cplx)
291    }
292
293    fn random_mutate(&self, value: &mut T, cache: &mut Self::Cache, max_cplx: f64) -> Self::UnmutateToken {
294        Rc::as_ref(&self.mutator).random_mutate(value, cache, max_cplx)
295    }
296
297    fn unmutate(&self, value: &mut T, cache: &mut Self::Cache, t: Self::UnmutateToken) {
298        Rc::as_ref(&self.mutator).unmutate(value, cache, t)
299    }
300}
fuzzcheck_traits/lib.rs

fuzzcheck_traits/
lib.rs
