Abstract
The processing and storage of critical data in large-scale cloud networks necessitate the need for scalable security solutions. It has been shown that deploying all possible detection measures incur a cost on performance by using up valuable computing and networking resources, thereby resulting in Service Level Agreement (SLA) violations promised to the cloud-service users. Thus, there has been a recent interest in developing Moving Target Defense (MTD) mechanisms that helps to optimize the joint objective of maximizing security while ensuring that the impact on performance is minimized. Often, these techniques model the challenge of multi-stage attacks by stealthy adversaries as a single-step attack detection game and use graph connectivity measures as a heuristic to measure performance, thereby (1) losing out on valuable information that is inherently present in multi-stage models designed for large cloud networks, and (2) come up with strategies that have asymmetric impacts on performance, thereby heavily affecting the Quality of Service (QoS) for some cloud users. In this work, we use the attack graph of a cloud network to formulate a general-sum Markov Game and use the Common Vulnerability Scoring System (CVSS) to come up with meaningful utility values in each state of the game. We then show that, for the threat model in which an adversary has knowledge of a defender’s strategy, the use of Stackelberg equilibrium can provide an optimal strategy for placement of security resources. In cases where this assumption turns out to be too strong, we show that the Stackelberg equilibrium turns out to be a Nash equilibrium of the general-sum Markov Game. We compare the gains obtained using our method(s) to other baseline techniques used in cloud network security. Finally, we highlight how the method was used in a real-world small-scale cloud system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Partial observability over the state space can increase the number of states to be a power-set of this number, i.e. \(2^{(\#\text { servers} \times \# \text { access-levels})}\).
- 2.
- 3.
This is a strong reason to move away from the zero-sum reward modeling in [5].
- 4.
In the case of multiple attackers, SSE \(\not \in \) NE. Although such scenarios exist in cybersecurity settings, we consider a single attacker in this modeling and plan to consider the multiple attacker setting in the future.
References
National vulnerability database. https://nvd.nist.gov. Accessed 25 Sept 2018
Basak, A., et al.: An initial study of targeted personality models in the flipit game. In: Bushnell, L., Poovendran, R., Başar, T. (eds.) GameSec 2018. LNCS, vol. 11199, pp. 623–636. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01554-1_36
Chowdhary, A., Dixit, V.H., Tiwari, N., Kyung, S., Huang, D., Ahn, G.J.: Science DMZ: SDN based secured cloud testbed. In: IEEE Conference on Network Function Virtualization and Software Defined Networks (2017)
Chowdhary, A., Pisharody, S., Huang, D.: SDN based scalable MTD solution in cloud network. In: ACM Workshop on Moving Target Defense (2016)
Chowdhary, A., Sengupta, S., Huang, D., Kambhampati, S.: Markov game modeling of moving target defense for strategic detection of threats in cloud networks. In: AAAI Workshop on Artificial Intelligence for Cyber Security (2019)
Chung, C.J., Khatkar, P., Xing, T., Lee, J., Huang, D.: NICE: network intrusion detection and countermeasure selection in virtual network systems. IEEE Trans. Dependable Secure Comput. 10(4), 198–211 (2013)
Western Regional Collegiate Cyber Defense Competition: WRCCDC (2018). https://archive.wrccdc.org/images/2018/
Nagios Enterprises: Nagios (2015)
Guerrero, D., Carsteanu, A.A., Huerta, R., Clempner, J.B.: An iterative method for solving Stackelberg security games: a Markov games approach. In: 2017 14th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE), pp. 1–6. IEEE (2017)
Houmb, S.H., Franqueira, V.N., Engum, E.A.: Quantifying security risk level from cvss estimates of frequency and impact. JSS 83(9), 1622–1634 (2010)
Jajodia, S., Park, N., Serra, E., Subrahmanian, V.: SHARE: a Stackelberg honey-based adversarial reasoning engine. ACM Trans. Internet Technol. (TOIT) 18, 30 (2018)
Jha, S., Sheyner, O., Wing, J.: Two formal analyses of attack graphs. In: 2002 Proceedings of the 15th IEEE Computer Security Foundations Workshop, pp. 49–63. IEEE (2002)
Jia, Q., Sun, K., Stavrou, A.: MOTAG: moving target defense against internet denial of service attacks. In: 2013 22nd International Conference on Computer Communication and Networks, pp. 1–9. IEEE (2013)
Kampanakis, P., Perros, H., Beyene, T.: SDN-based solutions for moving target defense network protection. In: IEEE 15th International Symposium on a World of Wireless, Mobile and Multimedia Networks. IEEE (2014)
Korzhyk, D., Conitzer, V., Parr, R.: Complexity of computing optimal Stackelberg strategies in security resource allocation games. In: AAAI (2010)
Korzhyk, D., Yin, Z., Kiekintveld, C., Conitzer, V., Tambe, M.: Stackelberg vs. nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness. J. Artif. Int. Res. 41(2), 297–327 (2011). http://dl.acm.org/citation.cfm?id=2051237.2051246
Korzhyk, D., Yin, Z., Kiekintveld, C., Conitzer, V., Tambe, M.: Stackelberg vs. nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness. J. Artif. Intell. Res. 41, 297–327 (2011)
Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: Eleventh International Conference on Machine Learning (1994)
Lye, K.W., Wing, J.M.: Game strategies in network security. Int. J. Inf. Secur. 4, 71–86 (2005)
McCumber, J.: Information systems security: a comprehensive model. In: Proceedings of the 14th National Computer Security Conference (1991)
Miehling, E., Rasouli, M., Teneketzis, D.: Optimal defense policies for partially observable spreading processes on Bayesian attack graphs. In: Proceedings of the Second ACM Workshop on Moving Target Defense, pp. 67–76. ACM (2015)
Nguyen, T.H., Wright, M., Wellman, M.P., Singh, S.: Multistage attack graph security games: heuristic strategies, with empirical game-theoretic analysis. In: Security and Communication Networks 2018 (2018)
Paruchuri, P., Pearce, J.P., Marecki, J., Tambe, M., Ordonez, F., Kraus, S.: Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games. In: AAMAS 2008, pp. 895–902 (2008)
Paruchuri, P., Pearce, J.P., Marecki, J., Tambe, M., Ordonez, F., Kraus, S.: Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games. In: AAMAS (2008)
Peng, W., Li, F., Huang, C.T., Zou, X.: A moving-target defense strategy for cloud-based services with heterogeneous and dynamic attack surfaces. In: IEEE International Conference on Communications (ICC) (2014)
Schlenker, A., et al.: Deceiving cyber adversaries: a game theoretic approach. In: Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, pp. 892–900. International Foundation for Autonomous Agents and Multiagent Systems (2018)
Sengupta, S., Chakraborti, T., Kambhampati, S.: MTDeep: boosting the security of deep neural nets against adversarial attacks with moving target defense. In: Workshop on Engineering Dependable and Secure Machine Learning Systems. AAAI (2018)
Sengupta, S., Chowdhary, A., Huang, D., Kambhampati, S.: Moving target defense for the placement of intrusion detection systems in the cloud. In: Bushnell, L., Poovendran, R., Başar, T. (eds.) GameSec 2018. LNCS, vol. 11199, pp. 326–345. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01554-1_19
Sengupta, S., et al.: A game theoretic approach to strategy generation for moving target defense in web applications. In: AAMAS (2017)
Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci. 39(10), 1095–1100 (1953)
Sinha, A., Nguyen, T.H., Kar, D., Brown, M., Tambe, M., Jiang, A.X.: From physical security to cybersecurity. J. Cybersecur. 1(1), 19–35 (2015)
Venkatesan, S., Albanese, M., Cybenko, G., Jajodia, S.: A moving target defense approach to disrupting stealthy botnets. In: Proceedings of the 2016 ACM Workshop on Moving Target Defense, pp. 37–46. ACM (2016)
Vorobeychik, Y., Singh, S.: Computing Stackelberg equilibria in discounted stochastic games (corrected version) (2012)
Zhuang, R., DeLoach, S.A., Ou, X.: Towards a theory of moving target defense. In: ACM MTD Workshop, 2014, pp. 31–40. ACM (2014)
Zhuang, R., Zhang, S., Bardas, A., DeLoach, S.A., Ou, X., Singhal, A.: Investigating the application of moving target defenses to network security. In: 6th International Symposium on Resilient Control Systems (ISRCS). IEEE (2013)
Acknowledgment
We want to thank the reviewers for their comments. This research is supported in part by these research grants: Naval Research Lab N00173-15-G017, AFOSR grant FA9550-18-1-0067, the NASA grant NNX17AD06G, ONR grants N00014-16-1-2892, N00014-18-1-2442, N00014-18-12840, NSF—US DGE-1723440, OAC-1642031, SaTC-1528099, 1723440 and NSF—China 61628201 and 61571375. The first author is also supported by an IBM Ph.D. Fellowship.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Sengupta, S., Chowdhary, A., Huang, D., Kambhampati, S. (2019). General Sum Markov Games for Strategic Detection of Advanced Persistent Threats Using Moving Target Defense in Cloud Networks. In: Alpcan, T., Vorobeychik, Y., Baras, J., Dán, G. (eds) Decision and Game Theory for Security. GameSec 2019. Lecture Notes in Computer Science(), vol 11836. Springer, Cham. https://doi.org/10.1007/978-3-030-32430-8_29
Download citation
DOI: https://doi.org/10.1007/978-3-030-32430-8_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-32429-2
Online ISBN: 978-3-030-32430-8
eBook Packages: Computer ScienceComputer Science (R0)