MESA: Prioritizing Vulnerable Communication Channels for Securing Multi-Agent Systems
For developers and operators of multi-agent systems, this work provides a proactive method to identify and defend against attacks on communication channels, addressing a poorly understood attack surface.
This paper addresses how to prioritize limited security resources to protect vulnerable inter-agent communication channels in multi-agent systems. The proposed framework, Mesa, ranks edges by security-criticality using graph metrics and dynamic probes, achieving a mean Spearman correlation of +0.60 with empirical attack success rates and intercepting about 3x more successful attacks when monitoring the top 10% of edges compared to random allocation.
Multi-agent systems (MAS) are increasingly used to automate complex, distributed workflows. However, their inter-agent communication channels introduce new attack surfaces that remain poorly understood and are difficult to defend against. In this paper, we address how defenders should prioritize limited security effort to protect vulnerable communication channels before attacks are observed. This is motivated by our observation that the channel-level attack impact is highly non-uniform: a single compromised edge can account for up to 75% of total attack success. We introduce Mesa, a label-free framework for proactively ranking which MAS edges are most security-critical -- that is, most likely to affect the system's decision if compromised. Mesa combines six graph-theoretic metrics and two dynamic probes (ablation and masking) without requiring attack traces. We evaluate Mesa against a dynamic misinformation attack pipeline across three diverse MAS scenarios, eight network topologies, and five open-source LLMs from Qwen, Llama, and Gemma families. Mesa rankings correlate strongly with empirical per-edge attack success rate, achieving mean Spearman $ρ=+0.60$ (peaking at $+0.73$). In resource-constrained defense deployment, monitoring the top 10% of Mesa-ranked edges intercepts about 3x the successful attacks as random allocation. We further test Mesa under varying attacker and defender models and LangGraph workflows and characterize its limits under adaptive attacks and high-redundancy graphs. Overall, our results show that edge-level risk in MAS is often concentrated and predictable, allowing proactive hardening of multi-agent infrastructures.