rapx/analysis/safedrop/
safedrop.rs

1use super::{bug_records::*, corner_case::*, drop::*, graph::*};
2use crate::{
3    analysis::core::alias_analysis::default::{MopFnAliasMap, block::Term, types::ValueKind},
4    utils::source::{get_filename, get_name},
5};
6use rustc_data_structures::fx::{FxHashMap, FxHashSet};
7use rustc_middle::{
8    mir::{
9        Operand::{self, Constant, Copy, Move},
10        Place, TerminatorKind,
11    },
12    ty::{self, TypingEnv},
13};
14use rustc_span::{Span, Symbol};
15
16pub const VISIT_LIMIT: usize = 1000;
17
18impl<'tcx> SafeDropGraph<'tcx> {
19    // analyze the drop statement and update the liveness for nodes.
20    pub fn drop_check(&mut self, bb_idx: usize) {
21        let cur_block = self.mop_graph.blocks[bb_idx].clone();
22        let is_cleanup = cur_block.is_cleanup;
23        if let Term::Drop(drop) = cur_block.terminator {
24            rap_debug!("drop check bb: {}, {:?}", bb_idx, drop);
25            match drop.kind {
26                TerminatorKind::Drop {
27                    ref place,
28                    target: _,
29                    unwind: _,
30                    replace: _,
31                    drop: _,
32                    async_fut: _,
33                } => {
34                    if !self.drop_heap_item_check(place) {
35                        return;
36                    }
37                    let value_idx = self.projection(place.clone());
38                    let info = drop.source_info.clone();
39                    self.add_to_drop_record(value_idx, bb_idx, &info, is_cleanup);
40                }
41                TerminatorKind::Call {
42                    func: _, ref args, ..
43                } => {
44                    if args.len() > 0 {
45                        let place = match args[0].node {
46                            Operand::Copy(place) => place,
47                            Operand::Move(place) => place,
48                            _ => {
49                                rap_error!("Constant operand exists: {:?}", args[0]);
50                                return;
51                            }
52                        };
53                        if !self.drop_heap_item_check(&place) {
54                            return;
55                        }
56                        let local = self.projection(place.clone());
57                        let info = drop.source_info.clone();
58                        self.add_to_drop_record(local, bb_idx, &info, is_cleanup);
59                    }
60                }
61                _ => {}
62            }
63        }
64    }
65
66    pub fn drop_heap_item_check(&self, place: &Place<'tcx>) -> bool {
67        let tcx = self.mop_graph.tcx;
68        let place_ty = place.ty(&tcx.optimized_mir(self.mop_graph.def_id).local_decls, tcx);
69        match place_ty.ty.kind() {
70            ty::TyKind::Adt(adtdef, ..) => match self.adt_owner.get(&adtdef.did()) {
71                None => true,
72                Some(owenr_unit) => {
73                    let idx = match place_ty.variant_index {
74                        Some(vdx) => vdx.index(),
75                        None => 0,
76                    };
77                    if owenr_unit[idx].0.is_onheap() || owenr_unit[idx].1.contains(&true) {
78                        true
79                    } else {
80                        false
81                    }
82                }
83            },
84            _ => true,
85        }
86    }
87
88    pub fn split_check(&mut self, bb_idx: usize, fn_map: &MopFnAliasMap) {
89        /* duplicate the status before visiteding a path; */
90        let backup_values = self.mop_graph.values.clone(); // duplicate the status when visiteding different paths;
91        let backup_constant = self.mop_graph.constants.clone();
92        let backup_alias_sets = self.mop_graph.alias_sets.clone();
93        let backup_drop_record = self.drop_record.clone();
94        self.check(bb_idx, fn_map);
95        /* restore after visited */
96        self.mop_graph.values = backup_values;
97        self.mop_graph.constants = backup_constant;
98        self.mop_graph.alias_sets = backup_alias_sets;
99        self.drop_record = backup_drop_record;
100    }
101
102    pub fn split_check_with_cond(
103        &mut self,
104        bb_idx: usize,
105        path_discr_id: usize,
106        path_discr_val: usize,
107        fn_map: &MopFnAliasMap,
108    ) {
109        /* duplicate the status before visiteding a path; */
110        let backup_values = self.mop_graph.values.clone(); // duplicate the status when visiteding different paths;
111        let backup_constant = self.mop_graph.constants.clone();
112        let backup_alias_sets = self.mop_graph.alias_sets.clone();
113        let backup_drop_record = self.drop_record.clone();
114        /* add control-sensitive indicator to the path status */
115        self.mop_graph
116            .constants
117            .insert(path_discr_id, path_discr_val);
118        self.check(bb_idx, fn_map);
119        /* restore after visited */
120        self.mop_graph.values = backup_values;
121        self.mop_graph.constants = backup_constant;
122        self.mop_graph.alias_sets = backup_alias_sets;
123        self.drop_record = backup_drop_record;
124    }
125
126    // the core function of the safedrop.
127    pub fn check(&mut self, bb_idx: usize, fn_map: &MopFnAliasMap) {
128        self.mop_graph.visit_times += 1;
129        if self.mop_graph.visit_times > VISIT_LIMIT {
130            return;
131        }
132        let scc_idx = self.mop_graph.blocks[bb_idx].scc.enter;
133        let cur_block = self.mop_graph.blocks[bb_idx].clone();
134        rap_debug!(
135            "Checking bb: {}, scc_idx: {}, scc: {:?}",
136            bb_idx,
137            scc_idx,
138            cur_block.scc.clone(),
139        );
140
141        if bb_idx == scc_idx && !cur_block.scc.nodes.is_empty() {
142            rap_debug!("check {:?} as a scc", bb_idx);
143            self.check_scc(bb_idx, fn_map);
144        } else {
145            self.check_single_node(bb_idx, fn_map);
146            self.handle_nexts(bb_idx, fn_map, None, None);
147        }
148    }
149
150    pub fn check_scc(&mut self, bb_idx: usize, fn_map: &MopFnAliasMap) {
151        let cur_block = self.mop_graph.blocks[bb_idx].clone();
152        /* Handle cases if the current block is a merged scc block with sub block */
153        let scc_tree = self.mop_graph.sort_scc_tree(&cur_block.scc);
154        let paths_in_scc =
155            self.mop_graph
156                .find_scc_paths(bb_idx, &scc_tree, &mut FxHashMap::default());
157        rap_debug!("Paths in scc: {:?}", paths_in_scc);
158
159        let backup_values = self.mop_graph.values.clone(); // duplicate the status when visiteding different paths;
160        let backup_constant = self.mop_graph.constants.clone();
161        let backup_alias_sets = self.mop_graph.alias_sets.clone();
162        let backup_drop_record = self.drop_record.clone();
163        for raw_path in &paths_in_scc {
164            let path = &raw_path.0;
165            let path_constants = &raw_path.1;
166
167            if !path.is_empty() {
168                for idx in &path[..path.len() - 1] {
169                    self.alias_bb(*idx);
170                    self.alias_bbcall(*idx, fn_map);
171                    self.drop_check(*idx);
172                }
173            }
174            // The last node is already ouside the scc.
175            if let Some(&last_node) = path.last() {
176                if self.mop_graph.blocks[last_node].scc.nodes.is_empty() {
177                    self.check_single_node(last_node, fn_map);
178                    self.handle_nexts(last_node, fn_map, None, Some(path_constants));
179                } else {
180                    // TODO
181                }
182            }
183            self.mop_graph.alias_sets = backup_alias_sets.clone();
184            self.mop_graph.values = backup_values.clone();
185            self.mop_graph.constants = backup_constant.clone();
186            self.drop_record = backup_drop_record.clone();
187        }
188    }
189
190    pub fn check_single_node(&mut self, bb_idx: usize, fn_map: &MopFnAliasMap) {
191        let cur_block = self.mop_graph.blocks[bb_idx].clone();
192        rap_debug!("check {:?} as a node", bb_idx);
193        self.alias_bb(bb_idx);
194        self.alias_bbcall(bb_idx, fn_map);
195        self.drop_check(bb_idx);
196
197        // For dangling pointer check;
198        // Since a node within an SCC cannot be an exit, we only check for non-scc nodes;
199        if cur_block.next.is_empty() {
200            if should_check(self.mop_graph.def_id) {
201                self.dp_check(cur_block.is_cleanup);
202            }
203        }
204    }
205
206    pub fn handle_nexts(
207        &mut self,
208        bb_idx: usize,
209        fn_map: &MopFnAliasMap,
210        exclusive_nodes: Option<&FxHashSet<usize>>,
211        path_constraints: Option<&FxHashMap<usize, usize>>,
212    ) {
213        let cur_block = self.mop_graph.blocks[bb_idx].clone();
214        let tcx = self.mop_graph.tcx;
215
216        // Extra path contraints are introduced during scc handling.
217        if let Some(path_constants) = path_constraints {
218            self.mop_graph.constants.extend(path_constants);
219        }
220
221        /* Begin: handle the SwitchInt statement. */
222        let mut single_target = false;
223        let mut sw_val = 0;
224        let mut sw_target = 0; // Single target
225        let mut path_discr_id = 0; // To avoid analyzing paths that cannot be reached with one enum type.
226        let mut sw_targets = None; // Multiple targets of SwitchInt
227        if let Term::Switch(switch) = &cur_block.terminator {
228            rap_debug!("Handle switchInt in bb {:?}", cur_block);
229            if let TerminatorKind::SwitchInt {
230                ref discr,
231                ref targets,
232            } = switch.kind
233            {
234                rap_debug!("{:?}", switch);
235                rap_debug!("{:?}", self.mop_graph.constants);
236                match discr {
237                    Copy(p) | Move(p) => {
238                        let value_idx = self.projection(*p);
239                        let local_decls = &tcx.optimized_mir(self.mop_graph.def_id).local_decls;
240                        let place_ty = (*p).ty(local_decls, tcx);
241                        rap_debug!("value_idx: {:?}", value_idx);
242                        match place_ty.ty.kind() {
243                            ty::TyKind::Bool => {
244                                rap_debug!("SwitchInt via Bool");
245                                if let Some(constant) = self.mop_graph.constants.get(&value_idx) {
246                                    if *constant != usize::MAX {
247                                        single_target = true;
248                                        sw_val = *constant;
249                                    }
250                                }
251                                path_discr_id = value_idx;
252                                sw_targets = Some(targets.clone());
253                            }
254                            _ => {
255                                if let Some(father) = self
256                                    .mop_graph
257                                    .discriminants
258                                    .get(&self.mop_graph.values[value_idx].local)
259                                {
260                                    if let Some(constant) = self.mop_graph.constants.get(father) {
261                                        if *constant != usize::MAX {
262                                            single_target = true;
263                                            sw_val = *constant;
264                                        }
265                                    }
266                                    if self.mop_graph.values[value_idx].local == value_idx {
267                                        path_discr_id = *father;
268                                        sw_targets = Some(targets.clone());
269                                    }
270                                }
271                            }
272                        }
273                    }
274                    Constant(c) => {
275                        single_target = true;
276                        let ty_env = TypingEnv::post_analysis(tcx, self.mop_graph.def_id);
277                        if let Some(val) = c.const_.try_eval_target_usize(tcx, ty_env) {
278                            sw_val = val as usize;
279                        }
280                    }
281                }
282                if single_target {
283                    /* Find the target based on the value;
284                     * Since sw_val is a const, only one target is reachable.
285                     * Filed 0 is the value; field 1 is the real target.
286                     */
287                    for iter in targets.iter() {
288                        if iter.0 as usize == sw_val {
289                            sw_target = iter.1.as_usize();
290                            break;
291                        }
292                    }
293                    /* No target found, choose the default target.
294                     * The default targets is not included within the iterator.
295                     * We can only obtain the default target based on the last item of all_targets().
296                     */
297                    if sw_target == 0 {
298                        let all_target = targets.all_targets();
299                        sw_target = all_target[all_target.len() - 1].as_usize();
300                    }
301                }
302            }
303        }
304        /* End: finish handling SwitchInt */
305        // fixed path since a constant switchInt value
306        if single_target {
307            match exclusive_nodes {
308                Some(exclusive) => {
309                    if !exclusive.contains(&sw_target) {
310                        self.check(sw_target, fn_map);
311                    }
312                }
313                None => {
314                    self.check(sw_target, fn_map);
315                }
316            }
317        } else {
318            // Other cases in switchInt terminators
319            if let Some(targets) = sw_targets {
320                for iter in targets.iter() {
321                    if self.mop_graph.visit_times > VISIT_LIMIT {
322                        continue;
323                    }
324                    let next = iter.1.as_usize();
325
326                    match exclusive_nodes {
327                        Some(exclusive) => {
328                            if exclusive.contains(&next) {
329                                continue;
330                            }
331                        }
332                        None => {}
333                    }
334                    let path_discr_val = iter.0 as usize;
335                    self.split_check_with_cond(next, path_discr_id, path_discr_val, fn_map);
336                }
337                let all_targets = targets.all_targets();
338                let next_idx = all_targets[all_targets.len() - 1].as_usize();
339                let path_discr_val = usize::MAX; // to indicate the default path;
340                self.split_check_with_cond(next_idx, path_discr_id, path_discr_val, fn_map);
341            } else {
342                for next in &cur_block.next {
343                    if self.mop_graph.visit_times > VISIT_LIMIT {
344                        continue;
345                    }
346
347                    match exclusive_nodes {
348                        Some(exclusive) => {
349                            if exclusive.contains(&next) {
350                                continue;
351                            }
352                        }
353                        None => {}
354                    }
355                    self.split_check(*next, fn_map);
356                }
357            }
358        }
359    }
360    pub fn report_bugs(&self) {
361        rap_debug!(
362            "report bugs, id: {:?}, uaf: {:?}",
363            self.mop_graph.def_id,
364            self.bug_records.uaf_bugs
365        );
366        let filename = get_filename(self.mop_graph.tcx, self.mop_graph.def_id);
367        match filename {
368            Some(filename) => {
369                if filename.contains(".cargo") {
370                    return;
371                }
372            }
373            None => {}
374        }
375        if self.bug_records.is_bug_free() {
376            return;
377        }
378        let fn_name = match get_name(self.mop_graph.tcx, self.mop_graph.def_id) {
379            Some(name) => name,
380            None => Symbol::intern("no symbol available"),
381        };
382        let body = self.mop_graph.tcx.optimized_mir(self.mop_graph.def_id);
383        self.bug_records
384            .df_bugs_output(body, fn_name, self.mop_graph.span);
385        self.bug_records
386            .uaf_bugs_output(body, fn_name, self.mop_graph.span);
387        self.bug_records
388            .dp_bug_output(body, fn_name, self.mop_graph.span);
389        /*
390        let _ = generate_mir_cfg_dot(
391            self.mop_graph.tcx,
392            self.mop_graph.def_id,
393            &self.mop_graph.alias_sets,
394        );
395        */
396    }
397
398    pub fn uaf_check(&mut self, value_idx: usize, bb_idx: usize, span: Span, is_fncall: bool) {
399        let local = self.mop_graph.values[value_idx].local;
400        rap_debug!(
401            "uaf_check, idx: {:?}, local: {:?}, drop_record: {:?}",
402            value_idx,
403            local,
404            self.drop_record[value_idx],
405        );
406
407        if !self.mop_graph.values[value_idx].may_drop {
408            return;
409        }
410        if self.mop_graph.values[value_idx].is_ptr() && !is_fncall {
411            return;
412        }
413
414        self.fetch_drop_info(value_idx);
415
416        let mut fully_dropped = true;
417        if !self.drop_record[value_idx].is_dropped {
418            fully_dropped = false;
419            if !self.drop_record[value_idx].has_dropped_field {
420                return;
421            }
422        }
423
424        let kind = self.mop_graph.values[value_idx].kind;
425        let confidence = Self::rate_confidence(kind, fully_dropped);
426
427        let bug = TyBug {
428            drop_spot: self.drop_record[value_idx].drop_spot,
429            trigger_info: LocalSpot::new(bb_idx, local),
430            prop_chain: self.drop_record[value_idx].prop_chain.clone(),
431            span: span.clone(),
432            confidence,
433        };
434        if self.bug_records.uaf_bugs.contains_key(&local) {
435            return;
436        }
437        rap_warn!("Find a use-after-free bug {:?}; add to records", bug);
438        self.bug_records.uaf_bugs.insert(local, bug);
439    }
440
441    pub fn rate_confidence(kind: ValueKind, fully_dropped: bool) -> usize {
442        let confidence = match (kind, fully_dropped) {
443            (ValueKind::SpecialPtr, _) => 0,
444            (_, true) => 99,
445            (_, false) => 50,
446        };
447        confidence
448    }
449
450    pub fn df_check(
451        &mut self,
452        value_idx: usize,
453        bb_idx: usize,
454        span: Span,
455        flag_cleanup: bool,
456    ) -> bool {
457        let local = self.mop_graph.values[value_idx].local;
458        // If the value has not been dropped, it is not a double free.
459        rap_debug!(
460            "df_check: value_idx = {:?}, bb_idx = {:?}, alias_sets: {:?}",
461            value_idx,
462            bb_idx,
463            self.mop_graph.alias_sets,
464        );
465        self.fetch_drop_info(value_idx);
466        let mut fully_dropped = true;
467        if !self.drop_record[value_idx].is_dropped {
468            fully_dropped = false;
469            if !self.drop_record[value_idx].has_dropped_field {
470                return false;
471            }
472        }
473        let kind = self.mop_graph.values[value_idx].kind;
474        let confidence = Self::rate_confidence(kind, fully_dropped);
475
476        let bug = TyBug {
477            drop_spot: self.drop_record[value_idx].drop_spot,
478            trigger_info: LocalSpot::new(bb_idx, local),
479            prop_chain: self.drop_record[value_idx].prop_chain.clone(),
480            span: span.clone(),
481            confidence,
482        };
483
484        for item in &self.drop_record {
485            rap_debug!("drop_spot: {:?}", item);
486        }
487        if flag_cleanup {
488            if !self.bug_records.df_bugs_unwind.contains_key(&local) {
489                self.bug_records.df_bugs_unwind.insert(local, bug);
490                rap_info!(
491                    "Find a double free bug {} during unwinding; add to records.",
492                    local
493                );
494            }
495        } else {
496            if !self.bug_records.df_bugs.contains_key(&local) {
497                self.bug_records.df_bugs.insert(local, bug);
498                rap_info!("Find a double free bug {}; add to records.", local);
499            }
500        }
501        return true;
502    }
503
504    pub fn dp_check(&mut self, flag_cleanup: bool) {
505        rap_debug!("dangling pointer check");
506        rap_debug!("current alias sets: {:?}", self.mop_graph.alias_sets);
507        if flag_cleanup {
508            for arg_idx in 1..self.mop_graph.arg_size + 1 {
509                if !self.mop_graph.values[arg_idx].is_ptr() {
510                    continue;
511                }
512                self.fetch_drop_info(arg_idx);
513                let mut fully_dropped = true;
514                if !self.drop_record[arg_idx].is_dropped {
515                    fully_dropped = false;
516                    if !self.drop_record[arg_idx].has_dropped_field {
517                        continue;
518                    }
519                }
520                let kind = self.mop_graph.values[arg_idx].kind;
521                let confidence = Self::rate_confidence(kind, fully_dropped);
522                let bug = TyBug {
523                    drop_spot: self.drop_record[arg_idx].drop_spot,
524                    trigger_info: LocalSpot::from_local(arg_idx),
525                    prop_chain: self.drop_record[arg_idx].prop_chain.clone(),
526                    span: self.mop_graph.span.clone(),
527                    confidence,
528                };
529                self.bug_records.dp_bugs_unwind.insert(arg_idx, bug);
530                rap_info!(
531                    "Find a dangling pointer {} during unwinding; add to record.",
532                    arg_idx
533                );
534            }
535        } else {
536            if self.mop_graph.values[0].may_drop
537                && (self.drop_record[0].is_dropped || self.drop_record[0].has_dropped_field)
538            {
539                self.fetch_drop_info(0);
540                let mut fully_dropped = true;
541                if !self.drop_record[0].is_dropped {
542                    fully_dropped = false;
543                }
544
545                let kind = self.mop_graph.values[0].kind;
546                let confidence = Self::rate_confidence(kind, fully_dropped);
547                let bug = TyBug {
548                    drop_spot: self.drop_record[0].drop_spot,
549                    trigger_info: LocalSpot::from_local(0),
550                    prop_chain: self.drop_record[0].prop_chain.clone(),
551                    span: self.mop_graph.span.clone(),
552                    confidence,
553                };
554                self.bug_records.dp_bugs.insert(0, bug);
555                rap_info!("Find a dangling pointer 0; add to record.");
556            } else {
557                for arg_idx in 0..self.mop_graph.arg_size + 1 {
558                    if !self.mop_graph.values[arg_idx].is_ptr() {
559                        continue;
560                    }
561                    self.fetch_drop_info(arg_idx);
562                    let mut fully_dropped = true;
563                    if !self.drop_record[arg_idx].is_dropped {
564                        fully_dropped = false;
565                        if !self.drop_record[arg_idx].has_dropped_field {
566                            continue;
567                        }
568                    }
569                    let kind = self.mop_graph.values[arg_idx].kind;
570                    let confidence = Self::rate_confidence(kind, fully_dropped);
571                    let bug = TyBug {
572                        drop_spot: self.drop_record[arg_idx].drop_spot,
573                        trigger_info: LocalSpot::from_local(arg_idx),
574                        prop_chain: self.drop_record[arg_idx].prop_chain.clone(),
575                        span: self.mop_graph.span.clone(),
576                        confidence,
577                    };
578                    self.bug_records.dp_bugs.insert(arg_idx, bug);
579                    rap_info!("Find a dangling pointer {}; add to record.", arg_idx);
580                }
581            }
582        }
583    }
584}
rapx/analysis/safedrop/safedrop.rs

rapx/analysis/safedrop/
safedrop.rs
