-The game setting of the zero-sum problem for selecting the protected assets is considered. There are two players in the game: the defender and the forward. The attacker chooses assets for the attack; the defender chooses assets for defense. The task is formulated in such a way that each player must solve his own problem of linear Boolean programming. It is proposed to reduce this problem to a matrix game for which algorithms of finding a saddle point in pure strategies, if it exists, or in mixed strategies are known. In this case, the problem, as a rule, is a problem of large dimension, to reduce the dimension of the matrix, algorithms for the search of unmixed solutions that determine the rows and columns of the matrix are developed. An example of solving the problem of finding a saddle point in mixed strategies is presented, the probabilities for admissible solutions and the game price are assessed.
INTRODUCTION
Consider the game task of selecting protected security resources and selecting attacks on protected assets against attacking the resources of the defense and attack sides. We will use the concepts: the protected asset is what is protected, and the resource is what is used for protection (e.g. [1, 2]).
Protected assets can be: - Integrity, accessibility and confidentiality of data stored on computer facilities or mobile devices; - Integrity of applications, installed on the computer; - Others.
The resources of the protection system can be the cost of protection, processor time; RAM; disk storage; other resources. Consider the task of allocating resources between assets, while using the model of two players with zero sum. Game theory has been widely used to solve various problems related to the protection of information.
An algorithm for finding optimal solutions in convex distributed online problems was developed in [3]. A modification of the algorithm of the Arrow-Hurwicz method is proposed to search for a saddle point in order to fulfill the global network criterion of Savage, using the method of Lagrange multipliers. An application to computer network security in which service providers cooperate to detect the signature of malicious users is developed to illustrate the practical value of the proposed algorithm.
In [4], a routing algorithm is described in mobile sensor networks based on models of game theory. This algorithm is based on a dynamic Bayesian signaling game and the achievement of a perfect Bayesian equilibrium (PBE). The algorithm allows to protect nodes from anonymous user actions.
In [5] it is shown how evolutionary game theory can help in the organization's economy to optimize the costs of information security systems. In the work, information security breaches are described by possible economic losses. Two types of security violations are considered: targeted attacks and the manifestation of spontaneous (accidental) threats. The game considers the ratio of investments in information security and possible losses.
In [6], dynamic games with players that have incomplete information about the resources of other players, as applied to cyber physical systems, are considered. Also, the authors consider the denial-of-service attack and develop an algorithm to compute the saddle-point.
In [7], the application of the theory of games in steganography is considered. The authors note that this topic is practically not covered, since until recently adaptive attacks in the field of steganography have not been conducted. Two players are considered: the introduction player and the detection player. An algorithm for finding the saddle point in mixed strategies is proposed.
In [8], an optimal strategy for protecting the network using the Moving Target Defense (MTD) concept based on the Markov game was considered. The essence of MTD certain elements of the network change over time, making it difficult to "defeat" the target. The Markov decision-making process is used to describe the transitions between multistates of the network. Dynamic game is used to describe multiphase protection and attack steps in MTD conditions.
In [9], the authentication was investigated at the physical level, while using the radio channel information to detect spoofing attacks in multiple- input multiple-output (MIMO) systems. The authors represent the interaction between the receiver and the spoofing node as a zero-sum game.
In [10], the application of learning based on game theory for the analysis of large amounts of data is considered. This approach can be useful for analyzing social network data. The authors consider a linear game model of many players (agents) whose data is stored in a large repository; confidential information is associated with each agent. The model is continuous, the search for solutions satisfying the Nash criterion is considered.
In [11], the allocation of resources in multiple-access listening channels is considered. The model considers several users who want to transfer confidential data to the legitimate recipient. On the receiving side there is an eavesdropper who passively listens to the channel and tries to decode messages. The authors obtain a coarse correlated equilibrium, a Pareto point and a Nash bargaining solution.
In [12] is considered an effective solution to the stochastic zero-sum games with lack of players information about each other. The paper discusses the problem of revealing the player's own secret information to obtain the enemy's secret information and suggests strategies for solving it.
In [
In [
In [
II. SETTING THE TASK OF ALLOCATING THE RESOURCES OF THE PROTECTION SYSTEM BETWEEN THE
PROTECTED ASSETS
Basic sets: 1) Z = {z1, z2, ..., zm} – the set of protected assets, M = {1,2, ..., m} – the set of indices of these assets. 2) R = {r1, r2, ..., rl} – the set of limited resources of the defense, L = {1,2, ..., l} – the set of indices of these resources. 3) N = {n1, n2, ..., ns} – the set of limited resources of the attacking side, S = {1,2, ..., s} – the set of indices of these resources.
Parameters of elements of sets and its ratio: 1) wi≥0, ∀ i ∈ M - possible damage in case of violation of the security of the ith protected asset (asset value). 2) pnp i ∈ [0,1], ∀ i ∈ M - probability (or possibility) of preventing an attack on the ith asset while protecting. 3) aki ∈ [0,1), ∀ k ∈ L, i ∈ M - the normalized value of the kth restricted resource used to provide protection for the ith asset. The entire resource is considered equal to 1 4) bk ∈ [0,1], ∀ k ∈ L - the maximum normalized value of the kth restricted resource allocated for protection. 5) cki ∈ [0,1), ∀ k ∈ S, i ∈ M - the normalized value of the kth restricted resource of the attacking side used to attack the ith asset. The entire resource is considered equal to 1. 6) dk ∈ [0,1], ∀ k ∈ S - the maximum normalized value of the kth restricted resource of the attacking side.
For the defense, we introduce the Boolean variable xi ∈ {0,1}, ∀ i ∈ M, xi = 1 if the ith asset is protected, xi = 0 otherwise, the variable elements vector ⃗ . For a part of the attack, we introduce a similar variable yi ∈ {0,1}, ∀ i ∈ M, yi = 1, if the attack side performs an attack on the ith protected asset, yi = 0 - otherwise, the variable elements are vector ⃗⃗ . C. Quality indicators
For a zero-sum game, the quality of two players is determined by the damage to the defense side. The damage can be defined as follows: ( ⃗ , ⃗⃗ ) =
( ⃗⃗ ) − пр ( ⃗ , ⃗⃗ )= = ∑ ∈ − ∑ ∈ , (1) where ( ⃗⃗ ) = ∑ ∈ - the maximum damage that can be caused by the attacking side in the absence of protection; пр ( ⃗ , ⃗⃗ ) = ∑ ∈ - prevented damage by the defense side.
D. Restrictions
Restrictions on the use of limited resources by the protection side:
∑ ∈ ≤ , ∀ ∈ . (2)
Restrictions on the use of limited resources by the attacking side:
∑ ∈ ≤ , ∀ ∈ . (3)
Thus, when deciding each of the players with a fixed decision of the other player, it is necessary to solve the problem of linear Boolean programming. We will assume that the solutions consisting of all 1 are inadmissible by restrictions.
III.
The game model with a quality score (1) and restrictions
(2), (3) can be reduced to a game defined by the payment
matrix. The dimension of this matrix can be quite large: the
number of rows is equal to the number of admissible ⃗
satisfying constraints (2) and the number of columns is equal
to the number of admissible ⃗⃗ satisfying constraints (3).
Elements of the matrix are the values of the exponent (1) for
given ⃗ and ⃗⃗ . In the case of a payment matrix, a saddle
point is often sought in pure strategies or if it does not exist
in mixed strategies. To find solutions to solutions in mixed
strategies for the payment matrix of the game, it is necessary
to formulate a special problem of linear programming [
To reduce the dimension of the matrix, one can use the notion of strategy dominance. Strategy B is dominated by strategy A if, for any behavior of other players, the use of strategy B leads to a worse outcome than the use of A. If there is some admissible vector ⃗ (or ⃗⃗ ) containing 0 and 1, then the replacement in vector 1 by 0 , also gives the permissible ⃗ (or ⃗⃗ ), and the value of the exponent (1) will not be reduced (or increased for ⃗⃗ ) for a given ⃗⃗ (or ⃗ ). Therefore, the initial vector ⃗ (or ⃗⃗ ) is dominated by any vector obtained from it by replacing any 1 by 0. Therefore, it suffices to find the admissible vectors containing the maximum number of ones for the construction of the matrix (the replacement of any 0 by 1 gives an inadmissible vector with respect to constraints).
Let us consider two recursive algorithms for searching mutually unmodified admissible solutions for the vector ⃗ (for the vector ⃗⃗ , algorithms are similar). The first algorithm starts with the initial vector ⃗ = ‖0, 0, … , 0‖Т, the second algorithm starts with the initial vector ⃗ = ‖1, 1, … , 1‖Т. A. A recursive algorithm for searching non-dominated solutions, starting with a null vector
Step 1. Set the initial solution ⃗ = ‖0, 0, … , 0‖Т, set Num = 0 (these parameters will be the input of the recursive algorithm or the parameters of the recursive function that implements it).
Step 2. Calling the recursive function, in this function, in a loop
for (int i = Num; i <m; i ++).
Create a copy of the vector ⃗ , in the copy we assume that the element xi = 1, if the new vector is allowed by constraints (2), then we call the recursive function for it, instead of the Num parameter, we pass i + 1.
Step 3. If in a cycle all new vectors are inadmissible by the constraints (2), i.e. the recursive function has not been called once, then the original vector ⃗ is the desired one, put it in the list, exit from the recursive function.
B. A recursive algorithm for searching non-dominated solutions, starting with a unit vector
Step 1. Set the initial solution ⃗ = ‖1, 1, … , 1‖Т, set Num = 0 (these parameters will be the input of the recursive algorithm or the parameters of the recursive function that implements it).
Step 2. Calling the recursive function, in this function, in a loop
for (int i = Num; i <m; i ++).
Create a copy of the vector ⃗ , in the copy we assume that the element xi = 0, if the new vector is allowed by constraints (2), then it is the desired one, put it in the list, otherwise, for it we call the recursive function, instead of the parameter Num, we pass i + 1.
Step 3. Exit the recursive function.
The first algorithm works faster if the permissible solutions are greater 0, than 1. The second one works faster - otherwise. We can introduce the following rule: min < 0.5, then we use the first algorithm, ∈ ∑ ∈ otherwise, the second one.
Calculating the values of the function for the vectors ⃗
and ⃗⃗ , which determine the rows and columns of the matrix,
one can find a saddle point in pure strategies, if it exists. If
there is no saddle point in pure strategies, then it can be
found in mixed strategies, solving the problem of linear
programming [
IV.
Consider the solution of the problem of small dimension by the example of protection of mobile devices assets: the number of protected assets is 8, the number of defender's limited resources with the cost of protection is 4, the number of limited resources of the attack side is 1 (the cost of attack). Parameters of the protected assets: possible damage, the cost of conducting attacks on assets, the probability (possibility) of preventing attacks on assets are presented in Table I. The values of possible damage and cost are given in conventional units. The parameters of the defender's limited resources, including the cost of protection, and the values of the right-hand parts of the restrictions on the use of these resources are presented in Table II.
For given initial data, the payment matrix constructed by
the algorithms described above has a size of 49 x 6 (49
solutions for the defender, 6 solutions for the attacker). By
checking the matrix and eliminating the dominant rows
(columns) [
As a result of searching for a saddle point in mixed strategies by solving the linear programming problem, probabilities for the permissible solutions of the defender and the attacker are presented, presented in Table III. The price of the game in this case (winnings of the attacker and defender's loss) is 19,700 conventional units, which indicates the need to increase the resources allocated to the defense.
The game statement of the problem with a zero-sum of the defender and the attacker is provided with restrictions on the resources for selecting the defended assets by the defender and selecting the assets for attacking. It is proposed to reduce this problem to a matrix game for which the algorithms for finding the saddle point are known. To reduce the dimension of the matrix, algorithms for searching nondominant solutions that determine the rows and columns of the matrix are developed.
The reliability of the proposed solutions is based on the use of known proven algorithms, is confirmed by checking the found saddle point by calculating the price of the game on a given model. № 1. Integrity and data
availability on the device 2. Data privacy on the
device 3. Integrity and availability
of transmitted data 4. Confidentiality of
transmitted data 5. Application integrity on
the device 6. Prohibition of unauthorized installation of applications 7. Confidentiality of data on the device in case of loss or theft 8. Protect your camcorder from unauthorized use by applications Total allocated to attack ( 1) 10000 3000 8000 5000 8000 10000 8000 600 60 500 100 120 1000 500 1500 0,99 0,70 0,90 0,80 0,90 0,50 0,90 № 1. 2. 3. 4. 1. 2. 3. 4. 1. 2. 3. 4. 5. 6. 7. 8.
Total allocated for protection, ( , ∀ ∈ ) 0,0884 3,0300 x 10-16
Bykov A. Panfilov F. Zenkovich S. Model and methods of multicriteria selection of the security classes for objects in distributed information system and databases placement on objects. Voprosy kiberbezopasnosti [Cybersecurity issues], 2016, N 2(15), pp. 9-20. DOI: 10.21681/2311-3456-2016-2-9-20.
Chesnokov V. Application of the community allocation algorithm in the information confrontation in the social networks. Voprosy kiberbezopasnosti [Cybersecurity issues], 2017, N 1(19), pp. 37-44. DOI: 10.21681/2311-3456-2017-1-37-44.
Koppel A., Jakubiec F.Y., Ribeiro A. A Saddle Point Algorithm for Networked Online Convex Optimization. IEEE Transactions on Signal Processing. 2015. Vol. 63, iss. 19. P. 5149–5164. DOI: 10.1109/TSP.2015.2449255.
Paramasivan B., Prakash M., Kaliappan M. Development of a secure routing protocol using game theory model in mobile ad hoc networks. Journal of Communications and Networks. 2015. Vol. 17, iss. 1. P. 75–83. DOI: 10.1109/JCN.2015.000012.
Wang Q., Zhu J. Optimal information security investment analyses with the consideration of the benefits of investment and using evolutionary game theory. 2016 2nd International Conference on Information Management (ICIM). 2016. P. 105–109. DOI: 10.1109/INFOMAN.2016.7477542.
Gupta A., Langbort C., Başar T. Dynamic Games With Asymmetric Information and Resource Constrained Players With Applications to Security of Cyberphysical Systems. IEEE Transactions on Control of Network Systems. 2017. Vol. 4, iss. 1. P. 71–81. DOI: 10.1109/TCNS.2016.2584183.
Xiao Liang., Chen T., Han G., Zhuang W., Sun L. Channel-Based Authentication Game in MIMO Systems. 2016 IEEE Global Communications Conference (GLOBECOM). 2016. P. 1–6. DOI: 10.1109/GLOCOM.2016.7841657. [11] Shah S. Chaitanya A., Sharma V. Resource allocation in fading multiple access wiretap channel via game theoretic learning. 2016 Information Theory and Applications Workshop (ITA). 2016. P. 1–7.
DOI: 10.1109/ITA.2016.7888137. [12] Li L., Shamma J. Efficient computation of discounted asymmetric information zero-sum stochastic games. 2015 54th IEEE Conference on Decision and Control (CDC). 2015. P. 4531–4536. DOI: 10.1109/CDC.2015.7402927. bilinear