foundry_evm_symbolic/runtime/
address.rs

1use super::*;
2
3/// Returns the `mask_bits` address normalization helper result.
4pub(crate) fn mask_bits(value: U256, bits: usize) -> U256 {
5    if bits >= 256 {
6        value
7    } else {
8        let mask = (U256::from(1) << bits) - U256::from(1);
9        value & mask
10    }
11}
12
13/// Returns the `address_word` address normalization helper result.
14pub(crate) fn address_word(address: Address) -> U256 {
15    U256::from_be_bytes(address.into_word().0)
16}
17
18/// Returns the `word_to_address` address normalization helper result.
19pub(crate) fn word_to_address(value: U256) -> Address {
20    Address::from_word(value.to_be_bytes::<32>().into())
21}
22
23/// Implements the `representative_symbolic_address` address normalization helper.
24pub(crate) fn representative_symbolic_address(word: &SymWord) -> Address {
25    let digest = keccak256(symbolic_address_key(word));
26    let mut bytes = [0u8; 20];
27    bytes[0] = 0xfe;
28    bytes[1..].copy_from_slice(&digest[..19]);
29    Address::from(bytes)
30}
31
32/// Returns the `symbolic_address_key` address normalization helper result.
33pub(crate) fn symbolic_address_key(word: &SymWord) -> String {
34    match word {
35        SymWord::Concrete(value) => format!("concrete-address:{:?}", word_to_address(*value)),
36        SymWord::Expr(expr) => {
37            let bytes = address_byte_terms(expr)
38                .map(|bytes| format!("{bytes:?}"))
39                .unwrap_or_else(|| format!("{expr:?}"));
40            format!("symbolic-address:{bytes}")
41        }
42    }
43}
44
45/// Returns the `address_match_condition` address normalization helper result.
46pub(crate) fn address_match_condition(word: &SymWord, address: Address) -> BoolExpr {
47    let expr = word.clone().into_expr();
48    let Some(terms) = address_byte_terms(&expr) else {
49        return BoolExpr::eq(expr, Expr::Const(address_word(address)));
50    };
51    let bytes = address.as_slice();
52    BoolExpr::and(
53        terms
54            .into_iter()
55            .enumerate()
56            .map(|(index, term)| BoolExpr::eq(term, Expr::Const(U256::from(bytes[index]))))
57            .collect(),
58    )
59}
60
61/// Returns the `symbolic_address_equivalent` address normalization helper result.
62pub(crate) fn symbolic_address_equivalent(candidate: &SymWord, alias: &SymWord) -> bool {
63    match (candidate, alias) {
64        (SymWord::Concrete(left), SymWord::Concrete(right)) => {
65            word_to_address(*left) == word_to_address(*right)
66        }
67        (SymWord::Expr(candidate), SymWord::Expr(alias)) => {
68            address_expr_equivalent(candidate, alias)
69        }
70        _ => false,
71    }
72}
73
74/// Returns the `address_expr_equivalent` address normalization helper result.
75pub(crate) fn address_expr_equivalent(candidate: &Expr, alias: &Expr) -> bool {
76    if candidate == alias {
77        return true;
78    }
79
80    if let (Some(candidate), Some(alias)) =
81        (address_byte_terms(candidate), address_byte_terms(alias))
82    {
83        return candidate == alias;
84    }
85
86    match candidate {
87        Expr::Op(ExprOp::And, left, right) => {
88            (is_address_mask(right) && address_expr_equivalent(left, alias))
89                || (is_address_mask(left) && address_expr_equivalent(right, alias))
90        }
91        Expr::Op(ExprOp::Shr, value, shift) if is_shift_96(shift) => match value.as_ref() {
92            Expr::Op(ExprOp::Shl, inner, inner_shift) if is_shift_96(inner_shift) => {
93                address_expr_equivalent(inner, alias)
94            }
95            _ => false,
96        },
97        _ => false,
98    }
99}
100
101/// Returns the `address_byte_terms` address normalization helper result.
102pub(crate) fn address_byte_terms(expr: &Expr) -> Option<Vec<Expr>> {
103    (12..32).map(|index| expr_byte_term(expr, index)).collect()
104}
105
106/// Returns the `expr_byte_term` address normalization helper result.
107pub(crate) fn expr_byte_term(expr: &Expr, index: usize) -> Option<Expr> {
108    debug_assert!(index < 32);
109
110    match expr {
111        Expr::Const(value) => Some(Expr::Const(U256::from(value.to_be_bytes::<32>()[index]))),
112        Expr::Var(_) | Expr::GasLeft(_) | Expr::Keccak { .. } | Expr::Hash { .. } => {
113            Some(extracted_byte_expr(expr, index))
114        }
115        Expr::Not(value) => Some(Expr::Not(Box::new(expr_byte_term(value, index)?))),
116        Expr::Ite(cond, then_expr, else_expr) => Some(Expr::Ite(
117            cond.clone(),
118            Box::new(expr_byte_term(then_expr, index)?),
119            Box::new(expr_byte_term(else_expr, index)?),
120        )),
121        Expr::Op(op, left, right) => match op {
122            ExprOp::And => expr_binary_byte_term(
123                left,
124                right,
125                index,
126                ExprOp::And,
127                |byte| byte == 0xff,
128                |byte| byte == 0,
129            ),
130            ExprOp::Or => {
131                expr_binary_byte_term(left, right, index, ExprOp::Or, |byte| byte == 0, |_| false)
132            }
133            ExprOp::Xor => {
134                expr_binary_byte_term(left, right, index, ExprOp::Xor, |byte| byte == 0, |_| false)
135            }
136            ExprOp::Shl => {
137                let shift = expr_const_value(right)?;
138                if shift >= U256::from(256) {
139                    return Some(Expr::Const(U256::ZERO));
140                }
141                let shift = shift.to::<usize>();
142                if shift % 8 != 0 {
143                    return None;
144                }
145                let source_index = index + shift / 8;
146                if source_index >= 32 {
147                    Some(Expr::Const(U256::ZERO))
148                } else {
149                    expr_byte_term(left, source_index)
150                }
151            }
152            ExprOp::Shr => {
153                let shift = expr_const_value(right)?;
154                if shift >= U256::from(256) {
155                    return Some(Expr::Const(U256::ZERO));
156                }
157                let shift = shift.to::<usize>();
158                if shift % 8 != 0 {
159                    return None;
160                }
161                let byte_shift = shift / 8;
162                if index < byte_shift {
163                    Some(Expr::Const(U256::ZERO))
164                } else {
165                    expr_byte_term(left, index - byte_shift)
166                }
167            }
168            ExprOp::Add
169            | ExprOp::Sub
170            | ExprOp::Mul
171            | ExprOp::UDiv
172            | ExprOp::URem
173            | ExprOp::SDiv
174            | ExprOp::SRem
175            | ExprOp::Sar => None,
176        },
177    }
178}
179
180/// Returns the `expr_binary_byte_term` address normalization helper result.
181pub(crate) fn expr_binary_byte_term(
182    left: &Expr,
183    right: &Expr,
184    index: usize,
185    op: ExprOp,
186    identity: impl Fn(u8) -> bool,
187    absorbing: impl Fn(u8) -> bool,
188) -> Option<Expr> {
189    let left = expr_byte_term(left, index)?;
190    let right = expr_byte_term(right, index)?;
191    match (expr_byte_const(&left), expr_byte_const(&right)) {
192        (Some(left), _) if absorbing(left) => Some(Expr::Const(U256::from(left))),
193        (_, Some(right)) if absorbing(right) => Some(Expr::Const(U256::from(right))),
194        (Some(left), _) if identity(left) => Some(right),
195        (_, Some(right)) if identity(right) => Some(left),
196        _ => Some(Expr::op(op, left, right)),
197    }
198}
199
200/// Returns the `expr_byte_const` address normalization helper result.
201pub(crate) fn expr_byte_const(expr: &Expr) -> Option<u8> {
202    let Expr::Const(value) = expr else { return None };
203    Some(value.to::<u8>())
204}
205
206/// Implements the `extracted_byte_expr` address normalization helper.
207pub(crate) fn extracted_byte_expr(expr: &Expr, index: usize) -> Expr {
208    Expr::op(
209        ExprOp::And,
210        Expr::op(ExprOp::Shr, expr.clone(), Expr::Const(U256::from((31 - index) * 8))),
211        Expr::Const(U256::from(0xff)),
212    )
213}
214
215/// Returns whether `is_address_mask` holds.
216pub(crate) fn is_address_mask(expr: &Expr) -> bool {
217    matches!(expr, Expr::Const(value) if *value == ((U256::from(1) << 160) - U256::from(1)))
218}
219
220/// Returns whether `is_shift_96` holds.
221pub(crate) fn is_shift_96(expr: &Expr) -> bool {
222    matches!(expr, Expr::Const(value) if *value == U256::from(96))
223}
224
225/// Implements the `stable_symbol` address normalization helper.
226pub(crate) fn stable_symbol(prefix: &'static str, input: impl AsRef<[u8]>) -> String {
227    let digest = keccak256(input.as_ref());
228    let mut symbol = String::with_capacity(prefix.len() + 17);
229    symbol.push_str(prefix);
230    symbol.push('_');
231    for byte in &digest[..8] {
232        let _ = write!(symbol, "{byte:02x}");
233    }
234    symbol
235}
foundry_evm_symbolic/runtime/address.rs

foundry_evm_symbolic/runtime/
address.rs
