Optimization Online


Risk-Averse Bi-Level Stochastic Network Interdiction Model for Cyber-Security Risk Management

Tanveer Hossain Bhuiyan(tbhuiyan***at***vols.utk.edu)
Hugh Medal(hmedal***at***utk.edu)
Apurba Nandi(apurbana***at***gmail.com)
Mahantesh Halappanavar(Mahantesh.Halappanavar***at***pnnl.gov)

Abstract: Security of cyber networks is crucial; recent severe cyber-attacks have had a devastating effect on many large organizations. The attack graph, which maps the potential attack paths of a cyber network, is a popular tool for analyzing cyber system vulnerability. In this study, we propose a bi-level stochastic network interdiction model on an attack graph to enable a risk-averse, resource constrained cyber network defender to optimally deploy security countermeasures that protect against attackers with an uncertain budget. This risk- averse conditional-value-at-risk (CVaR) model minimizes a weighted sum of the expected maximum loss over all scenarios and the expected maximum loss from the most damaging attack scenarios. We develop a customized constraint and column generation algorithm to solve our model as well as several acceleration techniques to improve the computational efficiency. Numerical experiments demonstrate that the acceleration techniques enable the solution of relatively large problems within a reasonable amount of time: applying all the acceleration techniques also reduces the average computation time of the basic algorithm by 71% for 100-node graphs. Using metrics called mean-risk value of stochastic solution and value of risk-aversion, computational results suggest that our stochastic risk-averse model significantly outperforms deterministic and risk-neutral models when 1) the distribution of attacker budget is heavy-right-tailed and 2) the defender is highly risk-averse.

Keywords: Attack graph, Stackelberg game, mixed-integer programming, conditional-value- at-risk, cyber-security

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Stochastic Programming

Category 3: Network Optimization

Citation: Bhuiyan, T. H., Medal, H., Nandi, A., Halappanavar, M. (2019). Risk-Averse Bi-Level Stochastic Network Interdiction Model for Cyber-Security Risk Management. University of Tennessee-Knoxville

Download: [PDF]

Entry Submitted: 05/30/2019
Entry Accepted: 05/30/2019
Entry Last Modified: 05/30/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society