1use crate::{
4 BasicTxDetails, FuzzFixtures,
5 invariant::FuzzRunIdentifiedContracts,
6 strategies::{
7 FuzzState, TxGenerator, constrain_enum_value, generate_msg_value, mutate_param_value,
8 },
9};
10use alloy_dyn_abi::{DynSolValue, JsonAbiExt, abi::AbiDecoderConfig};
11use alloy_json_abi::Function;
12use alloy_primitives::{U256, map::HashSet};
13use eyre::{Result, eyre};
14use foundry_config::{FuzzCorpusConfig, FuzzCorpusMutationWeights};
15use proptest::test_runner::TestRunner;
16use rand::{
17 Rng,
18 distr::{Distribution, weighted::WeightedIndex},
19};
20use std::mem::replace;
21
22#[derive(Clone, Copy)]
24pub struct CorpusEntryView<'a> {
25 transactions: &'a [BasicTxDetails],
26 comparisons: &'a [Vec<ComparisonHint>],
27}
28
29impl<'a> CorpusEntryView<'a> {
30 pub fn new(
31 transactions: &'a [BasicTxDetails],
32 comparisons: &'a [Vec<ComparisonHint>],
33 ) -> Result<Self> {
34 if transactions.is_empty() {
35 return Err(eyre!("corpus entry has no transactions"));
36 }
37 if comparisons.len() > transactions.len() {
38 return Err(eyre!("corpus entry has more comparison sets than transactions"));
39 }
40 Ok(Self { transactions, comparisons })
41 }
42}
43
44#[derive(Clone)]
45enum SequenceMode {
46 Stateless(Function),
47 Invariant(FuzzRunIdentifiedContracts),
48}
49
50#[derive(Clone)]
52pub struct SequenceGenerator {
53 tx: TxGenerator,
54 state: FuzzState,
55 fixtures: FuzzFixtures,
56 mode: SequenceMode,
57 weights: FuzzCorpusMutationWeights,
58 mutations: WeightedIndex<u32>,
59 arg_mutations: Option<WeightedIndex<u32>>,
60 fresh_weight: u32,
61 payable_weight: u32,
62 has_corpus_dir: bool,
63}
64
65pub struct SequencePlan {
67 initial: InitialSequence,
68 tx: TxGenerator,
69 continuation: Continuation,
70 source: Option<usize>,
71}
72
73#[derive(Clone, Copy, Debug, PartialEq, Eq)]
75enum Continuation {
76 Stateless,
78 Fresh,
80 Initial { fresh_weight: u32 },
83}
84
85enum InitialSequence {
86 Single(BasicTxDetails),
87 Multiple(Vec<BasicTxDetails>),
88}
89
90impl InitialSequence {
91 pub fn into_first(self) -> BasicTxDetails {
92 match self {
93 Self::Single(tx) => tx,
94 Self::Multiple(mut txs) => txs.remove(0),
95 }
96 }
97
98 pub fn as_slice(&self) -> &[BasicTxDetails] {
99 match self {
100 Self::Single(tx) => std::slice::from_ref(tx),
101 Self::Multiple(txs) => txs,
102 }
103 }
104}
105
106impl SequencePlan {
107 pub fn initial(&self) -> &[BasicTxDetails] {
108 self.initial.as_slice()
109 }
110 pub fn into_first(self) -> BasicTxDetails {
111 self.initial.into_first()
112 }
113 pub const fn source(&self) -> Option<usize> {
114 self.source
115 }
116
117 pub fn replay(mut self, transactions: Vec<BasicTxDetails>) -> Result<Self> {
119 if transactions.is_empty() {
120 return Err(eyre!("replay sequence has no transactions"));
121 }
122 self.initial = InitialSequence::Multiple(transactions);
123 if self.continuation != Continuation::Stateless {
124 self.continuation = Continuation::Initial { fresh_weight: 0 };
125 }
126 self.source = None;
127 Ok(self)
128 }
129
130 pub fn next(
131 &self,
132 runner: &mut TestRunner,
133 discarded: bool,
134 depth: usize,
135 ) -> Result<BasicTxDetails> {
136 match self.continuation {
137 Continuation::Stateless => {
138 Err(eyre!("stateless sequence is limited to one transaction"))
139 }
140 Continuation::Fresh => self.tx.next_tx(runner),
141 Continuation::Initial { .. } if discarded => self.tx.next_tx(runner),
142 Continuation::Initial { fresh_weight } => {
143 let fresh = fresh_weight > 0 && runner.rng().random_ratio(fresh_weight, 100);
144 if depth >= self.initial.as_slice().len() || fresh {
145 self.tx.next_tx(runner)
146 } else {
147 Ok(self.initial.as_slice()[depth].clone())
148 }
149 }
150 }
151 }
152}
153
154#[derive(Clone, Copy)]
155enum MutationType {
156 Splice,
157 Repeat,
158 Interleave,
159 Prefix,
160 Suffix,
161 Abi,
162 Cmp,
163}
164
165impl SequenceGenerator {
166 pub fn stateless(
167 tx: TxGenerator,
168 state: FuzzState,
169 function: Function,
170 config: &FuzzCorpusConfig,
171 ) -> Result<Self> {
172 Self::stateless_with_fixtures(tx, state, FuzzFixtures::default(), function, config)
173 }
174 pub fn stateless_with_fixtures(
175 tx: TxGenerator,
176 state: FuzzState,
177 fixtures: FuzzFixtures,
178 function: Function,
179 config: &FuzzCorpusConfig,
180 ) -> Result<Self> {
181 Self::new(tx, state, fixtures, SequenceMode::Stateless(function), config)
182 }
183 pub fn invariant(
184 tx: TxGenerator,
185 state: FuzzState,
186 targets: FuzzRunIdentifiedContracts,
187 config: &FuzzCorpusConfig,
188 ) -> Result<Self> {
189 Self::invariant_with_fixtures(tx, state, FuzzFixtures::default(), targets, config)
190 }
191 pub fn invariant_with_fixtures(
192 tx: TxGenerator,
193 state: FuzzState,
194 fixtures: FuzzFixtures,
195 targets: FuzzRunIdentifiedContracts,
196 config: &FuzzCorpusConfig,
197 ) -> Result<Self> {
198 Self::new(tx, state, fixtures, SequenceMode::Invariant(targets), config)
199 }
200 fn new(
201 tx: TxGenerator,
202 state: FuzzState,
203 fixtures: FuzzFixtures,
204 mode: SequenceMode,
205 config: &FuzzCorpusConfig,
206 ) -> Result<Self> {
207 let weights = config.mutation_weights.effective();
208 if weights.total() > u64::from(u32::MAX) {
209 return Err(eyre!(
210 "effective mutation weights sum to {}, which exceeds the maximum supported total {}",
211 weights.total(),
212 u32::MAX
213 ));
214 }
215 let all = [
216 weights.mutation_weight_splice,
217 weights.mutation_weight_repeat,
218 weights.mutation_weight_interleave,
219 weights.mutation_weight_prefix,
220 weights.mutation_weight_suffix,
221 weights.mutation_weight_abi,
222 weights.mutation_weight_cmp,
223 ];
224 let mutations =
225 WeightedIndex::new(all).map_err(|e| eyre!("invalid corpus mutation weights: {e}"))?;
226 let arg_mutations = if weights.mutation_weight_abi == 0 && weights.mutation_weight_cmp == 0
227 {
228 None
229 } else {
230 Some(
231 WeightedIndex::new([weights.mutation_weight_abi, weights.mutation_weight_cmp])
232 .map_err(|e| eyre!("invalid argument mutation weights: {e}"))?,
233 )
234 };
235 Ok(Self {
236 tx,
237 state,
238 fixtures,
239 mode,
240 weights,
241 mutations,
242 arg_mutations,
243 fresh_weight: config.corpus_random_sequence_weight.min(100),
244 payable_weight: config.payable_value_weight,
245 has_corpus_dir: config.corpus_dir.is_some(),
246 })
247 }
248
249 pub fn start<'a, F>(
250 &self,
251 runner: &mut TestRunner,
252 corpus_len: usize,
253 mut entry_at: F,
254 coverage: bool,
255 ) -> Result<SequencePlan>
256 where
257 F: FnMut(usize) -> Result<CorpusEntryView<'a>>,
258 {
259 let (initial, source) = match &self.mode {
260 SequenceMode::Stateless(function) => {
261 self.start_stateless(runner, corpus_len, &mut entry_at, coverage, function)?
262 }
263 SequenceMode::Invariant(targets) => {
264 self.start_invariant(runner, corpus_len, &mut entry_at, coverage, targets)?
265 }
266 };
267 Ok(SequencePlan { initial, tx: self.tx.clone(), continuation: self.continuation(), source })
268 }
269
270 const fn continuation(&self) -> Continuation {
272 match self.mode {
273 SequenceMode::Stateless(_) => Continuation::Stateless,
274 SequenceMode::Invariant(_) if self.has_corpus_dir => {
275 Continuation::Initial { fresh_weight: self.fresh_weight }
276 }
277 SequenceMode::Invariant(_) => Continuation::Fresh,
278 }
279 }
280
281 fn start_stateless<'a>(
282 &self,
283 runner: &mut TestRunner,
284 corpus_len: usize,
285 entry_at: &mut impl FnMut(usize) -> Result<CorpusEntryView<'a>>,
286 coverage: bool,
287 function: &Function,
288 ) -> Result<(InitialSequence, Option<usize>)> {
289 if !coverage
290 || corpus_len == 0
291 || (self.fresh_weight > 0 && runner.rng().random_ratio(self.fresh_weight, 100))
292 {
293 return Ok((InitialSequence::Single(self.tx.next_tx(runner)?), None));
294 }
295 let index = runner.rng().random_range(0..corpus_len);
296 let entry = entry_at(index)?;
297 let mut tx = entry.transactions[0].clone();
298 let hints = entry.comparisons.first().map_or(&[][..], Vec::as_slice);
299 match self.arg_mutations.as_ref().map(|d| d.sample(runner.rng()) == 1) {
300 Some(true)
301 if !SequenceMutator::cmp_mutate(
302 &mut tx,
303 function,
304 hints,
305 runner,
306 &self.fixtures,
307 )? && self.weights.mutation_weight_abi > 0
308 && !function.inputs.is_empty() =>
309 {
310 SequenceMutator::abi_mutate(
311 &mut tx,
312 function,
313 runner,
314 &self.state,
315 &self.fixtures,
316 self.payable_weight,
317 )?
318 }
319 Some(true) => {}
320 Some(false) if self.weights.mutation_weight_abi > 0 && !function.inputs.is_empty() => {
321 SequenceMutator::abi_mutate(
322 &mut tx,
323 function,
324 runner,
325 &self.state,
326 &self.fixtures,
327 self.payable_weight,
328 )?
329 }
330 Some(false) if self.weights.mutation_weight_cmp > 0 => {
331 let _ =
332 SequenceMutator::cmp_mutate(&mut tx, function, hints, runner, &self.fixtures)?;
333 }
334 None => return Ok((InitialSequence::Single(self.tx.next_tx(runner)?), None)),
335 _ => {}
336 }
337 Ok((InitialSequence::Single(tx), Some(index)))
338 }
339
340 fn start_invariant<'a>(
341 &self,
342 runner: &mut TestRunner,
343 corpus_len: usize,
344 entry_at: &mut impl FnMut(usize) -> Result<CorpusEntryView<'a>>,
345 coverage: bool,
346 targets: &FuzzRunIdentifiedContracts,
347 ) -> Result<(InitialSequence, Option<usize>)> {
348 if !coverage || corpus_len == 0 {
349 return Ok((InitialSequence::Multiple(vec![self.tx.next_tx(runner)?]), None));
350 }
351 let kind = match self.mutations.sample(runner.rng()) {
352 0 => MutationType::Splice,
353 1 => MutationType::Repeat,
354 2 => MutationType::Interleave,
355 3 => MutationType::Prefix,
356 4 => MutationType::Suffix,
357 5 => MutationType::Abi,
358 _ => MutationType::Cmp,
359 };
360 let a = runner.rng().random_range(0..corpus_len);
361 let b = runner.rng().random_range(0..corpus_len);
362 let primary = entry_at(a)?;
363 let secondary = entry_at(b)?;
364 let (mut seq, source) = match kind {
365 MutationType::Splice => {
366 (SequenceMutator::splice(primary.transactions, secondary.transactions, runner), a)
367 }
368 MutationType::Interleave => (
369 SequenceMutator::interleave(primary.transactions, secondary.transactions, runner),
370 a,
371 ),
372 MutationType::Repeat => {
373 let i = if runner.rng().random() { a } else { b };
374 let entry = if i == a { primary } else { secondary };
375 (SequenceMutator::repeat(entry.transactions, runner), i)
376 }
377 MutationType::Prefix | MutationType::Suffix => {
378 let i = if runner.rng().random() { a } else { b };
379 let base = if i == a { primary.transactions } else { secondary.transactions };
380 let len = if matches!(kind, MutationType::Prefix) {
381 runner.rng().random_range(0..=base.len())
382 } else {
383 runner.rng().random_range(0..base.len())
384 };
385 let mut r = Vec::with_capacity(len);
386 for _ in 0..len {
387 r.push(self.tx.next_tx(runner)?)
388 }
389 (
390 if matches!(kind, MutationType::Prefix) {
391 SequenceMutator::prefix(base, r)
392 } else {
393 SequenceMutator::suffix(base, r)
394 },
395 i,
396 )
397 }
398 MutationType::Abi | MutationType::Cmp => {
399 let i = if runner.rng().random() { a } else { b };
400 let entry = if i == a { primary } else { secondary };
401 let mut seq = entry.transactions.to_vec();
402 let fallback = runner.rng().random_range(0..seq.len());
403 if matches!(kind, MutationType::Abi) {
404 let tx = &mut seq[fallback];
405 if let (_, Some(f)) = targets.targets().fuzzed_artifacts(tx)
406 && !f.inputs.is_empty()
407 {
408 SequenceMutator::abi_mutate(
409 tx,
410 f,
411 runner,
412 &self.state,
413 &self.fixtures,
414 self.payable_weight,
415 )?;
416 }
417 } else {
418 let candidates =
419 entry.comparisons.iter().enumerate().filter(|(_, h)| !h.is_empty());
420 let count = candidates.clone().count();
421 let mut mutated = false;
422 if count > 0 {
423 let start = runner.rng().random_range(0..count);
424 for (idx, h) in candidates.cycle().skip(start).take(count) {
425 let tx = &mut seq[idx];
426 if let (_, Some(f)) = targets.targets().fuzzed_artifacts(tx) {
427 mutated =
428 SequenceMutator::cmp_mutate(tx, f, h, runner, &self.fixtures)?;
429 if mutated {
430 break;
431 }
432 }
433 }
434 }
435 if !mutated && self.weights.mutation_weight_abi > 0 {
436 let tx = &mut seq[fallback];
437 if let (_, Some(f)) = targets.targets().fuzzed_artifacts(tx)
438 && !f.inputs.is_empty()
439 {
440 SequenceMutator::abi_mutate(
441 tx,
442 f,
443 runner,
444 &self.state,
445 &self.fixtures,
446 self.payable_weight,
447 )?
448 }
449 }
450 }
451 (seq, i)
452 }
453 };
454 if seq.is_empty() {
455 seq.push(self.tx.next_tx(runner)?)
456 }
457 Ok((InitialSequence::Multiple(seq), Some(source)))
458 }
459}
460
461#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
463pub struct ComparisonHint {
464 pub lhs: U256,
465 pub rhs: U256,
466}
467
468impl ComparisonHint {
469 pub fn applicable(calldata: &[u8], hints: impl IntoIterator<Item = Self>) -> Vec<Self> {
478 let mut seen = HashSet::<Self>::default();
479 let hints = hints.into_iter().filter(|hint| seen.insert(*hint)).collect::<Vec<_>>();
480 if hints.is_empty() {
481 return hints;
482 }
483 let operands = hints
484 .iter()
485 .map(|hint| (hint.lhs.to_be_bytes::<32>(), hint.rhs.to_be_bytes::<32>()))
486 .collect::<Vec<_>>();
487 let found = CMP_WIDTHS.map(|width| {
488 find_operands(
489 calldata,
490 operands.iter().flat_map(|(lhs, rhs)| {
491 let lhs = &lhs[32 - width..];
492 let rhs = &rhs[32 - width..];
493 (lhs != rhs).then_some([lhs, rhs]).into_iter().flatten()
494 }),
495 )
496 });
497 let mut applicable = hints
498 .into_iter()
499 .zip(&operands)
500 .filter(|(_, (lhs, rhs))| {
501 CMP_WIDTHS.iter().zip(&found).any(|(&width, found)| {
502 let lhs = &lhs[32 - width..];
503 let rhs = &rhs[32 - width..];
504 lhs != rhs && (found.contains(lhs) || found.contains(rhs))
505 })
506 })
507 .map(|(hint, _)| hint)
508 .collect::<Vec<_>>();
509 applicable.shrink_to_fit();
511 applicable
512 }
513
514 pub fn applies_to(&self, calldata: &[u8]) -> bool {
517 let lhs = self.lhs.to_be_bytes::<32>();
518 let rhs = self.rhs.to_be_bytes::<32>();
519 CMP_WIDTHS.iter().any(|&width| {
520 let lhs = &lhs[32 - width..];
521 let rhs = &rhs[32 - width..];
522 lhs != rhs && (contains_operand(calldata, lhs) || contains_operand(calldata, rhs))
523 })
524 }
525}
526
527struct SequenceMutator;
529
530impl SequenceMutator {
531 fn splice(
532 first: &[BasicTxDetails],
533 second: &[BasicTxDetails],
534 runner: &mut TestRunner,
535 ) -> Vec<BasicTxDetails> {
536 let rng = runner.rng();
537 let start1 = rng.random_range(0..first.len());
538 let end1 = rng.random_range(start1..first.len());
539 let start2 = rng.random_range(0..second.len());
540 let end2 = rng.random_range(start2..second.len());
541 first[start1..=end1].iter().chain(&second[start2..=end2]).cloned().collect()
542 }
543
544 fn repeat(sequence: &[BasicTxDetails], runner: &mut TestRunner) -> Vec<BasicTxDetails> {
545 let rng = runner.rng();
546 let start = rng.random_range(0..sequence.len());
547 let end = rng.random_range(start..=sequence.len());
548 let repeated = sequence[rng.random_range(0..sequence.len())].clone();
549 let mut result = Vec::with_capacity(sequence.len());
550 result.extend_from_slice(&sequence[..start]);
551 result.extend((start..end).map(|_| repeated.clone()));
552 result.extend_from_slice(&sequence[end..]);
553 result
554 }
555
556 fn interleave(
557 first: &[BasicTxDetails],
558 second: &[BasicTxDetails],
559 runner: &mut TestRunner,
560 ) -> Vec<BasicTxDetails> {
561 first
562 .iter()
563 .zip(second)
564 .map(
565 |(first, second)| {
566 if runner.rng().random() { first.clone() } else { second.clone() }
567 },
568 )
569 .collect()
570 }
571
572 fn prefix(
573 sequence: &[BasicTxDetails],
574 mut replacements: Vec<BasicTxDetails>,
575 ) -> Vec<BasicTxDetails> {
576 replacements.truncate(sequence.len());
577 let mut result = sequence.to_vec();
578 result[..replacements.len()].clone_from_slice(&replacements);
579 result
580 }
581
582 fn suffix(
583 sequence: &[BasicTxDetails],
584 mut replacements: Vec<BasicTxDetails>,
585 ) -> Vec<BasicTxDetails> {
586 replacements.truncate(sequence.len());
587 let mut result = sequence.to_vec();
588 let retained = result.len() - replacements.len();
589 result[retained..].clone_from_slice(&replacements);
590 result
591 }
592
593 fn abi_mutate(
595 tx: &mut BasicTxDetails,
596 function: &Function,
597 runner: &mut TestRunner,
598 state: &FuzzState,
599 fixtures: &FuzzFixtures,
600 payable_value_weight: u32,
601 ) -> Result<()> {
602 if function.inputs.is_empty() || tx.call_details.calldata.len() < 4 {
603 return Ok(());
604 }
605 if function.state_mutability == alloy_json_abi::StateMutability::Payable
606 && runner.rng().random_ratio(payable_value_weight.min(100), 100)
607 {
608 tx.call_details.value = Some(generate_msg_value(runner));
609 }
610 let mut rounds = runner.rng().random_range(0..=function.inputs.len()).max(1);
611 let indices = if function.inputs.len() <= 1 {
612 vec![0]
613 } else {
614 (0..rounds).map(|_| runner.rng().random_range(0..function.inputs.len())).collect()
615 };
616 let Ok(mut inputs) = function.abi_decode_input(&tx.call_details.calldata[4..]) else {
619 return Ok(());
620 };
621 while rounds > 0 {
622 let index = indices[rounds - 1];
623 let param = function.inputs[index].selector_type().parse()?;
624 let value = replace(&mut inputs[index], DynSolValue::Bool(false));
625 inputs[index] = mutate_param_value(¶m, value, runner, state);
626 rounds -= 1;
627 }
628 let inputs = inputs
629 .into_iter()
630 .zip(&function.inputs)
631 .map(|(value, input)| constrain_enum_value(value, input, fixtures))
632 .collect::<Vec<_>>();
633 tx.call_details.calldata =
634 function.abi_encode_input(&inputs).map_err(|err| eyre!(err.to_string()))?.into();
635 Ok(())
636 }
637
638 fn cmp_mutate(
639 tx: &mut BasicTxDetails,
640 function: &Function,
641 hints: &[ComparisonHint],
642 runner: &mut TestRunner,
643 fixtures: &FuzzFixtures,
644 ) -> Result<bool> {
645 if hints.is_empty() || tx.call_details.calldata.len() <= 4 {
646 return Ok(false);
647 }
648 let config = AbiDecoderConfig::new().validate_words(true);
649 let start = runner.rng().random_range(0..hints.len());
650 for offset in 0..hints.len() {
651 if let Some(calldata) = cmp_mutated_calldata(
652 tx.call_details.calldata.as_ref(),
653 hints[(start + offset) % hints.len()],
654 runner,
655 ) && let Ok(inputs) = function.abi_decode_input_with_config(&calldata[4..], config)
656 && inputs.iter().zip(&function.inputs).all(|(value, input)| {
657 constrain_enum_value(value.clone(), input, fixtures) == *value
658 })
659 {
660 tx.call_details.calldata = calldata.into();
661 return Ok(true);
662 }
663 }
664 Ok(false)
665 }
666}
667
668const CMP_WIDTHS: [usize; 6] = [32, 16, 8, 4, 2, 1];
670
671fn cmp_mutated_calldata(
672 calldata: &[u8],
673 hint: ComparisonHint,
674 runner: &mut TestRunner,
675) -> Option<Vec<u8>> {
676 let lhs = hint.lhs.to_be_bytes::<32>();
677 let rhs = hint.rhs.to_be_bytes::<32>();
678 let start = runner.rng().random_range(0..CMP_WIDTHS.len());
679 for offset in 0..CMP_WIDTHS.len() {
680 let width = CMP_WIDTHS[(start + offset) % CMP_WIDTHS.len()];
681 let lhs = &lhs[32 - width..];
682 let rhs = &rhs[32 - width..];
683 if lhs == rhs {
684 continue;
685 }
686 let pairs =
687 if runner.rng().random() { [(lhs, rhs), (rhs, lhs)] } else { [(rhs, lhs), (lhs, rhs)] };
688 for (pattern, replacement) in pairs {
689 if let Some(mutated) = replace_operand(calldata, pattern, replacement, runner) {
690 return Some(mutated);
691 }
692 }
693 }
694 None
695}
696
697const SELECTOR_LEN: usize = 4;
699
700fn is_replaceable_operand(calldata: &[u8], pattern: &[u8]) -> bool {
702 !pattern.is_empty()
703 && calldata.len() >= SELECTOR_LEN + pattern.len()
704 && (pattern.len() == 32 || pattern.iter().any(|byte| *byte != 0))
705}
706
707fn contains_operand(calldata: &[u8], pattern: &[u8]) -> bool {
709 is_replaceable_operand(calldata, pattern)
710 && calldata[SELECTOR_LEN..].windows(pattern.len()).any(|window| window == pattern)
711}
712
713fn find_operands<'a>(
717 calldata: &[u8],
718 patterns: impl IntoIterator<Item = &'a [u8]>,
719) -> HashSet<&'a [u8]> {
720 let mut missing = patterns
721 .into_iter()
722 .filter(|pattern| is_replaceable_operand(calldata, pattern))
723 .collect::<HashSet<_>>();
724 let mut found = HashSet::default();
725 let Some(width) = missing.iter().next().map(|pattern| pattern.len()) else { return found };
726 for window in calldata[SELECTOR_LEN..].windows(width) {
727 if let Some(pattern) = missing.take(window) {
728 found.insert(pattern);
729 if missing.is_empty() {
730 break;
731 }
732 }
733 }
734 found
735}
736
737fn replace_operand(
738 calldata: &[u8],
739 pattern: &[u8],
740 replacement: &[u8],
741 runner: &mut TestRunner,
742) -> Option<Vec<u8>> {
743 if pattern.len() != replacement.len() || !is_replaceable_operand(calldata, pattern) {
744 return None;
745 }
746 let search_len = calldata.len() - SELECTOR_LEN - pattern.len() + 1;
747 let start = runner.rng().random_range(0..search_len);
748 for offset in 0..search_len {
749 let index = SELECTOR_LEN + ((start + offset) % search_len);
750 if &calldata[index..index + pattern.len()] == pattern {
751 let mut mutated = calldata.to_vec();
752 mutated[index..index + replacement.len()].copy_from_slice(replacement);
753 return Some(mutated);
754 }
755 }
756 None
757}
758
759#[cfg(test)]
760mod tests {
761 use super::*;
762 use crate::{
763 CallDetails,
764 invariant::{TargetedContract, TargetedContracts},
765 strategies::EvmFuzzState,
766 };
767 use alloy_json_abi::JsonAbi;
768 use alloy_primitives::{Address, Bytes, I256};
769 use evm2::evm::InMemoryDB;
770 use foundry_config::FuzzDictionaryConfig;
771 use proptest::{prelude::Just, strategy::Strategy};
772 use std::path::PathBuf;
773
774 fn sentinel(runner: &mut TestRunner) -> u64 {
775 runner.rng().random()
776 }
777
778 fn forced_weights(kind: usize) -> FuzzCorpusMutationWeights {
779 let mut weights = FuzzCorpusMutationWeights {
780 mutation_weight_splice: 0,
781 mutation_weight_repeat: 0,
782 mutation_weight_interleave: 0,
783 mutation_weight_prefix: 0,
784 mutation_weight_suffix: 0,
785 mutation_weight_abi: 0,
786 mutation_weight_cmp: 0,
787 };
788 match kind {
789 0 => weights.mutation_weight_splice = 1,
790 1 => weights.mutation_weight_repeat = 1,
791 2 => weights.mutation_weight_interleave = 1,
792 3 => weights.mutation_weight_prefix = 1,
793 4 => weights.mutation_weight_suffix = 1,
794 5 => weights.mutation_weight_abi = 1,
795 _ => weights.mutation_weight_cmp = 1,
796 }
797 weights
798 }
799
800 fn tx(sender: u8) -> BasicTxDetails {
801 BasicTxDetails {
802 warp: Some(U256::from(sender)),
803 roll: Some(U256::from(sender + 1)),
804 sender: Address::with_last_byte(sender),
805 call_details: CallDetails {
806 target: Address::with_last_byte(10),
807 calldata: Bytes::from(vec![sender]),
808 value: Some(U256::from(sender)),
809 },
810 }
811 }
812
813 fn state() -> FuzzState {
814 EvmFuzzState::new(&[], &InMemoryDB::default(), FuzzDictionaryConfig::default(), None)
815 .stateless_worker()
816 }
817
818 fn generator_tx(sender: u8) -> TxGenerator {
819 TxGenerator::from_strategy(Just(tx(sender)).boxed())
820 }
821
822 fn config() -> FuzzCorpusConfig {
823 FuzzCorpusConfig { corpus_dir: Some(PathBuf::from("corpus")), ..Default::default() }
824 }
825
826 #[test]
827 fn prefix_and_suffix_handle_sequence_edges() {
828 let sequence = vec![tx(1), tx(2), tx(3)];
829 assert_eq!(SequenceMutator::prefix(&sequence, Vec::new())[0].sender, sequence[0].sender);
830 assert_eq!(SequenceMutator::suffix(&sequence, Vec::new())[2].sender, sequence[2].sender);
831 assert_eq!(
832 SequenceMutator::prefix(&sequence, vec![tx(9), tx(8), tx(7)])[2].sender,
833 tx(7).sender
834 );
835 assert_eq!(SequenceMutator::suffix(&sequence, vec![tx(9)])[0].warp, sequence[0].warp);
836 }
837
838 #[test]
839 fn splice_retains_singleton_entries() {
840 let mut runner = TestRunner::deterministic();
841 let result = SequenceMutator::splice(&[tx(1)], &[tx(2)], &mut runner);
842
843 assert_eq!(
844 result.iter().map(|tx| tx.sender).collect::<Vec<_>>(),
845 [tx(1).sender, tx(2).sender]
846 );
847 }
848
849 #[test]
850 fn splice_can_select_final_transactions() {
851 let first = [tx(1), tx(2)];
852 let second = [tx(3), tx(4)];
853 let mut runner = TestRunner::deterministic();
854 let mut selected_first_final = false;
855 let mut selected_second_final = false;
856
857 for _ in 0..1000 {
858 let result = SequenceMutator::splice(&first, &second, &mut runner);
859 selected_first_final |= result.iter().any(|tx| tx.sender == first[1].sender);
860 selected_second_final |= result.iter().any(|tx| tx.sender == second[1].sender);
861 }
862
863 assert!(selected_first_final, "splice never selected the first entry's final transaction");
864 assert!(
865 selected_second_final,
866 "splice never selected the second entry's final transaction"
867 );
868 }
869
870 #[test]
871 fn repeat_can_replace_final_transaction() {
872 let sequence = [tx(1), tx(2)];
873 let mut runner = TestRunner::deterministic();
874 let mut replaced_final = false;
875
876 for _ in 0..1000 {
877 let result = SequenceMutator::repeat(&sequence, &mut runner);
878 replaced_final |= result[1].sender != sequence[1].sender;
879 }
880
881 assert!(replaced_final, "repeat never replaced the final transaction");
882 }
883
884 #[test]
885 fn cmp_mutation_replaces_operand_and_retains_metadata() {
886 let function = Function::parse("testCmp(uint256)").unwrap();
887 let mut input = tx(7);
888 input.call_details.calldata =
889 function.abi_encode_input(&[DynSolValue::Uint(U256::from(7), 256)]).unwrap().into();
890 let metadata = (input.warp, input.roll, input.sender, input.call_details.value);
891 let mut runner = TestRunner::default();
892
893 assert!(
894 SequenceMutator::cmp_mutate(
895 &mut input,
896 &function,
897 &[ComparisonHint { lhs: U256::from(7), rhs: U256::from(42) }],
898 &mut runner,
899 &FuzzFixtures::default(),
900 )
901 .unwrap()
902 );
903 let decoded = function.abi_decode_input(&input.call_details.calldata[4..]).unwrap();
904 assert_eq!(decoded[0].as_uint().unwrap().0, U256::from(42));
905 assert_eq!((input.warp, input.roll, input.sender, input.call_details.value), metadata);
906 }
907
908 #[test]
909 fn abi_mutation_keeps_undecodable_calldata() {
910 let function = Function::parse("test(uint256)").unwrap();
911 let mut input = tx(1);
912 input.call_details.calldata = function.selector().to_vec().into();
913 let calldata = input.call_details.calldata.clone();
914
915 SequenceMutator::abi_mutate(
916 &mut input,
917 &function,
918 &mut TestRunner::deterministic(),
919 &state(),
920 &FuzzFixtures::default(),
921 0,
922 )
923 .unwrap();
924 assert_eq!(input.call_details.calldata, calldata);
925 }
926
927 #[test]
928 fn cmp_mutation_rejects_dirty_value_words() {
929 let mut runner = TestRunner::deterministic();
930 for (signature, value, lhs, rhs) in [
931 ("test(bool)", DynSolValue::Bool(true), U256::from(1), U256::from(4)),
932 ("test(bool)", DynSolValue::Bool(false), U256::ZERO, U256::from(4)),
933 (
934 "test(bool[2])",
935 DynSolValue::FixedArray(vec![DynSolValue::Bool(false); 2]),
936 U256::ZERO,
937 U256::from(4),
938 ),
939 ("test(uint8)", DynSolValue::Uint(U256::from(7), 8), U256::from(7), U256::from(0x107)),
940 (
941 "test(address)",
942 DynSolValue::Address(Address::with_last_byte(1)),
943 U256::from(1),
944 (U256::from(1) << 160) | U256::from(1),
945 ),
946 ] {
947 let function = Function::parse(signature).unwrap();
948 let original = function.abi_encode_input(&[value]).unwrap();
949 let mut input = tx(7);
950 input.call_details.calldata = original.clone().into();
951 for _ in 0..100 {
952 assert!(
953 !SequenceMutator::cmp_mutate(
954 &mut input,
955 &function,
956 &[ComparisonHint { lhs, rhs }],
957 &mut runner,
958 &FuzzFixtures::default(),
959 )
960 .unwrap(),
961 "{signature}"
962 );
963 assert_eq!(input.call_details.calldata.as_ref(), original);
964 }
965 }
966 }
967
968 #[test]
969 fn cmp_mutation_accepts_values_solidity_accepts() {
970 let mut runner = TestRunner::deterministic();
971 let encode = |signature, value| {
972 Function::parse(signature).unwrap().abi_encode_input(&[value]).unwrap()
973 };
974 let replace_byte = |mut calldata: Vec<u8>, index: usize, byte| {
975 calldata[index] = byte;
976 calldata
977 };
978 let bytes = encode("test(bytes)", DynSolValue::Bytes(vec![0xaa; 40]));
979 let string = encode("test(string)", DynSolValue::String("abcd".into()));
980 for (signature, original, lhs, rhs, expected) in [
981 (
982 "test(bool)",
983 encode("test(bool)", DynSolValue::Bool(false)),
984 U256::ZERO,
985 U256::from(1),
986 encode("test(bool)", DynSolValue::Bool(true)),
987 ),
988 (
989 "test(int8)",
990 encode("test(int8)", DynSolValue::Int(I256::ZERO, 8)),
991 U256::ZERO,
992 U256::MAX,
993 encode("test(int8)", DynSolValue::Int(I256::MINUS_ONE, 8)),
994 ),
995 (
997 "test(bytes)",
998 bytes.clone(),
999 U256::from(40),
1000 U256::from(5),
1001 replace_byte(bytes, 67, 5),
1002 ),
1003 (
1005 "test(string)",
1006 string.clone(),
1007 U256::from(0x61),
1008 U256::from(0xff),
1009 replace_byte(string, 68, 0xff),
1010 ),
1011 ] {
1012 let function = Function::parse(signature).unwrap();
1013 let mut input = tx(7);
1014 input.call_details.calldata = original.into();
1015 assert!(
1016 SequenceMutator::cmp_mutate(
1017 &mut input,
1018 &function,
1019 &[ComparisonHint { lhs, rhs }],
1020 &mut runner,
1021 &FuzzFixtures::default(),
1022 )
1023 .unwrap(),
1024 "{signature}"
1025 );
1026 assert_eq!(input.call_details.calldata.as_ref(), expected, "{signature}");
1027 }
1028 }
1029
1030 #[test]
1031 fn stateless_fresh_and_disabled_mutators_generate_one_transaction() {
1032 let function = Function::parse("test(uint256)").unwrap();
1033 let corpus_tx = tx(1);
1034 let corpus = [CorpusEntryView::new(std::slice::from_ref(&corpus_tx), &[]).unwrap()];
1035 for disable_mutators in [false, true] {
1036 let mut config = config();
1037 config.corpus_random_sequence_weight = if disable_mutators { 0 } else { 100 };
1038 if disable_mutators {
1039 config.mutation_weights.mutation_weight_abi = 0;
1040 config.mutation_weights.mutation_weight_cmp = 0;
1041 }
1042 let generator =
1043 SequenceGenerator::stateless(generator_tx(9), state(), function.clone(), &config)
1044 .unwrap();
1045 let plan = generator
1046 .start(&mut TestRunner::default(), corpus.len(), |i| Ok(corpus[i]), true)
1047 .unwrap();
1048 assert_eq!(plan.initial().len(), 1);
1049 assert_eq!(plan.initial()[0].sender, tx(9).sender);
1050 assert_eq!(plan.initial()[0].call_details.value, tx(9).call_details.value);
1051 assert_eq!(plan.source(), None);
1052 }
1053 }
1054
1055 #[test]
1056 fn sequence_plan_continues_corpus_or_generates_when_unavailable() {
1057 let mut config = config();
1058 config.corpus_random_sequence_weight = 0;
1059 config.mutation_weights.mutation_weight_splice = 1;
1060 config.mutation_weights.mutation_weight_repeat = 0;
1061 config.mutation_weights.mutation_weight_interleave = 0;
1062 config.mutation_weights.mutation_weight_prefix = 0;
1063 config.mutation_weights.mutation_weight_suffix = 0;
1064 config.mutation_weights.mutation_weight_abi = 0;
1065 config.mutation_weights.mutation_weight_cmp = 0;
1066 let targets = FuzzRunIdentifiedContracts::new(TargetedContracts::new(), false);
1067 let generator =
1068 SequenceGenerator::invariant(generator_tx(9), state(), targets, &config).unwrap();
1069 let mut runner = TestRunner::default();
1070 let plan = SequencePlan {
1071 initial: InitialSequence::Multiple(vec![tx(1), tx(2)]),
1072 continuation: generator.continuation(),
1073 tx: generator.tx,
1074 source: Some(0),
1075 };
1076
1077 assert_eq!(plan.next(&mut runner, false, 1).unwrap().sender, tx(2).sender);
1078 assert_eq!(plan.next(&mut runner, true, 1).unwrap().sender, tx(9).sender);
1079 assert_eq!(plan.next(&mut runner, false, 2).unwrap().sender, tx(9).sender);
1080 }
1081
1082 #[test]
1083 fn continuation_preserves_gate_draw_order() {
1084 for (fresh_weight, discarded, depth, expected_sender, draws_gate) in [
1085 (0, false, 1, 2, false),
1086 (100, false, 1, 9, true),
1087 (50, false, 2, 9, true),
1088 (50, true, 1, 9, false),
1089 ] {
1090 let plan = SequencePlan {
1091 initial: InitialSequence::Multiple(vec![tx(1), tx(2)]),
1092 tx: generator_tx(9),
1093 continuation: Continuation::Initial { fresh_weight },
1094 source: Some(0),
1095 };
1096 let mut actual = TestRunner::deterministic();
1097 let mut reference = TestRunner::deterministic();
1098 if draws_gate {
1099 let _ = reference.rng().random_ratio(fresh_weight, 100);
1100 }
1101 assert_eq!(
1102 plan.next(&mut actual, discarded, depth).unwrap().sender,
1103 tx(expected_sender).sender
1104 );
1105 assert_eq!(sentinel(&mut actual), sentinel(&mut reference));
1106 }
1107 }
1108
1109 #[test]
1110 fn forced_invariant_mutations_preserve_old_selection_draws() {
1111 let sequences = [vec![tx(1), tx(2), tx(3)], vec![tx(4), tx(5), tx(6)]];
1112 let entries = sequences
1113 .iter()
1114 .map(|sequence| CorpusEntryView::new(sequence, &[]).unwrap())
1115 .collect::<Vec<_>>();
1116 for kind in 0..7 {
1117 let mut config = config();
1118 config.mutation_weights = forced_weights(kind);
1119 let generator = SequenceGenerator::invariant(
1120 generator_tx(9),
1121 state(),
1122 FuzzRunIdentifiedContracts::new(TargetedContracts::new(), false),
1123 &config,
1124 )
1125 .unwrap();
1126 let mut actual = TestRunner::deterministic();
1127 let mut reference = TestRunner::deterministic();
1128
1129 let distribution = WeightedIndex::new(
1133 [kind == 0, kind == 1, kind == 2, kind == 3, kind == 4, kind == 5, kind == 6]
1134 .map(u32::from),
1135 )
1136 .unwrap();
1137 assert_eq!(distribution.sample(reference.rng()), kind);
1138 let a = reference.rng().random_range(0..entries.len());
1139 let b = reference.rng().random_range(0..entries.len());
1140 let source = match kind {
1141 0 | 2 => a,
1142 _ => {
1143 if reference.rng().random() {
1144 a
1145 } else {
1146 b
1147 }
1148 }
1149 };
1150 if kind >= 5 {
1152 let _ = reference.rng().random_range(0..entries[source].transactions.len());
1153 }
1154
1155 let plan =
1156 generator.start(&mut actual, entries.len(), |i| Ok(entries[i]), true).unwrap();
1157 assert_eq!(plan.source(), Some(source), "mutation family {kind}");
1158 if kind >= 5 {
1162 assert_eq!(
1163 sentinel(&mut actual),
1164 sentinel(&mut reference),
1165 "mutation family {kind}"
1166 );
1167 }
1168 }
1169 }
1170
1171 #[test]
1172 fn stateless_plan_never_exposes_continuation() {
1173 let generator = SequenceGenerator::stateless(
1174 generator_tx(9),
1175 state(),
1176 Function::parse("test()").unwrap(),
1177 &config(),
1178 )
1179 .unwrap();
1180 let plan = generator
1181 .start(&mut TestRunner::deterministic(), 0, |_| unreachable!(), false)
1182 .unwrap();
1183 assert!(plan.next(&mut TestRunner::deterministic(), false, 0).is_err());
1184 }
1185
1186 #[test]
1187 fn overflowing_effective_mutation_weight_is_rejected() {
1188 let mut config = config();
1189 config.mutation_weights.mutation_weight_splice = u32::MAX;
1190 config.mutation_weights.mutation_weight_repeat = 1;
1191 assert!(
1192 SequenceGenerator::stateless(
1193 generator_tx(1),
1194 state(),
1195 Function::parse("test()").unwrap(),
1196 &config,
1197 )
1198 .is_err()
1199 );
1200 }
1201
1202 #[test]
1203 fn invariant_cmp_only_does_not_fallback_to_abi() {
1204 let target = Address::with_last_byte(42);
1205 let function = Function::parse("test(uint256)").unwrap();
1206 let mut abi = JsonAbi::new();
1207 abi.functions.entry(function.name.clone()).or_default().push(function.clone());
1208 let mut contracts = TargetedContracts::new();
1209 contracts.insert(target, TargetedContract::new("Target".into(), abi));
1210 let mut original = tx(1);
1211 original.call_details.target = target;
1212 original.call_details.calldata =
1213 function.abi_encode_input(&[DynSolValue::Uint(U256::from(7), 256)]).unwrap().into();
1214 let sequence = [original.clone()];
1215 let corpus = [CorpusEntryView::new(&sequence, &[]).unwrap()];
1216 let mut config = config();
1217 config.mutation_weights = FuzzCorpusMutationWeights {
1218 mutation_weight_splice: 0,
1219 mutation_weight_repeat: 0,
1220 mutation_weight_interleave: 0,
1221 mutation_weight_prefix: 0,
1222 mutation_weight_suffix: 0,
1223 mutation_weight_abi: 0,
1224 mutation_weight_cmp: 1,
1225 };
1226 let generator = SequenceGenerator::invariant(
1227 generator_tx(9),
1228 state(),
1229 FuzzRunIdentifiedContracts::new(contracts, false),
1230 &config,
1231 )
1232 .unwrap();
1233 let plan = generator
1234 .start(&mut TestRunner::default(), corpus.len(), |i| Ok(corpus[i]), true)
1235 .unwrap();
1236 assert_eq!(plan.initial()[0].call_details.calldata, original.call_details.calldata);
1237 }
1238
1239 #[test]
1240 fn malformed_corpus_views_are_rejected_without_panicking() {
1241 assert!(CorpusEntryView::new(&[], &[]).is_err());
1242 let sequence = [tx(1)];
1243 let comparisons = [Vec::new(), Vec::new()];
1244 assert!(CorpusEntryView::new(&sequence, &comparisons).is_err());
1245
1246 let generator = SequenceGenerator::stateless(
1247 generator_tx(9),
1248 state(),
1249 Function::parse("test(uint256)").unwrap(),
1250 &config(),
1251 )
1252 .unwrap();
1253 let result = generator.start(
1254 &mut TestRunner::deterministic(),
1255 1,
1256 |_| CorpusEntryView::new(&[], &[]),
1257 true,
1258 );
1259 assert!(result.is_err());
1260 }
1261
1262 #[test]
1263 fn start_accesses_at_most_two_corpus_entries() {
1264 let mut config = config();
1265 config.mutation_weights.mutation_weight_splice = 1;
1266 config.mutation_weights.mutation_weight_repeat = 0;
1267 config.mutation_weights.mutation_weight_interleave = 0;
1268 config.mutation_weights.mutation_weight_prefix = 0;
1269 config.mutation_weights.mutation_weight_suffix = 0;
1270 config.mutation_weights.mutation_weight_abi = 0;
1271 config.mutation_weights.mutation_weight_cmp = 0;
1272 let generator = SequenceGenerator::invariant(
1273 generator_tx(9),
1274 state(),
1275 FuzzRunIdentifiedContracts::new(TargetedContracts::new(), false),
1276 &config,
1277 )
1278 .unwrap();
1279 let sequence = [tx(1)];
1280 let mut accesses = 0;
1281 generator
1282 .start(
1283 &mut TestRunner::deterministic(),
1284 10_000,
1285 |_| {
1286 accesses += 1;
1287 CorpusEntryView::new(&sequence, &[])
1288 },
1289 true,
1290 )
1291 .unwrap();
1292 assert_eq!(accesses, 2);
1293 }
1294
1295 #[test]
1296 fn applicable_hints_dedup_and_drop_operands_missing_from_calldata() {
1297 let function = Function::parse("testCmp(uint256)").unwrap();
1298 let calldata = function.abi_encode_input(&[DynSolValue::Uint(U256::from(7), 256)]).unwrap();
1299 let hint =
1300 |lhs: u64, rhs: u64| ComparisonHint { lhs: U256::from(lhs), rhs: U256::from(rhs) };
1301
1302 let hints = [hint(7, 42), hint(1000, 2000), hint(7, 42), hint(5, 5), hint(42, 7)];
1303 let applicable = ComparisonHint::applicable(&calldata, hints);
1304 assert_eq!(applicable, [hint(7, 42), hint(42, 7)]);
1305 for hint in hints {
1306 let mut input = tx(7);
1307 input.call_details.calldata = calldata.clone().into();
1308 let mutated = SequenceMutator::cmp_mutate(
1309 &mut input,
1310 &function,
1311 &[hint],
1312 &mut TestRunner::default(),
1313 &FuzzFixtures::default(),
1314 )
1315 .unwrap();
1316 assert_eq!(mutated, applicable.contains(&hint));
1317 }
1318 }
1319
1320 #[test]
1321 fn applicable_hints_match_per_hint_filter() {
1322 fn word(rng: &mut impl Rng, bytes: &[u8]) -> U256 {
1323 let mut word = [0u8; 32];
1324 let start = 32 - rng.random_range(0..=bytes.len().min(32));
1325 word[start..].copy_from_slice(&bytes[..32 - start]);
1326 U256::from_be_bytes(word)
1327 }
1328
1329 let mut runner = TestRunner::deterministic();
1330 let rng = runner.rng();
1331 let (mut kept, mut dropped) = (0, 0);
1332 for _ in 0..1000 {
1333 let len = rng.random_range(0..100);
1335 let calldata = (0..len).map(|_| rng.random_range(0..3u8)).collect::<Vec<_>>();
1336 let hints = (0..rng.random_range(0..16))
1337 .map(|_| {
1338 let random = (0..32).map(|_| rng.random_range(0..3u8)).collect::<Vec<_>>();
1339 let start = rng.random_range(0..=calldata.len());
1340 let lhs = word(rng, &random);
1341 let rhs = word(rng, &calldata[start..]);
1342 if rng.random() {
1343 ComparisonHint { lhs, rhs }
1344 } else {
1345 ComparisonHint { lhs: rhs, rhs: lhs }
1346 }
1347 })
1348 .collect::<Vec<_>>();
1349 let mut seen = HashSet::<ComparisonHint>::default();
1350 let expected = hints
1351 .iter()
1352 .copied()
1353 .filter(|hint| seen.insert(*hint) && hint.applies_to(&calldata))
1354 .collect::<Vec<_>>();
1355 kept += expected.len();
1356 dropped += seen.len() - expected.len();
1357 assert_eq!(ComparisonHint::applicable(&calldata, hints), expected);
1358 }
1359 assert!(kept > 1000 && dropped > 500, "kept {kept}, dropped {dropped}");
1360 }
1361}