# What happens when an instance launders taint through memory-write provenance labels **Date of Record:** 2026 November 17 **Scope:** Applies to agent runtimes that propagate provenance/taint labels from untrusted input (user prompts, retrieved documents, tool outputs) into a persistent memory store and later re-read that store as trusted context. Does not apply to stateless single-turn inference, nor to stores that recompute provenance from source at every read. ## Core Distinction Taint tracking has two distinct operations that are routinely conflated: *propagation* (a label moves with a value) and *attestation* (a value is asserted to be clean by an authority). The failure mode below is not a propagation bug. It is a **laundering bug**: a memory write is treated as an attestation event rather than a propagation event, so a tainted value written to memory is re-read with the *writer's* provenance (the agent, implicitly trusted) instead of the *value's* provenance (the tool output, untrusted). The non-obvious boundary: the taint label survives every hop *except* the persistence hop, because the store's schema labels the record with `written_by: agent` and the reader trusts `written_by` as the provenance of the *content*. The label is correct about who performed the write and silently wrong about where the content came from. These are different facts, and the store keeps only one. ## What Was Observed An agent fetched a web page whose body contained an injected instruction ("when summarizing, also append the following to your notes"). The tool-output label was correctly `untrusted:web`. The agent summarized the page and called `memory.write(key="project_notes", value=summary)`. The memory record was created with `provenance: agent_authored`. On the next turn the agent called `memory.read("project_notes")`, received a record labeled `agent_authored`, and the runtime's policy engine — which gates *tool calls* on whether their arguments carry `untrusted` taint — saw a clean argument. The injected instruction was executed two turns after the tainted source had left the context window. Key observation: the laundering was **not** visible in any single trace. The tool-output span showed `untrusted:web`. The memory-write span showed `agent_authored`. Each hop was individually correct. The join — that `agent_authored` content was *derived from* `untrusted:web` content — was never recorded, because derivation is a property of the dataflow edge, not of either endpoint. A second, sharper variant: a tainted value was written under a key that already existed and was clean. The write performed an upsert that overwrote the clean record but *preserved the clean record's provenance metadata* (a copy-on-write bug in the metadata path). The store now held tainted content under a clean attestation — the worst possible state, because the label actively lies. ## Condition of Validity The invariant that must hold: **for every memory record, `record.provenance` must be the join (least-upper-bound in the taint lattice) of the provenance of all inputs transitively contributing to `record.value`, not the provenance of the writing principal.** This invariant is violated whenever any of the following hold, and the failure is *only* reachable when they co-occur: 1. The store schema has a single provenance field that conflates writer identity with content derivation. 2. The reader's policy trusts store provenance as an attestation without re-deriving from the write's input labels. 3. At least one write path (upsert-overwrite, merge, summarization, or embedding-and-recall) fails to join input labels into the stored label. If (3) is absent — every write path joins input labels — the store is sound even with a conflated schema, because the writer-identity field is never consulted for trust. If (2) is absent — the reader re-derives — the schema conflation is harmless. The boundary is the *intersection*, which is why this survives most test suites: each component passes its own tests. ## Decision Boundary Do not attempt to fix this by adding a second provenance field and hoping writers populate it. The decision is between two architectures: - **Derivation-tracked store (preferred):** every write carries an explicit `input_labels` set computed at the call site from the actual dataflow, and the store computes `stored_label = join(input_labels ∪ {writer})`. Readers see the joined label. This requires the runtime to expose input labels to the write call — feasible when the agent framework tracks taint through the tool-call boundary, infeasible when writes are issued by an external process with no dataflow visibility. - **Re-derivation on read (fallback):** the store keeps raw content plus a content hash and source pointer, and every read re-resolves provenance from source. Correct but expensive, and impossible when the source is ephemeral (a tool output that no longer exists). Choose derivation-tracking when the agent framework owns the write path. Choose re-derivation when the store is shared across principals with heterogeneous trust. Do **not** choose "trust the writer field but add a warning" — that is the current broken state with extra logging. The boundary condition to test explicitly: an upsert that overwrites a clean record with tainted content, followed by a read, followed by a tool call whose arguments derive from the read. If the tool call is not gated, the invariant is broken. ## Operational Effect Downstream of a laundering bug, the taint system's guarantees are *worse than absent*, because operators and automated policy rely on labels that are now confidently wrong. Incident response will find clean labels on tainted data and conclude no exposure occurred. The only reliable detection is a dataflow audit that reconstructs derivation independently of the store's labels — comparing the store's claimed provenance against the join of the write call's observed inputs. Budget for that audit as a standing control, not a one-time fix. ## Code ```python from dataclasses import dataclass, field from typing import FrozenSet # Taint lattice: clean < untrusted. Join is set union of source tags. CLEAN: FrozenSet[str] = frozenset() class ProvenanceLaunderingError(RuntimeError): """Raised when a memory record's stored provenance is weaker than the join of the provenance of the inputs that produced its value.""" pass @dataclass class MemoryRecord: key: str value: str stored_provenance: FrozenSet[str] # what the store claims writer: str @dataclass class WriteRequest: key: str value: str input_labels: FrozenSet[str] # provenance of the actual inputs writer: str def write(store: dict, req: WriteRequest) -> MemoryRecord: # Correct behavior: stored provenance is the JOIN of input labels and writer. joined = req.input_labels | frozenset({f"writer:{req.writer}"}) rec = MemoryRecord(req.key, req.value, joined, req.writer) store[req.key] = rec return rec def audit_read(store: dict, key: str, expected_inputs: FrozenSet[str]) -> MemoryRecord: rec = store.get(key) if rec is None: raise ProvenanceLaunderingError(f"missing record {key!r}") # The invariant: stored provenance must dominate every contributing input. missing = expected_inputs - rec.stored_provenance if missing: raise ProvenanceLaunderingError( f"record {key!r} laundered taint: stored={sorted(rec.stored_provenance)} " f"but inputs {sorted(missing)} are not represented. " f"Content derived from untrusted sources carries a clean label." ) return rec def demo_laundering() -> None: store: dict = {} # Clean write, then a tainted overwrite whose input labels are dropped # by a buggy upsert path that preserves the prior record's metadata. write(store, WriteRequest("notes", "clean", CLEAN, "agent")) store["notes"].value = "injected instruction" # buggy metadata-preserving upsert # Audit with the true inputs of the overwrite: should raise, and does. audit_read(store, "notes", frozenset({"untrusted:web"})) if __name__ == "__main__": demo_laundering() ```