A Game Theoretic Framework for Evaluating Resilience of Networks Against Attacks Assane Gueye Information Technology Laboratory, National Institute of Standards and Technology Applied and Computational Mathematics Division Seminar Series National Institute of Standards and Technology Gaithersburg, April 16, 2013 Joint work with: Dr. Vladimir Marbukh (NIST) Aron Lazska (Budapest University of Technology and Economics) Prof. Jean C. Walrand, Prof. Venkat Anantharam (UC Berkeley) of 33 Motivations Additional link Network Attacker Operator SSI* SSI

1. How robust/vulnerable is the network against such attacks? Communication Power Grid 2. What are the links that are most likely to be attacked? Financial Transportation Social 3. Where to put additional link? 4. 2 of 33 s Talk: A game-theoretic framework to answer to these questions Framework Communication model Network Topology Network value model + Vulnerability metric Critical subsets of links

2-Player Game Payoffs definition Nash equilibrium characterization 3 of 33 Summary/Outline Goals: Quantifying network vulnerability, identify most critical links Solution: Game Theory to capture strategic nature, equilibrium payoff for vulnerability metric Communication models Network value models, Cost of loss of connectivity (Loss-in-Value) Game Model Nash equilibrium characterization, Vulnerability metric Properties of vulnerability metric Identification of critical links, Relate to known graph theory notions Quantification of security cost/benefit tradeoff? Budget constraint Economics of vulnerability reduction Hardening vs Redundancy 4 of 33

Communication Models Examples 5 of 33 Examples (1/4) All-to-One Networks (e.g., Sensor Network) S There is a designated node (the gateway) to which everyone wants to connect S Communication infrastructure (Rooted) spanning arborescence Network Value Function (proxy) f(G) := # of nodes (connected to S) S Cost of loss of connectivity: |V|-|VS| VS connected component containing S LOST

A. Gueye, A. Laszka, J.C. Walrand, V. Anantharam: A Polyhedral-Based Analysis of Nash Equilibria of Quasi-Zero-Sum Games and its Applications to6 of 33 Communication Network Security. Submitted to ACM TEAC, 2012 Examples (2/4) Many-to-Many Networks (e.g., Supply-Demand) A total amount of goods () is to be moved) is to be moved from a set of sources to a set of destinations S1 D1 D2 S2 D3 Communication infrastructure Feasible flow (capacity constraints, conservation of flows) S1 3 S2 2

1 2 1 1 1 3 D1 1 D2 3 1 D3 1 Network Value Function f(G) := total amount of goods moved from S to D Cost of loss of connectivity: ) is to be moved(T)- ) is to be moved(T\e) ) is to be moved(X) := amount of goods moved over X) := amount of goods moved over X) := amount of goods moved over X S1 D1 D2 S2

D3 LOST D2+D3-S2 (>0) A. Gueye, V. Marbukh, A. Laszka, J.C. Walrand, V. Anantharam: A Polyhedral-Based Analysis of Nash Equilibria of Quasi-Zero-Sum Games and its Applications 7 of 33 to Communication Network Security. Submitted to ACM TEAC, 2012 Examples (3/4) All-to-All Networks (e.g., Bridged Ethernetconstant loss) Need a path between any pair of nodes (All nodes must be connected at all time) Communication infrastructure Spanning tree Network Value Function f(G) := K (constant) Cost of loss of connectivity: K (1-1connected)

LOST 1connected: indicator function A. Gueye, V. Marbukh, A. Laszka, J.C. Walrand, V. Anantharam: A Polyhedral-Based Analysis of Nash Equilibria of Quasi-Zero-Sum Games and its Applications 8 of 33 t Communication Network Security. Submitted to ACM TEAC, 2012 Examples (4/4) All-to-All Networks (e.g., Bridged Ethernetlinear loss) Need a path between any two nodes (when nodes are disconnected, the decision reached by the maximum number of nodes prevails) Communication infrastructure Spanning tree Network Value Function f(G) := # of connected nodes (in largest cluster) Cost of loss of connectivity: |V|-max(|Vi|)

LOST max(|Vi|) = # nodes in largest connected component A. Gueye, V. Marbukh, A. Laszka, J.C. Walrand, V. Anantharam, : A Polyhedral-Based Analysis of Nash Equilibria of Quasi-Zero-Sum Games and its Applications 9 of 33 Communication Network Security. Submitted to ACM TEAC, 2012 Alternate Network Value Models Sarnoff: n (Broadcast Network) Graph G=(V,E) |V|=n, |E|=m Metcalfe: n2 (Peer Connecting Network) Walrand: n1+a a1 (friendship network) Reed: 2n (Group Forming network) Odlyzky, Briscoe, Tilly (OBT): nlog(n)

A. Gueye, V. Marbukh, J.C. Walrand: Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach, In 3rd International ICST Conference on Game Theory for Networks (GameNets), May 25-26, 2012, Vancouver, Canada 10 of 33 Loss-in-Value (LiV) Network operators goal choose a set of links to maintain some connectivity Denote T: set of links Example 1: Sensor Network S S T: a (rooted) spanning arborescence and get some value: f(T) (=|V|) When link e fails (New) network T\e, with value f(T\e) Loss-in-Value (LiV) relative to T and e = f(T)- f(T\e)

11 of 33 Loss-in-Value (LiV) Sensor Network S S Supply-Demand S1 D1 D2 S2 D3 S1 3 S2 2 S Lost S1

3 S2 2 1 2 1 1 1 2 1 1 1 3 D1 1 D2 3 1 D3 1 Ethernet: (constant loss) Ethernet

(linear loss) 1 D1 1 3LostD 3 2 1 Lost Lost D3 1 =3 =3 # of nodes disconnected from S (when connection is over T and e fails) amount of goods that T carries over e = Kx1eT

total network value ( if e T) =3 size of smallest connected component (when connection is over 12 of 33 T and e fails) Loss-in-Value (LiV) Matrix Build Loss-in-Value matrix: LiV[E,T] Resources links LiV[T,e] Payoff matrix 13 of 33 Game Model SSI 14 of 33 Network Blocking Game Model

Graph G=(V,E) Players (Network) Manager Attacker (Pure) Strategies: Manager: resources (TT) Attacker: links (eE) Payoff Manager: Attacker: (e) (possible attack cost) 15 of 33 Network Blocking Game Model Game One shot game (Mixed) Strategies Defender: on T, to minimize ( , )= ( ,)

SSI Attacker: on E, to maximize ( , )= ( ,)() ( ) 16 of 33 Vulnerability Metric Nash equilibrium always exists [Nash 1950] Expected Loss (defender): ( , )= ( ,)

Vulnerability metric ( = attackers expected reward) () = Theorem[Gueye et. al., 2012] is uniquely defined (there might exist multiple equilibria) If , Attackers best choice is to never launch an attack Defender will randomize communication (e.g., multipath routing) If ,

There exists a critical subset of links (possibly multiple) Attacker will target a critical subset of links Defender will randomize and minimally use critical links 17 of 33 Vulnerability Metric: Properties is uniquely defined reflects defenders loss as well as attackers desire to attack closely depends on network structure (topology, amount of goods to be moved, etc) metric for vulnerability to attack (strategic failures reliability metric which is based on random failure)

indicates attackers behavior If <0 attacker does not attack If 0 attacker always attack 18 of 33 Vulnerability Metric & Graph Theory SSI SSI 19 of 33 Vulnerability Metric & Graph Theory (1/4) All-to-One Networks (e.g., Sensor Network) Game Operator: choose a rooted spanning arborescence Attacker: Attack a link = # of nodes disconnected from S associated with T and e Vulnerability Metric (= Average # of disconnected nodes per attacked link)

() = : ( ) | | S { } (Inverse) Directed Strength of Graph (Cunningham 1982) by removing links in E S =2 =4 Critical subset of links: E* achieves Uniform attack in each critical subset 20 of 33

Vulnerability Metric & Graph Theory (2/4) Many-to-Many Networks (e.g., Supply-Demand) Game Operator: choose a feasible flow Attacker: Attack a link = amount of goods T carries over e S1 D1 D2 S2 D3 Vulnerability Metric (= Average excess demand per attacked link)

= X) := amount of goods moved over X ( ) = = total demand in = Total supply in = excess demand in Critical subset of links: E* achieves Uniform attack in each critical subset 21 of 33 Vulnerability Metric & Graph Theory (3/4) All-to-All Networks (e.g., Bridged Ethernetconstant loss) Game Operator: choose a spanning tree

Attacker: Attack a link = total value ( if e T) Vulnerability Metric (= Average # of (dis)connected components per attacked link) = Spanning Tree Packing Number (SPT) (Tutte & Nash-Williams 1961) E = Set of edges going across the partitions = number of connected components Critical subset of links: E* achieves Uniform attack in each critical subset 22 of 33 Vulnerability Metric & Graph Theory (4/4) All-to-All Networks (e.g., Bridged Ethernetlinear loss) Game

Operator: choose a spanning tree Attacker: Attack a link = size of smallest connected component Vulnerability Metric (=Average # of disconnected nodes per links) = X) := amount of goods moved over X ( ) (inverse) Cheegers constant, Edge expansion factor of G nfinite number of graphs =

Critical subset of links: E* achieves Uniform attack in each critical subset 23 of 33 Vulnerability Metric & Critical Links All-2-All (constant loss) zero attack cost e=0 1/2 a) 1/2 Vulnerability = 1/2 1/7 b) 1/7 1/7 1/7 1/7 1/7 1/7

= 4/7>1/2 24 of 33 Vulnerability Metric & Critical Links Critical Subsets depends on network value model (f(.)) All-2-All (constant loss) Bridges All-2-All (linear loss) Edges in the cloud All-2-All (exponential loss) Edges to the cloud Criticality depends on network topology Bridges Edges to the cloud 25 of 33

Vulnerability Metric & Network Design Network Design Additional link = 3/4 Network in b) is more vulnerable than network in c) = 2/3 a) = 3/5 b) c) 2/3 > 3/5 26 of 33 Vulnerability/Risk Security Limits Vulnerability/Cost Tradeoff ? Cost

27 of 33 Vulnerability/Cost Tradeoff Each subset of resources T (e.g., feasible flow, spanning tree) has a cost w(T) Defender has a maximum budget b Can use only resources that satisfy budget constraint bw(T) Set of pure strategies ={ ( ) } () 4.5 4 (Buying out more randomness) Vulnerability metric is a function of b: Study function Vulnerability Define games parameterized by budget b * 3.5

3 2.5 2 1.5 1 4 6 8 10 12 (Maximum) Flow Cost 14 16 18 Cost b

A. Gueye, V. Marbukh: A Game Theoretic Framework for Network Security Vulnerability Assessment and Mitigation, In 3rd International ICST Conference on Decision and Game Theory (GameSec), November 5-6, 2012, Budapest, Hungary 28 of 33 Vulnerability Reduction Hardening vs Redundancy (ongoing) Operator Attacker Additional budget! Hardening Redundancy 29 of 33 Vulnerability Reduction Redundancy vs Hardening (ongoing) Relevant parameters:

Network topology Current set of available routes Benefit function Cost of attack Budget Run1 (fixed) (random for each run) (linear for hardening) (random for each run) (varies) Run2 Run3 A. Gueye, V. Marbukh: Economics of Network Vulnerability Reduction: Hardening versus Redundancy, submitted, In Joint Workshop on Pricing 30 of 33 and Incentives in Networks and Systems, June 21, 2013, in conjunction with ACM SIGMETRICS 2013 (Pittsburg, PA, USA) Summary Network Blocking Games Communication model Network value function, Loss-in-Value (LiV) NE theorem for blocking games Application: Quantify network vulnerability in adversarial environment Vulnerability Metric Critical subset of links

Properties Algorithms Security/Cost Tradeoff Budget constraints Tradeoff curves Computational complexity Conclusion .the ability of a malicious/selfish agent to acquire and exploit system information may alter conclusions drawn by using conventional 31 of 33 Future Work Fundamentals of adversarial relationship E.g. Game Theory Security as a design principle E.g.: System Design Predictive metrics for security of large-scale systems 1. Models for local Interaction

E.g.: Game Theory, Decision Theory 2. Identify macro parameters Predict global behavior Global level of security E.g.: Complex System Theory Statistical Inference 3. Develop appropriate feedback control loops E.g.: Control Theory 32 of 33 Thank You! Questions? 33 of 33