Algorithm for Determining Saddle Point in Game Theory Problem of Choosing Software for Information Security on Computer Network Servers Aleksandr Yu. Bykov1, Maksim V. Grishunin1, Evgenij G. Fedorov1 and Irina A. Markova1 1 Bauman Moscow State Technical University, 5/1 2nd Baymanskay ul., Moscow, 105005, Russia Abstract The game formulation of the problem of two players is presented: a defender and an attacker. The defender selects the information security software for the computer network servers, taking into account the importance of the processed information, and the attacker selects the possible types of attacks. The mathematical formulation of the problem is a discrete- continuous game, the set of solutions of the defender is discrete, and the set of solutions of the attacker is continuous. The game is a zero-sum game, with the defender's damage used as a quality indicator. The defender, given the attacker's solution, solves the Boolean programming problem, and the attacker, given the defender's solution, solves the linear programming problem. An algorithm for finding the saddle point in a mixed strategy for the defender, in a pure strategy for the attacker, based on reducing the continuous problem of the attacker to a discrete one, is proposed. The algorithm is based on the ideas of the Brown- Robinson method, but without explicit construction of the game matrix. To reduce the computational resources of the processor required for the operation of the algorithm, it is proposed that after a given number of steps a new solution is not obtained, not to solve optimization problems, but to search for solutions by brute force among the previously found solutions. An example of solving the problem is given. Keywords 1 Information security, discrete-continuous game, zero-sum game, boolean programming, linear programming, mixed strategy, pure strategy 1. Introduction Mathematical models originating from game theory frequently arise when solving different problems in information security field. The most common model class has two players: defender and attacker, but there can be more players. Let’s look at some examples. In [1] dynamic game theory is used to protect the privacy of medical data in internet of things. In [2] attack and defense are viewed as a dynamic process in real time, a differential game theory attack-defense model for choosing a strategy of network defense is used. In [3] dynamic games are used to discover Advanced persistent threats (APTs). Two players are making subjective decisions about choosing scanning interval and attack interval. In [4] a multi-stage dynamic game of defender and attacker for resource-heavy discovery of Advanced persistent threats (APTs). The game evolves on an information flow graph, whose nodes are processes and objects (e.g., file, network endpoints) in the system and the edges capture the interaction between different processes and objects. In [5] a model for deceiving a potential attacker is considered. The defender is using differential mechanisms for scrambling system configurations. The attacker is using Bayesian approach for outputting real system configurations. BIT-2021: XI International Scientific and Technical Conference on Secure Information Technologies, April 6-7, 2021, Moscow, Russia EMAIL: abykov@bmstu.ru (A. 1); grishunin-mv@ya.ru (A. 2); fedorov.evg.msu@gmail.com (A. 3); gurina.irina.94@gmail.com (A. 4) ORCID: 0000-0001-6336-5603 (A. 1); 0000-0001-9544-017X (A. 2); 0000-0003-2261-9691 (A. 3); 0000-0002-2297-5840 (A. 4) © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 22 In [6], an equilibrium is sought in a two-level hierarchical game with non-opposite interests of many players. A problem of protecting internet of things users from risks of breaching information security is studied. Top level contains a centralized defender, while defenders with rights of ordinary users are placed on the bottom level. Both centralized and decentralized models are studied. In [7] a problem of protecting cyber-physical power systems from exploitation risks is studied. Time delay of system recovery and distributed denial of service are considered as risks. A three stage defender-attacker-defender model of mathematical programming based on dynamic game theory with complete information is proposed. In [8] a problem of data transmission in noisy channels is studied. A trade-off between transmission speed and reliability is sought. Stochastic-mean-field-game is considered. Message codes play the role of agents. In [9] a game between a system administrator and an attacker is studied. This is an asymmetric information game with zero sum between two players that are unequally informed about the game: informed defender and uninformed attacker. In [10] a mobile ad-hoc network in which network nodes are in motion is studied. Evolutionary games for stimulating cooperation between mobile modes are used. In [11] a perspective theory describing human behavior during risk-involved decision making is used for discovering Advanced Persistent Threats. The game uses Nash equilibrium criterion. In [12] Nash equilibrium is searched in order to ensure performance of blockchain system. In [13] a fast defense system against DDoS and port scanning attacks in software-defined networking is studied. Three approaches to attack discovery are compared: particle swarm optimization, multi-layer neural network and discrete wavelet transform. In most cases considered models can be either discrete or continuous. Combined discrete- continuous models can also be used. In [14] a coalition-free game with conflicting interests in the data transmission network with possible loss of communication is studied. Data source and network nodes are considered as players. In order to reduce transmission delays, hosts are stimulated by the source to cache files. A search for equilibrium Nash states is carried out, both for pure/mixed strategies and for discrete/continuous sets of strategies. In [15] a game between intruder and subjects responsible for security, who exchange data on the network, is studied. Data confidentiality breach is possible during this exchange. The gains from cooperation and loss of confidentiality during information exchange are measured. Both discrete and continuous games are considered. Some other mathematical models that are applicable to information security problems are studied in [16-25]. A discrete-continuous game of choosing which software to install on network servers for information security is studied below. It takes into consideration the importance of data stored and processed on these servers. The problem under consideration is relevant, since there are many different software tools for protecting information that have different protection efficiency and require different resources. Because of this, the problem of choosing these tools arises, and defining this problem in terms of game theory allows us to take into account possible actions of the attacking side. The goal of this paper is to provide an information security specialist with mathematical software, that would take into account the importance degree of processed information and actions of the attacking side, for justifying the choice of information security software. The main tasks of the paper are: formulating mathematical game theory problem of choosing software; proposing algorithms for solving it, carrying out computational experiments; deriving conclusion. 2. Problem Description Let us consider a distributed computer system comprising many servers and providing different services on the network. Servers run some target tasks for which they are intended. Required software 23 including OS and applications is installed on the servers. There exists a minimal configuration of application and system programs enabling each server to run its target tasks. These programs are implemented as processes. Minimal configuration requires availability of certain computing resources on server (cpu time, memory, disk space, networks). Besides the main processes (required to run target tasks) maintenance processes are being launched. These processes can be for example security enforcing processes such as antivirus software, DDoS prevention tools, data integrity control programs, privacy programs, programs for protection against unauthorized network connections, etc. Auxiliary or maintenance processes also have some CPU time and memory requirements and cannot be all run at the same time due to lack of resources, however usually there is no reason to run them all. The problem arises of choosing running processes and installed programs. Server information resources are subject to attacks, which implement threats with different possible goals. Several types of attacks can be distinguished, for example DDoS attacks, confidential information access attacks, data distortion attacks (integrity violation), etc. Estimates of potential damage for server owner in case of attack success exist for each server depending on importance of data stored and processed on a server. Using auxiliary processes can prevent damage to servers from incoming attacks completely, or can partially mitigate their consequences (possible damage). Let us consider the problem of choosing auxiliary processes from the standpoint of game theory. There is a defender, whose solution to the problem consists choosing which auxiliary processes to run on each server, and an attacker, whose solution consists of choosing attack types. Possible limitations on attacker resources can also be considered, if such information is available. Let’s consider a game of two players, we will regard defender damage estimate as an indicator of choice for both players, therefore the game is a zero sum game. The problem can be summarized as follows. Given: A set of servers running target tasks. A set of auxiliary processes for enforcing information security. A set of possible attack types that can be carried out on systems’ information resources. A damage estimate in case of attack success is defined for each server and each attack type depending on importance of data stored and processed on a server. The following computational resource requirements are defined for each server and each auxiliary process: • CPU load ratio that depends on the servers’ computational power • Memory usage • Other resources are allowed A “process cost” is defined in case a corresponding program has to be purchased. For each server its memory size and computational power, which can be allocated to auxiliary processes (while taking into account resources needed to run main processes), as well as total defender funds for buying software are defined. For each server and type of attack a damage estimate in case of attack success is defined. For each auxiliary process and attack type the probability or possibilities of prevention (in terms of fuzzy sets) of an attack or a possible damage mitigation value if the process is running are defined. For each attach type financial burden on attacker for carrying it out are defined. Other attacker resource (for example computational resources) costs estimates can be considered if such information is available. Limit on attackers’ financial resources is defined (limit on other types of resources can be considered if such information is available). Required: In order to minimize possible damage for defender – determine which auxiliary processes should be run on each server, considering possible attacker actions, while also meeting requirements on servers’ computational power, memory and possibly other server resources, and on defenders’ financial resources needed for auxiliary software purchase. 24 3. Mathematical Formulation of the Problem 3.1. Initial data 1. 𝑆𝑆 = {𝑠𝑠1 , 𝑠𝑠2 , … , 𝑠𝑠𝑛𝑛 } – set of servers on a distributed computer system, 𝑁𝑁 = {1,2, … , 𝑛𝑛} - set of indices enumerating these servers. 2. 𝐴𝐴 = {𝑎𝑎1 , 𝑎𝑎2 , … , 𝑎𝑎𝑚𝑚 } – set of attack types (implementations of security threats) on the system, 𝑀𝑀 = {1,2, … , 𝑚𝑚} - set of indices enumerating these attack types. 3. 𝛱𝛱 = {𝜋𝜋1 , 𝜋𝜋2 , … , 𝜋𝜋𝜆𝜆 } – set of auxiliary processes, which can be run on servers for security enforcement, Λ = {1,2, … , λ} – set of indices enumerating these processes. (𝑑𝑑) (𝑑𝑑) (𝑑𝑑) (𝑑𝑑) 4. 𝑅𝑅 = �𝑟𝑟1 , 𝑟𝑟2 , … , 𝑟𝑟𝑙𝑙(𝑑𝑑) � – set of limited defender resources, 𝐿𝐿(𝑑𝑑) = {1,2, … , 𝑙𝑙 (𝑑𝑑) } - set of indices enumerating these resources. (𝑑𝑑) Resource set 𝑅𝑅 is divided into two disjoint subsets 𝑅𝑅 = 𝑅𝑅 (𝑝𝑝𝑝𝑝) ∪ 𝑅𝑅 (𝑠𝑠ℎ) , 𝑅𝑅 (𝑝𝑝𝑝𝑝) being a set of private server resources (each server has its own resources), and 𝑅𝑅 (𝑠𝑠ℎ) being a set of shared server resources that are distributed among all servers. We introduce separate enumeration for private and shared resources with two sets of resource indices 𝐿𝐿(𝑝𝑝𝑝𝑝) = {1,2, … , 𝑙𝑙 (𝑝𝑝𝑝𝑝) } and 𝐿𝐿(𝑠𝑠ℎ) = {1,2, … , 𝑙𝑙 (𝑠𝑠ℎ) } respectively. (𝑎𝑎) (𝑎𝑎) (𝑎𝑎) 5. 𝑅𝑅 (𝑎𝑎) = {𝑟𝑟1 , 𝑟𝑟2 , … , 𝑟𝑟𝑙𝑙(𝑎𝑎) } – set of limited attacker resources. 𝐿𝐿(𝑎𝑎) = {1,2, … , 𝑙𝑙 (𝑎𝑎) } - set of indices enumerating these resources. 3.2. Set elements parameters and relations between them 1. 𝑤𝑤𝑖𝑖𝑖𝑖 ≥ 0, ∀𝑖𝑖 ∈ 𝑁𝑁, 𝑗𝑗 ∈ 𝑀𝑀 – estimate of damage to defender on i-th server if attacker was successful in carrying out j-th type of attack. 2. 𝑝𝑝𝑗𝑗𝑗𝑗 ∈ [0,1], ∀𝑗𝑗 ∈ 𝑀𝑀, 𝑘𝑘 ∈ 𝛬𝛬 – probability (or possibility) of preventing j-th attack (threat implementetion) if k-th process is running on any server or defender damage mitigation value. (𝑝𝑝𝑝𝑝) 3. 𝑣𝑣𝑗𝑗𝑗𝑗𝑗𝑗 ≥ 0, ∀𝑗𝑗 ∈ 𝐿𝐿(𝑝𝑝𝑝𝑝) , 𝑘𝑘 ∈ 𝛬𝛬, 𝑖𝑖 ∈ 𝑁𝑁 – value of j-th private resource (performance or memory) required to run k-th process on i-th server. (𝑝𝑝𝑝𝑝) 4. 𝑉𝑉𝑗𝑗𝑗𝑗 ≥ 0, ∀𝑗𝑗 ∈ 𝐿𝐿(𝑝𝑝𝑝𝑝) , 𝑖𝑖 ∈ 𝑁𝑁 – maximum value of j-th private resource on i-th server, that can be spent on auxiliary processes, taking into account the ammount of the resource required to run main processes running target tasks. (𝑠𝑠ℎ) 5. 𝑣𝑣𝑗𝑗𝑗𝑗𝑗𝑗 ≥ 0, ∀𝑗𝑗 ∈ 𝐿𝐿(𝑠𝑠ℎ) , 𝑘𝑘 ∈ 𝛬𝛬, 𝑖𝑖 ∈ 𝑁𝑁 – value of j-th shared resource (for example, financial) required to run k-th process on i-th server. (𝑠𝑠ℎ) 6. 𝑉𝑉𝑗𝑗 ≥ 0, ∀𝑗𝑗 ∈ 𝐿𝐿(𝑠𝑠ℎ) – maximum value of j-th shared resource for all servers, that can be used for auxiliary processes. 7. We will combine some computer processes (applications) into homogeneous groups, for each group it makes sense to install only one of applications belonging to it. For example, There can be several antivirus applications, etc. 𝐺𝐺 = {1,2, … , 𝑔𝑔} – indices of these groups. For their definition let’s introduce a boolean matrix 𝐵𝐵< 𝜆𝜆 𝑥𝑥 𝑔𝑔> ‖𝑏𝑏𝑘𝑘𝑘𝑘 ‖, ∀ 𝑘𝑘 ∈ Λ, 𝑖𝑖 ∈ 𝐺𝐺, 𝑏𝑏𝑘𝑘𝑘𝑘 = 1 if k-th application belongs to i-th group and 𝑏𝑏𝑘𝑘𝑘𝑘 = 0 if otherwise. (𝑎𝑎) 8. 𝑣𝑣𝑘𝑘𝑘𝑘𝑘𝑘 ≥ 0, ∀𝑘𝑘 ∈ 𝐿𝐿(𝑎𝑎) , 𝑗𝑗 ∈ 𝑀𝑀, 𝑖𝑖 ∈ 𝑁𝑁 - value of k-th attacker resource required for j-th attack type on i-th server. (𝑎𝑎) 9. 𝑉𝑉𝑘𝑘 ≥ 0, ∀𝑘𝑘 ∈ 𝐿𝐿(𝑎𝑎) - maximum quantity of k-th attacker resource, that he can use for all attack types (only financial resource can be considered in the simplest case). 3.3. Parameters Let’s introduce a boolean value 𝑥𝑥𝑘𝑘𝑘𝑘 ∈ {0,1}, ∀𝑘𝑘 ∈ 𝛬𝛬, 𝑖𝑖 ∈ 𝑁𝑁, for the defender, 𝑥𝑥𝑘𝑘𝑘𝑘 = 1 if k-th process is running on i-th server and 𝑥𝑥𝑘𝑘𝑘𝑘 = 0 otherwise. These variables form the vector 𝑋𝑋⃗. 25 Let’s introduce a value 𝑦𝑦𝑖𝑖𝑖𝑖 ∈ [0,1], ∀𝑖𝑖 ∈ 𝑁𝑁, 𝑗𝑗 ∈ 𝑀𝑀 for the attacker. Its value can be interpreted as a probability or a possibility (in terms of fuzzy sets) of carrying out j-th attack type on i-th server. These variables form the vector 𝑌𝑌�⃗. 3.4. Players indicators During damage calculation we will assume that probability (safety degree in case of fuzzy description) of defending i-th server from j-th attack type while using several auxiliary processes is determined by a process with maximum probability: 𝑃𝑃𝑖𝑖𝑖𝑖 (𝑋𝑋⃗) = 𝑚𝑚𝑚𝑚𝑚𝑚 {𝑝𝑝𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 }, ∀𝑗𝑗 ∈ 𝑀𝑀, 𝑖𝑖 ∈ 𝑁𝑁. 𝑘𝑘∈𝛬𝛬 Therefore, an estimate of mitigated damage on all servers is 𝑈𝑈пр (𝑋𝑋⃗, 𝑌𝑌 �⃗) = ∑𝑖𝑖∈𝑁𝑁 ∑𝑗𝑗∈𝑀𝑀 𝑤𝑤𝑖𝑖𝑖𝑖 𝑃𝑃𝑖𝑖𝑖𝑖 (𝑋𝑋⃗)𝑦𝑦𝑖𝑖𝑖𝑖 = ∑𝑖𝑖∈𝑁𝑁 ∑𝑗𝑗∈𝑀𝑀 𝑤𝑤𝑖𝑖𝑖𝑖 𝑚𝑚𝑚𝑚𝑚𝑚 {𝑝𝑝𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 }𝑦𝑦𝑖𝑖𝑖𝑖 . 𝑘𝑘∈𝛬𝛬 The estimate of the full damage to the defender is given by a difference of estimate of maximum damage (without any defenses) and mitigated damage: 𝑈𝑈�𝑋𝑋⃗, 𝑌𝑌 �⃗� = � � 𝑤𝑤𝑖𝑖𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 − � � 𝑤𝑤𝑖𝑖𝑖𝑖 𝑚𝑚𝑚𝑚𝑚𝑚 �𝑝𝑝𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 �𝑦𝑦𝑖𝑖𝑖𝑖 (1) 𝑘𝑘∈𝛬𝛬 𝑖𝑖∈𝑁𝑁 𝑗𝑗∈𝑀𝑀 𝑖𝑖∈𝑁𝑁 𝑗𝑗∈𝑀𝑀 = � � 𝑤𝑤𝑖𝑖𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 �1 − 𝑚𝑚𝑚𝑚𝑚𝑚 �𝑝𝑝𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 ��. 𝑘𝑘∈𝛬𝛬 𝑖𝑖∈𝑁𝑁 𝑗𝑗∈𝑀𝑀 Defenders’ goal is to minimize this indicator, attackers’ – to maximize. 3.5. Limitations Conditions for defender Conditions on private resource usage on each server: � (𝑝𝑝𝑝𝑝) 𝑣𝑣𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 ≤ 𝑉𝑉𝑗𝑗𝑗𝑗 (𝑝𝑝𝑝𝑝) , ∀𝑗𝑗 ∈ 𝐿𝐿(𝑝𝑝𝑝𝑝) , 𝑖𝑖 ∈ 𝑁𝑁. (2) 𝑘𝑘∈𝛬𝛬 Condition on shared resource usage for all servers: �� (𝑠𝑠ℎ) 𝑣𝑣𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 ≤ 𝑉𝑉𝑗𝑗 (𝑠𝑠ℎ) , ∀𝑗𝑗 ∈ 𝐿𝐿(𝑠𝑠ℎ) . (3) 𝑖𝑖∈𝑁𝑁 𝑘𝑘∈𝛬𝛬 Condition limiting number of applications for each group to one on any server: � 𝑏𝑏𝑘𝑘𝑘𝑘 𝑥𝑥𝑘𝑘𝑘𝑘 ≤ 1, ∀𝑖𝑖 ∈ 𝑁𝑁, 𝑗𝑗 ∈ 𝐺𝐺. (4) 𝑘𝑘∈𝛬𝛬 Conditions for attacker Condition on usage of attackers resources required for carrying out attacks: �� (𝑎𝑎) (𝑎𝑎) 𝑣𝑣𝑘𝑘𝑘𝑘𝑘𝑘 𝑦𝑦𝑖𝑖𝑖𝑖 ≤ 𝑉𝑉𝑘𝑘 , ∀𝑘𝑘 ∈ 𝐿𝐿(𝑎𝑎) . (5) 𝑖𝑖∈𝑁𝑁 𝑗𝑗∈𝑀𝑀 Presented formulation of the problem with indicator given by (1) and conditions for defender (2)- (4) and attacker (5) is a mixed discrete-continuous zero sum game. Defender is solving a boolean programming problem with indicator (1) being non-linear for 𝑋𝑋⃗ and conditions (2)-(4) assuming fixed �⃗, while attacker is solving a linear programming problem with indicator (1) (non- attackers’ solution 𝑌𝑌 linear for 𝑌𝑌) and conditions (5) assuming fixed 𝑋𝑋⃗. �⃗ 4. Saddle Point Search Algorithm For a game of two players with zero sum equilibrium state is determined by games’ saddle point. For a continuous game of two players, in the case where possible player choice sets are convex and target function is linear, saddle point always exists for player indicator function [26]. In the discrete case, if player choice sets are finite, the game can be reduced to a matrix game [27]. For a matrix 26 game a saddle point can both be present or not present for pure strategies, but always exists for mixed strategies (a pure strategy is a special case of a mixed strategy). 4.1. Justification for saddle point existence in a discrete-continuous problem The defenders’ choices set is finite, while attackers’ choices set is continuous. Analogous to [27], because attacker is solving a linear programming problem and this games’ solution lies on a vertex of a polyhedron of possible choices with number of such vertices being finite, a continuous problem can be reduced to discrete one, if one considers polyhedron vertices as solutions. In this case the problem can be reduced to a matrix game in which a saddle point must always exist for mixed strategies. 4.2. Description of saddle point search algorithm using ideas from Brown- Robinson method The idea of Brown-Robinson method is based on each player solving consecutive problems, and using total accumulated win or loss as the indicator. For multiple solutions of these problems a probability of each solution is estimated, with combination of those estimates determining a mixed strategy. Analogous to [26], the attacker with continuous solution set should calculate average �Y⃗ among set of obtained solutions. For the defender we get probability estimates of obtaining each solution. �⃗ (1) , 𝑌𝑌 Let 𝑌𝑌 �⃗ (2) , … , 𝑌𝑌 �⃗ (𝑔𝑔) be a sequence of solutions that the attacker obtains while optimizing indicator (1), then the defender on (𝑔𝑔 + 1)-th step must solve the problem of minimizing indicator: 𝑔𝑔 𝑔𝑔 (6) (𝑔𝑔+1) ⃗ �⃗ (𝑒𝑒) ) = � � � 𝑤𝑤𝑖𝑖𝑖𝑖 𝑦𝑦 (𝑒𝑒) (1 − 𝑚𝑚𝑚𝑚𝑚𝑚 {𝑝𝑝𝑗𝑗𝑗𝑗 𝑥𝑥𝑘𝑘𝑘𝑘 }), 𝑈𝑈з (𝑋𝑋) = � 𝑈𝑈(𝑋𝑋⃗, 𝑌𝑌 𝑖𝑖𝑖𝑖 𝑘𝑘∈𝛬𝛬 𝑒𝑒=1 𝑒𝑒=1 𝑖𝑖∈𝑁𝑁 𝑗𝑗∈𝑀𝑀 (𝑒𝑒) �⃗ (𝑒𝑒) where 𝑦𝑦𝑖𝑖𝑖𝑖 are components of vector 𝑌𝑌 Let 𝑋𝑋⃗ (1) , 𝑋𝑋⃗ (2) , … , 𝑋𝑋⃗ (𝑔𝑔) be a sequence of solutions that the defender obtains while optimizing indicator (1), then the attacker on (𝑔𝑔 + 1)-th step must solve the problem of maximizing indicator: 𝑔𝑔 𝑔𝑔 (7) (𝑔𝑔+1) �⃗ �⃗) = � � � 𝑤𝑤𝑖𝑖𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 (1 − 𝑚𝑚𝑚𝑚𝑚𝑚 {𝑝𝑝𝑗𝑗𝑗𝑗 𝑥𝑥 (𝑒𝑒) }), 𝑈𝑈н (𝑌𝑌) = � 𝑈𝑈(𝑋𝑋⃗ , 𝑌𝑌(𝑒𝑒) 𝑘𝑘𝑘𝑘 𝑘𝑘∈𝛬𝛬 𝑒𝑒=1 𝑒𝑒=1 𝑖𝑖∈𝑁𝑁 𝑗𝑗∈𝑀𝑀 (𝑒𝑒) ⃗ (𝑒𝑒) where 𝑥𝑥𝑘𝑘𝑘𝑘 are components of vector 𝑋𝑋 . The problem with indicator (6) is a boolean programming problem for the defender. As indicator (6) is linear on components of 𝑌𝑌 �⃗ (𝑒𝑒) , therefore when optimizing we can use a middle point among vectors 𝑌𝑌�⃗ , 𝑌𝑌 (0) �⃗ , … , 𝑌𝑌 (1) �⃗ (𝑔𝑔) instead of their first sum. The problem with indicator (7) is a linear programming problem for the attacker. Let’s introduce a definition for the middle point, obtained on g initial algorithm steps. We denote solutions obtained on each of g initial algorithm steps for defender as 𝑌𝑌 �⃗ (1) , 𝑌𝑌 �⃗ (2) , … , 𝑌𝑌 �⃗ (𝑔𝑔) , then the middle point for attacker can be written as: 𝑔𝑔 1 (8) �⃗ 𝑌𝑌 (𝑚𝑚𝑚𝑚𝑚𝑚) = � 𝑌𝑌 �⃗ (𝑒𝑒) , 𝑔𝑔 𝑒𝑒=1 27 4.3. Let’s Formulate the Saddle Point Search Algorithm Step 0. We assume 𝑌𝑌 �⃗ (𝑠𝑠𝑠𝑠𝑠𝑠) = ‖0,0, … ,0‖𝑇𝑇 (total vector for calculation sum ∑𝑔𝑔𝑒𝑒=1 𝑌𝑌 �⃗ (𝑒𝑒) ), 𝑋𝑋⃗ (0) = ‖0,0, … ,0‖𝑇𝑇 - initial solution of the defender, any solution can be chosen, vector map 𝑋𝑋⃗ is empty. This map has vector 𝑋𝑋⃗ (𝑘𝑘) as key, and number of 𝑋𝑋⃗ occurrences in different steps of the algorithm as values. Step k (k=1, 2, 3, …). We determine 𝑌𝑌 �⃗ (𝑘𝑘) with 𝑋𝑋⃗ vector map obtained on current step, by searching linear programming problem for the attacker, maximize indicator (7) (for k=1 we maximize (𝑘𝑘) �⃗ (𝑘𝑘) indicator (1) for 𝑋𝑋⃗ = 𝑋𝑋⃗ (0)). Attackers’ quality indicator value we denote as 𝑈𝑈н (𝑌𝑌 ), we assume �⃗ 𝑌𝑌 (𝑠𝑠𝑠𝑠𝑠𝑠) �⃗ (𝑠𝑠𝑠𝑠𝑠𝑠) = 𝑌𝑌 𝑌𝑌 �⃗ (𝑠𝑠𝑠𝑠𝑠𝑠) + 𝑌𝑌 �⃗ (𝑘𝑘) , 𝑌𝑌 �⃗ (𝑚𝑚𝑚𝑚𝑚𝑚) = . 𝑘𝑘 We determine 𝑋𝑋⃗ (𝑘𝑘) for fixed 𝑌𝑌 �⃗ (𝑚𝑚𝑚𝑚𝑚𝑚) by solving a boolean programming problem for the defender (𝑘𝑘+1) ⃗ (𝑘𝑘) with indicator (6). Defenders’ quality indicator value we denote as 𝑈𝑈з (𝑋𝑋 ), obtained 𝑋𝑋⃗ (𝑘𝑘) we include into defender’s solution map. From second step onward we check the stopping criterion. If it is met, we stop the algorithm, obtained attackers’ solution - 𝑌𝑌 �⃗ (𝑚𝑚𝑚𝑚𝑚𝑚) , using obtained map for 𝑋𝑋⃗ vectors we calculate probability estimates for each vector in map, this will be the defenders’ solution in mixed strategies. Pair of defenders’ and attackers’ solutions comprises an approximated saddle point. If stopping criterion is not met, we continue with the next step. (𝑘𝑘) (𝑘𝑘+1) 𝑈𝑈 �⃗ (𝑘𝑘) ) (𝑌𝑌 𝑈𝑈 �⃗ (𝑘𝑘) ) (𝑋𝑋 The condition | н − з | < 𝜀𝜀 can be used as a stopping criterion, where ε - some 𝑘𝑘−1 𝑘𝑘 relatively small positive value, determining algorithm error, ε can be chosen as a percentage of the (𝑘𝑘) 𝑈𝑈 �⃗ (𝑘𝑘) � 𝑈𝑈з(𝑘𝑘+1) �𝑋𝑋 �𝑌𝑌 �⃗ (𝑘𝑘) � value 𝑚𝑚𝑚𝑚𝑚𝑚 � н 𝑘𝑘−1 , 𝑘𝑘 �. If the need arises, the algorithm can be reformulated thus, that on each step the optimization problem for the defender would be solved first, and for attacker – second. 4.4. Ways to reduce the required computing resources for algorithm and increase its precision The Described algorithm requires substantial computational resources starting from certain dimension of the problem, because on each step the defender has to solve boolean programming problem with exponential computational complexity. As shown by computational experiments, obtained solutions start to repeat on certain step, i.e. for a given relatively large step count no new solutions were obtained for both attacker and defender (attackers’ solutions can also be saved in a map), similar approach was used in [27]. In this case we can stop solving optimization tasks, and start looking for solutions among obtained ones using brute force. If there aren’t too many obtained solutions in maps, we can compose a usual game matrix from them by filling it with indicator values for each solution pair for defender and attacker, and then solve this problem precisely or approximately by using this matrix. 5. Example Table 1 shows the initial data obtained by the pseudorandom number generator. In the example, the number of objects is 5, the number of applications is 9, the number of threats is 3, for example, integrity, availability, and privacy violations. 28 Table 1 Source data for the task obtained by the pseudorandom number generator Threats Threat damage Objects Threat 1 Threat 2 Threat 3 Object 1 4580.43 3197.33 2444.14 Object 2 1205.57 4030.37 2383.47 Object 3 4378.77 4617.79 3061.22 Object 4 2747.12 3145.94 4061.98 Object 5 3529.50 2822.08 4833.49 Applications Applications (threat prevention probabilities) 1 2 3 4 5 6 7 8 9 Threats Threat 1 0.79 0.96 0.73 0.77 0.71 0.91 0.71 0.83 0.91 Threat 2 0.92 0.77 0.97 0.87 0.73 0.90 0.98 0.71 0.80 Threat 3 0.73 0.72 0.81 0.71 0.90 0.92 0.83 0.73 0.76 Applications Application groups Groups Application numbers Group 1 1, 4, 7 Group 2 2, 5, 8 Group 3 3, 6, 9 Applications Applications (defender shared resource consumption) Objects 1 2 3 4 5 6 7 8 9 Object 1 10.55 29.69 23.07 38.00 25.58 13.02 38.19 26.11 14.26 Object 2 27.37 15.60 27.56 23.66 33.65 26.19 28.81 36.90 34.97 Object 3 23.34 21.67 22.60 33.16 18.23 22.43 42.60 10.81 18.94 Object 4 39.41 34.07 49.80 39.66 30.45 22.33 37.83 26.25 31.22 Object 5 20.69 34.03 44.32 15.93 13.37 24.97 16.15 31.53 38.03 Total resource 250.53 Defender's private resource (one resource) Applica- Applications (private resource consumption for objects) Total tions 1 2 3 4 5 6 7 8 9 stock Objects Object 1 38.88 18.48 41.78 27.36 18.82 35.81 42.72 12.31 20.72 51.66 Object 2 39.64 43.36 11.90 23.73 46.27 33.48 40.73 12.30 37.69 62.34 Object 3 41.08 32.75 30.57 43.33 32.18 26.99 10.35 21.28 12.19 53.33 Object 4 28.28 13.78 15.12 20.27 29.39 32.05 42.84 47.70 20.65 61.30 Object 5 21.40 33.88 11.78 33.52 37.61 30.60 16.25 44.09 30.26 54.10 Threats Threats, resource consumption of the attacker for the implementation Objects of threats 1 2 3 Object 1 13.67 38.20 18.03 Object 2 49.22 30.85 38.59 Object 3 42.70 32.79 22.24 Object 4 13.90 21.28 44.87 Object 5 38.48 39.61 24.97 Total resource 234.70 29 The results of solving the problem are presented in Table 2. The table shows the saddle point: one solution for the attacker (the middle point found by the algorithm) and three solutions for the defender with estimates of their probabilities (a mixed strategy). The estimate of the indicator value is 2719.71. Table 2 Results of solving the task Intruder's solution 1.00 0.39 1.00 0.00 0.00 0.00 1.00 0.00 1.00 0.47 1.00 0.71 1.00 0.00 1.00 Defender's solutions 00001 00001 00011 00010 00010 00000 00000 01000 01000 00000 00000 00000 00000 01000 01000 10101 10111 10111 01110 00100 00100 00000 00000 00000 00000 00000 00000 Probabilities of 0.10 0.80 0.10 solutions 6. Conclusion The report considers the mathematical formulation of the problem of choosing software protection tools for a server system. The problem is a discrete-continuous zero-sum game of two players: a defender and an intruder. The set of decisions of the defender is discrete and finite, the set of decisions of the attacker is continuous, including the uncertainty of the actions of the attacker from the point of view of the defender. The defender must solve the Boolean programming problem, and the intruder must solve the linear programming problem. An algorithm for finding a saddle point for a defender in mixed strategies, for an intruder in pure strategies is proposed. The algorithm is based on reducing the continuous problem for the attacker to a discrete one and is based on the ideas of the Brown-Robinson method. Computational experiments were carried out that demonstrated the efficiency of the algorithm, and a method was proposed to reduce the computational complexity of the algorithm by switching from solving optimization problems to finding solutions among previously found ones, after the solutions are repeated at a given number of steps. The use of the proposed algorithm allows using software protection tools in the case of restrictions on various resources to significantly reduce the damage to the protection side from various types of attacks. The reliability of the obtained results is confirmed by the correctness of the mathematical formulation of the problem, an explicit meaningful interpretation of both the problem statement and the obtained solutions, as well as by experimental verification of the obtained solutions to meet the required criteria. 30 7. References [1] Fanyu Kong, Yufeng Zhou, Bin Xia, Li Pan, Limin Zhu. A Security Reputation Model for IoT Health Data Using S-AlexNet and Dynamic Game Theory in Cloud Computing Environment. IEEE Access, 2019, vol. 7, pp. 161822-161830. DOI: 10.1109/ACCESS.2019.2950731. [2] Hengwei Zhang, Lv Jiang, Shirui Huang, Jindong Wang, Yuchen Zhang. Attack-Defense Differential Game Model for Network Defense Strategy Selection. IEEE Access, 2018, vol. 7, pp. 50618-50629. DOI: 10.1109/ACCESS.2018.2880214. [3] Liang Xiao, Dongjin Xu, Narayan B. Mandayam, H. Vincent Poor. Attacker-Centric View of a Detection Game against Advanced Persistent Threats. IEEE Transactions on Mobile Computing, 2018, vol. 17, iss. 11, pp. 2512-2523. DOI: 10.1109/TMC.2018.2814052. [4] Shana Moothedath, Dinuka Sahabandu, Joey Allen, Andrew Clark, Linda Bushnell, Wenke Lee, Radha Poovendran. A Game-Theoretic Approach for Dynamic Information Flow Tracking to Detect Multistage Advanced Persistent Threats. IEEE Transactions on Automatic Control, 2020, vol. 65, iss. 12, pp. 5248-5263. DOI: 10.1109/TAC.2020.2976040. [5] Dayong Ye, Tianqing Zhu, Sheng Shen, Wanlei Zhou. A Differentially Private Game Theoretic Approach for Deceiving Cyber Adversaries. IEEE Transactions on Information Forensics and Security, 2020, vol. 16, pp. 569-584. DOI: 10.1109/TIFS.2020.3016842. [6] Rui Zhang, Quanyan Zhu. FlipIn: A Game-Theoretic Cyber Insurance Framework for Incentive- Compatible Cyber Risk Management of Internet of Things. IEEE Transactions on Information Forensics and Security, 2019, vol. 15, pp. 2026-2041. DOI: 10.1109/TIFS.2019.2955891 [7] Boyu Gao;Libao Shi. Modeling an Attack-Mitigation Dynamic Game-Theoretic Scheme for Security Vulnerability Analysis in a Cyber-Physical Power System. IEEE Access, 2020, vol. 8, pp. 30322-30331. DOI: 10.1109/ACCESS.2020.2973030 [8] Makan Zamanipour. Fast-and-Secure State-Estimation in Dynamic-Control Over Communication Channels: A Game-Theoretical Viewpoint. IEEE Transactions on Signal and Information Processing over Networks, 2020, vol. 6, pp. 645-655. DOI: 10.1109/TSIPN.2020.3018327 [9] Lichun Li, Jeff S. Shamma. Efficient Strategy Computation in Zero-Sum Asymmetric Information Repeated Games. IEEE Transactions on Automatic Control, 2020, vol. 65, iss. 7, pp. 2785-2800. DOI: 10.1109/TAC.2019.2933396 [10] Burhan Ul Islam Khan, Farhat Anwar, Rashidah Funke Olanrewaju, Bisma Rasool Pampori, Roohie Naaz Mir. A Game Theory-Based Strategic Approach to Ensure Reliable Data Transmission With Optimized Network Operations in Futuristic Mobile Adhoc Networks. IEEE Access, 2020, vol. 8, pp. 124097-124109. DOI: 10.1109/ACCESS.2020.3006043 [11] Liang Xiao, Dongjin Xu, Narayan B. Mandayam, H. Vincent Poor. Attacker-Centric View of a Detection Game against Advanced Persistent Threats. IEEE Transactions on Mobile Computing. 2018. Vol. 17, Iss. 11. P. 2512-2523. DOI: 10.1109/TMC.2018.2814052 [12] Jiaxing Qi, Jing Yu, Shunfu Jin. Nash Equilibrium and Social Optimization of Transactions in Blockchain System Based on Discrete-Time Queue. IEEE Access, 2020, vol. 8, pp. 73614- 73622. DOI: 10.1109/ACCESS.2020.2986084 [13] Marcos V.O. De Assis, Matheus P. Novaes, Cinara B. Zerbini, Luiz F. Carvalho, Taufik Abrãao, Mario L. Proença. Fast Defense System Against Attacks in Software Defined Networks. IEEE Access, 2020, vol. 6, pp. 69620-69639. DOI: 10.1109/ACCESS.2018.2878576 [14] Sidi Ahmed Ezzahidi, Essaid Sabir, Mohamed El Kamili, El-Houssine Bouyakhf. A non- cooperative file caching for delay tolerant networks: A reward-based incentive mechanism. 2016 IEEE Wireless Communications and Networking Conference, 2016. DOI: 10.1109/WCNC.2016.7565161 [15] Richeng Jin; Xiaofan He;Huaiyu Dai. On the Security-Privacy Tradeoff in Collaborative Security: A Quantitative Information Flow Game Perspective. IEEE Transactions on Information Forensics and Security, 2019, vol. 14, iss. 12, pp. 3273-3286. DOI: 10.1109/TIFS.2019.2914358 [16] Klyucharev P.G. Grafy Pajzera v zadachah kriptografii i obrabotki informacii [pizer graphs in cryptography and in information processing]. Sbornik trudov desyatoj mezhdunarodnoj 31 nauchno-tekhnicheskoj konferencii «Bezopasnye informacionnye tekhnologii» (BIT-2019), Moscow, MGTU im. N.E.Baumana, 2019, pp. 176-179. (In Russ). [17] Ponomarenko G.S., Klyucharyov P.G. Opredelenie obfuskacii JavaScript-programm s pomoshch'yu raskrasok na abstraktnyh sintaksicheskih derev'yah [detection of obfuscated javascript code based on abstract syntax trees coloring]. Matematika i matematicheskoe modelirovanie, 2020, no. 2, pp. 1-24. DOI: 10.24108/mathm.0220.0000218. [18] Vishnevskij A.S., Klyucharev P.G. Obnaruzhenie celenapravlennyh atak veb-orientirovannoj obmannoj sistemoj, osnovannoj na algoritme antiklassifikacii [Anticlassification algorithm for targeted computer attack detection in web-oriented honeypot]. Nejrokomp'yutery: razrabotka, primenenie, 2020, vol. 22, no. 3, pp. 5-17. DOI: 10.18127/j19998554-202003-01. [19] Andrey Vishnevsky, Petr Klyucharev. The Sound User Interface of Honeypot. CEUR Workshop Proceedings. 2019. Vol-2603. P. 83-87. URL: http://ceur-ws.org/Vol-2603/short18.pdf. [20] Grigory Ponomarenko, Petr Klyucharev. JavaScript Programs Obfuscation Detection Method that Uses Artificial Neural Network with Attention Mechanism. CEUR Workshop Proceedings. 2019. Vol-2603. P. 100-104. URL: http://ceur-ws.org/Vol-2603/paper21.pdf. [21] A. Varfolomeev. Strengthening the password authenticated key exchange protocols due to the use of asymmetric execution of cryptosystems. CEUR Workshop Proceedings. 2019. Vol-2603. P. 79-82. http://ceur-ws.org/Vol-2603/short17.pdf. [22] M. Basarab, T. Buldakova, K. Smolyaninova, M. Sokolov. User Identification Based on the Vein Pattern in Biometric Immobilizer. CEUR Workshop Proceedings. 2019. Vol-2603. P. 1-5. URL: http://ceur-ws.org/Vol-2603/short1.pdf. [23] A. Chilikov, A. Zhukov, A. Verkhovsky. The Research of Reversible Cellular Automata with a Finite Lattice. CEUR Workshop Proceedings. 2019. Vol-2603. P. 12-15. URL: http://ceur- ws.org/Vol-2603/short3.pdf. [24] А. Markov, I. Sheremet. Enhancement of Confidence in Software in the Context of International Security. 2019. Vol-2603. P. 88-92. URL: http://ceur-ws.org/Vol-2603/paper19.pdf. [25] A. Kalashnikov. Example of Using of Game-Theoretic Approach in Problems of Ensuring Cyber Security of Information Systems. Voprosy kiberbezopasnosti, 2014, No 1(2), pp. 49-54. [26] Bykov A.Yu., Krygin I.A., Grishunin M.V., Markova I.A. Ob odnom algoritme poiska sedlovoj tochki dlya nepreryvnyh linejnyh igr primenitel'no k zadacham zashchity informacii [One saddle point search algorithm for continuous games applied to information security problems]. Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta im. N.E. Baumana. Seriya: Priborostroenie [Herald of the Bauman MSTU. Ser. Instrument Engineering], 2020, no. 4 (133), pp. 58-74. DOI: 10.18698/0236-3933-2020-4-58-74. [27] Bykov A.Yu., Grishunin M.V., Krygin I.A. Igrovaya zadacha vybora zashchishchaemyh ob"ektov i issledovanie algoritma poiska sedlovoj tochki na osnove modifikacii metoda Brauna- Robinsona [THE game problem of selection of assets to protect and research of saddle point search algorithm based on Brown-Robinson method modification]. Voprosy kiberbezopasnosti, 2019, no. 2 (30), pp. 2-12. DOI: 10.21681/2311-3456-2019-2-2-12. 32