foundry_evm/executors/invariant/
live.rs1use 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;
33const MAX_OBSERVED_OUTCOMES: usize = 1 << 16;
37
38type Outcome = (Address, usize, u8, bool);
40
41#[derive(Clone, Debug, Default, Serialize, Deserialize)]
43pub struct LiveInvariantStats {
44 pub submitted: usize,
46 pub completed: usize,
48 pub solver_queries: usize,
50 pub solver_time_ms: u64,
52 pub scheduled: usize,
54}
55
56#[derive(Default)]
58pub struct LiveInvariantSolution {
59 pub sequence: Option<Vec<BasicTxDetails>>,
61 pub solver_queries: usize,
63 pub solver_time_ms: u64,
65}
66
67pub 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 admitted: HashSet<Outcome>,
76 flipped: HashSet<Outcome>,
78 retried: HashSet<(Outcome, u64)>,
80 pending: VecDeque<(FuzzBranchFrontier, bool)>,
82 limit: usize,
83 deadline: Instant,
84 stats: LiveInvariantStats,
85}
86
87impl LiveInvariantSolver {
88 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 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 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 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 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 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 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
313const fn outcome(cmp: &CmpOperands, result: bool) -> Outcome {
315 (cmp.address, cmp.pc, cmp.opcode, result)
316}