rapx/analysis/rcanary/
ranalyzer.rs

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

rapx/analysis/rcanary/
ranalyzer.rs
