💻 computer science

Maris: A Formally Verifiable Privacy Policy Enforcement Paradigm for Multi-Agent Collaboration Systems

This paper introduces Maris, a formally verifiable privacy enforcement paradigm that embeds reference monitors into multi-agent collaboration frameworks like AutoGen and LangChain to effectively mitigate sensitive data leakage while maintaining high task success rates.

Original authors: Jian Cui, Zichuan Li, Luyi Xing, Xiaojing Liao

Published 2026-03-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jian Cui, Zichuan Li, Luyi Xing, Xiaojing Liao

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 a bustling, high-tech office where a team of specialized AI robots (called Multi-Agent Collaboration Systems, or MACS) works together to solve complex problems. One robot is great at math, another at writing, and a third at talking to customers. They pass notes back and forth, share data, and use external tools like a giant brain (LLM) to get the job done.

The Problem:
While this teamwork is efficient, it's a privacy nightmare. Because these robots talk so freely, sensitive information (like a patient's phone number or a company's secret supply chain data) can accidentally leak to the wrong robot, or even to a hacker pretending to be a robot. Current safety measures are like having a bouncer who guesses who looks suspicious; they often miss the bad guys or stop the good guys from doing their jobs.

The Solution: Maris
The authors of this paper built Maris, a new "Privacy Police" system for these AI teams. Think of Maris not as a bouncer, but as a smart, unbreakable rulebook that sits between every conversation and action.

Here is how Maris works, using simple analogies:

1. The "Strict Mailroom" (Structured Actions)

In a normal AI office, robots might send notes written in messy, free-form English. It's hard to know exactly what's in them.

Maris's Fix: Maris forces every robot to fill out a digital form (like a standardized shipping label) before sending a message. They can't just write a paragraph; they must check boxes for "Name," "Phone Number," and "Task ID."
Why it helps: Because the forms are strict, Maris can instantly scan them. If a robot tries to put a "Phone Number" in a box meant for "Task ID," Maris catches it immediately.

2. The "Time-Traveling Judge" (Formal Verification)

Privacy rules aren't just about what data is shared, but when and how.

The Rule: "You can only send a text to a patient if you looked up their info in the last hour."
Maris's Fix: Maris uses a special math language (called MFOTL) that acts like a time-traveling judge. It doesn't just guess; it proves mathematically that the rule was followed.
The Metaphor: Imagine a security guard who doesn't just ask, "Did you get permission?" but actually checks a timestamped log to prove the permission was signed within the last 60 minutes. If the log is missing, the guard stops the action instantly.

3. The "Smart Redaction Pen" (Field-Level Control)

Sometimes, a robot needs to send a message, but only part of it.

The Scenario: A robot needs to send a patient's medical history to a doctor, but the "Supervisor" robot listening in shouldn't see the patient's phone number.
Maris's Fix: Maris acts like a magic redaction pen. It lets the message pass through, but it automatically blacks out (masks) the phone number for the Supervisor, while leaving it clear for the Doctor. It's like sending a letter where the envelope is transparent to the right person but opaque to everyone else.

4. The "Seamless Suit" (Non-Intrusive)

Usually, adding security to software is like trying to add a seatbelt to a car that's already driving down the highway—you have to stop the car and rebuild the chassis.

Maris's Fix: Maris is designed like a seamless suit that fits over the existing AI frameworks (like AG2 and LangGraph). Developers don't have to rewrite their code or stop their systems. They just "put on the suit," and the privacy protection kicks in automatically without slowing things down too much.

The Results: Did it work?

The researchers tested Maris in three real-world scenarios:

A Hospital System: Preventing patient phone numbers from leaking to the wrong staff members.
A Supply Chain System: Ensuring a company doesn't share supplier data without explicit permission.
A Travel Agent: Making sure flight and hotel agents don't swap unnecessary personal data.

The Outcome:

Zero Leaks: Maris stopped 100% of the privacy violations, even when hackers tried to trick the robots (proactive attacks) or when robots were just careless (passive leaks).
No Broken Jobs: The robots still finished their tasks successfully.
Tiny Speed Hit: The system got slightly slower (about 5% slower), which is a small price to pay for total privacy security.

In a Nutshell

Maris is a tool that turns the chaotic, free-flowing chat of AI robots into a structured, rule-abiding conversation. It uses math to prove that privacy rules are being followed, automatically hides sensitive data when it shouldn't be seen, and does all of this without breaking the AI systems we already use. It's the difference between a chaotic free-for-all and a secure, well-organized office where everyone knows exactly what they are allowed to say and when.

1. Problem Statement

Multi-Agent Collaboration Systems (MACS), powered by Large Language Models (LLMs), are increasingly used to solve complex tasks by distributing responsibilities among specialized agents. However, these systems face critical privacy challenges:

Data Leakage Risks: Inherent information exchange between agents and interactions with external entities (LLM providers, tools, users) create vectors for sensitive data leakage.
Lack of Formal Guarantees: Existing safeguards often rely on heuristic-based or LLM-powered detection mechanisms that lack provable correctness. They cannot guarantee compliance with complex, temporal privacy regulations like the GDPR (e.g., data minimization, purpose limitation, consent validity over time).
Deployment Friction: Current solutions often require invasive modifications to the application logic of existing MACS frameworks, making them difficult to integrate and scale.
Threat Model: The system must defend against both insider threats (compromised agents within the MACS) and external threats (malicious tools, users, or prompt injection attacks) that attempt to exfiltrate data or bypass privacy constraints.

2. Methodology: The Maris Framework

Maris is a privacy policy enforcement paradigm designed to be integrated at the development framework level (specifically demonstrated on AG2 and LangGraph). It ensures non-disruptive deployment while providing formal verification guarantees.

Core Architecture

Maris operates through two primary phases: Static Action Specification and Runtime Policy Enforcement.

A. Agent Action Specifications (Static Phase)

Structured Communication: Unlike standard MACS that use unstructured natural language, Maris forces agents to operate within a pre-defined, schema-based action space.
Automatic Generation: An Agent Action Generator (LLM-assisted) automatically analyzes system prompts and task descriptions to generate:
- YAML Configuration: Defines typed message schemas (e.g., send_info) and tool parameters.
- Signature Files (.sig): Translates these schemas into typed predicates compatible with formal logic.
Validation: Agents are prompted to output structured JSON. A format checker validates that actions match the schema before execution, preventing prompt injection attacks that rely on malformed inputs.

B. Runtime Policy Enforcement

Policy Language (MFOTL): Maris uses Metric First-Order Temporal Logic (MFOTL) to express privacy policies. This allows for:
- Fine-grained Control: Blocking specific data fields (e.g., masking phone numbers).
- Temporal Constraints: Enforcing time-bound rules (e.g., "Data must be queried within the last 3600 seconds before sending an outreach message").
- Contextual Logic: Expressing dependencies like "Action A implies Action B occurred within time $T$ ."
Enforcement Components:
1. Reference Monitor: Intercepts agent actions (inter-agent messages and tool calls) before execution.
2. Event Parser: Converts intercepted actions into MFOTL-formatted predicates with timestamps.
3. Policy Enforcer: Uses the MonPoly runtime verification engine to check the proposed action against the deployed MFOTL policies.
Actions: Based on the verification result, the system can Block (reject action), Mask (redact specific fields), or Warn (log and allow).

3. Key Contributions

Formally Verifiable Framework: Maris is the first framework to provide provable guarantees for privacy compliance in MACS using MFOTL, moving beyond heuristic detection.
Non-Intrusive Integration: It is designed to be embedded directly into popular open-source frameworks (AG2, LangGraph, A2A) without altering the original application logic, enabling rapid adoption.
Expressive Policy Support: It supports complex GDPR-compliant policies, including data minimization, purpose limitation, and time-sensitive consent requirements.
Autonomous Evaluation Framework: The authors developed a comprehensive evaluation suite that emulates realistic threat scenarios (passive eavesdropping, active prompt injection, and temporal violations) to test Maris's effectiveness.

4. Evaluation Results

The authors evaluated Maris across three real-world task suites: HospitalGPT (healthcare outreach), OptiGuide (supply chain optimization), and Travel Agent (booking system).

Privacy Compliance (Policy Violation Rate - PVR):
- Without Maris, PVR was high (ranging from 75% to 100%) due to uncontrolled data sharing and lack of temporal checks.
- With Maris, PVR dropped to 0% in all scenarios, including both passive (eavesdropping) and proactive (prompt injection) attack modes.
Task Utility (Task Success Rate - TSR):
- Maris maintained a 100% Task Success Rate for tasks where the policy did not inherently block the task (e.g., legitimate data sharing).
- In cases where a policy violation would have occurred (e.g., sending data without consent), the task was correctly blocked, preventing the violation.
Performance Overhead:
- Maris introduced an average end-to-end delay of 4.87% (approx. 1.13 seconds per query).
- The majority of overhead (approx. 800ms) came from the Policy Checking (MonPoly verification), while schema validation and parsing were negligible (<1ms).
- Overhead varied by task complexity: OptiGuide (1.1%), HospitalGPT (5.0%), and TravelAgent (9.1%).

5. Significance

Regulatory Compliance: Maris provides a concrete technical solution for adhering to strict regulations like the GDPR, which require not just data protection but also verifiable proof of compliance (e.g., proving consent was obtained within a specific timeframe).
Scalability and Adoption: By integrating at the framework level rather than the application level, Maris lowers the barrier to entry for developers, allowing them to secure complex multi-agent systems without rewriting core logic.
Security Paradigm Shift: It shifts the security model from "detect and react" (heuristic/LLM-based) to "verify and enforce" (formal logic), ensuring that privacy violations are mathematically impossible to execute within the system's constraints.
Open Science: The authors have released the code, datasets, and evaluation framework, fostering reproducibility and further research in secure multi-agent systems.

In conclusion, Maris demonstrates that it is possible to build highly expressive, formally verifiable privacy controls into multi-agent systems with minimal performance cost, effectively mitigating data leakage risks while preserving system functionality.