Abstract
We study the use of deception in attack graph-based Stackelberg security games. In our setting, in addition to allocating defensive resources to protect important targets from attackers, the defender can strategically manipulate the attack graph through three main types of deceptive actions. We show that finding the optimal deception and defense strategy is at least NP-hard. We provide two techniques for efficiently solving this problem: a mixed-integer linear program for layered directed acyclic graphs (DAGs) and neural architecture search for general DAGs. We empirically demonstrate that using deception on attack graphs gives the defender a significant advantage, and the algorithms we develop scale gracefully to medium-sized problems.
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.
For space, we omit the full proof for hiding edges. We follow a similar construction.
References
Abdallah, M., Naghizadeh, P., Hota, A.R., Cason, T., Bagchi, S., Sundaram, S.: Behavioral and game-theoretic security investments in interdependent systems modeled by attack graphs. IEEE Trans. Control Netw. Syst. (2020)
Achleitner, S., La Porta, T., McDaniel, P., Sugrim, S., Krishnamurthy, S.V., Chadha, R.: Cyber deception: virtual networks to defend insider reconnaissance. In: International Workshop Managing Insider security Threats (2016)
Albanese, M., Battista, E., Jajodia, S.: A deception based approach for defeating OS and service fingerprinting. In: Conference on Communications and Network Security (CNS) (2015)
Albanese, M., Battista, E., Jajodia, S.: Deceiving attackers by creating a virtual attack surface. In: Cyber Deception (2016)
Almeshekah, M., Spafford, E.: Planning and integrating deception into computer security defenses. In: New Security Paradigms Workshop (2014)
Almeshekah, M., Spafford, E.: Cyber security deception. In: Cyber Deception (2016)
Ammann, P., Wijesekera, D., Kaushik, S.: Scalable, graph-based network vulnerability analysis. In: Conference on Computer and Communications Security (2002)
An, B., Ordóñez, F., Tambe, M., Shieh, E., Yang, R., Baldwin, C., et al.: A deployed quantal response-based patrol planning system for the US coast guard. Interfaces 43(5) (2013)
Anwar, A.H., Kamhoua, C., Leslie, N.: A game-theoretic framework for dynamic cyber deception in internet of battlefield things. In: International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (2019)
Anwar, A.H., Kamhoua, C., Leslie, N.: Honeypot allocation over attack graphs in cyber deception games. In: International Conference on Computing, Networking and Communications (2020)
Basak, A., Kamhoua, C., Venkatesan, S., Gutierrez, M., Anwar, A.H., Kiekintveld, C.: Identifying stealthy attackers in a game theoretic framework using deception. In: Alpcan, T., Vorobeychik, Y., Baras, J.S., Dán, G. (eds.) GameSec 2019. LNCS, vol. 11836, pp. 21–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32430-8_2
Bercovitch, M., Renford, M., Hasson, L., Shabtai, A., Rokach, L., Elovici, Y.: HoneyGen: an automated honeytokens generator. In: IEEE ISI (2011)
Blocki, J., Christin, N., Datta, A., Procaccia, A.D., Sinha, A.: Audit games. In: International Joint Conference on Artificial Intelligence (2013)
Bondi, E., Oh, H., Xu, H., Fang, F., Dilkina, B., Tambe, M.: Broken signals in security games: coordinating patrollers and sensors in the real world. In: International Conference on Autonomous Agents and MultiAgent Systems (2019)
Car and Driver: artist shows google maps’ control over our lives by creating a fake traffic jam (2020)
Cohen, F.: The use of deception techniques: honeypots and decoys. In: Handbook Information Security, vol. 3(1) (2006)
Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: conference on Electronic commerce (2006)
Dong, C., Zhao, L.: Sensor network security defense strategy based on attack graph and improved binary PSO. Saf. Sci. 117, 81–87 (2019)
Durkota, K., Lisý, V., Bošanský, B., Kiekintveld, C.: Approximate solutions for attack graph games with imperfect information. In: Khouzani, M.H.R., Panaousis, E., Theodorakopoulos, G. (eds.) GameSec 2015. LNCS, vol. 9406, pp. 228–249. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25594-1_13
Durkota, K., Lisỳ, V., Bošanskỳ, B., Kiekintveld, C.: Optimal network security hardening using attack graph games. In: International Joint Conference on Artificial Intelligence (2015)
Durkota, K., Lisỳ, V., Bošanskỳ, B., Kiekintveld, C., Pěchouček, M.: Hardening networks against strategic attackers using attack graph games. Comput. Secur. 87, 101578 (2019)
Durkota, K., Lisỳ, V., Kiekintveld, C., Bošanskỳ, B., Pěchouček, M.: Case studies of network defense with attack graph games. Intell. Syst. 31(5), 24–30 (2016)
Elsken, T., Metzen, J.H., Hutter, F.: Neural architecture search: a survey. J. Mach. Learn. Res. 20 (2019)
Erdős, P., Rényi, A.: On Random Graphs. Publicationes Mathematicae Debrecen, vol. 6 (1959)
Fang, F., et al.: PAWS-a deployed game-theoretic application to combat poaching. AI Mag. 38(1), 23–36 (2017)
Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: Annual Symposium on Foundations of Computer Science (2011)
Garg, N., Grosu, D.: Deception in honeynets: a game-theoretic analysis. In: Information Assurance and Security Workshop (2007)
Gurobi Optimization, LLC: Gurobi optimizer reference manual (2020)
Horák, K., Zhu, Q., Bošanskỳ, B.: Manipulating adversary’s belief: a dynamic game approach to deception by design for proactive network security. In: Conference on Decision and Game Theory for Security (2017)
IBM Security: Cost of a data breach report 2019 (2019). https://ibm.co/2CPsVnV
Ingols, K., Lippmann, R., Piwowarski, K.: Practical attack graph generation for network defense. In: Annual Computer Security Applications Conference (2006)
Instructables: how to make your bike look an ugly discouragement for thieves (2015). https://rb.gy/kb384b
Jain, M., Korzhyk, D., Vaněk, O., Conitzer, V., Pěchouček, M., Tambe, M.: A double oracle algorithm for zero-sum security games on graphs. In: International Conference on Autonomous Agents and Multiagent Systems (2011)
Jajodia, S., Ghosh, A.K., Swarup, V., Wang, C., Wang, X.S.: Moving Target Defense: Creating Asymmetric Uncertainty for Cyber Threats, vol. 54. Springer Science & Business Media (2011)
Jajodia, S., Noel, S., O’berry, B.: Topological analysis of network attack vulnerability. In: Managing Cyber Threats (2005)
Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
Kreibich, C., Crowcroft, J.: Honeycomb: creating intrusion detection signatures using honeypots. Comput. Commun. Rev. 34(1), 51–56 (2004)
Kuipers, D., Fabro, M.: Control systems cyber security: defense in depth strategies. Technical report, Idaho Nat. Labo. (2006)
Liu, Y., Man, H.: Network vulnerability assessment using Bayesian networks. In: Data Mining, Intrusion Detection, Information Assurance, and Data Networks Security (2005)
McKelvey, R.D., Palfrey, T.R.: Quantal response equilibria for normal form games. Games Econ. Behav. 10(1), 6–38 (1995)
Mee, P., Schuermann, T.: How a cyber attack could cause the next financial crisis (2018). https://bit.ly/3f2lOFP
Mezura-Montes, E., Velázquez-Reyes, J., Coello Coello, C.A.: A comparative study of differential evolution variants for global optimization. In: Annual Conference on Genetic and Evolutionary Computation (2006)
Miah, M.S., Gutierrez, M., Veliz, O., Thakoor, O., Kiekintveld, C.: Concealing cyber-decoys using two-sided feature deception games. In: International Conference on System Sciences (2020)
Nguyen, T.H., Wright, M., Wellman, M.P., Baveja, S.: Multi-stage attack graph security games: Heuristic strategies, with empirical game-theoretic analysis. Secur. Commun. Netw. (2018)
Noel, S., Jajodia, S.: Managing attack graph complexity through visual hierarchical aggregation. In: Workshop on Visualization and Data Mining for Computer Security (2004)
Noel, S., Jajodia, S., O’Berry, B., Jacobs, M.: Efficient minimum-cost network hardening via exploit dependency graphs. In: Computer Security Applications Conference (2003)
Paszke, A., et al.: Pytorch: an imperative style, high-performance deep learning library. In: Advances in Neural Information Processing Systems (2019)
Pawlick, J., Colbert, E., Zhu, Q.: A game-theoretic taxonomy and survey of defensive deception for cybersecurity and privacy. Comput. Surv. 52(4), 1–28 (2019)
Phillips, C., Swiler, L.P.: A graph-based system for network-vulnerability analysis. In: Workshop on New Security Paradigms (1998)
Pita, J., Jain, M., Ordónez, F., Portway, C., Tambe, M., Western, C., et al.: Armor security for Los Angeles International Airport. In: AAAI Conference on AI (2008)
Polad, H., Puzis, R., Shapira, B.: Attack graph obfuscation. In: Dolev, S., Lodha, S. (eds.) CSCML 2017. LNCS, vol. 10332, pp. 269–287. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60080-2_20
Schlenker, A., et al.: Deceiving cyber adversaries: a game theoretic approach. In: International Conference on Autonomous Agents and Multiagent Systems (2018)
Schneier, B.: Attack trees. Dr. Dobb’s J. 24, 12 (1999)
Shen, W., Tang, P., Zuo, S.: Automated mechanism design via neural networks. In: International Conference on Autonomous Agents and Multiagent Systems (2019)
Sheyner, O., Haines, J., Jha, S., Lippmann, R., Wing, J.M.: Automated generation and analysis of attack graphs. In: IEEE Symposium on Security and Privacy (2002)
Shi, Z.R., et al.: Learning and planning in feature deception games. arXiv preprint arXiv:1905.04833 (2019)
Shi, Z.R., Tang, Z., Tran-Thanh, L., Singh, R., Fang, F.: Designing the game to play: optimizing payoff structure in security games. In: International Joint Conference on Artificial Intelligence (2018)
Shieh, E., et al.: Protect: a deployed game theoretic system to protect the ports of the United States. In: International Conference on Autonomous Agents and Multiagent Systems (2012)
Shieh, E., et al.: Protect in the ports of Boston, New York and beyond: experiences in deploying Stackelberg security games with quantal response. In: Handbook Computational Approaches to Counterterrorism (2013)
Stallings, W., Brown, L., Bauer, M.D., Bhattacharjee, A.K.: Computer Security: Principles and Practice (2012)
Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997)
Tambe, M.: Security and Game Theory: Algorithms, Deployed Systems. Lessons Learned. Cambridge University Press, Cambridge (2011)
Thakoor, O., Tambe, M., Vayanos, P., Xu, H., Kiekintveld, C., Fang, F.: Cyber camouflage games for strategic deception. In: Alpcan, T., Vorobeychik, Y., Baras, J.S., Dán, G. (eds.) GameSec 2019. LNCS, vol. 11836, pp. 525–541. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32430-8_31
Virtanen, P., et al.: Scipy 1.0: fundamental algorithms for scientific computing in python. Nat. Methods 17(3), 261–272 (2020)
Wright, M., Wang, Y., Wellman, M.P.: Iterated deep reinforcement learning in games: history-aware training for improved stability. In: ACM Conference on Economics and Computation (2019)
Zhuang, J., Bier, V.M.: Reasons for secrecy and deception in homeland-security resource allocation. Risk Anal. Int. J. 30(12), 1737–1743 (2010)
Acknowledgements
This research was sponsored by the U.S. Army Combat Capabilities Development Command Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Security CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Combat Capabilities Development Command Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
We modify the DE [61] variant DE/rand/1/bin [42]. To initialize the population, we randomly choose the sequence of deceptive actions to consider. For each type, we determine the maximum number of components that can be altered (e.g., edges to add) for this individual. If allowed, we then modify the graph with randomly-selected modifications of that type. We also add a new termination condition based on the known optimal utility (0) for the defender if the defender has infinite protective and deceptive budgets. If any solution yields this utility, then we stop early and select it as the final solution. We also use a more compact solution representation: the full solution takes space \( m_e (2 |N| + 1) + |N| + 2 |E|\), where \(m_e\) indicates the maximum number of edges that can be added to the graph given \(B^d\). Each edge to be added takes space 2|N|. To indicate that an edge is to be added, we take the \({{\,\mathrm{arg\,max}\,}}\) over the effort allocated in the first N and last N slots. The resulting indices i, j indicate the endpoints of the edge. If the summed effort at i, j is greater than a threshold, the edge is added. We further compact the representation when the defender cannot add or hide any edges without violating constraints by removing these parts of the solution, so each strategy uses space \(|E| + |N|\).
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Milani, S. et al. (2020). Harnessing the Power of Deception in Attack Graph-Based Security Games. In: Zhu, Q., Baras, J.S., Poovendran, R., Chen, J. (eds) Decision and Game Theory for Security. GameSec 2020. Lecture Notes in Computer Science(), vol 12513. Springer, Cham. https://doi.org/10.1007/978-3-030-64793-3_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-64793-3_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64792-6
Online ISBN: 978-3-030-64793-3
eBook Packages: Computer ScienceComputer Science (R0)