=Paper=
{{Paper
|id=Vol-2081/paper08
|storemode=property
|title=A Search for Saddle Point in Protectable Assets Selection Problem Based on Continuous Game Theory Model
|pdfUrl=https://ceur-ws.org/Vol-2081/paper08.pdf
|volume=Vol-2081
|authors=Alexander Yu. Bykov,Ivan. A. Krygin
}}
==A Search for Saddle Point in Protectable Assets Selection Problem Based on Continuous Game Theory Model ==
https://ceur-ws.org/Vol-2081/paper08.pdf
A Search for Saddle Point in Protectable Assets
Selection Problem Based on Continuous Game
Theory Model
Alexander Yu. Bykov Ivan. A. Krygin
Information Security Department Information Security Department
Bauman Moscow State Technical University Bauman Moscow State Technical University
Moscow, Russia Moscow, Russia
abykov@bmstu.ru krygin.ia@gmail.com
Abstract. This article considers a continuous zero-sum game formulate the interactions between a receiver and a spoofing
of two players with resources limitations between defender, node in the spoofing detection as a zero-sum game.
selecting the assets to be protected, and attacker, selecting the
assets to be attacked. Players’ solutions are defense and attack In [4] it’s investigated appliance of learning, based on game
probabilities vectors for each asset. The problem is formulated theory, to analyze big data. Such technique may be useful to
that each player must solve linear programming problem with analyze social networks. There are considered a linear game
fixed opponent’s solution. The saddle point is suggested to search model of multiple players (agents), data storing in huge
on simplices faces, defined by limitations. To find it two systems storages, each agent is related to sensitive information. Model
of linear equations is necessary to be solved: one to find is continuous, solution search satisfying Nash criterion is
defender’s solution and another to find attacker’s solution. Each considered.
player chooses solution on his face so that another player’s
parameter value is the same for any solution on his own face. To In [5] resource distribution in multiple access wiretap
find a saddle with a guarantee it necessary to go over all channels is considered. In model it’s considered several users
combinations of simplices faces. An example of the solution of the who want to confidentially transmit data to legitimate user. On
problem is presented. The total game cost, probabilities of receiver side there is an adversary, who passively listen to
attacks on assets and probabilities of defense are calculated. channel and try to decode messages. Stochastic game is
considered, solutions are sought to be Nash and Pareto optimal.
Keywords. information security, zero-sum game, linear
programming, saddle point, simplex, face of simplex, system of In [6] an efficient stochastic zero-sum game with
linear equations incomplete information is considered. In article it’s
investigated problem of own secret information disclosure to
obtain adversary secret information and its solution strategies
I. INTRODUCTION are suggested.
Game theory models are often used in problems related
with information security. Consider some examples. In [7] it’s considered game technique to detect hardware
trojans. Authors notice, the microcircuit industry is witnessing
In [1] a game theory appliance in steganography is a massive outsourcing of the fabrication of ICs, and it brings up
considered. Authors notice, there are a few articles related to multiple opportunities for the insertion of malicious logic in the
this topic, because of adaptive attacks in steganography haven’t ICs. Authors suggest using game theory to detect such
been carried out until recently. Two players are considered: insertions.
deplorer player and detection players are described. A saddle
point searching algorithm in mixed strategies is suggested. In [8] it’s considered a modelling of jamming attack in
networks with wireless energy transfer. Authors have
In [2] it is considered an optimal strategy of network developed a game model, that allows to avoid energy
protection with usage of Moving Target Defense principle, interception. There are two players in the game: legitimate user
based on Markov game. An essence of MTD – moving and adversary. Each player has his own utility function,
network elements vary in time, making attack more difficult. solution is sought as limited Nash equilibrity.
Markov decision process is used to describe transitions
between network multistates. Dynamic game is used to Information security software is often used to protect
describe multiphase steps of defense and attack in terms of information in information processing and control systems
MTD. (IPCS). This software is generally deployed on computational
tools, which is used to solve target and supporting tasks in
In [3] it’s investigated the PHY-layer authentication that IPCS. In this case security software uses computational
exploits radio channel information to detect spoofing attacks in resources, and these resources are often limited, and their
multiple- input multiple-output (MIMO) systems. Authors deficit is possible. This task becomes especially actual in
36
mobile security protection, which have limited computational 2) 𝑝𝑝𝑟 𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀 – i-th asset attack prevention
resources. probability when defending
The following definitions will be used: 3) 𝑎𝑘𝑖 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝐿, 𝑖 ∈ 𝑀 – normalized k-th
defender’s limited resource value, used to protect i-th asset.
protected asset – something is needed to be protected The whole asset equals to 1
resource – computational resource, used by security 4) 𝑏𝑘 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝐿 – maximum normalized k-th
software limited resource value, allocated for protection
5) с𝑘𝑖 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝑆, 𝑖 ∈ 𝑀 – normailzed k-th
Protected resources are:
attacker’s limited resource value, used to attack i-th asset. The
integrity, availability, confidentiality of data, storing on whole asset equals to 1
devices 6) 𝑑𝑘 ∈ [ 0, 1 ), ∀ 𝑘 ∈ 𝑆 – maximum normalized k-th
integrity, availability, confidentiality of data, attacker’s limited resource value
transferring over communication lines C. Parameters
etc. Define variable 𝑝𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀, signifying probability
asset protection probability or its security degree. Variables
System resources are:
forms vector 𝑃⃗ . For attacker define variable 𝑞𝑖 ∈ [0, 1], ∀ 𝑖 ∈
security software cost 𝑀, signifying asset attack probability or attack reliability
degree. Variables form vector 𝑄 ⃗.
CPU time
RAM size D. Players indicators
Storage size For zero-sum game players quality indicators are defined
by defender damage. Average cost damage is:
Network
⃗ ) = 𝑈𝑚𝑎𝑥 (𝑄
𝑈(𝑃⃗ , 𝑄 ⃗ ) − 𝑈пр (𝑃⃗ , 𝑄
⃗)
etc. (1)
= ∑ 𝑤𝑖 𝑞𝑖 − ∑ 𝑝𝑝𝑟 𝑖 𝑤𝑖 𝑝𝑖 𝑞𝑖
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 where 𝑈𝑚𝑎𝑥 (𝑄 ⃗ ) = ∑𝑖 ∈𝑀 𝑤𝑖 𝑞𝑖 maximum damage, may be
exists, is often a decision criterion in game-theory. Consider a caused by attacker without protection; 𝑈пр (𝑃⃗ , 𝑄 ⃗)=
possible approach to find a solution. Elements of selection set ∑𝑖 ∈𝑀 𝑝𝑝𝑟 𝑖 𝑤𝑖 𝑝𝑖 𝑞𝑖 – damage, prevented by defender
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 E. Limitations
problems are presented in [1-4]
Defender’s limited resources usage limitation:
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 (2)
𝑖 ∈𝑀
by optimized algorithm guaranteed result principle was
applied. Attacker’s limited resources usage limitation:
∑ 𝑐𝑖𝑘 𝑞𝑖 ≤ 𝑑𝑘 , ∀ 𝑘 ∈ 𝑆 (3)
II. FORMULATION OF SECURITY SYSTEM RESOURCES
𝑖 ∈𝑀
DISTRIBUTON BETWEEN PROTECTED ASSETS PROBLEM
Thus, each player’s decision (searching for unknown
A. Initial data ⃗ ) with fixed opponent’s solution implies linear
vectors 𝑃⃗ or 𝑄
1) 𝑍 = {𝑧1 , 𝑧2 , … , 𝑧𝑚 } - protected assets set, 𝑀 = programming problem solution
{1, 2, … , 𝑚} - their indices set
2) 𝑅 = {𝑟1 , 𝑟2 , … , 𝑟𝑙 } – defender’s limited resources set, III. BASES OF ALGORITHM OF SEARCHING FOR SADDLE
𝐿 = {1, 2, … , 𝑙} – their indicies set POINT ON THE DEFINED BY LIMITATIONS SIMPLEX FACES
3) 𝑁 = {𝑛1 , 𝑛2 , … , 𝑛𝑠 } – attacker’s limited resources set, Optimization problem for first player with fixed second
𝑆 = {1, 2, … , 𝑠} – their indices set player’s decision is a linear programming problem. The first
player wishes to minimize parameter (1) with limitations (2),
B. Set elements parameters and relations between them
and the second one wishes to maximize parameter (1) with
1) 𝑤𝑖 ≥ 0, ∀ 𝑖 ∈ 𝑀 – cost, if i-th protected asset security limitations (3).
breach occurred (asset cost)
In [15] levels technique is suggested to find saddle point of
convex-concave function. This method is approximate and is
37
required to solve convex programming problems. Also, it is ⃗ (1) ) = 𝑈(𝑃⃗ ∗ , 𝑄
𝑈(𝑃⃗ ∗ , 𝑄 ⃗ (2) ),
pointed the saddle point always exists under given conditions.
⃗ (1) ) = 𝑈(𝑃⃗ ∗ , 𝑄
𝑈(𝑃⃗ ∗ , 𝑄 ⃗ (3) ),
⃗ ∗ may
The saddle point defined by solutions pair 𝑃⃗ ∗ and 𝑄 …..
be as on vertices of two simplices, defined by limitations (2) ⃗ (1) ) = 𝑈(𝑃⃗ ∗ , 𝑄
𝑈(𝑃⃗ ∗ , 𝑄 ⃗ (𝑚) ),
and (3), and on simplices faces. Optimized technique may be
used to find saddle point if it is on vertices. ∑ 𝛼 (𝑖) = 1.
{ 𝑖 ∈𝑀
Simplices (polyhedron of allowable values) are in m-
dimension metric space. In this case each limitation of System of equations 2 relatively unknown
inequalities (2) and (3) defines (m-1)-dimensioned hyperplane 𝛽 (1) , 𝛽 (2) , … , 𝛽 (𝑚) :
if becomes equality. As 𝑝𝑖 ∈ [0, 1], ∀ 𝑖 ∈ 𝑀 and 𝑞𝑖 ∈
[0, 1], ∀ 𝑖 ∈ 𝑀, allowable solutions are also inside of ⃗ ∗ ) = 𝑈(𝑃⃗ (2) , 𝑄
𝑈(𝑃⃗ (1) , 𝑄 ⃗ ∗ ),
hypercube with sides are equal to 1. Hypercubes are ⃗ ∗ ) = 𝑈(𝑃⃗ (3) , 𝑄
𝑈(𝑃⃗ (1) , 𝑄 ⃗ ∗ ),
constrained by (m-1)-dimensioned hyperplanes, defined by …..
𝑝𝑖 = 0, ∀ 𝑖 ∈ 𝑀, 𝑝𝑖 = 1, ∀ 𝑖 ∈ 𝑀 evaluations for defender ⃗ ∗ ) = 𝑈(𝑃⃗ (𝑚) , 𝑄
⃗ ∗ ),
and 𝑞𝑖 = 0, ∀ 𝑖 ∈ 𝑀, 𝑞𝑖 = 1, ∀ 𝑖 ∈ 𝑀 evaluations for attacker. 𝑈(𝑃⃗ (1) , 𝑄
In this way simplices are constrained by hyperplanes defined ∑ 𝛽 (𝑖) = 1.
by limitations (2) and (3) (if inequalities become equalities) { 𝑖 ∈𝑀
and hypercubes borders hyperplanes. An intersection of two
(m-1)-dimensioned hyperplanes (if they intersect) is a (m-2)- ⃗ ∗ satisfy limitations (2) and (3)
If found solutions 𝑃⃗ ∗ and 𝑄
dimensioned hyperplane; an intersection of three hyperplanes and saddle point condition, then this is a required solution.
is (m-3)-dimensioned hyperplane etc. Separated point of m-
dimensioned space in this interpretation is 0-dimensioned IV. EXAMPLE
hyperplane. Simplices faces may belong to different
Consider the solution of low dimension problem of
dimensioned hyperplanes (in three dimensioned case the
protecting some assets: number of protectable assets – 8,
following terms are used: faces, edges, vertices). It is necessary
number of defender’s limited resources with defense cost -4,
to go over all faces for full search. Consider the technique of
number of attacker’s limited resources and attack costs – 4.
searching for possible solutions on faces, belong to same-
Other data are generated by pseudorandom number generator.
dimensioned hyperfaces.
Protected assets parameters, such as possible loss,
For each face it reachability is checked, that is allowable
probability (possibility) of assets attacks prevention are given
solution must exist for each player on his own face. It’s not
in table 1. Possible damage values are given in conventional
necessary to examine unreachable faces.
units. Defender’s limited resources parameters, such as defense
Saddle point on simplices faces, defined by limitations, costs as resource and right sides of (2) values are given in table
must satisfy the following conditions if it exists. Point 𝑃⃗ ∗ on 2. Attacker’s limited resources parameters, such as attack costs
face must ensure that target function reaches maximum and as resource and right sides of (2) values are given in table 2.
takes the same values on each point on second player’s face in Costs are given in conventional units.
vector space 𝑄 ⃗ . Similarly point 𝑄⃗ ∗ on face must ensure that
target function reaches minimum and takes the same values on TABLE I. PROTECTABLE ASSETS PARAMETERS
each point on first player’s face in vector space 𝑃⃗ . Size of possible Attack prevention
# damage probability
It is necessary to find m different points per each (m-1)- 𝑝𝑝𝑟 𝑖 , ∀ 𝑖 ∈ 𝑀
𝑤𝑖 , ∀ 𝑖 ∈ 𝑀
dimensioned face (not necessarily satisfying all the limitations 1 4535,63 0,967
(2) or (3)). Let 𝑃⃗(1) , 𝑃⃗ (2) , … , 𝑃⃗ (𝑚) are points on face in vector 2 2075,96 0,607
space 𝑃⃗ , and 𝑄⃗ (1) , 𝑄
⃗ (2) , … , 𝑄
⃗ (𝑚) are points on face in vector 3 3357,13 0,805
⃗ . Define multipliers 𝛼 (1) , 𝛼 (2) , … , 𝛼 (𝑚) and 4 2972,23 0,769
space 𝑄 5 3409,13 0,676
𝛽 , 𝛽 , … , 𝛽 (𝑚) . So required points is found is the following
(1) (2)
6 2260,05 0,973
form: 𝑃⃗ ∗ = ∑𝑖 ∈𝑀 𝛼 (𝑖) 𝑃⃗ (𝑖) , 𝑄 ⃗ ∗ = ∑𝑖 ∈𝑀 𝛽 (𝑖) 𝑄⃗ (𝑖) . 7 2188,76 0,660
8 4280,74 0,708
System of equations 1 relatively unknown
𝛼 (1) , 𝛼 (2) , … , 𝛼 (𝑚) :
38
Suggested solutions reliability is based on usage of known
TABLE II. DEFENDER’S RESOURCES verifies algorithms, found saddle point is confirmed by check
Defender’s resources values for compliance with conditions it must satisfy.
𝑎𝑘𝑖 , ∀ 𝑘 ∈ 𝐿, 𝑖 ∈ 𝑀
#
Defense
cost
Resource 1 Resource 2 Resource 3 REFERENCES
1 392,038 0,340 0,345 0,153 [1] Schöttle P., Böhme R. Game Theory and Adaptive Steganography. IEEE
2 144,472 0,176 0,319 0,392 Transactions on Information Forensics and Security. 2016. Vol. 11, iss.
3 292,657 0,273 0,160 0,426 4. P. 760–773. DOI: 10.1109/TIFS.2015.2509941.
4 147,133 0,130 0,151 0,381 [2] Lei C., Ma D., Zhang H. Optimal Strategy Selection for Moving Target
5 128,114 0,218 0,229 0,410 Defense Based on Markov Game. IEEE Access. 2017. Vol. 5. P. 156–
6 252,678 0,451 0,263 0,250 169. DOI: 10.1109/ACCESS.2016.2633983.
7 194,546 0,437 0,300 0,318 [3] Xiao Liang., Chen T., Han G., Zhuang W., Sun L. Channel-Based
8 329,060 0,101 0,345 0,246 Authentication Game in MIMO Systems. 2016 IEEE Global
Total Communications Conference (GLOBECOM). 2016. P. 1–6. DOI:
940,349 1,200 1,179 1,634 10.1109/GLOCOM.2016.7841657.
𝑏𝑘 , ∀𝑘 ∈ 𝐿
[4] Chessa M., Grossklags J., Loiseau P. A Game-Theoretic Study on Non-
TABLE III. ATTACKER’S RESOURCES monetary Incentives in Data Analytics Projects with Privacy
Implications. 2015 IEEE 28th Computer Security Foundations
Attacker’s resources values Symposium. 2015. P. 90–104. DOI: 10.1109/CSF.2015.14.
# с𝑘𝑖 , ∀ 𝑘 ∈ 𝑆, 𝑖 ∈ 𝑀
[5] Shah S. Chaitanya A., Sharma V. Resource allocation in fading multiple
Attack cost Resource 1 Resource 2 Resource 3
access wiretap channel via game theoretic learning. 2016 Information
1 22,361 0,350 0,233 0,242 Theory and Applications Workshop (ITA). 2016. P. 1–7. DOI:
2 14,527 0,148 0,248 0,247 10.1109/ITA.2016.7888137.
3 13,823 0,164 0,158 0,176
[6] Li L., Shamma J. Efficient computation of discounted asymmetric
4 20,547 0,199 0,112 0,306 information zero-sum stochastic games. 2015 54th IEEE Conference on
5 18,650 0,322 0,349 0,322 Decision and Control (CDC). 2015. P. 4531–4536. DOI:
6 34,593 0,431 0,479 0,403 10.1109/CDC.2015.7402927.
7 44,407 0,185 0,364 0,347
[7] Kamhoua C., Zhao H., Rodriguez M., Kwiat K. A Game-Theoretic
8 25,191 0,331 0,486 0,421 Approach for Testing for Hardware Trojans. IEEE Transactions on
Total Multi-Scale Computing Systems. 2016. Vol. 2, iss. 3. P. 199–210. DOI:
116,459 1,070 1,542 1,694
𝑑𝑘 , ∀𝑘 ∈ 𝑆 10.1109/TMSCS.2016.2564963.
[8] Niyato D., Wang P., Kim D., Han Z., Xiao L. Game theoretic modeling
of jamming attack in wireless powered communication networks. 2015
Because of going over faces the saddle point was found on IEEE International Conference on Communications (ICC). 2015. P.
faces belonging to 6-dimension hyperplanes (solution is sought 6018–6023. DOI: 10.1109/ICC.2015.7249281.
in initial 8-dimension spaces). For defender hyperplane is [9] Freudiger J., Manshaei M.H., Hubaux J. P., Parkes D.C. Non-
defined by two 7-dimension hyperplanes intersection – one Cooperative Location Privacy. IEEE Transactions on Dependable and
hyperplane containing face, defined by defense cost limitation, Secure Computing. 2013. Vol. 10, iss. 2. P. 84 – 98. DOI:
and another hyperplane defined by condition 𝑝6 = 0. For 10.1109/TDSC.2012.85.
attacker hyperplane is defined by two 7-dimension hyperplanes [10] Lelarge M. Coordination in Network Security Games: A Monotone
Comparative Statics Approach. IEEE Journal on Selected Areas in
intersection – one hyperplane containing face, defined by Communications. 2012. Vol. 30, iss. 11. P. 2210 – 2219. DOI:
resource 2 limitation, and another hyperplane defined by 10.1109/JSAC.2012.121213.
condition 𝑞6 = 0. Solution is presented in table 4. [11] Liang Xiao, Yan Chen, Lin W.S., Liu K.J.R. Indirect Reciprocity
Security Game for Large-Scale Wireless Networks. IEEE Transactions
on Information Forensics and Security. 2012. Vol. 7, iss. 4. P. 1368 –
TABLE IV. SOLUTION 1380. DOI: 10.1109/TIFS.2012.2202228.
Game [12] Ma C.Y.T., Yau D.K.Y., Rao N.S.V. Scalable Solutions of Markov
Vector 𝑃⃗ ∗ cost Games for Smart-Grid Infrastructure Protection. IEEE Transactions on
0,422 0,751 0,778 0,634 0,409 0,000 0,532 0,576 Smart Grid. 2013. Vol. 4, iss. 1. P. 47 – 55. DOI:
⃗∗ 8200, 10.1109/TSG.2012.2223243.
Vector 𝑄 144
0,607 0,779 0,736 0,437 0,378 0,000 0,915 0,737 [13] Xiannuan Liang, Yang Xiao. Game Theory for Network Security. IEEE
Communications Surveys & Tutorials. 2013. Vol. 15, iss. 1. P. 472 –
486. DOI: 10.1109/SURV.2012.062612.00056.
CONCLUSION
[14] A. Yu. Bykov, E. S. Shmatova The Algorithms of Resource Distribution
There is presented a continuous two players zero-sum game for Information Security Between Objects of an Information System
with resources limitation for choosing assets to protect by Based on the Game Model and Principle of Equal Security of Objects.
defender and choosing assets to attack by attacker. Each player Science and Education of the Bauman MSTU, 2015, No. 9, pp. 160–187.
DOI: 10.7463/0915.0812283.
solves linear programming problem with fixed opponent
decision. If saddle point is on simplices faces, defined by [15] Shmatova E. The Choice of Strategy for the Spurious Information
System on the Basis of the Game Theory Model. Voprosy
limitations, then it is suggested to solve two systems of linear kiberbezopasnosti [Cybersecurity issues], 2015. No 5 (13). P. 36-40.
equations to find it. DOI: 10.21681/2311-3456-2015-5-36-40.
[16] E. G. Golshtein, A. S. Nemirovsky, Yu. E. Nesterov Optimization
techniques. Levels technique, it generalizations and applications.
Economics and mathematical methods. 1995. V. 31. no. 3. pp. 164-180.
39