Optimal defense strategies against intelligent cyber attacks

Abstract

We propose a comprehensive game-theoretic model pertaining to the security of computer networks, specifically addressing the interaction between defenders and attackers. The model incorporates attack graphs to outline potential attacker strategies and defender responses. To account for the attacker's capacity to execute multiple attempts, we introduce a probabilistic element, wherein the success or failure at any arc of the attack graph is treated as stochastic. This characterization gives rise to a multi-stage stochastic network-interdiction problem. In this problem formulation, the defender strategically interdicts a set of arcs in anticipation of the likely actions of the attacker, who, in turn, can make multiple attempts to traverse the network. We mathematically articulate this scenario as a stochastic bilevel mixed-integer program with a "min-max" objective. The defender's aim is to minimize the probability of the attacker's success, while the attacker seeks to maximize the probability of successfully traversing the network across multiple attempts. The defender's stochastic bilevel optimization model is solved using the integer L-shaped method. Upon analyzing the defender's perspective, we observe the anticipated trend that the overall success probability of the attacker diminishes with an increasing level of defense. Notably, in the sensitivity analysis involving relatively small attack graphs, we discover that the optimal defense strategy against a myopic attacker often aligns with that against a non-myopic attacker. Furthermore, in instances where deviations exist, the disparity in performance is generally marginal. However, our findings demonstrate a potential divergence in optimal defense strategies when the available attack paths share numerous common arcs.

Keywords

• cybersecurity
• stochastic programming
• defender attacker model
• bilevel optimization
• network interdiction
• integer l-shaped method

Akıllı siber saldırılara karşı optimal savunma stratejileri

Abstract

Bilgisayar ağlarının güvenliği ile ilgili olarak, savunucular ve saldırganlar arasındaki etkileşimi özellikle ele alan kapsamlı bir oyun teorisi modeli öneriyoruz. Model, potansiyel saldırgan stratejilerini ve savunucu tepkilerini belirlemek için saldırı grafiklerini içermektedir. Saldırganın birden çok girişimi gerçekleştirme kapasitesini hesaba katmak için başarılı veya başarısız olma olasılığını herhangi bir saldırı grafiği yayında stokastik olarak ele alan bir olasılıksal öğe tanıtıyoruz. Bu karakterizasyon, çok aşamalı stokastik bir ağ-kesme problemine yol açmaktadır. Bu problem formulasyonunda, savunucu, saldırganın muhtemel eylemlerini önceden tahmin ederek bir dizi yayı engellemektedir. Ardından, saldırgan, ağı geçmeye yönelik birden çok girişimde bulunabilir. Bu senaryoyu matematiksel olarak, bir "min-max" hedefi olan stokastik bir iki seviyeli karma tamsayılı program olarak ifade ediyoruz. Savunucunun amacı, saldırganın başarısızlık olasılığını en aza indirmek iken, saldırgan, ağı birden çok girişimde başarıyla geçme olasılığını maksimize etmeye çalışmaktadır. Savunucunun stokastik iki seviyeli optimizasyon modeli, tamsayılı L-şekilli yöntem kullanılarak çözülmektedir. Savunucunun bakış açısını analiz ettiğimizde, saldırganın genel başarı olasılığının savunma seviyesinin artmasıyla azaldığı beklenen eğilimi gözlemliyoruz. Özellikle, göreceli olarak küçük saldırı grafiklerini içeren hassasiyet analizimizde, bir kör noktalı saldırgana karşı optimal savunma stratejisinin genellikle bir kör noktalı olmayan saldırgana karşı olanla uyumlu olduğunu keşfediyoruz. Ayrıca, sapmaların var olduğu durumlarda, performanstaki fark genellikle marjinaldir. Ancak, bulgularımız, mevcut saldırı yollarının birçok ortak yayı paylaştığı durumlarda optimal savunma stratejilerinde potansiyel bir ayrışma olduğunu göstermektedir.

Keywords

• siber güvenlik
• stokastik programlama
• savunmacı saldırgan modeli
• iki seviyeli eniyileme
• ağ kesme
• tamsayılı L-şekli metodu

References

1. Cybersecurity & Infrastructure Security Agency (CISA). (2022). "Annual Cybersecurity Report." https://www.cisa.gov/publications-library. Accessed 7 November 2023.
2. Schneier B (2000) Secrets & Lies: Digital Security in a Networked World. 2nd ed. Wiley.
3. Carin L, Cybenko G, Hughes J (2008) Cybersecurity strategies: The queries methodology. IEEE Computer 41(8) 20–26.
4. Bier VM, Cox LA Jr., Azaiez MN (2009) Chap. 1: Why both game theory and reliability theory are important in defending infrasutructure against intelligent attacks. In Bier VM and Azaiez MN (ed) Game Theoretic Risk Analysis of Security Threats. Springer, 1–11.
5. Sheyner, O, Haines J, Jha S, Lippmann R, Wing JM (2002) Automated generation and analysis of attack graphs. Proceedings of the IEEE Symposium on Security and Privacy. IEEE, 273–284.
6. Lippmann RP, Ingols KW (2005) An annotated review of past papers on attack graphs. Tech. Rep. No. PR-IA-1, MIT Lincoln Lab, Lexington, MA.
7. Liu P, Zang W, Yu M (2005) Incentive-based modeling and inference of attacker intent, objectives, and strategies. ACM Transactions on Information and System Security (TISSEC) 8(1) 78–118.
8. Lye K, Wing JM (2005) Game strategies in network security. International Journal of Information Security 4(1) 71–86.

9. Xiaolin C, Xiaobin T, Yong Z, Hongsheng X (2008) A Markov game theory-based risk assessment model for network information system. International Conference on Computer Science and Software Engineering, vol. 3. IEEE, 1057–1061.
10. Nguyen KC, Alpcan T, Basar T (2009) Stochastic games for security in networks with interdependent nodes. International Conference on Game Theory for Networks, IEEE, 697–703.
11. McMasters AW, Mustin TM (1970) Optimal interdiction of a supply network. Naval Research Logistics Quarterly 17(3) 261–268.
12. Steinrauf, RL (1991) Network interdiction models. Master’s thesis, Naval Postgraduate School, Monterey, CA.
13. Phillips CA (1992) The network destruction problem. Tech. Rep. No. SAND-92-0186C, Sandia National Labs., Albuquerque, NM.
14. Wood RK (1993) Deterministic network interdiction. Mathematical and Computer Modelling 17(2) 1–18.
15. Fulkerson DR, Harding GC (1977) Maximizing the minimum source-sink path subject to a budget constraint. Mathematical Programming 13(1) 116–118.
16. Golden B (1978) A problem in network interdiction. Naval Research Logistics Quarterly 25(4) 711–713. [17] Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Operations Research 46(2) 184–197.
17. Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2) 97–111.
18. Bayrak H, Bailey MD (2008) Shortest path network interdiction with asymmetric information. Networks 52(3) 133–140.
19. Pan F, Morton DP (2008) Minimizing a stochastic maximum-reliability path. Networks 52(3) 111–119.
20. Dimitrov NB, Morton DP (2013) Interdiction models and applications. Handbook of Operations Research for Homeland Security, Herrmann, J.W., Editor. Springer, 73–103.
21. Morton DP (2011) Stochastic network interdiction. Wiley Encyclopedia of Operations Research and Management Science, Cochran, J. J., Editor. John Wiley & Sons, Inc.
22. Cormican KJ (1995) Computational methods for deterministic and stochastic network interdiction problems. Master’s thesis, Naval Postgraduate School, Monterey, CA.
23. Held H, Hemmecke R, Woodruff DL (2005) A decomposition algorithm applied to planning the interdiction of stochastic networks. Naval Research Logistics 52(4) 321–328.
24. Kall P, Wallace S (1994) Stochastic Programming. Wiley.
25. Janjarassuk U, Linderoth J (2008) Reformulation and sampling to solve a stochastic network interdiction problem. Networks 52(3) 120–132.
26. Van S, Richard M, Wets R (1969) L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics 17(4) 638–663.
27. Shapiro A (2003) Monte Carlo sampling methods. Handbook in Operations Research and Management Science, Shapiro, A. and Ruszczynski, A., editors., North-Holland, Amsterdam, 2003 10 353–425.
28. Verweij B, Ahmed S, Kleywegt AJ, Nemhauser G, Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: A computational study. Computational Optimization and Applications 24(2) 289–333.
29. Santoso T, Ahmed S, Goetschalckx M, Shapiro A (2005) A stochastic programming approach for supply chain network design under uncertainty. European Journal of Operational Research 167(1) 96–115.
30. Ahmed S, Shapiro A, Shapiro E (2002) The sample average approximation method for stochastic programs with integer recourse. Preprint is available at www.optimization-online.org.
31. Linderoth J, Shapiro A, Wright S (2006) The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research 142(1) 215–241.
32. Shapiro A, Xu H (2008) Stochastic mathematical programs with equilibrium constraints, modelling, and sample average approximation. Optimization 57(3) 395–418.
33. Ertem M, Bier VM (2021) A Stochastic Network-Interdiction Model for Cyber Security. 5th International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), Ankara, Turkey, 2021, pp. 171-176, DOI: 10.1109/ISMSIT52890.2021.9604681.
34. Gumus ZH, Floudas CA (2005) Global optimization of mixed integer bilevel programming problems. Computational Management Science 2(3) 181–212.
35. Bertsimas DJ, Jaillet P, Odoni AR (1990) A priori optimization. Operations Research 38(6) 1019–1033.
36. Lageweg BJ, Lenstra JK, Rinnooy Kan AHG, Stougie L (1985) Stochastic integer programming by dynamic programming. Statistica Neerlandica 39(2) 97–113.
37. Laporte G, Louveaux F, Mercure H (1992) The vehicle routing problem with stochastic travel times. Transportation Science 26(3) 161–170.
38. Psaraftis HN (1984) On the practical importance of asymptotic optimality in certain heuristic algorithms. Networks 14(4) 587–596.
39. Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters 13(3) 133–142.
40. Lippmann RP, Ingols KW, Scott C, Piwowarski K, Kratkiewicz KJ, Artz M, Cunningham RK (2005) Evaluating and strengthening enterprise network security using attack graphs. Tech. Rep. ESC-TR-2005-064, MIT Lincoln Laboratory, Lexington, MA.
41. Lippmann RP, Ingols KW, Scott C, Piwowarski K, Kratkiewicz KJ, Artz M, Cunningham RK (2006) Validating and restoring defense in depth using attack graphs. Military Communications Conference, MILCOM 2006. IEEE, 1–10.
42. Ou X, Govindavajhala S, Appel AW (2005) MulVal: A logic-based network security analyzer. 14th USENIX Security Symposium. 1–16.
43. Mell P, Scarfone K, Romanosky S (2006) Common vulnerability scoring system. Security & Privacy, IEEE 4(6) 85–89.
44. NIST (2013) National Vulnerability Database. URL http://nvd.nist.gov/. Accessed 7 November 2023.