Multi-Instance Adversarial Attack on GNN-Based Malicious Domain Detection

Multi-Instance Adversarial Attack on GNN-Based Malicious Domain Detection

Speakers: Mahmoud Nazzal, New Jersey Institute of Technology; Issa Khalil, Hamad Bin Khalifa University; Abdallah Khreishah, New Jersey Institute of Technology; NhatHai Phan, New Jersey Institute of Technology; Yao Ma, New Jersey Institute of Technology

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=ynXtvb8DCAI

Overview

This talk, presented by Mahmoud Nazzal, delves into a critical vulnerability within Graph Neural Networks (GNNs) when applied to security-critical tasks, specifically Malicious Domain Detection (MDD). The research introduces a novel multi-instance adversarial attack named MAA, designed to evade the detection of multiple malicious domains simultaneously. This work, a collaboration between the New Jersey Institute of Technology and QC at Hammed bin Khalifa University, highlights how even state-of-the-art GNN-based MDD systems are susceptible to practical, stealthy, and black-box adversarial manipulations.

The core of the presentation addresses the inherent fragility of GNNs in cybersecurity applications, despite their impressive performance in other domains. Malicious Domain Detection is a vital defense mechanism, often relying on complex graph structures derived from DNS and enterprise logs. By demonstrating a sophisticated attack that can collectively bypass these advanced detection systems, the research underscores a significant security gap. This vulnerability has profound implications for how organizations protect against phishing, malware distribution, and other cyber threats that leverage compromised or malicious domains.

The importance of this research stems from the increasing adoption of GNNs in security. As these models become more prevalent for identifying patterns of malicious activity, understanding and mitigating their adversarial weaknesses becomes paramount. MAA not only exposes these vulnerabilities but also provides a framework for developing more robust and resilient GNN-based security solutions, pushing the boundaries of adversarial machine learning in the context of real-world cybersecurity challenges.

Background

▶ Watch: GNNs in security critical applications vulnerable to attacks (0:00)

Graph Neural Networks (GNNs) represent a powerful class of machine learning models capable of extending deep learning to structured data. By effectively combining information from individual entities (nodes) with their relational context (edges), GNNs have achieved state-of-the-art performance across a diverse range of applications, from traffic analytics and social network analysis to drug discovery. However, a significant challenge arises when GNNs are deployed in security-critical applications. Like many other deep learning and machine learning models, GNNs are inherently susceptible to adversarial attacks, which can manifest at various granularities, including node, graph, edge, or multi-instance levels.

The specific application under scrutiny in this research is Malicious Domain Detection (MDD). MDD is the process of identifying internet domains associated with cyberattacks, such as phishing, malware command-and-control, or spam. This process typically leverages publicly available data, primarily DNS logs, and often incorporates enterprise-level data to construct a Domain Maliciousness Graph (DMG). At its essence, MDD operates on a "guilt by association" principle, inferring the maliciousness of unknown domains from their connections to known malicious or benign entities within the graph. A DMG might include nodes representing domains, IP addresses, and clients, interconnected by various edge types reflecting DNS queries, IP resolutions, or other network interactions. Once constructed, a GNN model is trained on this DMG to classify domains as malicious or benign, and then used during inference to make real-time decisions. GNNs have recently emerged as a highly promising and effective framework for conducting MDD due to their ability to naturally model the relational data inherent in DNS and network traffic.

Despite their efficacy, existing adversarial attacks on GNNs have proven insufficient when applied to the specific context of GNN-based MDD, particularly in multi-instance scenarios. Prior approaches, often focusing on perturbing individual nodes or edges, exhibit "low evasiveness" and "low effectiveness" when the adversary aims to protect multiple domains. As the number of adversary-controlled domains increases, the effectiveness of these single-instance attacks diminishes significantly, making them impractical for coordinated campaigns. This limitation motivated the presented work: to develop a multi-instance adversarial attack capable of collectively and stealthily evading detection for a group of malicious domains, without requiring extensive knowledge of the target defense system.

Key Findings

▶ Watch: New multi-instance black-box attack and its features (3:19)

The research presented by Mahmoud Nazzal and his team introduces several key findings and contributions that significantly advance the understanding of GNN vulnerabilities in cybersecurity:

Firstly, the core contribution is the proposal of MAA (Multi-Instance Adversarial Attack), a novel adversarial technique specifically designed for GNN-based MDD. Unlike prior attacks, MAA operates at the subgraph level and is tailored to evade the detection of multiple adversary-controlled domains simultaneously. This marks a departure from single-instance attacks, which are shown to be inadequate for such coordinated evasion.

Secondly, MAA is characterized by its stealthy and practical nature, operating as a black-box attack. Crucially, the adversary is not assumed to have prior knowledge of the entire Domain Maliciousness Graph (DMG) or the specific architecture and parameters of the target GNN model. Instead, the adversary is only required to know the nodes within its own subgraph and commonly used edge types, making the attack highly realistic and applicable in real-world scenarios where defenders' models are typically opaque.

Thirdly, the research provides both theoretical and empirical establishments of the insufficiency of existing adversarial attacks on GNNs for the purpose of MDD. Experiments demonstrate that repeatedly applying single-instance attacks to multiple adversary nodes leads to a diminishing attack effectiveness as the number of targeted domains grows. This finding underscores the necessity for a multi-instance approach like MAA, which is designed for collective evasion.

Fourthly, the effectiveness of MAA was rigorously validated through experiments with real-world data. The target model used in these experiments was an HGNN (Heterogeneous Graph Neural Network), a state-of-the-art GNN-based MDD approach known for its high performance, utilization of both public and enterprise data, and its commercialized status. This choice of target model and dataset lends significant credibility to the practical implications of the attack.

Finally, MAA consistently demonstrated superior performance compared to existing baselines, including both node feature-focused and edge feature-focused adversarial attacks. In terms of Attack Success Rate (ASR), MAA achieved higher evasion rates for adversary domains, while maintaining a lower Negative Flip Rate (NFR), indicating minimal unintended impact on non-adversary nodes. This superior performance, coupled with the practical implementation methods (simple name edits and IP resolution changes in DNS records), highlights MAA as a potent and realistic threat to modern GNN-based malicious domain detection systems.

Technical Deep Dive

▶ Watch: Adversary's goals, knowledge, and capabilities defined (4:06)

The proposed Multi-Instance Adversarial Attack (MAA) on GNN-based MDD is meticulously designed, grounded in a clear threat model and a sophisticated optimization framework. The technical underpinnings detail how an adversary can strategically manipulate a subgraph to achieve collective evasion.

Threat Model Characterization:

The attack operates under a precisely defined threat model that outlines the adversary's goals, knowledge, and capabilities:

• Adversary's Goals: The primary objective of the adversary is to achieve stealthy evasion for multiple of its own controlled malicious domains. This means bypassing the GNN-based MDD system's detection for a set of adversary nodes, while simultaneously ensuring that these perturbations have a minimal, ideally negligible, impact on legitimate, non-adversary nodes in the broader graph. The aim is collective, salient bypass.
• Adversary's Knowledge: A crucial aspect of MAA's practicality is its black-box nature. The adversary is assumed to have limited knowledge. Specifically, it knows only the nodes (domains) within its own subgraph and assumes certain commonly used edge types (e.g., domain-IP, domain-client relationships). Critically, the adversary is not assumed to know the remaining subgraphs of the overall Domain Maliciousness Graph (DMG), nor does it possess knowledge of the target GNN model's architecture, parameters, or training data.
• Adversary's Capabilities: Within its estimated subgraph, the adversary is capable of manipulating specific features of its domains (e.g., domain name characteristics) and altering certain edge types or relationships (e.g., changing IP resolutions). These manipulations are designed to be practical and implementable in real-world DNS infrastructure.

Problem Formulation and Solution:

The adversarial attack problem in this multi-instance context is formulated as a two-objective optimization problem. This formulation aims to achieve two simultaneous goals:

1. For every adversary's domain node, the crafted perturbations should directly contribute to its individual bypass of the detection model.
2. The impact of these perturbations on neighboring adversary nodes should be positive and synergistic, actively contributing to their collective evasion. This ensures that the attack is not just a collection of individual attacks, but a coordinated effort.

The research derives a closed-form solution for the optimized perturbations at the adversary nodes. This solution is presented as a weighted sum of two components, each directly corresponding to one of the aforementioned attack objectives. This mathematical formulation ensures that the perturbations are optimized to maximize both individual and collective evasion while remaining within the adversary's practical manipulation capabilities.

The MAA Algorithm (d-m):

The practical implementation of the MAA algorithm, referred to as d-m in the presentation, involves several key steps to craft adversarial attacks on GNN-based MDD:

1. Surrogate Model Availability: Since the target GNN model is black-box, the adversary first needs a surrogate model. This is obtained by starting with a certain set of training data (a partial DMG), querying the black-box target model to acquire labels for a subset of nodes, and then using these labeled nodes to train a local GNN surrogate model. This surrogate model acts as a proxy for the target model, allowing the adversary to optimize perturbations without direct knowledge of the target.
2. Subgraph Estimation: The adversary constructs an estimate of its own subgraph. This involves understanding its own domains, associated IPs, and how they connect to other entities within its control or observation.
3. Perturbation Optimization: Utilizing the already trained surrogate model and the d-m algorithm, the adversary optimizes the specific perturbations to be applied to its nodes (domain features) and edges (relationships). This optimization leverages the closed-form solution derived from the two-objective problem.
4. Practical Implementation: The optimized perturbations are then implemented in a practical manner. For domain owners, this typically involves making changes that will reflect in public DNS logs. The speaker highlights two primary methods:

• Name Edits: Simple manipulations of domain names (e.g., adding or removing subdomains, altering characters).
• IP Resolution Changes: Modifying the IP addresses that a domain resolves to.

These changes are easily conducted by any domain owner and directly manipulate both the local features of domain nodes and the edges connecting entities within the DMG.

1. Defense Interaction: The defense entity continuously constructs its DMG from DNS logs. Crucially, the perturbations injected by the adversary, even without knowledge of the full DMG, will appear in these logs. When the defense entity's target GNN model processes this perturbed DMG, the optimized changes are designed to bypass the actual target model's detection mechanisms.

Experimental Setup and Metrics:

• Target Model: The effectiveness of MAA was evaluated against an HGNN (Heterogeneous Graph Neural Network) approach. This model is characterized as state-of-the-art in GNN-based MDD, leveraging both public and enterprise data, and has achieved commercialization, underscoring its real-world relevance.
• Dataset: The experiments utilized a real-world dataset of representative scale, combining publicly available DNS data with proprietary enterprise data. The DMG schema adopted was consistent with that proposed by the authors of the HGNN paper.
• Baselines: MAA's performance was compared against established adversarial attack baselines, including generic GNN attacks focused solely on node feature perturbations and those focused on edge feature perturbations.
• Metrics: Two primary metrics were employed to quantify attack success and impact:
• Attack Success Rate (ASR): This metric measures the ability of the attack to successfully bypass the MDD system's detection for adversary-controlled domains. A higher ASR indicates a more effective attack.
• Negative Flip Rate (NFR): This metric quantifies the "side effect" of the attack. While the presentation describes it as "negligibly small negative impact on other adversary nodes," in the context of adversarial attacks, NFR often refers to the rate at which benign nodes are misclassified as malicious due to the attack (collateral damage) or other unintended changes. A lower NFR is desirable, indicating a more stealthy attack with less unwanted disturbance to the graph's classification.

Experimental Results:

The experimental results conclusively demonstrated MAA's superiority:

• Feature Perturbation Alone: Even when only domain features were manipulated, MAA successfully evaded detection for the vast majority of adversary domains, while exhibiting a negligibly small negative impact on other nodes. Its effectiveness (ASR) generally increased as more adversary nodes were included in the attack.
• Combined Attack (Features + Edges): When both local features and edges across adversary nodes were simultaneously manipulated by MAA, the attack proved even more successful. This combined approach yielded higher ASR and lower NFR, indicating a more potent and controlled evasion strategy.
• Baseline Comparison: MAA significantly outperformed both the feature-centered and edge-centered baseline attacks across both ASR and NFR metrics. This validated the multi-instance, optimized approach of MAA over simpler, single-focus attacks. The research also highlighted MAA's scalability and reasonable cost, further emphasizing its practical feasibility.

Demo / Proof of Concept

▶ Watch: Two-objective optimization for adversarial attack formulation (6:18)

While the presentation did not include a live, interactive demonstration of the MAA attack in action, the "Experiments" section served as the empirical proof of concept. The researchers rigorously demonstrated the attack's feasibility and effectiveness by applying it to a real-world dataset and a state-of-the-art, commercialized HGNN-based malicious domain detection system. The quantitative results, particularly the high Attack Success Rate (ASR) and low Negative Flip Rate (NFR) achieved by MAA compared to existing baselines, unequivocally validated the attack's practical utility and significant threat. The provision of a QR code linking to the implementation and artifacts further confirms the practical nature of the research.

Defensive Implications

▶ Watch: Practical implementation of the DM attack algorithm (8:00)

The findings from the MAA research carry significant implications for defenders responsible for securing networks and leveraging GNN-based systems for threat detection. The demonstrated practicality and effectiveness of a multi-instance, black-box attack on state-of-the-art MDD systems necessitate a re-evaluation of current defense strategies and an urgent call for enhanced GNN robustness.

Firstly, increased awareness is paramount. Security teams must recognize that GNN-based MDD, despite its sophistication, is not immune to adversarial manipulation. The ability for an adversary to collectively evade detection for multiple malicious domains through simple DNS changes (name edits, IP resolution changes) means that even robust GNN models can be systematically bypassed.

Secondly, there is an urgent need for research into robust GNN architectures and adversarial training techniques. Current GNN models, as shown, are vulnerable. Defenders should push for and adopt GNN models that are specifically designed with adversarial robustness in mind. This includes exploring techniques like adversarial training, where models are exposed to perturbed data during their training phase to improve their resilience against such attacks.

Thirdly, enhanced monitoring and anomaly detection are crucial. Defenders should implement advanced monitoring of DNS logs and related network data, looking beyond individual domain characteristics for coordinated and subtle changes across multiple related domains. Detecting anomalies in graph structures or feature distributions within the Domain Maliciousness Graph (DMG) itself could signal an ongoing multi-instance attack. For instance, a sudden, coordinated shift in IP resolutions or domain name patterns across a cluster of related domains could be an indicator of MAA.

Fourthly, diversification of defense layers is essential. Relying solely on a single GNN-based MDD system is risky. Organizations should integrate GNN-based detection with other complementary security measures, such as traditional signature-based detection, behavioral analytics, threat intelligence feeds, and sandboxing. A multi-layered defense strategy can help catch what an adversarially manipulated GNN might miss.

Finally, continuous evaluation and red-teaming are critical. Defenders should regularly subject their GNN-based MDD systems to red-teaming exercises and adversarial robustness evaluations using techniques inspired by MAA. This proactive approach helps identify and mitigate vulnerabilities before they are exploited by real-world adversaries. Furthermore, exploring techniques to make domain features and graph structures more difficult for adversaries to manipulate without detection, or to introduce "tripwires" that flag suspicious coordinated changes, would be beneficial. The paper's insights should drive the development of more resilient, explainable, and trustworthy GNNs for critical security applications.

Key Takeaways

• GNN Vulnerability in Security: Graph Neural Networks, while powerful, are inherently vulnerable to practical adversarial attacks in security-critical applications like Malicious Domain Detection (MDD).
• Insufficiency of Prior Attacks: Existing single-instance adversarial attacks on GNNs are insufficient for multi-instance MDD scenarios, exhibiting diminishing effectiveness when targeting multiple domains simultaneously.
• MAA: A New Multi-Instance Threat: The proposed MAA (Multi-Instance Adversarial Attack) is a novel, stealthy, and black-box attack capable of collectively evading detection for multiple malicious domains.
• Practical Attack Vectors: MAA leverages practical manipulation techniques such as simple DNS name edits and IP resolution changes to perturb domain features and graph edges.
• Superior Performance: MAA significantly outperforms state-of-the-art feature-focused and edge-focused GNN attacks on real-world data and a commercialized HGNN-based MDD system, demonstrating high Attack Success Rate (ASR) with minimal Negative Flip Rate (NFR).
• Urgent Need for Robustness: This research highlights a critical security threat to GNN-based defenses, underscoring the urgent need for increased research and development into robust and resilient GNN architectures for cybersecurity applications.

About the Speaker(s)

The talk "Multi-Instance Adversarial Attack on GNN-Based Malicious Domain Detection" was presented by Mahmoud Nazzal. He is affiliated with the New Jersey Institute of Technology and QC at Hammed bin Khalifa University in Doha, Qatar, where this joint work was conducted. Mahmoud Nazzal's research, along with his co-authors Issa Khalil, Abdallah Khreishah, NhatHai Phan, and Yao Ma, focuses on the intersection of machine learning, particularly Graph Neural Networks, and cybersecurity. Their work specifically investigates the adversarial robustness of GNNs in critical applications such as malicious domain detection, aiming to uncover vulnerabilities and inform the development of more secure AI-driven defense mechanisms.