Degree Type


Date of Award


Degree Name

Master of Science


Computer Science

First Advisor

Samik Basu


Attack graphs provide formalism for modelling the vulnerabilities using a compact representation scheme. Two of the most popular attack graph representations are scenario attack graphs, and logical attack graphs. In logical attack graphs, the host machines present in the network are represented as exploit nodes, while the configurations (IDS rules, firewall policies etc.) running on them are represented as fact nodes. The actual user privileges that are possible on each of these hosts are represented as privilege nodes.

Existing work provides methods to analyze logical attack graphs and compute attack paths of varying costs. In this thesis we develop a framework for analyzing the attack graph from a defender perspective. Given an acyclic logical dependency attack graph we compute defense policies that cover all known exploits that can be used by the attacker and also are preferred with respect to minimizing the impacts. In contrast to previous work on analysis of logical attack graphs where quantitative costs are assigned to the vulnerabilities (exploits), our framework allows attack graph analysis using descriptions of vulnerabilities on a qualitative scale. We develop two algorithms for computing preferred defense policies that are optimal with respect to defender preferences. Our research to the best of our knowledge is the first fully qualitative approach to analyzing these logical attack graphs and formulating defense policies based on the preferences and priorities of the defender.

We provide a prototype implementation of our framework that allows logical attack graphs to be input using a simple text file (custom language), or using a GUI tool in graphical markup language (GML) format. Our implementation uses the NVD (National Vulnerability Database) as the source of CVSS impact metrics for vulnerabilities in the attack graph. Our framework generates a preferred order of defense policies using an existing preference reasoner. Preliminary experiments on various attack graphs show the correctness and efficiency of our approach.


Copyright Owner

Swapnanjan Chatterjee



File Format


File Size

78 pages