Most Vulnerable Attack Trace in a Probabilistic Attack Graph

In this paper, we investigate the properties and computation of attack traces on probabilistic attack graphs, a model that integrates probability into traditional attack graphs to reflect the varying exploitability of network vulnerabilities. We introduce the Most Vulnerable Attack Trace (MVAT) problem, which aims to identify the attack trace with the highest cumulative success probability for an attacker. To address this problem, we propose both an exact algorithm and a heuristic algorithm, each designed to navigate the complexities introduced by cycles in the attack graph. Our exact algorithm explores all possible sequences of node selections to ensure the optimal attack trace, while our heuristic algorithm efficiently approximates the MVAT in polynomial time. We evaluate the performance of our algorithms using an extensive dataset, demonstrating the usefulness of the proposed algorithms.