1pub mod merged_extent;
4
5use serde::{Deserialize, Serialize};
6pub mod source_file;
7pub use source_file::{clean_source_path, same_source_file};
8pub mod inline;
9pub use inline::*;
10pub mod contraction;
11pub mod position;
12pub mod proof;
13pub mod reach;
14mod refusal;
15pub use refusal::{BindingRefusal, BindingRefusalKind, BindingRefusals};
16
17#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
19#[serde(rename_all = "kebab-case")]
20pub enum MapHow {
21 Call,
23 Syscall,
25 Inlined,
27 TailJump,
30 PointerConstant,
32}
33
34#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
36pub struct MappedSite {
37 #[serde(default, skip_serializing_if = "Option::is_none")]
39 pub inline_binding: Option<InlineBinding>,
40 pub site: u32,
42 pub node: String,
43 pub how: MapHow,
44 pub addresses: Vec<u64>,
46 pub copies: u32,
49 pub copies_with_call: u32,
50 #[serde(with = "proof::wire")]
52 pub proof: String,
53 pub required: bool,
56 #[serde(default)]
62 pub kernel_ips: Vec<u64>,
63 #[serde(default, skip_serializing_if = "Option::is_none")]
64 #[serde(with = "proof::optional_wire")]
65 pub ips_proof: Option<String>,
66 #[serde(default, skip_serializing_if = "Option::is_none")]
68 pub ips_why: Option<String>,
69}
70
71pub const PROOF_KERNEL_IPS_ASM: &str = "the site's own syscall instructions: address + 2";
73
74pub const PROOF_KERNEL_IPS: &str = "the call instructions' direct targets and every function the static analysis's report reaches from them by calls and tail jumps, none holding an unresolved transfer (a hole of the site table); the site table's syscall instructions in those functions whose numbers (proven, the callers' constants of an argument site, jump-table arms) include one of the node's; ip = address + 2";
76
77pub const PROOF_KERNEL_IPS_NULL: &str = "every call instruction of the site is a direct call to address 0 (a weak symbol the link left undefined) and no executable segment of the image holds address 0: the call faults before any instruction runs, so no syscall instruction is reached from it; the list is empty";
80
81pub const PROOF_KERNEL_IPS_OPENS: &str = "the call instructions' direct targets and every function the static analysis's report reaches from them by calls and tail jumps; an indirect transfer there (the call itself, or a hole of the site table in a reached function) enters the functions of the sections the site table says it opens (`fallback`: every blind section, the reach of every address-taken function, the site floor's premise that an indirect transfer enters only an address-taken function), and so on until no new hole is reached; the site table's syscall instructions in all those functions whose numbers (proven, the callers' constants of an argument site, jump-table arms) include one of the node's; ip = address + 2";
84
85pub const PROOF_REGISTER_CONSTANT: &str = "a call through a callee-saved register (rbx, rbp, r12-r15) whose every reaching definition in its function sets the same constant: a `mov` of an immediate, a `lea` of a RIP-relative address, or a `mov` of the 8-byte word at a RIP-relative address in a segment the image does not let be written or in the PT_GNU_RELRO range of a static ET_EXEC image (no PT_DYNAMIC: no relocation writes it); reaching definitions over the report's blocks and successors, a block entered from outside the function or with no predecessor in it (the entry, a landing pad) starting with every register unknown, and a call preserving these registers (the SysV ABI)";
87
88pub const PROOF_SITE: &str = "DWARF scope with the instance's symbol as linkage name (up to v0's instantiating crate); line-table row = the call site's file and line; the instruction's kind and direct target (a call through a callee-saved register: the one constant every definition reaching it sets, PROOF_REGISTER_CONSTANT)";
90
91pub const PROOF_SITE_ASM_INLINED: &str = "DWARF scope with the instance's symbol as linkage name (up to v0's instantiating crate); the row is inline assembly at a call of a system-call wrapper (mimir-exec makes a wrapper whose number is its parameter a site of each caller); the syscall instructions of the copy's own code at the row's file and line, and every syscall instruction inside a subroutine DWARF says is inlined at that file and line (its call file and line)";
93
94pub const PROOF_SITE_ASM_ONLY: &str = "DWARF scope with the instance's symbol as linkage name (up to v0's instantiating crate); the row is the instance's only inline-assembly call site (mimir-exec makes a system-call wrapper whose number is its parameter a site of each caller, so the wrapper has no row of its own); the syscall instructions of the copy's own code at the row's file and line, and every syscall instruction inside a subroutine DWARF says is inlined into the copy whose instance has no exec row (a wrapper; the macro that calls it gives DWARF the macro body's line), less those inside a subroutine inlined there whose instance has exec rows (that instance's own sites)";
97
98pub const PROOF_ENTRY_MAIN: &str = "the kernel starts the main thread at the image's entry, and the main thread runs the process entry (site table thread start, role main)";
100
101pub const PROOF_ENTRY_DWARF: &str = "DWARF scopes with the instance's symbol as linkage name (up to v0's instantiating crate) (its copies; no function of its own)";
103
104pub const PROOF_SITE_POINTER: &str = "DWARF scopes with the instance's symbol as linkage name (up to v0's instantiating crate); no line ties any instruction to the call site, and it is the instance's only such call site; a target some copy first tests against zero (`mov $t,%r; test %r,%r`) and then calls is a pointer whose value the link fixed (a weak symbol), which no direct call is (a function's address is never tested against zero); in each copy, the one direct call to that target (the compiler may share the test between copies)";
106
107pub const PROOF_ENTRY: &str =
109 "the instance's symbol is a function of the image (the static analysis's function list)";
110
111#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
113#[serde(rename_all = "kebab-case", tag = "why")]
114pub enum Unmapped {
115 NoDwarf,
117 InstanceAbsent,
119 NoInstruction,
122 LineShared { with: Vec<u32> },
124 NoSource,
126 EntryStart { entries: Vec<u32> },
129}
130
131impl Unmapped {
132 pub fn name(&self) -> &'static str {
134 match self {
135 Unmapped::NoDwarf => "no-dwarf",
136 Unmapped::InstanceAbsent => "instance-absent",
137 Unmapped::NoInstruction => "no-instruction",
138 Unmapped::LineShared { .. } => "line-shared",
139 Unmapped::NoSource => "no-source",
140 Unmapped::EntryStart { .. } => "entry-start",
141 }
142 }
143}
144
145#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
147pub struct UnmappedSite {
148 pub site: u32,
149 pub node: String,
150 #[serde(flatten)]
151 pub why: Unmapped,
152 pub required: bool,
154}
155
156#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
158#[serde(rename_all = "kebab-case")]
159pub enum HoleKind {
160 Call,
163 Jump,
166 Unproven,
168}
169
170#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
172pub struct HoleReturn {
173 #[serde(default, skip_serializing_if = "Option::is_none")]
175 pub merged_guard: Option<merged_extent::ExtentGuard>,
176 #[serde(default, skip_serializing_if = "Option::is_none")]
178 pub outside_guard: Option<outside::OutsideGuard>,
179 #[serde(default, skip_serializing_if = "Option::is_none")]
181 pub merged_function: Option<u64>,
182 #[serde(
184 default,
185 skip_serializing_if = "Option::is_none",
186 with = "proof::optional_wire"
187 )]
188 pub outside: Option<String>,
189 #[serde(default)]
191 pub premises: Vec<proof::Premise>,
192 pub address: u64,
193 pub kind: HoleKind,
194 #[serde(default, skip_serializing_if = "Option::is_none")]
196 pub continuation: Option<u64>,
197 #[serde(default)]
199 pub sites: Vec<u32>,
200 #[serde(default, skip_serializing_if = "Option::is_none")]
202 pub reason: Option<String>,
203 #[serde(default)]
208 pub at: Vec<Frame>,
209 #[serde(default)]
211 pub hole_nodes: Vec<u32>,
212 #[serde(default, skip_serializing_if = "Option::is_none")]
215 pub direct: Option<DirectCall>,
216 #[serde(default, skip_serializing_if = "Option::is_none")]
218 #[serde(with = "proof::optional_wire")]
219 pub proof: Option<String>,
220 pub required: bool,
224}
225
226#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
228#[serde(rename_all = "kebab-case")]
229pub enum HoleHow {
230 Call,
232 TailJump,
235 Devirtualized,
238 Inlined,
242}
243
244#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
247pub struct DirectCall {
248 pub address: u64,
249 pub target: u64,
250 pub symbol: String,
251}
252
253#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
256pub struct HoleNode {
257 #[serde(default, skip_serializing_if = "Option::is_none")]
259 pub inline_binding: Option<InlineBinding>,
260 #[serde(default, skip_serializing_if = "Vec::is_empty")]
262 pub merged: Vec<MergedPosition>,
263 #[serde(default)]
265 pub premises: Vec<proof::Premise>,
266 pub site: u32,
267 pub node: String,
268 #[serde(default, skip_serializing_if = "Option::is_none")]
269 pub return_site: Option<u32>,
270 #[serde(default, skip_serializing_if = "Option::is_none")]
271 pub return_node: Option<String>,
272 #[serde(default, skip_serializing_if = "Option::is_none")]
273 pub how: Option<HoleHow>,
274 #[serde(default)]
276 pub addresses: Vec<u64>,
277 #[serde(default)]
279 pub continuations: Vec<u64>,
280 #[serde(default, skip_serializing_if = "Vec::is_empty")]
282 pub direct: Vec<DirectCall>,
283 pub copies: u32,
284 pub copies_with_call: u32,
285 #[serde(default, skip_serializing_if = "Option::is_none")]
287 #[serde(with = "proof::optional_wire")]
288 pub proof: Option<String>,
289 #[serde(default, skip_serializing_if = "Option::is_none")]
290 pub why: Option<String>,
291 #[serde(default, skip_serializing_if = "Option::is_none")]
293 #[serde(with = "proof::optional_wire")]
294 pub return_proof: Option<String>,
295 #[serde(default, skip_serializing_if = "Option::is_none")]
296 pub return_why: Option<String>,
297 pub required: bool,
299 #[serde(default, skip_serializing_if = "Option::is_none")]
301 #[serde(with = "proof::optional_wire")]
302 pub quiet: Option<String>,
303}
304
305pub const PROOF_HOLE: &str = "DWARF scope with the instance's symbol as linkage name (up to v0's instantiating crate); line-table row = the hole node's file and line (the MIR call through a pointer); in each copy, the one indirect call there not held by another call site, or else the one jump through a register there (a tail call)";
307
308pub const PROOF_HOLE_DIRECT: &str = "DWARF scope with the instance's symbol as linkage name (up to v0's instantiating crate); line-table row = the hole node's file and line (the MIR call through a pointer); in each copy, the one indirect call there not held by another call site, or else the one jump through a register there (a tail call), or else the one direct call (or jump) there not held by another call site whose target is a function (a DWARF subprogram's linkage name, or the report's link name or alias at that address) whose symbol the exec row names among the hole's targets (exec.nodes callee: the instances the call through a pointer may reach): the compiler made the call direct, to that target";
310
311pub const PROOF_HOLE_SITE: &str = "the hole node and a mapped call site are one exec block (node ids `<instance>#<block>:hole` and `<instance>#<block>`): one MIR call through a pointer, which the call site's binding ties to its instructions (its proof); the hole node takes its call and jump instructions, one per copy (an address that is no call or jump is the entry of a subroutine inlined at the line: another call there)";
313
314pub const PROOF_HOLE_RETURN: &str =
316 "the address after each bound call instruction: where that call returns";
317
318pub const PROOF_HOLE_DUPLICATED: &str = "DWARF scope with the instance's symbol as linkage name (up to v0's instantiating crate); line-table row = the hole node's file and line; the hole node is the instance's only exec row at that line (no other call site, hole or drop there), so every indirect call there not held by another call site is that one MIR call: a copy holding several (the compiler duplicated the call, as when it copies a loop) is bound at each, and each returns after itself";
320
321pub const PROOF_HOLE_INLINED: &str = "a checked inline-hole certificate joins each observed copy by exact instance, call file, line, column and target identity; a complete decoded instruction inventory contains no residual boundary transfer; descendant observable nodes remain in the graph";
323
324pub const PROOF_HOLE_PURE_CALL: &str = "a call through a callee-saved register whose every reaching definition sets the same constant (PROOF_REGISTER_CONSTANT), the start of a function of the static analysis's report whose name (its link name or a linker alias) is a C function that makes no system call (the pure functions of the boundary map, nornir mimir-ingest `libc_map::PURE`: Mímir's executor writes no call site for a call of one); the call is a direct call to it, which no followed thread stands at (as a direct call to it is no call site)";
326
327pub const PROOF_HOLE_QUIET: &str = "every exec.edges pair out of the hole node goes to its own return node; this graph-path observation alone proves neither machine boundary absence nor a complete syscall bound";
329
330pub const PROOF_HOLE_RETURN_TAIL: &str = "the address after each bound call instruction; for a copy compiled as a tail jump, the jump replaced its function's frame, so the code it enters returns where that function returns: the address after each direct call to the function (every function of the static analysis's report decoded; each function the report says calls it, a tail call included, holds a decoded call or jump to it), and a function that enters it by a tail jump or a fall-through (a jump to its start, or the report's successor into its start, from another function, or the report's call into its start from the function that ends there) returns to its own callers in turn; an address-taken function on the way (the report's) returns after each hole of the site table that may enter it too (a hole that opens a blind section the function is an entry of, by name or as a `fallback` hole: the site floor's premise that an indirect transfer enters only an address-taken function), or where the function holding it returns when that hole is a jump, and, as a signal handler the kernel may enter, at the start of each function that issues rt_sigreturn (the sa_restorer; no system call whose number is not known); no function on the way is the process entry (a thread start is no kernel entry: the clone child resumes after its syscall)";
332
333pub const PROOF_HOLE_EDGE: &str = "an exec.edges pair of the order pass with hole nodes (mimir-exec --holes: Next over the MIR CFG), both of whose ends are bound to instructions (or a start by its entries)";
335
336#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
338pub struct HoleEdge {
339 pub from: u32,
340 pub to: u32,
341 pub from_node: String,
342 pub to_node: String,
343 pub entries: Vec<u32>,
345 pub required: bool,
348 #[serde(default, skip_serializing_if = "Option::is_none")]
349 #[serde(with = "proof::optional_wire")]
350 pub proof: Option<String>,
351 #[serde(default, skip_serializing_if = "Option::is_none")]
352 pub why: Option<String>,
353}
354
355#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
357pub struct Frame {
358 #[serde(default, skip_serializing_if = "Option::is_none")]
359 pub symbol: Option<String>,
360 pub file: String,
361 pub line: u32,
362}
363
364#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
366pub struct EntryFunction {
367 pub entry: u32,
368 pub kind: String,
370 pub instance: String,
371 pub symbol: String,
372 #[serde(default, skip_serializing_if = "Option::is_none")]
373 pub address: Option<u64>,
374 #[serde(default, skip_serializing_if = "Vec::is_empty")]
377 pub addresses: Vec<u64>,
378 #[serde(default, skip_serializing_if = "Vec::is_empty")]
381 pub functions: Vec<u64>,
382 #[serde(default, skip_serializing_if = "Option::is_none")]
384 #[serde(with = "proof::optional_wire")]
385 pub how: Option<String>,
386 #[serde(default, skip_serializing_if = "Option::is_none")]
388 pub reason: Option<String>,
389 pub required: bool,
392}
393
394pub const REQUIRED_ENTRY_KINDS: [&str; 4] = ["process", "thread", "init", "signal"];
396
397#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
399pub struct ThreadEntries {
400 #[serde(default, skip_serializing_if = "Option::is_none")]
402 pub spawn_site: Option<u32>,
403 pub start: u64,
404 #[serde(default, skip_serializing_if = "Option::is_none")]
405 pub function: Option<String>,
406 pub entries: Vec<u32>,
407 pub how: String,
413}
414
415#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
417pub struct BinEdge {
418 pub function: u64,
419 pub from: u64,
420 pub to: u64,
421 pub kind: String,
423}
424
425pub const PROOF_SITE_REPORT: &str = "one report symbol-table function extent, no DWARF copy, one assembly row: every syscall instruction in that extent";
428
429pub const PROOF_HOLE_REPORT: &str = "one report symbol-table function extent, no DWARF copy, one hole and one indirect call: every proven target is an exec candidate";
432
433pub const PROOF_HOLE_UNREACHED: &str = "the node is outside every entry's closure of first nodes over exec.edges; it is no graph position";
435
436pub const PROOF_HOLE_OUTSIDE_REACH: &str = "a positive scope names a body whose aliases uniquely match unreached instances in pinned exec.reached; a complete machine-entry scan excludes direct incoming calls and jumps from outside the jointly excluded bodies and excludes runtime starts; subject to the data-held merged-alias limit, scope-ancestor and exec-reach make this instruction no graph position";
438
439#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
441pub struct MergedPosition {
442 pub address: u64,
443 pub jump: bool,
444 pub continuation: Option<u64>,
445}
446pub const PROOF_HOLE_MERGED: &str = "a line-zero indirect transfer in a report function with positive fitting pointer-call scope evidence; every reachable hole of the complete exec.reached.calls closure of its own instances is a candidate, under code-origin, pointer-call and exec-reach";
448
449pub mod outside;