Decentralized multi-agent LLM systems enable independently administered agents, each with its own operator, model, memory, and configuration, to collaborate on complex tasks without centralized coordination. Agents autonomously decompose tasks, execute subtasks and delegate remaining work to peers, enabling scalability and eliminating single points of failure. However, decentralization also introduces significant security challenges, as no single entity has complete visibility into task execution or the authority to enforce correct behavior across agents. In this paper, we systematize threats from malicious agents in decentralized multi-agent systems and propose mitigation techniques. We first design and evaluate attacks against integrity, availability, and confidentiality, demonstrating that a single malicious agent can cause up to 100% task failure, inflate token consumption and runtime by up to 7.7x and 3.2x, respectively, and exfiltrate up to 94% of relevant prior tasks from benign agents. We then present a cryptographic protocol that produces an irrefutable verified execution trace of every action taken in the system and develop an auditor that analyzes these traces to detect and attribute malicious behavior. Evaluations on HiddenBench using gpt-6.1-sol and Qwen3.8-27B-FP8 show that our protocol incurs negligible latency overhead, while the auditor detects and correctly attributes 98% of attacks, including those that comply with the protocol.
Figures & tables
Fig. 1 : Benign (a) and compromised (b) hop-by-hop decomposition and delegation.
Symbol
Definition
U
User.
Ai
Agent executing step i .
ID
Unique task identifier.
T
Verified execution trace.
Q
Task description.
Qc,Qr
Completed and remaining work.
TABLE I : Notation for the Verified Execution Trace.
Fig. 2 : Hop-by-hop system with our Verified Execution Trace protocol. Every message is appended with additional metadata, including the prior hash, and signed by the sender. Agents verifies incoming messages before proceeding ( Section IV-B ). The auditor, invoked by the user, verifies the hash chain and the semantic properties of the trace ( Section IV-C ).
gpt-6.1-sol
Qwen3.8-27B-FP8
Attack
Visited
ASR
Time
Tokens (in/out)
Hops
Visited
ASR
Time
Tokens (in/out)
Hops
I1
71%
100%
0.4 ×
0.3 × / 0.4 ×
0.7 ×
61%
100%
0.3 ×
0.3 × / 0.3 ×
0.6 ×
I2
73%
86%
0.6 ×
0.6 × / 0.6 ×
1.0 ×
58%
91%
0.5 ×
0.5 × / 0.5 ×
1.0 ×
I3
71%
46%
0.9 ×
0.9 × / 0.9 ×
1.2 ×
55%
86%
0.7 ×
0.5 × / 0.7 ×
1.0 ×
I4
69%
100%
0.7 ×
0.6 × / 0.6 ×
1.1 ×
50%
100%
0.8 ×
0.5 × / 0.6 ×
1.2 ×
I5
74%
43%
1.2 ×
0.9 × / 0.9 ×
1.6 ×
66%
56%
1.4 ×
0.9 × / 0.9 ×
1.9 ×
TABLE II : Integrity attacks. 20 tasks, 5 trials per task. All metrics are computed over runs the baseline run answered correctly ( gpt-6.1-sol : 91; Qwen3.8-27B-FP8 : 38). Time, tokens, and hops are averaged over runs where the attacker was visited relative to the clean-correct tasks ( BL row).
gpt-6.1-sol
Qwen3.8-27B-FP8
Attack
Visited
Accuracy
Time
Tokens (in/out)
Hops
Visited
Accuracy
Time
Tokens (in/out)
Hops
A1
63%
74%
2.7 ×
3.7 × / 2.4 ×
6.7 ×
42%
43%
2.3 ×
1.6 × / 1.5 ×
3.3 ×
A2
64%
82%
2.4 ×
3.5 × / 2.5 ×
12.3 ×
51%
28%
2.1 ×
2.3 × / 1.8 ×
9.8 ×
A3
69%
84%
1.3 ×
7.7 × / 0.9 ×
1.4 ×
52%
38%
1.4 ×
1.5 × / 0.9 ×
1.4 ×
A4
69%
79%
2.7 ×
5.8 × / 2.5 ×
12.3 ×
52%
37%
3.2 ×
4.1 × / 2.4 ×
8.6 ×
BL
–
91%
45.3
24440 / 1690
2.91
–
38%
197.1
20928 / 5786
1.89
TABLE III : Availability attacks. 20 tasks, 5 trials per task. Time, tokens, and hops are averaged over runs where the attacker was visited, relative to the clean run ( BL row).
gpt-6.1-sol
Qwen3.8-27B-FP8
Attack
Visited
Leakage
Accuracy
Time
Tokens (in/out)
Hops
Visited
Leakage
Accuracy
Time
Tokens (in/out)
Hops
C1
72%
94%
83%
1.1 ×
0.8 × / 1.2 ×
1.5 ×
51%
55%
36%
1.0 ×
0.7 × / 0.8 ×
1.3 ×
C2
68%
93%
90%
1.3 ×
1.1 × / 1.8 ×
2.2 ×
46%
55%
40%
1.3 ×
1.0 × / 1.2 ×
1.9 ×
C3
69%
66%
84%
1.2 ×
0.8 × / 0.8 ×
1.5 ×
50%
52%
32%
1.0 ×
0.8 × / 0.8 ×
1.4 ×
C4
67%
1%
87%
1.1 ×
0.8 × / 0.8 ×
1.4 ×
48%
33%
36%
1.1 ×
0.8 × / 0.8 ×
1.4 ×
BL
–
–
91%
45.3
24440 / 1690
2.91
–
–
38%
197.1
20928 / 5786
1.89
TABLE IV : Confidentiality attacks. 20 tasks, 5 trials per task. Leakage, time, tokens, and hops are averaged over runs where the attacker was visited, relative to the clean run ( BL row).
System Time (s)
Crypto (ms)
Model
Deleg.
Mem.
Exec.
Full
Sender
gpt-6.1-sol
26.7
0.312
22.2
1.681
1.059
Qwen3.8-27B-FP8
114.7
0.288
82.1
0.829
0.596
TABLE V: Per-task overhead under benign conditions. 20 tasks, 5 trials per task. Divided into system time and cryptographic cost under two independent verification modes. Note the unit change.
Attack
Recall
Precision
Audit Time
I1
100%
100%
3.09 s
I2
99%
99%
2.78 s
I3
83%
83%
5.12 s
I4
100%
50%
live
I5
100%
50%
live
A1
92%
92%
4.22 s
TABLE VI : Auditor Attribution. 20 tasks, 5 trials per task, ( gpt-6.1-sol ). live denotes attacks detected at execution time by full-trace verification rather than by the LLM auditor. † Average time only considers non-live times.
Who&When
Crafted
Crafted + AK
Attack
Recall
Time
Recall
Time
Recall
Time
I1
94%
2.64 s
100%
3.09 s
100%
3.07 s
I2
92%
2.91 s
99%
2.78 s
99%
2.78 s
I3
49%
5.31 s
83%
5.12 s
88%
5.26 s
A1
30%
4.12 s
92%
4.22 s
92%
3.83 s
A2
94%
3.99 s
100%
2.74 s
100%
2.96 s
TABLE VII : Blame attribution across auditor settings. 20 tasks, 5 trials per task, gpt-6.1-sol .
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Fig. 3 : The Who&When baseline auditor prompt [ 62 ] , lightly adapted for our setting. {trace} is replaced with the structured trace, without added metrics.
Fig. 4 : The Crafted auditor prompt used in Section VI-D . {trace} is replaced with the structured trace described in Section IV-C .
Fig. 5 : The Crafted + Attack Knowledge auditor prompt. Extends the Crafted prompt with brief descriptions of each of the thirteen attacks defined in Section III . {trace} is replaced with the structured trace from Section IV-C .
Multi-agent systems (MAS) comprise AI agents that collaborate or compete to perform complex, distributed tasks. Their dynamic interactions create opportunities for threat actors to target and impersonate other agents, intercept messages, inject malicious prompts, and exfiltrate sensitive data while simultaneously complicating the detection of anomalous behavior through conventional monitoring. This paper surveys threats and cryptographic challenges in agent-to-agent communication and presents a zero-trust architecture integrating identity, transport security, message integrity, and monitoring. The architecture establishes agent identities via decentralized identifiers and task-scoped verifiable credentials backed by a permissioned ledger, enforcing least-privilege authorization. For transport security, it provides mutually authenticated, crypto-agile TLS with hybrid post-quantum key establishment, and evaluates KEMTLS with pre-distributed public keys to reduce handshake overhead. Signed CBOR envelopes preserve payload integrity across multi-hop exchanges, while zero-knowledge proofs verify declared task constraints without exposing underlying inputs. Context-aware monitoring of inter-agent messages, tool activity, and execution telemetry informs the setting of risk-based trust thresholds and supports the detection of behavioral anomalies. Together, these mechanisms provide an integrated framework for securing and auditing agent communication, with implications for other agentic protocols and prospective 6G semantic communication.
Karol Budzyn, Adrian Brodzik, Mateusz Szczepkowski
Multi-agent systems solve complex tasks by decomposing them into subtasks, delegating the subtasks to agents, and aggregating the agents' responses using an aggregation rule. Malicious agents can manipulate the final solution by providing malicious responses to their assigned subtasks. In this paper, we first propose response manipulation attacks (ReMA), which iteratively optimize malicious responses to maximize attack effectiveness. Specifically, we formulate untargeted and targeted attacks as optimization problems and develop an approach to approximately solve these problems by iteratively refining malicious responses based on feedback from a surrogate multi-agent system. To defend against such attacks, we further propose SecMAS, a secure aggregation rule that leverages the semantic similarities among agent responses to select the response that is most consistent with a sufficiently large subset of the other responses. We theoretically establish security guarantees for SecMAS against both untargeted and targeted attacks. Extensive evaluations demonstrate that existing aggregation rules are vulnerable to ReMA, whereas SecMAS effectively defends against all evaluated attacks, including adaptive variants of ReMA, while maintaining utility comparable to that of existing aggregation rules.
Multi-agent LLM systems can be attacked by a payload that no single agent ever holds in full: a poisoned tool hides encrypted fragments in its observations, spreads them across several agents, and an external step reassembles and executes them after the run. Per-step safety checks that judge each action in isolation may fail to recognize the complete distributed payload. We investigate how early such an attack can be detected while the run is still unfolding, and how robustly it can be caught once its most obvious cues are stripped away. We build a working instance on a hierarchical multi-agent system, run it under benign and attacked conditions across five language models and two task domains, and record when each fragment is injected and when the payload is assembled and executed. Detection is a race against assembly. Before the first fragment is injected, attacked and benign runs are indistinguishable; once injection begins, a prefix detector flags 99.3% of successful attacks with a median of five steps remaining and a 10.3% safe-run false-positive rate. Because assembly occurs only after the run, these alarms arrive in time to abort nearly every successful attack. We then measure how much of that warning rests on removable surface cues of the attack rather than on its distributed structure. Generic zero-shot and behavior-trained detectors provide almost no warning at all; the detectors that do work lean in part on removable surface cues, chiefly the ciphertext's length and entropy, and once the entropy cue is removed from the payload and the length features from the detector, detection arrives later and transfers poorly across domains, though a fine-tuned model recovers some of the loss.
Diego Fernandez Arias, Dev Prashant Mistry, Ren Wang +1
Illinois Institute of Technology Chicago, Illinois, USA