Skip to main content

foundry_evm_core/
edgecov.rs

1//! Compiler-instrumented edge coverage and comparison logging through the `EDGECOV` and `CMPLOG`
2//! opcodes.
3//!
4//! Coverage builds of a compiler emit `PUSHn <id>; EDGECOV` on every control-flow edge and
5//! `PUSHn <site << 8 | cmp opcode>; CMPLOG` right before every `EQ`, `LT`, `GT`, `SLT` and `SGT`.
6//! Both opcodes are otherwise undefined. Foundry's EVMs carry them in their opcode tables, but
7//! they fail as undefined opcodes unless an [`EdgeCovGuard`] is alive on the thread.
8//!
9//! While it is, `EDGECOV` pops the edge ID and bumps its AFL NeverZero hit counter, and `CMPLOG`
10//! pops its tag and records the two words below it, the operands of the comparison that follows.
11//! Both refund the 3 gas of the `PUSH` the compiler emits before them, so a probe costs no gas
12//! once it ran. Hits and operands are kept per thread in dense tables indexed by ID, and taken
13//! once the call ends.
14
15use alloy_primitives::{Address, U256};
16use evm2::{
17    EvmConfig, EvmTypesHost, ExecutionConfig, OpcodeConfig, SpecId, Version,
18    interpreter::{InstrStop, op},
19};
20use evm2_macros::instruction;
21use std::{cell::UnsafeCell, marker::PhantomData};
22
23/// The `EDGECOV` opcode byte.
24const EDGECOV: u8 = 0xC0;
25
26/// The `CMPLOG` opcode byte.
27const CMPLOG: u8 = 0xC1;
28
29/// Gas of the `PUSHn` that precedes every `EDGECOV` or `CMPLOG`, refunded by the instruction.
30const PUSH_GAS: u64 = 3;
31
32/// Largest edge or comparison site ID that is recorded. IDs are dense from 1, so anything above
33/// this is malformed instrumentation and is ignored instead of growing the tables without bound.
34const MAX_EDGE_ID: u32 = 1 << 24;
35
36/// Maximum number of unique comparison sites tracked per call for CmpLog-style feedback.
37pub const MAX_CMP_LOG_SITES: usize = 1024;
38
39/// Maximum number of comparison operand pairs tracked per site. This matches the downstream loop
40/// detection threshold so a hot loop can be classified without filling the whole log.
41pub const MAX_CMP_OBSERVATIONS_PER_SITE: u8 = 8;
42
43/// A comparison operand pair captured during execution.
44#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
45pub struct CmpOperands {
46    /// First operand of the comparison.
47    pub op1: U256,
48    /// Second operand of the comparison.
49    pub op2: U256,
50    /// Program counter where the comparison occurred, or its site ID for a `CMPLOG` probe.
51    pub pc: usize,
52    /// Contract address where the comparison occurred.
53    pub address: Address,
54    /// EVM opcode that performed the comparison.
55    pub opcode: u8,
56}
57
58/// One instrumented edge hit during a call: its ID and AFL-style hit counter.
59#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
60pub struct InstrumentedEdgeHit {
61    /// Compiler-assigned edge ID.
62    pub id: u32,
63    /// Hit counter; never zero once the edge was hit (it saturates back to 1 on overflow).
64    pub count: u8,
65}
66
67/// Hit counters of one call, indexed by edge ID.
68#[derive(Debug)]
69struct EdgeHits {
70    counts: Vec<u8>,
71    /// IDs hit since the last reset, in first-hit order.
72    touched: Vec<u32>,
73}
74
75impl EdgeHits {
76    fn record(&mut self, id: u32) {
77        let index = id as usize;
78        if index >= self.counts.len() {
79            self.counts.resize((index + 1).next_power_of_two(), 0);
80        }
81        let count = &mut self.counts[index];
82        if *count == 0 {
83            self.touched.push(id);
84        }
85        // AFL NeverZero: a counter that wraps stays non-zero.
86        *count = count.wrapping_add(1).max(1);
87    }
88
89    fn take(&mut self) -> Vec<InstrumentedEdgeHit> {
90        let Self { counts, touched } = self;
91        touched
92            .drain(..)
93            .map(|id| InstrumentedEdgeHit { id, count: std::mem::take(&mut counts[id as usize]) })
94            .collect()
95    }
96}
97
98/// Comparison operands of one call, with the cmp-log inspector's caps counted per site ID in a
99/// dense table. Unlike the inspector, copies of a contract at several addresses share their caps.
100#[derive(Debug)]
101struct SiteCmpLog {
102    log: Vec<CmpOperands>,
103    /// Observations per site, indexed by site ID.
104    counts: Vec<u8>,
105    /// Sites observed since the last reset.
106    touched: Vec<u32>,
107}
108
109impl SiteCmpLog {
110    fn record(&mut self, site: u32, cmp: impl FnOnce() -> CmpOperands) {
111        let index = site as usize;
112        if index >= self.counts.len() {
113            self.counts.resize((index + 1).next_power_of_two(), 0);
114        }
115        let count = &mut self.counts[index];
116        if *count >= MAX_CMP_OBSERVATIONS_PER_SITE {
117            return;
118        }
119        if *count == 0 {
120            if self.touched.len() >= MAX_CMP_LOG_SITES {
121                return;
122            }
123            self.touched.push(site);
124        }
125        *count += 1;
126        self.log.push(cmp());
127    }
128
129    fn take(&mut self) -> Vec<CmpOperands> {
130        for site in self.touched.drain(..) {
131            self.counts[site as usize] = 0;
132        }
133        std::mem::take(&mut self.log)
134    }
135}
136
137/// This thread's instrumentation state.
138#[derive(Debug)]
139struct State {
140    /// Whether the opcodes execute instead of failing as undefined.
141    enabled: bool,
142    /// Whether `EDGECOV` records hits.
143    edges: bool,
144    /// Whether `CMPLOG` records operands.
145    cmp_log: bool,
146    hits: EdgeHits,
147    cmps: SiteCmpLog,
148}
149
150thread_local! {
151    // An `UnsafeCell` rather than a `RefCell` keeps the probes free of borrow-flag updates.
152    static STATE: UnsafeCell<State> = const {
153        UnsafeCell::new(State {
154            enabled: false,
155            edges: false,
156            cmp_log: false,
157            hits: EdgeHits { counts: Vec::new(), touched: Vec::new() },
158            cmps: SiteCmpLog { log: Vec::new(), counts: Vec::new(), touched: Vec::new() },
159        })
160    };
161}
162
163fn with_state<R>(f: impl FnOnce(&mut State) -> R) -> R {
164    // SAFETY: the reference does not escape `f`, and nothing called from `f` re-enters this
165    // function, so it is the only live reference to this thread's state.
166    STATE.with(|state| f(unsafe { &mut *state.get() }))
167}
168
169/// Executes the instrumentation opcodes on this thread while alive, recording edge hits when
170/// `edges` is set and comparison operands when `cmp_log` is set.
171#[derive(Debug)]
172pub struct EdgeCovGuard(());
173
174impl EdgeCovGuard {
175    /// Clears the hits and operands of the previous call and enables the opcodes.
176    pub fn new(edges: bool, cmp_log: bool) -> Self {
177        with_state(|state| {
178            state.enabled = true;
179            state.edges = edges;
180            state.cmp_log = cmp_log;
181            state.hits.take();
182            state.cmps.take();
183        });
184        Self(())
185    }
186}
187
188impl Drop for EdgeCovGuard {
189    fn drop(&mut self) {
190        with_state(|state| state.enabled = false);
191    }
192}
193
194/// Takes this thread's edge hits in first-hit order.
195pub fn take_edges() -> Vec<InstrumentedEdgeHit> {
196    with_state(|state| state.hits.take())
197}
198
199/// Takes this thread's comparison operands.
200pub fn take_cmp_log() -> Vec<CmpOperands> {
201    with_state(|state| state.cmps.take())
202}
203
204/// Converts a probe's ID word, ignoring the reserved ID 0 and IDs above [`MAX_EDGE_ID`].
205fn probe_id(word: U256) -> Option<u32> {
206    u32::try_from(word).ok().filter(|id| (1..=MAX_EDGE_ID).contains(id))
207}
208
209/// The `EDGECOV` instruction: pops the edge ID, records the hit and refunds the `PUSH` gas.
210#[instruction(dynamic_gas, no_stack_preamble)]
211fn edgecov(cx: _) -> Result {
212    with_state(|state| {
213        if !state.enabled {
214            return Err(InstrStop::OpcodeNotFound);
215        }
216        let id = stack.pop()?;
217        cx.gas.erase_cost(PUSH_GAS);
218        if state.edges
219            && let Some(id) = probe_id(id)
220        {
221            state.hits.record(id);
222        }
223        Ok(())
224    })
225}
226
227/// The `CMPLOG` instruction: pops `site << 8 | cmp opcode`, records the two words below it as the
228/// operands of that comparison, with the site ID as the program counter, and refunds the `PUSH`
229/// gas.
230#[instruction(dynamic_gas, no_stack_preamble)]
231fn cmplog(cx: _) -> Result {
232    with_state(|state| {
233        if !state.enabled {
234            return Err(InstrStop::OpcodeNotFound);
235        }
236        let tag = stack.pop()?;
237        let [op1, op2] = stack.peekn::<2>().ok_or(InstrStop::StackUnderflow)?;
238        cx.gas.erase_cost(PUSH_GAS);
239        let opcode = tag.byte(0);
240        if state.cmp_log
241            && matches!(opcode, op::EQ | op::LT | op::GT | op::SLT | op::SGT)
242            && let Some(site) = probe_id(tag >> 8)
243        {
244            let address = cx.state.message().destination;
245            state.cmps.record(site, || CmpOperands {
246                op1,
247                op2,
248                pc: site as usize,
249                address,
250                opcode,
251            });
252        }
253        Ok(())
254    })
255}
256
257/// Adds the `EDGECOV` and `CMPLOG` instructions to `config`.
258pub(crate) const fn with_instrumentation<T: EvmTypesHost>(
259    mut config: OpcodeConfig<T>,
260) -> OpcodeConfig<T> {
261    config.set_instruction::<edgecov<T>>(EDGECOV, 0);
262    config.set_instruction::<cmplog<T>>(CMPLOG, 0);
263    config
264}
265
266/// The base opcode table of `BASE_SPEC_ID` with the instrumentation opcodes.
267struct InstrumentedConfig<T, const BASE_SPEC_ID: u32>(PhantomData<fn() -> T>);
268
269impl<T: EvmTypesHost, const BASE_SPEC_ID: u32> EvmConfig<T>
270    for InstrumentedConfig<T, BASE_SPEC_ID>
271{
272    const BASE_SPEC_ID: SpecId = SpecId::try_from_u32(BASE_SPEC_ID).expect("invalid base spec id");
273    const OPCODE_CONFIG: &'static OpcodeConfig<T> =
274        &with_instrumentation(OpcodeConfig::base::<Self>());
275}
276
277/// The execution config of a network that runs the base opcode table, with the instrumentation
278/// opcodes.
279pub(crate) fn execution_config<T: EvmTypesHost>(
280    spec: T::SpecId,
281    version: Version,
282) -> ExecutionConfig<T> {
283    evm2::spec_to_generic!(spec.into(), |BASE_SPEC_ID| ExecutionConfig::for_config::<
284        InstrumentedConfig<T, BASE_SPEC_ID>,
285    >()
286    .with_version(version))
287}
288
289#[cfg(test)]
290mod tests {
291    use super::*;
292    use crate::evm::{EthEvmFactory, FoundryEvmFactory, SpecOf};
293    use evm2::OpcodeChange;
294    use tempo_evm::TempoEvmFactory;
295
296    fn hits(ids: &[u32]) -> Vec<InstrumentedEdgeHit> {
297        let _guard = EdgeCovGuard::new(true, false);
298        with_state(|state| {
299            for &id in ids {
300                if let Some(id) = probe_id(U256::from(id)) {
301                    state.hits.record(id);
302                }
303            }
304        });
305        take_edges()
306    }
307
308    #[test]
309    fn counter_never_wraps_to_zero() {
310        assert_eq!(hits(&[5; 256]), [InstrumentedEdgeHit { id: 5, count: 1 }]);
311        assert_eq!(hits(&[5; 255]), [InstrumentedEdgeHit { id: 5, count: 255 }]);
312    }
313
314    #[test]
315    fn ignores_reserved_and_out_of_range_ids() {
316        assert!(hits(&[0, MAX_EDGE_ID + 1]).is_empty());
317        assert_eq!(probe_id(U256::MAX), None);
318    }
319
320    /// Asserts that `F`'s opcode table is its network's default table plus the probes.
321    fn assert_adds_only_probes<F: FoundryEvmFactory>() {
322        let spec = SpecOf::<F>::default();
323        let version = F::default().version(spec, 1);
324        let ours = F::default().execution_config(spec, version).opcode_view();
325        let default =
326            ExecutionConfig::<F::Types>::for_spec_and_version(spec, version).opcode_view();
327        for opcode in 0..=u8::MAX {
328            let expected = match opcode {
329                EDGECOV | CMPLOG => OpcodeChange::Instruction,
330                _ => default.change(opcode),
331            };
332            assert_eq!(ours.change(opcode), expected, "opcode {opcode:#04x}");
333            assert_eq!(ours.static_gas(opcode), default.static_gas(opcode), "opcode {opcode:#04x}");
334        }
335    }
336
337    #[test]
338    fn networks_add_only_probes_to_their_opcode_tables() {
339        assert_adds_only_probes::<EthEvmFactory>();
340        assert_adds_only_probes::<TempoEvmFactory>();
341        #[cfg(feature = "optimism")]
342        assert_adds_only_probes::<op_evm2::OpEvmFactory>();
343        #[cfg(feature = "base")]
344        assert_adds_only_probes::<base_evm2::BaseEvmFactory>();
345    }
346}