This article considers a continuous zero-sum game of two players with resources limitations between defender, selecting the assets to be protected, and attacker, selecting the assets to be attacked. Players' solutions are defense and attack probabilities vectors for each asset. The problem is formulated that each player must solve linear programming problem with fixed opponent's solution. The saddle point is suggested to search on simplices faces, defined by limitations. To find it two systems of linear equations is necessary to be solved: one to find defender's solution and another to find attacker's solution. Each player chooses solution on his face so that another player's parameter value is the same for any solution on his own face. To find a saddle with a guarantee it necessary to go over all combinations of simplices faces. An example of the solution of the problem is presented. The total game cost, probabilities of attacks on assets and probabilities of defense are calculated.
INTRODUCTION
Game theory models are often used in problems related with information security. Consider some examples.
In [1] a game theory appliance in steganography is considered. Authors notice, there are a few articles related to this topic, because of adaptive attacks in steganography haven’t been carried out until recently. Two players are considered: deplorer player and detection players are described. A saddle point searching algorithm in mixed strategies is suggested.
In [2] it is considered an optimal strategy of network protection with usage of Moving Target Defense principle, based on Markov game. An essence of MTD – moving network elements vary in time, making attack more difficult. Markov decision process is used to describe transitions between network multistates. Dynamic game is used to describe multiphase steps of defense and attack in terms of MTD.
In [3] it’s investigated the PHY-layer authentication that exploits radio channel information to detect spoofing attacks in multiple- input multiple-output (MIMO) systems. Authors Ivan. A. Krygin formulate the interactions between a receiver and a spoofing node in the spoofing detection as a zero-sum game.
In [4] it’s investigated appliance of learning, based on game theory, to analyze big data. Such technique may be useful to analyze social networks. There are considered a linear game model of multiple players (agents), data storing in huge storages, each agent is related to sensitive information. Model is continuous, solution search satisfying Nash criterion is considered.
In [5] resource distribution in multiple access wiretap channels is considered. In model it’s considered several users who want to confidentially transmit data to legitimate user. On receiver side there is an adversary, who passively listen to channel and try to decode messages. Stochastic game is considered, solutions are sought to be Nash and Pareto optimal.
In [6] an efficient stochastic zero-sum game with incomplete information is considered. In article it’s investigated problem of own secret information disclosure to obtain adversary secret information and its solution strategies are suggested.
In [7] it’s considered game technique to detect hardware trojans. Authors notice, the microcircuit industry is witnessing a massive outsourcing of the fabrication of ICs, and it brings up multiple opportunities for the insertion of malicious logic in the ICs. Authors suggest using game theory to detect such insertions.
In [8] it’s considered a modelling of jamming attack in networks with wireless energy transfer. Authors have developed a game model, that allows to avoid energy interception. There are two players in the game: legitimate user and adversary. Each player has his own utility function, solution is sought as limited Nash equilibrity.
Information security software is often used to protect information in information processing and control systems (IPCS). This software is generally deployed on computational tools, which is used to solve target and supporting tasks in IPCS. In this case security software uses computational resources, and these resources are often limited, and their deficit is possible. This task becomes especially actual in mobile security protection, which have limited computational resources.
protected asset – something is needed to be protected resource – computational resource, used by security software Protected resources are: integrity, availability, confidentiality of data, storing on devices integrity, availability, confidentiality transferring over communication lines of data, etc.
System resources are: security software cost etc.
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 exists, is often a decision criterion in game-theory. Consider a possible approach to find a solution. Elements of selection set 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 problems are presented in [1-4]
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 by optimized algorithm guaranteed result principle was applied.
II. FORMULATION OF SECURITY SYSTEM RESOURCES DISTRIBUTON BETWEEN PROTECTED ASSETS PROBLEM A. Initial data
1) = { 1, 2, … , } - protected assets set, = {1, 2, … , } - their indices set
2) = { 1, 2, … , } – defender’s limited resources set, = {1, 2, … , } – their indicies set
3) = { 1, 2, … , } – attacker’s limited resources set, = {1, 2, … , } – their indices set B. Set elements parameters and relations between them 1) ≥ 0, ∀ ∈ – cost, if i-th protected asset security breach occurred (asset cost)
2) ∈ [0, 1], ∀ ∈ – i-th asset attack prevention probability when defending
3) ∈ [ 0, 1 ), ∀ ∈ , ∈ – normalized k-th defender’s limited resource value, used to protect i-th asset. The whole asset equals to 1
4) ∈ [ 0, 1 ), ∀ ∈ – maximum normalized k-th limited resource value, allocated for protection
5) с ∈ [ 0, 1 ), ∀ ∈ , ∈ – normailzed k-th attacker’s limited resource value, used to attack i-th asset. The whole asset equals to 1
6) ∈ [ 0, 1 ), ∀ ∈ – maximum normalized k-th attacker’s limited resource value
Define variable ∈ [0, 1], ∀ ∈ , signifying probability asset protection probability or its security degree. Variables forms vector ⃗ . For attacker define variable ∈ [0, 1], ∀ ∈ , signifying asset attack probability or attack reliability degree. Variables form vector ⃗ .
For zero-sum game players quality indicators are defined by defender damage. Average cost damage is: ( ⃗ , ⃗ ) = ( ⃗ ) − пр ( ⃗ , ⃗ ) = ∑ − ∑
by attacker without protection; пр ( ⃗ , ⃗ ) = ∑ ∈ – damage, prevented by defender
Thus, each player’s decision (searching for unknown
vectors ⃗ or ⃗ ) with fixed opponent’s solution implies linear
programming problem solution
III. BASES OF ALGORITHM OF SEARCHING FOR SADDLE
POINT ON THE DEFINED BY LIMITATIONS SIMPLEX FACES
Optimization problem for first player with fixed second
player’s decision is a linear programming problem. The first
player wishes to minimize parameter (
In [15] levels technique is suggested to find saddle point of
convex-concave function. This method is approximate and is
(
The saddle point defined by solutions pair ⃗ ∗ and ⃗ ∗ may
be as on vertices of two simplices, defined by limitations (
Simplices (polyhedron of allowable values) are in
mdimension metric space. In this case each limitation of
inequalities (
For each face it reachability is checked, that is allowable solution must exist for each player on his own face. It’s not necessary to examine unreachable faces.
Saddle point on simplices faces, defined by limitations, must satisfy the following conditions if it exists. Point ⃗ ∗ on face must ensure that target function reaches maximum and takes the same values on each point on second player’s face in vector space ⃗ . Similarly point ⃗ ∗ on face must ensure that target function reaches minimum and takes the same values on each point on first player’s face in vector space ⃗ .
It is necessary to find m different points per each
(m-1)dimensioned face (not necessarily satisfying all the limitations
(
equations 1 relatively unknown
(
System of
(
… . .
( ⃗ ∗, ⃗ (
∈
equations
( ⃗ (
… . .
( ⃗ (
If found solutions ⃗ ∗ and ⃗ ∗ satisfy limitations (
Consider the solution of low dimension problem of protecting some assets: number of protectable assets – 8, number of defender’s limited resources with defense cost -4, number of attacker’s limited resources and attack costs – 4. Other data are generated by pseudorandom number generator.
Protected assets parameters, such as possible loss,
probability (possibility) of assets attacks prevention are given
in table 1. Possible damage values are given in conventional
units. Defender’s limited resources parameters, such as defense
costs as resource and right sides of (
DEFENDER’S RESOURCES Defender’s resources values
, ∀ ∈ , ∈ Resource 1
Resource 2
Resource 3
Because of going over faces the saddle point was found on faces belonging to 6-dimension hyperplanes (solution is sought in initial 8-dimension spaces). For defender hyperplane is defined by two 7-dimension hyperplanes intersection – one hyperplane containing face, defined by defense cost limitation, and another hyperplane defined by condition 6 = 0. For attacker hyperplane is defined by two 7-dimension hyperplanes intersection – one hyperplane containing face, defined by resource 2 limitation, and another hyperplane defined by condition 6 = 0. Solution is presented in table 4. 0,422 0,607 0,751 0,779 0,778 0,736
SOLUTION
Vector ⃗ ∗ 0,634
0,409 0,000 0,000 0,532 0,915 0,576 0,737
Game cost
There is presented a continuous two players zero-sum game with resources limitation for choosing assets to protect by defender and choosing assets to attack by attacker. Each player solves linear programming problem with fixed opponent decision. If saddle point is on simplices faces, defined by limitations, then it is suggested to solve two systems of linear equations to find it.
Suggested solutions reliability is based on usage of known verifies algorithms, found saddle point is confirmed by check for compliance with conditions it must satisfy.