Modeling Network Diversity for Evaluating the Robustness of Networks against ZeroDay Attacks Lingyu Wang1 Mengyuan Zhang1, Sushil Jajodia2, Anoop Singhal3, and Massimiliano Albanese2 1 2 3 Concordia University, Canada George Mason University, USA National Institute of Standards and Technology, USA ESORICS 2014 Outline Introduction Modeling Network Diversity

Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric Simulation Conclusion 2 Outline Introduction Network Diversity Metrics Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric

Simulation Conclusion 3 Why Worry about Zero-Day Attacks? A real threat to mission critical networks Governments and cybercriminals alike are stockpiling zero-day bugs1 The NSA spent more than $25 million a year to acquire software vulnerabilities - Edward Snowden Private vendors provide at least 85 zero-day exploits on any given day of the year - Stefan

Frei E.g., Stuxnet exploits 4 different/complementary zero day vulnerabilities to infiltrate a SCADA network 1 http://krebsonsecurity.com/2013/12/how-many-zero-days-hit-you-today/ 4 How Could Diversity Help? Stuxnets attack strategy

3rd party (e.g., contractor) organizations network machine with Siemens Step 7 PLC The degree of software diversity along potential attack paths can be considered a good metric for the networks capability of resisting Stuxnet 5 Existing Work on Diversity Software diversity has long been regarded as a security mechanism for improving robustness Tolerating attacks as Byzantine faults by comparing outputs or behaviors of diverse variants Opportunistic or automatically generated diversity (e.g., via randomization) improves the practicality

Many new applications for diversity Moving target defense (MTD) Resisting worms in sensor networks 6 So Why Another Paper? At a higher abstraction level, as a global property of an entire network, network diversity and its impact on security has not been formally modeled How to define the diversity metric function? count? how to count? How to apply the metric function? on the network as a multiset of resources? what about

paths? On which path? On one or more paths? It depends on the use cases... 7 Example Use Cases 1. Intuitive notion of diversity can be Worm propagation misleading. A formal Count might be sufficient model is needed. 2. Different diversity Targeted attack (e.g., on metrics host4)may be needed for different Least attack effort may not be sufficient

purposes. MTD The layers do not combine to increase attack effort 8 Our Contribution We take the first step towards formally modeling network diversity as a security metric We propose a network diversity function based on well known mathematical models of

biodiversity in ecology We design a network diversity metric based on the least attacking effort We design a probabilistic network diversity metric to reflect the average attacking effort We evaluate the metrics and algorithms through simulation The modeling effort helps understanding 9 Outline Introduction Network Diversity Metrics

Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric Simulation Conclusion 10 Bio-Diversity and Richness of Species A rich literature exists on biodiversity Both theoretical studies and experiments confirm a positive relationship between biodiversity and the ecosystems resistance to invasion and diseases

Many lessons may be borrowed, but we focus on metric functions and how they are applied Richness of species The number of different species in an ecosystem Problem: It ignores the relative abundance of each species 11 Effective Richness of Resources Effective number1 Shannon-Wiener index (Shannon entropy using natural logarithm) groups systems with same

levels of diversity The effective number, the exponential of this index, measures the number of equally-common species, even if in reality all species are not equally common. We define the effective richness of resources as: (pi is the relative frequency of resource i) 1 Problem: Assuming all resources are equally M.O. Hill. Diversity and evenness: a unifying notation and its consequences. Ecology, 54(2):427432, 12

Similarity-Sensitive Effective Richness Similarity-Sensitive Richness1 Given a resource similarity function z(.): [1;m] [1;m] [0; 1] (with z(i,i) = 1), we define the effective richness of resources as: ( ) We can simply talk about the number of distinct resource types from now on, as if all resources are equally common and equally different

T. Leinster and C.A Cobbold. Measuring diversity: the importance of species similarity. Ecology, 93(3):477489, 2012. 1 13 Outline Introduction Network Diversity Metrics Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric Simulation Conclusion

14 From Food Web to Resource Graph The second lesson from biodiversity The effect of biodiversity on stability of an ecosystem critically depends on the interaction of different species inside a food web1 For food web, it is the feeding relationship (e.g.,

disease in one species affect those who feed on it) For networks, it is the causal relationships (e.g., hacking one service may lead to accesses to others) Resource graph Syntactically equivalent to attack graph Models causal relationships between network resources (instead of known vulnerabilities) K.S. McCann. The diversity-stability debate. Nature, 405:228233, 2000. 1 15 Resource Graph

Vertices: zero day exploits of resources, their pre- and postconditions Edges: AND between preconditions, OR between exploits On which path should we apply the diversity metric function (i.e., the number of distinct resource types)? 16 Selecting the Right Path(s)

Intuitively, it should be the shortest path 1 or 2, minimum # of steps? But 4 may take less effort than 1! 2 or 4, minimum # of resources? But they both have 2 resources, so which one to choose, 2 or 4? 4, minimizing (#steps/#of resources)? But what if theres a path with 9 steps and 3 resources? 1/3<2/4, but it clearly does not represent the least attack effort! 17 Network Diversity in Least Attack Effort We define network diversity as:

(minimum # of resources on any path)/(minimum # of steps on any path) Note: These may or may not be the same path! e.g., in this case: = 2 (path 2, 4) / 3 (path 1, 2) The numerator 2 denotes the networks current level of diversity and the denominator 3 maximum potential (# of resources can never be greater than # of steps) 18 Complexity and Heuristic Algorithm Determining the network diversity is NPhard Heuristic algorithm Only keep a limited number of local optima

at each step 19 Outline Introduction Network Diversity Metrics Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric Simulation Conclusion 20

Network Diversity in Average Effort The least attacking effort-based metric only provides a partial picture of the threat We now define a probabilistic network diversity metric based on the average attacking effort Informally, as p /p , where 1 2 p1 is the probability an attacker can compromise the given asset now, and p the probability he/she can still compromise it 2 if all the resources were to be made different (i.e., every resource type would appear at most once)

21 An Example Number in smaller font: probability of an exploit given all pre-conditions are true Number in larger font: probability of reaching this node

Dotted lines/ underlined numbers: given probabilities of reusing an exploit Network diversity = 0.007/0.0103 22 Outline Introduction Network Diversity Metrics Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric

Simulation Conclusion 23 Simulation Results Accuracy/performance of the heuristic algorithm 24 Simulation Results Contd Comparison of the metrics 25

Outline Introduction Network Diversity Metrics Biodiversity-Inspired Metric Least Attacking Effort-Based Metric Probabilistic Metric Simulation Conclusion 26 Conclusion

We have takenkabased first step towards modeling can unfold on the model network diversity, by proposing a biodiversity-inspired metric a least attacking effort-based metric a probabilistic metric Limitations and future work

Depending on the availability and accuracy of inputs, e.g., resources, their relationships, and similarity Simulations are based on random inputs Not considering the cost and impact of diversity Not considering the likelihood of attacks on resources Future work will also apply other biodiversity 27 Q&A Thank You!

Contact Author: Lingyu Wang ([email protected]) 28