1 //! Generating sequences of Wasmtime API calls.
2 //!
3 //! We only generate *valid* sequences of API calls. To do this, we keep track
4 //! of what objects we've already created in earlier API calls via the `Scope`
5 //! struct.
6 //!
7 //! To generate even-more-pathological sequences of API calls, we use [swarm
8 //! testing]:
9 //!
10 //! > In swarm testing, the usual practice of potentially including all features
11 //! > in every test case is abandoned. Rather, a large “swarm” of randomly
12 //! > generated configurations, each of which omits some features, is used, with
13 //! > configurations receiving equal resources.
14 //!
15 //! [swarm testing]: https://www.cs.utah.edu/~regehr/papers/swarm12.pdf
16 
17 use arbitrary::{Arbitrary, Unstructured};
18 use std::collections::BTreeSet;
19 
20 #[derive(Arbitrary, Debug)]
21 struct Swarm {
22     config_debug_info: bool,
23     config_interruptable: bool,
24     module_new: bool,
25     module_drop: bool,
26     instance_new: bool,
27     instance_drop: bool,
28     call_exported_func: bool,
29 }
30 
31 /// A call to one of Wasmtime's public APIs.
32 #[derive(Arbitrary, Debug)]
33 #[allow(missing_docs)]
34 pub enum ApiCall {
35     ConfigNew,
36     ConfigDebugInfo(bool),
37     ConfigInterruptable(bool),
38     EngineNew,
39     StoreNew,
40     ModuleNew {
41         id: usize,
42         wasm: super::GeneratedModule,
43     },
44     ModuleDrop {
45         id: usize,
46     },
47     InstanceNew {
48         id: usize,
49         module: usize,
50     },
51     InstanceDrop {
52         id: usize,
53     },
54     CallExportedFunc {
55         instance: usize,
56         nth: usize,
57     },
58 }
59 use ApiCall::*;
60 
61 #[derive(Default)]
62 struct Scope {
63     id_counter: usize,
64     modules: BTreeSet<usize>,
65     instances: BTreeSet<usize>,
66 }
67 
68 impl Scope {
69     fn next_id(&mut self) -> usize {
70         let id = self.id_counter;
71         self.id_counter = id + 1;
72         id
73     }
74 }
75 
76 /// A sequence of API calls.
77 #[derive(Debug)]
78 pub struct ApiCalls {
79     /// The API calls.
80     pub calls: Vec<ApiCall>,
81 }
82 
83 impl<'a> Arbitrary<'a> for ApiCalls {
84     fn arbitrary(input: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
85         crate::init_fuzzing();
86 
87         let swarm = Swarm::arbitrary(input)?;
88         let mut calls = vec![];
89 
90         arbitrary_config(input, &swarm, &mut calls)?;
91         calls.push(EngineNew);
92         calls.push(StoreNew);
93 
94         let mut scope = Scope::default();
95 
96         // Total limit on number of API calls we'll generate. This exists to
97         // avoid libFuzzer timeouts.
98         let max_calls = 100;
99 
100         for _ in 0..input.arbitrary_len::<ApiCall>()? {
101             if calls.len() > max_calls {
102                 break;
103             }
104 
105             let mut choices: Vec<fn(_, &mut Scope) -> arbitrary::Result<ApiCall>> = vec![];
106 
107             if swarm.module_new {
108                 choices.push(|input, scope| {
109                     let id = scope.next_id();
110                     let mut wasm = super::GeneratedModule::arbitrary(input)?;
111                     wasm.ensure_termination(1000);
112                     scope.modules.insert(id);
113                     Ok(ModuleNew { id, wasm })
114                 });
115             }
116             if swarm.module_drop && !scope.modules.is_empty() {
117                 choices.push(|input, scope| {
118                     let modules: Vec<_> = scope.modules.iter().collect();
119                     let id = **input.choose(&modules)?;
120                     scope.modules.remove(&id);
121                     Ok(ModuleDrop { id })
122                 });
123             }
124             if swarm.instance_new && !scope.modules.is_empty() {
125                 choices.push(|input, scope| {
126                     let modules: Vec<_> = scope.modules.iter().collect();
127                     let module = **input.choose(&modules)?;
128                     let id = scope.next_id();
129                     scope.instances.insert(id);
130                     Ok(InstanceNew { id, module })
131                 });
132             }
133             if swarm.instance_drop && !scope.instances.is_empty() {
134                 choices.push(|input, scope| {
135                     let instances: Vec<_> = scope.instances.iter().collect();
136                     let id = **input.choose(&instances)?;
137                     scope.instances.remove(&id);
138                     Ok(InstanceDrop { id })
139                 });
140             }
141             if swarm.call_exported_func && !scope.instances.is_empty() {
142                 choices.push(|input, scope| {
143                     let instances: Vec<_> = scope.instances.iter().collect();
144                     let instance = **input.choose(&instances)?;
145                     let nth = usize::arbitrary(input)?;
146                     Ok(CallExportedFunc { instance, nth })
147                 });
148             }
149 
150             if choices.is_empty() {
151                 break;
152             }
153             let c = input.choose(&choices)?;
154             calls.push(c(input, &mut scope)?);
155         }
156 
157         Ok(ApiCalls { calls })
158     }
159 
160     fn size_hint(depth: usize) -> (usize, Option<usize>) {
161         arbitrary::size_hint::recursion_guard(depth, |depth| {
162             arbitrary::size_hint::or(
163                 // This is the stuff we unconditionally need, which affects the
164                 // minimum size.
165                 arbitrary::size_hint::and(
166                     <Swarm as Arbitrary>::size_hint(depth),
167                     // `arbitrary_config` uses four bools:
168                     // 2 when `swarm.config_debug_info` is true
169                     // 2 when `swarm.config_interruptable` is true
170                     <(bool, bool, bool, bool) as Arbitrary>::size_hint(depth),
171                 ),
172                 // We can generate arbitrary `WasmOptTtf` instances, which have
173                 // no upper bound on the number of bytes they consume. This sets
174                 // the upper bound to `None`.
175                 <super::GeneratedModule as Arbitrary>::size_hint(depth),
176             )
177         })
178     }
179 }
180 
181 fn arbitrary_config(
182     input: &mut Unstructured,
183     swarm: &Swarm,
184     calls: &mut Vec<ApiCall>,
185 ) -> arbitrary::Result<()> {
186     calls.push(ConfigNew);
187 
188     if swarm.config_debug_info && bool::arbitrary(input)? {
189         calls.push(ConfigDebugInfo(bool::arbitrary(input)?));
190     }
191 
192     if swarm.config_interruptable && bool::arbitrary(input)? {
193         calls.push(ConfigInterruptable(bool::arbitrary(input)?));
194     }
195 
196     // TODO: flags, features, and compilation strategy.
197 
198     Ok(())
199 }
200