PaperlayerView exact revision on arXiv

Source-linked AI summary

SAGA: A Security Architecture for Governing AI Agentic Systems

Georgios Syros, Anshuman Suri, Jacob Ginesin, Cristina Nita-Rotaru, Alina Oprea

arXiv:2504.21034v2cs.CRcs.AIcs.LG

TL;DR

Existing agent-management approaches do not combine discovery, secure communication, and remote access control with user oversight, while many proposed governance designs lack implementation and evaluation. SAGA uses a Provider-mediated registry and cryptographic access-control tokens; formal verification and Provider evaluations report security properties and scalable operation. The paper presents this as a concrete protocol architecture for secure inter-agent communication and user-governed management.

  • Problem

    Agent-management systems must address discovery, secure communication, and remote access control, while existing approaches do not cover all three and agent-specific A2A lacks security guarantees and access control.

    Source: B. Requirements and Challenges for… · p. 3

  • Method

    SAGA registers users and agents with a Provider that maintains metadata and policies, and uses cryptographic tokens derived from one-time keys to enforce user-defined access control.

    Source: §I · pp. 1–2

  • Results

    PROVERIF automatically proves token secrecy and agent–Provider and agent–agent authentication; RAFT adds negligible Provider throughput degradation, while sharding yields linear throughput increases.

    Source: §I · p. 2

  • Takeaways & Limitations

    SAGA provides a concrete protocol specification and reference implementation with formal security guarantees for user-governed inter-agent communication.

    Source: §VIII · p. 14

Abstract

from arXiv · show

Large Language Model (LLM)-based agents increasingly interact, collaborate, and delegate tasks to one another autonomously with minimal human interaction. Industry guidelines for agentic system governance emphasize the need for users to maintain comprehensive control over their agents, mitigating potential damage from malicious agents. Several proposed agentic system designs address agent identity, authorization, and delegation, but remain purely theoretical, without concrete implementation and evaluation. Most importantly, they do not provide user-controlled agent management. To address this gap, we propose SAGA, a scalable Security Architecture for Governing Agentic systems, that offers user oversight over their agents' lifecycle. In our design, users register their agents with a central entity, the Provider, that maintains agent contact information, user-defined access control policies, and helps agents enforce these policies on inter-agent communication. We introduce a cryptographic mechanism for deriving access control tokens, that offers fine-grained control over an agent's interaction with other agents, providing formal security guarantees. We evaluate SAGA on several agentic tasks, using agents in different geolocations, and multiple on-device and cloud LLMs, demonstrating minimal performance overhead with no impact on underlying task utility in a wide range of conditions. Our architecture enables secure and trustworthy deployment of autonomous agents, accelerating the responsible adoption of this technology in sensitive environments.

I. INTRODUCTION

Autonomous LLM agents create security challenges as they interact with tools, external resources, and one another, while existing designs leave user-controlled management unresolved. SAGA combines user oversight and policy-enforced communication with formal verification and evaluation across agentic tasks and deployment settings.

I. INTRODUCTION

  • Existing agent-governance designs address identity, attribution, authorization, or delegation but largely lack implementation, evaluation, and user-controlled agent management.A2A supports verifiable identifiers and encrypted communication but lacks policy enforcement and runtime mediation, and does not mitigate adversarial agents.Source: §I · p. 1
  • SAGA registers users and agents with a Provider that stores metadata and user-defined access policies, then uses cryptographic access-control tokens to enforce those policies.Agents derive tokens from one-time keys; subsequent inter-agent communication proceeds over TLS without Provider mediation.Source: §I · pp. 1–2, Figure 1 · p. 2
  • PROVERIF automatically proves SAGA token secrecy and authentication of agent–Provider and agent–agent communication against an attacker controlling network messages.The attacker may observe, intercept, modify, replay, reorder, and synthesize messages.Source: §I · p. 2
  • The evaluation spans meeting scheduling, expense reports, and collaborative writing with on-device and cloud LLMs and agents in diverse geolocations.The paper uses these settings to evaluate the scalability of its design.Source: §I · p. 2
  • RAFT-based Provider fault tolerance introduces negligible throughput degradation, while sharding produces linear throughput increases.The paper reports these results for key Provider operations.Source: §I · p. 2

B. Requirements and Challenges for Secure Agentic Systems

  • Agent-management systems must support discovery, secure communication, and remote access control while keeping discovery and access control under user control.The passage contrasts these needs with messaging, transport-security, and access-control systems that do not address all three together.Source: B. Requirements and Challenges for… · p. 3

C. Problem Statement

SAGA aims to combine agent discovery, secure communication, and fine-grained access control while leaving management of agent lifecycles to users. Its Provider-mediated setup uses user policies and cryptographic tokens, while agents communicate directly after establishing contact.

C. Problem Statement

  • SAGA targets agent discovery, secure communication, and fine-grained access control while preserving user control over agent management.The design goal also includes control of an agent’s lifecycle, contacts, and deactivation according to user preferences and policies.Source: C. Problem Statement · p. 3

A. System Goals

  • The system is designed to preserve task-completion utility, support different agent implementations and LLMs, and scale with minimal performance overhead.Other stated goals include user-managed lifecycles, policy-controlled access, limited trust, and limiting compromised agents’ vulnerability windows.Source: A. System Goals · p. 3

B. Architecture Overview

  • A centralized Provider maintains user and agent identities, authenticates entities, and facilitates controlled communication establishment.The Provider maintains user and agent registries, including agent metadata, credentials, endpoint information, and communication policies.Source: B. Architecture Overview · p. 4
  • Users specify an Access Contact Policy for each agent; the Provider distributes one-time keys for initial access, while subsequent communication proceeds directly over TLS.Users can deactivate their own agents, and the Provider does not mediate ongoing inter-agent communication.Source: B. Architecture Overview · p. 4
  • Receiving agents issue encrypted access-control tokens with expiration times and request limits, reusing them until a limit is reached or they expire.The token is encrypted under a shared key derived for an initiating–receiving agent pair; a new token follows retrieval of another one-time key from the Provider.Source: B. Architecture Overview · p. 4
  • Token lifetime and the number of registered one-time keys let users tune the trade-off between access-control granularity, vulnerability windows, and performance overhead.Access control is asymmetric: policies govern which initiating agents may contact a receiving agent.Source: B. Architecture Overview · p. 4

C. System Assumptions

SAGA’s stated security guarantees depend on assumptions about trusted user authentication, secure registries and cryptography, TLS-protected channels, and network protections. Its threat model includes malicious or compromised agents and network attackers, while the protocol specification covers cryptographic primitives and user-led agent registration.

C. System Assumptions

  • The system assumes robust user authentication and human verification, no compromised credentials, globally routable public IP addresses, secure cryptographic primitives, TLS-protected communication, and basic network defenses against flooding.Agent registration is assumed to be restricted to authenticated human users through a trusted external identity service.Source: C. System Assumptions · p. 5

D. Threat Model

  • The threat model includes malicious registered agents, compromised legitimate agents, unregistered self-replicating children, shared credentials, Sybil identities, and network attackers.The Provider follows protocol logic but may observe metadata and traffic patterns; registries are assumed secure against adversarial control or tampering.Source: D. Threat Model · p. 5

IV. SAGA PROTOCOL SPECIFICATION

  • The protocol specification covers user registration, agent registration, agent management, and inter-agent communication after introducing its cryptographic primitives.These procedures are organized as separate protocol components.Source: §IV · p. 5

A. Cryptographic Primitives and Notation

  • The specification uses signatures, collision-resistant hashes, Diffie–Hellman key exchange, and HKDF with SHA-256.Diffie–Hellman derives a shared secret from one party’s secret key and the other party’s public key.Source: A. Cryptographic Primitives and Notation · p. 5

C. Agent Registration by User

  • During agent registration, the user selects an identifier and endpoint details, generates TLS and access-control keys, and registers contact-policy information with the Provider.Registration binds the agent cryptographically to its user and device; the user generates a batch of one-time key pairs for access control.Source: C. Agent Registration by User · p. 6

A, SOTK1

Agent registration binds user-generated agent credentials and metadata to an identity and Provider, then stores verified agent information and returns confirmation to the user.

A, SOTK1

  • Users generate a batch of one-time key pairs for access control and sign each public one-time key.They also sign the agent’s device and networking information and long-term keys.Source: A, SOTK1 · p. 6, A, SOTKN · p. 6

A, ..., OTKN

  • The Provider checks that the agent ID and endpoint descriptor are globally unique and verifies the agent certificate and signatures.After verification, it stores agent metadata, contact policy, signatures, and the associated user identity.Source: A, ..., SOTKN · p. 7

A, ..., SOTKN

  • The Provider signs the agent information and returns it as confirmation; the user stores that signature for initiating agent communication.Successful registration enables the agent to communicate within the ecosystem.Source: A, ..., SOTKN · p. 7

D. Agent Management

SAGA’s agent management combines user-defined contact policies with one-time-key quotas and user-managed policy and key updates. The Provider applies these controls during agent contact and OTK provisioning.

1) Agent Contact Policy:

  • Contact policies use identifier-pattern rules and choose the most-specific matching rule to set the initiating agent’s OTK budget.A policy with no matching rule is distinguished from an expired OTK budget.Source: 1) Agent Contact Policy · p. 7

2) One-Time Key Generation:

  • The Provider checks policy eligibility, initializes a per-agent-pair OTK counter from the applicable budget, and decrements it when issuing a key.The receiving agent’s user uploads OTKs, and only one OTK is issued per request to limit the compromise vulnerability window.Source: 2) One-Time Key Generation · p. 7
  • OTK retrieval can fail when the recipient’s overall OTK pool is exhausted or the initiator’s policy quota is depleted.The recipient’s user can update the policy and refresh OTKs.Source: 2) One-Time Key Generation · p. 7
  • Users can update contact policies to add or remove rules, block specific agents, or deactivate their own agents, but cannot deactivate another user’s agent.A blocking rule assigns a budget of −1; deactivation disables incoming contact.Source: 2) One-Time Key Generation · pp. 7–8
  • Users manage agent TLS and access-control key rotation, while the Provider follows user-authentication and password-management best practices.The paper points to key-management guidance and Provider authentication guidance.Source: 2) One-Time Key Generation · p. 8

E. Inter-Agent Communication

SAGA’s communication protocol combines Provider-mediated contact authorization and OTK distribution with a shared key and a recipient-issued access-control token. The token is checked by the receiving agent and can be reused within its validity and request limits.

E. Inter-Agent Communication

  • The recipient encrypts a task-scoped token under the shared key, with an expiration time and request limit.The token includes a nonce, issue and expiration timestamps, maximum request count, and the initiator’s access-control key.Source: E. Inter-Agent Communication · p. 8
  • The Provider checks the recipient’s contact policy and OTK quota before returning recipient metadata and a signed OTK to the initiating agent.The Provider decrements the initiator-recipient OTK counter after retrieval.Source: E. Inter-Agent Communication · p. 8
  • The agents verify certificates and use the OTK in a Diffie–Hellman exchange to derive a shared key for the access-control token.The initiating agent sends its information and Provider signature with the OTK when requesting a token.Source: E. Inter-Agent Communication · p. 8
  • For each request, the recipient verifies that the token is for the initiator, unexpired, and within its usage quota before discarding it after task completion.Both parties discard the token when the task is deemed complete.Source: E. Inter-Agent Communication · p. 8
  • A valid token can be reused without contacting the Provider until expiration or quota exhaustion, trading fewer Provider contacts against greater exposure if an agent is compromised.A larger request limit reduces Provider-contact overhead but increases potential exposure.Source: E. Inter-Agent Communication · p. 8

F. Formal Protocol Analysis

SAGA’s formal model verifies token secrecy and communication authentication against a symbolic network attacker. The paper also describes Provider resilience and scalability extensions and an integration that adds policy-governed security to A2A.

F. Formal Protocol Analysis

  • PROVERIF proves token secrecy and authentication of agent–Provider and agent–agent communications against an attacker that can observe, intercept, modify, replay, reorder, and synthesize network messages.The modeled attacker corresponds to the Dolev–Yao symbolic cryptographic protocol model.Source: F. Formal Protocol Analysis · pp. 8–9

A. Provider Architecture Design

  • The base architecture trusts the Provider, while a PBFT service can tolerate f compromised servers among 3f + 1 servers.A lighter alternative combines RAFT or Paxos with proactive auditing to detect compromises.Source: A. Provider Architecture Design · p. 9
  • A RAFT or Paxos Provider cluster can replicate the registry and tolerate failures; rate limiters are proposed as a first line of DoS defense.A typical five-server cluster can tolerate two faulty servers; rate limiters work best with additional protective measures against sophisticated distributed attacks.Source: A. Provider Architecture Design · p. 9
  • Sharding the agent registry by agent ID, with RAFT clusters and load balancers for sharders, is proposed to increase scalability.The paper points to scalability results in Section VI-D.Source: A. Provider Architecture Design · p. 9
  • Federated Providers can authenticate agents across organizations while each organization retains control of its local registry and policies.Providers establish trust through shared cryptographic keys or certificates and validate local agents in cross-boundary interactions.Source: A. Provider Architecture Design · p. 9

B. Integration with the A2A Protocol

  • SAGA’s A2A integration protects agent cards with user-specified access policies and user signatures, addressing A2A’s stated lack of authentication, access control, and governance.The Provider stores cards as part of agent metadata; only authorized agents may retrieve them.Source: B. Integration with the A2A Protocol · p. 9
  • Before a message reaches the A2A layer, SAGA verifies token authenticity, freshness, and contact authorization, discarding requests that fail a check.A2A request metadata includes task and message IDs and content type.Source: B. Integration with the A2A Protocol · pp. 9–10
  • The integration uses minimal changes, preserves A2A functionality, and remains agnostic to agent design and task semantics.It adds user-policy-controlled security to interoperable agent communication.Source: B. Integration with the A2A Protocol · p. 10

VI. EVALUATION

SAGA is implemented as an HTTPS Provider coordinating mutually authenticated TLS communication, and the framework supports different LLM-agent implementations. The evaluation measures cryptographic and protocol overhead, including effects of token generation, token lifetime, request reuse, and geography.

A. Implementation

  • The Provider uses HTTPS, while inter-agent communication uses mutually authenticated TLS; the framework is agnostic to the underlying LLM-agent implementation.Experiments include a local Qwen-2.5 72B model and two cloud-hosted OpenAI models.Source: A. Implementation · p. 10

B. Overhead Evaluation

  • Core cryptographic operations take several milliseconds, and the measured overheads are small compared with task execution times, which typically last at least a few minutes.The evaluation also measures fault-tolerance and scalability costs and evaluates SAGA on three agentic tasks.Source: B. Overhead Evaluation · p. 10, §VI · p. 10
  • Under 10 seconds of user computation and at most 0.5 seconds of Provider cost support generating 1000 OTKs every 5 minutes over 8 hours.Access-control and identity key pairs each take 0.11 milliseconds to generate on commodity hardware.Source: B. Overhead Evaluation · p. 10, Figure 2 · p. 10
  • Just below 400 seconds per day suffices to derive 144K access-control tokens for one agent, even with a 1-minute token lifetime.The reported process includes a Diffie–Hellman handshake and token encryption and validation.Source: B. Overhead Evaluation · p. 10, Figure 3 · p. 11
  • Longer token lifetimes reduce Provider reliance but extend the time compromised agents can operate uninterrupted; shorter lifetimes add cryptographic overhead.OTKs are rotated frequently, access-control keys typically weekly or biweekly, and identity keys commonly every 30 to 90 days.Source: B. Overhead Evaluation · p. 10
  • Under 25 ms of protocol overhead is reported when agents interact for at least 4–5 requests, with overhead decreasing as token quota increases.The reported overhead is low across Provider locations, and is even lower when the initiating agent is geographically close to the Provider.Source: Figure 5 · p. 11, B. Overhead Evaluation · p. 11, Figure 4 · p. 11

C. Task Completion

SAGA’s task evaluations report successful completion with low protocol overhead, while Provider measurements examine replication, sharding, capacity, and longer OTK key-chains. The related work contrasts SAGA with unevaluated governance designs and other approaches to secure agent interaction.

C. Task Completion

  • All three agent tasks completed, and protocol overhead stayed below 0.6% of the fastest calendar task’s end-to-end cost, even across distant locations.The evaluated tasks were meeting scheduling, expense-report submission, and collaborative writing.Source: C. Task Completion · pp. 11–12

D. Fault Tolerance and Scalability

  • RAFT replication reduced OTK-request throughput by 12–15% versus one node; OTK refresh fell from 173K to 153K requests per minute with three nodes.Agent registration remained largely stable under five-node replication, at 511K requests per minute regardless of OTKs provisioned per agent.Source: D. Fault Tolerance and Scalability · p. 12, Figure 6 · p. 13
  • With 10 sharders and 24-hour tokens, the Provider can support up to 300 million agents.Each agent contacts the Provider once per token lifetime to obtain an OTK.Source: D. Fault Tolerance and Scalability · p. 12
  • With 10 sharders, agent registration using 1000 OTKs still exceeds 40K requests per minute; registration outperforms refresh because it appends rather than updates registry entries.Longer key-chains reduce throughput as payloads grow and more registry state must be written; pre-provisioning large batches supports resilience under intermittent connectivity.Source: D. Fault Tolerance and Scalability · pp. 12–13
  • Adding 10 sharders increases OTK throughput nearly tenfold, reaching 178K to 511K requests per minute depending on the operation.Throughput scales linearly with added sharders; Figure 6 is among the cited visuals for these results.Source: D. Fault Tolerance and Scalability · p. 12, Figure 6 · p. 13

VII. RELATED WORK

  • Prior governance designs –[12] remain unevaluated; agent-development libraries such as LangChain, AutoGen, and smolagents do not address governance.SAGA is compatible with agent development frameworks, including smolagents.Source: §VII · p. 13
  • SAGA uses one-time-key pre-distribution like Signal and Matrix; users who distrust the identity service must verify identity keys off-band.The Provider can be made resilient to compromise.Source: §VII · p. 13

VIII. CONCLUSION

  • SAGA’s Provider-mediated architecture enforces user policies and is presented as a concrete protocol specification with formal security guarantees and a reference implementation, unlike prior conceptual designs –[12].The conclusion says SAGA is compatible with A2A and the Model Context Protocol.Source: §VIII · p. 14

APPENDIX

The appendix points to protocol diagrams and cryptographic overhead results, then details the agent tasks, tools, and cryptographic primitives used in the implementation.

A. Protocol Figures

B. More Cryptographic Overhead Results

C. Agent-Interaction Task Details

  • The agents use smolagents CodeAgent to write and execute Python, with role-specific prompts for initiating and receiving agents.Email and calendar tools implement end-to-end actions that update recipients’ inboxes or calendars.Source: C. Agent-Interaction Task Details · p. 15
  • Calendar agents inspect availability, negotiate a time, and create an event; success requires a correct, conflict-free future invite in both calendars.The task uses GPT-4.1-mini.Source: C. Agent-Interaction Task Details · p. 16
  • For expense reports, agents search separate inboxes, exchange relevant entries, and submit a combined report; checks include totals and participant membership.The supplied success criteria also require that no extraneous users appear in the report.Source: C. Agent-Interaction Task Details · p. 16
  • Two agents with law and machine-learning expertise collaborate through multiple revision rounds to produce and save a unified blog post.The task uses Qwen2.5-72B-Instruct; each task runs in a fresh agent instance without shared prior context.Source: C. Agent-Interaction Task Details · pp. 16–17
  • Listing 2 models Diffie-Hellman, signing, symmetric encryption, hashing, and key derivation primitives for PROVERIF.The listing includes equations for Diffie-Hellman, signature checking, and symmetric decryption.Source: C. Agent-Interaction Task Details · p. 18

D. Verification Details

The verification models use PROVERIF’s symbolic Dolev–Yao setting to check authentication, secrecy, and reachability properties of SAGA’s registration and communication protocols.

D. Verification Details

  • PROVERIF models attackers as able to observe, intercept, replay, and synthesize network messages, and models SAGA’s registration and communication handshakes.The modeled cryptographic primitives include Diffie-Hellman, signing, symmetric encryption, hashing, and key derivation.Source: D. Verification Details · p. 18
  • The models check whether an attacker can obtain the token and use authentication events to verify that received content was sent in the same form.Queries cover agent-provider authentication, provider-agent authentication, and inter-agent communication; reachability is checked by querying whether specified events occur.Source: D. Verification Details · p. 18
  • The PROVERIF models and test environment are open source and reproducible with a nix flake; verification took about 10 minutes on a 6th-generation i7 laptop with 16 GB RAM.Source: D. Verification Details · p. 18

E. Attacker Evaluation

The evaluation implements eight adversarial agents targeting authentication, secrecy, and access control, and tests where protocol checks reject or constrain their actions.

E. Attacker Evaluation

  • Missing TLS credentials stop the handshake; callers without an OTK or access token are terminated, and expired or overused tokens cause immediate closure.The TLS failure occurs before application-layer interaction; invalid tokens are rejected after receipt.Source: E. Attacker Evaluation · pp. 18–19
  • Table IV organizes attack models by required adversarial capabilities and protocol detection step; eight adversaries target authentication, secrecy, and access control.The evaluation assumes attackers cannot compromise TLS, break standard cryptographic primitives, or bypass human verification during registration.Source: E. Attacker Evaluation · p. 18, Table IV · p. 19
  • Impersonating A with its Provider-issued signature and public information fails receiving-agent signature verification.The receiving agent verifies the signature using the impersonator’s information.Source: E. Attacker Evaluation · p. 19
  • A valid token issued to another agent is rejected when its intended-recipient identity mismatches the initiating agent’s identity.The connection is immediately aborted.Source: E. Attacker Evaluation · p. 19
  • The Provider denies contacts disallowed by policy, while human verification during user registration blocks attempts to register replicated or variant identities.The registration requirement is enforced through integration with trusted identity services.Source: E. Attacker Evaluation · p. 19
  • A valid token can open a short-lived vulnerability window, bounded by its expiration and communication quota; the user may blocklist the agent to prevent new OTKs.Further requests are rejected after either token limit is reached.Source: E. Attacker Evaluation · p. 19

F. Additional Fault Tolerance & Scalability Results

Fault-tolerance and scaling experiments report high registration and OTK-refresh throughput, while AWS measurements support capacity up to 260 million agents under the tested deployment conditions.

F. Additional Fault Tolerance & Scalability Results

  • Over 40K registrations per minute are achieved with 1000 OTKs and 10 sharders, with marginal RAFT-replication impact across configurations.Throughput decreases as key-chain length increases because of larger payloads and additional registry writes.Source: F. Additional Fault Tolerance &… · p. 19, Figure 10 · p. 20

G. Experiments on Amazon Web Services

  • The AWS Provider deployment used a single proxy and up to 7 US-East sharders, each running 5-node RAFT replication.The proxy routed requests to the appropriate sharder to balance workload across the cluster.Source: G. Experiments on Amazon Web Services · p. 20

F. Additional Fault Tolerance & Scalability Results

G. Experiments on Amazon Web Services

  • 260 million agents are supported with 7 sharders and a 24-hour token lifetime in the AWS capacity experiment.The AWS deployment was limited to 7 sharders versus 10 in the earlier analysis; same-region placement did not guarantee a shared physical datacenter, adding network latency.Source: Figure 12 · p. 20, G. Experiments on Amazon Web Services · p. 21

Related papers

Loading 2504.21034v2…