Exploring Node Ranking Algorithms in Attack Graphs: A Study on Structure, Observations, and Algorithmic Variants
Mukesh Kumar Yadav, Peter J. Hawrylak · 2024
Effective reduction of state in an attack graph is crucial for predicting threats in the system. This ablation study explores different state reduction algorithms including node ranking algorithms based on graph structure; state indexing, Naive Bayes, and modified Naive Bayes algorithms based on evidence. State indexing lacks prior knowledge; Naive Bayes utilizes prior knowledge; modified Naive Bayes algorithm includes prior, evidence, and graph structure information for the analysis. A comparison of these state reduction algorithms is made based on the quality of a reduced set of states. The reduced set of states contains a highly probable set of states that capture intrinsic details about the attack graph. This study utilizes attack graphs in which nodes represent system states and edges represent exploits. The experiment used in our study reveals that the algorithms that use evidence perform better than algorithms that utilize graph structures. Consequently, the modified Naive Bayes algorithm is selected for the state reduction task for the analysis of attack graphs.