Cyclic Bayesian Attack Graphs: A Systematic Computational Approach
This work addresses a computational bottleneck for security analysts using attack graphs to evaluate network security, offering a generic solution for handling cycles, though it appears incremental as it builds on existing BAG frameworks.
The paper tackles the problem of cycles in automatically generated Bayesian Attack Graphs (BAGs), which prevent probability calculations using standard Bayesian network theory, by providing a systematic computational approach that interprets BAGs as combinational logic circuits and presents an algorithm to compute state probabilities without altering the graphs, demonstrating scalability on networks with hundreds of machines.
Attack graphs are commonly used to analyse the security of medium-sized to large networks. Based on a scan of the network and likelihood information of vulnerabilities, attack graphs can be transformed into Bayesian Attack Graphs (BAGs). These BAGs are used to evaluate how security controls affect a network and how changes in topology affect security. A challenge with these automatically generated BAGs is that cycles arise naturally, which make it impossible to use Bayesian network theory to calculate state probabilities. In this paper we provide a systematic approach to analyse and perform computations over cyclic Bayesian attack graphs. %thus providing a generic approach to handle cycles as well as unifying the theory of Bayesian attack graphs. Our approach first formally introduces two commonly used versions of Bayesian attack graphs and compares their expressiveness. We then present an interpretation of Bayesian attack graphs based on combinational logic circuits, which facilitates an intuitively attractive systematic treatment of cycles. We prove properties of the associated logic circuit and present an algorithm that computes state probabilities without altering the attack graphs (e.g., remove an arc to remove a cycle). Moreover, our algorithm deals seamlessly with all cycles without the need to identify their types. A set of experiments using synthetically created networks demonstrates the scalability of the algorithm on computer networks with hundreds of machines, each with multiple vulnerabilities.