# What happens when an instance propagates taint via span links instead of parent-child edges in GenAI semantic-convention traces

**Date of Record:** 2026 November 14

**Scope:** Applies to OpenTelemetry GenAI semantic-convention traces (`gen_ai.*` attributes) where prompt-injection taint provenance is encoded by linking an untrusted-input span to downstream tool-invocation or model-generation spans via `SpanLink` rather than `parent_span_id`. Does not apply to traces where taint is carried as an attribute on a single span, or where the collector enforces a DAG traversal over `parent_span_id` only.

## Core Distinction

Taint provenance is a *data-flow* relation, not a *causality* relation. The GenAI semantic conventions define `gen_ai.prompt`, `gen_ai.completion`, and tool-call spans with an implicit expectation that causal ancestry (parent/child) mirrors data flow. When an untrusted document is retrieved, the retrieval span is causally *before* the generation span but is not its parent — the generation span is a child of the user-turn span. Encoding "this completion's tokens were influenced by untrusted content" therefore requires a **span link**, because a span has exactly one parent but may have many links.

The non-obvious invariant: **a link is not traversed by default in most span-tree consumers.** Jaeger, Tempo's TraceQL `{childOf}`, and the OTel `SpanProcessor` hierarchy all walk `parent_span_id`. Links are stored but not queryable as ancestry. A taint-provenance system that emits links and a policy engine that reads parent chains will silently see zero tainted spans.

## What Was Observed

In a retrieval-augmented agent, the retrieval span (`gen_ai.operation.name=retrieval`) was linked to the generation span (`gen_ai.operation.name=chat`) with `Link(attributes={"taint.source": "untrusted_document", "taint.confidence": 0.91})`. The generation span's parent was the orchestrator's user-turn span.

A downstream policy gate queried the trace backend for "spans whose ancestor chain contains an untrusted-source span" and found none. The generation span executed a tool call (`gen_ai.tool.name=send_email`) whose arguments were attacker-controlled. The gate allowed it because the parent chain was clean: user-turn → chat → tool-call. The taint existed only as a link on the chat span, and the tool-call span had no link back to the retrieval span at all — links are not transitive and not inherited by children.

Three compounding failures were observed:

1. **Link non-inheritance.** A child span does not inherit its parent's links. The tool-call span, a child of the chat span, carried no taint link. Policy evaluated at the tool-call span saw an untainted ancestry.
2. **Link cardinality asymmetry.** The retrieval span could link to many generations; the policy engine assumed one-to-one and deduplicated by `trace_id`, dropping all but the first link.
3. **Clock-skew reordering.** Links carry no ordering guarantee. A batch re-indexer replayed spans out of order; the taint link was attached to a generation span whose `start_time` preceded the retrieval span's `end_time` by 40 ms due to cross-node clock skew, and a time-window join discarded it as "causally impossible."

## Condition of Validity

The link-based encoding is valid **only if** the taint consumer performs an explicit forward closure: for every span, union the taint set of its parent with the taint sets of all spans it links to, and propagate that union to all children. This must be recomputed at every span in the tree, not once at the root. It is **invalid** when:

- The consumer queries ancestry via `parent_span_id` only (the default in every major backend).
- The consumer treats links as attributes (read-once) rather than as edges (transitive).
- The trace is sampled such that the retrieval span is dropped but the generation span is kept — a link to a non-exported span is a dangling reference and must be treated as *tainted-unknown*, not *untainted*.

## Decision Boundary

Choose link-based taint encoding when the untrusted source and the influenced span are causally siblings (both children of a shared turn) and the source may influence multiple downstream spans. Choose parent-child encoding — a synthetic `taint.propagation` span that becomes the parent of everything downstream — when the policy engine cannot be modified to traverse links. The synthetic-parent approach preserves default-queryability at the cost of distorting the causal tree (the generation span's true parent is no longer the user turn). Do not mix the two within one trace: a policy engine that handles both will double-count and a human reading the waterfall will misattribute causality.

## Operational Effect

The practical consequence is that **absence of a taint link in an ancestry query is not evidence of safety.** Any gate that reasons "no untrusted ancestor found → allow" is unsound under link-based encoding. The correct gate fails closed on dangling links, propagates taint forward through the full tree including link edges, and treats a link whose target span was not exported as tainted. The following validator enforces the forward-closure invariant and raises when a taint-bearing link cannot be resolved to an exported span or when a consumer is configured for ancestry-only traversal.

```python
from dataclasses import dataclass, field
from typing import Iterable


class TaintClosureError(RuntimeError):
    """Raised when link-based taint provenance cannot be soundly closed."""


@dataclass
class Span:
    span_id: str
    parent_id: str | None
    links: list[str] = field(default_factory=list)          # target span_ids
    taint: set[str] = field(default_factory=set)            # taint labels on this span
    exported: bool = True


def compute_taint_closure(
    spans: Iterable[Span],
    *,
    consumer_traverses_links: bool,
) -> dict[str, set[str]]:
    """
    Forward taint closure over BOTH parent edges and link edges.
    A span's effective taint = own taint UNION parent's closure UNION
    closure of every link target. Children inherit the parent's closure.
    """
    if not consumer_traverses_links:
        raise TaintClosureError(
            "policy consumer traverses parent_span_id only; link-based taint "
            "provenance would be silently invisible (fail-closed required)"
        )

    by_id = {s.span_id: s for s in spans}
    closure: dict[str, set[str]] = {}
    visiting: set[str] = set()

    def resolve(span_id: str) -> set[str]:
        if span_id in closure:
            return closure[span_id]
        if span_id in visiting:
            raise TaintClosureError(f"cycle in taint graph at {span_id}")
        span = by_id.get(span_id)
        if span is None or not span.exported:
            # dangling link target: tainted-unknown, never untainted
            raise TaintClosureError(
                f"taint link target {span_id} not exported; "
                f"treat as tainted-unknown, do not default to clean"
            )
        visiting.add(span_id)
        acc: set[str] = set(span.taint)
        if span.parent_id is not None:
            acc |= resolve(span.parent_id)
        for target in span.links:
            acc |= resolve(target)
        visiting.discard(span_id)
        closure[span_id] = acc
        return acc

    for s in by_id:
        resolve(s)
    return closure


def gate_tool_call(
    tool_span: Span,
    closure: dict[str, set[str]],
    *,
    denied_taints: set[str] = frozenset({"untrusted_document"}),
) -> None:
    effective = closure.get(tool_span.span_id, set())
    hit = effective & denied_taints
    if hit:
        raise TaintClosureError(
            f"tool span {tool_span.span_id} ({tool_span.span_id}) blocked: "
            f"inherited taint {sorted(hit)} via link closure"
        )
```