car_engine/

taint.rs

//! Runtime taint provenance — which state keys currently hold a value
//! derived from an untrusted tool result.
//!
//! The VIGIL intent gate ([`crate::intent_gate`]) hard-blocks an
//! out-of-intent action when that action is *tool-stream-influenced* —
//! reachable from an untrusted tool result. That reachability was
//! computed from two inputs only: the tool NAMES listed in
//! `.car/intent.json`'s `untrusted_tools`, and the `depends_on` edges
//! **inside the one proposal being admitted**. Both inputs are static, and
//! that leaves two live holes an injection walks straight through:
//!
//! 1. **Laundering through a trusted tool.** `fetch_web` (untrusted) writes
//!    attacker-controlled content into state key `page`. A later
//!    `read_file`/`summarize` — a tool the operator listed in
//!    `allowed_tools`, and rightly so — reads `page` and carries the same
//!    attacker text forward. Its own tool name is trusted, so nothing marks
//!    it, and an out-of-intent action downstream of it reads as the model's
//!    own drift (escalate to approval) rather than as the injection
//!    signature (hard block).
//! 2. **Laundering through a replan.** The poisoned `fetch_web` action is in
//!    the PREVIOUS proposal. The replanned proposal has no dependency edge
//!    reaching back to it — proposals are separate DAGs — so at admission
//!    time the new plan looks pristine even when its actions read the exact
//!    state key the poisoned result wrote.
//!
//! The executor is the only component that knows, at execution time, which
//! SPECIFIC results were tainted. This ledger is where it records that, and
//! it is what turns `intent_actions_from`'s long-empty `untrusted_ids`
//! argument into a real input.
//!
//! ## The model
//!
//! Taint is carried by **state keys**, partitioned by tenant (`None` = the
//! untenanted flat namespace), because state is the only channel by which
//! one action's result reaches another action across proposal boundaries.
//! After each successful action the executor calls [`TaintLedger::record_result`]:
//!
//! - the action's result is tainted if its tool is in `untrusted_tools` **or**
//!   any key in its [`car_ir::Action::effective_read_set`] is already tainted
//!   for that tenant (taint flows through the running session, not just one
//!   proposal's DAG);
//! - a tainted result taints every key the action wrote;
//! - a **trusted** result CLEARS every key it wrote — a fresh trusted write
//!   is new provenance, so taint does not accumulate monotonically until the
//!   whole namespace is untouchable.
//!
//! At admission, [`TaintLedger::untrusted_action_ids`] names every action in
//! the incoming proposal whose read set intersects the tainted keys. Those
//! ids go to `car_verify::intent::intent_actions_from` as `untrusted_ids`,
//! and `check_intent` propagates from there along `depends_on` exactly as
//! before. Nothing about the verify core changes; it finally gets the
//! provenance it always accepted.
//!
//! ## Honest limitations
//!
//! - **Taint is per state key, not per byte within a result.** If an action
//!   reads a tainted key and writes a key, the whole written value is
//!   treated as tainted — even when the attacker-controlled span never
//!   reached it. That over-approximates (the safe direction for a security
//!   check) and it means a long-lived key that once held untrusted content
//!   stays tainted until some trusted action overwrites it.
//! - **A tool that reads an open environment WITHOUT declaring the read
//!   can only be caught by naming it in `untrusted_tools`.** The ledger sees
//!   `effective_read_set()` / `effective_write_set()` — declared state
//!   dependencies, assumptions, and effects. A tool that reaches the network
//!   or the filesystem directly, out of band of the state store, declares
//!   nothing, so nothing propagates. That is precisely what the static
//!   `untrusted_tools` list is for; this ledger extends it, it does not
//!   replace it.
//! - **The clear is attacker-reachable.** A trusted result clearing the keys
//!   it wrote is correct data-flow semantics — after the overwrite the key
//!   genuinely holds untainted content — but an injected plan can *arrange*
//!   that overwrite. One extra in-intent action is enough: a trusted tool
//!   with the tainted key in its `expected_effects` and no declared read is
//!   admitted by the gate and wipes the key from the ledger, after which the
//!   out-of-intent action escalates to approval instead of hard-rejecting.
//!   The value the follow-on action reads is not attacker-derived, so this
//!   launders the LEDGER, not the data. It is not a regression: the ceiling
//!   on the attack is exactly the pre-change verdict (an approval
//!   escalation), which is what the attacker got before this ledger existed.
//! - **Taint fires only on DECLARED reads, and the declaration is
//!   model-authored.** [`car_ir::Action::effective_read_set`] is `read_set` +
//!   `state_dependencies` + assumption keys — all plan fields an injected
//!   model writes. An out-of-intent action that simply omits its
//!   `state_dependencies` reads the poisoned value through dispatch and is
//!   never marked by the ledger. This is the reader-side twin of the
//!   writer-side limitation above, and it is the cheaper of the two
//!   evasions. Same ceiling: omitting the declaration recovers the
//!   pre-change behavior (approval escalation), nothing beyond it.
//! - **The executor's idempotency dedup path does not re-taint.** A cached
//!   hit returns the stored [`car_ir::ActionResult`] before `execute_with_retry`
//!   runs, so `record_result` is never called for it — a re-proposed
//!   idempotent untrusted tool does not re-taint a key some trusted action
//!   cleared in between. The dedup path also commits no state (it only
//!   *reports* the cached `state_changes`), so the ledger stays in step with
//!   the store; the caveat is for a consumer that reads those reported
//!   changes as if a write had just happened.
//! - **The ledger is process-local and in-memory.** It reflects the taint
//!   this runtime observed since it started. It is not persisted and does
//!   not survive a restart, so a restart re-opens the pre-existing static
//!   behavior until a tainted result is observed again.

use std::collections::{HashMap, HashSet};
use tokio::sync::RwLock;

/// Runtime-observed taint provenance: the state keys, per tenant, that
/// currently hold a value derived from an untrusted tool result.
///
/// Owned by the [`crate::Runtime`] and installed alongside the VIGIL intent
/// gate — no intent gate, no ledger, so an unconfigured runtime pays
/// nothing. See the module docs for the threat model and the limitations.
pub struct TaintLedger {
    /// Tools whose RESULTS are attacker-influenceable by construction (web
    /// fetch, inbox read, …) — the same list the intent gate uses, captured
    /// so the ledger can decide taint without reaching back into the gate.
    untrusted_tools: HashSet<String>,
    /// tenant (`None` = untenanted) → the tainted state keys for it.
    tainted: RwLock<HashMap<Option<String>, HashSet<String>>>,
}

impl TaintLedger {
    /// Build a ledger over the configured untrusted tool names.
    pub fn new(untrusted_tools: HashSet<String>) -> Self {
        Self {
            untrusted_tools,
            tainted: RwLock::new(HashMap::new()),
        }
    }

    /// The configured untrusted tool names.
    pub fn untrusted_tools(&self) -> &HashSet<String> {
        &self.untrusted_tools
    }

    /// Record the provenance of one **successful** action.
    ///
    /// `written_keys` is what the action actually changed (the executor's
    /// `state_changes`: declared `expected_effects` plus the state
    /// transitions dispatch produced). The result is tainted when the
    /// action's tool is untrusted, or when it read a key that is already
    /// tainted for `tenant`; a tainted result taints every written key and a
    /// trusted one clears them.
    ///
    /// Failed actions must NOT be recorded — a failed action commits no
    /// effects, so it changes no provenance.
    pub async fn record_result(
        &self,
        tenant: Option<&str>,
        action: &car_ir::Action,
        written_keys: impl IntoIterator<Item = String>,
    ) {
        let written: Vec<String> = written_keys.into_iter().collect();
        if written.is_empty() {
            // Nothing reached state, so nothing's provenance changed.
            return;
        }
        let tool_is_untrusted = action
            .tool
            .as_ref()
            .map(|t| self.untrusted_tools.contains(t))
            .unwrap_or(false);
        let reads = action.effective_read_set();

        // One write lock for the read-then-mutate: a read lock followed by a
        // write lock would let a concurrently-executing action interleave
        // between the taint decision and the commit of it.
        let mut guard = self.tainted.write().await;
        let key = tenant.map(str::to_string);
        let entry = guard.entry(key).or_default();
        let tainted = tool_is_untrusted || reads.iter().any(|k| entry.contains(k));

        if tainted {
            for k in written {
                entry.insert(k);
            }
        } else {
            for k in &written {
                entry.remove(k);
            }
        }
    }

    /// The ids of `actions` whose read set intersects `tenant`'s tainted
    /// keys — exactly the `untrusted_ids` input
    /// `car_verify::intent::intent_actions_from` takes.
    ///
    /// Tools named in `untrusted_tools` are deliberately NOT re-derived
    /// here: `intent_actions_from` already marks those from the tool name.
    /// This answers the question the tool name cannot — *did this action
    /// read something a previous untrusted result wrote?*
    pub async fn untrusted_action_ids(
        &self,
        tenant: Option<&str>,
        actions: &[car_ir::Action],
    ) -> HashSet<String> {
        let guard = self.tainted.read().await;
        let Some(keys) = guard.get(&tenant.map(str::to_string)) else {
            return HashSet::new();
        };
        if keys.is_empty() {
            return HashSet::new();
        }
        actions
            .iter()
            .filter(|a| a.effective_read_set().iter().any(|k| keys.contains(k)))
            .map(|a| a.id.clone())
            .collect()
    }

    /// The tainted state keys for `tenant` — for tests and observability.
    pub async fn tainted_keys(&self, tenant: Option<&str>) -> HashSet<String> {
        self.tainted
            .read()
            .await
            .get(&tenant.map(str::to_string))
            .cloned()
            .unwrap_or_default()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use car_ir::{Action, ActionType};

    fn tool_action(id: &str, tool: &str) -> Action {
        let mut a = Action::new(ActionType::ToolCall);
        a.id = id.to_string();
        a.tool = Some(tool.to_string());
        a.max_retries = 0;
        a
    }

    fn ledger() -> TaintLedger {
        TaintLedger::new(["fetch_web".to_string()].into_iter().collect())
    }

    #[tokio::test]
    async fn a_trusted_tool_reading_a_tainted_key_is_untrusted() {
        // The laundering case: fetch_web (untrusted) writes `page`; a later
        // `summarize` (a tool the intent explicitly allows) reads `page`.
        // Its tool name says trusted, its provenance says otherwise — and
        // provenance is what the injection signature is made of.
        let led = ledger();
        led.record_result(None, &tool_action("a1", "fetch_web"), ["page".to_string()])
            .await;
        assert!(led.tainted_keys(None).await.contains("page"));

        let mut summarize = tool_action("a2", "summarize");
        summarize.state_dependencies.push("page".to_string());
        let ids = led.untrusted_action_ids(None, &[summarize]).await;
        assert!(
            ids.contains("a2"),
            "an action reading a tainted key must be reported untrusted: {ids:?}"
        );
    }

    #[tokio::test]
    async fn taint_flows_through_a_trusted_intermediate() {
        // Two hops, no dependency edge needed: fetch_web → page,
        // summarize(page) → digest. `digest` is tainted even though
        // `summarize` is a trusted tool, so an action reading only `digest`
        // is still untrusted.
        let led = ledger();
        led.record_result(None, &tool_action("a1", "fetch_web"), ["page".to_string()])
            .await;
        let mut summarize = tool_action("a2", "summarize");
        summarize.state_dependencies.push("page".to_string());
        led.record_result(None, &summarize, ["digest".to_string()])
            .await;
        assert!(led.tainted_keys(None).await.contains("digest"));

        let mut pay = tool_action("a3", "send_payment");
        pay.state_dependencies.push("digest".to_string());
        assert!(led.untrusted_action_ids(None, &[pay]).await.contains("a3"));
    }

    #[tokio::test]
    async fn a_trusted_overwrite_clears_the_taint() {
        // Taint must not be monotone — a fresh trusted write to the key is
        // new provenance, otherwise a long session degenerates into every
        // key tainted forever.
        let led = ledger();
        led.record_result(None, &tool_action("a1", "fetch_web"), ["page".to_string()])
            .await;
        assert!(led.tainted_keys(None).await.contains("page"));

        // A trusted tool that reads nothing tainted, writing the same key.
        led.record_result(None, &tool_action("a2", "summarize"), ["page".to_string()])
            .await;
        assert!(
            !led.tainted_keys(None).await.contains("page"),
            "a trusted overwrite must clear the key"
        );

        let mut reader = tool_action("a3", "send_payment");
        reader.state_dependencies.push("page".to_string());
        assert!(led.untrusted_action_ids(None, &[reader]).await.is_empty());
    }

    #[tokio::test]
    async fn taint_does_not_cross_tenants() {
        // State is tenant-partitioned in the store; provenance over it has
        // to be partitioned the same way, or one tenant's untrusted fetch
        // starts hard-blocking another tenant's legitimate work.
        let led = ledger();
        led.record_result(
            Some("tenant-a"),
            &tool_action("a1", "fetch_web"),
            ["page".to_string()],
        )
        .await;

        let mut reader = tool_action("b1", "summarize");
        reader.state_dependencies.push("page".to_string());
        assert!(led
            .untrusted_action_ids(Some("tenant-a"), std::slice::from_ref(&reader))
            .await
            .contains("b1"));
        assert!(led
            .untrusted_action_ids(Some("tenant-b"), std::slice::from_ref(&reader))
            .await
            .is_empty());
        assert!(led
            .untrusted_action_ids(None, std::slice::from_ref(&reader))
            .await
            .is_empty());
    }

    #[tokio::test]
    async fn an_action_writing_nothing_changes_nothing() {
        let led = ledger();
        led.record_result(None, &tool_action("a1", "fetch_web"), Vec::new())
            .await;
        assert!(led.tainted_keys(None).await.is_empty());
    }

    #[tokio::test]
    async fn an_untainted_ledger_reports_no_untrusted_ids() {
        let led = ledger();
        let mut reader = tool_action("a1", "summarize");
        reader.state_dependencies.push("page".to_string());
        assert!(led.untrusted_action_ids(None, &[reader]).await.is_empty());
    }
}