crates/mimir-room/src/possible.rs
//! **The possible system calls of a program** — the MAX the code graph
//! sets: every system call some path from the program's entry points can
//! reach, walked over CALLS to the `SYSCALLS` boundary in a room with the
//! dependency universe folded in. A measured profile (Heimdall's probe) is
//! the MIN a test saw; the cross-check (dwarves `dwarves-tune-graph
//! --graph`) proves the test stays inside the max.
//!
//! ```text
//! entries ──CALLS──▶ … ──CALLS──▶ fn / ffi ──SYSCALLS──▶ @syscall <arch>/<name>
//! │ trait method with no resolved impl (dyn Trait, a generic bound)
//! │ ⇒ EVERY impl's method of that name in the room (unresolved site)
//! │ Fn::call / FnMut::call_mut / FnOnce::call_once (a closure or a
//! │ fn pointer called as a value) ⇒ its impls, and every static /
//! │ const whose initializer names a fn (unresolved site)
//! │ an `ffi` node with no SYSCALLS edge (our own `extern "C"`)
//! │ ⇒ the C map ([`mimir_ingest::boundary::libc_map`])
//! └ the raw door (`<indirect>`): a number chosen at run time (unresolved site)
//! runtime: std's rt::lang_start(_internal) are entries too, and the C
//! runtime's start-up calls (before main) are possible
//! ```
//!
//! The max stays a TRUE max: an edge the compiler could not resolve is
//! widened to every target the room holds, never dropped, and each such
//! place is listed in `unresolved_sites`. What the graph cannot see at all
//! (a C function the map has no answer for, `dlopen`, a raw syscall number)
//! is said in `unresolved_imports`, `dlopen` and `unresolved_sites`: then
//! a seen call outside the max is a graph gap to review, not a test bug.
//!
//! The JSON ([`PossibleGraph`]) is the `Graph` dwarves-tune-graph's
//! `read_graph` reads (`syscalls{name → Reach}`, `unresolved_sites`,
//! `dlopen` …, every field it requires), with a few extra fields of its
//! own (`format`, `uncertain`, `reason` …) its reader ignores.
use std::collections::{BTreeMap, BTreeSet, HashMap};
use anyhow::Result;
use mimir_ingest::boundary::{self, INDIRECT, Libc, Mapped};
use mimir_schema::{EdgeKind, kind as nk, moniker};
use serde::{Deserialize, Serialize};
use crate::evidence::{Answer, Emptiness};
use crate::export::EdgeSel;
use crate::Room;
/// The format id of [`PossibleGraph`].
pub const FORMAT: &str = "mimir.possible-syscalls/1";
/// The edge kinds a possible-syscalls walk follows.
pub const WALK: [EdgeKind; 2] = [EdgeKind::Calls, EdgeKind::Syscalls];
/// Why a call site is unresolved.
pub const REASON_DISPATCH: &str = "trait method with no resolved impl (dyn Trait or a generic bound): every impl of it in the room is taken";
pub const REASON_VALUE: &str = "a closure or fn pointer called as a value (Fn / FnMut / FnOnce): its impls and every fn a static or const names are taken";
pub const REASON_RAW: &str = "a system call whose number is chosen at run time (the raw door): any call is possible here";
/// What to walk for.
#[derive(Debug, Clone)]
pub struct PossibleOpts {
/// The program's name (the `binary` field).
pub binary: String,
/// The architecture whose `@syscall` nodes count (`x86_64`, `aarch64`).
pub arch: String,
/// The C library our own `extern "C"` items are answered with.
pub libc: Libc,
/// The program is a linked executable: its start-up runs before the
/// entries — std's `rt::lang_start` / `lang_start_internal` are entries
/// too (when the room holds them), and the C runtime's start-up calls
/// ([`mimir_ingest::boundary::libc_map::startup`]) are possible.
pub runtime: bool,
}
/// The `path` and `site` of a call the C runtime's start-up makes.
pub const STARTUP_SITE: &str = "<C runtime start-up, before main>";
/// One crate the walk reached (the `modules` of the Graph).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ModuleInfo {
/// `crate@version`.
pub name: String,
/// The repo whose rows hold it (`@universe` for a dependency).
pub path: String,
pub reached_functions: usize,
}
/// How one system call is reached.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Reach {
/// The call's number in the architecture's table.
pub nr: u64,
/// Reached over resolved CALLS alone (no widened site on the way).
pub direct: bool,
/// The function chain from an entry point to the function that makes
/// the call (entry first; readable paths).
pub path: Vec<String>,
/// The function that makes the call (`path`'s last), with its crate.
pub site: String,
/// How many reached functions make this call.
pub sites: usize,
/// Every maker's boundary hop is UNCERTAIN (the C function MAY make it).
pub uncertain: bool,
}
/// A place the graph widened or cannot see past.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct Site {
/// The caller's `crate@version`.
pub module: String,
/// The caller (readable path).
pub function: String,
/// Always 0: a source graph has no byte offset (the binary graph's field).
pub offset: u64,
/// The caller is reached over resolved CALLS alone.
pub direct: bool,
/// What it calls: the trait method, the `Fn*` method, `<indirect>`.
pub callee: String,
/// [`REASON_DISPATCH`], [`REASON_VALUE`] or [`REASON_RAW`].
pub reason: String,
/// How many targets the site was widened to (0 for the raw door).
pub targets: usize,
}
/// The possible system calls of one program.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct PossibleGraph {
pub format: String,
pub binary: String,
pub arch: String,
pub modules: Vec<ModuleInfo>,
/// The entry points (readable paths).
pub entries: Vec<String>,
/// System call name → how it is reached.
pub syscalls: BTreeMap<String, Reach>,
/// Constant numbers the table does not name (none in a source graph).
pub unnamed: BTreeSet<u64>,
pub unresolved_sites: Vec<Site>,
/// Libraries not found (none in a source graph: the room holds them all).
pub missing_libs: Vec<String>,
/// Reached C functions the C map has no answer for: they may make any call.
pub unresolved_imports: Vec<String>,
/// A reached C function is `dlopen`: code the graph never saw may load.
pub dlopen: bool,
/// Widened call sites (dispatch + value calls).
pub indirect_sites: usize,
/// Functions reached (fn, method, ffi).
pub reached_functions: usize,
}
impl Emptiness for PossibleGraph {
fn is_empty_answer(&self) -> bool {
self.syscalls.is_empty()
}
}
/// How the walk got to a node.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pred {
from: Option<u64>,
depth: u32,
direct: bool,
}
/// Is `m` one of core's `Fn::call`, `FnMut::call_mut`, `FnOnce::call_once`?
pub fn is_fn_family(m: &str) -> bool {
let Some(("core", _, d)) = moniker::parse(m) else { return false };
["ops/function/Fn#call().", "ops/function/FnMut#call_mut().", "ops/function/FnOnce#call_once()."].iter().any(|s| d.ends_with(s))
}
/// The arch of a `@syscall` node's moniker (`x86_64` of `… @syscall . x86_64/read().`).
fn syscall_arch(m: &str) -> Option<&str> {
moniker::parse(m).and_then(|(_, _, d)| d.split('/').next())
}
fn is_function(kind: Option<&str>) -> bool {
matches!(kind, Some(nk::FN | nk::METHOD | nk::FFI))
}
struct Ctx<'r> {
room: &'r Room,
/// trait → its impl blocks
impls_of: HashMap<u64, Vec<u64>>,
/// trait method → the impl methods it is widened to (cached)
widened: HashMap<u64, Vec<u64>>,
/// statics / consts whose initializer names a fn
initializers: Vec<u64>,
seeded: bool,
}
impl<'r> Ctx<'r> {
fn new(room: &'r Room) -> Result<Ctx<'r>> {
let mut impls_of: HashMap<u64, Vec<u64>> = HashMap::new();
for e in room.edges(&EdgeSel::kinds(&[EdgeKind::Implements]))?.value.edges {
impls_of.entry(e.to).or_default().push(e.from);
}
let inits = room.mask(&crate::MaskSpec { node_kinds: vec![nk::STATIC.into(), nk::CONST.into()], ..Default::default() })?.value;
let mut initializers: Vec<u64> = room.out_pairs(EdgeKind::Calls, inits.ordinals())?.into_iter().map(|(f, _)| f).collect();
initializers.dedup();
Ok(Ctx { room, impls_of, widened: HashMap::new(), initializers, seeded: false })
}
/// The trait `t` is a method of, when it is one.
fn trait_of(&self, t: u64) -> Option<u64> {
let n = self.room.node(t);
if !matches!(n.kind, Some(nk::FN | nk::METHOD)) {
return None;
}
let p = n.parent?;
(self.room.node(p).kind == Some(nk::TRAIT)).then_some(p)
}
/// Is `t` a call target the compiler left unresolved?
fn unresolved(&self, t: u64) -> Option<&'static str> {
if is_fn_family(self.room.moniker(t)) {
Some(REASON_VALUE)
} else if self.trait_of(t).is_some() {
Some(REASON_DISPATCH)
} else {
None
}
}
/// Every impl method `t` (a trait method) can be at run time.
fn widen(&mut self, t: u64) -> Result<Vec<u64>> {
if let Some(v) = self.widened.get(&t) {
return Ok(v.clone());
}
let mut out = Vec::new();
if let Some(tr) = self.trait_of(t) {
let name = self.room.node(t).name;
let mut impls = self.impls_of.get(&tr).cloned().unwrap_or_default();
impls.sort_unstable();
impls.dedup();
for (_, m) in self.room.out_pairs(EdgeKind::Contains, &impls)? {
let n = self.room.node(m);
if matches!(n.kind, Some(nk::FN | nk::METHOD)) && n.name == name {
out.push(m);
}
}
out.sort_unstable();
out.dedup();
}
self.widened.insert(t, out.clone());
Ok(out)
}
}
impl Room {
/// The possible system calls of the program whose entry points are
/// `entries`: a walk over CALLS and SYSCALLS (ring on), widened at every
/// unresolved call site, to the `@syscall` nodes of `opts.arch`.
pub fn possible_syscalls(&self, entries: &[u64], opts: &PossibleOpts) -> Result<Answer<PossibleGraph>> {
let mut ev = self.evidence(format!("possible_syscalls({} entries, {})", entries.len(), opts.arch), false, &[EdgeKind::Calls, EdgeKind::Syscalls, EdgeKind::Implements]);
if !self.snap.scope.universe {
ev.miss("universe", None, "the dependency universe is not folded in: the walk stops at the first dependency and no SYSCALLS edge is in the room — open the room with the universe");
}
if boundary::table(&opts.arch).is_none() {
ev.miss("syscall table", None, format!("no syscall table for `{}`", opts.arch));
}
let mut ctx = Ctx::new(self)?;
let mut seen: HashMap<u64, Pred> = HashMap::new();
let mut start: Vec<u64> = entries.to_vec();
if opts.runtime {
for d in ["rt/lang_start().", "rt/lang_start_internal()."] {
let hit = self.resolve(&moniker::stable(&moniker::moniker("std", "x", d)));
start.extend(hit);
}
}
start.sort_unstable();
start.dedup();
for &e in &start {
seen.insert(e, Pred { from: None, depth: 0, direct: true });
}
// 1. resolved edges only: what is reached `direct`
self.possible_walk(start.clone(), &mut seen, false, &mut ctx)?;
// 2. from everything reached, widened at each unresolved site
let mut all: Vec<u64> = seen.keys().copied().collect();
all.sort_unstable();
self.possible_walk(all, &mut seen, true, &mut ctx)?;
let mut reached: Vec<u64> = seen.keys().copied().collect();
reached.sort_unstable();
let reached_mask = self.mask_of(&reached);
// the makers: SYSCALLS edges out of reached nodes, to this arch
let sel = EdgeSel { kinds: vec![EdgeKind::Syscalls], from: Some(&reached_mask), ..Default::default() };
// call name → (maker, uncertain)
let mut makers: BTreeMap<String, Vec<(u64, bool)>> = BTreeMap::new();
let mut raw_doors: BTreeSet<u64> = BTreeSet::new();
let mut with_edges: BTreeSet<u64> = BTreeSet::new();
for e in self.edges(&sel)?.value.edges {
with_edges.insert(e.from);
let to = self.moniker(e.to);
if syscall_arch(to) != Some(opts.arch.as_str()) {
continue;
}
let name = self.node(e.to).name.unwrap_or("?").to_string();
if name == INDIRECT {
raw_doors.insert(e.from);
continue;
}
makers.entry(name).or_default().push((e.from, e.partial));
}
// C functions with no SYSCALLS edge (our own `extern "C"`): the C map
let mut unmapped: BTreeSet<String> = BTreeSet::new();
let mut dlopen = false;
let arch = opts.arch.as_str();
let is_call = |n: &str| !boundary::calls_on(arch, n).is_empty();
for &o in &reached {
let n = self.node(o);
if n.kind != Some(nk::FFI) {
continue;
}
let symbol = self.attr(o, "link_name").and_then(|v| v.as_str().map(str::to_string)).or_else(|| n.name.map(str::to_string)).unwrap_or_default();
if symbol == "dlopen" || symbol == "dlmopen" {
dlopen = true;
}
if with_edges.contains(&o) {
continue;
}
match boundary::libc_map::lookup(&symbol, opts.libc, &is_call) {
Some(Mapped::Calls(calls)) => {
for (c, sure) in calls {
for c in boundary::calls_on(arch, c) {
if c == INDIRECT {
raw_doors.insert(o);
} else {
makers.entry(c.to_string()).or_default().push((o, !sure));
}
}
}
}
Some(Mapped::Pure) => {}
None => {
unmapped.insert(symbol);
}
}
}
let path_to = |m: u64| -> Vec<String> {
let mut chain = vec![m];
let mut cur = m;
while let Some(Pred { from: Some(p), .. }) = seen.get(&cur) {
if chain.len() > 4096 {
break;
}
chain.push(*p);
cur = *p;
}
chain.reverse();
chain.into_iter().map(|o| self.display_path(o)).collect()
};
let site_of = |o: u64| -> String {
let n = self.node(o);
format!("{} ({}@{})", self.display_path(o), n.krate.unwrap_or("?"), n.version.unwrap_or("?"))
};
let mut syscalls = BTreeMap::new();
if opts.runtime {
for (c, sure) in boundary::libc_map::startup(opts.libc, arch) {
let Some(sc) = boundary::syscall(arch, c) else { continue };
syscalls.insert(
c.to_string(),
Reach { nr: sc.nr as u64, direct: true, path: vec![STARTUP_SITE.into()], site: STARTUP_SITE.into(), sites: 1, uncertain: !sure },
);
}
}
for (name, ms) in &makers {
let mut ms = ms.clone();
ms.sort_unstable();
ms.dedup_by_key(|m| m.0);
// the shortest path, a direct one first
let best = ms.iter().map(|(m, _)| *m).min_by_key(|m| {
let p = seen[m];
(!p.direct, p.depth, *m)
});
let Some(best) = best else { continue };
let nr = boundary::syscall(arch, name).map_or(u64::MAX, |s| s.nr as u64);
// a call the start-up makes too stays certain and counts it as a site
let startup = syscalls.get(name).map(|r: &Reach| !r.uncertain);
syscalls.insert(
name.clone(),
Reach {
nr,
direct: ms.iter().any(|(m, _)| seen[m].direct),
path: path_to(best),
site: site_of(best),
sites: ms.len() + startup.map_or(0, |_| 1),
uncertain: ms.iter().all(|(_, u)| *u) && startup != Some(true),
},
);
}
// the unresolved sites: reached callers of an unresolved target, and the raw doors
let mut targets: Vec<u64> = reached.iter().copied().filter(|t| ctx.unresolved(*t).is_some()).collect();
targets.sort_unstable();
let mut sites: Vec<Site> = Vec::new();
if !targets.is_empty() {
let tmask = self.mask_of(&targets);
let sel = EdgeSel { kinds: vec![EdgeKind::Calls], from: Some(&reached_mask), to: Some(&tmask), ..Default::default() };
for e in self.edges(&sel)?.value.edges {
let reason = ctx.unresolved(e.to).unwrap_or(REASON_DISPATCH);
let n = ctx.widen(e.to)?.len() + if reason == REASON_VALUE { ctx.initializers.len() } else { 0 };
sites.push(self.site(e.from, e.to, reason, n, seen[&e.from].direct));
}
}
let indirect_sites = sites.len();
for &o in &raw_doors {
let to = self.ordinal(&moniker::syscall(arch, INDIRECT));
sites.push(Site { callee: INDIRECT.into(), ..self.site(o, to.unwrap_or(o), REASON_RAW, 0, seen[&o].direct) });
}
sites.sort();
sites.dedup();
let mut modules: BTreeMap<(String, String), usize> = BTreeMap::new();
let mut reached_functions = 0;
for &o in &reached {
let n = self.node(o);
if !is_function(n.kind) || n.krate == Some(moniker::KERNEL_PACKAGE) {
continue;
}
reached_functions += 1;
let name = format!("{}@{}", n.krate.unwrap_or("?"), n.version.unwrap_or("?"));
*modules.entry((name, n.repo.unwrap_or("?").to_string())).or_default() += 1;
}
if !unmapped.is_empty() {
ev.miss("C map", None, format!("{} reached C function(s) the boundary map has no answer for (they may make any call): {}", unmapped.len(), unmapped.iter().take(12).cloned().collect::<Vec<_>>().join(", ")));
}
let g = PossibleGraph {
format: FORMAT.into(),
binary: opts.binary.clone(),
arch: opts.arch.clone(),
modules: modules.into_iter().map(|((name, path), reached_functions)| ModuleInfo { name, path, reached_functions }).collect(),
entries: start.iter().map(|o| self.display_path(*o)).collect(),
syscalls,
unnamed: BTreeSet::new(),
unresolved_sites: sites,
missing_libs: Vec::new(),
unresolved_imports: unmapped.into_iter().collect(),
dlopen,
indirect_sites,
reached_functions,
};
Ok(Answer::new(g, ev))
}
fn site(&self, from: u64, to: u64, reason: &str, targets: usize, direct: bool) -> Site {
let n = self.node(from);
Site {
module: format!("{}@{}", n.krate.unwrap_or("?"), n.version.unwrap_or("?")),
function: self.display_path(from),
offset: 0,
direct,
callee: self.display_path(to),
reason: reason.into(),
targets,
}
}
/// Breadth-first from `frontier`; `widen` = also take the targets of
/// unresolved sites. A `syscall` node is an end: the walk never goes on
/// into the kernel's functions.
fn possible_walk(&self, mut frontier: Vec<u64>, seen: &mut HashMap<u64, Pred>, widen: bool, ctx: &mut Ctx<'_>) -> Result<()> {
while !frontier.is_empty() {
frontier.retain(|o| self.node(*o).kind != Some(nk::SYSCALL));
let mut next: Vec<u64> = Vec::new();
let mut visit = |seen: &mut HashMap<u64, Pred>, from: Option<u64>, to: u64, direct: bool, depth: u32| {
if let std::collections::hash_map::Entry::Vacant(v) = seen.entry(to) {
v.insert(Pred { from, depth, direct });
next.push(to);
}
};
for kind in WALK {
for (f, t) in self.out_pairs(kind, &frontier)? {
let p = seen[&f];
visit(seen, Some(f), t, p.direct && !widen, p.depth + 1);
}
}
if widen {
for &f in &frontier {
let Some(reason) = ctx.unresolved(f) else { continue };
let depth = seen[&f].depth + 1;
for t in ctx.widen(f)? {
visit(seen, Some(f), t, false, depth);
}
if reason == REASON_VALUE && !ctx.seeded {
ctx.seeded = true;
for t in ctx.initializers.clone() {
visit(seen, Some(f), t, false, depth);
}
}
}
}
next.sort_unstable();
next.dedup();
frontier = next;
}
Ok(())
}
}