puffin/fuzzer/term_zoo.rs
1//! Generates a zoo of terms form a [`Signature`]. For each function symbol in the signature
2//! a closed term is generated and added to the zoo.
3
4use libafl_bolts::rands::Rand;
5
6use crate::algebra::atoms::Function;
7use crate::algebra::signature::{FunctionDefinition, Signature};
8use crate::algebra::{DYTerm, Term, TermType};
9use crate::fuzzer::utils::Choosable;
10use crate::protocol::ProtocolBehavior;
11use crate::trace::TraceContext;
12
13/// Defaults for the zoo budgets of [`ProtocolBehavior`], which every protocol may override. The
14/// values are the ones tuned for tlspuffin, whose impl documents where they come from.
15///
16/// [`DEFAULT_MAX_DEPTH`] bounds which symbols the zoo can build a term for at all: a term must
17/// reach a closed leaf within that many levels, and the wrapper chains of a generated signature
18/// eat several of them. Too low, and whole families of symbols silently become ungeneratable.
19///
20/// [`DEFAULT_MAX_SIZE`] is what actually keeps terms small — the size grows exponentially with the
21/// depth — which lets the depth budget be about reachability alone.
22///
23/// [`DEFAULT_MAX_TRIES`] is how many consecutive failures we accept for one symbol. With
24/// `filter_evaluated` it is really a budget of *evaluations*, since building a term essentially
25/// always succeeds, so it is driven by the cost of the slowest symbols to evaluate.
26pub const DEFAULT_MAX_DEPTH: u16 = 14;
27/// See [`DEFAULT_MAX_DEPTH`].
28pub const DEFAULT_MAX_SIZE: usize = 64;
29/// See [`DEFAULT_MAX_DEPTH`].
30pub const DEFAULT_MAX_TRIES: usize = 140_000;
31
32pub struct TermZoo<PB: ProtocolBehavior> {
33 terms: Vec<Term<PB::ProtocolTypes>>,
34}
35
36impl<PB: ProtocolBehavior> TermZoo<PB> {
37 pub fn generate<R: Rand>(
38 ctx: &TraceContext<PB>,
39 signature: &Signature<PB::ProtocolTypes>,
40 rand: &mut R,
41 how_many: usize,
42 max_depth: Option<u16>,
43 ) -> Self {
44 Self::generate_many(ctx, signature, rand, how_many, max_depth, None, true, true)
45 }
46
47 #[allow(clippy::too_many_arguments)]
48 pub fn generate_many<R: Rand>(
49 ctx: &TraceContext<PB>,
50 signature: &Signature<PB::ProtocolTypes>,
51 rand: &mut R,
52 how_many: usize, // how many terms to generate
53 max_depth: Option<u16>, // how deep the terms may be, `None` for `PB::ZOO_MAX_DEPTH`
54 filter: Option<&FunctionDefinition<PB::ProtocolTypes>>,
55 filter_evaluated: bool,
56 filter_no_gen: bool,
57 ) -> Self {
58 let max_depth = max_depth.unwrap_or(PB::ZOO_MAX_DEPTH);
59 let skip = |def: &FunctionDefinition<PB::ProtocolTypes>| {
60 let skip = filter_no_gen && signature.attrs_by_name.get(def.0.name).unwrap().no_gen;
61 if skip {
62 log::debug!("Skipping generation for [{:?}]", def.0.name);
63 }
64 skip
65 };
66
67 let mut acc = vec![];
68 if let Some(def) = filter {
69 // Also skipped when asked for one symbol at a time: a `no_gen` symbol would otherwise
70 // spend the whole `PB::ZOO_MAX_TRIES` budget evaluating terms that cannot evaluate.
71 if !skip(def) {
72 Self::generate_for(
73 &mut acc,
74 ctx,
75 signature,
76 rand,
77 def,
78 how_many,
79 max_depth,
80 filter_evaluated,
81 );
82 }
83 } else {
84 for def in &signature.functions {
85 if skip(def) {
86 continue; // Skip this function symbol
87 }
88 Self::generate_for(
89 &mut acc,
90 ctx,
91 signature,
92 rand,
93 def,
94 how_many,
95 max_depth,
96 filter_evaluated,
97 );
98 }
99 }
100
101 Self { terms: acc }
102 }
103
104 /// Appends up to `how_many` terms rooted at `def` to `acc`, giving up on that symbol after
105 /// [`ProtocolBehavior::ZOO_MAX_TRIES`] consecutive failures.
106 #[allow(clippy::too_many_arguments)]
107 fn generate_for<R: Rand>(
108 acc: &mut Vec<Term<PB::ProtocolTypes>>,
109 ctx: &TraceContext<PB>,
110 signature: &Signature<PB::ProtocolTypes>,
111 rand: &mut R,
112 def: &FunctionDefinition<PB::ProtocolTypes>,
113 how_many: usize,
114 max_depth: u16,
115 filter_evaluated: bool,
116 ) {
117 let mut counter = PB::ZOO_MAX_TRIES;
118 let mut many = 0;
119
120 while counter > 0 && many < how_many {
121 counter -= 1;
122
123 if let Some(term) =
124 Self::generate_term(signature, def, max_depth, PB::ZOO_MAX_SIZE, rand)
125 {
126 // If filter_evaluated, we must check the term can be evaluated before including it
127 if !filter_evaluated || term.evaluate(ctx).is_ok() {
128 many += 1;
129 counter = PB::ZOO_MAX_TRIES;
130 acc.push(term);
131 }
132 }
133 }
134 }
135
136 /// Builds a random closed term rooted at the given symbol, using at most `depth` levels and
137 /// `max_size` nodes.
138 ///
139 /// The children are drawn among the symbols that still fit both budgets, so an attempt is
140 /// essentially never abandoned half-way — the exception being that the reservation made for
141 /// the remaining arguments is a lower bound (see [`Signature::min_gen_size_of_type`]) which a
142 /// symbol may fail to meet at the depth left, in which case this returns `None` and the caller
143 /// retries.
144 ///
145 /// The size budget is what a depth budget alone cannot do: keeping the choice of children
146 /// unrestricted otherwise, so that the deep argument chains some symbols need (a `ClientHello`
147 /// for `fn_fill_binder`, say) stay as reachable as they are without any budget at all.
148 fn generate_term<R: Rand>(
149 signature: &Signature<PB::ProtocolTypes>,
150 (shape, dynamic_fn): &FunctionDefinition<PB::ProtocolTypes>,
151 depth: u16,
152 max_size: usize,
153 rand: &mut R,
154 ) -> Option<Term<PB::ProtocolTypes>> {
155 // Rejecting a doomed symbol here, before building anything, is what keeps the recursion
156 // below from wasting attempts: `depth` is at least the budget this symbol needs.
157 if signature.min_gen_depth(shape.name)? > depth
158 || signature.min_gen_size(shape.name)? > max_size
159 {
160 return None;
161 }
162
163 let required_types = &shape.argument_types;
164
165 let mut subterms = Vec::with_capacity(required_types.len());
166
167 // A symbol with arguments needs a depth of at least 2, and the check above guarantees
168 // `depth` covers it, so there is a level left for the children.
169 let budget = depth - 1;
170 // What we must keep aside for the arguments we have not built yet, so that a greedy first
171 // argument cannot eat the whole budget.
172 let mut reserved: usize = required_types
173 .iter()
174 .map(|typ| signature.min_gen_size_of_type(typ))
175 .sum::<Option<usize>>()?;
176 let mut size_left = max_size - 1; // this node
177
178 for typ in required_types {
179 reserved -= signature.min_gen_size_of_type(typ)?;
180 let child_max_size = size_left - reserved;
181
182 // Only symbols that can reach a closed leaf within both budgets are considered.
183 // Restricting the choice rather than recursing and failing keeps an attempt alive
184 // instead of throwing away the whole term (and with it one of the `PB::ZOO_MAX_TRIES`
185 // attempts); with a depth budget of 1 it leaves exactly the constants.
186 let possibility =
187 signature.choose_function_within(typ, budget, child_max_size, rand)?;
188 let subterm =
189 Self::generate_term(signature, possibility, budget, child_max_size, rand)?;
190
191 size_left -= subterm.size();
192 subterms.push(subterm);
193 }
194
195 Some(Term::from(DYTerm::Application(
196 Function::new(shape.clone(), dynamic_fn.clone()),
197 subterms,
198 )))
199 }
200
201 pub fn choose_filtered<P, R: Rand>(
202 &self,
203 filter: P,
204 rand: &mut R,
205 ) -> Option<&Term<PB::ProtocolTypes>>
206 where
207 P: FnMut(&&Term<PB::ProtocolTypes>) -> bool,
208 {
209 self.terms.choose_filtered(filter, rand)
210 }
211
212 #[must_use]
213 pub fn terms(&self) -> &[Term<PB::ProtocolTypes>] {
214 &self.terms
215 }
216}