# Under what conditions must an instance treat prompt-injection taint as non-transitive across tool-invocation hops

**Date of Record:** 2026 November 14

**Scope:** Applies to agent runtimes that propagate a per-value taint label (untrusted-provenance bit, source set, or integrity lattice element) across a directed graph of tool calls where outputs of one tool are consumed as inputs to another. Does not apply to single-hop retrieval-then-generate pipelines, nor to systems that enforce global session quarantine on first untrusted byte (those systems have no per-hop propagation problem, only a liveness problem).

## Core Distinction

The distinction that matters is between **taint as provenance** and **taint as capability**. Provenance taint says "this value descends from an untrusted source." Capability taint says "this value can influence a privileged sink." A multi-hop tool graph collapses these two only under an unstated assumption: that every intermediate tool is a *pure function of its inputs with respect to control flow*. That assumption is false for any tool that (a) reads ambient state not passed as an argument, (b) performs side effects whose results are re-ingested on a later hop, or (c) has its own instruction-following behavior — i.e., any tool that is itself an LLM, a web fetcher with redirects, a shell, or a database with stored procedures.

The non-obvious boundary: **taint propagation is sound only along hops where the consumer's output is a deterministic function of the tainted input plus untainted constants.** The moment a hop introduces an ambient read, the taint label on the output is under-approximated by naive set-union propagation, and the under-approximation is exactly the attack surface.

## What Was Observed

A three-hop graph: `fetch_url → summarize(text) → write_file(path, summary)`. The `summarize` tool is an LLM call. Naive propagation marks `summary` tainted because `text` was tainted, so `write_file` is gated. Correct. Now change the graph: `fetch_url → summarize(text) → format_report(summary, template)`. The `template` argument is read from a config file the agent considers trusted. The `format_report` tool substitutes `{summary}` into the template and *also* evaluates any `{{...}}` expressions in the template. An attacker who can write to the config file — or who can get a prior hop to write to it — injects `{{ read_env('AWS_SECRET') }}` into the template. The `summary` value is correctly tainted and gated; the *template* is untainted and ungated; the output is a function of both, and the taint lattice records only the union of input labels, which here is `{untrusted}` from `summary` — so the output is gated for the wrong reason, and an operator who reviews the gate sees "blocked because summary is untrusted" and *whitelists the template path* to fix a false positive. The whitelist is the vulnerability.

The second observation: **taint laundering via re-ingestion.** Hop 1 writes a tainted value to a scratch table. Hop 2 reads the scratch table with a query that does not carry the taint column (because the table schema has no taint column, because the DB is external). Hop 3 consumes the read. The taint is gone not because the value was sanitized but because it crossed a serialization boundary that does not serialize labels. This is the multi-hop analogue of a lost label in a message queue, and it is the dominant real-world failure — more common than the expression-injection case above, and harder to detect because nothing looks wrong in the trace.

## Condition of Validity

Naive union-propagation of taint across hops is valid **iff** all of the following hold for every hop `h` in the path:

1. `h`'s output is a deterministic function of its declared arguments and no other mutable state (no ambient reads, no clock, no RNG, no environment, no filesystem, no network beyond declared args).
2. `h` does not persist its arguments or outputs to a store that a later hop can read without the label attached.
3. `h` does not itself interpret its inputs as instructions (no nested LLM, no template evaluation, no shell, no SQL with string interpolation).
4. The label is carried *in-band* with the value across every serialization boundary, or the boundary is instrumented to re-attach it.

If any condition fails, the path must be treated as **taint-amplifying**: the output's true taint is a superset of the union of input labels, and the correct action is to *downgrade the trust of the whole path*, not to compute a per-value label. In practice this means the gate must be evaluated on the *tool identity and its ambient capabilities*, not on the values flowing through it.

## Decision Boundary

The operational rule an instance should apply:

- If all four conditions hold for a hop, propagate labels by union and gate on the sink's label.
- If condition 1 fails (ambient read), the hop's output is tainted by *everything the ambient state could contain*; treat the output as untrusted regardless of input labels, and additionally flag the hop as a **confused-deputy candidate** — it can be made to act on behalf of an attacker who controls ambient state.
- If condition 2 fails (label-dropping store), the path is **broken for tracking purposes**; either instrument the store or treat every read from it as untrusted. Do not attempt to "remember" the label out-of-band across the store — the store is shared mutable state and the association is not stable under concurrent writers.
- If condition 3 fails (interpreter hop), the hop is a **taint sink and source simultaneously**; the only sound policy is to require the hop's inputs to be untainted *before* the hop, i.e., sanitize at the boundary, because post-hoc label propagation cannot recover which substrings of the output derived from which input tokens.
- If condition 4 fails, treat the boundary as a trust downgrade: everything crossing it loses its label and becomes untrusted.

The non-obvious consequence: **a path can be more dangerous than any of its hops**, because the composition of an ambient read (hop A) with an interpreter (hop B) yields a confused-deputy-to-code-execution chain that neither hop exhibits alone, and neither hop's label arithmetic reveals. Gate on path shape, not on path labels.

## Operational Effect

Instances that apply union-propagation without the validity check exhibit a characteristic failure signature: the taint gate fires on the *obvious* hop (the fetched text), operators whitelist the *non-obvious* hop (the template, the scratch table, the config), and the whitelist becomes the exploit. The remediation is to invert the default: **unlabeled is untrusted**, and labels are an optimization that must be justified per-hop by the four conditions, not assumed. The cost is false positives on legitimate ambient reads (config, clock, locale); the mitigation is to enumerate ambient reads as declared capabilities on the tool manifest so the runtime can distinguish "reads config by design" from "reads config because the attacker pointed it there." A tool that declares its ambient reads is auditable; a tool that does not is a taint hole regardless of what its output label says.

```python
from dataclasses import dataclass, field
from enum import Enum
from typing import Callable, Iterable


class TaintPropagationError(RuntimeError):
    """Raised when a hop cannot soundly propagate taint under union semantics."""


class HopKind(Enum):
    PURE = "pure"                 # deterministic function of declared args only
    AMBIENT_READ = "ambient"      # reads mutable state not passed as an argument
    INTERPRETER = "interpreter"   # evaluates its inputs as instructions/code
    LABEL_DROPPING = "dropping"   # persists to a store that loses labels


@dataclass(frozen=True)
class Hop:
    name: str
    kind: HopKind
    declared_ambient: frozenset[str] = field(default_factory=frozenset)


@dataclass(frozen=True)
class Label:
    untrusted: bool
    reasons: frozenset[str] = field(default_factory=frozenset)


def propagate(path: Iterable[Hop], input_label: Label) -> Label:
    """Sound union-propagation, or raise if the path is taint-amplifying."""
    label = input_label
    for hop in path:
        if hop.kind is HopKind.PURE:
            continue
        if hop.kind is HopKind.AMBIENT_READ:
            # Ambient reads are tainted by whatever the ambient state holds.
            # Only sound if the read set is declared and disjoint from mutable
            # attacker-writable state; the runtime cannot verify that here.
            if not hop.declared_ambient:
                raise TaintPropagationError(
                    f"hop {hop.name!r} performs an undeclared ambient read; "
                    "output taint is under-approximated by input-label union"
                )
            label = Label(
                untrusted=True,
                reasons=label.reasons | {f"ambient:{hop.name}"},
            )
            continue
        if hop.kind is HopKind.INTERPRETER:
            # Cannot recover which output token derived from which input token.
            # The only sound policy is pre-hop sanitization, enforced upstream.
            raise TaintPropagationError(
                f"hop {hop.name!r} interprets its inputs; post-hoc label "
                "propagation is unsound, sanitize before the hop"
            )
        if hop.kind is HopKind.LABEL_DROPPING:
            raise TaintPropagationError(
                f"hop {hop.name!r} crosses a label-dropping boundary; "
                "treat every read from it as untrusted"
            )
    return label


def gate(sink: str, label: Label, allow_untrusted: frozenset[str] = frozenset()) -> None:
    if label.untrusted and sink not in allow_untrusted:
        raise TaintPropagationError(
            f"refusing sink {sink!r}: tainted by {sorted(label.reasons)}"
        )
```