Abstract
Today’s high-stakes adversarial interactions feature attackers who constantly breach the ever-improving security measures. Deception mitigates the defender’s loss by misleading the attacker to make suboptimal decisions. In order to formally reason about deception, we introduce the feature deception problem (FDP), a domain-independent model and present a learning and planning framework for finding the optimal deception strategy, taking into account the adversary’s preferences which are initially unknown to the defender. We make the following contributions. (1) We show that we can uniformly learn the adversary’s preferences using data from a modest number of deception strategies. (2) We propose an approximation algorithm for finding the optimal deception strategy given the learned preferences and show that the problem is NP-hard. (3) We perform extensive experiments to validate our methods and results. In addition, we provide a case study of the credit bureau network to illustrate how FDP implements deception on a real-world problem.
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.
Typically, the loss \(u_{i}\) is non-negative, but it might be negative if, for example, the target is set up as a decoy or honeypot, and allows the defender to gain information about the attacker.
- 2.
Refer to the proof of Theorem 1 for the notations used.
- 3.
The full version of the paper is available at https://arxiv.org/abs/1905.04833.
References
Abbasi, Y., et al.: Know your adversary: insights for a better adversarial behavioral model. In: CogSci (2016)
Albanese, M., Battista, E., Jajodia, S.: Deceiving attackers by creating a virtual attack surface. In: Jajodia, S., Subrahmanian, V.S.S., Swarup, V., Wang, C. (eds.) Cyber Deception, pp. 169–201. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-32699-3_8
Blum, A., Haghtalab, N., Procaccia, A.D.: Learning optimal commitment to overcome insecurity. In: NIPS (2014)
Chiang, C.Y.J., et al.: ACyDS: An adaptive cyber deception system. In: MILCOM (2016)
Fang, F., Stone, P., Tambe, M.: When security games go green: designing defender strategies to prevent poaching and illegal fishing. In: IJCAI (2015)
Gan, J., Xu, H., Guo, Q., Tran-Thanh, L., Rabinovich, Z., Wooldridge, M.: Imitative follower deception in Stackelberg games. In: EC (2019)
Guo, Q., An, B., Bosanskỳ, B., Kiekintveld, C.: Comparing strategic secrecy and Stackelberg commitment in security games. In: IJCAI, pp. 3691–3699 (2017)
Haghtalab, N., Fang, F., Nguyen, T.H., Sinha, A., Procaccia, A.D., Tambe, M.: Three strategies to success: learning adversary models in security games. In: IJCAI (2016)
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: Rass, S., An, B., Kiekintveld, C., Fang, F., Schauer, S. (eds.) GameSec 2017. Lecture Notes in Computer Science, vol. 10575, pp. 273–294. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68711-7_15
Hurlburt, G.: “Good enough” security: the best we’ll ever have. Computer 49, 98–101 (2016)
Jafarian, J.H., Al-Shaer, E., Duan, Q.: Openflow random host mutation: transparent moving target defense using software defined networking. In: Proceedings of the First Workshop on Hot Topics in Software Defined Networks. ACM (2012)
Jajodia, S., et al.: A probabilistic logic of cyber deception. IEEE Trans. Inf. Forensics Secur. 12(11), 2532–2544 (2017)
Jajodia, S., Subrahmanian, V., Swarup, V., Wang, C.: Cyber Deception. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-319-32699-3
Latimer, J.: Deception in War. John Murray, London (2001)
Letchford, J., Conitzer, V., Munagala, K.: Learning and approximating the optimal strategy to commit to. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 250–262. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04645-2_23
Lyon, G.F.: Nmap network scanning: The Official Nmap Project Guide to Network Discovery and Security Scanning. Insecure (2009)
Marecki, J., Tesauro, G., Segal, R.: Playing repeated Stackelberg games with unknown opponents. In: AAMAS (2012)
Nakashima, E.: To thwart hackers, firms salting their servers with fake data (2013)
Nguyen, T.H., Wang, Y., Sinha, A., Wellman, M.P.: Deception in finitely repeated security games. In: AAAI (2019)
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, B., Shen, W., Tang, P., Zuo, S.: Learning optimal strategies to commit to. In: AAAI (2019)
Perrault, A., Wilder, B., Ewing, E., Mate, A., Dilkina, B., Tambe, M.: Decision-focused learning of adversary behavior in security games. arXiv preprint arXiv:1903.00958 (2019)
Potter, B., Day, G.: The effectiveness of anti-malware tools. Comput. Fraud Secur. 2009, 12–13 (2009)
Provos, N., et al.: A virtual honeypot framework. In: USENIX Security Symposium (2004)
PwC: Operation Cloud Hopper Technical Annex
Rowe, N.C.: Deception in defense of computer systems from cyber attack. In: Cyber Warfare and Cyber Terrorism. IGI Global (2007)
Schlenker, A., et al.: Deceiving cyber adversaries: a game theoretic approach. In: AAMAS (2018)
Shamsi, Z., Nandwani, A., Leonard, D., Loguinov, D.: Hershel: single-packet OS fingerprinting. ACM SIGMETRICS Perform. Eval. Rev. 42, 195–206 (2014)
Sinha, A., Kar, D., Tambe, M.: Learning adversary behavior in security games: A pac model perspective. In: AAMAS (2016)
Spitzner, L.: The honeynet project: trapping the hackers. IEEE Secur. Priv. 1, 15–23 (2003)
Stancu-Minasian, I.M.: Fractional Programming: Theory, Methods and Applications, vol. 409. Springer, Heidelberg (2012). https://doi.org/10.1007/978-94-009-0035-6
Wang, W., Zeng, B.: A two-stage deception game for network defense. In: GameSec (2018)
Yang, R., Ford, B., Tambe, M., Lemieux, A.: Adaptive resource allocation for wildlife protection against illegal poachers. In: AAMAS (2014)
Yang, R., Ordonez, F., Tambe, M.: Computing optimal strategy against quantal response in security games. In: AAMAS (2012)
Yin, Y., An, B., Vorobeychik, Y., Zhuang, J.: Optimal deceptive strategies in security games: a preliminary study. In: AAAI Symposium on Applied Computational Game Theory (2014)
Acknowledgments
This research was sponsored by the 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 not withstanding any copyright notation here on.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Shi, Z.R. et al. (2020). Learning and Planning in the Feature Deception Problem. 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_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-64793-3_2
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)