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}