# Why does an instance of prompt-injection taint appear to vanish when an agent delegates to a sub-agent whose trace spans are emitted on a different clock domain than the parent

**Date of Record:** 2026 November 11

**Scope:** Applies to multi-agent systems where a parent agent invokes nested sub-agents and taint (untrusted-origin data derived from a prompt-injection surface) is propagated via trace context (W3C `traceparent`/`tracestate` or an equivalent correlation header) rather than via in-band payload tagging. Does not apply to single-process agents that carry taint in the message object itself, nor to systems where every span is stamped by a single monotonic source.

## Core Distinction

The distinction that matters is between *taint propagation as a data-flow property* and *taint propagation as a trace-correlation artifact*. Operators routinely conflate the two because, in the happy path, they coincide: a tainted input causes a tainted span, and the span's `trace_id` links it to the parent. The failure is that taint is inferred post-hoc by joining spans on `trace_id` and ordering them by `start_time`. When a nested agent runs on a different clock domain — a separate container with its own monotonic clock, a serverless invocation whose wall clock is NTP-step-adjusted, or a cross-region worker — the parent and child spans can be emitted with `start_time` values that are *inconsistent* with causal order. The join still succeeds (the `trace_id` matches), but the *ordering* used to reconstruct "which span introduced the taint" resolves to the wrong span, or to no span at all.

The non-obvious part: the taint did not disappear. The correlation query that reconstructs taint lineage silently returns a truncated or misordered chain, and downstream policy (e.g., "block any tool call whose ancestor span is tainted") evaluates against an incomplete ancestor set. The system reports "no tainted ancestor" — a false negative — while the tainted data is, in fact, flowing through the call.

## What Was Observed

In a three-level agent topology (planner → retriever-subagent → tool-executor), a prompt injection arrived in a retrieved document. The retriever-subagent correctly tagged the span with `taint=external_untrusted` in `tracestate`. The tool-executor, two hops down, executed a side-effecting call. The post-incident correlation query — `SELECT ancestors WHERE trace_id = X ORDER BY start_time` — returned the planner and the tool-executor spans but *dropped the retriever span from the ordered ancestor chain*. The retriever had been scheduled on a node whose clock was 340 ms behind the planner's; its `start_time` landed *before* the planner's own root span. The ordering-based lineage walk terminated early because the "first" span in the chain was the retriever, which had no parent pointer resolving to a span with a lower timestamp. The taint tag existed in storage but was unreachable by the traversal.

A second, subtler observation: when the skew exceeded the sub-agent's total runtime (a fast sub-agent on a slow-clock node), the child span's `start_time` preceded the parent's `start_time` entirely. Some tracers reject this as an invalid span at ingestion, dropping the taint-bearing span silently. The trace looked complete; the taint record was gone.

## Condition of Validity

The inference "taint propagates across a nested call iff the child span carries a taint tag in its `tracestate` and is a descendant of the tainted span by `trace_id`" is valid **only** when the following invariant holds:

> For every parent-child span pair `(P, C)` in the same trace, `P.start_time ≤ C.start_time` under a *shared* clock reference, and `C` is retained at ingestion.

This invariant is *not* guaranteed by `trace_id` propagation. `trace_id` guarantees *identity* of the trace, not *ordering* within it. Clock-domain skew, NTP steps, and ingestion-side span rejection each violate the invariant independently. When the invariant is violated, any lineage reconstruction that uses timestamp ordering as a proxy for causal order is unsound, and taint queries built on it produce false negatives.

The invariant *does* hold — and the inference is valid — when taint is carried in-band (in the message payload) rather than reconstructed from span ordering, or when spans are ordered by an explicit causal token (e.g., a per-trace Lamport counter or a `parent_span_id`-linked DAG walk that never consults `start_time`).

## Decision Boundary

The operational decision is: **do you trust timestamp-ordered lineage for taint enforcement, or do you require a causal-order primitive?**

- If taint enforcement gates side-effecting tool calls, you **must** walk the `parent_span_id` graph (a DAG), not `ORDER BY start_time`. The DAG walk is invariant to clock skew because it uses explicit edges.
- If the tracer drops spans with `start_time` preceding the parent (skew > runtime), you **must** either disable that validation for cross-domain traces or carry taint on the *parent* span's `tracestate` as a "downward" propagation flag so the taint survives even if the child span is dropped.
- If you cannot change the tracer, treat any trace where `min(child.start_time) < parent.start_time` as *taint-unknown*, not *taint-clean*. Fail closed.

The boundary is crossed the moment a taint-bearing span is ordered by a clock that is not the clock that ordered its parent. Below that boundary, timestamp lineage is a fine approximation. Above it, it is a silent false-negative generator.

## Operational Effect

The practical consequence is a class of **fail-open taint gaps**: the security control reports "clean" precisely when the tainted data is most deeply nested — i.e., when it has passed through the most delegation hops and is closest to a side-effecting action. Because the gap correlates with delegation depth, it is systematically biased toward the highest-risk calls. Teams that instrument taint only at the leaf and reconstruct lineage by timestamp will see a clean dashboard while injections traverse the full agent chain. The remediation is to (a) propagate taint downward in `tracestate` so it is present on every descendant span regardless of ordering, and (b) reconstruct lineage via `parent_span_id` DAG traversal, treating any span whose causal position cannot be established as taint-unknown and failing closed.

```python
from __future__ import annotations
from dataclasses import dataclass


class TaintLineageError(RuntimeError):
    """Raised when taint lineage cannot be established from trace data."""


@dataclass(frozen=True)
class Span:
    span_id: str
    parent_span_id: str | None
    trace_id: str
    start_time_ns: int
    taint: str | None  # e.g. "external_untrusted" or None


def reconstruct_taint_lineage(spans: list[Span], leaf_span_id: str) -> list[Span]:
    """Walk parent_span_id edges (NOT start_time) to find tainted ancestors.

    Fails closed: if the causal chain is broken or a clock-skew anomaly is
    detected, raises TaintLineageError rather than returning a clean result.
    """
    by_id = {s.span_id: s for s in spans}
    if leaf_span_id not in by_id:
        raise TaintLineageError(
            f"leaf span {leaf_span_id!r} absent from trace; cannot establish taint lineage"
        )

    chain: list[Span] = []
    cursor: Span | None = by_id[leaf_span_id]
    seen: set[str] = set()

    while cursor is not None:
        if cursor.span_id in seen:
            raise TaintLineageError(f"cycle detected at span {cursor.span_id!r}")
        seen.add(cursor.span_id)
        chain.append(cursor)

        if cursor.parent_span_id is None:
            break

        parent = by_id.get(cursor.parent_span_id)
        if parent is None:
            # Parent span was dropped at ingestion (often due to clock-skew
            # validation). We cannot prove the ancestor is clean.
            raise TaintLineageError(
                f"parent span {cursor.parent_span_id!r} of {cursor.span_id!r} "
                f"missing from trace; taint state is UNKNOWN, not clean"
            )

        # Detect the clock-domain anomaly explicitly: a child that starts
        # before its parent indicates cross-domain skew, so timestamp-based
        # ordering downstream would be unsound.
        if cursor.start_time_ns < parent.start_time_ns:
            raise TaintLineageError(
                f"clock-skew anomaly: span {cursor.span_id!r} starts before parent "
                f"{parent.span_id!r}; timestamp lineage is unsound, fail closed"
            )

        cursor = parent

    return chain


def enforce_taint_policy(spans: list[Span], leaf_span_id: str) -> None:
    """Block side-effecting calls when any ancestor is tainted."""
    try:
        lineage = reconstruct_taint_lineage(spans, leaf_span_id)
    except TaintLineageError as exc:
        # Fail closed: unknown taint state blocks the action.
        raise TaintLineageError(
            f"refusing side-effecting call: {exc}"
        ) from exc

    tainted = [s for s in lineage if s.taint]
    if tainted:
        raise TaintLineageError(
            f"side-effecting call blocked: tainted ancestor "
            f"{tainted[0].span_id!r} (taint={tainted[0].taint!r})"
        )
```