veriwasm/analyses/
mod.rs

1mod call_analyzer;
2mod heap_analyzer;
3mod jump_analyzer;
4pub mod locals_analyzer;
5pub mod reaching_defs;
6mod stack_analyzer;
7use crate::ir::types::{Binopcode, IRBlock, IRMap, Stmt, Unopcode, Value};
8use crate::lattices::reachingdefslattice::LocIdx;
9use crate::lattices::{Lattice, VarState};
10use std::collections::{HashMap, VecDeque};
11use yaxpeax_core::analyses::control_flow::VW_CFG;
12
13/*     Public API     */
14pub use self::call_analyzer::CallAnalyzer;
15pub use self::heap_analyzer::HeapAnalyzer;
16pub use self::jump_analyzer::SwitchAnalyzer;
17pub use self::stack_analyzer::StackAnalyzer;
18
19pub type AnalysisResult<T> = HashMap<u64, T>;
20
21pub trait AbstractAnalyzer<State: Lattice + VarState + Clone> {
22    fn init_state(&self) -> State {
23        Default::default()
24    }
25    fn process_branch(
26        &self,
27        _irmap: &IRMap,
28        in_state: &State,
29        succ_addrs: &Vec<u64>,
30        _addr: &u64,
31    ) -> Vec<(u64, State)> {
32        succ_addrs
33            .into_iter()
34            .map(|addr| (addr.clone(), in_state.clone()))
35            .collect()
36    }
37    fn aexec_unop(
38        &self,
39        in_state: &mut State,
40        _opcode: &Unopcode,
41        dst: &Value,
42        _src: &Value,
43        _loc_idx: &LocIdx,
44    ) -> () {
45        in_state.set_to_bot(dst)
46    }
47    fn aexec_binop(
48        &self,
49        in_state: &mut State,
50        opcode: &Binopcode,
51        dst: &Value,
52        _src1: &Value,
53        _src2: &Value,
54        _loc_idx: &LocIdx,
55    ) -> () {
56        match opcode {
57            Binopcode::Cmp => (),
58            Binopcode::Test => (),
59            _ => in_state.set_to_bot(dst),
60        }
61    }
62
63    fn aexec(&self, in_state: &mut State, ir_instr: &Stmt, loc_idx: &LocIdx) -> () {
64        match ir_instr {
65            Stmt::Clear(dst, _srcs) => in_state.set_to_bot(dst),
66            Stmt::Unop(opcode, dst, src) => self.aexec_unop(in_state, opcode, &dst, &src, loc_idx),
67            Stmt::Binop(opcode, dst, src1, src2) => {
68                self.aexec_binop(in_state, opcode, dst, src1, src2, loc_idx);
69                in_state.adjust_stack_offset(opcode, dst, src1, src2)
70            }
71            Stmt::Call(_) => in_state.on_call(),
72            _ => (),
73        }
74    }
75
76    fn analyze_block(&self, state: &State, irblock: &IRBlock) -> State {
77        let mut new_state = state.clone();
78        for (addr, instruction) in irblock.iter() {
79            for (idx, ir_insn) in instruction.iter().enumerate() {
80                log::debug!(
81                    "Analyzing insn @ 0x{:x}: {:?}: state = {:?}",
82                    addr,
83                    ir_insn,
84                    new_state
85                );
86                self.aexec(
87                    &mut new_state,
88                    ir_insn,
89                    &LocIdx {
90                        addr: *addr,
91                        idx: idx as u32,
92                    },
93                );
94            }
95        }
96        new_state
97    }
98}
99
100fn align_succ_addrs(addr: u64, succ_addrs: Vec<u64>) -> Vec<u64> {
101    if succ_addrs.len() != 2 {
102        return succ_addrs;
103    }
104    let a1 = succ_addrs[0];
105    let a2 = succ_addrs[1];
106    if a1 < addr {
107        return vec![a2, a1];
108    }
109    if a2 < addr {
110        return vec![a1, a2];
111    }
112    if a1 < a2 {
113        return vec![a1, a2];
114    }
115    if a1 >= a2 {
116        return vec![a2, a1];
117    }
118    panic!("Unreachable");
119}
120
121pub fn run_worklist<T: AbstractAnalyzer<State>, State: VarState + Lattice + Clone>(
122    cfg: &VW_CFG,
123    irmap: &IRMap,
124    analyzer: &T,
125) -> AnalysisResult<State> {
126    let mut statemap: HashMap<u64, State> = HashMap::new();
127    let mut worklist: VecDeque<u64> = VecDeque::new();
128    worklist.push_back(cfg.entrypoint);
129    statemap.insert(cfg.entrypoint, analyzer.init_state());
130
131    while !worklist.is_empty() {
132        let addr = worklist.pop_front().unwrap();
133        let irblock = irmap.get(&addr).unwrap();
134        let state = statemap.get(&addr).unwrap();
135        let new_state = analyzer.analyze_block(state, irblock);
136        let succ_addrs_unaligned: Vec<u64> = cfg.graph.neighbors(addr).collect();
137        let succ_addrs: Vec<u64> = align_succ_addrs(addr, succ_addrs_unaligned);
138        log::debug!("Processing Block: 0x{:x} -> {:?}", addr, succ_addrs);
139        for (succ_addr, branch_state) in
140            analyzer.process_branch(irmap, &new_state, &succ_addrs, &addr)
141        {
142            let has_change = if statemap.contains_key(&succ_addr) {
143                let old_state = statemap.get(&succ_addr).unwrap();
144                let merged_state = old_state.meet(&branch_state, &LocIdx { addr: addr, idx: 0 });
145
146                if merged_state > *old_state {
147                    log::debug!("{:?} {:?}", merged_state, old_state);
148                    panic!("Meet monoticity error");
149                }
150                let has_change = *old_state != merged_state;
151                log::debug!(
152                    "At block 0x{:x}: merged input {:?}",
153                    succ_addr,
154                    merged_state
155                );
156                statemap.insert(succ_addr, merged_state);
157                has_change
158            } else {
159                log::debug!("At block 0x{:x}: new input {:?}", succ_addr, branch_state);
160                statemap.insert(succ_addr, branch_state);
161                true
162            };
163
164            if has_change && !worklist.contains(&succ_addr) {
165                worklist.push_back(succ_addr);
166            }
167        }
168    }
169    statemap
170}
veriwasm/analyses/mod.rs

veriwasm/analyses/
mod.rs
