brillig_vm/
fuzzing.rs

1use acir::AcirField;
2use acvm_blackbox_solver::BlackBoxFunctionSolver;
3use num_bigint::BigUint;
4
5use crate::{
6    BinaryFieldOp, BinaryIntOp, MemoryValue, NextOpcodePositionOrState, OpcodePosition, VM,
7};
8use std::collections::HashMap;
9
10/// A state that represents a true comparison as part of a feature
11const FUZZING_COMPARISON_TRUE_STATE: usize = usize::MAX - 1;
12/// A state that represents a false comparison as part of a feature
13const FUZZING_COMPARISON_FALSE_STATE: usize = usize::MAX;
14
15/// The start of the range of the states that represent logarithm of the difference between the comparison arguments as part of a feature
16const FUZZING_COMPARISON_LOG_RANGE_START_STATE: usize = 0;
17
18/// A tuple of the current opcode position and the next opcode position or state
19pub type Branch = (OpcodePosition, NextOpcodePositionOrState);
20
21/// The index of a unique feature in the fuzzing trace
22pub type UniqueFeatureIndex = usize;
23
24/// A map for translating encountered branching logic to features for fuzzing
25pub type BranchToFeatureMap = HashMap<Branch, UniqueFeatureIndex>;
26
27/// Context structure for all information necessary to compute the fuzzing trace
28#[derive(Debug, PartialEq, Eq, Clone, Default)]
29pub(super) struct FuzzingTrace {
30    /// Fuzzer tracing memory.
31    ///
32    /// It records each time a key in the `branch_to_feature_map` was observed.
33    /// Its length is equal to that of the `branch_to_feature_map`.
34    trace: Vec<u32>,
35    /// Branch to feature map for fuzzing.
36    /// Maps program counter + feature to index in the trace vector.
37    branch_to_feature_map: HashMap<(usize, usize), usize>,
38}
39
40impl FuzzingTrace {
41    fn branch_state(cond: bool) -> usize {
42        if cond { FUZZING_COMPARISON_TRUE_STATE } else { FUZZING_COMPARISON_FALSE_STATE }
43    }
44
45    fn log_range_state(log: usize) -> usize {
46        FUZZING_COMPARISON_LOG_RANGE_START_STATE + log
47    }
48
49    /// Compute the distance of two field elements as the number of bits required
50    /// to represent their difference, which is the same as its logarithm.
51    fn field_diff_log<F: AcirField>(a: F, b: F) -> u64 {
52        // Field subtraction is modular, not signed. When a > b, even if the two values
53        // are numerically very close in the intended integer sense, `b - a` becomes a
54        // large field element near the modulus. For example, if `a = b + 1`, the computed
55        // difference is effectively `-1 mod p`, which has a very large bit length.
56        // Since we are only interested in how close the numbers are, we subtract the
57        // smaller representation from the larger.
58        let d = if a > b { a - b } else { b - a };
59        BigUint::from_bytes_be(&d.to_be_bytes()).bits()
60    }
61
62    /// Compute the distance of two integers as the logarithm of the absolute value
63    /// of their difference, which is the number of bits required to represent it.
64    fn int_diff_log(a: u128, b: u128) -> u32 {
65        a.abs_diff(b).checked_ilog2().map_or(0, |x| x + 1)
66    }
67
68    pub(super) fn new(branch_to_feature_map: HashMap<(usize, usize), usize>) -> Self {
69        let len = branch_to_feature_map.len();
70        Self { trace: vec![0; len], branch_to_feature_map }
71    }
72
73    fn record_branch(&mut self, pc: usize, destination: usize) {
74        let index = self.branch_to_feature_map[&(pc, destination)];
75        self.trace[index] += 1;
76    }
77
78    fn record_conditional_mov(&mut self, pc: usize, branch: bool) {
79        let index = self.branch_to_feature_map[&(pc, Self::branch_state(branch))];
80        self.trace[index] += 1;
81    }
82
83    fn record_binary_field_op_comparison<F: AcirField>(
84        &mut self,
85        pc: usize,
86        op: &BinaryFieldOp,
87        lhs: MemoryValue<F>,
88        rhs: MemoryValue<F>,
89        result: MemoryValue<F>,
90    ) {
91        match op {
92            BinaryFieldOp::Equals | BinaryFieldOp::LessThan | BinaryFieldOp::LessThanEquals => {
93                let MemoryValue::Field(a) = lhs else {
94                    return;
95                };
96                let MemoryValue::Field(b) = rhs else {
97                    return;
98                };
99                let MemoryValue::U1(c) = result else {
100                    return;
101                };
102
103                // Logarithm of the difference between LHS as RHS as the number of bits required to represent its value:
104                let diff_log = Self::field_diff_log(a, b);
105
106                let approach_index =
107                    self.branch_to_feature_map[&(pc, Self::log_range_state(diff_log as usize))];
108
109                let condition_index = self.branch_to_feature_map[&(pc, Self::branch_state(c))];
110
111                self.trace[approach_index] += 1;
112                self.trace[condition_index] += 1;
113            }
114            BinaryFieldOp::Add
115            | BinaryFieldOp::Sub
116            | BinaryFieldOp::Mul
117            | BinaryFieldOp::Div
118            | BinaryFieldOp::IntegerDiv => {}
119        }
120    }
121
122    fn record_binary_int_op_comparison<F: AcirField>(
123        &mut self,
124        pc: usize,
125        op: &BinaryIntOp,
126        lhs: MemoryValue<F>,
127        rhs: MemoryValue<F>,
128        result: MemoryValue<F>,
129    ) {
130        match op {
131            BinaryIntOp::Equals | BinaryIntOp::LessThan | BinaryIntOp::LessThanEquals => {
132                let lhs_val = lhs.to_u128().expect("lhs is not an integer");
133                let rhs_val = rhs.to_u128().expect("rhs is not an integer");
134                let MemoryValue::U1(c) = result else {
135                    return;
136                };
137
138                let diff_log = Self::int_diff_log(lhs_val, rhs_val);
139
140                let approach_index =
141                    self.branch_to_feature_map[&(pc, Self::log_range_state(diff_log as usize))];
142
143                let condition_index = self.branch_to_feature_map[&(pc, Self::branch_state(c))];
144
145                self.trace[approach_index] += 1;
146                self.trace[condition_index] += 1;
147            }
148            BinaryIntOp::Add
149            | BinaryIntOp::Sub
150            | BinaryIntOp::Mul
151            | BinaryIntOp::Div
152            | BinaryIntOp::And
153            | BinaryIntOp::Or
154            | BinaryIntOp::Xor
155            | BinaryIntOp::Shl
156            | BinaryIntOp::Shr => {}
157        }
158    }
159
160    pub(super) fn get_trace(&self) -> Vec<u32> {
161        self.trace.clone()
162    }
163}
164
165impl<F: AcirField, B: BlackBoxFunctionSolver<F>> VM<'_, F, B> {
166    /// Collect information about the comparison of two field values in the fuzzing trace
167    pub(super) fn fuzzing_trace_binary_field_op_comparison(
168        &mut self,
169        op: &BinaryFieldOp,
170        lhs: MemoryValue<F>,
171        rhs: MemoryValue<F>,
172        result: MemoryValue<F>,
173    ) {
174        if let Some(ref mut trace) = self.fuzzing_trace {
175            trace.record_binary_field_op_comparison(self.program_counter, op, lhs, rhs, result);
176        }
177    }
178
179    /// Collect information about the comparison of two integer values in the fuzzing trace
180    pub(super) fn fuzzing_trace_binary_int_op_comparison(
181        &mut self,
182        op: &BinaryIntOp,
183        lhs: MemoryValue<F>,
184        rhs: MemoryValue<F>,
185        result: MemoryValue<F>,
186    ) {
187        if let Some(ref mut trace) = self.fuzzing_trace {
188            trace.record_binary_int_op_comparison(self.program_counter, op, lhs, rhs, result);
189        }
190    }
191
192    /// Mark the execution of a particular branch in the fuzzing trace
193    pub(super) fn fuzzing_trace_branching(&mut self, destination: NextOpcodePositionOrState) {
194        if let Some(ref mut trace) = self.fuzzing_trace {
195            trace.record_branch(self.program_counter, destination);
196        }
197    }
198
199    /// Mark the execution of a conditional move in the fuzzing trace
200    pub(super) fn fuzzing_trace_conditional_mov(&mut self, branch: bool) {
201        if let Some(ref mut trace) = self.fuzzing_trace {
202            trace.record_conditional_mov(self.program_counter, branch);
203        }
204    }
205}
206
207#[cfg(test)]
208mod tests {
209    use acir::FieldElement;
210    use proptest::proptest;
211
212    use crate::FuzzingTrace;
213
214    proptest! {
215        #[test]
216        fn int_diff_log_is_symmetric(a: u128, b: u128) {
217            let ab = FuzzingTrace::int_diff_log(a, b);
218            let ba = FuzzingTrace::int_diff_log(b, a);
219            assert_eq!(ab, ba);
220        }
221    }
222
223    proptest! {
224        #[test]
225        fn field_diff_log_is_symmetric(a: u128, b: u128) {
226            let a = FieldElement::from(a);
227            let b = FieldElement::from(b);
228            let ab = FuzzingTrace::field_diff_log(a, b);
229            let ba = FuzzingTrace::field_diff_log(b, a);
230            assert_eq!(ab, ba);
231        }
232    }
233
234    #[test]
235    fn field_diff_log_with_1_diff() {
236        let a = FieldElement::from(1);
237        let b = FieldElement::from(2);
238        let ab = FuzzingTrace::field_diff_log(a, b);
239        let ba = FuzzingTrace::field_diff_log(b, a);
240        assert_eq!(ab, 1);
241        assert_eq!(ab, ba);
242    }
243}
brillig_vm/fuzzing.rs

brillig_vm/
fuzzing.rs
