Skip to main content

foundry_evm/executors/invariant/
live.rs

1//! Bounded, asynchronous assistance for an invariant campaign. Candidates are executed by the
2//! ordinary campaign before they can contribute coverage or failures.
3
4use super::RecordedCallSequence;
5use crate::{
6    EVM_THREAD_STACK_SIZE,
7    executors::{
8        EarlyExit, EvmExecutionCancellation, Executor,
9        fuzz::{FuzzBranchFrontier, FuzzFrontierRecorder, comparison_result},
10    },
11    inspectors::CmpOperands,
12};
13use alloy_primitives::{Address, map::HashSet};
14use eyre::Result;
15use foundry_config::SymbolicConfig;
16use foundry_evm_core::evm::FoundryEvmNetwork;
17use foundry_evm_fuzz::BasicTxDetails;
18use serde::{Deserialize, Serialize};
19use std::{
20    collections::VecDeque,
21    sync::{
22        Arc,
23        atomic::{AtomicBool, Ordering},
24        mpsc::{self, Receiver, SyncSender},
25    },
26    thread::{self, JoinHandle},
27    time::{Duration, Instant},
28};
29
30const MAX_PENDING: usize = 32;
31const MAX_CALLS: usize = 1024;
32const MAX_CALLDATA_BYTES: usize = 64 * 1024;
33/// Distinct comparison outcomes remembered to select solve targets. Real targets reach far more
34/// outcomes than `frontier_limit` in their first sequence, so this bound is separate from the
35/// submission budget.
36const MAX_OBSERVED_OUTCOMES: usize = 1 << 16;
37
38/// One side of a comparison site: address, pc, opcode, and result.
39type Outcome = (Address, usize, u8, bool);
40
41/// Counters for the live worker, separate from bounded symbolic verification results.
42#[derive(Clone, Debug, Default, Serialize, Deserialize)]
43pub struct LiveInvariantStats {
44    /// Frontiers accepted into the request queue.
45    pub submitted: usize,
46    /// Frontiers examined by the worker.
47    pub completed: usize,
48    /// Total queries issued to the solver.
49    pub solver_queries: usize,
50    /// Total time spent in solver queries, in milliseconds.
51    pub solver_time_ms: u64,
52    /// Candidate sequences handed to the concrete campaign.
53    pub scheduled: usize,
54}
55
56/// A solver response. The campaign re-executes the candidate using its own predicate policy.
57#[derive(Default)]
58pub struct LiveInvariantSolution {
59    /// Candidate sequence, still subject to normal campaign execution.
60    pub sequence: Option<Vec<BasicTxDetails>>,
61    /// Total queries issued to the solver.
62    pub solver_queries: usize,
63    /// Total time spent in solver queries, in milliseconds.
64    pub solver_time_ms: u64,
65}
66
67/// One solver thread, 32 retained frontiers, and one slot in each channel.
68pub struct LiveInvariantSolver {
69    requests: Option<SyncSender<FuzzBranchFrontier>>,
70    responses: Receiver<(Vec<BasicTxDetails>, Outcome)>,
71    stop: Arc<AtomicBool>,
72    thread: Option<JoinHandle<LiveInvariantStats>>,
73    observed: HashSet<Outcome>,
74    /// Outcomes already queued for the worker; each is attempted once unless it is flipped.
75    admitted: HashSet<Outcome>,
76    /// Admitted outcomes for which the worker returned a candidate.
77    flipped: HashSet<Outcome>,
78    /// Flipped outcomes already retried from a storage state.
79    retried: HashSet<(Outcome, u64)>,
80    /// Queued frontiers, flagged when they retry an admitted outcome from a new prefix.
81    pending: VecDeque<(FuzzBranchFrontier, bool)>,
82    limit: usize,
83    deadline: Instant,
84    stats: LiveInvariantStats,
85}
86
87impl LiveInvariantSolver {
88    /// Starts one worker with campaign-wide time, query, and frontier budgets.
89    pub fn spawn<FEN: FoundryEvmNetwork>(
90        setup: Executor<FEN>,
91        config: &SymbolicConfig,
92        mut solve: impl FnMut(Executor<FEN>, &FuzzBranchFrontier, Instant, u32) -> LiveInvariantSolution
93        + Send
94        + 'static,
95    ) -> Result<Self> {
96        let (requests, input) = mpsc::sync_channel::<FuzzBranchFrontier>(1);
97        let (output, responses) = mpsc::sync_channel(1);
98        let stop = Arc::new(AtomicBool::new(false));
99        let cancelled = Arc::clone(&stop);
100        let deadline = Instant::now() + Duration::from_secs(config.timeout.unwrap_or(30).into());
101        let max_queries = config.max_solver_queries as usize;
102        let builder = thread::Builder::new().name("invariant-symbolic".into());
103        let thread = builder.stack_size(EVM_THREAD_STACK_SIZE).spawn(move || {
104            let mut stats = LiveInvariantStats::default();
105            while !cancelled.load(Ordering::Relaxed)
106                && Instant::now() < deadline
107                && stats.solver_queries < max_queries
108            {
109                let frontier = match input.recv_timeout(Duration::from_millis(10)) {
110                    Ok(frontier) => frontier,
111                    Err(mpsc::RecvTimeoutError::Timeout) => continue,
112                    Err(mpsc::RecvTimeoutError::Disconnected) => break,
113                };
114                let mut executor = setup.clone();
115                executor.inspector_mut().set_execution_cancellation(
116                    EvmExecutionCancellation::campaign(
117                        EarlyExit::new(false),
118                        Arc::clone(&cancelled),
119                        Some(deadline),
120                    ),
121                );
122                let result = solve(
123                    executor,
124                    &frontier,
125                    deadline,
126                    (max_queries - stats.solver_queries) as u32,
127                );
128                stats.completed += 1;
129                stats.solver_queries += result.solver_queries;
130                stats.solver_time_ms += result.solver_time_ms;
131                if let Some(sequence) = result.sequence {
132                    let (cmp, result) = frontier.comparison();
133                    let mut response = (sequence, outcome(&cmp, result));
134                    // Preserve useful responses under backpressure, while keeping shutdown
135                    // bounded when the concrete campaign has already stopped consuming.
136                    while !cancelled.load(Ordering::Relaxed) && Instant::now() < deadline {
137                        match output.try_send(response) {
138                            Ok(()) | Err(mpsc::TrySendError::Disconnected(_)) => break,
139                            Err(mpsc::TrySendError::Full(pending)) => response = pending,
140                        }
141                        thread::sleep(Duration::from_millis(1));
142                    }
143                }
144            }
145            stats
146        })?;
147        Ok(Self {
148            requests: (max_queries > 0 && config.frontier_limit > 0).then_some(requests),
149            responses,
150            stop,
151            thread: Some(thread),
152            observed: HashSet::default(),
153            admitted: HashSet::default(),
154            flipped: HashSet::default(),
155            retried: HashSet::default(),
156            pending: VecDeque::new(),
157            limit: config.frontier_limit,
158            deadline,
159            stats: LiveInvariantStats::default(),
160        })
161    }
162
163    /// Offers a completed run's comparisons. `states` lists the storage states the run reached
164    /// in call order, as the index of the call that produced each and a feature identifying it.
165    pub(super) fn submit(
166        &mut self,
167        sequence: &RecordedCallSequence,
168        depth: usize,
169        states: &[(usize, u64)],
170    ) {
171        if !self.is_active()
172            || !Self::accepts_sequence(
173                sequence.inputs.len(),
174                sequence.inputs.iter().map(|tx| tx.call_details.calldata.len()).sum(),
175            )
176        {
177            return;
178        }
179        let cmp_seq = &sequence.cmp_seq[..sequence.cmp_seq.len().min(depth)];
180        for cmp in cmp_seq.iter().flatten() {
181            if self.observed.len() >= MAX_OBSERVED_OUTCOMES {
182                break;
183            }
184            if let Some(result) = comparison_result(cmp) {
185                self.observed.insert(outcome(cmp, result));
186            }
187        }
188        self.dispatch();
189        let room = (MAX_PENDING - self.pending.len())
190            .min(self.limit - self.stats.submitted - self.pending.len());
191        if room > 0 {
192            let state_before = |index: usize| {
193                states.iter().rev().find(|(call, _)| *call < index).map(|&(_, state)| state)
194            };
195            // A first attempt needs an outcome whose other side fuzzing has not reached; one that
196            // does not fit stays unadmitted, so a later run offers it again. A flipped outcome is
197            // retried once from each new storage state, which may need different arguments, unless
198            // a retry of it is already queued.
199            let targets = cmp_seq
200                .iter()
201                .enumerate()
202                .map(|(index, cmps)| {
203                    cmps.iter()
204                        .copied()
205                        .filter(|cmp| {
206                            let Some(result) = comparison_result(cmp) else { return false };
207                            let reached = outcome(cmp, result);
208                            self.observed.contains(&reached)
209                                && if self.admitted.contains(&reached) {
210                                    self.flipped.contains(&reached)
211                                        && state_before(index).is_some_and(|state| {
212                                            !self.retried.contains(&(reached, state))
213                                        })
214                                        && !self.pending.iter().any(|(frontier, _)| {
215                                            let (cmp, result) = frontier.comparison();
216                                            outcome(&cmp, result) == reached
217                                        })
218                                } else {
219                                    !self.observed.contains(&outcome(cmp, !result))
220                                }
221                        })
222                        .collect::<Vec<_>>()
223                })
224                .collect::<Vec<_>>();
225            let mut recorder = FuzzFrontierRecorder::new(room);
226            recorder.prefer_shortest_prefix();
227            recorder.capture_sequence(&sequence.inputs, &targets);
228            for frontier in recorder.into_frontiers() {
229                let (cmp, result) = frontier.comparison();
230                let reached = outcome(&cmp, result);
231                let retry = !self.admitted.insert(reached);
232                if retry && let Some(state) = state_before(frontier.sequence().len() - 1) {
233                    self.retried.insert((reached, state));
234                }
235                self.pending.push_back((frontier, retry));
236            }
237        }
238        self.dispatch();
239    }
240
241    fn dispatch(&mut self) {
242        // Fuzzing may have reached the other side of a first attempt since it was admitted.
243        self.pending.retain(|(frontier, retry)| {
244            let (cmp, result) = frontier.comparison();
245            *retry || !self.observed.contains(&outcome(&cmp, !result))
246        });
247        while let Some((frontier, retry)) = self.pending.pop_front() {
248            let Some(requests) = &self.requests else { break };
249            match requests.try_send(frontier) {
250                Ok(()) => self.stats.submitted += 1,
251                Err(mpsc::TrySendError::Full(frontier)) => {
252                    self.pending.push_front((frontier, retry));
253                    break;
254                }
255                Err(mpsc::TrySendError::Disconnected(_)) => {
256                    self.requests = None;
257                    self.pending.clear();
258                    break;
259                }
260            }
261        }
262    }
263
264    pub(super) fn next(&mut self, depth: usize) -> Option<Vec<BasicTxDetails>> {
265        self.dispatch();
266        let (sequence, flipped) = self.responses.try_recv().ok()?;
267        self.flipped.insert(flipped);
268        if sequence.is_empty() || sequence.len() > depth {
269            return None;
270        }
271        self.stats.scheduled += 1;
272        Some(sequence)
273    }
274
275    pub(super) fn finish(&mut self) -> LiveInvariantStats {
276        self.stop.store(true, Ordering::Relaxed);
277        self.requests = None;
278        if let Some(thread) = self.thread.take() {
279            match thread.join() {
280                Ok(stats) => {
281                    self.stats.completed = stats.completed;
282                    self.stats.solver_queries = stats.solver_queries;
283                    self.stats.solver_time_ms = stats.solver_time_ms;
284                }
285                Err(_) => {
286                    tracing::warn!("live symbolic worker panicked; concrete campaign continued")
287                }
288            }
289        }
290        self.stats.clone()
291    }
292
293    /// Whether recording more frontiers can still contribute work to this campaign.
294    pub(super) fn is_active(&self) -> bool {
295        self.requests.is_some()
296            && self.stats.submitted + self.pending.len() < self.limit
297            && Instant::now() < self.deadline
298            && self.thread.as_ref().is_some_and(|thread| !thread.is_finished())
299    }
300
301    /// Applies the same input bounds during collection and before channel admission.
302    pub(super) const fn accepts_sequence(calls: usize, calldata_bytes: usize) -> bool {
303        calls <= MAX_CALLS && calldata_bytes <= MAX_CALLDATA_BYTES
304    }
305}
306
307impl Drop for LiveInvariantSolver {
308    fn drop(&mut self) {
309        self.finish();
310    }
311}
312
313/// Identifies one side of a comparison site.
314const fn outcome(cmp: &CmpOperands, result: bool) -> Outcome {
315    (cmp.address, cmp.pc, cmp.opcode, result)
316}