A Search for Saddle Point in Protectable Assets Selection Problem Based on Continuous Game Theory Model Alexander Yu. Bykov Ivan. A. Krygin Information Security Department Information Security Department Bauman Moscow State Technical University Bauman Moscow State Technical University Moscow, Russia Moscow, Russia abykov@bmstu.ru krygin.ia@gmail.com Abstract. This article considers a continuous zero-sum game formulate the interactions between a receiver and a spoofing of two players with resources limitations between defender, node in the spoofing detection as a zero-sum game. selecting the assets to be protected, and attacker, selecting the assets to be attacked. Players’ solutions are defense and attack In [4] it’s investigated appliance of learning, based on game probabilities vectors for each asset. The problem is formulated theory, to analyze big data. Such technique may be useful to that each player must solve linear programming problem with analyze social networks. There are considered a linear game fixed opponent’s solution. The saddle point is suggested to search model of multiple players (agents), data storing in huge on simplices faces, defined by limitations. To find it two systems storages, each agent is related to sensitive information. Model of linear equations is necessary to be solved: one to find is continuous, solution search satisfying Nash criterion is defender’s solution and another to find attacker’s solution. Each considered. player chooses solution on his face so that another player’s parameter value is the same for any solution on his own face. To In [5] resource distribution in multiple access wiretap find a saddle with a guarantee it necessary to go over all channels is considered. In model it’s considered several users combinations of simplices faces. An example of the solution of the who want to confidentially transmit data to legitimate user. On problem is presented. The total game cost, probabilities of receiver side there is an adversary, who passively listen to attacks on assets and probabilities of defense are calculated. channel and try to decode messages. Stochastic game is considered, solutions are sought to be Nash and Pareto optimal. Keywords. information security, zero-sum game, linear programming, saddle point, simplex, face of simplex, system of In [6] an efficient stochastic zero-sum game with linear equations incomplete information is considered. In article it’s investigated problem of own secret information disclosure to obtain adversary secret information and its solution strategies I. INTRODUCTION are suggested. Game theory models are often used in problems related with information security. Consider some examples. In [7] it’s considered game technique to detect hardware trojans. Authors notice, the microcircuit industry is witnessing In [1] a game theory appliance in steganography is a massive outsourcing of the fabrication of ICs, and it brings up considered. Authors notice, there are a few articles related to multiple opportunities for the insertion of malicious logic in the this topic, because of adaptive attacks in steganography haven’t ICs. Authors suggest using game theory to detect such been carried out until recently. Two players are considered: insertions. deplorer player and detection players are described. A saddle point searching algorithm in mixed strategies is suggested. In [8] it’s considered a modelling of jamming attack in networks with wireless energy transfer. Authors have In [2] it is considered an optimal strategy of network developed a game model, that allows to avoid energy protection with usage of Moving Target Defense principle, interception. There are two players in the game: legitimate user based on Markov game. An essence of MTD – moving and adversary. Each player has his own utility function, network elements vary in time, making attack more difficult. solution is sought as limited Nash equilibrity. Markov decision process is used to describe transitions between network multistates. Dynamic game is used to Information security software is often used to protect describe multiphase steps of defense and attack in terms of information in information processing and control systems MTD. (IPCS). This software is generally deployed on computational tools, which is used to solve target and supporting tasks in In [3] it’s investigated the PHY-layer authentication that IPCS. In this case security software uses computational exploits radio channel information to detect spoofing attacks in resources, and these resources are often limited, and their multiple- input multiple-output (MIMO) systems. Authors deficit is possible. This task becomes especially actual in 36 mobile security protection, which have limited computational 2) 𝑝𝑝𝑟 𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀 – i-th asset attack prevention resources. probability when defending The following definitions will be used: 3) 𝑎𝑘𝑖 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝐿, 𝑖 ∈ 𝑀 – normalized k-th defender’s limited resource value, used to protect i-th asset.  protected asset – something is needed to be protected The whole asset equals to 1  resource – computational resource, used by security 4) 𝑏𝑘 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝐿 – maximum normalized k-th software limited resource value, allocated for protection 5) с𝑘𝑖 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝑆, 𝑖 ∈ 𝑀 – normailzed k-th Protected resources are: attacker’s limited resource value, used to attack i-th asset. The  integrity, availability, confidentiality of data, storing on whole asset equals to 1 devices 6) 𝑑𝑘 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝑆 – maximum normalized k-th  integrity, availability, confidentiality of data, attacker’s limited resource value transferring over communication lines C. Parameters  etc. Define variable 𝑝𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀, signifying probability asset protection probability or its security degree. Variables System resources are: forms vector 𝑃⃗ . For attacker define variable 𝑞𝑖 ∈ [0, 1], ∀ 𝑖 ∈  security software cost 𝑀, signifying asset attack probability or attack reliability degree. Variables form vector 𝑄 ⃗.  CPU time  RAM size D. Players indicators  Storage size For zero-sum game players quality indicators are defined by defender damage. Average cost damage is:  Network ⃗ ) = 𝑈𝑚𝑎𝑥 (𝑄 𝑈(𝑃⃗ , 𝑄 ⃗ ) − 𝑈пр (𝑃⃗ , 𝑄 ⃗)  etc. (1) = ∑ 𝑤𝑖 𝑞𝑖 − ∑ 𝑝𝑝𝑟 𝑖 𝑤𝑖 𝑝𝑖 𝑞𝑖 Consider the problem of computer resources distribution 𝑖 ∈𝑀 𝑖 ∈𝑀 between assets and use two-players zero-sum game (defender and attacker parties). Solution belonging to saddle-point, if it where 𝑈𝑚𝑎𝑥 (𝑄 ⃗ ) = ∑𝑖 ∈𝑀 𝑤𝑖 𝑞𝑖 maximum damage, may be exists, is often a decision criterion in game-theory. Consider a caused by attacker without protection; 𝑈пр (𝑃⃗ , 𝑄 ⃗)= possible approach to find a solution. Elements of selection set ∑𝑖 ∈𝑀 𝑝𝑝𝑟 𝑖 𝑤𝑖 𝑝𝑖 𝑞𝑖 – damage, prevented by defender are continuous. It’s necessary to find asset protection possibilities and attacks on assets possibilities. Some samples of game-theory usage for solving information security E. Limitations problems are presented in [1-4] Defender’s limited resources usage limitation: Proposed protected assets selection problem formulation is similar to formulation, discussed in [5], but in [5] was used the ∑ 𝑎𝑖𝑘 𝑝𝑖 ≤ 𝑏𝑘 , ∀ 𝑘 ∈ 𝐿. one cost limitation. In case of saddle point is impossible to find (2) 𝑖 ∈𝑀 by optimized algorithm guaranteed result principle was applied. Attacker’s limited resources usage limitation: ∑ 𝑐𝑖𝑘 𝑞𝑖 ≤ 𝑑𝑘 , ∀ 𝑘 ∈ 𝑆 (3) II. FORMULATION OF SECURITY SYSTEM RESOURCES 𝑖 ∈𝑀 DISTRIBUTON BETWEEN PROTECTED ASSETS PROBLEM Thus, each player’s decision (searching for unknown A. Initial data ⃗ ) with fixed opponent’s solution implies linear vectors 𝑃⃗ or 𝑄 1) 𝑍 = {𝑧1 , 𝑧2 , … , 𝑧𝑚 } - protected assets set, 𝑀 = programming problem solution {1, 2, … , 𝑚} - their indices set 2) 𝑅 = {𝑟1 , 𝑟2 , … , 𝑟𝑙 } – defender’s limited resources set, III. BASES OF ALGORITHM OF SEARCHING FOR SADDLE 𝐿 = {1, 2, … , 𝑙} – their indicies set POINT ON THE DEFINED BY LIMITATIONS SIMPLEX FACES 3) 𝑁 = {𝑛1 , 𝑛2 , … , 𝑛𝑠 } – attacker’s limited resources set, Optimization problem for first player with fixed second 𝑆 = {1, 2, … , 𝑠} – their indices set player’s decision is a linear programming problem. The first player wishes to minimize parameter (1) with limitations (2), B. Set elements parameters and relations between them and the second one wishes to maximize parameter (1) with 1) 𝑤𝑖 ≥ 0, ∀ 𝑖 ∈ 𝑀 – cost, if i-th protected asset security limitations (3). breach occurred (asset cost) In [15] levels technique is suggested to find saddle point of convex-concave function. This method is approximate and is 37 required to solve convex programming problems. Also, it is ⃗ (1) ) = 𝑈(𝑃⃗ ∗ , 𝑄 𝑈(𝑃⃗ ∗ , 𝑄 ⃗ (2) ), pointed the saddle point always exists under given conditions. ⃗ (1) ) = 𝑈(𝑃⃗ ∗ , 𝑄 𝑈(𝑃⃗ ∗ , 𝑄 ⃗ (3) ), ⃗ ∗ may The saddle point defined by solutions pair 𝑃⃗ ∗ and 𝑄 ….. be as on vertices of two simplices, defined by limitations (2) ⃗ (1) ) = 𝑈(𝑃⃗ ∗ , 𝑄 𝑈(𝑃⃗ ∗ , 𝑄 ⃗ (𝑚) ), and (3), and on simplices faces. Optimized technique may be used to find saddle point if it is on vertices. ∑ 𝛼 (𝑖) = 1. { 𝑖 ∈𝑀 Simplices (polyhedron of allowable values) are in m- dimension metric space. In this case each limitation of System of equations 2 relatively unknown inequalities (2) and (3) defines (m-1)-dimensioned hyperplane 𝛽 (1) , 𝛽 (2) , … , 𝛽 (𝑚) : if becomes equality. As 𝑝𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀 and 𝑞𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀, allowable solutions are also inside of ⃗ ∗ ) = 𝑈(𝑃⃗ (2) , 𝑄 𝑈(𝑃⃗ (1) , 𝑄 ⃗ ∗ ), hypercube with sides are equal to 1. Hypercubes are ⃗ ∗ ) = 𝑈(𝑃⃗ (3) , 𝑄 𝑈(𝑃⃗ (1) , 𝑄 ⃗ ∗ ), constrained by (m-1)-dimensioned hyperplanes, defined by ….. 𝑝𝑖 = 0, ∀ 𝑖 ∈ 𝑀, 𝑝𝑖 = 1, ∀ 𝑖 ∈ 𝑀 evaluations for defender ⃗ ∗ ) = 𝑈(𝑃⃗ (𝑚) , 𝑄 ⃗ ∗ ), and 𝑞𝑖 = 0, ∀ 𝑖 ∈ 𝑀, 𝑞𝑖 = 1, ∀ 𝑖 ∈ 𝑀 evaluations for attacker. 𝑈(𝑃⃗ (1) , 𝑄 In this way simplices are constrained by hyperplanes defined ∑ 𝛽 (𝑖) = 1. by limitations (2) and (3) (if inequalities become equalities) { 𝑖 ∈𝑀 and hypercubes borders hyperplanes. An intersection of two (m-1)-dimensioned hyperplanes (if they intersect) is a (m-2)- ⃗ ∗ satisfy limitations (2) and (3) If found solutions 𝑃⃗ ∗ and 𝑄 dimensioned hyperplane; an intersection of three hyperplanes and saddle point condition, then this is a required solution. is (m-3)-dimensioned hyperplane etc. Separated point of m- dimensioned space in this interpretation is 0-dimensioned IV. EXAMPLE hyperplane. Simplices faces may belong to different Consider the solution of low dimension problem of dimensioned hyperplanes (in three dimensioned case the protecting some assets: number of protectable assets – 8, following terms are used: faces, edges, vertices). It is necessary number of defender’s limited resources with defense cost -4, to go over all faces for full search. Consider the technique of number of attacker’s limited resources and attack costs – 4. searching for possible solutions on faces, belong to same- Other data are generated by pseudorandom number generator. dimensioned hyperfaces. Protected assets parameters, such as possible loss, For each face it reachability is checked, that is allowable probability (possibility) of assets attacks prevention are given solution must exist for each player on his own face. It’s not in table 1. Possible damage values are given in conventional necessary to examine unreachable faces. units. Defender’s limited resources parameters, such as defense Saddle point on simplices faces, defined by limitations, costs as resource and right sides of (2) values are given in table must satisfy the following conditions if it exists. Point 𝑃⃗ ∗ on 2. Attacker’s limited resources parameters, such as attack costs face must ensure that target function reaches maximum and as resource and right sides of (2) values are given in table 2. takes the same values on each point on second player’s face in Costs are given in conventional units. vector space 𝑄 ⃗ . Similarly point 𝑄⃗ ∗ on face must ensure that target function reaches minimum and takes the same values on TABLE I. PROTECTABLE ASSETS PARAMETERS each point on first player’s face in vector space 𝑃⃗ . Size of possible Attack prevention # damage probability It is necessary to find m different points per each (m-1)- 𝑝𝑝𝑟 𝑖 , ∀ 𝑖 ∈ 𝑀 𝑤𝑖 , ∀ 𝑖 ∈ 𝑀 dimensioned face (not necessarily satisfying all the limitations 1 4535,63 0,967 (2) or (3)). Let 𝑃⃗(1) , 𝑃⃗ (2) , … , 𝑃⃗ (𝑚) are points on face in vector 2 2075,96 0,607 space 𝑃⃗ , and 𝑄⃗ (1) , 𝑄 ⃗ (2) , … , 𝑄 ⃗ (𝑚) are points on face in vector 3 3357,13 0,805 ⃗ . Define multipliers 𝛼 (1) , 𝛼 (2) , … , 𝛼 (𝑚) and 4 2972,23 0,769 space 𝑄 5 3409,13 0,676 𝛽 , 𝛽 , … , 𝛽 (𝑚) . So required points is found is the following (1) (2) 6 2260,05 0,973 form: 𝑃⃗ ∗ = ∑𝑖 ∈𝑀 𝛼 (𝑖) 𝑃⃗ (𝑖) , 𝑄 ⃗ ∗ = ∑𝑖 ∈𝑀 𝛽 (𝑖) 𝑄⃗ (𝑖) . 7 2188,76 0,660 8 4280,74 0,708 System of equations 1 relatively unknown 𝛼 (1) , 𝛼 (2) , … , 𝛼 (𝑚) : 38 Suggested solutions reliability is based on usage of known TABLE II. DEFENDER’S RESOURCES verifies algorithms, found saddle point is confirmed by check Defender’s resources values for compliance with conditions it must satisfy. 𝑎𝑘𝑖 , ∀ 𝑘 ∈ 𝐿, 𝑖 ∈ 𝑀 # Defense cost Resource 1 Resource 2 Resource 3 REFERENCES 1 392,038 0,340 0,345 0,153 [1] Schöttle P., Böhme R. Game Theory and Adaptive Steganography. IEEE 2 144,472 0,176 0,319 0,392 Transactions on Information Forensics and Security. 2016. Vol. 11, iss. 3 292,657 0,273 0,160 0,426 4. P. 760–773. DOI: 10.1109/TIFS.2015.2509941. 4 147,133 0,130 0,151 0,381 [2] Lei C., Ma D., Zhang H. Optimal Strategy Selection for Moving Target 5 128,114 0,218 0,229 0,410 Defense Based on Markov Game. IEEE Access. 2017. Vol. 5. P. 156– 6 252,678 0,451 0,263 0,250 169. DOI: 10.1109/ACCESS.2016.2633983. 7 194,546 0,437 0,300 0,318 [3] Xiao Liang., Chen T., Han G., Zhuang W., Sun L. Channel-Based 8 329,060 0,101 0,345 0,246 Authentication Game in MIMO Systems. 2016 IEEE Global Total Communications Conference (GLOBECOM). 2016. P. 1–6. DOI: 940,349 1,200 1,179 1,634 10.1109/GLOCOM.2016.7841657. 𝑏𝑘 , ∀𝑘 ∈ 𝐿 [4] Chessa M., Grossklags J., Loiseau P. A Game-Theoretic Study on Non- TABLE III. ATTACKER’S RESOURCES monetary Incentives in Data Analytics Projects with Privacy Implications. 2015 IEEE 28th Computer Security Foundations Attacker’s resources values Symposium. 2015. P. 90–104. DOI: 10.1109/CSF.2015.14. # с𝑘𝑖 , ∀ 𝑘 ∈ 𝑆, 𝑖 ∈ 𝑀 [5] Shah S. Chaitanya A., Sharma V. Resource allocation in fading multiple Attack cost Resource 1 Resource 2 Resource 3 access wiretap channel via game theoretic learning. 2016 Information 1 22,361 0,350 0,233 0,242 Theory and Applications Workshop (ITA). 2016. P. 1–7. DOI: 2 14,527 0,148 0,248 0,247 10.1109/ITA.2016.7888137. 3 13,823 0,164 0,158 0,176 [6] Li L., Shamma J. Efficient computation of discounted asymmetric 4 20,547 0,199 0,112 0,306 information zero-sum stochastic games. 2015 54th IEEE Conference on 5 18,650 0,322 0,349 0,322 Decision and Control (CDC). 2015. P. 4531–4536. DOI: 6 34,593 0,431 0,479 0,403 10.1109/CDC.2015.7402927. 7 44,407 0,185 0,364 0,347 [7] Kamhoua C., Zhao H., Rodriguez M., Kwiat K. A Game-Theoretic 8 25,191 0,331 0,486 0,421 Approach for Testing for Hardware Trojans. IEEE Transactions on Total Multi-Scale Computing Systems. 2016. Vol. 2, iss. 3. P. 199–210. DOI: 116,459 1,070 1,542 1,694 𝑑𝑘 , ∀𝑘 ∈ 𝑆 10.1109/TMSCS.2016.2564963. [8] Niyato D., Wang P., Kim D., Han Z., Xiao L. Game theoretic modeling of jamming attack in wireless powered communication networks. 2015 Because of going over faces the saddle point was found on IEEE International Conference on Communications (ICC). 2015. P. faces belonging to 6-dimension hyperplanes (solution is sought 6018–6023. DOI: 10.1109/ICC.2015.7249281. in initial 8-dimension spaces). For defender hyperplane is [9] Freudiger J., Manshaei M.H., Hubaux J. P., Parkes D.C. Non- defined by two 7-dimension hyperplanes intersection – one Cooperative Location Privacy. IEEE Transactions on Dependable and hyperplane containing face, defined by defense cost limitation, Secure Computing. 2013. Vol. 10, iss. 2. P. 84 – 98. DOI: and another hyperplane defined by condition 𝑝6 = 0. For 10.1109/TDSC.2012.85. attacker hyperplane is defined by two 7-dimension hyperplanes [10] Lelarge M. Coordination in Network Security Games: A Monotone Comparative Statics Approach. IEEE Journal on Selected Areas in intersection – one hyperplane containing face, defined by Communications. 2012. Vol. 30, iss. 11. P. 2210 – 2219. DOI: resource 2 limitation, and another hyperplane defined by 10.1109/JSAC.2012.121213. condition 𝑞6 = 0. Solution is presented in table 4. [11] Liang Xiao, Yan Chen, Lin W.S., Liu K.J.R. Indirect Reciprocity Security Game for Large-Scale Wireless Networks. IEEE Transactions on Information Forensics and Security. 2012. Vol. 7, iss. 4. P. 1368 – TABLE IV. SOLUTION 1380. DOI: 10.1109/TIFS.2012.2202228. Game [12] Ma C.Y.T., Yau D.K.Y., Rao N.S.V. Scalable Solutions of Markov Vector 𝑃⃗ ∗ cost Games for Smart-Grid Infrastructure Protection. IEEE Transactions on 0,422 0,751 0,778 0,634 0,409 0,000 0,532 0,576 Smart Grid. 2013. Vol. 4, iss. 1. P. 47 – 55. DOI: ⃗∗ 8200, 10.1109/TSG.2012.2223243. Vector 𝑄 144 0,607 0,779 0,736 0,437 0,378 0,000 0,915 0,737 [13] Xiannuan Liang, Yang Xiao. Game Theory for Network Security. IEEE Communications Surveys & Tutorials. 2013. Vol. 15, iss. 1. P. 472 – 486. DOI: 10.1109/SURV.2012.062612.00056. CONCLUSION [14] A. Yu. Bykov, E. S. Shmatova The Algorithms of Resource Distribution There is presented a continuous two players zero-sum game for Information Security Between Objects of an Information System with resources limitation for choosing assets to protect by Based on the Game Model and Principle of Equal Security of Objects. defender and choosing assets to attack by attacker. Each player Science and Education of the Bauman MSTU, 2015, No. 9, pp. 160–187. DOI: 10.7463/0915.0812283. solves linear programming problem with fixed opponent decision. If saddle point is on simplices faces, defined by [15] Shmatova E. The Choice of Strategy for the Spurious Information System on the Basis of the Game Theory Model. Voprosy limitations, then it is suggested to solve two systems of linear kiberbezopasnosti [Cybersecurity issues], 2015. No 5 (13). P. 36-40. equations to find it. DOI: 10.21681/2311-3456-2015-5-36-40. [16] E. G. Golshtein, A. S. Nemirovsky, Yu. E. Nesterov Optimization techniques. Levels technique, it generalizations and applications. Economics and mathematical methods. 1995. V. 31. no. 3. pp. 164-180. 39