| When evaluating a network's security in terms of its defenses against potential security threats, it does not suffice to simply scan a network and identify the vulnerabilities of individual hosts on the network without considering how those vulnerabilities interact with the hosts and each other. Penetration testers and security researchers recognized this, and consequently developed a network attack chaining analysis which they routinely use to construct conceptual attack graphs consisting of multi-stage attack paths where each path represents a chain of exploits used by an attacker to break into a network. For example, an attacker typically penetrates a computer network by probing and modifying the network configuration and by exploiting vulnerabilities through a chain of exploits, where each exploit in the chain lays the groundwork for subsequent exploits.; A number of graph-based vulnerability analysis techniques have been proposed to analyze the vulnerability of networked systems to composite attacks. This dissertation extends the knowledge base of attack graph generation by investigating the limitations of the current attack graph models, as well as, providing novel solutions to the problem of efficient attack graph representation and analysis. We provide the following contributions to the area of attack graph generation and analysis: (1) Scalability. By utilizing a penetration tester's perspective of maximal level of penetration possible on a host, we provide a host-based model that grows polynomially with the number of hosts on the network. This allows our model to scale better than complete attack graphs in practical, more realistic enterprise sized networks. A working prototype tool has been implemented to demonstrate the practicality of our approach. (2) Incremental Analysis. We provide an incremental analysis to attack graphs by utilizing an already generated attack graph structure, as well as, propose a method whose total computational cost is smaller than that of recomputing an entire attack graph structure from scratch. (3) Network Sharing. In the context of our host-based model, we provide a novel framework for establishing, assessing, and managing trust in inter-organizational relationships, in terms of allowable network sharing, that is based on analyzing an invariance property of a computer network environment. (4) Non-monotonic Rules. By expressing state transitions as a set of rules in the state transition rule-based model, where rules are allowed to reduce attacker's capabilities and, possibly, depend on the absence of certain capabilities or con figuration attributes, we provide a more expressive model that is more flexible than the monotonicity assumption. (5) Security Metric. We provide automatic security recommendations from attack graphs in terms of the minimal number of initial attacker's attributes needed to compromise the system. Our recommendations help system administrators decide which network configuration is the most robust. |
