MDPI - Publisher of Open Access Journals

24 pages, 2294 KiB

Open AccessArticle

Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes

by Eugene Levner and Dmitry Tsadikovich

Algorithms 2024, 17(11), 504; https://doi.org/10.3390/a17110504 - 4 Nov 2024

Viewed by 1108

This paper studies the security issues for cyber–physical systems, aimed at countering potential malicious cyber-attacks. The main focus is on solving the problem of extracting the most vulnerable attack path in a known attack graph, where an attack path is a sequence of steps that an attacker can take to compromise the underlying network. Determining an attacker’s possible attack path is critical to cyber defenders as it helps identify threats, harden the network, and thwart attacker’s intentions. We formulate this problem as a path-finding optimization problem with logical constraints represented by AND and OR nodes. We propose a new Dijkstra-type algorithm that combines elements from Dijkstra’s shortest path algorithm and the critical path method. Although the path extraction problem is generally NP-hard, for the studied special case, the proposed algorithm determines the optimal attack path in polynomial time,

O (n m)

, where

n

is the number of nodes and

m

is the number of edges in the attack graph. To our knowledge this is the first exact polynomial algorithm that can solve the path extraction problem for different attack graphs, both cycle-containing and cycle-free. Computational experiments with real and synthetic data have shown that the proposed algorithm consistently and quickly finds optimal solutions to the problem. Full article

(This article belongs to the Section Algorithms for Multidisciplinary Applications)

► Show Figures

Figure 1

Abstract

This paper initiates the study of the mathematical aspects of the ad-hoc Lanzhou index. If G is a graph with the vertex set

{x_{1}, \dots, x_{n}}

, then the ad-hoc Lanzhou index of G is defined by [...] Read more.

This paper initiates the study of the mathematical aspects of the ad-hoc Lanzhou index. If G is a graph with the vertex set

{x_{1}, \dots, x_{n}}

, then the ad-hoc Lanzhou index of G is defined by

\tilde{L z} (G) = \sum_{i = 1}^{n} d_{i} {(n - 1 - d_{i})}^{2}

, where

d_{i}

represents the degree of the vertex

x_{i}

. Several identities for the ad-hoc Lanzhou index, involving some existing topological indices, are established. The problems of finding graphs with the extremum values of the ad-hoc Lanzhou index from the following sets of graphs are also attacked: (i) the set of all connected

ξ

-cyclic graphs of a fixed order, (ii) the set of all connected molecular

ξ

-cyclic graphs of a fixed order, (iii) the set of all graphs of a fixed order, and (iv) the set of all connected molecular graphs of a fixed order. Full article

Search Results (2)

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Saved Queries

Search Filter Reset All

Years

Feature Papers

Subjects

Journals

Article Types

Countries / Regions

Search Results (2)

Further Information

Guidelines

MDPI Initiatives

Follow MDPI