foundry_evm/inspectors/
edge_cov.rs

1use alloy_primitives::{
2    Address, U256,
3    map::{DefaultHashBuilder, HashMap},
4};
5use core::{
6    fmt,
7    hash::{BuildHasher, Hash, Hasher},
8};
9use revm::{
10    Inspector,
11    bytecode::opcode,
12    context::{ContextTr, JournalTr},
13    interpreter::{
14        Interpreter,
15        interpreter_types::{InputsTr, Jumps},
16    },
17};
18
19// Default capacity for the hitcount buffer.
20pub(crate) const MAX_EDGE_COUNT: usize = 65536;
21
22// Maximum number of unique comparison sites to track for CmpLog-style feedback.
23const MAX_CMP_LOG_SITES: usize = 1024;
24
25// Maximum number of comparison operand pairs to track per site. This matches the downstream loop
26// detection threshold so a hot loop can be classified without filling the whole log.
27const MAX_CMP_OBSERVATIONS_PER_SITE: u8 = 8;
28
29/// Edge coverage collection kind.
30#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
31pub enum EdgeCovKind {
32    /// Assign dense monotonically-increasing indices to unique edges.
33    #[default]
34    CollisionFree,
35    /// Preserve the legacy fixed-size hash ID calculation.
36    Hash,
37}
38
39/// Configuration for [`EdgeCovInspector`].
40#[derive(Clone, Copy, Debug, Eq, PartialEq)]
41pub struct EdgeCovConfig {
42    /// Which edge coverage representation should be collected.
43    pub kind: EdgeCovKind,
44    /// Whether call-frame depth should be included in the edge identity.
45    pub include_call_depth: bool,
46}
47
48impl EdgeCovConfig {
49    /// Creates a new edge coverage configuration.
50    pub const fn new(kind: EdgeCovKind, include_call_depth: bool) -> Self {
51        Self { kind, include_call_depth }
52    }
53
54    /// Legacy fixed-size hash ID configuration.
55    pub const fn legacy_hash_ids() -> Self {
56        Self::new(EdgeCovKind::Hash, false)
57    }
58}
59
60impl Default for EdgeCovConfig {
61    fn default() -> Self {
62        Self::new(EdgeCovKind::CollisionFree, false)
63    }
64}
65
66impl From<&foundry_config::FuzzCorpusConfig> for EdgeCovConfig {
67    fn from(corpus: &foundry_config::FuzzCorpusConfig) -> Self {
68        let kind = if corpus.evm_edge_coverage_collision_free() {
69            EdgeCovKind::CollisionFree
70        } else {
71            EdgeCovKind::Hash
72        };
73        Self::new(kind, corpus.evm_edge_coverage_include_call_depth())
74    }
75}
76
77/// A comparison operand pair captured during execution.
78#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
79pub struct CmpOperands {
80    /// First operand of the comparison.
81    pub op1: U256,
82    /// Second operand of the comparison.
83    pub op2: U256,
84    /// Program counter where the comparison occurred.
85    pub pc: usize,
86    /// Contract address where the comparison occurred.
87    pub address: Address,
88    /// EVM opcode that performed the comparison.
89    pub opcode: u8,
90}
91
92#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
93pub struct EdgeKey {
94    pub address: Address,
95    pub depth: Option<usize>,
96    pub pc: usize,
97    pub jump_dest: U256,
98}
99
100impl EdgeKey {
101    fn new(
102        address: Address,
103        depth: usize,
104        pc: usize,
105        jump_dest: U256,
106        include_depth: bool,
107    ) -> Self {
108        Self { address, depth: include_depth.then_some(depth), pc, jump_dest }
109    }
110}
111
112#[derive(Clone, Debug, Default)]
113pub struct EdgeIndexMap {
114    edge_indices: HashMap<EdgeKey, usize>,
115    next_index: usize,
116}
117
118impl EdgeIndexMap {
119    pub fn edge_index(&mut self, edge: EdgeKey) -> usize {
120        if let Some(index) = self.edge_indices.get(&edge) {
121            *index
122        } else {
123            let index = self.next_index;
124            self.next_index += 1;
125            self.edge_indices.insert(edge, index);
126            index
127        }
128    }
129
130    pub const fn edge_count(&self) -> usize {
131        self.next_index
132    }
133}
134
135#[derive(Clone, Copy, Debug, Eq, PartialEq)]
136pub struct EdgeCovHit {
137    pub edge: EdgeKey,
138    pub count: u8,
139}
140
141#[derive(Clone, Debug, Eq, PartialEq)]
142pub enum EdgeCoverage {
143    Hash(Vec<u8>),
144    CollisionFree(Vec<EdgeCovHit>),
145}
146
147impl EdgeCoverage {
148    pub fn is_empty(&self) -> bool {
149        match self {
150            Self::Hash(hitcount) => hitcount.iter().all(|&count| count == 0),
151            Self::CollisionFree(hits) => hits.is_empty(),
152        }
153    }
154}
155
156/// An `Inspector` that tracks [edge coverage](https://clang.llvm.org/docs/SanitizerCoverage.html#edge-coverage).
157/// Covered edges will not wrap to zero e.g. a loop edge hit more than 255 will still be retained.
158///
159/// Also tracks comparison operands for CmpLog-style guided fuzzing.
160// see https://github.com/AFLplusplus/AFLplusplus/blob/5777ceaf23f48ae4ceae60e4f3a79263802633c6/instrumentation/afl-llvm-pass.so.cc#L810-L829
161#[derive(Clone)]
162pub struct EdgeCovInspector {
163    /// Map of hitcounts that can be diffed against to determine if new coverage was reached.
164    hitcount: Vec<u8>,
165    /// Configuration for edge ID generation.
166    config: EdgeCovConfig,
167    /// Per-execution dense edge hitcounts. Stable IDs are assigned by the corpus history owner.
168    dense_hitcount: HashMap<EdgeKey, u8>,
169    hash_builder: DefaultHashBuilder,
170    /// Comparison operand log for CmpLog-style guided fuzzing.
171    cmp_log: Option<Vec<CmpOperands>>,
172    cmp_site_counts: HashMap<CmpSiteKey, u8>,
173}
174
175impl fmt::Debug for EdgeCovInspector {
176    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
177        f.debug_struct("EdgeCovInspector")
178            .field("capacity", &self.hitcount.len())
179            .field("edges", &self.edge_count())
180            .field("config", &self.config)
181            .finish()
182    }
183}
184
185impl EdgeCovInspector {
186    /// Create a new `EdgeCovInspector` with default configuration and capacity.
187    pub fn new() -> Self {
188        Self::with_config(EdgeCovConfig::default())
189    }
190
191    /// Create a new `EdgeCovInspector` with comparison operand logging enabled.
192    pub fn with_cmp_log() -> Self {
193        let mut inspector = Self::new();
194        inspector.enable_cmp_log(true);
195        inspector
196    }
197
198    /// Create a new `EdgeCovInspector` with the given configuration.
199    ///
200    /// [`EdgeCovKind::Hash`] preallocates a fixed-size bitmap;
201    /// [`EdgeCovKind::CollisionFree`] grows its dense map on demand.
202    pub fn with_config(config: EdgeCovConfig) -> Self {
203        let hitcount = match config.kind {
204            EdgeCovKind::Hash => vec![0; MAX_EDGE_COUNT],
205            EdgeCovKind::CollisionFree => Vec::new(),
206        };
207        Self {
208            hitcount,
209            config,
210            dense_hitcount: HashMap::default(),
211            hash_builder: DefaultHashBuilder::default(),
212            cmp_log: None,
213            cmp_site_counts: HashMap::default(),
214        }
215    }
216
217    /// Set whether to collect comparison operand logs.
218    pub fn enable_cmp_log(&mut self, yes: bool) {
219        if yes {
220            self.cmp_log.get_or_insert_with(|| Vec::with_capacity(MAX_CMP_LOG_SITES));
221        } else {
222            self.cmp_log = None;
223            self.cmp_site_counts.clear();
224        }
225    }
226
227    /// Reset the hitcount to zero and clear the comparison log.
228    pub fn reset(&mut self) {
229        match self.config.kind {
230            EdgeCovKind::CollisionFree => self.dense_hitcount.clear(),
231            EdgeCovKind::Hash => self.hitcount.fill(0),
232        }
233        if let Some(cmp_log) = &mut self.cmp_log {
234            cmp_log.clear();
235        }
236        self.cmp_site_counts.clear();
237    }
238
239    /// Get an immutable reference to the comparison operand log.
240    pub const fn get_cmp_log(&self) -> &[CmpOperands] {
241        match &self.cmp_log {
242            Some(cmp_log) => cmp_log.as_slice(),
243            None => &[],
244        }
245    }
246
247    /// Consume the inspector and take ownership of both the hitcount and comparison log.
248    pub fn into_parts(mut self) -> (EdgeCoverage, Vec<CmpOperands>) {
249        let cmp_log = self.cmp_log.take().unwrap_or_default();
250        (self.into(), cmp_log)
251    }
252
253    /// Number of unique collision-free edges discovered so far.
254    pub fn edge_count(&self) -> usize {
255        self.dense_hitcount.len()
256    }
257
258    /// Mark the edge `(address, depth, pc, jump_dest)` as hit.
259    fn store_hit(&mut self, address: Address, depth: usize, pc: usize, jump_dest: U256) {
260        let edge_id = match self.config.kind {
261            EdgeCovKind::CollisionFree => {
262                self.store_dense_hit(address, depth, pc, jump_dest);
263                return;
264            }
265            EdgeCovKind::Hash => self.hash_edge_id(address, depth, pc, jump_dest),
266        };
267        self.hitcount[edge_id] = self.hitcount[edge_id].wrapping_add(1).max(1);
268    }
269
270    fn store_dense_hit(&mut self, address: Address, depth: usize, pc: usize, jump_dest: U256) {
271        let key = EdgeKey::new(address, depth, pc, jump_dest, self.config.include_call_depth);
272        let count = self.dense_hitcount.entry(key).or_default();
273        *count = count.wrapping_add(1).max(1);
274    }
275
276    fn hash_edge_id(
277        &mut self,
278        address: Address,
279        depth: usize,
280        pc: usize,
281        jump_dest: U256,
282    ) -> usize {
283        let mut hasher = self.hash_builder.build_hasher();
284        address.hash(&mut hasher);
285        if self.config.include_call_depth {
286            depth.hash(&mut hasher);
287        }
288        pc.hash(&mut hasher);
289        jump_dest.hash(&mut hasher);
290        // The hash is used to index into the hitcount array,
291        // so it must be modulo the map size.
292        (hasher.finish() % self.hitcount.len() as u64) as usize
293    }
294
295    #[cfg(test)]
296    fn dense_hits(&self) -> Vec<EdgeCovHit> {
297        let mut hits = self
298            .dense_hitcount
299            .iter()
300            .map(|(&edge, &count)| EdgeCovHit { edge, count })
301            .collect::<Vec<_>>();
302        hits.sort_by_key(|hit| hit.edge);
303        hits
304    }
305
306    /// Store comparison operands for CmpLog-style guided fuzzing.
307    fn store_cmp(&mut self, cmp: CmpOperands) {
308        let Some(cmp_log) = &mut self.cmp_log else {
309            return;
310        };
311
312        let site = CmpSiteKey::new(&cmp);
313        if let Some(count) = self.cmp_site_counts.get_mut(&site) {
314            if *count >= MAX_CMP_OBSERVATIONS_PER_SITE {
315                return;
316            }
317            *count += 1;
318            cmp_log.push(cmp);
319        } else if self.cmp_site_counts.len() < MAX_CMP_LOG_SITES {
320            self.cmp_site_counts.insert(site, 1);
321            cmp_log.push(cmp);
322        }
323    }
324
325    #[cold]
326    fn do_step<CTX>(&mut self, interp: &mut Interpreter, context: &mut CTX)
327    where
328        CTX: ContextTr,
329    {
330        let address = interp.input.target_address();
331        let depth = context.journal_ref().depth();
332        let current_pc = interp.bytecode.pc();
333
334        match interp.bytecode.opcode() {
335            opcode::JUMP => {
336                // unconditional jump
337                if let Ok(jump_dest) = interp.stack.peek(0) {
338                    self.store_hit(address, depth, current_pc, jump_dest);
339                }
340            }
341            opcode::JUMPI => {
342                if let Ok(stack_value) = interp.stack.peek(1) {
343                    let jump_dest = if stack_value.is_zero() {
344                        // fall through
345                        Ok(U256::from(current_pc + 1))
346                    } else {
347                        // branch taken
348                        interp.stack.peek(0)
349                    };
350
351                    if let Ok(jump_dest) = jump_dest {
352                        self.store_hit(address, depth, current_pc, jump_dest);
353                    }
354                }
355            }
356            _ => {
357                // no-op
358            }
359        }
360    }
361
362    #[cold]
363    fn do_cmp_step(&mut self, interp: &mut Interpreter) {
364        if self.cmp_log.is_none() {
365            return;
366        }
367
368        let address = interp.input.target_address();
369        let current_pc = interp.bytecode.pc();
370
371        match interp.bytecode.opcode() {
372            op @ (opcode::EQ | opcode::LT | opcode::SLT | opcode::GT | opcode::SGT) => {
373                if let (Ok(op1), Ok(op2)) = (interp.stack.peek(0), interp.stack.peek(1)) {
374                    self.store_cmp(CmpOperands { op1, op2, pc: current_pc, address, opcode: op });
375                }
376            }
377            op @ opcode::ISZERO => {
378                if let Ok(op1) = interp.stack.peek(0) {
379                    self.store_cmp(CmpOperands {
380                        op1,
381                        op2: U256::ZERO,
382                        pc: current_pc,
383                        address,
384                        opcode: op,
385                    });
386                }
387            }
388            _ => {}
389        }
390    }
391}
392
393impl Default for EdgeCovInspector {
394    fn default() -> Self {
395        Self::new()
396    }
397}
398
399impl From<EdgeCovInspector> for EdgeCoverage {
400    fn from(inspector: EdgeCovInspector) -> Self {
401        let EdgeCovInspector { hitcount, config, dense_hitcount, .. } = inspector;
402        match config.kind {
403            // Hits are deliberately not sorted here — this is the per-call drain
404            // path and `merge_edge_coverage` doesn't care about order. Consumers
405            // that need a deterministic order (e.g. `snapshot_edge_fingerprint`)
406            // sort locally.
407            EdgeCovKind::CollisionFree => Self::CollisionFree(
408                dense_hitcount
409                    .into_iter()
410                    .map(|(edge, count)| EdgeCovHit { edge, count })
411                    .collect(),
412            ),
413            EdgeCovKind::Hash => Self::Hash(hitcount),
414        }
415    }
416}
417
418impl<CTX> Inspector<CTX> for EdgeCovInspector
419where
420    CTX: ContextTr,
421{
422    #[inline]
423    fn step(&mut self, interp: &mut Interpreter, context: &mut CTX) {
424        let op = interp.bytecode.opcode();
425        if matches!(op, opcode::JUMP | opcode::JUMPI) {
426            self.do_step(interp, context);
427        }
428        if self.cmp_log.is_some()
429            && matches!(
430                op,
431                opcode::EQ | opcode::LT | opcode::GT | opcode::SLT | opcode::SGT | opcode::ISZERO
432            )
433        {
434            self.do_cmp_step(interp);
435        }
436    }
437}
438
439#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
440struct CmpSiteKey {
441    address: Address,
442    pc: usize,
443    opcode: u8,
444}
445
446impl CmpSiteKey {
447    const fn new(cmp: &CmpOperands) -> Self {
448        Self { address: cmp.address, pc: cmp.pc, opcode: cmp.opcode }
449    }
450}
451
452#[cfg(test)]
453mod tests {
454    use super::*;
455
456    fn dense_counts(inspector: &EdgeCovInspector) -> Vec<u8> {
457        inspector.dense_hits().into_iter().map(|hit| hit.count).collect()
458    }
459
460    #[test]
461    fn cmp_operands_defaults_and_clones() {
462        let cmp = CmpOperands {
463            op1: U256::from(123),
464            op2: U256::from(456),
465            pc: 42,
466            address: Address::repeat_byte(0xaa),
467            opcode: opcode::EQ,
468        };
469
470        assert_eq!(cmp.op1, U256::from(123));
471        assert_eq!(cmp.op2, U256::from(456));
472        assert_eq!(cmp.pc, 42);
473
474        assert_eq!(CmpOperands::default(), CmpOperands::default());
475        let cloned = cmp;
476        assert_eq!(cloned, cmp);
477    }
478
479    #[test]
480    fn cmp_log_starts_empty_and_is_returned_by_into_parts() {
481        let inspector = EdgeCovInspector::new();
482
483        assert!(inspector.get_cmp_log().is_empty());
484
485        let (coverage, cmp_log) = inspector.into_parts();
486        assert_eq!(coverage, EdgeCoverage::CollisionFree(Vec::new()));
487        assert!(cmp_log.is_empty());
488    }
489
490    #[test]
491    fn collision_free_ids() {
492        let mut inspector = EdgeCovInspector::new();
493        let addr = Address::ZERO;
494
495        inspector.store_hit(addr, 0, 0, U256::from(10));
496        inspector.store_hit(addr, 0, 0, U256::from(20));
497        inspector.store_hit(addr, 0, 1, U256::from(10));
498
499        assert_eq!(inspector.edge_count(), 3);
500        assert_eq!(dense_counts(&inspector), [1, 1, 1]);
501    }
502
503    #[test]
504    fn same_edge_increments_same_dense_slot() {
505        let mut inspector = EdgeCovInspector::new();
506        let addr = Address::ZERO;
507
508        for _ in 0..5 {
509            inspector.store_hit(addr, 0, 42, U256::from(100));
510        }
511
512        assert_eq!(inspector.edge_count(), 1);
513        assert_eq!(dense_counts(&inspector), [5]);
514    }
515
516    #[test]
517    fn edge_index_map_keeps_indices_stable() {
518        let addr = Address::ZERO;
519        let mut indices = EdgeIndexMap::default();
520        let first = EdgeKey::new(addr, 0, 0, U256::from(10), false);
521        let second = EdgeKey::new(addr, 0, 0, U256::from(20), false);
522
523        assert_eq!(indices.edge_index(first), 0);
524        assert_eq!(indices.edge_index(second), 1);
525        assert_eq!(indices.edge_index(first), 0);
526        assert_eq!(indices.edge_count(), 2);
527    }
528
529    #[test]
530    fn hitcount_neverzero_on_wrap() {
531        let mut inspector = EdgeCovInspector::new();
532        let addr = Address::ZERO;
533
534        for _ in 0..256 {
535            inspector.store_hit(addr, 0, 0, U256::from(1));
536        }
537
538        assert_eq!(inspector.edge_count(), 1);
539        assert_eq!(dense_counts(&inspector), [1]);
540    }
541
542    #[test]
543    fn reset_clears_dense_hitcounts() {
544        let mut inspector = EdgeCovInspector::new();
545        let addr = Address::ZERO;
546
547        inspector.store_hit(addr, 0, 0, U256::from(1));
548        inspector.store_hit(addr, 0, 0, U256::from(2));
549        assert_eq!(inspector.edge_count(), 2);
550        assert_eq!(dense_counts(&inspector), [1, 1]);
551
552        inspector.reset();
553        assert_eq!(inspector.edge_count(), 0);
554        assert!(inspector.dense_hits().is_empty());
555
556        inspector.store_hit(addr, 0, 0, U256::from(1));
557        assert_eq!(inspector.edge_count(), 1);
558        assert_eq!(dense_counts(&inspector), [1]);
559    }
560
561    #[test]
562    fn legacy_hash_ids_match_old_calculation() {
563        let mut inspector = EdgeCovInspector::with_config(EdgeCovConfig::legacy_hash_ids());
564        let addr = Address::ZERO;
565        let pc = 42;
566        let jump_dest = U256::from(100);
567
568        let mut hasher = inspector.hash_builder.build_hasher();
569        addr.hash(&mut hasher);
570        pc.hash(&mut hasher);
571        jump_dest.hash(&mut hasher);
572        let expected_id = (hasher.finish() % MAX_EDGE_COUNT as u64) as usize;
573
574        inspector.store_hit(addr, 0, pc, jump_dest);
575
576        assert_eq!(inspector.hitcount[expected_id], 1);
577        assert_eq!(inspector.hitcount.iter().filter(|&&count| count != 0).count(), 1);
578    }
579
580    #[test]
581    fn call_depth_option_delineates_same_edge() {
582        let addr = Address::ZERO;
583
584        let mut without_depth = EdgeCovInspector::new();
585        without_depth.store_hit(addr, 0, 0, U256::from(1));
586        without_depth.store_hit(addr, 1, 0, U256::from(1));
587        assert_eq!(without_depth.edge_count(), 1);
588        assert_eq!(dense_counts(&without_depth), [2]);
589
590        let mut with_depth =
591            EdgeCovInspector::with_config(EdgeCovConfig::new(EdgeCovKind::CollisionFree, true));
592        with_depth.store_hit(addr, 0, 0, U256::from(1));
593        with_depth.store_hit(addr, 1, 0, U256::from(1));
594        assert_eq!(with_depth.edge_count(), 2);
595        assert_eq!(dense_counts(&with_depth), [1, 1]);
596    }
597
598    #[test]
599    fn reset_clears_hitcount_and_cmp_log() {
600        let mut inspector = EdgeCovInspector::with_cmp_log();
601
602        inspector.store_hit(Address::ZERO, 0, 0, U256::from(1));
603        inspector.store_cmp(CmpOperands {
604            op1: U256::from(123),
605            op2: U256::from(456),
606            pc: 42,
607            address: Address::ZERO,
608            opcode: opcode::EQ,
609        });
610
611        inspector.reset();
612
613        assert!(inspector.dense_hits().is_empty());
614        assert!(inspector.get_cmp_log().is_empty());
615    }
616
617    #[test]
618    fn cmp_log_is_capped_per_site() {
619        let mut inspector = EdgeCovInspector::with_cmp_log();
620
621        for i in 0..usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) + 1 {
622            inspector.store_cmp(CmpOperands {
623                op1: U256::from(i),
624                op2: U256::from(i + 1),
625                pc: 42,
626                address: Address::ZERO,
627                opcode: opcode::EQ,
628            });
629        }
630
631        assert_eq!(inspector.get_cmp_log().len(), usize::from(MAX_CMP_OBSERVATIONS_PER_SITE));
632    }
633
634    #[test]
635    fn cmp_log_caps_sites_without_starving_later_observations() {
636        let mut inspector = EdgeCovInspector::with_cmp_log();
637
638        for i in 0..usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) * 2 {
639            inspector.store_cmp(CmpOperands {
640                op1: U256::from(i),
641                op2: U256::from(i + 1),
642                pc: 1,
643                address: Address::ZERO,
644                opcode: opcode::EQ,
645            });
646        }
647        inspector.store_cmp(CmpOperands {
648            op1: U256::from(123),
649            op2: U256::from(456),
650            pc: 2,
651            address: Address::ZERO,
652            opcode: opcode::EQ,
653        });
654
655        assert_eq!(inspector.get_cmp_log().len(), usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) + 1);
656        assert_eq!(inspector.get_cmp_log().last().unwrap().pc, 2);
657    }
658}
foundry_evm/inspectors/edge_cov.rs

foundry_evm/inspectors/
edge_cov.rs
