← All papers
First page of Tether: Verified Stateful Policy Engine for System-Level Monitoring of Agents

Tether: Verified Stateful Policy Engine for System-Level Monitoring of Agents

Meghana Aparna Sistla, Alaia Solko-Breslin, Somesh Jha, Aditya Kanade, Krishnamurthy Dj Dvijotham

cs.CR Nov 19, 2026 · v1 cs.AI
Implements a stateful security-policy DSL for agent monitoring as a Lean 4 EDSL that runs as the runtime monitor and proves policy metatheorems.
Autonomous AI agents are increasingly deployed for long-running tasks that execute arbitrary shell commands or programs. However, these actions can result in unauthorized network requests or persistent, malicious changes to the user's file system, processes, or privileges. Existing defense mechanisms rely on either LLM-based monitors, which lack provable safety guarantees, or stateless policy enforcement layers, which miss multi-step data flows and execution side-effects unmodeled by the policy language (e.g., network calls initiated inside a Python script). We introduce Tether, a framework for runtime enforcement of stateful security policies over the observed side-effects of an agent's actions. Tether executes each proposed action in an ephemeral, isolated sandbox, inferring abstract action semantics from observed system calls. Tether then enforces stateful policies over these inferred semantics, permitting actions to proceed only if they comply with the policy. Policies and action semantics are defined in an embedded DSL in Lean 4 capable of expressing diverse constraints, including information flow control (IFC), access control, and network security policies. Because actions can propagate labels from sources to destinations, a single rule can enforce fine-grained IFC policies across multi-step execution flows of arbitrary length. Expressing policies in Lean enables formal verification that they satisfy global security invariants (e.g., preventing network access after reading a sensitive file). We evaluate Tether on realistic coding-agent benchmarks across both benign and adversarial trajectories. With a single policy shared across all tasks, Tether blocks 100% of in-scope attacks while maintaining a benign false-positive rate under 5%.

Autonomous terminal agents can run arbitrary commands that exfiltrate data or make persistent malicious changes. Existing defenses are either LLM monitors without formal guarantees or stateless policy layers. Stateless layers miss multi-step information flows and side effects of commands whose effects cannot be predicted statically.

Tether runs each proposed command speculatively in an ephemeral sandbox (OverlayFS, a network proxy, paused background processes). It infers abstract actions from strace system-call traces and commits side effects only if a stateful policy allows them. Policies are written over a lattice-parametric action calculus that unifies access control and information flow control. They are implemented as an embedded DSL in Lean 4, which serves both as the executable reference monitor and as the specification for mechanized proofs. The proofs cover deny-overrides monotonicity, non-bypassability of required policies, permutation invariance, and state preservation under denial. Fuzzing over provenance DAGs checks that inferred action traces match ground-truth abstract traces.

On the MonitoringBench and LinuxArena coding-agent benchmarks, a single shared policy blocks 100% of in-scope attacks with a benign false-positive rate of 4.7%. LLM-based monitors miss some attacks on the same tasks. Red-teaming exposed gaps in the sandbox; after fixes, attack success rate fell to 0%.