Implementing interactive analysis of attack graphs using relational databases

An attack graph models the causal relationships between vulnerabilities. Attack graphs have important applications in protecting critical resources in networks against sophisticated multi-step intrusions. Currently, analyses of attack graphs largely depend on proprietary implementations of specialized algorithms. However, developing and implementing algorithms causes a delay to the availability of new analyses. The delay is usually unacceptable due to rapidly-changing needs in defending against network intrusions. An administrator may want to revise an analysis as soon as its outcome is observed. Such an interactive analysis, similar to that in decision support systems, is desirable but difficult with current approaches based on proprietary implementations of algorithms. This paper addresses the above issue through a relational approach. Specifically, we devise a relational model for representing necessary inputs, such as network configurations and domain knowledge, and we generate attack graphs from these inputs as relational views. We show that typical analyses can be supported through different type of searches in an attack graph, and these searches can be realized as relational queries. Our approach eliminates the needs for implementing algorithms, because an analysis is now simply a relational query. The interactive analysis of attack graphs becomes possible, since relational queries can be dynamically constructed and revised at run time. As a side effect, experimental results show that the mature optimization techniques in relational databases can transparently improve the performance of the analysis.