SAGA: A Security Architecture for Governing AI Agentic Systems

📝 Paper Summary

Agent security and governance Multi-agent systems

SAGA is a security architecture that enables users to govern their AI agents through a centralized registry for discovery and policy management, combined with decentralized, cryptographically secured inter-agent communication.

Core Problem

Current agentic systems lack concrete implementations for user-controlled agent management, leaving users without oversight mechanisms to prevent malicious agents from impersonating or exploiting their agents.

Why it matters:

Malicious actors can impersonate agents or manipulate behavior to extract sensitive information if identity and communication aren't secured.
Existing proposals are largely theoretical or lack fine-grained policy enforcement (like Google's A2A), failing to meet emerging safety requirements for critical applications.
Users currently cannot effectively limit who their autonomous agents interact with or for how long, expanding the attack surface.

Concrete Example: Alice's calendar agent might need to contact Bob's agent to schedule a meeting. Without SAGA, a malicious agent could impersonate Bob's agent to harvest schedule data, or flood Alice's agent with requests. SAGA ensures Alice's agent only communicates with authenticated agents under specific user-defined policies (e.g., 'allow 5 requests from Bob').

Key Novelty

User-Governed Agent Lifecycle with Cryptographic Access Tokens

Introduces a 'Provider' entity that manages agent identities and policies but does not mediate actual communication, preserving scalability.
Uses a cryptographic mechanism where receiving agents issue 'Access Control Tokens' to authorized initiators; these tokens are encrypted under dynamically derived shared keys.
Tokens enforce fine-grained constraints (expiration time, request limits) defined by the user's policy, balancing security windows with performance.

Architecture

Overview of the SAGA architecture showing the Provider, User Registry, Agent Registry, and the flow of registration and communication between User, Provider, and Agents.

Evaluation Highlights

Formal verification using PROVERIF proves secrecy of tokens and authentication of communication against network attackers.
Making the Provider fault-tolerant using RAFT consensus introduces negligible throughput degradation across key operations.
Provider throughput scales linearly with sharding, demonstrating the architecture can handle large-scale agent deployments.

Breakthrough Assessment

8/10

Provides a complete, implemented, and formally verified security architecture for agentic systems, addressing a critical gap in governance that previous theoretical works missed.

⚙️ Technical Details

Problem Definition

Setting: A distributed system of autonomous LLM agents owned by users, communicating over public networks

Inputs: User-defined Access Contact Policies (ACP) and agent registration metadata

Outputs: Secure, policy-compliant communication channels between agents via Access Control Tokens

Pipeline Flow

User Registration (User registers with Provider)
Agent Registration (User registers agent + keys + policy with Provider)
Discovery (Initiating Agent queries Provider for Target Agent)
Key Exchange (Initiator gets OTK from Provider; derives shared key with Target)
Token Issuance (Target validates request, issues Access Control Token)
Direct Communication (Agents communicate p2p using Token + TLS)

System Modules

Provider Service

Central registry for identities and policies; issues OTKs to authorized initiators

Model or implementation: Distributed system (Go implementation)

Agent (Initiator) (Agent Operation)

Requests access to other agents to fulfill tasks

Model or implementation: LLM-based agent (e.g., Llama-3-8B-Instruct)

Agent (Receiver) (Agent Operation)

Enforces access control policies on incoming requests

Model or implementation: LLM-based agent

Novel Architectural Elements

Hybrid centralized-decentralized control: Centralized policy/identity management (Provider) decoupled from decentralized runtime enforcement (Agents via Tokens).
Cryptographic Access Control Token mechanism: Binds permissions to specific agent pairs via ephemeral keys derived from long-term identity keys.

Modeling

Base Model: Llama-3-8B-Instruct (used for agent logic in evaluation)

Compute: Not reported in the paper

Comparison to Prior Work

vs. Google A2A: SAGA adds centralized policy enforcement and user-controlled management; A2A lacks runtime mediation and mitigation against adversarial agents.
vs. Signal/Matrix: SAGA adds fine-grained access control policies specifically for autonomous agents; messaging apps lack these agent-specific governance layers.
vs. Kerberos: SAGA supports secure communication establishment (discovery + key exchange) suitable for autonomous agents over public networks, whereas Kerberos focuses primarily on authentication in trusted networks.
+ 1 more
vs. OIDC (OpenID Connect) [not cited in paper]: OIDC handles user identity; SAGA extends identity and governance to autonomous agents acting on behalf of users.

Limitations

Provider is a central point of failure (mitigated by RAFT/sharding but still architecturally central).
Relies on users to define effective policies; poor user configurations could weaken security.
Does not prevent compromised agents from acting maliciously within the bounds of their valid tokens (insider threat).

Reproducibility

Code: https://github.com/gsiros/saga

Publicly available code at https://github.com/gsiros/saga. The paper includes formal proofs in PROVERIF. Evaluation uses Llama-3-8B-Instruct and GPT-4o (cloud).

📊 Experiments & Results

Evaluation Setup

Performance evaluation of the Provider architecture and end-to-end agent task latency

Benchmarks:

Agentic Tasks (Scheduling meetings, expense reports, collaborative writing) [New]

Metrics:

Throughput (requests/sec)
Latency (ms)
Token overhead
Statistical methodology: Not explicitly reported in the paper

Key Results

Benchmark	Metric	Baseline	This Paper	Δ
Evaluation of Provider scalability and fault tolerance mechanisms.
Provider Throughput	Throughput scalability	Not reported in the paper	Linear increase	Linear increase
Provider Latency	Overhead	Not reported in the paper	Negligible degradation	Negligible degradation

Main Takeaways

The architecture incurs minimal performance overhead on agent tasks compared to unsecured baselines.
The Provider can scale linearly with sharding, making it suitable for large deployments.
Fault tolerance (RAFT) can be added with negligible performance cost.
Formal verification confirms the design guarantees secrecy and authentication.

📚 Prerequisite Knowledge

Prerequisites

Public Key Infrastructure (PKI) and TLS
Diffie-Hellman key exchange
Basic understanding of distributed systems (RAFT consensus)
Formal verification concepts (PROVERIF)

Key Terms

Provider: A centralized service in SAGA that maintains user/agent registries and enforces initial access policies but does not relay messages.

OTK: One-Time Key—a public cryptographic key registered by an agent, used by others to initiate secure contact and derive shared secrets.

Access Control Token: A cryptographically signed and encrypted token issued by a receiving agent to an initiating agent, granting permission to communicate for a limited time/count.

Access Contact Policy: A user-defined set of rules specifying which agents can contact their agent and under what constraints (e.g., rate limits).

PROVERIF: A software tool for automatically analyzing the security properties of cryptographic protocols.

RAFT: A consensus algorithm used to manage a replicated log, ensuring fault tolerance in distributed systems.

Sybil attack: An attack where a single adversary creates multiple fake identities (agents) to gain disproportionate influence or subvert trust.