September 24, 2026
Talk, ESORICS, European Symposium on Research in Computer Security, Rome, Italy
While Graph Neural Network (GNN)-based Network Intrusion Detection Systems (NIDS) excel by encoding relational traffic struc- tures, this structural dependency introduces novel adversarial vulner- abilities. Existing graph attacks remain impractical, often demanding white-box access, prohibitive query budgets, or exploit-breaking payload manipulations. To overcome these limitations, we propose a practical, hard-label black-box attack that evades detection strictly by injecting valid supplementary traffic flows, perfectly preserving the exploit’s func- tional integrity. By formulating this combinatorial challenge as a weakly submodular maximization problem, we leverage a local surrogate GNN and an influence-guided greedy search to efficiently identify highly impactful injections. We theoretically prove this approach yields a strict polynomial-time approximation guarantee. Empirically, we demonstrate the proposed flow injection attack can bypass state-of-the-art GNN-based NIDS with minimal query budgets