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 static STEP_LOCK: Cell<Option<StepIndex>> = const { Cell::new(None) };
19}
20
21pub fn set_step_lock(step: Option<StepIndex>) -> Option<StepIndex> {
24 STEP_LOCK.with(|c| c.replace(step))
25}
26
27pub fn step_lock() -> Option<StepIndex> {
29 STEP_LOCK.with(Cell::get)
30}
31
32#[derive(Copy, Clone, Debug)]
76pub struct TermConstraints {
77 pub min_term_size: usize,
79 pub max_term_size: usize,
82 pub max_result_term_size: usize,
85 pub must_be_symbolic: bool,
86 pub no_payload_in_subterm: bool,
88 pub must_payload_in_subterm: bool,
90 pub not_inside_list: bool,
94 pub weighted_depth: bool,
96 pub must_be_root: bool,
98 pub not_readable: bool,
100 pub must_be_det: bool,
102 pub zoo_gen_how_many: usize,
104 pub zoo_max_depth: Option<u16>,
107 pub threshold_max_payloads_per_term: usize,
109}
110
111impl Default for TermConstraints {
113 fn default() -> Self {
114 Self {
115 min_term_size: 0,
116 max_term_size: 800,
120 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, zoo_max_depth: None,
137 threshold_max_payloads_per_term: 10,
138 }
139 }
140}
141
142impl TermConstraints {
143 pub fn satisfy_size_max_constraints<PT: ProtocolTypes>(&self, term: &Term<PT>) -> bool {
146 term.size() < self.max_term_size
147 }
148
149 pub fn satisfy_constraints_with_size<PT: ProtocolTypes>(
155 &self,
156 term: &Term<PT>,
157 size: usize,
158 ) -> bool {
159 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 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 pub fn should_recurse<PT: ProtocolTypes>(&self, term: &Term<PT>) -> bool {
190 !self.must_be_root && term.is_symbolic()
192 }
193
194 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 let mut iter = from.into_iter();
257 let length = iter.len();
258
259 if length == 0 {
260 None
261 } else {
262 let index = rand.below_or_zero(length);
264
265 iter.nth(index)
267 }
268}
269
270pub type StepIndex = usize;
271pub type TermPath = Vec<usize>;
272pub type TracePath = (StepIndex, TermPath);
273
274pub 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 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; }
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 }
321 }
322 }
323
324 reservoir
325}
326
327#[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 next_child: usize,
360 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 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 if frame.selectable
405 && constraints.satisfy_constraints_with_size(frame.term, frame.size)
406 && filter(frame.term)
407 {
408 *visited += 1;
409
410 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 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
590pub 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
602fn 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
642pub 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 #[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 #[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 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 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 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 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 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}