Network security modeling with intelligent and complexity analysis (2010)

Protecting network-accessible resources from unauthorized use requires understanding&#13;\nof network vulnerability. Modeling network attacks as chains of exploitable&#13;\nvulnerabilities, referred to as vulnerability exploits, can help security administrators&#13;\nlocate security flaws and implement appropriate preventative measures.&#13;\nHowever,mostmodel generation approaches do not scalewell to very large networks&#13;\ndue to the combinatorial explosion of the size of the search space. Much research&#13;\nhas focused on how to automatically and efficiently generate such models.&#13;\nTo realize the full benefits of network securitymodels, effectivemodel analysis is&#13;\ncrucial. Since security models are often too large and complex for pinpointing critical&#13;\nattacks manually, there is a need for automated approaches to security model&#13;\nanalysis. Moreover, network security has to deal with the trade off between accessibility&#13;\nand safety protection. Thus, selecting suitable counter-measures to secure&#13;\na network may involve conflicting judgments and subjective preferences. There&#13;\nhas been little research in this area and most current approaches lack the ability to&#13;\ndirectly assist in making informed decisions.&#13;\nThis dissertation presents a principled and practical approach to developing&#13;\nautomated preventative network security systems that show possible attacks, in&#13;\nterms of chains of vulnerability exploits, and offer mechanisms to assist in selecting&#13;\nappropriate counter-measures. To address the problem of scalability, this&#13;\ndissertation proposes host-centric model checking, an analytical framework that provides&#13;\nefficient generation of a new network security model, namely a host-centric&#13;\nattack graph, using a model checking technique along with a monotony assumption (i.e., valid preconditions of a vulnerability exploit are never invalidated). Using&#13;\nmodel abstraction and efficient reachability computation by a model checker&#13;\ntogether with the assumption, the proposed approach can be shown, both theoretically&#13;\nand empirically, to reduce the time complexity of model generation to a&#13;\nquadratic polynomial in the number of hosts. At the time of this research, compared&#13;\nwith all other existing model generation approaches, this is the best computational&#13;\nbound obtained.&#13;\nTo address the issue of security model analysis, this dissertation proposes two&#13;\nautomated approaches to intelligent analysis of a security attack model, namely&#13;\nexploit-based analysis and preference-based analysis. The former is quantitative and&#13;\nthe latter is qualitative analysis. Exploit-based analysis proposes a heuristic algorithm&#13;\nthat uses knowledge about the exploitability of network vulnerability and&#13;\na link analysis technique that employs a Markov property to rank each node in&#13;\nthe security attack model in order of its likelihood of being successfully attacked.&#13;\nPreference-based analysis provides a semi-automated analysis by means of logical&#13;\nreasoning and an explicitmodel of conditional preferences. The analysis result can&#13;\nassist a security administrator in making informed decisions about cost-effective&#13;\ncounter-measures based on the administrator’s preference criteria. To the best of&#13;\nour knowledge, preference-based analysis is the first of its kind for approaches to&#13;\nnetwork security model analysis. This research also proposes an efficient method&#13;\nfor computing attack path expressions and includes a study of a simple but realistic&#13;\ncase scenario. The proposed analysis approaches can be applied to any form&#13;\nand any topological structure of a security model. These approaches are general&#13;\nand theoretically grounded.