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 discretecontinuous 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 BrownRobinson 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.
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 discretecontinuous 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.
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 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. = { 1, 2, … , } – set of servers on a distributed computer system, = {1,2, … , } - set of indices enumerating these servers.
= {1,2, … , } - set of indices enumerating these attack types.
= { 1, 2, … , } – set of attack types (implementations of security threats) on the system, enforcement, Λ = {1,2, … , λ} – set of indices enumerating these processes.
= { 1, 2, … , } – set of auxiliary processes, which can be run on servers for security ( ) = ( ) 1
, 2( ), … , ( ) indices enumerating these resources.
( ) – set of limited defender resources, ( ) = {1,2, … , ( )} - set of indices enumerating these resources. respectively.
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, … , ( ℎ)} ( ) = { 1 ( ), 2
( ), … , (( ))} – set of limited attacker resources. ( ) = {1,2, … , ( )} - set of
1. 2. ( ) ( ) 3.2.
Set elements parameters and relations between them implementetion) if k-th process is running on any server or defender damage mitigation value. ≥ 0, ∀ ∈ ( ) , ∈ , ∈
– value of j-th private resource (performance or memory)
≥ 0, ∀ ∈ , ∈ ∈ [0,1], ∀ ∈ , ∈ successful in carrying out j-th type of attack. required to run k-th process on i-th server.
≥ 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.
– estimate of damage to defender on i-th server if attacker was
– probability (or possibility) of preventing j-th attack (threat required to run k-th process on i-th server. used for auxiliary processes.
≥ 0, ∀ ∈ ( ℎ), ∈ , ∈
– value of j-th shared resource (for example, financial) ≥ 0, ∀ ∈ ( ℎ) – maximum value of j-th shared resource for all servers, that can be belongs to i-th group and
= 0 if otherwise.
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 ≥ 0, ∀ ∈ ( ), ∈ , ∈ - value of k-th attacker resource required for j-th attack type on i-th server.
≥ 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.
∈ {0,1}, ∀ ∈ , ∈ , for the defender, = 1 if k-th process is running on i-th server and = 0 otherwise. These variables form the vector ⃗.
∈ [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.
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 пр( ⃗, ⃗) = ∑ ∈ ∑ ∈ ( ⃗) = .
Defenders’ goal is to minimize this indicator, attackers’ – to maximize. 3.5.
Conditions on private resource usage on each server:
Conditions for defender ( ) ≤ ( ) , ∀ ∈ ( ), ∈ .
(
, ∀ ∈ ( ℎ). ≤ 1, ∀ ∈ , ∈ .
Conditions for attacker ( ) ≤
( ), ∀ ∈ ( ).
Presented formulation of the problem with indicator given by (
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 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.
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.
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.
indicator (
=1 ∈ ∈ з ( +1)( ⃗) = ( ⃗, ⃗( )) = ( ) (1 − where
( ) are components of vector ⃗( )
indicator (
=1 ∈ ∈ where ( ) are components of vector ⃗ ( ). н ( +1)( ⃗) = ( ⃗( ), ⃗) = (1 −
{ ( )}),
The problem with indicator (
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 =1 4.3.
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 (
We determine ⃗( ) for fixed ⃗( ) by solving a boolean programming problem for the defender
include into defender’s solution map.
with indicator (
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 ( +1)( ⃗( )), obtained ⃗( ) we | < can be used as a stopping criterion, where ε - some not met, we continue with the next step.
The condition | н( )( ⃗( )) −
з( +1)( ⃗( )) −1 value
−1 н( ) ⃗( ) , з( +1) ⃗( ) .
relatively small positive value, determining algorithm error, ε can be chosen as a percentage of the
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.
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.
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.
2 38.20 30.85 32.79 21.28 39.61 234.70
3 18.03 38.59 22.24 44.87 24.97
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. 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.