rapx/check/opt/checking/bounds_checking/
bounds_len.rs

1use once_cell::sync::OnceCell;
2
3use rustc_ast::BinOpKind;
4use rustc_hir::{Expr, ExprKind, intravisit};
5use rustc_middle::{mir::Local, ty::TyCtxt};
6use rustc_span::Span;
7
8use crate::{analysis::dataflow::*, helpers::def_path::DefPath};
9use annotate_snippets::Level;
10
11use crate::check::opt::report::OptReport;
12
13use super::super::super::NO_STD;
14
15static DEFPATHS: OnceCell<DefPaths> = OnceCell::new();
16
17struct DefPaths {
18    ops_range: DefPath,
19    vec_len: DefPath,
20    slice_len: DefPath,
21    ops_index: DefPath,
22    ops_index_mut: DefPath,
23}
24
25impl DefPaths {
26    pub fn new(tcx: &TyCtxt<'_>) -> Self {
27        let no_std = NO_STD.lock().unwrap();
28        if *no_std {
29            Self {
30                ops_range: DefPath::new("core::ops::Range", tcx),
31                vec_len: DefPath::new("alloc::vec::Vec::len", tcx),
32                slice_len: DefPath::new("core::slice::len", tcx),
33                ops_index: DefPath::new("core::ops::Index::index", tcx),
34                ops_index_mut: DefPath::new("core::ops::IndexMut::index_mut", tcx),
35            }
36        } else {
37            Self {
38                ops_range: DefPath::new("std::ops::Range", tcx),
39                vec_len: DefPath::new("std::vec::Vec::len", tcx),
40                slice_len: DefPath::new("slice::len", tcx),
41                ops_index: DefPath::new("std::ops::Index::index", tcx),
42                ops_index_mut: DefPath::new("std::ops::IndexMut::index_mut", tcx),
43            }
44        }
45    }
46}
47
48use crate::check::opt::OptCheck;
49
50pub struct BoundsLenCheck {
51    pub record: Vec<(Local, Vec<Local>)>,
52}
53
54struct IfFinder {
55    record: Vec<(Span, Vec<Span>)>,
56}
57struct LtFinder {
58    record: Vec<Span>,
59}
60struct IndexFinder {
61    record: Vec<Span>,
62}
63
64impl intravisit::Visitor<'_> for LtFinder {
65    fn visit_expr(&mut self, ex: &Expr) {
66        if let ExprKind::Binary(op, ..) = ex.kind {
67            if op.node == BinOpKind::Lt {
68                self.record.push(ex.span);
69            }
70        }
71        intravisit::walk_expr(self, ex);
72    }
73}
74
75impl<'tcx> intravisit::Visitor<'tcx> for IfFinder {
76    fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
77        if let ExprKind::If(cond, e1, _) = ex.kind {
78            let mut lt_finder = LtFinder { record: vec![] };
79            intravisit::walk_expr(&mut lt_finder, cond);
80            if !lt_finder.record.is_empty() {
81                let mut index_finder = IndexFinder { record: vec![] };
82                intravisit::walk_expr(&mut index_finder, e1);
83                if !index_finder.record.is_empty() {
84                    self.record.push((lt_finder.record[0], index_finder.record));
85                }
86            }
87        }
88        intravisit::walk_expr(self, ex);
89    }
90}
91
92impl<'tcx> intravisit::Visitor<'tcx> for IndexFinder {
93    fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
94        if let ExprKind::Index(_, ex2, _) = ex.kind {
95            self.record.push(ex2.span);
96        }
97        intravisit::walk_expr(self, ex);
98    }
99}
100
101impl OptCheck for BoundsLenCheck {
102    fn new() -> Self {
103        Self { record: vec![] }
104    }
105
106    fn check(&mut self, graph: &Graph, tcx: &TyCtxt) {
107        DEFPATHS.get_or_init(|| DefPaths::new(tcx));
108        for (node_idx, node) in graph.nodes.iter_enumerated() {
109            if let Some(upperbound_node_idx) = extract_upperbound_node_if_ops_range(graph, node) {
110                if let Some(vec_len_node_idx) = find_upside_len_node(graph, upperbound_node_idx) {
111                    let maybe_vec_node_idx = graph.get_upside_idx(vec_len_node_idx, 0).unwrap();
112                    let maybe_vec_node_idxs =
113                        graph.collect_equivalent_locals(maybe_vec_node_idx, true);
114                    let mut index_record = vec![];
115                    for index_node_idx in find_downside_index_node(graph, node_idx).into_iter() {
116                        let maybe_vec_node_idx = graph.get_upside_idx(index_node_idx, 0).unwrap();
117                        if maybe_vec_node_idxs.contains(&maybe_vec_node_idx) {
118                            index_record.push(index_node_idx);
119                        }
120                    }
121                    if !index_record.is_empty() {
122                        self.record.push((upperbound_node_idx, index_record));
123                    }
124                }
125            }
126        }
127        let def_id = graph.def_id;
128        let body = tcx.hir_body_owned_by(def_id.as_local().unwrap());
129        let mut if_finder = IfFinder { record: vec![] };
130        intravisit::walk_body(&mut if_finder, body);
131        for (cond, slice_index_record) in if_finder.record.iter() {
132            if let Some((node_idx, node)) = graph.query_node_by_span(*cond, true) {
133                let left_arm = graph.edges[node.in_edges[0]].src;
134                let right_arm = graph.edges[node.in_edges[1]].src;
135                if find_upside_len_node(graph, right_arm).is_some() {
136                    let index_set = graph.collect_ancestor_locals(left_arm, true);
137                    let len_set = graph.collect_ancestor_locals(right_arm, true);
138                    let mut slice_node_indice = vec![];
139                    for slice_index_idx in slice_index_record {
140                        if let Some((index_node_idx, _)) =
141                            graph.query_node_by_span(*slice_index_idx, true)
142                        {
143                            let index_ancestors =
144                                graph.collect_ancestor_locals(index_node_idx, true);
145                            let indexed_node_idx =
146                                find_indexed_node_from_index(graph, index_node_idx);
147                            if let Some(indexed_node_idx) = indexed_node_idx {
148                                let indexed_ancestors =
149                                    graph.collect_ancestor_locals(indexed_node_idx, true);
150                                // Warning: We only checks index without checking the indexed value
151                                if index_ancestors.intersection(&index_set).next().is_some()
152                                    && indexed_ancestors.intersection(&len_set).next().is_some()
153                                {
154                                    slice_node_indice.push(index_node_idx);
155                                }
156                            }
157                        }
158                    }
159                    self.record.push((node_idx, slice_node_indice));
160                }
161            }
162        }
163    }
164
165    fn report(&self, graph: &Graph) {
166        for (upperbound_node_idx, index_record) in self.record.iter() {
167            report_upperbound_bug(graph, *upperbound_node_idx, index_record);
168        }
169    }
170
171    fn cnt(&self) -> usize {
172        self.record.iter().map(|(_, spans)| spans.len()).sum()
173    }
174}
175
176fn find_indexed_node_from_index(graph: &Graph, index_node_idx: Local) -> Option<Local> {
177    let def_paths = &DEFPATHS.get().unwrap();
178    let index_node = &graph.nodes[index_node_idx];
179    for edge_idx in index_node.out_edges.iter() {
180        let dst_node_idx = graph.edges[*edge_idx].dst;
181        let dst_node = &graph.nodes[dst_node_idx];
182        for op in dst_node.ops.iter() {
183            if let NodeOp::Call(def_id) = op {
184                if *def_id == def_paths.ops_index.last_def_id()
185                    || *def_id == def_paths.ops_index_mut.last_def_id()
186                {
187                    let index_operator_node =
188                        &graph.nodes[graph.edges[index_node.out_edges[0]].dst];
189
190                    return Some(graph.edges[index_operator_node.in_edges[0]].src);
191                }
192            }
193            if graph.is_marker(dst_node_idx) {
194                for edge_idx_ in dst_node.in_edges.iter() {
195                    let edge = &graph.edges[*edge_idx_];
196                    if let EdgeOp::Index = edge.op {
197                        return Some(edge.src);
198                    }
199                }
200            }
201        }
202    }
203    None
204}
205
206fn extract_upperbound_node_if_ops_range(graph: &Graph, node: &GraphNode) -> Option<Local> {
207    let def_paths = &DEFPATHS.get().unwrap();
208    let target_def_id = def_paths.ops_range.last_def_id();
209    for op in node.ops.iter() {
210        if let NodeOp::Aggregate(AggKind::Adt(def_id)) = op {
211            if *def_id == target_def_id {
212                let upperbound_edge = &graph.edges[node.in_edges[1]]; // the second field
213                return Some(upperbound_edge.src);
214            }
215        }
216    }
217    None
218}
219
220fn find_upside_len_node(graph: &Graph, node_idx: Local) -> Option<Local> {
221    let def_paths = &DEFPATHS.get().unwrap();
222    graph.find_first_node(
223        node_idx,
224        Direction::Upside,
225        &mut |graph: &Graph, idx: Local| {
226            let node = &graph.nodes[idx];
227            for op in node.ops.iter() {
228                if let NodeOp::Call(def_id) = op {
229                    if *def_id == def_paths.vec_len.last_def_id()
230                        || *def_id == def_paths.slice_len.last_def_id()
231                    {
232                        return true;
233                    }
234                }
235            }
236            false
237        },
238        &mut Graph::equivalent_edge_validator,
239    )
240}
241
242fn find_downside_index_node(graph: &Graph, node_idx: Local) -> Vec<Local> {
243    let def_paths = &DEFPATHS.get().unwrap();
244    graph.find_all_nodes(
245        node_idx,
246        Direction::Downside,
247        &mut |graph: &Graph, idx: Local| {
248            let node = &graph.nodes[idx];
249            for op in node.ops.iter() {
250                if let NodeOp::Call(def_id) = op {
251                    if *def_id == def_paths.ops_index.last_def_id()
252                        || *def_id == def_paths.ops_index_mut.last_def_id()
253                    {
254                        return true;
255                    }
256                }
257            }
258            false
259        },
260        &mut Graph::always_true_edge_validator,
261    )
262}
263
264fn report_upperbound_bug(graph: &Graph, upperbound_node_idx: Local, index_record: &Vec<Local>) {
265    let upperbound_span = graph.nodes[upperbound_node_idx].span;
266    let mut report = OptReport::from_graph(graph)
267        .title("Unnecessary bounds checkings detected")
268        .annotate(Level::Info, upperbound_span, "Index is upperbounded.");
269    for node_idx in index_record {
270        let index_span = graph.nodes[*node_idx].span;
271        report = report.annotate(Level::Error, index_span, "Checked here.");
272    }
273    report.footer("Use unsafe APIs instead.").emit();
274}
rapx/check/opt/checking/bounds_checking/bounds_len.rs

rapx/check/opt/checking/bounds_checking/
bounds_len.rs
