rapx/analysis/rcanary/
ranalyzer.rs

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

rapx/analysis/rcanary/
ranalyzer.rs
