💻 computer science

Runtime Compliance Verification for AI Agents

This paper introduces C-Trace, a runtime verification framework that enforces GDPR compliance for AI agents by expressing regulatory requirements as formal predicates, monitoring execution traces to block non-compliant actions, and demonstrating high effectiveness in mitigating attack-induced violations across multiple case studies.

Original authors: Nafiseh Kahani, Masoud Barati, Diana Addae

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nafiseh Kahani, Masoud Barati, Diana Addae

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you hire a highly intelligent, chatty personal assistant to help you manage your life. This assistant can make phone calls, send emails, look up your bank details, and even delete your records. However, because this assistant is powered by an AI, it doesn't always "know" the rules of privacy. It might accidentally tell a stranger your address, or send you marketing emails when you never said "yes" to that.

This paper introduces a system called C-Trace (Compliance Trace-based Runtime Agent Conformance Enforcement). Think of C-Trace not as a new assistant, but as a strict, super-vigilant security guard standing right next to the AI assistant, watching every single word it says and every action it takes in real-time.

Here is how the system works, broken down into simple concepts:

1. The Problem: The "Forgetful" Assistant

Current ways of testing these AI assistants are like giving them a pop quiz before they start working. You ask, "Will you follow the rules?" and they say "Yes." But once they are actually working, talking to real people, they might forget those rules.

The Issue: An AI might be compliant in one conversation but break the rules in the next, depending on what the user asks.
The Gap: Existing safety tools are like bouncers who only check your ID at the door (static checks). They don't know if you already promised to leave the party earlier in the night. They miss the context of the whole conversation.

2. The Solution: The "Security Guard" (C-Trace)

C-Trace sits between the AI and the outside world. It watches the entire conversation as it happens (the "trace"). It doesn't just look at one sentence; it remembers the whole story.

It enforces four main "Privacy Laws" (based on GDPR) by acting as a filter:

The "Consent" Check (P1): Before the AI can do something like send a marketing email, the guard checks: "Did the user explicitly say 'Yes' to this earlier?" If the user just said, "I guess I don't mind," but never clicked a formal "Yes," the guard stops the action.
The "Purpose" Check (P2): The AI is hired for a specific job, like fixing a broken order. If the user asks the AI to use that order data to build a profile for a different company, the guard says, "No, that's a different job. You weren't hired for that."
The "Minimal Data" Check (P3): If the AI needs to check an order, it only needs the order number and email. If the AI tries to grab the user's date of birth or government ID just to check an order, the guard says, "That's too much information. You only need the basics."
The "Erasure" Check (P4): If a user says, "Delete my data," the guard marks that user as "deleted." If the AI tries to talk about that user again later, the guard slams the door: "This person doesn't exist in our system anymore. You can't mention them."

3. How They Tested It: The "Red Team" Game

To see if this security guard actually works, the researchers played a game of "Cat and Mouse."

The Attackers: They used a special program (DSPy) to generate hundreds of tricky, confusing, or aggressive conversations designed to trick the AI into breaking the rules. They also used real-world "jailbreak" prompts from other security tests.
The Test: They let the AI try to handle these tricky conversations with and without the security guard.
The Result: Without the guard, the AI broke the rules constantly (sometimes 100% of the time). With the C-Trace guard, the AI was stopped almost every time. Even when the guard had to "guess" what data was in a sentence (because it's hard to read human language perfectly), it still caught the vast majority of violations.

4. The "Three-Headed" Verification

To make sure the guard wasn't just making things up, the researchers built the same rulebook in three different languages (Python code, a policy language called Rego, and a logic language called MFOTL).

The Analogy: Imagine three different judges reading the same script. If they all agree on who is guilty, you know the verdict is solid. In this paper, all three "judges" agreed perfectly on every single test case.

5. The Bottom Line

The paper claims that C-Trace works.

It stops the AI from breaking privacy rules in real-time.
It doesn't slow the AI down significantly (it adds a tiny fraction of a second to the process).
It creates a permanent "audit log" (a written record) of every decision the guard made, so humans can review it later.

In short: If you have an AI assistant that handles sensitive data, C-Trace is the system that ensures it doesn't accidentally spill your secrets, sell your data to the wrong people, or ignore your request to be forgotten, by watching every move it makes and stopping it the moment it tries to break the rules.

Technical Summary: Runtime Compliance Verification for AI Agents

Problem Statement

AI agents increasingly handle personal data through tool use, function calls, and multi-turn dialogue. Unlike traditional APIs, agents dynamically decide which tools to call, what arguments to pass, and what to disclose in natural language. These runtime decisions can trigger obligations under the General Data Protection Regulation (GDPR), such as processing personal data without consent or disclosing data after an erasure request.

Current testing practices fail to address this dynamic risk:

Offline Red-Teaming: Tests models with curated prompts but does not enforce rules at runtime or observe the session state of deployed agents.
Guardrail Libraries: Match patterns in individual inputs/outputs but lack session history, failing to track whether consent was granted earlier in a dialogue or if a purpose was declared.

Consequently, an agent deployment can be compliant in one dialogue and non-compliant in another without any code or model weight changes. This creates a need for runtime verification over the agent's event trace, paired with an in-process attack driver to test the monitor with hostile inputs.

Methodology: C-Trace Framework

The authors propose C-Trace (Compliance Trace-based Runtime Agent Conformance Enforcement), a framework that treats GDPR compliance as a runtime property of an event stream rather than a property of a single message.

1. Event Model and Extraction

The framework instruments the agent loop to convert natural-language runs into a typed event trace ( $\tau = e_1 \dots e_n$ ). Events include UserMsg, AsstMsg, ToolCall, ToolRet, Consent, and Erasure.

Annotation: An extractor annotates each event with data categories ( $C(e)$ ) and purposes ( $\Pi(e)$ ).
Policy: A session policy defines declared purposes, tool-to-purpose bindings, and per-purpose data whitelists (necessary data categories).

2. Formal Predicates

Four GDPR principles are encoded as first-order predicates over the growing trace. These predicates are monotone: once a violation occurs, it cannot be "fixed" by subsequent events.

P1 (Consent): Processing data requires a prior Consent event for that specific purpose (unless a Legitimate Interest basis applies).
P2 (Purpose Limitation): Every purpose attached to an event must be declared in the policy.
P3 (Data Minimization): Data categories in a tool call must be necessary for at least one of the call's declared purposes.
P4 (Right to Erasure): After an Erasure event for a subject, no subsequent event may disclose that subject's identifier.

3. Runtime Monitor and Attack Driver

Interceptor: Placed between the agent loop and tool APIs, it evaluates predicates incrementally. Decisions include forward, redact (removing non-necessary data), or block (rejecting the event).
Attack Driver: Generates adversarial dialogues targeting each predicate using:
- DSPy-generated prompts: Variants of seed requests using role-play, urgency, and jailbreak framing.
- Real-corpus prompts: Verbatim prompts from red-teaming corpora (HarmBench, AdvBench, DAN).
Oracle: A separate, observable oracle determines attack success by checking the accepted trace against the policy, independent of the monitor's internal predicates.

4. Cross-Validation

To ensure the operational monitor matches the formal specification, the same policy logic is implemented in three runtimes:

Python: Operational enforcement.
Rego/OPA: Auditor-facing policy.
MFOTL (MonPoly): Formal temporal logic specifications.
The authors verify that all three agree event-by-event on every trace.

Evaluation and Results

The framework was evaluated on four GDPR-reframed case studies: Shopper (retail), Airline (travel), MedAgent (healthcare), and FinAssist (banking/KYC).

Key Metrics

Attack Success Rate (ASR): The percentage of attacks that successfully bypass the monitor.
False Positive Rate (FPR): The percentage of benign requests incorrectly blocked.
Realization Rate: How often the model attempts the violation in the absence of a monitor.

Findings

Vulnerability of Unmonitored Agents: Without a monitor, agents commit violations across all four families. Consent bypass (A1) and over-collection (A3) are frequently triggered (up to 100% ASR in some cases).
Baseline Limitations:
- Regex/Presidio (Stateless): These baselines fail to detect violations dependent on session history (Consent, Purpose Limitation, Erasure). While Presidio reduces over-collection, it cannot stop consent bypass or post-erasure recall.
- Random Baseline: High false positives (72–88%) with no targeted protection.
C-Trace Performance:
- Perfect Extraction: Achieves 0% ASR and 0% FPR across all case studies and attack registers (generated and real-corpus).
- Noisy Extraction: Under 10% per-category extractor noise (simulating drop-out and over-typing):
  - ASR remains $\le$ 12% (significantly lower than baselines).
  - FPR remains $\le$ 16%.
- Ablation: Removing individual predicates restores specific attack families (e.g., removing P1 restores consent bypass), confirming each predicate is necessary.
Overhead: The monitor adds a negligible median latency of 1.8 $\mu$ s per event.

Significance and Claims

The paper claims to be the first work to apply runtime verification of GDPR obligations to the natural-language execution traces of AI agents.

Novelty: Unlike stateless guardrails, C-Trace reasons over the session trace, enabling it to catch violations that depend on earlier events (e.g., prior consent or erasure).
Practicality: The framework operates as an in-process interceptor without requiring changes to the underlying model or tool implementations. It produces append-only JSONL audit logs suitable for compliance review.
Reliability: The results indicate that the monitor's reliability is heavily dependent on the accuracy of the category extractor. While the policy logic is robust, missed categories due to extraction errors are the primary failure mode.
Scope: The approach focuses on four core GDPR principles (Consent, Purpose Limitation, Data Minimization, Right to Erasure) applicable across multiple domains (retail, healthcare, finance) and lawful bases (consent, legal obligation).

The authors conclude that trace-based monitoring is a practical enforcement layer for AI agents, provided that the underlying event extraction is high-quality and fail-closed mechanisms are considered for ambiguous data categories.