rapx/verify/call_summary/
interprocedural.rs

1use std::collections::{HashSet, VecDeque};
2
3use rustc_hir::def_id::DefId;
4use rustc_middle::{
5    mir::{BasicBlock, BinOp, Local, Operand, ProjectionElem, Rvalue, StatementKind, TerminatorKind},
6    ty::TyCtxt,
7};
8
9use crate::analysis::dataflow::{DataflowAnalysis, default::DataflowAnalyzer};
10use crate::analysis::path::graph::{PathEnumerator, PathGraph};
11use crate::helpers::mir_utils as helpers;
12
13use super::CallEffect;
14
15/// Trace backward from an operand (inner call arg) through Copy/Move/Cast
16/// assignments to the outer callee's argument local, returning its index.
17fn trace_to_callee_arg<'tcx>(
18    tcx: TyCtxt<'tcx>,
19    body: &rustc_middle::mir::Body<'tcx>,
20    operand: &Operand<'_>,
21) -> Option<usize> {
22    let local = match operand {
23        Operand::Copy(place) | Operand::Move(place) => place.local,
24        _ => return None,
25    };
26    let idx = local.as_usize();
27    if idx >= 1 && idx <= body.arg_count {
28        return Some(idx - 1);
29    }
30    let mut queue = VecDeque::from([local]);
31    let mut seen = HashSet::from([local]);
32    while let Some(current) = queue.pop_front() {
33        let cidx = current.as_usize();
34        if cidx >= 1 && cidx <= body.arg_count {
35            return Some(cidx - 1);
36        }
37        for bb in body.basic_blocks.iter() {
38            for stmt in &bb.statements {
39                let StatementKind::Assign(assign) = &stmt.kind else {
40                    continue;
41                };
42                let dest = assign.0.local;
43                if dest != current {
44                    continue;
45                }
46                let source = match &assign.1 {
47                    Rvalue::Use(Operand::Copy(place), ..)
48                    | Rvalue::Use(Operand::Move(place), ..)
49                    | Rvalue::Cast(_, Operand::Copy(place), _)
50                    | Rvalue::Cast(_, Operand::Move(place), _)
51                    | Rvalue::Ref(_, _, place)
52                    | Rvalue::RawPtr(_, place)
53                    | Rvalue::CopyForDeref(place) => place.local,
54                    _ => continue,
55                };
56                if !seen.contains(&source) {
57                    seen.insert(source);
58                    queue.push_back(source);
59                }
60            }
61            let Some(terminator) = &bb.terminator else {
62                continue;
63            };
64            let TerminatorKind::Call {
65                func,
66                args,
67                destination,
68                ..
69            } = &terminator.kind
70            else {
71                continue;
72            };
73            if destination.local != current {
74                continue;
75            }
76            let name = helpers::call_name(tcx, func);
77            if !crate::helpers::api_classify::is_as_ptr(&name) {
78                continue;
79            }
80            let Some(source) = args.first().and_then(|arg| match &arg.node {
81                Operand::Copy(place) | Operand::Move(place) => Some(place.local),
82                Operand::Constant(_) => None,
83                #[cfg(rapx_ge_99)]
84                Operand::RuntimeChecks(_) => None,
85            }) else {
86                continue;
87            };
88            if !seen.contains(&source) {
89                seen.insert(source);
90                queue.push_back(source);
91            }
92        }
93    }
94    None
95}
96
97/// Detect when a local callee wraps a pointer-arithmetic call (add/sub) and
98/// produce the correct `ReturnPointerAdd` / `ReturnPointerSub` effect.
99pub(super) fn try_pointer_arith_wrapper_effect<'tcx>(
100    tcx: TyCtxt<'tcx>,
101    callee: DefId,
102    _destination: Option<Local>,
103) -> Option<CallEffect> {
104    if !tcx.is_mir_available(callee) {
105        return None;
106    }
107
108    let body = tcx.optimized_mir(callee);
109    if body.basic_blocks.len() > 16 {
110        return None;
111    }
112    let ret = Local::from_usize(0);
113
114    for bb in body.basic_blocks.iter() {
115        let Some(terminator) = &bb.terminator else {
116            continue;
117        };
118        let TerminatorKind::Call {
119            func,
120            args,
121            destination: call_dest,
122            ..
123        } = &terminator.kind
124        else {
125            continue;
126        };
127
128        let name = helpers::call_name(tcx, func);
129        let is_add = crate::helpers::api_classify::is_pointer_add(&name);
130        let is_sub = crate::helpers::api_classify::is_pointer_sub(&name);
131
132        let inner_effect = if !is_add && !is_sub {
133            helpers::dep_callee_def_id(func).and_then(|inner_callee| {
134                let inner_name = helpers::call_name(tcx, func);
135                if inner_name.contains("::intrinsics::")
136                    || inner_name.starts_with("intrinsics::")
137                    || inner_name.ends_with("::drop_in_place")
138                {
139                    return None;
140                }
141                try_pointer_arith_wrapper_effect(tcx, inner_callee, Some(call_dest.local))
142            })
143        } else {
144            None
145        };
146
147        if !is_add && !is_sub && inner_effect.is_none() {
148            continue;
149        }
150
151        let mut queue = VecDeque::from([call_dest.local]);
152        let mut seen = HashSet::from([call_dest.local]);
153        let mut reaches_ret = false;
154        while let Some(current) = queue.pop_front() {
155            if current == ret {
156                reaches_ret = true;
157                break;
158            }
159            for bb2 in body.basic_blocks.iter() {
160                for stmt in &bb2.statements {
161                    let StatementKind::Assign(assign) = &stmt.kind else {
162                        continue;
163                    };
164                    let dest = assign.0.local;
165                    if seen.contains(&dest) {
166                        continue;
167                    }
168                    match &assign.1 {
169                        Rvalue::Use(Operand::Copy(place), ..)
170                        | Rvalue::Use(Operand::Move(place), ..) => {
171                            if place.local == current {
172                                queue.push_back(dest);
173                                seen.insert(dest);
174                            }
175                        }
176                        Rvalue::Cast(_, Operand::Copy(place), _)
177                        | Rvalue::Cast(_, Operand::Move(place), _) => {
178                            if place.local == current {
179                                queue.push_back(dest);
180                                seen.insert(dest);
181                            }
182                        }
183                        _ => {}
184                    }
185                }
186            }
187        }
188        if !reaches_ret {
189            continue;
190        }
191
192        if let Some(effect) = inner_effect {
193            match effect {
194                CallEffect::ReturnPointerAdd {
195                    base_arg: inner_base,
196                    offset_arg: inner_offset,
197                    stride,
198                }
199                | CallEffect::ReturnPointerSub {
200                    base_arg: inner_base,
201                    offset_arg: inner_offset,
202                    stride,
203                } => {
204                    let base_arg = trace_to_callee_arg(tcx, body, &args.get(inner_base)?.node)?;
205                    let offset_arg = trace_to_callee_arg(tcx, body, &args.get(inner_offset)?.node)?;
206                    return Some(match effect {
207                        CallEffect::ReturnPointerSub { .. } => CallEffect::ReturnPointerSub {
208                            base_arg,
209                            offset_arg,
210                            stride,
211                        },
212                        _ => CallEffect::ReturnPointerAdd {
213                            base_arg,
214                            offset_arg,
215                            stride,
216                        },
217                    });
218                }
219                _ => {}
220            }
221            continue;
222        }
223
224        let base_arg = trace_to_callee_arg(tcx, body, &args[0].node)?;
225        let offset_arg = trace_to_callee_arg(tcx, body, &args[1].node)?;
226        let stride = if crate::helpers::api_classify::is_byte_ptr_arith(&name) {
227            Some(1)
228        } else {
229            helpers::destination_stride(tcx, callee, Some(call_dest.local))
230        };
231
232        return if is_sub {
233            Some(CallEffect::ReturnPointerSub {
234                base_arg,
235                offset_arg,
236                stride,
237            })
238        } else {
239            Some(CallEffect::ReturnPointerAdd {
240                base_arg,
241                offset_arg,
242                stride,
243            })
244        };
245    }
246
247    None
248}
249
250/// Check whether a callee body contains pointer arithmetic calls.
251pub(super) fn callee_contains_pointer_arithmetic(tcx: TyCtxt<'_>, callee: DefId) -> bool {
252    let Some(_) = callee.as_local() else { return false };
253    if !tcx.is_mir_available(callee) { return false; }
254    let body = tcx.optimized_mir(callee);
255    for bb in body.basic_blocks.iter() {
256        let Some(terminator) = &bb.terminator else { continue };
257        let TerminatorKind::Call { func, .. } = &terminator.kind else { continue };
258        let name = helpers::call_name(tcx, func);
259        if crate::helpers::api_classify::is_pointer_add(&name) || crate::helpers::api_classify::is_pointer_sub(&name) {
260            return true;
261        }
262    }
263    false
264}
265
266/// Use the existing dataflow graph to approximate local callee return deps.
267pub(super) fn local_return_dependencies(tcx: TyCtxt<'_>, callee: DefId) -> Option<Vec<usize>> {
268    callee.as_local()?;
269    if !tcx.is_mir_available(callee) {
270        return None;
271    }
272    helpers::catch_panic(|| {
273        let mut analyzer = DataflowAnalyzer::new(tcx, false);
274        analyzer.build_graph(callee);
275        let deps = analyzer.get_fn_arg2ret(callee);
276        deps.iter_enumerated()
277            .filter_map(|(local, depends)| {
278                if *depends && local.as_usize() > 0 {
279                    Some(local.as_usize() - 1)
280                } else {
281                    None
282                }
283            })
284            .collect()
285    })
286    .ok()
287}
288
289/// Detect when a local callee wraps `from_raw_parts(ptr, len)` and produce
290/// a `ReturnFreshAllocation` effect with the correct element size.
291pub(super) fn try_from_raw_parts_wrapper_effect<'tcx>(
292    tcx: TyCtxt<'tcx>,
293    callee: DefId,
294    _destination: Option<Local>,
295) -> Option<CallEffect> {
296    if !tcx.is_mir_available(callee) {
297        return None;
298    }
299    let body = tcx.optimized_mir(callee);
300    if body.basic_blocks.len() > 8 {
301        return None;
302    }
303    let ret = Local::from_usize(0);
304
305    for bb in body.basic_blocks.iter() {
306        let Some(terminator) = &bb.terminator else { continue };
307        let TerminatorKind::Call {
308            func, args, destination: call_dest, ..
309        } = &terminator.kind else { continue };
310
311        let name = helpers::call_name(tcx, func);
312        if !crate::helpers::api_classify::is_from_raw_parts(&name) {
313            continue;
314        }
315
316        // Verify the call result reaches return
317        let mut queue = VecDeque::from([call_dest.local]);
318        let mut seen = HashSet::from([call_dest.local]);
319        let mut reaches_ret = false;
320        while let Some(current) = queue.pop_front() {
321            if current == ret { reaches_ret = true; break; }
322            for bb2 in body.basic_blocks.iter() {
323                for stmt in &bb2.statements {
324                    let StatementKind::Assign(assign) = &stmt.kind else { continue };
325                    if seen.contains(&assign.0.local) { continue; }
326                    match &assign.1 {
327                        Rvalue::Use(Operand::Copy(place), ..)
328                        | Rvalue::Use(Operand::Move(place), ..)
329                        | Rvalue::Cast(_, Operand::Copy(place), _)
330                        | Rvalue::Cast(_, Operand::Move(place), _) => {
331                            if place.local == current {
332                                queue.push_back(assign.0.local);
333                                seen.insert(assign.0.local);
334                            }
335                        }
336                        _ => {}
337                    }
338                }
339            }
340        }
341        if !reaches_ret { continue; }
342
343        // Trace from_raw_parts args to callee args
344        let pointer_arg = trace_to_callee_arg(tcx, body, &args[0].node)?;
345        let size_arg = trace_to_callee_arg(tcx, body, &args[1].node)?;
346
347        // Determine element size from return type
348        let ret_ty = body.local_decls[ret].ty;
349        let elem_size = match ret_ty.kind() {
350            rustc_middle::ty::TyKind::Ref(_, inner, _) => match inner.kind() {
351                rustc_middle::ty::TyKind::Slice(elem) => {
352                    let typing_env = rustc_middle::ty::TypingEnv::post_analysis(tcx, callee);
353                    let input = rustc_middle::ty::PseudoCanonicalInput { typing_env, value: *elem };
354                    crate::helpers::mir_utils::catch_panic(|| {
355                        tcx.layout_of(input)
356                    }).ok().and_then(|r| r.ok())
357                        .map(|l| l.size.bytes())
358                        .unwrap_or(1)
359                }
360                _ => 1,
361            },
362            _ => 1,
363        };
364
365        return Some(CallEffect::ReturnFreshAllocation {
366            pointer_arg,
367            size_arg,
368            elem_size,
369        });
370    }
371    None
372}
373
374/// Return callee argument indices that are definitely written on every
375/// reachable return path.
376pub(super) fn local_must_write_args(tcx: TyCtxt<'_>, callee: DefId) -> Option<Vec<usize>> {
377    callee.as_local()?;
378    if !tcx.is_mir_available(callee) {
379        return None;
380    }
381
382    helpers::catch_panic(|| {
383        let body = tcx.optimized_mir(callee);
384        let mut graph = PathGraph::new(tcx, callee);
385        graph.find_scc();
386        let mut enumerator = PathEnumerator::new(&graph);
387        let paths = enumerator.enumerate_paths_repeat(0);
388
389        let mut must_write: Option<HashSet<usize>> = None;
390        for path in paths.iter() {
391            if !path_ends_in_return(body, &path) {
392                continue;
393            }
394            let writes = write_args_on_path(tcx, body, &path);
395            must_write = Some(match must_write {
396                Some(current) => current.intersection(&writes).copied().collect(),
397                None => writes,
398            });
399        }
400
401        must_write
402            .unwrap_or_default()
403            .into_iter()
404            .collect::<Vec<_>>()
405    })
406    .ok()
407}
408
409/// Recognize the standard-library `get_disjoint_check_valid` helper as a
410/// trusted index-disjoint validator by name.
411pub(super) fn named_index_disjoint_validator(name: &str) -> Option<(usize, usize)> {
412    let base = name
413        .split('<')
414        .next()
415        .unwrap_or(name)
416        .trim_end_matches("::");
417    if base.ends_with("get_disjoint_check_valid")
418        || base.ends_with("get_disjoint_check_valid_ext") {
419        Some((0, 1))
420    } else {
421        None
422    }
423}
424
425/// Detect an "index disjoint validator": a function whose body loads elements
426/// from an array argument, and returns early (`Err`) both when an element is
427/// out of range against a scalar argument (`>= len`) and when two elements are
428/// equal (a duplicate).  Returns `(indices_arg, len_arg)`.
429pub(super) fn detect_index_disjoint_validator(tcx: TyCtxt<'_>, callee: DefId) -> Option<(usize, usize)> {
430    callee.as_local()?;
431    if !tcx.is_mir_available(callee) {
432        return None;
433    }
434    helpers::catch_panic(|| {
435        let body = tcx.optimized_mir(callee);
436        let arg_count = body.arg_count;
437        let mut elem_load_arg: HashSet<(Local, usize)> = HashSet::new();
438        let mut copy_of_arg: HashSet<(Local, usize)> = HashSet::new();
439
440        for bb in body.basic_blocks.iter() {
441            for stmt in &bb.statements {
442                let StatementKind::Assign(assign) = &stmt.kind else {
443                    continue;
444                };
445                let (dest, rvalue) = &**assign;
446                if !dest.projection.is_empty() {
447                    continue;
448                }
449                let Rvalue::Use(Operand::Copy(place) | Operand::Move(place), ..) = rvalue else {
450                    continue;
451                };
452                let Some(arg) = helpers::arg_of_local(place.local, arg_count) else {
453                    continue;
454                };
455                if place
456                    .projection
457                    .iter()
458                    .any(|p| matches!(p, ProjectionElem::Index(_)))
459                {
460                    elem_load_arg.insert((dest.local, arg));
461                } else if place.projection.is_empty() {
462                    copy_of_arg.insert((dest.local, arg));
463                }
464            }
465        }
466
467        let elem_arg = |op: &Operand<'_>| -> Option<usize> {
468            let (Operand::Copy(p) | Operand::Move(p)) = op else {
469                return None;
470            };
471            if !p.projection.is_empty() {
472                return None;
473            }
474            elem_load_arg
475                .iter()
476                .find(|(l, _)| *l == p.local)
477                .map(|(_, a)| *a)
478        };
479        let scalar_arg = |op: &Operand<'_>| -> Option<usize> {
480            let (Operand::Copy(p) | Operand::Move(p)) = op else {
481                return None;
482            };
483            if !p.projection.is_empty() {
484                return None;
485            }
486            helpers::arg_of_local(p.local, arg_count).or_else(|| {
487                copy_of_arg
488                    .iter()
489                    .find(|(l, _)| *l == p.local)
490                    .map(|(_, a)| *a)
491            })
492        };
493
494        let mut bounds: Option<(usize, usize)> = None;
495        let mut disjoint_arg: Option<usize> = None;
496        for bb in body.basic_blocks.iter() {
497            for stmt in &bb.statements {
498                let StatementKind::Assign(assign) = &stmt.kind else {
499                    continue;
500                };
501                let (_, Rvalue::BinaryOp(op, pair)) = &**assign else {
502                    continue;
503                };
504                let (a, b) = &**pair;
505                match op {
506                    BinOp::Ge | BinOp::Gt | BinOp::Le | BinOp::Lt => {
507                        if let (Some(idx), Some(len)) = (elem_arg(a), scalar_arg(b)) {
508                            bounds = Some((idx, len));
509                        } else if let (Some(idx), Some(len)) = (elem_arg(b), scalar_arg(a)) {
510                            bounds = Some((idx, len));
511                        }
512                    }
513                    BinOp::Eq | BinOp::Ne => {
514                        if let (Some(x), Some(y)) = (elem_arg(a), elem_arg(b))
515                            && x == y
516                        {
517                            disjoint_arg = Some(x);
518                        }
519                    }
520                    _ => {}
521                }
522            }
523        }
524
525        match (bounds, disjoint_arg) {
526            (Some((idx, len)), Some(dj)) if dj == idx && idx != len => Some((idx, len)),
527            _ => None,
528        }
529    })
530    .ok()
531    .flatten()
532}
533fn path_ends_in_return(body: &rustc_middle::mir::Body<'_>, path: &[usize]) -> bool {
534    path.last().is_some_and(|block| {
535        body.basic_blocks
536            .get(BasicBlock::from_usize(*block))
537            .and_then(|data| data.terminator.as_ref())
538            .is_some_and(|terminator| matches!(terminator.kind, TerminatorKind::Return))
539    })
540}
541
542fn write_args_on_path<'tcx>(
543    tcx: TyCtxt<'tcx>,
544    body: &rustc_middle::mir::Body<'tcx>,
545    path: &[usize],
546) -> HashSet<usize> {
547    let mut writes = HashSet::new();
548    for block in path {
549        let Some(data) = body.basic_blocks.get(BasicBlock::from_usize(*block)) else {
550            continue;
551        };
552        let Some(terminator) = data.terminator.as_ref() else {
553            continue;
554        };
555        let TerminatorKind::Call { func, args, .. } = &terminator.kind else {
556            continue;
557        };
558        let name = helpers::call_name(tcx, func);
559        if !crate::helpers::api_classify::is_ptr_write(&name) {
560            continue;
561        }
562        if let Some(pointer_arg) = args
563            .first()
564            .and_then(|arg| trace_to_callee_arg(tcx, body, &arg.node))
565        {
566            writes.insert(pointer_arg);
567        }
568    }
569    writes
570}
571
572/// Return true if the callee body contains any Call terminator (to local functions
573/// that may have side effects), meaning the callee is not self-contained.
574pub(super) fn callee_calls_other_local(tcx: TyCtxt<'_>, callee: DefId) -> bool {
575    let body = tcx.optimized_mir(callee);
576    for bb in body.basic_blocks.iter() {
577        if matches!(bb.terminator().kind,
578            rustc_middle::mir::TerminatorKind::Call { .. }
579        ) {
580            return true;
581        }
582    }
583    false
584}
rapx/verify/call_summary/interprocedural.rs

rapx/verify/call_summary/
interprocedural.rs
