SPGNN-API: A Transferable Graph Neural Network for Attack Paths
  Identification and Autonomous Mitigation
Attack paths are the potential chain of malicious activities an attacker
performs to compromise network assets and acquire privileges through exploiting
network vulnerabilities. Attack path analysis helps organizations to identify
new/unknown chains of attack vectors that reach critical assets within the
network, as opposed to individual attack vectors in signature-based attack
analysis. Timely identification of attack paths enables proactive mitigation of
threats. Nevertheless, manual analysis of complex network configurations,
vulnerabilities, and security events to identify attack paths is rarely
feasible. This work proposes a novel transferable graph neural network-based
model for shortest path identification. The proposed shortest path detection
approach, integrated with a novel holistic and comprehensive model for
identifying potential network vulnerabilities interactions, is then utilized to
detect network attack paths. Our framework automates the risk assessment of
attack paths indicating the propensity of the paths to enable the compromise of
highly-critical assets (e.g., databases) given the network configuration,
assets' criticality, and the severity of the vulnerabilities in-path to the
asset. The proposed framework, named SPGNN-API, incorporates automated threat
mitigation through a proactive timely tuning of the network firewall rules and
zero-trust policies to break critical attack paths and bolster cyber defenses.
Our evaluation process is twofold; evaluating the performance of the shortest
path identification and assessing the attack path detection accuracy. Our
results show that SPGNN-API largely outperforms the baseline model for shortest
path identification with an average accuracy >= 95% and successfully detects
100% of the potentially compromised assets, outperforming the attack graph
baseline by 47%.
Houssem Jmal, Firas Ben Hmida, Nardine Basta, Muhammad Ikram, Mohamed Ali Kaafar, Andy Walker
SPGNN-API: A Transferable Graph Neural Network for Attack Paths Identification and Autonomous Mitigation

###### Abstract

Attack paths are the potential chain of malicious activities an attacker performs to compromise network assets and acquire privileges through exploiting network vulnerabilities. Attack path analysis helps organizations to identify new/unknown chains of attack vectors that reach critical assets within the network, as opposed to individual attack vectors in signature-based attack analysis. Timely identification of attack paths enables proactive mitigation of threats. Nevertheless, manual analysis of complex network configurations, vulnerabilities, and security events to identify attack paths is rarely feasible. This work proposes a novel transferable graph neural network-based model for shortest path identification. The proposed shortest path detection approach, integrated with a novel holistic and comprehensive model for identifying potential network vulnerabilities interactions, is then utilized to detect network attack paths. Our framework automates the risk assessment of attack paths indicating the propensity of the paths to enable the compromise of highly-critical assets (e.g., databases) given the network configuration, assets' criticality, and the severity of the vulnerabilities in-path to the asset. The proposed framework, named SPGNN-API, incorporates automated threat mitigation through a proactive timely tuning of the network firewall rules and zero-trust policies to break critical attack paths and bolster cyber defenses. Our evaluation process is twofold; evaluating the performance of the shortest path identification and assessing the attack path detection accuracy. Our results show that SPGNN-API largely outperforms the baseline model for shortest path identification with an average accuracy \(\geq\) 95% and successfully detects 100% of the potentially compromised assets, outperforming the attack graph baseline by 47%.

 Graph Neural Network, Automated risk identification, zero trust, autonomous mitigation, risk assessment.

## I Introduction

Cyber attacks have become not only more numerous and diverse but also more damaging and disruptive. New attack vectors and increasingly sophisticated threats are emerging every day. Attack paths, in general, are the potential chain of malicious activities an attacker performs to compromise assets and acquire network privileges through exploiting network vulnerabilities. Attack path analysis helps organizations identify previously unknown or unfamiliar chains of attack vectors that could potentially compromise critical network assets. This approach contrasts with signature-based attack analysis approaches such as vulnerability scanning, which typically focus on detecting individual attack vectors.

Timely identification of attack paths enables proactive mitigation of threats before damage takes place. Nevertheless, manual processes cannot always provide the proactivity, fast response, or real-time mitigation required to deal with modern threats and threat actors, and constantly growing and dynamic network structure. An automated and efficient threat identification, characterization, and mitigation process is critical to every organization's cybersecurity infrastructure.

The existing literature proposes various approaches based on attack graphs and attack trees that assess the interdependencies between vulnerabilities and the potential impact of exploitation [1, 2, 3, 4]. While these techniques provide a systematic perspective on potential threat scenarios in networks, their effectiveness is constrained by their inability to dynamically adapt to changes in the network structure, thus requiring the re-evaluation of the entire process.

Several approaches based on deep learning (DL) have been proposed in the literature [5, 6, 7] to address this issue. For such models, network structure information is not learned, unlike Graph Neural Networks (GNN), but rather provided as input to the DL models. Consequently, the structure-based input must be re-generated every time there is a change in the network structure. This can potentially necessitate the entire DL models to be retrained, causing additional computational overhead.

Another limitation of existing approaches is either being restricted to a set of predefined attacks [6] or using a set of predefined rules to define the potential interplay between vulnerabilities [8]. Given the rising complexity of cyber-attacks, a comprehensive approach is vital to ensure the security of network assets and sensitive data.

**Challenges.** There are three major challenges for attack path detection: (1) **Adaptiveness**: How to develop an automated and adaptive identification of attack paths given the dynamic nature of the network structure driven by trends such as remote users, bring-your-own devices, and cloud assets? (2) **Agility**: With attackers constantly finding new ways to exploit vulnerabilities, how to comprehensively identify the potential interplay between vulnerabilities without being bound to a pre-defined set of rules or attack scenarios? (3) **Efficiency**: How to efficiently characterize and rank the risks of attack paths, and autonomously triage the ones requiring prompt response without disrupting the network functionalities?
**Our Work.** Considering these challenges, we devise "Shortest Path Graph Neural Network-API" (SPGNN-API), a framework offering an autonomous identification of potential attack paths and associated risks of compromising critical assets. It further incorporates proactive mitigation of high-risk paths. (1) To address the adaptiveness challenge, we develop a novel GNN approach for attack path identification. The inductive property of GNNs enables them to leverage feature information of graph elements to efficiently generate node embeddings for previously unseen data. Additionally, GNNs incorporate network structural information as learnable features. This renders GNN-based approaches self-adaptive to dynamic changes in the network structure. (2) To tackle the agility challenge, we assume that an attacker who has compromised an asset can exploit all the underlying vulnerabilities. We rely on the GNN efficiency of graph representation learning to learn all potential vulnerability interactions that could compromise critical assets based on the CVSS base score metrics [9]. (3) To address the efficiency challenge, we automate the risk analysis of attack paths to determine their likelihood of compromising critical assets, based on factors such as network configuration, assets' criticality, and the severity of the vulnerabilities [10] in-path to the asset. We then develop autonomous mitigation of high-risk attack paths by automatically tuning the network zero-trust policies (See Section III-A) to disrupt the paths without impacting the network functionalities.

In this work, we address a key limitation of existing GNNs that fail to capture the positional information of the nodes within the broader context of the graph structure [11, 12]. For instance, when two nodes share the same local neighborhood patterns but exist in different regions of the graph, their GNN representations will be identical. To address this, we introduce the SPGNN-API, which extends the Positional Graph Neural Network model [13] to achieve a transferable model for computing shortest paths to a predefined set of nodes representing highly-critical network assets.

**Evaluation.** We conduct a three-fold evaluation process: Firstly, we evaluate the performance of the SPGNN shortest path calculation in a semi-supervised setting. Secondly, we assess the performance in a transfer-learning setting. Thirdly, we evaluate the accuracy of identifying critical attack paths. To carry out our evaluation, we use two synthetic network datasets, two real-world datasets obtained from middle-sized networks, and two widely used citation network datasets: Cora [14] and Citeseer [15]. We compare the GNN path identification performance with the state-of-the-art GNN path identification model "SPAGAN" [11]. Additionally, we compare the performance of the SPGNN-API with a state-of-the-art approach for attack path generation, "MulVAL" [8].

**Contributions.** In summary, our research contributions are:

* We develop a novel transferable GNN for shortest path calculation that relies exclusively on nodes' positional embedding, regardless of other features. The presented approach is able to transfer previous learning to new tasks, hence alleviating the lack of labeled data problems.
* We propose a novel GNN-based approach for network vulnerability assessment and potential attack path identification that leverages the inductive ability of the GNNs to accommodate the dynamic nature of enterprise networks without requiring continuous retraining.
* We demonstrate that, unlike traditional GNN, the performance of positional GNN models is enhanced by removing self-loops achieving an average improvement \(\approx\) 5% on our six datasets with a maximum of 9%.
* We develop a novel comprehensive model for learning the propensity of vulnerabilities to contribute to attacks compromising critical assets based on the CVSS base metrics without being bound to specific attack signatures or pre-defined set of rules for vulnerabilities interactions.
* We formulate an autonomous risk characterization of the detected attack paths based on the network connectivity structure, asset configurations, criticality, and underlying vulnerabilities CVSS base score metrics.
* We automate the mitigation of high-risk attack paths that could potentially compromise critical assets by tuning the network's zero-trust policies to break the path without disrupting the network functionalities.
* We evaluate our proposed approach, the SPGNN-API, against two baseline models: the SPAGAN [11] for GNN-based shortest paths detection and MulVAL [8] for attack paths identification. Our results show that SPGNN-API outperforms the baseline models, achieving an average accuracy of over 95% for GNN shortest path identification. Moreover, our approach successfully identifies 47% more potentially compromised assets that were not detected by the baseline model, MulVAL.

The rest of the paper is organized as follows: In Section II, we survey the literature. In Section III, we overview the zero-trust network architecture on which we base the attack paths risk assessment and mitigation. We further review different GNN architectures and limitations. Section IV details the design of our SPGNN-API framework. We evaluate our model and present our results in Section V. Finally, Section VI concludes our paper.

## II Related Work

This work has two major contributions; a novel GNN approach for shortest path identification and an autonomous framework for detecting and mitigating attack paths in dynamic and complex networks. To highlight the novelty of our work, in this section, we survey the literature and differentiate our contributions from previous studies related to network vulnerability assessment and attack graphs generation (Sec. II-A) and GNN-based distance encoding and shortest path identification (Sec. II-B).

### _Network Attack Graph and Vulnerability Assessment_

We classify the existing approaches for vulnerability assessment into three main categories: traditional attack graphs/trees, ML/DL-based frameworks, and GNN-based approaches.

**Traditional attack graphs/trees vulnerabilities assessment frameworks.** This class of models examines the interplay between the network vulnerabilities and the extent to which attackers can exploit them, offering a structured representation of the sequence of events that can potentially lead to the
compromise of network assets [1, 2, 3, 4]. However, a major limitation of these models is their inability to adapt to dynamic changes in the network structure. Any modification to the network structure requires the regeneration of the attack graph.

**Deep learning vulnerabilities assessment frameworks.** Previous studies have explored the use of deep learning-based (DL) approaches for vulnerability assessment and attack path detection [5, 6, 7]. To identify potential attack paths in a network, information about the network structure and configurations is essential. However, in DL-based approaches, the network structure information is not learned, unlike GNN, and instead, provided as input to the DL model. Therefore, the structure-based input needs to be re-generated every time there is a change in the network structure, which may also require retraining the entire DL model.

**Graph neural network vulnerabilities assessment frameworks.** Recently, several approaches based on GNN have been proposed for cyber security tasks such as vulnerabilities detection [16, 17], anomaly detection [18], malware detection [19] and intrusion detection [20]. However, these approaches, in particular the vulnerability detection models, do not include any risk evaluation process that can help prioritize the detected threats for proactive mitigation.

### _GNN Shortest Path Identification_

The goal of graph representation learning is to create representation vectors of graphs that can precisely capture their structure and features. This is particularly important because the expressive power and accuracy of the learned embedding vectors impact the performance of downstream tasks such as node classification and link prediction.

However, the existing GNN architectures have limited capability for capturing the position/location of a given node relative to other nodes in the graph [21] (See Sec. III-E). GNN iteratively updates the representation of each node by aggregating representations of its neighbors. Many nodes may share a similar neighborhood structure, and thus, the GNN produces the same representation for them although the nodes may be located at different locations in the graph.

Several recent works have addressed this limitation of GNNs. Although some of these approaches have been successful, we present the first GNN-based method that is transferable and can accurately calculate shortest paths using only distance information, without relying on other node or edge features.

For instance, in [12], the authors propose a general class of structure-related features called distance encoding, which captures the distance between the node set whose representation is to be learned and each node in the graph. These features are either used as extra node attributes or as controllers of message aggregation in GNNs.

The Positional Graph Neural Network (PGNN) [13] approach randomly samples sets of anchor nodes. It then learns a non-linear vector of distance-weighted aggregation scheme over the anchor sets that represents the distance between a given node and each of the anchor sets. Another approach, SPAGAN [11], conducts paths-based attention in node-level aggregation to compute the shortest path between a center node and its higher-order neighbors. SPAGAN, therefore, allows more effective aggregation of information from distant neighbors into the center node.

## III Background

In this section, we overview the Zero-Trust architecture and related policies' governance and compliance on which we base the risk assessment, triage, and mitigation of the detected attack paths (Sec. III-A, III-B). As the proposed framework relies on shortest paths calculation to identify attack paths, we briefly explain the shortest path identification problem (Sec. III-C) and discuss the processing of graph data with GNNs (Sec. III-D). We highlight the limitations of existing GNN architectures (Sec. III-E) that have motivated our novel GNN-based model for shortest path identification.

### _Zero-Trust Architecture_

Zero-trust (ZT) is a comprehensive approach to secure corporate or enterprise resources and data, including identity, credentials, access management, hosting environments, and interconnecting infrastructure. ZT architecture (ZTA) can be enacted in various ways for workflows.

For instance, micro-segmentation [22] enforces ZTA by creating secure zones in cloud and data-center environments, isolating and securing different application segments independently. It further generates dynamic access network-layer control policies that limit network and application flows between micro-segments based on the characteristics and risk appetite of the underlying network's assets.

Micro-segmentation is implemented via a distributed virtual firewall that regulates access based on network-layer security policies for each micro-segment. By limiting access to only what is necessary, micro-segmentation helps to prevent the spread of attacks within a network. The ZT micro-segmentation policies are defined as:

**Definition 1**.: _ZT policies refer to network layer policies that the micro-segmentation distributed firewalls enforce to control the internal communications of the network. These policies follow the format: < Source Micro-Segment IP Range > < Destination Micro-Segment IP Range > < Protocol > Port Range >._

### _Governance and Compliance_

The visibility of the network micro-segments underlying assets' characteristics and criticality is crucial for the optimal management of network communication policies. To achieve this purpose, a semantic-aware tier, called "governance", is used with the ZT policies to ensure their compliance with the best practices for communication between the network assets [23]. The governance tier uses semantic tags (e.g. Database, Web Server, etc.) to perform a risk-aware classification of the micro-segments and underlying assets based on the criticality of the data stored transported, or processed by the micro-segment assets and their accessibility [24].

In this work, we consider eight criticality levels for classifying the network micro-segments as detailed in Table I. This
table is generated following the study in [24] in conjunction with guidance from the security team administrators of the two enterprises contributing to this study. It is worth mentioning that the governance rules are generated following the best network communication practices. They are tuned per organization based on the network structure and business processes. A governance rule is defined as follows:

**Definition 2**.: _A governance rule represents the best practice of who/what communicates to the different network assets. It relies on the micro-segments assigned tags to assess the communications enabled through the network ZT policies. A governance rule has the following format: \(<\) Source Tag \(>\)\(<\) Destination Tag \(>\)\(<\) Service Tag \(>\)._

The Governance module assesses the compliance of each ZT policy with the respective governance rule. Consider \(P\) to be the set of governance rules. Governance-compliant connections, denotes by \(CC\), are defined as follows:

**Definition 3**.: _Compliant connections are communications allowed by the ZT policies that comply with the defined governance rules. Let \(CC\) denote the set of compliant edges (connections enabled by the ZT policies) where \(CC\subseteq\left\{E\mid\left(\mathit{tag}(x),\mathit{tag}(y),s\right)\in P\right\}\) and \(\mathit{tag}(v)\) be a function to identify the governance tag assigned to vertex \(v\in V\)._

For instance, the ZT policy \(<\) Human-Resources Web Server IP Address \(>\)\(<\) Human-Resources Application Server IP Address \(>\)\(<\) TCP \(>\)\(<\) 443 \(>\) is compliant with the governance rule \(<\) Web Server \(>\)\(<\) Application Server \(>\)\(<\) Secure Web \(>\). Hence, all communications enabled through the above ZT policy are marked safe.

Similarly, we denote by \(NC\) the set of non-compliant edges. In a network setting, _compliant_ connections are usually considered trusted as per the governance policies. The criticality of the non-compliant connections amongst the assets is a function of the trust rating of its incident vertices i.e., assets.

In this work, we are mostly concerned with attack paths potentially compromising highly-critical assets. In particular, the ones incorporating non-compliant connections which imply a relatively higher risk of being exploited. In this context, we define highly-critical assets as follows:

**Definition 4**.: _Highly-critical assets are network resources that are considered valuable due to the sensitivity of the data they host (e.g. databases). Let \(V_{critical}\) denote a set of nodes with maximum criticality. Formally, \(V_{critical}=\left\{v\mid v\in V\ \wedge\ c_{v}=\ 7\right\}\) where \(c_{v}\) is the criticality rating of node \(v\) implied by the assigned governance tag._

### _Shortest Path Identification_

Shortest path (SP) algorithms (e.g. Bellman-Ford, Dijkstra's) are designed to find a path between two given vertices in a graph such that the total sum of the weights of the edges is minimum. Our proposed framework relies on shortest paths calculation to identify the eminent worst-case scenario for potential cyber-attacks compromising highly-critical assets. In this context, we define a critical attack path as follows [25]:

**Definition 5**.: _An attack path is a succinct representation of the sequence of connections (enabled by ZT policies) through vulnerable assets that an attacker needs to exploit to eventually compromise a highly-critical asset._

The time complexity of shortest path (SP) algorithms on a directed graph can be bounded as a function of the number of edges and vertices by \(\mathit{O}\left(VE\right)\)[26]. However, the complexity of SP algorithms can be improved by using GNNs to approximate the distance between nodes in a graph. After training a neural network, the time complexity of finding the distance between nodes during the inference phase is constant, denoted by \(\left(O\left(1\right)\right)\).

### _Processing Graph Data with GNNs_

The goal of graph representation learning is to generate graph representation vectors that capture the structure and features of graphs accurately. Classical approaches to learning low dimensional graph representations [27, 28] are inherently transductive. They make predictions on nodes in a single, fixed graph (e.g. using matrix-factorization-based objectives) and do not naturally generalize to unseen graph elements.

Graph Neural Networks (GNNs) [29, 30] are categories of artificial neural networks for processing data represented as graphs. Instead of training individual embeddings for each node, GNNs _learn_ a function that generates embeddings by sampling and aggregating features from a node's local neighborhood to efficiently generate node embeddings for previously unseen data. This inductive approach to generating node embeddings is essential for evolving graphs and networks constantly encountering unseen nodes.

GNNs broadly follow a recursive neighborhood aggregation (or message passing) where each round of neighborhood aggregation is a hidden layer \(l\) in the GNN. Let \(\mathit{G=\left(V,E\right)}\) denote a directed graph with nodes \(V\) and edges \(E\). Let \(\mathit{N}(v)\) be the neighborhood of a node \(v\) where \(\mathit{N}(v)=\left\{u\in V\mid(v,u)\in E\right\}\). For each layer, or each message passing iteration, a node \(v\) aggregates information from its sampled neighbors \(\mathcal{N}\left(v\right)\) as described in Equation 1.

\[h_{v}^{l}=\sigma\left(M^{l}\cdot\Lambda\left(\{h_{v}^{l-1}\}\cup\left\{w_{e} h_{u}^{l-1},\forall u\in\mathcal{N}(v)\right\}\right)\right) \tag{1}\]

The aggregated information is computed using a differentiable function \(\Lambda\) and a non-linear activation function \(\sigma\). \(w_{e}\) is the edge feature vector from node \(v\) to node \(u\). The set of weight matrices \(M^{l},\forall l\in\left\{1,\ldots,L\right\}\) are used to propagate information between layers. After undergoing \(k\) rounds of aggregation, a node is represented by its transformed feature vector, which encapsulates the structural information of the node's k-hop neighborhood as described in [31].

\begin{table}
\begin{tabular}{|l|l|} \hline
**Level** & **Description** \\ \hline
0 & UnTagged/unknown \\
1 & Untrusted and external/public c.g internet 0.0.0.0/0 \\
2 & Trusted external e.g vendor \\
3 & Internet facing \\
4 & Untrusted and internal e.g users \\
5 & Internal and connecting to untrusted internal e.g web servers \\
6 & Internal and connecting to data or non-critical data \\
7 & Critical data \\ \hline \end{tabular}
\end{table} TABLE I: Assets criticality levels and associated description.
### _GNNs Expressive Power_

The success of neural networks is based on their strong expressive power that allows them to approximate complex non-linear mappings from features to predictions. GNNs learn to represent nodes' structure-aware embeddings in a graph by aggregating information from their \(k\)-hop neighboring nodes. However, GNNs have limitations in representing a node's location or position within the broader graph structure [12]. For instance, two nodes that have topologically identical or isomorphic local neighborhood structures and share attributes, but are in different parts of the graph, will have identical embeddings.

The bounds of the expressive power of GNNs are defined by the 1-Weisfeiler-Lehman (WL) isomorphism test [21] In other words, GNNs have limited expressive power as they yield identical vector representations for subgraph structures that the 1-WL test cannot distinguish, which may be very different [12, 13].

## IV Proposed Framework SPGNN-API

In this section, we present our proposed framework that aims to achieve end-to-end autonomous identification, risk assessment, and proactive mitigation of potential network attack paths. As depicted in Figure 1, the SPGNN-API consists of five modules: (a) Network micro-segmentation, (b) governance and compliance, (c) network data pre-processing, (d) GNN-based calculation of shortest paths to critical assets, and (e) risk triage and proactive mitigation. We elaborate on these modules in the following subsections.

### _Micro-Segmentation_

First, we represent a given network as a directed connectivity graph. Let \(C(V,E,S)\) be a labeled, directed graph that represents the network's connectivity, where \(V\) is the set of graph vertices representing the network assets (servers and cloud resources). The set of graph-directed edges \(E\) indicates the connected vertices' communication using the service identified through the edge label \(s\in S\). Here \(S\) denotes the set of network services that are defined by a protocol and port range and \(E\subseteq\{(v,u,s)\mid(v,u)\in V^{2}\wedge x\neq y\wedge s\in S\}\).

We derive the set of feature vectors characterizing the graph vertices (network assets) and edges (incident assets communication) from layers 3 and 4 network flow packet headers. This includes features such as frequently used ports and protocols, frequent destinations, and flow volume. Our approach assumes that assets within the same micro-segment exhibit similar communication patterns.

To automatically identify the network micro-segments, we use attentional embedded graph clustering [32], a deep embedded clustering based on graph attentional auto-encoder. The clustering algorithm aims at partitioning the connectivity graph \(C=(V,E,S)\) into \(k\) sub-graphs representing the network micro-segments. It learns the hidden representations of each network asset, by attending to its neighbors, to combine the features' values with the graph structure in the latent representation. We stack two graph attention layers to encode both the structure and the node attributes into a hidden representation.

### _Governance and Compliance_

Each micro-segment is assigned a "governance" tag implying its underlying assets' criticality and risk appetite. For instance, a _web server_ asset criticality is lower than a _database_. To automate the assignment of tags, we further assess the network flows in terms of communication patterns and frequently used ports and protocols to identify the dominating service(s) used by each micro-segment's underlying assets. For instance, a micro-segment mostly using TCP 80 for communication is most likely a web server while a micro-segment substantially using TCP 3306 is presumably a database. The detailed process of application profile assignment and the handling of dynamic ports is beyond the scope of this paper.

We then automate the generation of the ZT policies to govern the communication between the micro-segments at the network layer. We first identify all attempted communications in the network and automatically generate ZT policies to enable all these communications. We compare the generated

Fig. 1: SPGNN-API framework architecture where Sub-figure a) illustrates the micro-segmentation process through attentional embedded graph clustering of the network based on layer 2 and 3 flow packets header analysis and the network connectivity graph. This process is followed by a GNN-based model for generating the ZT policies governing the communication between the micro-segments as detailed in Sub-figure b). Sub-figure c) describes the network data pre-processing stage to illuminate the edges that cannot be part of an attack path. The updated graph is then used to identify the shortest paths to highly-critical assets as illustrated in sub-figure d). Finally, edges are classified as either safe, compliant critical, or non-compliant critical. The ZT policies are then tuned to block the latter class of edges.
policies with the governance rules and highlight the non-compliant policies. We further assess the risk imposed by the non-compliant connections based on the criticality of the incident edges and the network topology. We then formulate a GNN model for tuning the ZT policies to reduce the risks without disrupting the network functionalities. The details of this process are beyond the scope of this paper.

### _Network Data Pre-processing_

SPGNN-API relies on shortest paths calculation to predict imminent attack paths. We aim to pre-process the network connectivity graph by identifying edges that can potentially contribute to attack paths and filter out the edges that cannot be exploited by an attacker. This pre-processing stage ensures that all calculated shortest paths do represent attack paths.

An essential step toward the identification of an attack path is locating network vulnerabilities and assessing their severity which directly impacts the risk imposed by potential attacks exploiting these vulnerabilities. To locate the network vulnerabilities, we utilize a port scanner (e.g. Nessus). We then rely on the NIST Common Vulnerability Scoring System (CVSS) base metrics [10] to identify the features and severity of the detected vulnerabilities.

We identify edges potentially contributing to critical attack paths following an exclusion methodology. We filter out edges that cannot be exploited by attackers based on a pre-defined set of criteria. This set of criteria does not define specific vulnerability interactions and ways of exploiting these vulnerabilities. They rather highlight the propensity of exploiting the vulnerabilities to eventually compromise critical assets.

**Edges exclusion criteria:** Graph edges are excluded if they don't meet the following criteria: (1) The edge source node needs to have a vulnerability with CVSS base metric "scope" set to "changed". This implies that the vulnerability can impact resources in components beyond its security scope. Hence, being exploited, it enables the attacker to move further in the network and potentially reach a highly-critical asset. (2) The edge source node needs to have a vulnerability with CVSS overall base score metric "High" or "Critical". This implies the potential criticality of the attack step. (3) All edges with highly-critical asset destinations are considered.

A major strength of our proposed approach is that it does not restrict the detection of potential attacks to a predefined set of vulnerability interactions. Instead, we assume that once an attacker gains access to an asset, they can exploit any underlying vulnerability without any specific prerequisites such as access rights or user privilege. This assumption is based on the constantly evolving nature of attacks and the ability of attackers to discover new ways of exploiting vulnerabilities. Consequently, we do not track an end-to-end sequence of attack steps as there might be infinite alternatives. Instead, we identify the propensity of an edge being involved in an attack by determining if there exists a (shortest) path from that edge to a highly-critical asset going through vulnerable nodes.

This comprehensive approach to representing vulnerability interactions is not feasible for traditional attack path detection models due to the time complexity of generating attack trees, where the size of the graph is a function of the potential vulnerabilities' interactions [8]. However, our presented approach, which is based on the P-GNN, overcomes this issue with a time complexity of \(O(\mathit{nlog}^{2}n)\), where \(n\) is the number of assets in the network. Accordingly, the size of the graph is irrelevant to the number of vulnerabilities and their potential interactions.

### _GNN Model for Shortest Paths Identification_

We formulate and develop a transferable GNN model for shortest path identification. Our approach involves identifying the shortest paths to a predefined set of nodes representing highly-critical assets in a network. By identifying the shortest path representing the minimum set of exploits an attacker would need to compromise such highly-critical assets, we account for the worst-case scenario for potential attacks.

We base our framework on the Position Graph Neural Network (P-GNN) model. The P-GNN approach randomly samples sets of anchor nodes. It then learns a non-linear vector of distance-weighted aggregation scheme over the anchor sets that represents the distance between a given node and each of the anchor sets [13].

To enhance the P-GNN architecture; firstly, we recover the actual shortest path distance from the node embeddings through a transferable GNN model. Secondly, we identify the shortest path length to a predefined set of nodes representing high-criticality assets rather than a randomly distributed set of anchors. Thirdly, we update the message function to only consider the position information for calculating the absolute distances, independent of node features. Lastly, since we aim to identify high-risk network connections, we embed the shortest path distance as an edge feature.

**Anchor Sets.** We formulate a strategy for selecting anchors and assigning critical assets to anchor sets. Let \(n\) be the number of highly-critical assets in the network. We first mark anchors around the nodes representing highly-critical assets where each anchor set holds only one critical asset. As per the original P-GNN model, to guarantee low distortion embedding at least \(k\) anchors are sampled where \(k=c\log^{2}|V|\) and \(c\) is a constant. If the number of critical assets \(|V_{critical}|<k\), the remaining anchors are sampled randomly where each node in \(V\sim V_{critical}\) is sampled independently. The anchors' size is distributed exponentially and is calculated as follows:

\[|Anchor\_i|=\lfloor\frac{|V|}{2^{i+1}}\rfloor,i\in\{0..k\} \tag{2}\]

**Objective Function.** The goal of the SPGNN is to learn a mapping \(V\times V_{critical}^{k}\mapsto R^{+}\) to predict the actual minimum shortest path distances from each \(u\in V\) to \(V_{critical}\) where \(k=|\,V_{critical}|\). Hence, unlike the original P-GNN objective function, defined for the downstream learning tasks using the learned positional embeddings (e.g. membership to the same community), our objective is formulated for learning the actual shortest path length as follows:

\[\min_{\phi}\sum_{\forall u\in V}\mathcal{L}\left(\min_{i\in\{1..k\}}\hat{d}_{\phi}\left(u,v_{i}\right)-\min_{i\in\{1..k\}}d_{y}\left(u,v_{ i}\right)\right)\] \[\min_{\phi}\sum_{\forall u\in V}\mathcal{L}\left(\min\left(\hat{d }_{\phi}\left(u,V_{critical}\right)\right)-\min\left(d_{y}(u,V_{critical}) \right)\right) \tag{3}\]
where \(\mathcal{L}\) is the mean squared error (MSE) loss function to be minimized. \(\hat{d}_{\phi}\left(u,\,V_{critical}\right)\) is the vector of learned approximation of the shortest path distance from a node \(u\) to every critical asset \(v\in V_{critical}\). \(d_{y}\) is the observed shortest path distance. As the model aims to identify the risk imposed by critical paths, we account for the worst-case scenario by considering the minimum shortest path length from the (vulnerable) node to a highly-critical asset. Therefore, the loss is computed only on the minimum of the distance vector.

**Message Passing.** The message-passing function, in our approach, exclusively relies on the position information to calculate the absolute distances to the anchor sets and disregards node features. To calculate position-based embeddings, we follow the original P-GNN \(q\)-hop approach where the 1-hop \(d_{sp}^{t}\) distance can be directly inferred from the adjacency matrix. During the training process, the shortest path distances \(d_{sp}^{g}(u,v)\) between a node \(u\) and an anchor node \(v\) are calculated as follows [13]:

\[d_{sp}^{q}(u,v)\mapsto\begin{cases}d_{sp}(u,v),&if\ d_{sp}(u,v)<q\\ \infty&otherwise.\end{cases} \tag{4}\]

Where \(d_{sp}(u,v)\) is the shortest path distance between a pair of nodes. Since the P-GNN aims to map nodes that are close (in position) in the network to similar embedding, the distance is further mapped to a range in \((\,0\,,1\,)\) as follows [13]:

\[s(u,v)=\frac{1}{d_{sp}^{g}(u,v)+1} \tag{5}\]

Accordingly, the message-passing process is defined as:

\[h_{u}=\phi(x_{u}\oplus_{(v\in\mathbb{R}_{v})}\psi(u,v)) \tag{6}\]

where \(h_{u}\) represents the node embedding of the vertex \(u\), \(x_{u}\) is the input feature vector of the node \(u\) inferred based on the adjacency matrix. \(\oplus\) is the aggregation function. In our approach, we found that the mean aggregation function provides the best performance. \(\psi\) is the message function and is computed as described in Equation 5. Finally, \(\phi\) is the update function to obtain the final representation of node \(u\).

**Recovery of true paths length.** We aim to learn the true shortest path length by pulling the value of the node embedding closer to the labels during the learning process. To this end, we rely on the MSE loss function to minimize the deviation between the predicted and observed shortest path distances. To recover the true path length from the learned positional embedding, we introduce four steps to the P-GNN learning process after learning the node embeddings through message passing: Firstly, for every node \(u\in V\), we calculate the absolute distance (AD) of the learned node embeddings between \(u\) and each critical asset \(v\in V_{critical}\). Secondly, we assign the minimum value of the calculated AD to the node \(u\). Thirdly, as the calculated AD is not necessarily an integer value, we approximate the assigned AD to an integer value to represent the predicted shortest path distance. Lastly, we attribute the approximated shortest path value to the incident edge features.

_(1) Absolute Distance (AD) of node embedding._ We particularly use the AD function since it is less impacted by outliers, hence, more robust. This is particularly significant since complex network structures are characterized by a high variance in the criticality of the assets and the path-length distributions. For every node \(u\in V\), we calculate a vector of absolute distances \(T_{u}\) between the learned embedding of \(u\) denoted as \(h_{u}\) and the embedding of every critical asset \(v_{i}\in V_{critical}\), denoted as \(h_{v_{i}}\). \(h_{u}\) and \(h_{v_{i}}\) are calculated as described in Equation 6. The AD vector is calculated as follows, where \(k\) is the embedding space dimension:

\[AD(u,v)=\sum_{n=1}^{k}|h_{u}^{n}-h_{v}^{n}| \tag{7}\] \[T_{u}=\forall_{v_{i}\in V_{critical}}AD(u,v_{i})\]

\(T_{u}\) is then used in Equation 3 to calculate the loss where \(\hat{d}\left(u,\,V_{critical}\right)=T_{u}\).

_(2) Minimum absolute distance to a critical asset._ The downstream task is concerned with identifying the risk imposed by potential attack paths. If a node \(u\in V\) has (shortest) paths to multiple critical assets, we account for the worst-case scenario by identifying the minimum length of the shortest paths \(z_{u}\) and assigning its value as a feature for node \(u\). It is calculated as follows:

\[z_{u}=\min_{i\in\{1...k\}}T_{u}^{i} \tag{8}\]

where \(k\) is the embedding space dimension.

_(3) Approximation of path length._ We identify two approaches for approximating the learned minimum shortest path length \(z_{u}\) of a certain node \(u\). The first approach, denoted as \(SPGNN_{R}\), relies on simple rounding of the shortest path length. This naive approach is rather intuitive and is fully transferable as discussed in Section V. The predicted distance \(SP_{R}(u)\) is then calculated as follows:

\[SP_{R}:V\mapsto N \tag{9}\] \[SP_{R}(u)\mapsto Round(z_{u})\]

The second approach, \(SPGNN_{DNN}\), relies on a deep neural network (DNN) to learn a mapping between the learned shortest path length and its integer representation. To overcome the inaccuracies induced by rounding the AD, we aim to increase the separation between the labels representing the observed paths-length. Since the downstream task is concerned with assessing the risks imposed by the attack paths, we restrict the detection of paths to a certain range of length values that are anticipated to induce high risks. Accordingly, we transform the path identification into a classification task where the learned embeddings are mapped to a class representing a path length within the range of interest.

The goal of the DNN is to learn a mapping to predict the integer representation of the minimum shortest path distance \(z_{u}\) described in Equation 8 from each \(u\in V\) to \(V_{critical}\) where \(k=|\,V_{critical}|\). Accordingly, the objective function is:

\[\min_{\theta}\sum_{\forall u\in V}\mathcal{L}_{c}(g_{\theta}(\lambda_{u}),l) \tag{10}\]

where \(g_{\theta}:R^{a}\mapsto R^{b}\) is a function that maps the node features \(\lambda_{u}\) (that include \(z_{u}\)) where \(|\lambda_{u}|=a\) to a label \(l\) in the set of the encoded labels \(L=I,...,b\) where \(b\) is the threshold of
paths length considered. \(\theta\) denotes the parameters of \(g_{\theta}\) and \(\mathcal{L}_{c}\) is the categorical cross entropy loss function.

In addition to the minimum shortest path distance \(z_{u}\), we enrich the classifier input with additional heuristics of the original P-GNN positional embeddings \(h_{u}\) described in Equation 6. We rely on the intuition that the learned P-GNN embeddings of nodes that share the same shortest path distance are most likely to have similar statistical features. We define the DNN classifier input feature vector \(\lambda_{u}|\ \forall u\in\ V\) as follows:

\[\begin{split}\lambda_{u}=&(\max_{v\in V_{critical}}| cos_{sim}(u,v)|,\max_{v\in V_{critical}}cross_{entropy}(u,v),\\ & min(h_{u}),max(h_{u}),mean(h_{u}),var(h_{u}),norm_{2}(h_{u}), \\ & std(h_{u}),median(h_{u}),z_{u}).\end{split} \tag{11}\]

The output of the DNN model is the classes representing the different shortest path lengths. We rely on the one-hot encoding mapping to represent the output. The predicted distance denoted as \(SP_{DNN}(u)\) is then calculated as follows:

\[\begin{split} SP_{DNN}:V\mapsto N\\ SP_{DNN}(u)\mapsto g_{\theta}(z_{u})\end{split} \tag{12}\]

The stacking of a DNN classifier significantly enhances the accuracy of the SPGNN when trained and tested on the same network data. However, it does not perform equally well in a transfer learning setting as discussed later in Section V. This can be attributed to the fact that the input to the DNN classifier depends on the learned positional embeddings \(h_{u}\) and is highly impacted by the size and distribution of the anchors set.

_(4) Shortest path as edge feature._ When it comes to graph representation learning, relying on node features is often more efficient than edge features due to the amount of information contained within the nodes, and the relatively smaller number of nodes as compared to edges. As a result, we begin by predicting the shortest paths as additional node features. Then, We attribute the calculated distance to all _incident edges of the node_, as shown in Figure 2. Let \(v\) be a node in the network, \(SP(v)\) be the learned integer representation of the minimum shortest path for node \(v\), and \(y_{e}\) be the feature vector for edge \(e\). Accordingly, the node features are assigned to their incident edges as follows:

\[\{\forall u\in V\ \wedge\ \exists\ e_{u,v}\in E\,\ y_{e_{u,v}}=SP(v)\} \tag{13}\]

**Labels.** Manually generated labels are expensive and hard to acquire. Therefore, we rely on a regular shortest path algorithm (e.g. Dijkstra), denoted by \(d_{sp}(u,v)\), to generate the labels for training the SPGNN. We calculate the observed shortest path \(d_{y}\) from a node \(u\) to critical asset \(v\) as per Equation 14. The calculated shortest path represents the label of the node \(u\).

\[\begin{split} d_{y}(u,v)\mapsto\begin{cases}0&if\ v\notin V _{critical}\ \lor\ d_{sp}(u,v)=\emptyset\\ d_{sp}(u,v)&otherwise\end{cases}\end{split} \tag{14}\]

### _Risk Triage and Mitigation_

We develop a module to automate the assessment of risks imposed by potential exploitation of the detected attack paths in terms of the propensity and impact of compromising highly-critical assets. We first identify critical attack paths that require immediate intervention based on a pre-defined set of criteria. We then autonomously locate connections (edges) playing a key role in enabling the critical attack paths. Accordingly, we proactively implement the proper mitigation actions.

To assess attack path criticality, we introduce a new metric namely _Application Criticality (AC)_. The assets criticality metric assesses the risk based on the assets workload (e.g. database, application server, etc.) and data processed. However, the AC metric assesses the risk based on the application the asset belongs to. For instance, a human-resources application database with human-identifiable information is assigned a higher AC rating than an inventory application database.

**Application criticality:** Applications can be classified based on the scope of expected damages, if the application fails, as either, mission-critical, business-critical, or non-critical (operational and administrative) [33]. Organizations rely on mission-critical systems and devices for immediate operations. Even brief downtime of a mission-critical application can cause disruption and lead to negative immediate and long-term impacts. A business-critical application is needed for long-term operations and does not always cause an immediate disaster. Finally, organizations can continue normal operations for long periods without the non-critical application. Two different companies might use the same application but it might only be critical to one. Hence, we rely on the security team of enterprises contributing to this study to assign the AC.

Attack paths are considered critical if they meet the following criteria: (1) The start of the path is an asset with criticality level \(\leq\) 4 implying the ease of accessibility of the asset. (2) Destination highly-critical assets belong to a mission-critical application (3) The shortest path is of length at most five.

After filtering out non-critical paths, we aim to locate and characterize connections playing a key role in enabling critical attack paths. Accordingly, we model a DNN edge classifier to assess the edges of attack paths. Three output classes are defined, based on which mitigation actions are planned: (1) Non-compliant critical, (2) compliant critical, and (3) safe.

Non-compliant edges are inherently un-trusted as they do not comply with the organization's communication best practices. Accordingly, non-compliant critical edges are immediately blocked by automatically tuning the ZT policies enabling the connection. Compliant connections represent legitimate organizational communication, hence blocking them might disrupt the network functionalities. Therefore, these

Fig. 2: The shortest path length is assigned to the path source node and all its incident edges.
connections are highlighted and the associated ZT policies are located. A system warning is generated requesting the network administrators to further assess the highlighted ZT policies. Finally, no actions are required for safe connections.

We assess the criticality of attack paths' edges based on the following criteria, representing the input of the DNN classifier:

* \(\text{Feature}_{1}\): The trust level of the edge destination asset.
* \(\text{Feature}_{2}\): The AC rating of the edge destination asset.
* \(\text{Feature}_{3}\): Exploited vulnerability base score of the source asset.
* \(\text{Feature}_{4}\): The shortest path distance from the edge to the highly-critical asset.
* \(\text{Feature}_{5}\): The compliance of the edge.

Let \(f_{\psi}:E\mapsto Y\) be a function that maps the set of edges \(E\) to the set of labels \(Y\) representing the three edge classes where \(\psi\) denotes the parameters of \(f_{\psi}\). Let \(feat_{e}\) be the input feature vector of the edge \(e\) to be assessed. To optimize the edge's classification task, we express the objective function as the minimization of the cross-entropy loss function \(\mathcal{L}_{d}\). We represent this objective function as follows:

\[\min_{\psi}\sum_{\forall einE}(f_{\psi}(feat_{e}),y) \tag{15}\]

## V Results and Evaluation

The evaluation process is three folds: (1) evaluating the performance of the \(SPGNN\) shortest path calculation in a semi-supervised setting (Sec. V-D), (2) assessing the performance in a transfer-learning setting (Sec. V-E), and (3) evaluating the accuracy of identifying critical attack paths and locating key paths edges (Sec. V-F).

### _Experimental Settings_

We test the performance of SPGNN in three settings:

**Experiment 1 - evaluating the performance of shortest paths identification.** The focus of this experiment is to evaluate the ability of \(SPGNN_{R}\) and \(SPGNN_{DNN}\) to identify the shortest paths in a semi-supervised setting. We use the same dataset for training and testing. We compare the prediction accuracy with the baseline model \(SPAGAN\). To identify the minimum ratio of labeled data required to achieve satisfactory performance, we use the train and test split masks with distribution shifts for all datasets described in Section V-B.

**Experiment 2 - assessing and validating the learning transferability.** This experiment setting is particularly concerned with assessing the learning transferability of the proposed \(SPGNN_{R}\) shortest path identification. We test the transferability by training the model using a dataset and testing it using a different unlabeled dataset.

**Experiment 3 - Assessing and validating the attack paths identification.** This experiment aims to assess the end-to-end performance of the SPGNN-API in identifying critical attack paths and highlighting key connections enabling the paths. We test the performance of this task by comparing the model accuracy to labeled synthetic network datasets and real-world datasets of enterprises contributing to this research.

### _Dataset_

Two classes of datasets are used for the proposed model evaluation: (1) Enterprise network datasets (two synthetic datasets, \(STD_{1}\) and \(STD_{2}\), and two real-world datasets, \(RTD_{1}\) and \(RTD_{2}\)). (2) Two widely used citation network datasets Cora [14] and Citeseer [15].

We generate two synthetic datasets (\(STD_{1}\) and \(STD_{2}\)) to imitate a mid-sized enterprise network setting. We defined the node configurations and network connections to cover all possible combinations of values for the five features used for assessing the criticality of the attack path's edges.

We collect the real-world datasets, denoted by \(RTD_{1}\) and \(RTD_{2}\), from two-mid sized enterprises; a law firm and a university, respectively. We rely on the Nessus scan output to identify the configurations and properties of the network assets as well as the underlying vulnerabilities. We use enterprise-provided firewall rules, ZT policies, and governance rules to define and characterize the assets' communications.

Table II lists the details of the datasets used in assessing the performance of our proposed model. In the proposed approach, we identify the path length to a set of anchor nodes to represent highly-critical assets. For the citation datasets, we randomly sample nodes to represent highly-critical assets. Since the citation datasets do not represent a real network setting, we will limit the evaluation of the attack path identification to the (real-world and synthetic) enterprise network datasets.

### _Baseline Models_

We compare the performance of our proposed model architectures \(SPGNN_{R}\) and \(SPGNN_{DNN}\) with the state-of-the-art baseline \(SPAGAN\)[11] w.r.t. to the shortest path identification. The SPAGAN conducts path-based attention that explicitly accounts for the influence of a sequence of nodes yielding the minimum cost, or shortest path, between the center node and its higher-order neighbors.

To validate the performance of the SPGNN-API for attack paths identification, we generate the network attack graph using the MulVAL tool [8] by combining the output of the vulnerability scanner Nessus [34] and the enterprise network perimeter and zero-trust firewall policies.

### _Evaluation of Shortest path Detection_

In this section, we assess the performance of the two proposed architectures the \(SPGNN_{R}\) and \(SPGNN_{DNN}\) using all six datasets. We report the mean accuracy of 100 runs with 80%-20% train-test masks and 20 epochs.

\begin{table}
\begin{tabular}{l||r|r|r|r|r} \hline \hline
**Dataset** & **Nodes** & **Edges** & **Critical** & **Compliant** & **Non-compliant** \\ \hline \(SDT_{1}\) & 864 & 5,018 & 284 & 2,002 & 3,016 \\ \(SDT_{2}\) & 865 & 5,023 & 284 & 2,002 & 3,021 \\ \(RTD_{1}\) & 221 & 1,914 & 21 & 882 & 1,032 \\ \(RTD_{2}\) & 370 & 21,802 & 70 & 10901 & 10901 \\ \(CORA\) & 2,708 & 10,556 & 180 & N/A & N/A \\ \(CITESEER\) & 3,327 & 9,464 & 523 & N/A & N/A \\ \hline \hline \end{tabular}
\end{table} TABLE II: Dataset features and statistics.
**Accuracy evaluation:** Table III summarizes the performance of \(\mathit{SPGNN}_{R}\) and \(\mathit{SPGNN}_{DNN}\). While both models can discriminate symmetric nodes by their different distances to anchor sets, we observe that \(\mathit{SPGNN}_{DNN}\) significantly outperforms \(\mathit{SPGNN}_{R}\) across all datasets. This can be attributed to the power of the DNN in capturing the skewed relationships between the generated positional embedding and the defined set of path-length classes. Furthermore, transforming the prediction of path lengths to a classification task, where one-hot encoding is used to represent the output, enables the model to capture the ordinal relationships between the different lengths and hence the gain in the performance. Both architectures exhibit performance degradation when tested with the real-world dataset \(RTD_{1}\). Due to the relatively small size of the dataset. The model could not capture the complex relationships between the network entities during training.

**Self-loops:** In general, adding self-loops allows the GNN to aggregate the source node's features along with that of its neighbors [35]. Nevertheless, since our model relies only on positional embedding irrelevant to the features of the nodes, removing the self-loops enhances the accuracy of SPGNN as detailed in Table III as the iterative accumulation of the node positional embedding confuses the learned relative distance to the anchor sets. Accordingly, we introduce a data pre-processing stage to remove self-loops in the real-world network datasets and the citation datasets.

**SPGNN convergence:** We illustrate in Figure 3 the progression of the Mean Squared Error MSE loss during the training process of \(\mathit{SPGNN}_{R}\). We particularly assess the \(\mathit{SPGNN}_{R}\) since, unlike the \(\mathit{SPGNN}_{DNN}\), its output directly reflects the GNN performance without further learning tasks. We observe that the gradient is sufficiently large and proceeding in the direction with the steepest descent which indeed minimizes the objective. The stability and efficacy of the learning process constantly enhance the accuracy of the model irrelevant of the dataset characteristics. The objective function is sufficiently smooth indicating that the model is not under-fitting.

**Analysis of the \(\mathit{SPGNN}_{R}\) generated shortest path distance embedding.** We conducted an in-depth analysis of 20 random samples from the test sets of the six datasets. For each sample, we plot the predicted \(\hat{d}\) vs rounded \(\mathit{SP}_{pred}\) vs observed \(d_{y}\) shortest paths distances in blue, yellow, and red, respectively, as illustrated in Figure 4. We observe the proximity of the predicted and observed distances where the predicted values are mostly in the range of +/- 1 hop from the observed values. Hence, we prove the strength of the proposed GNN approach in approximating the shortest path distance. We further notice that the rounded values are vastly overlapping with the observed values which further proves the robustness of the simple, yet intuitive, rounding approach.

**Baseline comparison:** We compare the performance of the proposed model with the baseline \(\mathit{SPGAN}\). We observe that the proposed architectures, in particular the \(\mathit{SPGNN}_{DNN}\), strictly outperform \(\mathit{SPGAN}\) and can capture the skewed relationships in the datasets as shown in Table III. This can be attributed to the fact that \(\mathit{SPGAN}\) uses a spatial attention mechanism that only considers the neighboring nodes within a predefined radius around each target node during the learning phase and does not incorporate features of nodes beyond the predefined distance which impacts the model performance. Furthermore, \(\mathit{SPAGAN}\) (and most state-of-the-art approaches) relies on the graph elements' features to calculate the shortest paths distance information. This justifies the performance degradation of \(\mathit{SPAGAN}\), in this case, since only graph structure and positional embedding are considered. This further proves the strength of the proposed approach that can identify, with high accuracy, the shortest paths distance irrelevant to graph elements features.

### _Evaluation of Transfer-Learning_

In this setting, the pre-training and testing processes are executed through distinct datasets. The goal of the pre-training is to transfer knowledge learned from labeled datasets to facilitate the downstream tasks with the unlabeled datasets. We only consider the \(\mathit{SPGNN}_{R}\) for testing in this setting. The stacked DNN of the \(\mathit{SPGNN}_{DNN}\) approach is characterized by a fixed input size and hence is not expandable to accommodate different network structures.

To assess the robustness of the model transferability, we pre-train the model using different synthetic and real-world datasets. We observe that, in general, the size and sophistication of the dataset used for pre-training highly impact the performance of the model transferability. In general, training with real data yields better performance. We believe that the significant improvements can be attributed to the ability of \(\mathit{SPGNN}\) to utilize the perturbation in real-world data to consider more complicated interactions between the data samples which optimizes the model's ability to extend label information to unlabeled datasets.

In contrast, pre-training the model with synthetic data and testing on a real dataset slightly hurts the accuracy. The non-perturbed structure of the synthetic data gives limited performance gain and yields negative transfer on the downstream classification task. In general, the results show convincing evidence that the inductive capabilities of the proposed \(\mathit{SPGNN}\) generalize to unseen datasets as detailed in Table IV.

### _Evaluation of Attack Paths and Critical Edges Detection_

The SPGNN-API does not record the end-to-end sequence of attack steps as there might be an infinite number of alternatives as discussed in Section V-F. It rather identifies

Fig. 3: \(\mathit{SPGNN}_{R}\) MSE loss convergence for the six datasets.
the propensity of an edge being part of an attack, i.e. there exists a (shortest) path from that edge to a highly-critical asset going through vulnerable nodes. Accordingly, to evaluate the performance of the attack path detection, we do not rely on an end-to-end assessment of attack paths. We rather assess the propensity of single edges being part of an attack. We evaluate the accuracy of the edge classification (Sec. IV-E) in two different settings semi-supervised and transfer-learning. We compare the model performance against a baseline (MulVAL).

We base our assessment on the four enterprise network datasets as the citation datasets do not incorporate vulnerability information. We rely on the security team of the enterprises contributing to this study to manually label connections they would potentially block or patch given the network structure, reported vulnerabilities, and network visualization tools.

**Accuracy assessment:** We assess the performance of the edge classifier in categorizing the attack path edges as either critical compliant, critical non-compliant, or safe. Comparing the output of the classifier to the manually labeled data we note the performance results in Table V. Since the set of safe edges comprises the attack path edges classified as safe as well as the connectivity graph edges that were not part of any attack path, the recorded model accuracy proves the efficacy of the presented approach in detecting attack paths in general and identifying key critical edges in particular.

In addition to the raw accuracy rates, we report the receiver operating characteristic curve (ROC) and area under the curve

\begin{table}
\begin{tabular}{l c c c c c|c c c c c c} \hline \hline  & \multicolumn{4}{c}{**Dataset Before Deleting self loops**} & \multicolumn{4}{c}{**Dataset After Deleting self loops**} \\ \cline{2-13}
**Metrics** & \(STD_{1}\) & \(STD_{2}\) & \(RTD_{1}\) & \(RTD_{2}\) & \(CORA\) & \(CITESER\) & \(STD_{1}\) & \(STD_{2}\) & \(RTD_{1}\) & \(RTD_{2}\) & \(CORA\) & \(CITESER\) \\ \hline \(SPGNN_{R}\)\(\mathcal{L}\) & 0.07 & 0.14 & 0.36 & 0.02 & 0.33 & 0.53 & 0.02 & 0.14 & 0.22 & 0.01 & 0.29 & 0.38 \\ \hline \hline Accuracy \(SP_{pred}\) & 90.00\% & 84.04\% & 71.00\% & 94.02\% & 65.70\% & 68.53\% & 98.88\% & 84.47\% & 72.41\% & 97.05\% & 65.34\% & 72.53\% \\ \hline \(Accuracy\pm_{1hop}\) & 100\% & 98.42\% & 91.61\% & 100\% & 96.41\% & 92.65\% & 100\% & 98.50\% & 93.85\% & 100\% & 97.11\% & 94.54\% \\ \hline \hline \(SPGNN_{DNN}\)\(\mathcal{L}_{c}\) & 0.03 & 0.08 & 0.24 & 0.01 & 0.26 & 0.41 & 0.01 & 0.10 & 0.19 & 0.01 & 0.23 & 0.26 \\ \hline \(AccuracyPSIGN_{DNN}\) & 95.63\% & 80.14\% & 53.05\% & 96.10\% & 81.36\% & 79.36\% & 98.45\% & 84.47\% & 78.65\% & 98.25\% & 75.82\% & 81.20\% \\ \hline \(Accuracy\pm_{1hop}\) & 86.45\% & 85.29\% & 86.15\% & 98.65\% & 92.70\% & 84\% & 93.10\% & 91.93\% & 89.23\% & 100\% & 92.94\% & 87.32\% \\ \hline \hline MSE(SPAGAN) & 0.54 & 0.62 & 0.91 & 0.48 & 0.85 & 0.95 & 0.52 & 0.59 & 0.72 & 0.35 & 0.69 & 0.82 \\ \hline \(AccuracySP_{pred}\) & 52.36\% & 50.14\% & 57.50\% & 82.35\% & 62.12\% & 53.36\% & 54.23\% & 52.36\% & 56.23\% & 85.65\% & 63.26\% & 55.68\% \\ \hline \(Accuracy\pm_{1hop}\) & 86.45\% & 85.29\% & 86.15\% & 98.65\% & 92.70\% & 84\% & 88.20\% & 85.60\% & 84.42\% & 96.75\% & 93.98\% & 83.62\% \\ \hline \hline \end{tabular}
\end{table} TABLE III: Overview of shortest paths identification accuracy of \(SPGNN_{R}\) and \(SPGNN_{DNN}\) as compared to the \(SPAGAN\) across the six datasets before and after deleting self-loops.

Fig. 4: Shortest path distance distribution of 20 random samples from each of the six datasets. The blue and yellow points are the \(SPGNN\) predicted distances _before_ and _after_ the application of the rounding process, respectively. The red points are the observed distances. The Figures illustrate the accuracy of the predicted distances being within the range [-1,1] of the observed values. We further observe that the majority of the _rounded distances_ are either overlapping with or closer to the _observed distances_. This shows the efficiency of the rounding approach to enhance the shortest path distance prediction accuracy.
(AUC). We assess the ability of the classifier to discriminate critical and safe edges, in general. Accordingly, we combine the critical compliant and critical non-compliant classes. The true positive samples are (compliant/non-compliant) critical samples that have been classified as critical. The false positive samples are critical samples that have been classified as safe. The ROC curve in Figure 5 illustrates outstanding discrimination of the two classes with an AUC score of 0.998.

**Transfer-learning:** To assess the end-to-end transferability of the presented approach, we train the edge classifier using a dataset and test it using different datasets. The recorded classification accuracy in Table VI proves the inductive capabilities of \(SPGNN\) and its ability to efficiently characterize previously unseen data. To our expectations, training the model using a real dataset performs better on all datasets. The model's capacity to extend the label information to previously unseen datasets is enhanced by the perturbations in real-world datasets that enable the classifier to consider more complex interactions between the data samples. To plot the ROC curve, we combine the critical compliant and critical non-compliant classes and assess the model's ability to discriminate the critical and safe edges. The ROC curve in Figure 6 illustrates outstanding discrimination of the two classes with an AUC score between 0.93 and 0.98.

**Baseline comparison** : We compare the SPGNN-API with the MulVAL attack graph generator. The MulVAL-generated attack graph nodes can be of three types; configuration nodes, privilege nodes (exploits), and attack step nodes (conditions). The privilege nodes represent compromised assets. The root nodes of the attack graph represent network configurations/vulnerabilities contributing to attack possibilities. The privilege nodes denote the compromised assets.

The set of paths of the attack graph comprises all directed attack paths starting at the root configuration nodes and ending at the privilege nodes (attack goals). We configure the attack path generation to have all highly-critical assets as attack goals. We assess the attack step nodes and note the ZT policies that have been a step to achieve the attack privilege. We then compare the noted rules to the set of rules that have been flagged as critical by the SPGNN-API.

We perform the analysis relying on \(RTD_{2}\) since no Nessus scan is available for the synthetic datasets and we had limited access to the \(RTD_{1}\) Nessus output for privacy reasons. The dataset has 370 nodes, of which 70 are highly-critical assets. The Nessus identified 44 vulnerable assets, of which six are highly critical. All six assets have been identified as potentially compromised by the MulVAL as well as \(SPGNN-API\). The \(SPGNN\), however, outperformed the MulVAL by detecting more potentially compromised non-critical assets as detailed in Table VII. This proves the significance of the presented holistic approach to vulnerability interaction.

Further assessing the generated attack paths, we observe that SPGNN-API labeled 713 edges (and underlying ZT policies) as critical while only 171 appeared as a MulVAL attack step. This can be attributed to the fact that MulVAL restricts the detection of potential attacks to a predefined set of vulnerability interactions while the SPGNN-API assumes that any vulnerability can potentially be exploited by the attacker irrelevant of any pre-requisites. Of the 171 edges detected by MulVAL, our approach was able to detect 166. The five edges we missed are connecting level 7 highly-critical assets to level 1 assets. Since we aim to protect highly-critical assets these edges are not considered critical as per our features.

## VI Conclusion

This work presents the first attempt at GNN-based identification of attack paths in dynamic and complex network structures. Our work fills the gaps and extends the current

\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{3}{c}{**Dataset**} \\ \cline{2-5}
**Metrics** & \(STD_{1}\) & \(STD_{2}\) & \(RTD_{1}\) & \(RTD_{2}\) \\ \hline Cross\_Entropy Loss & \(0.095\) & \(0.0061\) & \(0.01\) & \(0.007\) \\ \hline Accuracy & \(99.5\%\) & \(100\%\) & \(99.11\%\) & \(100\%\) \\ \hline \hline \end{tabular}
\end{table} TABLE V: Performance overview of the \(SPGNN\) edge criticality classification in semi-supervised setting.

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Model trained by**} & \(RTD_{1}\) & **Model trained by** & \(STD_{1}\) \\ \cline{2-7}
**Metrics** & \(STD_{1}\) & \(STD_{2}\) & \(RTD_{2}\) & \(STD_{2}\) & \(RTD_{1}\) & \(RTD_{2}\) \\ \hline Cross\_Entropy Loss & \(0.009\) & \(0.0037\) & \(1.20\) & \(0.002\) & \(0.79\) & \(0.18\) \\ \hline Accuracy & \(100.00\%\) & \(98.17\%\) & \(92.75\%\) & \(99.87\%\) & \(92.42\%\) & \(97.44\%\) \\ \hline \hline \end{tabular}
\end{table} TABLE VI: Performance overview of the \(SPGNN\) edge criticality classification in transfer-learning.

Fig. 5: ROC curves of the \(SPGNN\) edge classification in the semi-supervised setting.

Fig. 6: ROC curves of the \(SPGNN\) edge classification in the transfer-learning setting.
literature with a novel GNN-based approach to automated vulnerability analysis, attack path identification, and risk assessment of underlying network connections that enable critical attack paths. We further present a framework for automated mitigation through a proactive non-person-based timely tuning of the network firewall rules and ZT policies to bolster cyber defenses before potential damage takes place.

We model a novel GNN architecture for calculating shortest path lengths exclusively relying on nodes' positional information irrelevant to graph elements' features. We prove that removing self-loops enhances the accuracy of shortest path distance identification as self-loops render the nodes' positional embedding misleading. Furthermore, our in-depth analysis of attack path identification proves the efficiency of the presented approach in locating key connections potentially contributing to attacks compromising network highly-critical assets, with high accuracy. A key strength of the presented approach is not limiting the attacks' detection to a predefined set of possible vulnerabilities interaction. Hence, it is capable of effectively and proactively mitigating cyber risks in complex and dynamic networks where new attack vectors and increasingly sophisticated threats are emerging every day.
