acceptodds
Under review as a conference paper at ICLR 2027

Compositional Permission Flow Verification for Multi-Agent LLM Systems with Adaptive Security Consolidation

Abstract

Multi-agent systems built on large language models share tools, messages, and delegated authority in ways that create security risks invisible under per-agent analysis. Privilege escalation across agents, confused-deputy misuse, and transitive exfiltration arise from interaction structure rather than from any single prompt or tool call. We present ProMeTheUSE, a framework that formalizes Security Contracts for agents, builds a Permission Dependency Graph (PDG) with algebraic flow operators, and verifies three properties, namely least privilege, data confidentiality, and delegation integrity. A polynomial-time analyzer detects six compositional vulnerability classes and synthesizes minimal repairs. Across large-scale evaluation on nearly 10,000 samples spanning a synthetic corpus, public-template PDG encodings, and a held-out transfer set, the sound verifier recovers injected structural witnesses when the full graph is visible and stays in the mid-90s F1 under contract and edge degradation. A distilled Adaptive Security Consolidation (ASC) student remains competitive under partial observability while nearest-centroid and feature baselines fall behind. The analyzer scales to 50 agents in under 50 ms. ASC adds hierarchical security memory, runtime motif monitoring, and verification-gated contract updates. Generative Adversarial Verification expands the threat taxonomy beyond the initial six classes.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
multi-agent systems, large language models, LLM agents, agent security, permission flow, compositional verification, least privilege, data confidentiality, delegation integrity, adaptive security, formal methods, tool-using agents

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_eBi3OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents ProMeTheUSE, a framework for checking permission violations in multi-agent LLM systems. The authors encodes agents, tools, resources, and delegation relationships as a graph, which then uses permission propagation, reachability checks, and cycle detection to flag security risks such as privilege and data-leakage problems. The authors also propose greedy edge removals to repair violations and add runtime pattern monitoring, verification-gated updates, and a neural classifier for more efficient/faster detection. The evaluation includes about 3,700 synthetic configurations, >1,300 graphs encoded from public agent-framework templates (mostly w/ injected violations, though).

The technical contribution seems rather limited to me. Much of the framework appears to combine existing graph-based security checks with relatively simple monitoring and classification techniques bolded up with complex naming which also lowers readability by a lot. I also don't think the experiments establish how useful the system would be for securing actual multi-agent applications.

Critical strengths
  • The authors use explicit permission checks rather than relying entirely on LLM-based detection. And the underlying graph checks are relatively easy to reason about and/or interpret.

  • There is a decent amount of evaluation across multiple graph corpora. The paper also reports per-class detection results (fig. 7 mainly), robustness to incomplete graphs, as well as verification latency.

Critical weaknesses
  • I don't see much novelty in the core method. Permission closure, graph reachability, SCC-based cycle detection, and greedy edge removal are well-established techniques. The memory and classifier components also seem fairly straightforward to me. It is unclear what new algorithmic insight the combination provides.

  • The evaluation mainly relies on injected violations (why do the authors think these are representative of real-world violations?) in constructed graphs, and assumes accurate permission graphs and contracts to begin with. It is unclear how realistic these assumptions are for actual multi-agent systems, where agent behavior and information flows may not match the specifications. I don't see much evidence that the approach would work reliably in such settings.

  • I am not convinced by the baselines. The classifier is mainly compared against a nearest-centroid model, which tells us relatively little about advantages over existing graph-policy analyzers.

  • The paper formulates minimum-cost mitigation but then apparently uses a greedy edge-removal procedure. No optimality argument and not much analysis of how these approaches affect useful functionality.

  • The figures are so low quality and cluttered and do not seem polished at all for a publication-ready manuscript.

Questions for authors
  • What can the proposed verifier detect that established graph-based permission or access-control analyses cannot? Is there a concrete example that requires the full framework?

  • How would permission graphs and contracts be obtained and validated in deployed multi-agent systems to begin with?? (including cases with undeclared interactions or changing tool behaviors or even where MCP remote tools are integrated into the system)

  • Could you evaluate actual attack scenarios on running agents and compare with stronger graph-analysis baselines?

  • What guarantees, if any, does the greedy repair procedure provide?

Reviewer_ztBCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Agents with limited individual permissions can gain unintended capabilities through delegation, communication, and shared resources. ProMeTheUSE models these interactions using security contracts and a Permission Dependency Graph. It checks least privilege, confidentiality, and delegation integrity, then proposes repairs by removing edges.

Critical strengths

The paper addresses an important problem across agent boundaries. Permission paths can reveal risks that individual tool restrictions miss. Graph witnesses and proposed repairs could help developers understand and fix these risks.

The separation between learned monitoring and formal checks is interesting.

Formal checks are a useful design principle.

Critical weaknesses

The main guarantees do not follow from the stated conditions. Theorem 1’s permission-set conditions do not rule out delegation cycles. Two agents with empty permissions, requirements, provisions, and invariants can satisfy those conditions while delegating to each other, violating P3. Theorem 3 also claims that shrinking provision sets preserves the earlier conditions. However, shrinking a parent’s provision set can break a child’s requirement inclusion. These problems affect the verification gate at the center of the adaptive system.

The evaluation does not establish the claimed transfer and repair quality. Runtime traces are also simulated. In addition, the paper claims minimum-cost repairs, but Algorithm 2 is greedy and has no demonstrated optimality guarantee. Small repairs on injected examples do not establish minimum cost or preservation of legitimate tasks.

Questions for authors

What additional conditions guarantee acyclicity, bounded delegation depth, and confidentiality across non-delegation edges?

Does consolidation recheck affected requirement–provision relationships?

Can you test independently extracted configurations and compare greedy repairs with exact solutions on small graphs?

Reviewer_QmgYOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a static checker for permission problems in multi-agent LLM systems. The idea is that each agent can look safe on its own, but once agents are wired together, delegation can give an agent access it was never supposed to have. Authors define 6 vulnerability types and present detection protocol.

Critical strengths

The paper studies an important topic of agentic security and privacy.

Critical weaknesses

It is extremely hard to understand the paper and its purpose. The main advantage of AI Agents is that they produce dynamic control flows that depend on data. The proposed theorems assume static rules that are not derived from data.

If anything deriving static rules is the biggest challenge for AI agents: tasks are often ambiguous and under-specified.

The paper uses a lot of jargon that is not common for ML: "traces are ephemeral, motifs are semi-stable" which make it harder to understand and read.

Evaluation looks quite weak given the ambitious goals and again it is not clear what values are important and not, i.e. why Figure 5 measures verification time?

Questions for authors

Addressing writing and core message of the paper will significantly strengthen the manuscript.

Comments on the paper

1 comment
Area_Chair_95iuOpenReview ↗

Last 24 hours of the reviewer discussion period

Dear Authors and Reviewers

Just a reminder we are soon to be entering the last 24 hours of the reviewer discussion period.

Authors: If you have not yet responded to the reviews and intend to please do so ASAP. Please note reviewers will most likely not have time to respond to any late rebuttal comments so please make sure any comments are clear and not in need of further clarification.

Reviewers: If the authors have responded to your reviews and you have not yet responded please do so, even if it is a one line response acknowledging you have read the rebuttal.

Thanks for all your time, and I hope you all learnt something interesting during the process.

Kind regards,

Your ICLR Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.