crates/heimdall-probe/src/minimise.rs
// SPDX-License-Identifier: AGPL-3.0-only
// Copyright (C) 2026 Ignalina ApS and Vetra Automation AB
//! Merge and minimise (spec §3.1 step 3): observations -> the smallest rule
//! set. Heimdall is a defensive sandbox: exact argument matches where the
//! observed values form a small set, masks for flag fields, a bare allow only
//! where the recorded arguments vary freely (and that is reported).
use std::collections::{BTreeMap, BTreeSet};
use heimdall_seccomp::{Action, ArgCmp, Profile, ProfileError, Rule, Width};
use serde::{Deserialize, Serialize};
use crate::facts::{fixed_rules, is_wx, spec, Kind, VDSO_NOTE};
use crate::observe::{Call, Observations};
/// Generator options (from the workload manifest).
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct GenOptions {
/// At most this many distinct exact tuples per call; more = bare allow.
pub exact_limit: usize,
/// Keep `PROT_WRITE|PROT_EXEC` mappings in the profile (a JIT that
/// needs them). Off by default: they are reported and left out.
pub allow_wx: bool,
}
impl Default for GenOptions {
fn default() -> GenOptions {
GenOptions {
exact_limit: 16,
allow_wx: false,
}
}
}
/// A call and the runs that made it, for the review.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct Finding {
pub call: String,
pub runs: Vec<String>,
}
/// What a person reviews beside the rules (spec §3.1 step 5, §3.3).
#[derive(Clone, Debug, PartialEq, Eq, Default, Serialize, Deserialize)]
pub struct Review {
/// The corpus runs (tests) the profile was probed with.
pub runs: Vec<String>,
/// Calls seen only in error-path runs (kept in the profile, listed so a
/// person sees what only the error paths need).
#[serde(default)]
pub near_miss: Vec<Finding>,
/// `PROT_WRITE|PROT_EXEC` mappings seen (left out unless `allow_wx`).
#[serde(default)]
pub wx: Vec<Finding>,
/// Calls whose recorded arguments varied too much: bare allow.
#[serde(default)]
pub bare: Vec<String>,
/// Calls the arch table does not name (never allowed).
#[serde(default)]
pub unknown: Vec<Finding>,
/// Fixed rules every profile carries.
#[serde(default)]
pub fixed: Vec<String>,
#[serde(default)]
pub notes: Vec<String>,
}
/// A generated profile and its review.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Generated {
#[serde(flatten)]
pub profile: Profile,
pub review: Review,
}
impl Generated {
/// `<arch>-<libc>.json`: the profile fields, then the review.
pub fn to_json(&self) -> String {
serde_json::to_string_pretty(self).expect("a profile serializes") + "\n"
}
/// Read a generated `.json` back (validated).
pub fn from_json(s: &str) -> Result<Generated, ProfileError> {
let g: Generated =
serde_json::from_str(s).map_err(|e| ProfileError::Json(e.to_string()))?;
g.profile.validate()?;
Ok(g)
}
}
fn mask_of(w: Width) -> u64 {
match w {
Width::W32 => 0xffff_ffff,
Width::W64 => u64::MAX,
}
}
/// Minimise observations into a profile.
pub fn generate(obs: &Observations, opts: GenOptions) -> Generated {
let mut review = Review {
runs: obs
.runs
.iter()
.map(|r| r.name.clone())
.collect::<BTreeSet<_>>()
.into_iter()
.collect(),
notes: vec![VDSO_NOTE.to_string()],
..Review::default()
};
let errors = obs.error_runs();
// Calls grouped by syscall (BTreeMap: sorted, deterministic).
let mut by_name: BTreeMap<&str, Vec<(&Call, &BTreeSet<String>)>> = BTreeMap::new();
for (c, runs) in &obs.calls {
by_name
.entry(c.syscall.as_str())
.or_default()
.push((c, runs));
if !runs.is_empty() && runs.iter().all(|r| errors.contains(r.as_str())) {
review.near_miss.push(Finding {
call: c.describe(),
runs: runs.iter().cloned().collect(),
});
}
}
for (u, runs) in &obs.unknown {
review.unknown.push(Finding {
call: u.clone(),
runs: runs.iter().cloned().collect(),
});
}
let fixed = fixed_rules();
let mut rules = Vec::new();
for (name, calls) in by_name {
if fixed.iter().any(|f| f.syscall == name) {
continue;
}
let Some(s) = spec(name) else {
rules.push(Rule::bare(name, Action::Allow));
continue;
};
match s.kind {
Kind::Flags => {
let mut alt = Vec::new();
for &(i, w) in s.args {
let union = calls
.iter()
.filter_map(|(c, _)| c.arg(i))
.fold(0u64, |a, v| a | v);
alt.push(ArgCmp {
arg: i,
width: w,
mask: !union & mask_of(w),
value: 0,
});
}
rules.push(Rule {
syscall: name.to_string(),
action: Action::Allow,
when: vec![alt],
});
}
Kind::Exact => {
let mut tuples: BTreeSet<Vec<u64>> = BTreeSet::new();
for (c, runs) in &calls {
let t: Vec<u64> = s.args.iter().map(|&(i, _)| c.arg(i).unwrap_or(0)).collect();
if s.prot && t.iter().any(|v| is_wx(*v)) && !opts.allow_wx {
review.wx.push(Finding {
call: c.describe(),
runs: runs.iter().cloned().collect(),
});
continue;
}
tuples.insert(t);
}
if tuples.is_empty() {
continue;
}
if tuples.len() > opts.exact_limit {
review.bare.push(format!(
"{name}: {} distinct argument values > {}: bare allow",
tuples.len(),
opts.exact_limit
));
rules.push(Rule::bare(name, Action::Allow));
continue;
}
let when = tuples
.into_iter()
.map(|t| {
s.args
.iter()
.zip(t)
.map(|(&(i, w), v)| ArgCmp {
arg: i,
width: w,
mask: mask_of(w),
value: v,
})
.collect()
})
.collect();
rules.push(Rule {
syscall: name.to_string(),
action: Action::Allow,
when,
});
}
}
}
for f in fixed {
review.fixed.push(format!(
"{}: {} (answered by the probe in learning mode too)",
f.syscall, f.action
));
rules.push(f);
}
rules.sort();
review.near_miss.sort();
review.wx.sort();
review.unknown.sort();
Generated {
profile: Profile {
workload: obs.workload.clone(),
arch: obs.arch,
libc: obs.libc,
rules,
},
review,
}
}