Playing repeated security games with multiple attacker types: a Q-iteration on a linear programming approach

Abstract

This paper investigates infinite horizon repeated security games with one defender and multiple attacker types. The incomplete information brings uncertainty of attackers' behaviour for the defender. Under the uncertainty of attackers' behaviours, we take the worst-case analysis to minimise the defender's regret w.r.t. each attacker type. We wish to keep the regret especially small w.r.t. one attacker type, at the cost of modest additional overhead compared to others. The trade-off among the objectives requires us to build a Multi-Objective Repeated Security Game (MORSG) model. To parameterise the regret Pareto frontier, we combine the different weight vectors with different objectives and build a linear programming approach. By running the Q-iteration procedure on linear programming for each weight vector, the optimal regret Pareto frontier can be computed. We also propose an approximate approach to approximate it. The approximation analysis proves the effectiveness of the approximation approach.

Keywords:

• Multi-objective repeated security game (MORSG)
• Q-iteration
• regret Pareto frontier

Acknowledgments

The authors thank the editor and two anonymous referees for their valuable comments and suggestions, which greatly helped improve the content and presentation of this article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The paper is supported by the National Natural Science Foundation of China [grant nos 61572095, 61877007].

Notes on contributors

Ling Chen

Ling Chen received the B.S. degree in statistics from Shandong University, Weihai, in 2016. She is currently pursuing the Ph.D. degree with the School of Mathematical Sciences, Dalian University of Technology. Her current research includes security game and reinforcement learning.

Mingchu Li

Mingchu Li received the B.S. degree in mathematics from Jiangxi Normal University, in 1983, the M.S. degree in applied science from the University of Science and Technology Beijing, in 1989, and the Ph.D. degree in mathematics from the University of Toronto, in 1997. He was an Associate Professor with the University of Science and Technology Beijing, from 1989 to 1994. He was engaged in the research and development of information security at Long View Solution Inc. and Compute Ware Inc., from 1997 to 2002. Since 2002, he has been a Full Professor with the School of Software, Tianjin University. He has been with the School of Software Technology, Dalian University of Technology, as a Full Professor, a Ph.D. Supervisor, and the Vice Dean. His main research interests include theoretical computer science and cryptography. His other research interests include graph theory, network security, and game theory.

Yingmo Jie

Yingmo Jie received the B.S. degree in information and computing science from Tianjin University of Technology and Education in 2011. She received the M.S. degree in 2015 in applied mathematics from Civil Aviation University of China, Tianjin, China. In 2019, she received the Ph.D. degree in the School of Mathematical Sciences at the Dalian University of Technology. Since 2019, she has been a post doc in the School of Software Technology at the Dalian University of Technology. Her current research interests include information security, resources optimisation and game theory.