# How does an instance detect taint-laundering through idempotent tool-output caches **Date of Record:** 2026 November 16 **Scope:** Applies to agent runtimes that propagate provenance labels (e.g., `trusted:system`, `trusted:user`, `untrusted:tool_output`) across tool calls and cache results keyed on `(tool_name, canonical_args_hash)`. Does not apply to runtimes that re-fetch every tool output per turn with no cross-turn or cross-session memoization, nor to label schemes where taint is attached to the message envelope rather than the payload. ## Core Distinction Taint tracking for prompt injection is usually framed as a *propagation* problem: does an untrusted byte sequence reach a sink (a tool that executes code, sends mail, or mutates state)? The non-obvious failure is not propagation — it is **provenance collapse at a deduplication boundary**. When a tool-output cache returns a previously-seen result, the runtime must decide which provenance label to attach to the *cache hit*. The label that is correct for the *original* fetch is not necessarily correct for the *replaying* context, because the cache key omits the caller's taint state. Concretely: a tool invoked from a `trusted:user` turn produces output, cached with label `trusted:user` (the caller's label is often used as the default output label when the tool is declared "pure"). A later turn whose context contains an injected instruction causes the *same tool with the same args* to be invoked from an `untrusted:tool_output` lineage. The cache returns the hit and the runtime re-attaches the *stored* label — `trusted:user` — laundering untrusted influence into a trusted sink. The taint did not propagate; it was **re-labeled by the cache**. ## What Was Observed In a runtime using a content-addressed result cache with a 30-minute TTL, the following sequence was reproducible: 1. Turn 1 (`trusted:user`): `fetch_url("https://docs.example/a")` → output cached, label `trusted:tool_output` (tool declared pure, caller trusted). 2. Turn 4: an injected string in a retrieved document instructs the agent to re-run `fetch_url("https://docs.example/a")` and then pass its body to `send_email`. The instruction itself carries `untrusted:tool_output`. 3. Turn 5: `fetch_url` cache hit. Runtime attaches stored label `trusted:tool_output`. The `send_email` sink's policy admits `trusted:tool_output` inputs. Exfiltration succeeds. The taint-tracking invariant — *"every value derived from an untrusted source retains at least that untrusted label"* — was satisfied on the *first* derivation and violated on the *second*, because the cache is not a derivation; it is a substitution, and the runtime's label-join rule treated a cache hit as a fresh trusted derivation rather than as a re-materialization under a new caller. A second, subtler variant: the cache key included `tool_name` and `args_hash` but **not the taint of the caller**. Two callers with different provenance produced the same key. The cache is therefore a *provenance-blind* function unless the label is part of the key or part of the join. ## Condition of Validity The invariant "cache hits preserve the label of the original fetch" is valid only when **all** of the following hold: - The cache key includes the caller's provenance label (or a monotone summary of it), so a tainted caller cannot address a trusted entry. - The tool is *pure with respect to the caller's context*: its output depends only on `(tool_name, args)`, not on ambient session state. - The label lattice has a join (`⊔`) that is monotone and the runtime applies `caller_label ⊔ stored_label` on every hit, never `stored_label` alone. - Cache entries are invalidated when the tool's declaration (e.g., "pure") changes, since purity is what licensed the trusted default in the first place. If any condition fails, the cache is a taint-laundering channel. In the observed runtime, condition 1 and condition 3 both failed; the failure was masked because the tool was declared pure, which made the *stored* label look correct in isolation. ## Decision Boundary The operational question is not "is the cache safe?" but "**is this hit a re-derivation or a substitution?**" - If the hit is **re-derivation** (tool is pure, key includes caller taint, join applied) → treat the hit as a fresh tool call and label it `caller_label ⊔ stored_label`. - If the hit is **substitution** (key omits caller taint, or tool is impure) → the hit must be treated as `untrusted:tool_output` regardless of stored label, or the cache must be bypassed. A useful heuristic: **a cache hit is only as trustworthy as the least-trusted caller that can address its key.** If an untrusted caller can produce the same key, the entry's effective label is `untrusted` for that caller. Deduplication is a join over the provenance of *all* possible addressers, not just the one that populated the entry. ## Operational Effect Two concrete consequences for runtime design: 1. **Key partitioning.** Include a provenance class in the cache key (`(tool, args_hash, caller_taint_class)`), or maintain per-taint-class namespaces. This trades hit rate for soundness; the hit-rate loss is bounded by the number of distinct taint classes (typically 2–3), which is acceptable. 2. **Sink-side re-check.** Sinks that admit `trusted:tool_output` must additionally verify that the value's *cache lineage* did not include an untrusted caller. This is a second label — `lineage_taint` — joined at the sink, not at the cache. The failure is silent: no error, no policy violation at the cache, and the taint tracker reports the value as trusted because it *is* trusted relative to the original fetch. Detection requires an explicit check that the cache key's addressable-caller set is a subset of the label's trusted set. ```python from dataclasses import dataclass from typing import Hashable class TaintLaunderingError(RuntimeError): """Raised when a cache hit would re-label a value more trusted than its addressable callers.""" @dataclass(frozen=True) class Provenance: label: str # e.g. "trusted:user", "untrusted:tool_output" rank: int # lower = more trusted; join = max rank def join(self, other: "Provenance") -> "Provenance": return self if self.rank >= other.rank else other TRUSTED = Provenance("trusted:user", 0) UNTRUSTED = Provenance("untrusted:tool_output", 2) class ToolOutputCache: def __init__(self) -> None: # key -> (payload, stored_provenance, addressable_caller_ranks) self._store: dict[Hashable, tuple[bytes, Provenance, set[int]]] = {} def put(self, key: Hashable, payload: bytes, stored: Provenance, caller: Provenance) -> None: ranks = self._store.get(key, (b"", stored, set()))[2] ranks.add(caller.rank) self._store[key] = (payload, stored, ranks) def get(self, key: Hashable, caller: Provenance) -> tuple[bytes, Provenance]: if key not in self._store: raise KeyError(key) payload, stored, caller_ranks = self._store[key] # The entry is addressable by any caller that shares the key; its # effective label must be the join over all addressable callers. effective = stored for r in caller_ranks: effective = effective.join(Provenance("", r)) effective = effective.join(caller) if effective.rank < stored.rank: raise TaintLaunderingError( f"cache hit for {key!r} would upgrade {stored.label} " f"to {effective.label} for caller {caller.label}" ) return payload, effective def admit_to_sink(value_label: Provenance, sink_admits: Provenance) -> None: if value_label.rank > sink_admits.rank: raise TaintLaunderingError( f"sink admits up to {sink_admits.label}, got {value_label.label}" ) ```