rapx/check/rcanary/
ranalyzer.rs

1pub mod intra_visitor;
2pub mod order;
3pub mod ownership;
4
5use rustc_middle::{
6    mir::{Body, Terminator},
7    ty::{InstanceKind::Item, TyCtxt},
8};
9use rustc_span::def_id::DefId;
10
11use super::{IcxMut, IcxSliceMut, Rcx, RcxMut, rCanary};
12use crate::analysis::heap_ownership::{
13    HeapOwnership, HeapOwnershipResultMap, default::TyWithIndex,
14};
15use ownership::{IntraVar, Taint};
16
17use std::{
18    collections::{HashMap, HashSet},
19    env,
20    fmt::{Debug, Formatter},
21};
22
23pub type MirGraph = HashMap<DefId, Graph>;
24pub type ToPo = Vec<usize>;
25pub type Edges = Vec<Vec<usize>>;
26
27#[derive(Debug, Clone)]
28pub struct Graph {
29    e: Edges,
30    pre: Edges,
31    topo: ToPo,
32}
33
34impl Default for Graph {
35    fn default() -> Self {
36        Self {
37            e: Vec::default(),
38            pre: Vec::default(),
39            topo: Vec::default(),
40        }
41    }
42}
43
44impl Graph {
45    pub fn new(len: usize) -> Self {
46        Graph {
47            e: vec![Vec::new(); len],
48            pre: vec![Vec::new(); len],
49            topo: Vec::new(),
50        }
51    }
52
53    pub fn get_edges_mut(&mut self) -> &mut Edges {
54        &mut self.e
55    }
56
57    pub fn get_pre_mut(&mut self) -> &mut Edges {
58        &mut self.pre
59    }
60
61    pub fn get_topo(&self) -> &ToPo {
62        &self.topo
63    }
64
65    pub fn get_topo_mut(&mut self) -> &mut ToPo {
66        &mut self.topo
67    }
68}
69
70pub struct FlowAnalysis<'tcx, 'a> {
71    rcx: &'a mut rCanary<'tcx>,
72    fn_set: HashSet<DefId>,
73}
74
75impl<'tcx, 'a> FlowAnalysis<'tcx, 'a> {
76    pub fn new(rcx: &'a mut rCanary<'tcx>) -> Self {
77        Self {
78            rcx,
79            fn_set: HashSet::new(),
80        }
81    }
82
83    pub fn fn_set(&self) -> &HashSet<DefId> {
84        &self.fn_set
85    }
86
87    pub fn fn_set_mut(&mut self) -> &mut HashSet<DefId> {
88        &mut self.fn_set
89    }
90
91    pub fn mir_graph(&self) -> &MirGraph {
92        self.rcx().mir_graph()
93    }
94
95    pub fn mir_graph_mut(&mut self) -> &mut MirGraph {
96        self.rcx_mut().mir_graph_mut()
97    }
98
99    pub fn start(&mut self) {
100        // this phase determines the final order of all basic blocks for us to visit
101        // Note: we will not visit the clean-up blocks (unwinding)
102        self.order();
103        // this phase will generate the Intra procedural visitor for us to visit the block
104        self.intra_run();
105    }
106}
107
108impl<'tcx, 'o, 'a> RcxMut<'tcx, 'o, 'a> for FlowAnalysis<'tcx, 'a> {
109    #[inline(always)]
110    fn rcx(&'o self) -> &'o rCanary<'tcx> {
111        self.rcx
112    }
113
114    #[inline(always)]
115    fn rcx_mut(&'o mut self) -> &'o mut rCanary<'tcx> {
116        self.rcx
117    }
118
119    #[inline(always)]
120    fn tcx(&'o self) -> TyCtxt<'tcx> {
121        self.rcx().tcx()
122    }
123}
124
125#[derive(Clone, Debug)]
126pub struct NodeOrder<'tcx> {
127    body: &'tcx Body<'tcx>,
128    graph: Graph,
129}
130
131impl<'tcx> NodeOrder<'tcx> {
132    pub fn new(body: &'tcx Body<'tcx>) -> Self {
133        let len = body.basic_blocks.len();
134        Self {
135            body,
136            graph: Graph::new(len),
137        }
138    }
139
140    #[inline(always)]
141    pub fn body(&self) -> &'tcx Body<'tcx> {
142        self.body
143    }
144
145    #[inline(always)]
146    pub fn graph(&self) -> &Graph {
147        &self.graph
148    }
149
150    #[inline(always)]
151    pub fn graph_mut(&mut self) -> &mut Graph {
152        &mut self.graph
153    }
154}
155
156struct IntraFlowAnalysis<'tcx, 'z3, 'a> {
157    pub rcx: &'a rCanary<'tcx>,
158    icx: IntraFlowContext<'tcx, 'z3>,
159    icx_slice: IcxSliceFroBlock<'tcx, 'z3>,
160    pub def_id: DefId,
161    pub body: &'a Body<'tcx>,
162    pub graph: &'a Graph,
163    taint_flag: bool,
164    taint_source: Vec<Terminator<'tcx>>,
165}
166
167impl<'tcx, 'z3, 'a> IntraFlowAnalysis<'tcx, 'z3, 'a> {
168    pub fn new(
169        rcx: &'a rCanary<'tcx>,
170        def_id: DefId,
171        //unique: &'a mut HashSet<DefId>,
172    ) -> Self {
173        let body = rcx.tcx.instance_mir(Item(def_id));
174        let v_len = body.local_decls.len();
175        let b_len = body.basic_blocks.len();
176        let graph = rcx.mir_graph().get(&def_id).unwrap();
177
178        Self {
179            rcx,
180            icx: IntraFlowContext::new(b_len, v_len),
181            icx_slice: IcxSliceFroBlock::new_for_block_0(v_len),
182            def_id,
183            body,
184            graph,
185            taint_flag: false,
186            taint_source: Vec::default(),
187        }
188    }
189
190    pub fn owner(&self) -> &HeapOwnershipResultMap {
191        self.rcx.adt_owner()
192    }
193
194    pub fn add_taint(&mut self, terminator: Terminator<'tcx>) {
195        self.taint_source.push(terminator);
196    }
197}
198
199impl<'tcx, 'z3, 'o, 'a> Rcx<'tcx, 'o, 'a> for IntraFlowAnalysis<'tcx, 'z3, 'a> {
200    #[inline(always)]
201    fn rcx(&'o self) -> &'a rCanary<'tcx> {
202        self.rcx
203    }
204
205    #[inline(always)]
206    fn tcx(&'o self) -> TyCtxt<'tcx> {
207        self.rcx.tcx()
208    }
209}
210
211impl<'tcx, 'z3, 'o, 'a> IcxMut<'tcx, 'z3, 'o> for IntraFlowAnalysis<'tcx, 'z3, 'a> {
212    #[inline(always)]
213    fn icx(&'o self) -> &'o IntraFlowContext<'tcx, 'z3> {
214        &self.icx
215    }
216
217    #[inline(always)]
218    fn icx_mut(&'o mut self) -> &'o mut IntraFlowContext<'tcx, 'z3> {
219        &mut self.icx
220    }
221}
222
223impl<'tcx, 'z3, 'o, 'a> IcxSliceMut<'tcx, 'z3, 'o> for IntraFlowAnalysis<'tcx, 'z3, 'a> {
224    #[inline(always)]
225    fn icx_slice(&'o self) -> &'o IcxSliceFroBlock<'tcx, 'z3> {
226        &self.icx_slice
227    }
228
229    #[inline(always)]
230    fn icx_slice_mut(&'o mut self) -> &'o mut IcxSliceFroBlock<'tcx, 'z3> {
231        &mut self.icx_slice
232    }
233}
234
235#[derive(Debug, Clone)]
236pub struct IntraFlowContext<'tcx, 'z3> {
237    taint: IOPairForGraph<Taint<'tcx>>,
238    var: IOPairForGraph<IntraVar<'z3>>,
239    len: IOPairForGraph<usize>,
240    // the ty in icx is the Rust ownership layout of the pointing instance
241    // Note: the ty is not the exact ty of the local
242    ty: IOPairForGraph<TyWithIndex<'tcx>>,
243    layout: IOPairForGraph<Vec<HeapOwnership>>,
244}
245
246impl<'tcx, 'z3, 'icx> IntraFlowContext<'tcx, 'z3> {
247    pub fn new(b_len: usize, v_len: usize) -> Self {
248        Self {
249            taint: IOPairForGraph::new(b_len, v_len),
250            var: IOPairForGraph::new(b_len, v_len),
251            len: IOPairForGraph::new(b_len, v_len),
252            ty: IOPairForGraph::new(b_len, v_len),
253            layout: IOPairForGraph::new(b_len, v_len),
254        }
255    }
256
257    pub fn taint(&self) -> &IOPairForGraph<Taint<'tcx>> {
258        &self.taint
259    }
260
261    pub fn taint_mut(&mut self) -> &mut IOPairForGraph<Taint<'tcx>> {
262        &mut self.taint
263    }
264
265    pub fn var(&self) -> &IOPairForGraph<IntraVar<'z3>> {
266        &self.var
267    }
268
269    pub fn var_mut(&mut self) -> &mut IOPairForGraph<IntraVar<'z3>> {
270        &mut self.var
271    }
272
273    pub fn len(&self) -> &IOPairForGraph<usize> {
274        &self.len
275    }
276
277    pub fn len_mut(&mut self) -> &mut IOPairForGraph<usize> {
278        &mut self.len
279    }
280
281    pub fn ty(&self) -> &IOPairForGraph<TyWithIndex<'tcx>> {
282        &self.ty
283    }
284
285    pub fn ty_mut(&mut self) -> &mut IOPairForGraph<TyWithIndex<'tcx>> {
286        &mut self.ty
287    }
288
289    pub fn layout(&self) -> &IOPairForGraph<Vec<HeapOwnership>> {
290        &self.layout
291    }
292
293    pub fn layout_mut(&mut self) -> &mut IOPairForGraph<Vec<HeapOwnership>> {
294        &mut self.layout
295    }
296
297    pub fn derive_from_pre_node(&mut self, from: usize, to: usize) {
298        // derive the storage from the pre node
299        *self.taint_mut().get_g_mut()[to].get_i_mut() =
300            self.taint_mut().get_g_mut()[from].get_o_mut().clone();
301
302        // derive the var vector from the pre node
303        *self.var_mut().get_g_mut()[to].get_i_mut() =
304            self.var_mut().get_g_mut()[from].get_o_mut().clone();
305
306        // derive the len vector from the pre node
307        *self.len_mut().get_g_mut()[to].get_i_mut() =
308            self.len_mut().get_g_mut()[from].get_o_mut().clone();
309
310        // derive the ty vector from the pre node
311        *self.ty_mut().get_g_mut()[to].get_i_mut() =
312            self.ty_mut().get_g_mut()[from].get_o_mut().clone();
313
314        // derive the layout vector from the pre node
315        *self.layout_mut().get_g_mut()[to].get_i_mut() =
316            self.layout_mut().get_g_mut()[from].get_o_mut().clone();
317    }
318
319    pub fn derive_from_icx_slice(&mut self, from: IcxSliceFroBlock<'tcx, 'z3>, to: usize) {
320        *self.taint_mut().get_g_mut()[to].get_o_mut() = from.taint;
321
322        *self.var_mut().get_g_mut()[to].get_o_mut() = from.var;
323
324        *self.len_mut().get_g_mut()[to].get_o_mut() = from.len;
325
326        *self.ty_mut().get_g_mut()[to].get_o_mut() = from.ty;
327
328        *self.layout_mut().get_g_mut()[to].get_o_mut() = from.layout;
329    }
330}
331
332#[derive(Debug, Clone, Default)]
333pub struct InOutPair<T: Debug + Clone + Default> {
334    i: Vec<T>,
335    o: Vec<T>,
336}
337
338impl<T> InOutPair<T>
339where
340    T: Debug + Clone + Default,
341{
342    pub fn new(len: usize) -> Self {
343        Self {
344            i: vec![T::default(); len],
345            o: vec![T::default(); len],
346        }
347    }
348
349    pub fn get_i_mut(&mut self) -> &mut Vec<T> {
350        &mut self.i
351    }
352
353    pub fn get_o_mut(&mut self) -> &mut Vec<T> {
354        &mut self.o
355    }
356
357    pub fn len(&self) -> usize {
358        self.i.len()
359    }
360}
361
362#[derive(Debug, Clone, Default)]
363pub struct IOPairForGraph<T: Debug + Clone + Default> {
364    pair_graph: Vec<InOutPair<T>>,
365}
366
367impl<T> IOPairForGraph<T>
368where
369    T: Debug + Clone + Default,
370{
371    pub fn new(b_len: usize, v_len: usize) -> Self {
372        Self {
373            pair_graph: vec![InOutPair::new(v_len); b_len],
374        }
375    }
376
377    pub fn get_g_mut(&mut self) -> &mut Vec<InOutPair<T>> {
378        &mut self.pair_graph
379    }
380}
381
382#[derive(Clone, Default)]
383pub struct IcxSliceFroBlock<'tcx, 'z3> {
384    taint: Vec<Taint<'tcx>>,
385    var: Vec<IntraVar<'z3>>,
386    len: Vec<usize>,
387    // the ty in icx is the Rust ownership layout of the pointing instance
388    // Note: the ty is not the exact ty of the local
389    ty: Vec<TyWithIndex<'tcx>>,
390    layout: Vec<Vec<HeapOwnership>>,
391}
392
393impl<'tcx, 'z3> IcxSliceFroBlock<'tcx, 'z3> {
394    pub fn new_in(icx: &mut IntraFlowContext<'tcx, 'z3>, idx: usize) -> Self {
395        Self {
396            taint: icx.taint_mut().get_g_mut()[idx].get_i_mut().clone(),
397            var: icx.var_mut().get_g_mut()[idx].get_i_mut().clone(),
398            len: icx.len_mut().get_g_mut()[idx].get_i_mut().clone(),
399            ty: icx.ty_mut().get_g_mut()[idx].get_i_mut().clone(),
400            layout: icx.layout_mut().get_g_mut()[idx].get_i_mut().clone(),
401        }
402    }
403
404    pub fn new_out(icx: &mut IntraFlowContext<'tcx, 'z3>, idx: usize) -> Self {
405        Self {
406            taint: icx.taint_mut().get_g_mut()[idx].get_o_mut().clone(),
407            var: icx.var_mut().get_g_mut()[idx].get_o_mut().clone(),
408            len: icx.len_mut().get_g_mut()[idx].get_o_mut().clone(),
409            ty: icx.ty_mut().get_g_mut()[idx].get_o_mut().clone(),
410            layout: icx.layout_mut().get_g_mut()[idx].get_o_mut().clone(),
411        }
412    }
413
414    pub fn new_for_block_0(len: usize) -> Self {
415        Self {
416            taint: vec![Taint::default(); len],
417            var: vec![IntraVar::default(); len],
418            len: vec![0; len],
419            ty: vec![TyWithIndex::default(); len],
420            layout: vec![Vec::new(); len],
421        }
422    }
423
424    pub fn taint(&self) -> &Vec<Taint<'tcx>> {
425        &self.taint
426    }
427
428    pub fn taint_mut(&mut self) -> &mut Vec<Taint<'tcx>> {
429        &mut self.taint
430    }
431
432    pub fn var(&self) -> &Vec<IntraVar<'z3>> {
433        &self.var
434    }
435
436    pub fn var_mut(&mut self) -> &mut Vec<IntraVar<'z3>> {
437        &mut self.var
438    }
439
440    pub fn len(&self) -> &Vec<usize> {
441        &self.len
442    }
443
444    pub fn len_mut(&mut self) -> &mut Vec<usize> {
445        &mut self.len
446    }
447
448    pub fn ty(&self) -> &Vec<TyWithIndex<'tcx>> {
449        &self.ty
450    }
451
452    pub fn ty_mut(&mut self) -> &mut Vec<TyWithIndex<'tcx>> {
453        &mut self.ty
454    }
455
456    pub fn layout(&self) -> &Vec<Vec<HeapOwnership>> {
457        &self.layout
458    }
459
460    pub fn layout_mut(&mut self) -> &mut Vec<Vec<HeapOwnership>> {
461        &mut self.layout
462    }
463
464    pub fn taint_merge(&mut self, another: &IcxSliceFroBlock<'tcx, 'z3>, u: usize) {
465        if another.taint()[u].is_untainted() {
466            return;
467        }
468
469        if self.taint()[u].is_untainted() {
470            self.taint_mut()[u] = another.taint()[u].clone();
471        } else {
472            for elem in another.taint()[u].set().clone() {
473                self.taint_mut()[u].insert(elem);
474            }
475        }
476    }
477}
478
479impl<'tcx, 'z3> Debug for IcxSliceFroBlock<'tcx, 'z3> {
480    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
481        write!(
482            f,
483            "IcxSliceForBlock\n     {:?}\n     {:?}\n     {:?}\n     {:?}\n     {:?}",
484            self.taint(),
485            self.len(),
486            self.var(),
487            self.layout(),
488            self.ty(),
489        )
490    }
491}
492
493#[derive(Debug, Copy, Clone, Hash)]
494pub enum Z3GoalDisplay {
495    Verbose,
496    Disabled,
497}
498
499pub fn is_z3_goal_verbose() -> bool {
500    env::var_os("Z3").is_some()
501}
rapx/check/rcanary/ranalyzer.rs

rapx/check/rcanary/
ranalyzer.rs
