extending logical attack graphs for efficient vulnerability analysis
Attack graph illustrates all possible multi-stage, multi-host attacks in an enterprise network and is essential for vulnerability analysis tools. Recently, researchers have addressed the problem of scalable generation of attack graph by logical formulation of vulnerability analysis in an existing framework called MulVAL. In this paper, we take a step further to make attack graph-based vulnerability analysis useful and practical for real networks. Firstly, we extend the MulVAL framework to include more complex security policies existing in advanced operating systems. Secondly, we present an expressive view of the attack graph by including negation in the logical characterization, and we present an algorithm to generate it. Finally, we present an incremental algorithm which efficiently recomputes the attack graph in response to the changes in the inputs of the vulnerability analysis framework. This is particularly useful for mutation or "what-if" analysis, where network administrators want to view the effect of network or host parameter changes to the attack graph before pushing the changes on the network. Preliminary experiments demonstrate the effectiveness of our algorithms.
attack graphs incremental analysis logic programming