Modeling Attacker-Defender Interaction as a Zero-Sum Stochastic Game

E.O. Ibidunmoye^, , B.K. Alese and O.S. Ogundele

Cite this paper:
E.O. Ibidunmoye, B.K. Alese and O.S. Ogundele. Modeling Attacker-Defender Interaction as a Zero-Sum Stochastic Game. Journal of Computer Sciences and Applications. 2013; 1(2):27-32. doi: 10.12691/jcsa-1-2-3

Abstract

Game-theoretic modeling of computer security views security attack scenarios as an optimization game comprising of multiple players notably the attackers and the defenders (system administrators). This paper first presents theoretically, a two-player zero-sum stochastic game model of the interaction between malicious users and network administrators and secondly introduces a hypothetical network of a typical scenario to show the applicability of our model within that scenario. State games are encoded using a binary scheme in order to properly capture components of the underlying network environment. Our solution involves reducing each state game into a min and max linear programming problems for both the defender and attacker respectively. Game costs, rewards and outcomes are modeled to closely match real world measurements. We propose the use of a combination of the pivotal algorithm and a custom stochastic algorithm to compute the optimal (best-response) strategies for the players at each state. We also describe how the results can be analyzed to show how the optimal strategies can be used by the network administrators to predict adversary's actions, determine vulnerable network assets and suggest optimal defense strategies.

Keywords:
security games strategies attackers defenders stochastic games game theory

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Figures

References:

[1]	Adetunmbi A.O. Falaki S.O., Adewale, O.S. and Alese, B.K. (2008) “Intrusion Detection based on rough Set and k- Nearest Neighbour”, International Journal of Computing and ICT Research, vol. 2 No. 1. pp. 60-66.
[2]	Adetunmbi A.O., Alese B.K., Ogundele O.S. and Falaki S.O. (2007) “A Data Mining Approach to Network Intrusion Detection”, Journal of Computer Science & its Applications, vol. 14 No. 2.pp 24-37.
[3]	Alpcan T. and Baser T (2010), “Network Security: A Decision and Game-Theoretic Approach”, 1st ed. Cambridge University Press.
[4]	Arome G. (2010) “Modelling of Internet Protocol Security Policies in a Networking Environment”. M.Tech. Thesis, Department of Computer Science, Federal University of Technology, Akure. Nigeria.
[5]	Assane Gueye "A Game Theoretical Approach to Communication Security" (2011), Electrical Engineering and Computer Sciences University of California at Berkeley. Technical Report No. UCB/EECS-2011-19.
[6]	Cavusoglu H., Raghunathan S., and Yue W.(2008), “Decision-Theoretic and Game-Theoretic Approaches to IT Security Investment" Journal of Management Information Systems, vol. 25, pp. 281 September.
[7]	Ferguson S. T. (2007) “Game Theory II – Two-Person Zero-Sum Games”.
[8]	Karin Sallhammar (2007) “Stochastic Models for Combined Security and Dependability Evaluation”. Ph.D. Thesis, Department of Telematics, FITME, Norwegian of Science and Technology. Trondheim, Norway.
[9]	Karin Sallhammar, Knapskog S. J. (2004) “Using Game Theory in Stochastic Models for Quantifying Security” In Proceedings of the 9th Nordic Workshop on Secure IT-systems (Nordsec 2004). Espoo, Finland.
[10]	Karin Sallhammar, Knapskog S. J. and Helvik B. E. (2005) “Using Stochastic Game Theory to Compute the Expected Behavior of Attackers”, In Proceedings of the 2005 International Symposium on Applications and the Internet (Saint 2005). Trento, Italy.
[11]	Khanna R. and Liu H.(2007), “Distributed and Control Theoretic Approach to Intrusion Detection" Proceedings of the 2007 International Conference on Wireless Communications and Mobile Computing, ser. IWCMC ’07. New York, NY, USA: ACM.
[12]	Lye Kong-wei, Jeanette Wing (2002) "Game Strategies In Network Security", Extended Abstract for FCS.
[13]	Roy S., Ellis C., Shiva S., Dasgupta D., Shandilya V. and Wu Q (2010). “A Survey of Game Theory as Applied to Network Security". Proc. of the 43rd HICSS, Hawaii.
[14]	Ryan Trost (2009) “Practical Intrusion Analysis: Prevention and Detection for the Twenty-First Century” Addison-Wesley Professional.
[15]	Schneier B. (1999), “Attack trees: Modeling security threats,” Dr. Dobb’s Journal, December.
[16]	Shapley L. S. (1953) “Stochastic Games”. Proceedings of the National Academy of Science USA, vol 39, pp. 1095-1100.
[17]	Steffan J. & Schumacher M. (2002) "Collaborative Attack Modeling" In proceeding of the Symposium on Applied Computing, Madrid, Spain.