The Task of Selecting the Protected Assets Within the Limited Resources Based on the Model of Discrete Game Theory Alexander Yu. Bykov Maksim V. Grishunin Information Security Department Information Security Department Bauman Moscow State Technical University Bauman Moscow State Technical University Moscow, Russia Moscow, Russia abykov@bmstu.ru zux2@ya.ru Abstract—The game setting of the zero-sum problem for Lagrange multipliers. An application to computer network selecting the protected assets is considered. There are two security in which service providers cooperate to detect the players in the game: the defender and the forward. The signature of malicious users is developed to illustrate the attacker chooses assets for the attack; the defender chooses practical value of the proposed algorithm. assets for defense. The task is formulated in such a way that In [4], a routing algorithm is described in mobile sensor each player must solve his own problem of linear Boolean networks based on models of game theory. This algorithm is programming. It is proposed to reduce this problem to a based on a dynamic Bayesian signaling game and the matrix game for which algorithms of finding a saddle point in achievement of a perfect Bayesian equilibrium (PBE). The pure strategies, if it exists, or in mixed strategies are known. In algorithm allows to protect nodes from anonymous user this case, the problem, as a rule, is a problem of large dimension, to reduce the dimension of the matrix, algorithms actions. for the search of unmixed solutions that determine the rows In [5] it is shown how evolutionary game theory can help and columns of the matrix are developed. An example of in the organization's economy to optimize the costs of solving the problem of finding a saddle point in mixed information security systems. In the work, information strategies is presented, the probabilities for admissible security breaches are described by possible economic losses. solutions and the game price are assessed. Two types of security violations are considered: targeted attacks and the manifestation of spontaneous (accidental) Keywords— information security; zero-sum game; discrete threats. The game considers the ratio of investments in optimization; saddle point, payment game matrix, pure strategy, information security and possible losses. mixed strategy In [6], dynamic games with players that have incomplete information about the resources of other players, as applied I. INTRODUCTION to cyber physical systems, are considered. Also, the authors consider the denial-of-service attack and develop an Consider the game task of selecting protected security algorithm to compute the saddle-point. resources and selecting attacks on protected assets against In [7], the application of the theory of games in attacking the resources of the defense and attack sides. We steganography is considered. The authors note that this topic will use the concepts: the protected asset is what is protected, is practically not covered, since until recently adaptive and the resource is what is used for protection (e.g. [1, 2]). attacks in the field of steganography have not been Protected assets can be: conducted. Two players are considered: the introduction - Integrity, accessibility and confidentiality of data stored player and the detection player. An algorithm for finding the on computer facilities or mobile devices; saddle point in mixed strategies is proposed. - Integrity of applications, installed on the computer; In [8], an optimal strategy for protecting the network - Others. using the Moving Target Defense (MTD) concept based on The resources of the protection system can be the cost of the Markov game was considered. The essence of MTD - protection, processor time; RAM; disk storage; other certain elements of the network change over time, making it resources. Consider the task of allocating resources between difficult to "defeat" the target. The Markov decision-making assets, while using the model of two players with zero sum. process is used to describe the transitions between multi- Game theory has been widely used to solve various problems states of the network. Dynamic game is used to describe related to the protection of information. multiphase protection and attack steps in MTD conditions. An algorithm for finding optimal solutions in convex In [9], the authentication was investigated at the physical distributed online problems was developed in [3]. A level, while using the radio channel information to detect modification of the algorithm of the Arrow-Hurwicz method spoofing attacks in multiple- input multiple-output (MIMO) is proposed to search for a saddle point in order to fulfill the systems. The authors represent the interaction between the global network criterion of Savage, using the method of receiver and the spoofing node as a zero-sum game. 32 In [10], the application of learning based on game theory attacking side, S = {1,2, ..., s} – the set of indices of these for the analysis of large amounts of data is considered. This resources. approach can be useful for analyzing social network data. The authors consider a linear game model of many players Parameters of elements of sets and its ratio: (agents) whose data is stored in a large repository; 1) wi≥0, ∀ i ∈ M - possible damage in case of violation of confidential information is associated with each agent. The the security of the ith protected asset (asset value). model is continuous, the search for solutions satisfying the 2) pnp i ∈ [0,1], ∀ i ∈ M - probability (or possibility) of Nash criterion is considered. preventing an attack on the ith asset while protecting. In [11], the allocation of resources in multiple-access 3) aki ∈ [0,1), ∀ k ∈ L, i ∈ M - the normalized value of the listening channels is considered. The model considers several kth restricted resource used to provide protection for the ith users who want to transfer confidential data to the legitimate asset. The entire resource is considered equal to 1 recipient. On the receiving side there is an eavesdropper who 4) bk ∈ [0,1], ∀ k ∈ L - the maximum normalized value of passively listens to the channel and tries to decode messages. the kth restricted resource allocated for protection. The authors obtain a coarse correlated equilibrium, a Pareto 5) cki ∈ [0,1), ∀ k ∈ S, i ∈ M - the normalized value of the point and a Nash bargaining solution. kth restricted resource of the attacking side used to attack the In [12] is considered an effective solution to the ith asset. The entire resource is considered equal to 1. stochastic zero-sum games with lack of players information 6) dk ∈ [0,1], ∀ k ∈ S - the maximum normalized value of the about each other. The paper discusses the problem of kth restricted resource of the attacking side. revealing the player's own secret information to obtain the B. Required parameters enemy's secret information and suggests strategies for For the defense, we introduce the Boolean variable xi ∈ solving it. {0,1}, ∀ i ∈ M, xi = 1 if the ith asset is protected, xi = 0 - In [13], the application of the theory of games for otherwise, the variable elements vector 𝑋⃗. For a part of the security in mobile ad hoc networks (MANETs) is attack, we introduce a similar variable yi ∈ {0,1}, ∀ i ∈ M, yi considered. It is proposed to use the theory of medium-field = 1, if the attack side performs an attack on the ith protected games, which is oriented to a set of players (in the limit an ⃗⃗. asset, yi = 0 - otherwise, the variable elements are vector 𝑌 infinite number of players), each of which tends to optimize some functional. The proposed scheme may allow a separate C. Quality indicators node in MANETs to make security decisions without For a zero-sum game, the quality of two players is centralized administration. determined by the damage to the defense side. The damage In [14], a review of the existing solutions of game theory can be defined as follows: to network security problems, the article is an overview. The 𝑈(𝑋⃗, 𝑌 ⃗⃗) = 𝑈𝑚𝑎𝑥 (𝑌 ⃗⃗) − 𝑈пр (𝑋⃗, 𝑌 ⃗⃗)= classification of games according to various criteria is = ∑𝑖 ∈𝑀 𝑤𝑖 𝑦𝑖 − ∑𝑖 ∈𝑀 𝑝𝑝𝑟 𝑖 𝑤𝑖 𝑥𝑖 𝑦𝑖 , (1) presented: by the number of game steps (static, dynamic, ⃗⃗) = ∑𝑖 ∈𝑀 𝑤𝑖 𝑦𝑖 - the maximum damage that stochastic); on completeness of information about previous where 𝑈𝑚𝑎𝑥 (𝑌 moves of players; on the completeness of information about can be caused by the attacking side in the absence of the functions of winning other players. Various game models protection; are considered: models of cooperative games; models of 𝑈пр (𝑋⃗, 𝑌 ⃗⃗) = ∑𝑖 ∈𝑀 𝑝𝑝𝑟 𝑖 𝑤𝑖 𝑥𝑖 𝑦𝑖 - prevented damage by the non-cooperative games. Various combinations of game class defense side. attributes are described. D. Restrictions In [15], to assign security classes to objects of the Restrictions on the use of limited resources by the information system and to distribute data on these objects in protection side: order to reduce the dimension of the discrete optimization ∑𝑖 ∈𝑀 𝑎𝑖𝑘 𝑥𝑖 ≤ 𝑏𝑘 , ∀ 𝑘 ∈ 𝐿. (2) problem, an artificial admission of the optimization task to Restrictions on the use of limited resources by the the game of two players with non-conflicting interests is attacking side: used. One player is responsible for assigning security classes ∑𝑖 ∈𝑀 𝑐𝑖𝑘 𝑦𝑖 ≤ 𝑑𝑘 , ∀ 𝑘 ∈ 𝑆. (3) to objects, and the second is responsible for assigning data to Thus, when deciding each of the players with a fixed objects. The solution is sought for by Nash equilibrium. decision of the other player, it is necessary to solve the II. SETTING THE TASK OF ALLOCATING THE problem of linear Boolean programming. We will assume RESOURCES OF THE PROTECTION SYSTEM BETWEEN THE that the solutions consisting of all 1 are inadmissible by PROTECTED ASSETS restrictions. A. Basic reference data III. SADDLE POINT SEARCH ALGORITHMS Basic sets: The game model with a quality score (1) and restrictions 1) Z = {z1, z2, ..., zm} – the set of protected assets, M = {1,2, (2), (3) can be reduced to a game defined by the payment ..., m} – the set of indices of these assets. matrix. The dimension of this matrix can be quite large: the 2) R = {r1, r2, ..., rl} – the set of limited resources of the number of rows is equal to the number of admissible 𝑋⃗ defense, L = {1,2, ..., l} – the set of indices of these satisfying constraints (2) and the number of columns is equal resources. ⃗⃗ satisfying constraints (3). 3) N = {n1, n2, ..., ns} – the set of limited resources of the to the number of admissible 𝑌 Elements of the matrix are the values of the exponent (1) for 33 given 𝑋⃗ and 𝑌 ⃗⃗. In the case of a payment matrix, a saddle otherwise, for it we call the recursive function, instead of point is often sought in pure strategies or if it does not exist the parameter Num, we pass i + 1. in mixed strategies. To find solutions to solutions in mixed Step 3. Exit the recursive function. strategies for the payment matrix of the game, it is necessary The first algorithm works faster if the permissible to formulate a special problem of linear programming [14, solutions are greater 0, than 1. The second one works faster 15], for its solution one can use, for example, the simplex - otherwise. We can introduce the following rule: method. 𝑏 To reduce the dimension of the matrix, one can use the min ∑ 𝑘 < 0.5, then we use the first algorithm, 𝑘 ∈𝐿 𝑖 ∈𝑀 𝑎𝑖𝑘 notion of strategy dominance. Strategy B is dominated by otherwise, the second one. strategy A if, for any behavior of other players, the use of Calculating the values of the function for the vectors 𝑋⃗ strategy B leads to a worse outcome than the use of A. If and 𝑌⃗⃗, which determine the rows and columns of the matrix, there is some admissible vector 𝑋⃗ (or 𝑌 ⃗⃗) containing 0 and 1, one can find a saddle point in pure strategies, if it exists. If then the replacement in vector 1 by 0 , also gives the there is no saddle point in pure strategies, then it can be permissible 𝑋⃗ (or 𝑌 ⃗⃗), and the value of the exponent (1) will found in mixed strategies, solving the problem of linear not be reduced (or increased for 𝑌 ⃗⃗) for a given 𝑌 ⃗⃗ (or 𝑋⃗). programming [14, 15]. ⃗ ⃗ ⃗ Therefore, the initial vector 𝑋 (or 𝑌) is dominated by any IV. EXAMPLE OF SOLUTION OF THE PROBLEM vector obtained from it by replacing any 1 by 0. Therefore, it suffices to find the admissible vectors containing the Consider the solution of the problem of small dimension maximum number of ones for the construction of the matrix by the example of protection of mobile devices assets: the (the replacement of any 0 by 1 gives an inadmissible vector number of protected assets is 8, the number of defender's with respect to constraints). limited resources with the cost of protection is 4, the number Let us consider two recursive algorithms for searching of limited resources of the attack side is 1 (the cost of mutually unmodified admissible solutions for the vector 𝑋⃗ attack). Parameters of the protected assets: possible damage, (for the vector 𝑌 ⃗⃗, algorithms are similar). The first algorithm the cost of conducting attacks on assets, the probability starts with the initial vector 𝑋⃗ = ‖0, 0, … , 0‖Т , the second (possibility) of preventing attacks on assets are presented in algorithm starts with the initial vector 𝑋⃗ = ‖1, 1, … , 1‖Т . Table I. The values of possible damage and cost are given in conventional units. The parameters of the defender's limited A. A recursive algorithm for searching non-dominated resources, including the cost of protection, and the values of solutions, starting with a null vector the right-hand parts of the restrictions on the use of these Step 1. Set the initial solution 𝑋⃗ = ‖0, 0, … , 0‖Т , set resources are presented in Table II. Num = 0 (these parameters will be the input of the recursive For given initial data, the payment matrix constructed by algorithm or the parameters of the recursive function that the algorithms described above has a size of 49 x 6 (49 implements it). solutions for the defender, 6 solutions for the attacker). By checking the matrix and eliminating the dominant rows Step 2. Calling the recursive function, in this function, in (columns) [14, 15], the dimension of the matrix is reduced a loop to 13 x 6. There is no saddle point for the resulting matrix in for (int i = Num; i