puffin/fuzzer/
utils.rs

1use std::cell::Cell;
2
3use libafl_bolts::rands::Rand;
4
5use crate::algebra::{DYTerm, Term, TermType};
6use crate::protocol::ProtocolTypes;
7use crate::trace::{Action, Step, Trace};
8
9thread_local! {
10    /// Per-stage anchor step lock. When set to `Some(k)`, every anchor drawn by
11    /// [`reservoir_sample`] -- and therefore all `choose*` helpers built on it -- is restricted to
12    /// step `k`. Set by [`crate::fuzzer::stages::StepLockedStackMutator`] so that all mutations
13    /// stacked in one mutational stage edit the SAME step. Global/Step *fan-out* (via
14    /// `find_all_term_filtered` / `find_all_sub_term_filtered`) does NOT consult this lock, so a
15    /// Global mutation still spreads its effect across the whole trace -- only its anchor choice is
16    /// confined to the locked step. Safe as a thread-local: LibAFL runs a single mutation thread
17    /// per fuzzer process (one process per core), so there is no cross-trace interference.
18    static STEP_LOCK: Cell<Option<StepIndex>> = const { Cell::new(None) };
19}
20
21/// Set (or clear, with `None`) the process-local anchor step lock. Returns the previous value so
22/// the caller can restore it after the stage.
23pub fn set_step_lock(step: Option<StepIndex>) -> Option<StepIndex> {
24    STEP_LOCK.with(|c| c.replace(step))
25}
26
27/// Read the current anchor step lock (`None` when unlocked).
28pub fn step_lock() -> Option<StepIndex> {
29    STEP_LOCK.with(Cell::get)
30}
31
32/// Size budget for terms and traces during mutation.
33///
34/// # Units
35///
36/// All `*_size` values below are **node counts** in the term tree (`Term::size()`): every
37/// application/variable counts 1, summed over the whole (symbolic) tree; `Trace::size()` sums each
38/// input step's recipe size and additionally counts every output action as one node. They are NOT
39/// bytes.
40///
41/// # How the caps relate
42///
43/// - `min_term_size` / `max_term_size`: bounds on a *sub-term selected* as a mutation candidate.
44/// - `max_result_term_size`: **hard post-condition on the *result* of a replacement mutation** — a
45///   mutation that would push any single step recipe over `max_result_term_size` is rejected
46///   (reject-whole). Whole-trace growth is bounded instead by the number of steps
47///   (`MutationConfig::max_result_trace_length`) times this per-step cap. It is enforced
48///   *incrementally* on top of an already-bounded input (seeds within caps + reject-whole preserve
49///   the invariant), so set them at or above the largest seed: a cap configured *below* an existing
50///   seed's size is a corpus-boundary misconfiguration and cannot be enforced retroactively by the
51///   mutators (see the precondition on `replacement_within_caps`).
52///
53/// # Maintenance rules — READ THIS BEFORE ADDING A PROTOCOL OR EXTENDING A MAPPER
54///
55/// These numbers are chosen from the sizes of the hand-written seeds/attacks. When you add a
56/// protocol, add seeds, or grow the signature (mapper), **re-measure the seeds and re-check the
57/// rules below**. As of this writing the largest seed values are:
58///
59/// | metric                         | TLS  | OPC UA | SSH  | rule for the cap                            |
60/// |--------------------------------|------|--------|------|---------------------------------------------|
61/// | max single-step recipe (nodes) | 324  | 137    | 285  | `max_term_size >= 2 * max_seed_term`        |
62/// | max #steps                     | 13   | 10     | 10   | `max_result_trace_length >= max_seed_steps + 2` |
63///
64/// The current values sit **well above** these minima on purpose, to leave headroom for future
65/// growth of the mappers (larger signatures / seed terms / longer attacks) without another cap
66/// bump:
67/// - `max_term_size` MUST be at least `2 * (largest single-term size across all seeds)` so seeds
68///   (and moderately grown variants) stay selectable. Largest today = 324 (TLS) ⇒ rule wants ≥648;
69///   set to 800.
70/// - whole-trace growth is bounded by `MutationConfig::max_result_trace_length` (max #steps) times
71///   the per-step `max_result_term_size` cap, so there is no separate whole-trace node cap.
72///   `max_result_trace_length` is set to 20 (largest seed today = 13 steps, rule wants ≥15).
73/// - `max_result_term_size` (whole step recipe after a replacement) is kept >= `max_term_size` so a
74///   max-size replacement sub-term still fits; set to 1000.
75#[derive(Copy, Clone, Debug)]
76pub struct TermConstraints {
77    /// Minimum size of a sub-term selected as a mutation candidate.
78    pub min_term_size: usize,
79    /// Maximum size of a sub-term selected as a mutation candidate. Rule: `>= 2 * max_seed_term`
80    /// (largest single-term size across all seeds). Measured max seed term = 324 (TLS).
81    pub max_term_size: usize,
82    /// Hard post-condition: reject a replacement whose *result* makes any single step recipe
83    /// exceed this many nodes. Rule: `> max_seed_term` with headroom (measured max = 324).
84    pub max_result_term_size: usize,
85    pub must_be_symbolic: bool,
86    /// when true: only look for terms with no payload in sub-terms
87    pub no_payload_in_subterm: bool,
88    // when true: only look for terms with at least one payload in sub-terms
89    pub must_payload_in_subterm: bool,
90    /// when true: we do not choose terms that have a list symbol and whose parent also has a list
91    /// symbol those terms are thus "inside a list", like t in fn_append(t,t3) for t =
92    /// fn(append(t1,t2)
93    pub not_inside_list: bool,
94    /// choose term giving higher probability to deeper term
95    pub weighted_depth: bool,
96    /// only select root terms
97    pub must_be_root: bool,
98    /// when true: only look for readable terms
99    pub not_readable: bool,
100    /// Forbids sub-terms with no det function symbols
101    pub must_be_det: bool,
102    /// Number of terms to generate for each type
103    pub zoo_gen_how_many: usize,
104    /// Max depth of the terms generated for the zoo, `None` to use the protocol's
105    /// [`crate::protocol::ProtocolBehavior::ZOO_MAX_DEPTH`], see [`crate::fuzzer::term_zoo`]
106    pub zoo_max_depth: Option<u16>,
107    /// Max number of paylaods per term (limiting further MakeMessage)
108    pub threshold_max_payloads_per_term: usize,
109}
110
111/// Default values which represent no constraint
112impl Default for TermConstraints {
113    fn default() -> Self {
114        Self {
115            min_term_size: 0,
116            // Selection cap. Comfortably above the maintenance rule `>= 2 * max_seed_term`
117            // (largest seed term today = 324 (TLS) => rule wants >= 648); we set 800 to leave
118            // headroom for future growth of the mappers (larger signatures / seed terms).
119            max_term_size: 800,
120            // Post-condition cap (reject-whole) on a single step recipe, i.e. the largest a step
121            // may become after a replacement. Kept >= `max_term_size` so a max-size replacement
122            // sub-term still fits into a step.
123            max_result_term_size: 1000,
124            must_be_symbolic: false,
125            no_payload_in_subterm: false,
126            must_payload_in_subterm: false,
127            not_inside_list: false,
128            weighted_depth: false,
129            must_be_root: false,
130            not_readable: false,
131            must_be_det: false,
132            zoo_gen_how_many: 10, /* Over-approximates 1/10 of the threshold obtained from
133                                   * `test_term_payloads_eval`, making sure we successfully
134                                   * generate, MakeMessage,
135                                   * and evaluate after 10 expansions of TermZoo. Was 1 initially */
136            zoo_max_depth: None,
137            threshold_max_payloads_per_term: 10,
138        }
139    }
140}
141
142impl TermConstraints {
143    /// Returns whether a term is not extremely large (in which case we don't even bother exploring
144    /// it)
145    pub fn satisfy_size_max_constraints<PT: ProtocolTypes>(&self, term: &Term<PT>) -> bool {
146        term.size() < self.max_term_size
147    }
148
149    /// Returns whether `term` satisfies the constraints, for a caller that already knows its size.
150    ///
151    /// [`TermType::size`] is recursive, so recomputing it at every node of a term makes a traversal
152    /// quadratic in the term size. Traversals that fold the sizes bottom-up (see
153    /// [`reservoir_sample`]) pass the size in instead.
154    pub fn satisfy_constraints_with_size<PT: ProtocolTypes>(
155        &self,
156        term: &Term<PT>,
157        size: usize,
158    ) -> bool {
159        // Use inclusive bounds (min <= size <= max)
160        if size < self.min_term_size || size > self.max_term_size {
161            return false;
162        }
163
164        if self.must_be_symbolic && !term.is_symbolic() {
165            return false;
166        }
167        if self.no_payload_in_subterm {
168            // filter-out terms with payload in strict sub-term
169            if term.is_symbolic() && term.has_payload_to_replace() {
170                return false;
171            }
172            if !term.is_symbolic() && term.has_payload_to_replace_wo_root() {
173                return false;
174            }
175        }
176        if self.not_inside_list && term.is_list() {
177            return false;
178        }
179        if self.not_readable && term.is_readable() {
180            return false;
181        }
182        if self.must_be_det && term.has_no_det() {
183            return false;
184        }
185        true
186    }
187
188    /// Returns whether we should recurse into the sub-terms of a given term.
189    pub fn should_recurse<PT: ProtocolTypes>(&self, term: &Term<PT>) -> bool {
190        // Only recurse into symbolic terms, and not when we only want root terms
191        !self.must_be_root && term.is_symbolic()
192    }
193
194    /// Return TermConstraints with minimal/no constraint
195    pub fn no_constraint() -> Self {
196        Self {
197            min_term_size: 0,
198            max_term_size: usize::MAX,
199            max_result_term_size: usize::MAX,
200            must_be_symbolic: false,
201            no_payload_in_subterm: false,
202            must_payload_in_subterm: false,
203            not_inside_list: false,
204            weighted_depth: false,
205            must_be_root: false,
206            not_readable: false,
207            must_be_det: false,
208            zoo_gen_how_many: usize::MAX,
209            zoo_max_depth: None,
210            threshold_max_payloads_per_term: usize::MAX,
211        }
212    }
213}
214
215pub trait Choosable<T, R: Rand> {
216    fn choose_filtered<P>(&self, filter: P, rand: &mut R) -> Option<&T>
217    where
218        P: FnMut(&&T) -> bool;
219    fn choose(&self, rand: &mut R) -> Option<&T>;
220}
221
222impl<T, R: Rand> Choosable<T, R> for Vec<T> {
223    fn choose_filtered<P>(&self, filter: P, rand: &mut R) -> Option<&T>
224    where
225        P: FnMut(&&T) -> bool,
226    {
227        let filtered = self.iter().filter(filter).collect::<Vec<&T>>();
228        let length = filtered.len();
229
230        if length == 0 {
231            None
232        } else {
233            let index = rand.below_or_zero(length);
234            filtered.into_iter().nth(index)
235        }
236    }
237
238    fn choose(&self, rand: &mut R) -> Option<&T> {
239        let length = self.len();
240
241        if length == 0 {
242            None
243        } else {
244            let index = rand.below_or_zero(length);
245            self.get(index)
246        }
247    }
248}
249
250pub fn choose_iter<I, E, T, R: Rand>(from: I, rand: &mut R) -> Option<T>
251where
252    I: IntoIterator<Item = T, IntoIter = E>,
253    E: ExactSizeIterator + Iterator<Item = T>,
254{
255    // create iterator
256    let mut iter = from.into_iter();
257    let length = iter.len();
258
259    if length == 0 {
260        None
261    } else {
262        // pick a random, valid index
263        let index = rand.below_or_zero(length);
264
265        // return the item chosen
266        iter.nth(index)
267    }
268}
269
270pub type StepIndex = usize;
271pub type TermPath = Vec<usize>;
272pub type TracePath = (StepIndex, TermPath);
273
274/// <https://en.wikipedia.org/wiki/Reservoir_sampling#Simple_algorithm>
275pub fn reservoir_sample<'a, R: Rand, PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
276    trace: &'a Trace<PT>,
277    filter: P,
278    constraints: &TermConstraints,
279    rand: &mut R,
280) -> Option<(&'a Term<PT>, TracePath)> {
281    let mut reservoir: Option<(&'a Term<PT>, TracePath)> = None;
282    let mut visited = 0;
283    let mut path = TermPath::new();
284
285    let locked = step_lock();
286    for (step_index, step) in trace.steps.iter().enumerate() {
287        // Anchor step lock: when a stage has locked a step, only draw anchors from that step.
288        if let Some(k) = locked {
289            if step_index != k {
290                continue;
291            }
292        }
293        match &step.action {
294            Action::Input(input) => {
295                let term = &input.recipe;
296
297                if !constraints.satisfy_size_max_constraints(term) {
298                    log::warn!(
299                        "[reservoir_sample] Skipping term because it is too large: {}",
300                        term.size()
301                    );
302                    continue; // the term is too large, we don't even bother
303                }
304
305                path.clear();
306                sample_subterms(
307                    term,
308                    step_index,
309                    &mut path,
310                    true,
311                    &filter,
312                    constraints,
313                    rand,
314                    &mut reservoir,
315                    &mut visited,
316                );
317            }
318            Action::Output(_) => {
319                // no term -> skip
320            }
321        }
322    }
323
324    reservoir
325}
326
327/// Post-order half of [`reservoir_sample`]: offers every selectable sub-term of `term` to the
328/// reservoir and returns `term`'s [`TermType::size`].
329///
330/// The size is folded bottom-up so that the whole traversal stays linear in the term size:
331/// calling [`TermType::size`] at each node instead would make it quadratic.
332///
333/// `selectable` says whether this node may be picked at all. It is `false` under a node the
334/// constraints forbid recursing into ([`TermConstraints::should_recurse`]); the traversal still
335/// goes on below such a node, but only to fold its size.
336///
337/// The recursion is spelled out as an explicit stack so that deep terms cannot overflow the call
338/// stack. `path` is the path of `term` inside its recipe, maintained in place: a child index is
339/// pushed before descending and popped after, so the traversal allocates a path only when the
340/// reservoir is actually updated.
341#[allow(clippy::too_many_arguments)]
342fn sample_subterms<'a, R: Rand, PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool>(
343    term: &'a Term<PT>,
344    step_index: StepIndex,
345    path: &mut TermPath,
346    selectable: bool,
347    filter: &P,
348    constraints: &TermConstraints,
349    rand: &mut R,
350    reservoir: &mut Option<(&'a Term<PT>, TracePath)>,
351    visited: &mut usize,
352) -> usize {
353    struct Frame<'a, PT: ProtocolTypes> {
354        term: &'a Term<PT>,
355        selectable: bool,
356        children_selectable: bool,
357        /// Index of the next child to descend into: the frame is visited once it reaches the
358        /// number of children.
359        next_child: usize,
360        /// Folded size of the children visited so far, plus 1 for the node itself. Mirrors
361        /// `TermType::size`: a non-symbolic term counts as an atom, and so does a variable or a
362        /// constant.
363        size: usize,
364    }
365
366    fn new_frame<'a, PT: ProtocolTypes>(
367        term: &'a Term<PT>,
368        selectable: bool,
369        constraints: &TermConstraints,
370    ) -> Frame<'a, PT> {
371        Frame {
372            term,
373            selectable,
374            children_selectable: selectable && constraints.should_recurse(term),
375            next_child: 0,
376            size: 1,
377        }
378    }
379
380    let mut root_size = 0;
381    let mut stack = vec![new_frame(term, selectable, constraints)];
382
383    while !stack.is_empty() {
384        let frame = stack.last_mut().unwrap();
385
386        let subterms: &'a [Term<PT>] = match &frame.term.term {
387            DYTerm::Application(_, subterms) if frame.term.is_symbolic() => subterms,
388            _ => &[],
389        };
390
391        // Descend into the next child, left to right, before visiting this node.
392        if frame.next_child < subterms.len() {
393            let child = &subterms[frame.next_child];
394            let children_selectable = frame.children_selectable;
395            path.push(frame.next_child);
396            frame.next_child += 1;
397            stack.push(new_frame(child, children_selectable, constraints));
398            continue;
399        }
400
401        let frame = stack.pop().unwrap();
402
403        // Check constraints and user filter
404        if frame.selectable
405            && constraints.satisfy_constraints_with_size(frame.term, frame.size)
406            && filter(frame.term)
407        {
408            *visited += 1;
409
410            // `1/visited` chance of overwriting: replace elements with gradually decreasing
411            // probability
412            if reservoir.is_none() || rand.between(1, *visited) == 1 {
413                *reservoir = Some((frame.term, (step_index, path.clone())));
414            }
415        }
416
417        match stack.last_mut() {
418            Some(parent) => {
419                parent.size += frame.size;
420                path.pop();
421            }
422            // `frame` is the root: its path was never pushed, and its size is the result.
423            None => root_size = frame.size,
424        }
425    }
426
427    root_size
428}
429
430pub fn find_term_by_term_path_mut<'a, PT: ProtocolTypes>(
431    term: &'a mut Term<PT>,
432    term_path: &[usize],
433) -> Option<&'a mut Term<PT>> {
434    if term_path.is_empty() {
435        return Some(term);
436    }
437    let subterm_index = term_path[0];
438
439    match &mut term.term {
440        DYTerm::Variable(_) => None,
441        DYTerm::Application(_, subterms) => {
442            if let Some(subterm) = subterms.get_mut(subterm_index) {
443                find_term_by_term_path_mut(subterm, &term_path[1..])
444            } else {
445                None
446            }
447        }
448    }
449}
450
451pub fn find_term_by_term_path<'a, PT: ProtocolTypes>(
452    term: &'a Term<PT>,
453    term_path: &[usize],
454) -> Option<&'a Term<PT>> {
455    if term_path.is_empty() {
456        return Some(term);
457    }
458
459    let subterm_index = term_path[0];
460
461    match &term.term {
462        DYTerm::Variable(_) => None,
463        DYTerm::Application(_, subterms) => {
464            if let Some(subterm) = subterms.get(subterm_index) {
465                find_term_by_term_path(subterm, &term_path[1..])
466            } else {
467                None
468            }
469        }
470    }
471}
472
473pub fn find_term_mut<'a, PT: ProtocolTypes>(
474    trace: &'a mut Trace<PT>,
475    trace_path: &TracePath,
476) -> Option<&'a mut Term<PT>> {
477    let (step_index, term_path) = trace_path;
478
479    let step: Option<&mut Step<PT>> = trace.steps.get_mut(*step_index);
480    if let Some(step) = step {
481        match &mut step.action {
482            Action::Input(input) => {
483                find_term_by_term_path_mut(&mut input.recipe, &term_path.clone())
484            }
485            Action::Output(_) => None,
486        }
487    } else {
488        None
489    }
490}
491
492#[must_use]
493pub fn find_term<'a, PT: ProtocolTypes>(
494    trace: &'a Trace<PT>,
495    trace_path: &TracePath,
496) -> Option<&'a Term<PT>> {
497    let (step_index, term_path) = trace_path;
498
499    let step: Option<&Step<PT>> = trace.steps.get(*step_index);
500    if let Some(step) = step {
501        match &step.action {
502            Action::Input(input) => find_term_by_term_path(&input.recipe, &term_path.clone()),
503            Action::Output(_) => None,
504        }
505    } else {
506        None
507    }
508}
509
510pub fn choose<'a, R: Rand, PT: ProtocolTypes>(
511    trace: &'a Trace<PT>,
512    constraints: &TermConstraints,
513    rand: &mut R,
514) -> Option<(&'a Term<PT>, (usize, TermPath))> {
515    reservoir_sample(trace, |_| true, constraints, rand)
516}
517
518pub fn choose_filtered<'a, R: Rand, PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
519    trace: &'a Trace<PT>,
520    constraints: &TermConstraints,
521    filter: P,
522    rand: &mut R,
523) -> Option<(&'a Term<PT>, (usize, TermPath))> {
524    reservoir_sample(trace, filter, constraints, rand)
525}
526
527pub fn choose_mut<'a, R: Rand, PT: ProtocolTypes>(
528    trace: &'a mut Trace<PT>,
529    constraints: &TermConstraints,
530    rand: &mut R,
531) -> Option<(&'a mut Term<PT>, (usize, TermPath))> {
532    if let Some((_, (u, path))) = reservoir_sample(trace, |_| true, constraints, rand) {
533        let t = find_term_mut(trace, &(u, path.clone()));
534        t.map(|t| (t, (u, path)))
535    } else {
536        None
537    }
538}
539
540pub fn choose_term<'a, R: Rand, PT: ProtocolTypes>(
541    trace: &'a Trace<PT>,
542    constraints: &TermConstraints,
543    rand: &mut R,
544) -> Option<&'a Term<PT>> {
545    reservoir_sample(trace, |_| true, constraints, rand).map(|ret| ret.0)
546}
547
548pub fn choose_term_mut<'a, R: Rand, PT: ProtocolTypes>(
549    trace: &'a mut Trace<PT>,
550    constraints: &TermConstraints,
551    rand: &mut R,
552) -> Option<&'a mut Term<PT>> {
553    if let Some(trace_path) = choose_term_path_filtered(trace, |_| true, constraints, rand) {
554        find_term_mut(trace, &trace_path)
555    } else {
556        None
557    }
558}
559
560pub fn choose_term_filtered_mut<'a, R: Rand, PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
561    trace: &'a mut Trace<PT>,
562    filter: P,
563    constraints: &TermConstraints,
564    rand: &mut R,
565) -> Option<&'a mut Term<PT>> {
566    if let Some(trace_path) = choose_term_path_filtered(trace, filter, constraints, rand) {
567        find_term_mut(trace, &trace_path)
568    } else {
569        None
570    }
571}
572
573pub fn choose_term_path<R: Rand, PT: ProtocolTypes>(
574    trace: &Trace<PT>,
575    constraints: &TermConstraints,
576    rand: &mut R,
577) -> Option<TracePath> {
578    choose_term_path_filtered(trace, |_| true, constraints, rand)
579}
580
581pub fn choose_term_path_filtered<R: Rand, PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
582    trace: &Trace<PT>,
583    filter: P,
584    constraints: &TermConstraints,
585    rand: &mut R,
586) -> Option<TracePath> {
587    reservoir_sample(trace, filter, constraints, rand).map(|ret| ret.1)
588}
589
590/// Finds all sub-terms in a given term that satisfy a filtering condition and term constraints.
591pub fn find_all_sub_term_filtered<PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
592    term: &Term<PT>,
593    filter: P,
594    constraints: &TermConstraints,
595) -> Vec<TermPath> {
596    let mut result = Vec::new();
597    let mut path = TermPath::new();
598    collect_subterms(term, &mut path, true, filter, constraints, &mut result);
599    result
600}
601
602/// Post-order half of [`find_all_sub_term_filtered`]: same bottom-up size fold and in-place `path`
603/// as [`sample_subterms`], collecting every matching path instead of sampling one.
604fn collect_subterms<PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
605    term: &Term<PT>,
606    path: &mut TermPath,
607    selectable: bool,
608    filter: P,
609    constraints: &TermConstraints,
610    result: &mut Vec<TermPath>,
611) -> usize {
612    let children_selectable = selectable && constraints.should_recurse(term);
613
614    let mut size = 1;
615    if term.is_symbolic() {
616        match &term.term {
617            DYTerm::Variable(_) => {}
618            DYTerm::Application(_, subterms) => {
619                for (i, subterm) in subterms.iter().enumerate() {
620                    path.push(i);
621                    size += collect_subterms(
622                        subterm,
623                        path,
624                        children_selectable,
625                        filter,
626                        constraints,
627                        result,
628                    );
629                    path.pop();
630                }
631            }
632        }
633    }
634
635    if selectable && constraints.satisfy_constraints_with_size(term, size) && filter(term) {
636        result.push(path.clone());
637    }
638
639    size
640}
641
642/// Finds all trace paths in a trace that satisfy a given filter predicate and term constraints.
643pub fn find_all_term_filtered<PT: ProtocolTypes, P: Fn(&Term<PT>) -> bool + Copy>(
644    trace: &Trace<PT>,
645    filter: P,
646    constraints: &TermConstraints,
647) -> Vec<TracePath> {
648    trace
649        .steps
650        .iter()
651        .enumerate()
652        .flat_map(|(step_index, step)| match &step.action {
653            Action::Input(input) => {
654                let term = &input.recipe;
655                find_all_sub_term_filtered(term, filter, constraints)
656                    .into_iter()
657                    .map(move |term_path| (step_index, term_path))
658                    .collect::<Vec<_>>()
659            }
660            Action::Output(_) => vec![],
661        })
662        .collect()
663}
664
665#[cfg(test)]
666mod tests {
667    use std::cell::RefCell;
668    use std::collections::{HashMap, HashSet};
669
670    use libafl_bolts::rands::StdRand;
671
672    use super::*;
673    use crate::algebra::test_signature::*;
674
675    /// Verbatim copy of the recursive `sample_subterms` this module replaced, kept as the
676    /// behavioural reference for `test_sample_subterms_matches_recursive_reference`.
677    #[allow(clippy::too_many_arguments)]
678    fn sample_subterms_reference<
679        'a,
680        R: Rand,
681        PT: ProtocolTypes,
682        P: Fn(&Term<PT>) -> bool + Copy,
683    >(
684        term: &'a Term<PT>,
685        step_index: StepIndex,
686        path: &mut TermPath,
687        selectable: bool,
688        filter: P,
689        constraints: &TermConstraints,
690        rand: &mut R,
691        reservoir: &mut Option<(&'a Term<PT>, TracePath)>,
692        visited: &mut usize,
693    ) -> usize {
694        let children_selectable = selectable && constraints.should_recurse(term);
695
696        let mut size = 1;
697        if term.is_symbolic() {
698            match &term.term {
699                DYTerm::Variable(_) => {}
700                DYTerm::Application(_, subterms) => {
701                    for (path_index, subterm) in subterms.iter().enumerate() {
702                        path.push(path_index);
703                        size += sample_subterms_reference(
704                            subterm,
705                            step_index,
706                            path,
707                            children_selectable,
708                            filter,
709                            constraints,
710                            rand,
711                            reservoir,
712                            visited,
713                        );
714                        path.pop();
715                    }
716                }
717            }
718        }
719
720        if selectable && constraints.satisfy_constraints_with_size(term, size) && filter(term) {
721            *visited += 1;
722            if reservoir.is_none() || rand.between(1, *visited) == 1 {
723                *reservoir = Some((term, (step_index, path.clone())));
724            }
725        }
726
727        size
728    }
729
730    /// The explicit-stack `sample_subterms` must be observationally identical to the recursion it
731    /// replaced: same visit order (hence same RNG draws), same folded sizes, same paths.
732    #[test_log::test]
733    fn test_sample_subterms_matches_recursive_reference() {
734        let trace = setup_simple_trace();
735        let constraints = TermConstraints::default();
736
737        for seed in 0..64u64 {
738            for (step_index, step) in trace.steps.iter().enumerate() {
739                let Action::Input(input) = &step.action else {
740                    continue;
741                };
742                let term = &input.recipe;
743
744                // Record the terms offered to the reservoir, in order. `filter` runs last in the
745                // `&&` chain, so this captures exactly the nodes that passed selectable + size.
746                let new_order: RefCell<Vec<*const Term<_>>> = RefCell::new(Vec::new());
747                let mut new_reservoir = None;
748                let mut new_visited = 0;
749                let mut new_path = TermPath::new();
750                let mut new_rand = StdRand::with_seed(seed);
751                let new_size = sample_subterms(
752                    term,
753                    step_index,
754                    &mut new_path,
755                    true,
756                    &|t: &Term<_>| {
757                        new_order.borrow_mut().push(t as *const _);
758                        true
759                    },
760                    &constraints,
761                    &mut new_rand,
762                    &mut new_reservoir,
763                    &mut new_visited,
764                );
765
766                let ref_order: RefCell<Vec<*const Term<_>>> = RefCell::new(Vec::new());
767                let mut ref_reservoir = None;
768                let mut ref_visited = 0;
769                let mut ref_path = TermPath::new();
770                let mut ref_rand = StdRand::with_seed(seed);
771                let ref_size = sample_subterms_reference(
772                    term,
773                    step_index,
774                    &mut ref_path,
775                    true,
776                    |t: &Term<_>| {
777                        ref_order.borrow_mut().push(t as *const _);
778                        true
779                    },
780                    &constraints,
781                    &mut ref_rand,
782                    &mut ref_reservoir,
783                    &mut ref_visited,
784                );
785
786                assert_eq!(new_size, ref_size, "folded size differs (seed {seed})");
787                assert_eq!(
788                    new_size,
789                    term.size(),
790                    "folded size differs from TermType::size"
791                );
792                assert_eq!(
793                    new_visited, ref_visited,
794                    "visited count differs (seed {seed})"
795                );
796                assert_eq!(
797                    new_order.into_inner(),
798                    ref_order.into_inner(),
799                    "visit order differs (seed {seed})"
800                );
801                assert!(new_path.is_empty(), "path left dirty (seed {seed})");
802                assert_eq!(new_path, ref_path, "path left dirty (seed {seed})");
803
804                let new_pick = new_reservoir.map(|(t, p)| (t as *const Term<_>, p));
805                let ref_pick = ref_reservoir.map(|(t, p)| (t as *const Term<_>, p));
806                assert_eq!(
807                    new_pick, ref_pick,
808                    "sampled term/path differs (seed {seed})"
809                );
810            }
811        }
812    }
813
814    #[test_log::test]
815    fn test_find_term() {
816        let mut rand = StdRand::with_seed(45);
817        let mut trace = setup_simple_trace();
818        let term_size = trace.count_functions();
819
820        let mut stats: HashSet<TracePath> = HashSet::new();
821
822        for _ in 0..10000 {
823            let path = choose_term_path(&trace, &TermConstraints::default(), &mut rand).unwrap();
824            find_term_mut(&mut trace, &path).unwrap();
825            stats.insert(path);
826        }
827
828        assert_eq!(term_size, stats.len());
829    }
830
831    #[test_log::test]
832    fn test_reservoir_sample_randomness() {
833        /// https://rust-lang-nursery.github.io/rust-cookbook/science/mathematics/statistics.html#standard-deviation
834        fn std_deviation(data: &[u32]) -> Option<f32> {
835            fn mean(data: &[u32]) -> Option<f32> {
836                let sum = data.iter().sum::<u32>() as f32;
837                let count = data.len();
838
839                match count {
840                    positive if positive > 0 => Some(sum / count as f32),
841                    _ => None,
842                }
843            }
844
845            match (mean(data), data.len()) {
846                (Some(data_mean), count) if count > 0 => {
847                    let variance = data
848                        .iter()
849                        .map(|value| {
850                            let diff = data_mean - (*value as f32);
851
852                            diff * diff
853                        })
854                        .sum::<f32>()
855                        / count as f32;
856
857                    Some(variance.sqrt())
858                }
859                _ => None,
860            }
861        }
862
863        let trace = setup_simple_trace();
864        let term_size = trace.count_functions();
865
866        let mut rand = StdRand::with_seed(45);
867        let mut stats: HashMap<u32, u32> = HashMap::new();
868
869        for _ in 0..10000 {
870            let term = choose(&trace, &TermConstraints::default(), &mut rand).unwrap();
871
872            let id = term.0.resistant_id();
873
874            let count: u32 = *stats.get(&id).unwrap_or(&0);
875            stats.insert(id, count + 1);
876        }
877
878        let std_dev =
879            std_deviation(stats.values().copied().collect::<Vec<u32>>().as_slice()).unwrap();
880        /*        println!("{:?}", std_dev);
881        println!("{:?}", stats);*/
882
883        assert!(std_dev < 30.0);
884        assert_eq!(term_size, stats.len());
885    }
886
887    #[test_log::test]
888    fn test_step_lock_confines_anchors_to_locked_step() {
889        let trace = setup_simple_trace();
890        let n_steps = trace.steps.len();
891        assert!(n_steps >= 2, "need a multi-step trace to test the lock");
892        let mut rand = StdRand::with_seed(45);
893
894        // With a lock set, every anchor drawn must come from exactly the locked step.
895        for k in 0..n_steps {
896            let prev = set_step_lock(Some(k));
897            for _ in 0..500 {
898                if let Some((_, (step_index, _))) =
899                    choose(&trace, &TermConstraints::default(), &mut rand)
900                {
901                    assert_eq!(step_index, k, "anchor escaped the locked step {}", k);
902                }
903            }
904            set_step_lock(prev);
905        }
906
907        // Without a lock, anchors must spread across more than one step (sanity: the lock is what
908        // confined them above, not some other property of the trace).
909        set_step_lock(None);
910        let mut seen = HashSet::new();
911        for _ in 0..2000 {
912            if let Some((_, (step_index, _))) =
913                choose(&trace, &TermConstraints::default(), &mut rand)
914            {
915                seen.insert(step_index);
916            }
917        }
918        assert!(
919            seen.len() > 1,
920            "unlocked anchors should span multiple steps, saw {:?}",
921            seen
922        );
923    }
924}