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.
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