Efficient Network Attack Graph Generation A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Information Technology at George Mason University By Ronald W. Ritchey Master of Science George Mason University, 1999 Director: Dr. Paul Ammann, Professor The Volgenau School of Information Technology and Engineering Spring Semester 2007 George Mason University Fairfax, VA UMI Number: 3242708 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction.
In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3242708 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved.
This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 ii Copyright 2006 Ronald W. Ritchey All Rights Reserved EFFICIENT NETWORK ATTACK GRAPH GENERATION by Ronald W.
Ritchey A Dissertation Submitted to the Graduate Faculty of George Mason University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Information Technology Committee: _) \. 7 Paul Ammann, Dissertation Director RE Daniel Barbara A Sanjeev Setia } ey c t ' Âu#czek —— Duminda Wijesekera Lara Daniel Menascé, Associate Dean for ZO Research and Graduate Studies YF Lloyd J. Griffiths, Dean, The (/ /⁄2Z⁄ Volgenau School of Information Technology and Engineering Dao „ba, 2^4 ẩ 2ò“ Spring Semester 2007 George Mason University Fairfax, Virginia iii DEDICATION This research is dedicated to all of the people who have supported both my work and my life over the several years it took me to complete this dissertation. Most especially this includes my wife Sharon who has been a constant source of encouragement, assistance, and guidance.
This research would not have been completed without her. iv ACKNOWLEDGEMENTS I would like to thank the many people who have supported and motivated my research. Foremost on this list is Dr. Paul Amman who encouraged me to complete and submit for publication the foundational ideas that led to the majority of this work.
I would also like to acknowledge the contributions of the other members of my dissertation committee including Dr. Daniel Barbara, Dr. Duminda Wijesekera, and Dr. Sanjeev Setia who have all contributed their knowledge, ideas and encouragement.
In addition to my committee, I have also had the privilege of collaborating with other faculty members, fellow students and university researchers including Dr. Sushil Jajodia, Mr. Joseph Pamula, Ms. Julie Street, Dr.
Steven Noel and Mr. Much of the technical motivation for my research comes from my corporate work at Booz Allen Hamilton. For this I must thank Mrs. Debra Banning, who has been my manager for the last eight years, and Admiral McConnell who, along with Debra hired me into the firm.
Finally, I would like to single out my friend and colleague Dr. Jeff Offutt who has been a constant source not only of ideas, but also inspiration. TABLE OF CONTENTS Page ABSTRACT. HH HH HH TH 1000.
su THỌ TH TH TH HH HH TH HT HH9 2 2 ThesSiS. SH HH TH HH TT TH Tàn.1 Attack graph construction and analysis can be automated while maintaining characteristics of real netWOrkS.2 Attack graphs can be used to assess the resiliency of candidate enterprise TI€WOKS. Attack graphs can be scaled to enterprise sized netWOrkS.o se e2 5 3 Related work (Other) .904 958 6 4 — Attack Graph MOdell. dc ch TH TT 0.
co TH TT TC n0 0100160108 13 4. cung HH TH HH ng 0081061600000.3 Composition of the Model .4 Instantiating the Model .H HH HH HH TH HH H010 011K13004600814010014011507560 19 5 Modeling vulnerabilities in TCP/TP netWOrkS .1 Modeling Link Layer S€CUTÏẨY.2 Modeling Network and Transport Layer S€CUTIẨy.3 Modeling Application Layer S€CUFÌty. on HH nan sa, 28 5.5 _ Section ConcÌusiOn.0 00000 01000088010004888758 33 6 Using attack graphs to analyze security resiliency of TCP/IP networks.2 Mutating the Miodel.3 Defining Mutation OperafOrS.4 — Coverage Criterion for Network S€CUFIẨ. co ng ng g2 6116158 42 6.5 Running the AnaÏySiS.
0 0 008001009983 898 45 7 Scaling attack graphs to enterprise netWOFKS.1 The Host-Centric Model. co HT ng n0 000840 80469001360090100010 80 56 7.4 Larger Network Example.5 Using the Host Centric Model to Analyze Inter-Organizational Relationships 70 vi 7.6 Network Merge Example.--- ch HH ng H000 000 031 g9 7.7 Section ConCÌUSIOT\. ----ccc co 99 SH 09 9. 10 0 0008550550856 A References +OEĐGCG000000000000000090%00000060%00000020090000400000000900000600000000009500000000600040000600600000009900900000 90606 : 9d): iu.
vil LIST OF TABLES Table Page Table 1. Example ConnectIVIty ÌMAfTIX.- - «HH ng 31 Table 2. Border Filtering RuÌes .- -- sọ HH TH HT. TH HH ng 37 Table 3.
Successful Mut2TIS. Thọ ng 45 Table 4. TH TH TH 0 1Á 000100800 04 61 Table 5. Host Vulnerabi]ifieS.
--- - << Họ Họ me 9 62 Table 6. Symantec Antivirus Corporate Edition vulnerability description. The list of access edges between the Supplier and the Customer networks. The firewall rules between the Supplier and the Customer networks.
84 viii LIST OF FIGURES Figure Page Figure 1. Example network security analysis for a single hOS(. Generic Link Layer Exploits. Example Transport Layer EXpÏOI.
Example Network with Connectivity-Limiting Firewall. Example Exploit Path 0. Example Telnet EXDÌOÏI. --- 4 <1 TH HT ng ng 29 Figure 8.
Example Berkeley rcp Command EXpÌÏOÏ(. 4 «- Ă 1s s se sessee 29 Figure 9. Example ÌNÑ@tWOTK.- óc Họ TH cọ TH Họ ng 0v 340 Figure 10. Example EXpÌOÏES.
-- óc có HH TH TH Họ ii 0g 33 Figure 12. - Gì TH THỌ cọ T0 v04 36 Figure 13.-- G5 sọ TH 0006 41 Figure 14. Mutation Analysis ŠySfem.-- -- <0 ng vớ 44 Figure 15. -- Ác HH HH Họ TH ng gp 51 Figure ló.
£inđMaximalAccess Algorithm. -- «sọ ng 53 Figure 17. potentia1NewMaximalAccess algorithm. Access graph with intended aCC€SS.
Maximal possible access due to all explOits. Effect of patching Apache Chunk vulnerab1Ìity.-- - ----« «sec essse 68 Figure 21. Adjacency-matriX SÍTUCUIT€.- - <5 nọ 0n nệm 71 Figure 22. Revised transitive closure prOC€dUF€.
addEdgeBetweenNetworks algorithm computes the highest levels of access Of a merged n€fWOFKK. The network topology for information sharing between Supplier and Customer TTWOTKS. 0 HH TH TH TH TT HH. The access graph for the Supplier netWOK.
The access graph for the Customer netWOFĂ .- sec nên 81 Figure 27. Resulting access graph after the customer and the supplier networks have been ÌnterCOnn€C{€C. - - -- c- cọ 0000000 00 000000150050 08880099310009910108690099180889 85 Abstract EFFICIENT NETWORK ATTACK GRAPH GENERATION Ronald W. George Mason University, 2006 Dissertation Director: Dr.
Paul Ammann Attack graphs are often used by penetration testing teams to represent the individual steps an attacker could use to compromise a network. The graphs built manually by these teams though are often incomplete and require substantial effort to create. Because of this, automated network attack graph generation is an area that has enjoyed significant research over the last several years. This dissertation further develops the body of knowledge in automated network attack graphs specifically focused on proving its usefulness to protecting real networks.
I show that attack graph construction and analysis can be automated while maintaining characteristics of real networks, that attack graphs can be used to assess the resiliency of candidate enterprise networks and that attack graphs can be scaled to enterprise sized networks. 1 | Introduction Attack graphs are often used by penetration testing teams to represent the individual steps an attacker could use to compromise a network. The graphs built manually by these teams though are often incomplete and require substantial effort to create. Because of this, automated network attack graph generation is an area that has enjoyed significant research over the last several years.
This dissertation contributes to the body of knowledge in automated network attack graphs specifically focused on proving its usefulness to protecting real networks. This document is organized as follows: the remainder of section one describes the problem and the relevance of the work; section two presents the hypotheses statements that I validate with this research; section three provides a survey of related work; section four presents an overview of network attack graphs; and sections five, six, and seven contain the results of my research. The document will conclude with a section containing conclusions. Motivation Security testing is normally limited to scanning of individual hosts with the goal of locating vulnerabilities that can be exploited to gain some improper level of access on the target network.
This approach can be very successful at discovering security problems, but it suffers from two major problems. First, it ignores security issues that can arise due to interactions of systems on a network. Second, it does not provide any prioritization of remediation for the issues that it reports. While most tools do report on the generic severity of each vulnerability they discover, these tools have no way of knowing the ultimate severity of the vulnerability to the entire network.
A method is needed that can determine the overall security of the network given knowledge of its individual vulnerabilities. This method must also be able to produce answers quickly. When a flaw is introduced into the security of a network, it opens a window of opportunity for an attacker. The longer this window is open, the more likely it is that an attacker will take advantage of it to compromise the network.
The amount of time from vulnerability introduction to attack can vary from seconds to infinity depending upon the current threat level, the discoverability of the flaw, and the environment of the vulnerable system. While, the average time between vulnerability introduction and attack is diminishing, it is still rare to see a vulnerability exploited in the first few days that knowledge of it exists. So in current conditions, a technique that can locate system wide vulnerabilities in hours would be helpful, but longer run-times would not be tolerable because there would be too great a risk that the information would arrive too late to be useful.2 Problem Statement The problem that this dissertation addresses is the development of techniques that efficiently automate the analysis of network security as opposed to host security A large collection of tools exists to perform local and remote computer vulnerability detection. These tools perform an acceptable job at locating individual vulnerabilities, but have no ability to place vulnerabilities in context with the overall network’s security.
This rapidly becomes a problem given the large number of findings that a single execution of one of these tools can produce. System administrators typically have a limited amount of time that can be spent remediating vulnerabilities. They need to focus their energies first on the vulnerabilities that will most likely lead to system compromise. Most tools prioritize their findings into high, medium and low severity.
Unfortunately, no system or network level insight is used to make this determination. They make their recommendations in an entirely generic way with no knowledge of the impact that these individual vulnerabilities have on the overall security of the network. This, combined with the volume of findings makes remediation prioritization difficult. There are a very limited number of vulnerabilities that are likely to be compromised in any given network.
There are also a limited number of vulnerabilities that would cause real concern to the network owners if they were compromised. What is needed is a technique or tool which can be used to show which vulnerabilities can lead to real damage. If administrators had such a tool they would be able to target their activities to the most significant issues leading to a large reduction in real-world risk.
