car-verify 0.35.0

//! Intent-grounded action verification (arXiv 2601.05755, *VIGIL: Defending LLM
//! Agents Against Tool Stream Injection via Verify-Before-Commit*).
//!
//! See `docs/proposals/intent-grounded-verification.md`. VIGIL's threat is
//! **tool stream injection**: a manipulated tool result (metadata, runtime
//! feedback) hijacks the agent into actions the user never asked for — exfiltrate
//! a file, call a payment tool, touch a resource outside the task. Its defense is
//! *verify-before-commit*: anchor a **root of trust in the user's original
//! intent**, then validate each tentative action against that intent before
//! committing it; injected actions are rejected pre-execution.
//!
//! That is CAR's own thesis ("models propose; the runtime validates and
//! executes") applied to control-flow integrity. This module is the deterministic
//! core: bound a session to an [`IntentSpec`] (the tools/resources the task
//! authorizes and the capabilities it forbids) and flag any action that drifts
//! outside it — **blocking commit** when the drifting action is *tool-stream-
//! influenced* (reachable from an untrusted tool result via the dependency
//! graph), which is the injection signature.
//!
//! Distinct from its neighbours: [`crate::infoflow`] guards *data confidentiality*
//! (sensitive bytes reaching a sink); [`crate::permission`]-style tiers guard
//! *risk class*. This guards **scope drift from the declared task** — an action
//! can be low-risk and leak nothing yet still be an injected detour. The three
//! compose.

use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet};

/// The root of trust: what the user's original intent authorizes. Anything an
/// action does outside this surface is drift; combined with tool-stream
/// influence, it is an injection.
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct IntentSpec {
    /// Tools the task is allowed to call (exact names). Empty ⇒ no tool
    /// restriction (every tool is in-intent).
    #[serde(default)]
    pub allowed_tools: Vec<String>,
    /// Resource identifiers/prefixes the task may target — matched as prefixes,
    /// so `"db/users/"` authorizes `"db/users/42"`. Empty ⇒ no resource
    /// restriction.
    #[serde(default)]
    pub allowed_resources: Vec<String>,
    /// Capabilities the intent explicitly forbids (e.g. `"exfiltrate"`,
    /// `"payment"`, `"delete"`). An action declaring one is always blocked.
    #[serde(default)]
    pub forbidden_capabilities: Vec<String>,
}

/// A tentative action awaiting verify-before-commit.
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct IntentAction {
    pub id: String,
    /// The tool this action invokes, if any.
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub tool: Option<String>,
    /// Resources this action targets (writes/affects) — checked against
    /// [`IntentSpec::allowed_resources`].
    #[serde(default)]
    pub targets: Vec<String>,
    /// Capabilities this action exercises — checked against
    /// [`IntentSpec::forbidden_capabilities`].
    #[serde(default)]
    pub capabilities: Vec<String>,
    /// Ids of the actions/results this action depends on (data or control). Used
    /// to propagate tool-stream influence.
    #[serde(default)]
    pub depends_on: Vec<String>,
    /// This action *directly* carries untrusted tool-stream output (it is, or
    /// consumes, a tool result from an open environment). Influence propagates to
    /// dependents transitively.
    #[serde(default)]
    pub untrusted: bool,
}

/// Why an action is out of intent.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum IntentViolationKind {
    /// Calls a tool the intent did not authorize.
    ToolOutOfIntent,
    /// Targets a resource outside the declared scope.
    TargetOutOfIntent,
    /// Exercises a forbidden capability.
    ForbiddenCapability,
}

/// A single intent violation by one action.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct IntentViolation {
    pub action: String,
    pub kind: IntentViolationKind,
    /// The offending tool name / resource / capability.
    pub detail: String,
    /// The action is reachable from an untrusted tool result — the tool-stream-
    /// injection signature. Drives whether the violation blocks commit.
    pub tool_influenced: bool,
    pub explanation: String,
}

/// The verify-before-commit verdict over a plan.
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct IntentReport {
    /// True when nothing must be blocked from committing.
    pub safe: bool,
    /// Action ids that must NOT commit (injected detours + forbidden
    /// capabilities). The runtime rejects these before execution.
    pub commit_blocked: Vec<String>,
    /// Every intent violation found, blocking or not.
    pub violations: Vec<IntentViolation>,
}

/// Compute the set of action ids that are tool-stream-influenced: directly
/// `untrusted`, or transitively dependent on something that is.
fn influenced_set(actions: &[IntentAction]) -> HashSet<String> {
    let by_id: HashMap<&str, &IntentAction> = actions.iter().map(|a| (a.id.as_str(), a)).collect();
    let mut influenced: HashSet<String> = HashSet::new();

    // Memoized DFS over depends_on. An action is influenced iff it is untrusted
    // or any (transitive) dependency is.
    fn visit(
        id: &str,
        by_id: &HashMap<&str, &IntentAction>,
        influenced: &mut HashSet<String>,
        visiting: &mut HashSet<String>,
    ) -> bool {
        if influenced.contains(id) {
            return true;
        }
        // Cycle guard: treat an in-progress node as not-yet-influencing to avoid
        // infinite recursion; a real influence still surfaces via another path.
        if !visiting.insert(id.to_string()) {
            return false;
        }
        let result = match by_id.get(id) {
            Some(a) => {
                a.untrusted
                    || a.depends_on
                        .iter()
                        .any(|d| visit(d, by_id, influenced, visiting))
            }
            // Unknown dependency id: conservatively not influenced (it isn't an
            // action in this plan; nothing we can attribute).
            None => false,
        };
        visiting.remove(id);
        if result {
            influenced.insert(id.to_string());
        }
        result
    }

    for a in actions {
        let mut visiting = HashSet::new();
        visit(&a.id, &by_id, &mut influenced, &mut visiting);
    }
    influenced
}

/// True if `target` is covered by any allowed prefix (or there are no
/// restrictions).
fn covered(target: &str, allowed: &[String]) -> bool {
    allowed.is_empty() || allowed.iter().any(|p| target.starts_with(p.as_str()))
}

/// Verify a plan's actions against the user intent (VIGIL verify-before-commit).
///
/// For each action:
/// - a **forbidden capability** is always commit-blocking (the intent says no);
/// - a **tool/target out of intent** is commit-blocking *when the action is
///   tool-stream-influenced* — that is the injection signature; an out-of-intent
///   action that is **not** influenced is the model's own under-specified drift,
///   reported but not hard-blocked (surface it; don't abort a legitimate task).
///
/// `safe` is true iff nothing is commit-blocked.
pub fn check_intent(intent: &IntentSpec, actions: &[IntentAction]) -> IntentReport {
    let influenced = influenced_set(actions);
    let mut violations = Vec::new();
    let mut commit_blocked: Vec<String> = Vec::new();

    for a in actions {
        let tainted = influenced.contains(&a.id);
        let mut block = false;
        let mut push = |kind: IntentViolationKind, detail: String, explanation: String| {
            violations.push(IntentViolation {
                action: a.id.clone(),
                kind,
                detail,
                tool_influenced: tainted,
                explanation,
            });
        };

        // Tool out of intent.
        if let Some(tool) = &a.tool {
            if !intent.allowed_tools.is_empty() && !intent.allowed_tools.contains(tool) {
                let why = if tainted {
                    format!(
                        "tool '{tool}' is outside the user's intent and the call is influenced by \
                         an untrusted tool result — likely tool-stream injection; reject before commit"
                    )
                } else {
                    format!("tool '{tool}' is outside the user's declared intent")
                };
                push(IntentViolationKind::ToolOutOfIntent, tool.clone(), why);
                block |= tainted;
            }
        }

        // Target out of intent.
        for t in &a.targets {
            if !covered(t, &intent.allowed_resources) {
                let why = if tainted {
                    format!(
                        "target '{t}' is outside the intent's resource scope and is influenced by \
                         an untrusted tool result — likely injection; reject before commit"
                    )
                } else {
                    format!("target '{t}' is outside the intent's declared resource scope")
                };
                push(IntentViolationKind::TargetOutOfIntent, t.clone(), why);
                block |= tainted;
            }
        }

        // Forbidden capability — always blocks, influenced or not.
        for c in &a.capabilities {
            if intent.forbidden_capabilities.contains(c) {
                push(
                    IntentViolationKind::ForbiddenCapability,
                    c.clone(),
                    format!("capability '{c}' is forbidden by the user's intent"),
                );
                block = true;
            }
        }

        if block {
            commit_blocked.push(a.id.clone());
        }
    }

    IntentReport {
        safe: commit_blocked.is_empty(),
        commit_blocked,
        violations,
    }
}

// ---------------------------------------------------------------------------
// Slice 2 — gate: map an IntentReport to an enforcement disposition.
//
// `check_intent` *detects*; `gate_intent` *decides what to do*, mirroring
// `infoflow::gate_flow`. Injections (tool-stream-influenced drift) and forbidden
// capabilities always block; the model's own untainted drift is policy-driven
// (HITL by default). The HITL bridge against the durable approval ledger lives
// in `car_policy::intent_gate` (it needs the ledger), exactly as `flow_gate`
// sits beside `infoflow`.
// ---------------------------------------------------------------------------

/// What the gate does with an intent violation.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum IntentDisposition {
    /// Proceed (commit the action).
    Allow,
    /// Suspend autonomy pending a human decision (HITL).
    RequireApproval,
    /// Refuse the commit outright.
    Block,
}

fn default_on_untainted_drift() -> IntentDisposition {
    IntentDisposition::RequireApproval
}

/// Policy for gating an [`IntentReport`]. Injections (tool-stream-influenced
/// drift) and forbidden capabilities always `Block` regardless of policy — only
/// the model's *untainted* drift is configurable.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct IntentGatePolicy {
    /// Disposition for out-of-intent drift that is **not** tool-stream-
    /// influenced (the model's own under-specified deviation, not a clear
    /// injection). Default: `RequireApproval`.
    #[serde(default = "default_on_untainted_drift")]
    pub on_untainted_drift: IntentDisposition,
}

impl Default for IntentGatePolicy {
    fn default() -> Self {
        Self {
            on_untainted_drift: default_on_untainted_drift(),
        }
    }
}

/// The gate's verdict over an [`IntentReport`].
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct IntentGateDecision {
    /// The most severe disposition required (`Block` > `RequireApproval` >
    /// `Allow`).
    pub action: IntentDisposition,
    /// Violations that must block the commit (injections + forbidden
    /// capabilities, plus any drift the policy blocks).
    pub blocked: Vec<IntentViolation>,
    /// Violations escalated to a human.
    pub needs_approval: Vec<IntentViolation>,
    pub reason: String,
}

/// Map an [`IntentReport`] to an [`IntentGateDecision`] under `policy`. A
/// forbidden capability or a tool-stream-influenced drift always blocks (the
/// injection signature); untainted drift follows `policy.on_untainted_drift`.
pub fn gate_intent(report: &IntentReport, policy: &IntentGatePolicy) -> IntentGateDecision {
    let mut blocked = Vec::new();
    let mut needs_approval = Vec::new();

    for v in &report.violations {
        let disposition = if v.kind == IntentViolationKind::ForbiddenCapability || v.tool_influenced
        {
            IntentDisposition::Block
        } else {
            policy.on_untainted_drift
        };
        match disposition {
            IntentDisposition::Block => blocked.push(v.clone()),
            IntentDisposition::RequireApproval => needs_approval.push(v.clone()),
            IntentDisposition::Allow => {}
        }
    }

    let action = if !blocked.is_empty() {
        IntentDisposition::Block
    } else if !needs_approval.is_empty() {
        IntentDisposition::RequireApproval
    } else {
        IntentDisposition::Allow
    };

    let reason = match action {
        IntentDisposition::Block => format!(
            "blocked: {} action(s) must not commit ({} also need approval)",
            blocked.len(),
            needs_approval.len()
        ),
        IntentDisposition::RequireApproval => format!(
            "{} out-of-intent action(s) require human approval before commit",
            needs_approval.len()
        ),
        IntentDisposition::Allow => "all actions are within the declared intent".to_string(),
    };

    IntentGateDecision {
        action,
        blocked,
        needs_approval,
        reason,
    }
}

// ---------------------------------------------------------------------------
// Slice 4 — IR populater: build IntentActions from a plan's car_ir Actions, so
// the runtime assembles the verify-before-commit input from its own IR rather
// than the caller hand-building it.
// ---------------------------------------------------------------------------

/// Derive [`IntentAction`]s from a plan's [`car_ir::Action`]s (VIGIL Slice 4).
///
/// - `tool` ← `Action.tool`
/// - `targets` ← `effective_write_set` (declared writes + a `StateWrite`'s key)
/// - `capabilities` ← `metadata["capabilities"]` (a JSON string array) if present
/// - `depends_on` ← the executor's [`car_ir::dependency_edges`] — the *same* DAG
///   the runtime sequences on — mapped to action ids, so influence propagates
///   along real data/control dependencies
/// - `untrusted` ← the action's `tool` is in `untrusted_tools` (tools whose
///   output is attacker-controllable — web/file/remote reads in an open
///   environment), OR its id is in `untrusted_ids` (the executor marked this
///   specific result tainted from tool-result provenance)
///
/// The two provenance inputs are facts the harness holds, not the IR: which
/// tools read untrusted surfaces, and which concrete results came back tainted.
pub fn intent_actions_from(
    actions: &[car_ir::Action],
    untrusted_tools: &HashSet<String>,
    untrusted_ids: &HashSet<String>,
) -> Vec<IntentAction> {
    let edges = car_ir::dependency_edges(actions);
    actions
        .iter()
        .enumerate()
        .map(|(i, a)| {
            let depends_on = edges[i].iter().map(|&d| actions[d].id.clone()).collect();
            let capabilities = a
                .metadata
                .get("capabilities")
                .and_then(|v| v.as_array())
                .map(|arr| {
                    arr.iter()
                        .filter_map(|x| x.as_str().map(String::from))
                        .collect()
                })
                .unwrap_or_default();
            let untrusted = untrusted_ids.contains(&a.id)
                || a.tool
                    .as_ref()
                    .map(|t| untrusted_tools.contains(t))
                    .unwrap_or(false);
            IntentAction {
                id: a.id.clone(),
                tool: a.tool.clone(),
                targets: a.effective_write_set(),
                capabilities,
                depends_on,
                untrusted,
            }
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    fn act(id: &str) -> IntentAction {
        IntentAction {
            id: id.into(),
            ..Default::default()
        }
    }

    fn intent() -> IntentSpec {
        IntentSpec {
            allowed_tools: vec!["search".into(), "read_file".into()],
            allowed_resources: vec!["docs/".into()],
            forbidden_capabilities: vec!["exfiltrate".into(), "payment".into()],
        }
    }

    #[test]
    fn in_intent_plan_is_safe() {
        let actions = vec![IntentAction {
            tool: Some("read_file".into()),
            targets: vec!["docs/readme.md".into()],
            ..act("a1")
        }];
        let r = check_intent(&intent(), &actions);
        assert!(r.safe, "{r:?}");
        assert!(r.violations.is_empty());
    }

    #[test]
    fn injected_tool_call_is_blocked() {
        // a1 is an untrusted tool result; a2 (a forbidden, out-of-intent tool)
        // depends on it → influenced → blocked.
        let actions = vec![
            IntentAction {
                tool: Some("search".into()),
                untrusted: true,
                ..act("a1")
            },
            IntentAction {
                tool: Some("send_email".into()),
                depends_on: vec!["a1".into()],
                ..act("a2")
            },
        ];
        let r = check_intent(&intent(), &actions);
        assert!(!r.safe);
        assert_eq!(r.commit_blocked, vec!["a2".to_string()]);
        let v = r.violations.iter().find(|v| v.action == "a2").unwrap();
        assert_eq!(v.kind, IntentViolationKind::ToolOutOfIntent);
        assert!(v.tool_influenced);
    }

    #[test]
    fn out_of_intent_but_untainted_is_reported_not_blocked() {
        // The model itself calls an unlisted tool, not downstream of any tool
        // result → drift, surfaced but not hard-blocked.
        let actions = vec![IntentAction {
            tool: Some("send_email".into()),
            ..act("a1")
        }];
        let r = check_intent(&intent(), &actions);
        assert!(r.safe, "untainted drift doesn't block commit: {r:?}");
        assert_eq!(r.violations.len(), 1);
        assert!(!r.violations[0].tool_influenced);
    }

    #[test]
    fn forbidden_capability_always_blocks() {
        // Even untainted, a forbidden capability is rejected.
        let actions = vec![IntentAction {
            tool: Some("read_file".into()),
            capabilities: vec!["exfiltrate".into()],
            ..act("a1")
        }];
        let r = check_intent(&intent(), &actions);
        assert!(!r.safe);
        assert_eq!(r.commit_blocked, vec!["a1".to_string()]);
        assert_eq!(
            r.violations[0].kind,
            IntentViolationKind::ForbiddenCapability
        );
    }

    #[test]
    fn influence_propagates_transitively() {
        // a1 untrusted → a2 depends on a1 → a3 depends on a2; a3 targets an
        // out-of-scope resource → blocked via transitive influence.
        let actions = vec![
            IntentAction {
                tool: Some("search".into()),
                untrusted: true,
                ..act("a1")
            },
            IntentAction {
                depends_on: vec!["a1".into()],
                ..act("a2")
            },
            IntentAction {
                targets: vec!["secrets/key".into()],
                depends_on: vec!["a2".into()],
                ..act("a3")
            },
        ];
        let r = check_intent(&intent(), &actions);
        assert_eq!(r.commit_blocked, vec!["a3".to_string()]);
        let v = &r.violations[0];
        assert_eq!(v.kind, IntentViolationKind::TargetOutOfIntent);
        assert!(v.tool_influenced);
    }

    #[test]
    fn empty_intent_imposes_no_tool_or_resource_limit() {
        let actions = vec![IntentAction {
            tool: Some("anything".into()),
            targets: vec!["anywhere".into()],
            untrusted: true,
            ..act("a1")
        }];
        let r = check_intent(&IntentSpec::default(), &actions);
        assert!(r.safe, "no restrictions ⇒ nothing out of intent: {r:?}");
    }

    #[test]
    fn gate_blocks_injection_and_escalates_drift() {
        // a1 untrusted → a2 (injected out-of-intent tool) blocked; a3 is the
        // model's own untainted drift → escalated to HITL by default policy.
        let actions = vec![
            IntentAction {
                tool: Some("search".into()),
                untrusted: true,
                ..act("a1")
            },
            IntentAction {
                tool: Some("send_email".into()),
                depends_on: vec!["a1".into()],
                ..act("a2")
            },
            IntentAction {
                tool: Some("delete_file".into()),
                ..act("a3")
            },
        ];
        let report = check_intent(&intent(), &actions);
        let decision = gate_intent(&report, &IntentGatePolicy::default());
        assert_eq!(decision.action, IntentDisposition::Block);
        assert_eq!(decision.blocked.len(), 1);
        assert_eq!(decision.blocked[0].action, "a2");
        assert_eq!(decision.needs_approval.len(), 1);
        assert_eq!(decision.needs_approval[0].action, "a3");
    }

    #[test]
    fn gate_allow_drift_policy_lets_untainted_through() {
        let actions = vec![IntentAction {
            tool: Some("delete_file".into()),
            ..act("a1")
        }];
        let report = check_intent(&intent(), &actions);
        let policy = IntentGatePolicy {
            on_untainted_drift: IntentDisposition::Allow,
        };
        let decision = gate_intent(&report, &policy);
        assert_eq!(decision.action, IntentDisposition::Allow);
        assert!(decision.blocked.is_empty() && decision.needs_approval.is_empty());
    }

    #[test]
    fn populater_maps_ir_to_intent_actions() {
        // The executor's DAG keys reads off `state_dependencies` and writes off
        // `expected_effects`, so use those (the same fields `dependency_edges`
        // sequences on).
        let actions: Vec<car_ir::Action> = serde_json::from_str(
            r#"[
                {"id":"fetch","type":"tool_call","tool":"web_fetch","expected_effects":{"page":"x"}},
                {"id":"act","type":"tool_call","tool":"send_email","state_dependencies":["page"],
                 "expected_effects":{"outbox":"y"},"metadata":{"capabilities":["network"]}}
            ]"#,
        )
        .unwrap();
        let untrusted_tools: HashSet<String> = ["web_fetch".to_string()].into_iter().collect();
        let derived = intent_actions_from(&actions, &untrusted_tools, &HashSet::new());

        let fetch = derived.iter().find(|a| a.id == "fetch").unwrap();
        assert!(fetch.untrusted, "web_fetch reads an open surface");
        assert_eq!(fetch.targets, vec!["page".to_string()]);

        let act = derived.iter().find(|a| a.id == "act").unwrap();
        assert_eq!(
            act.depends_on,
            vec!["fetch".to_string()],
            "reads what fetch wrote"
        );
        assert_eq!(act.capabilities, vec!["network".to_string()]);
        assert!(!act.untrusted, "its own tool isn't an untrusted source");
    }

    #[test]
    fn populated_plan_blocks_injected_action() {
        // A search result (untrusted) feeds an out-of-intent send_email →
        // check_intent, fed the populated actions, blocks it.
        let actions: Vec<car_ir::Action> = serde_json::from_str(
            r#"[
                {"id":"fetch","type":"tool_call","tool":"search","expected_effects":{"page":"x"}},
                {"id":"send","type":"tool_call","tool":"send_email","state_dependencies":["page"]}
            ]"#,
        )
        .unwrap();
        let untrusted: HashSet<String> = ["search".to_string()].into_iter().collect();
        let ia = intent_actions_from(&actions, &untrusted, &HashSet::new());
        let intent = IntentSpec {
            allowed_tools: vec!["search".into()],
            ..Default::default()
        };
        let r = check_intent(&intent, &ia);
        assert_eq!(r.commit_blocked, vec!["send".to_string()]);
    }

    #[test]
    fn dependency_cycle_does_not_hang() {
        let actions = vec![
            IntentAction {
                depends_on: vec!["a2".into()],
                ..act("a1")
            },
            IntentAction {
                depends_on: vec!["a1".into()],
                untrusted: true,
                ..act("a2")
            },
        ];
        // a2 is untrusted; a1 depends on a2 → both influenced; terminates.
        let inf = influenced_set(&actions);
        assert!(inf.contains("a2") && inf.contains("a1"));
    }
}