When Containment Becomes the Attack: Denial-of-Service Against Transitive Taint Propagation in Shared Agent State

Abstract

Shared-state autonomous-agent systems increasingly coordinate through persistent memory, blackboards, retrieval stores, summaries, and other common state. Transitive Taint Propagation (TTP) addresses a central trust problem in such systems: once a record is identified as poisoned, a provenance graph can be traversed to find and contain downstream records that derived from it. Security soundness, however, is not the same as operational survivability. An adversary may deliberately influence where poison enters the graph, which records depend on it, which observations become recorded dependencies, which trusted agents relay it, or which record is designated as poisoned. A correct containment mechanism can then become the means by which the adversary disables legitimate state. We define this failure mode as Containment Denial-of-Service (CDoS): adversarial manipulation of dependency structure, poison placement, propagation characteristics, or poison designation that causes correct transitive containment to disable substantially more legitimate system state than the attacker directly compromised. We contribute a formal system and threat model, a frozen eight-class attack taxonomy, six measurement constructs that report security and availability together, and CSR-BENCH-1.0, a deterministic synthetic benchmark with independently authored ground truth. The preregistered evaluation compares seven containment baselines across nine directed-acyclic graph families, matched poison-placement controls, observed-edge admission controls, and matched cross-session controls. Primary outcomes are Containment Pressure Index, Collateral Containment Rate, Attacker Leverage Factor, Weighted Critical Asset Loss, Residual Exposure Rate, and a multidimensional Recovery Burden vector. The confirmatory campaign is designed to determine when a low attacker budget can induce high legitimate-state loss while containment remains security-sound. It measures the failure; it does not propose a mitigation or claim that any runtime eliminates CDoS. Empirical findings: Across 69,930 verified confirmatory trials, median attacker leverage under exact observed-reachable containment was 3301.3 quarantined records per poison seed, median containment pressure was 1.00, median residual exposure was 0.00, and 7883 trials (78.9%) met the preregistered high-impact convention. Early and hub placements produced positive matched leverage effects. The preregistered tracking-width, policy footprint-reduction, criticality-divergence, and cross-session leverage hypotheses were not supported. Pre-containment graph features predicted high-impact events with cross-validated AUPRC 0.9983 against a 0.7499 prevalence baseline. A containment mechanism can remain materially sound while becoming a powerful availability attack surface.