Contents
0. How I got into (Game Theory) 1. Basic Notions 1) Pooling / (Semi-)Separating equilibrium 2) Cho and Kreps criterion (Intuitive criterion) 2. Summary (paper) 3. Review (paper) - Background - Honeypot deception game model - Analysis 4. Analysis 1) Identify an attacker's strategy for which there exists a semi-separating PBE in Theorem IV.1. + finding separating/pooling equilibrium 2) Find all PBEs in a full-featured honeypot game. Then, check if there is a PBE that satisfies the Cho-Kreps criterion. 5. Conclusions 1) Existence of semi-separating PBEs 2) PBE that satisfy the Cho-Kreps criterion 6. References
0. How I got into Game Theory
게임 이론에 대한 제 관심은 수학을 실생활에 적용하려는 열정과, 제 관심사를 알아봐 준 한 선배의 제의로 시작되었습니다.
사실 저는 직접적으로 수학 기술을 보안에 적용할 수 있는 사례로, 암호학이나 전자서명 등 통계적인 규칙이나 패턴을 분석하는 용도로만 생각했습니다. 하지만 게임 이론을 탐구하면서 보안 기술의 원리나, 실제 시나리오에 게임 이론이 어떻게 적용되는지 구체화할 수 있었습니다.
확률 이론이나 최적화, 미적분학과 같은 수학적 기술에 크게 의존하는 게임 이론 분야에서, 저는 다양한 전략적 시나리오를 모델링하고 분석하고자 공부 중입니다. 그리고 연구 준비 단계로 다음의 논문을 첫 번째 리뷰 논문으로 소개합니다.
이 논문을 분석하면서 저는 최적의 의사 결정 전략에 대한 통찰력을 파악하고 최적의 결과를 예측할 수 있었습니다.
1. Basic Notions
#1. Pooling / (Semi-)Separating equilibrium
A. Pooling equilibrium
an equilibrium in which all types of sender send the same message.
B. Separating equilibrium
an equilibrium in which all types of sender send different messages.
C. Semi-Separating equilibrium
(Partially-pooling equilibrium is) an equilibrium in which some types of sender send the same message, while some others sends some other messages.
#2. Cho and Kreps criterion (Intuitive criterion)
직관적 기준(Intuitive criterion)은 신호 게임에서 평형을 개선하기 위한 기법이다.
신호 게임에는 일반적으로 많은 내쉬 평형이 존재하고, 일부 평형은 평형에 속한 플레이어가 평형 경로에서 벗어난 부당한 믿음을 갖게 된다는 점에서 불합리하다.
이러한 불합리한 평형을 배제하기 위해 일반적으로 내쉬 평형을 다양한 방식으로 개선하고 있으며,
이러한 개선 사항 중 Cho와 Kreps의 직관적인 기준이 가장 강력하고 가장 널리 사용되는 것으로 보인다.
이는 가능한 발신자 유형을 평형에서 벗어난 메시지로 이탈하여 더 높은 효용 수준을 얻을 수 있는 유형과, 평형에서 벗어난 메시지가 지배적이지 않은 유형으로 제한한다.
따라서 이 기준은 가능한 결과 시나리오를 줄이는 것을 목표로 한다.
Do You Really Need to Disguise Normal Servers as Honeypots?
2. Summary
Index Terms – cybersecurity, game theory, honeypot, signaling game
Compare and analyze three attacker-defender games against honeypot detection techniques
Research on honeypot deception tactics and their effectiveness in mitigating Cyber Threats
3. Review
II. BACKGROUND
B. Signaling Game
For off-equilibrium paths, the beliefs can be arbitrary.
However, some arbitrary beliefs can be irrational so that a PBE which relies on such beliefs can be eliminated with advanced refinement rules.
- I.-K. Cho and D. M. Kreps, “Signaling games and stable equilibria,” The Quarterly Journal of Economics, vol. 102, no. 2, pp. 179–221, 1987.
III. HONEYPOT DECEPTION GAME MODEL
A. The attacker-defender honeypot game scenario
type \ signal | honeypot (signal h) | normal (signal n) |
Honeypot | Obvious Honeypot (Fake service) | Honeypot (Fake service) – honeypot-as-normal |
Normal | Fake Honeypot (Real service) – normal-as-honeypot | Server (Real service) |
B. The attacker-defender Game Model
(a) Honest game
: defenders do not use any honeypot techniques
(b) Semi-featured honeypot game
1) \(c_t > c_p\) : revealing concrete attack methods will be more costly than simply proving nodes
2) \(c_h < c_a\) : the cost by successful attacks will be the most threatening
(c) Full-featured honeypot game
1) \(c_n < c_h\) : the cost to deploy a normal-as-honeypot node can be handled in a software method to an existing normal node
2) \(c_n < c_a\), \(c_h < c_a\) : the cost by successful attacks will be the most threatening
따라서, 방어자에게 발생하는 비용은 \(c_n, c_h, c_a\) 순으로 적으며, 공격자는 \(c_p\)보다 \(c_t\)가 더 많은 비용이 발생한다.
(Thus, the cost figure for the defender is \(c_n < c_h < c_a\) and for the attacker is \(c_p < c_t\).)
IV. ANALYSIS
B. Equilibria Analysis on Semi-featured Honeypot Game
- Let (a, (B, C)) denote a strategy set where ‘a’ is the H- type defender’s action, ‘B’ is the attacker’s action when the signal (h) is received, and ‘C’ is the attacker’s action when the signal (n) is received.
C. Equilibria Analysis on Full-featured Honeypot Game
- Let ((a, b), (C, D)) denote a strategy set where ‘a’ is the H-type defender’s action, ‘b’ is the N-type defender’s action, ‘C’ is the attacker’s action when the signal (h) is received, and ‘D’ is the attacker’s action when the signal (n) is received.
4. Analysis
Objectives #1: Theorem IV.1에서 반분리 PBE가 존재하는 공격자의 전략을 구한다. #2: Full-featured 허니팟 게임에서 모든 PBE를 찾는다. 그 이후, Cho-Kreps의 직관적인 기준에 의해 (만족하는지 여부에 따라) PBE가 지워지거나 평형이 유지되는지 확인한다). #1: Identify an attacker's strategy for which there exists a semi-separating PBE in Theorem IV.1. #2: Find all PBEs in a Full-featured honeypot game. Then, check that the PBE is erased by the intuitive criterion of Cho-Kreps or that equilibrium is preserved(satisfies the Cho-Kreps criterion).
comments #1
Proof. Let there exist a semi-separating PBE with an attacker’s strategy \(((\sigma_a, 1-\sigma_a), (\sigma_b, 1-\sigma_b))\) with a belief (p, q).
Applying the indifference principle, the utilities of the defender’s actions given the honeypot type should be same
Suppose a semi-separating equilibrium exists for all arbitrary non-zero payoff parameter.
$$ u_h^H(A) = \sigma_{pA}(b_d-c_h)+(1-\sigma_{pA}(-c_h) = \sigma_{pA}b_d=c_h $$
$$ u_n^H(A) = \sigma_{qA}(b_d-c_h)+(1-\sigma_{qA}(-c_h) = \sigma_{qA}b_d=c_h $$
⇒ \(\sigma_{pA} = \sigma_{qA}\) – (1)
$$ u_h^N(A) = \sigma_{(1-p)A}(-c_a)+(1-\sigma_A)\cdot0 = -c_a\sigma_{(1-p)A} $$
$$ u_n^N(A) = \sigma_{(1-q)A}(-c_a-c_n)+(1-\sigma_{(1-q)A}(-c_n)=-\sigma_{(1-q)A}c_a-c_n $$
⇒ \(c_a(\sigma_{(1-p)A}-\sigma_{(1-q)A}) = c_n\) – (2)
That is, by (1) and (2), \(c_n = 0\), which contradicts the assumption that \(c_n \neq 0\).
Therefore, there is no semi-separating equilibrium for any nonzero \(c_n\).
+ finding separating/pooling equilibrium
(1) Represent defender’s strategy \(\sigma_d\) with two parameters:
\(\sigma_d\) = (\(\sigma_d^H(h), \sigma_d^N(h)\)) = (x, y)
\(\sigma_d^H(h)\): for honeypot type, \(\sigma_d^N(h)\): for normal type
(2) Compute attacker’s Bayesian beliefs given \(\sigma_d\):
in signal h,
$$ p \equiv \mu_{att}^h(A) = \frac{p_{\sigma}(h)}{p_{\sigma}(I_h)} = \frac{P_hy}{P_hy + (1-P_h)x} \\ = \frac{P_hy}{x-P_h(x-y)} $$
in signal n,
$$ q \equiv \mu_{att}^n(A) = \frac{p_{\sigma}(n)}{p_{\sigma}(I_n)} = \frac{P_h(1-y)}{P_h(1-y) + (1-P_h)(1-x)} \\ = \frac{P_h(1-y)}{1-x+P_h(x-y)} $$
(3) Find attacker’s best response to \(\sigma_d\) given beliefs:
attacker’s BR @ \(I_h = \begin {cases} A & \text{if } p \geq \frac{1}{2} \\ L & \text{if } p < \frac{1}{2} \end {cases}\)
attacker’s BR @ \(I_n = \begin {cases} A & \text{if } q \geq \frac{1}{2} \\ L & \text{if } q < \frac{1}{2} \end {cases}\)
(Since one goal of this paper is to determine if the fake strategy for normal nodes is efficient, let’s set Pr(\(t_d\) = H) < 1/2 for the defender’s type \(t_d\).
Therefore, \(P_h\) < 1/2.)
– 아래 평형을 구하기 위한 가정
1) (x, y) = (1, 1)
a pooling strategy in which both types send message h
p = \(P_h\) but q is unrestricted
If h was sent, A is BR given p = \(P_h\) < 0.5
Suppose n was sent and q < 0.5 → A is BR
Not an eqbm
Suppose n was sent but q ≥ 0.5 and \(c_t > c_p\) → L is BR
Both types wouldn’t deviate, and thus it is an eqbm
There exists on perfect Bayesian eqbm in pooling strategies:
⟨(hh, AL), p = \(P_h\), q ≥ 0.5⟩
But, not an eqbm this normal type would deviate to n
if \(P_h\) > 0.5, pooling strategies: ⟨(hh, LA), p = \(P_h\), q ≤ 0.5⟩
But, also not an eqbm this normal type would deviate to n
2) (x, y) = (1, 0)
a separating strategy in which the honeypot type sends h but the normal type sends n.
attacker exactly infers defender type from the message sent A is a BR to h and L is a BR to n
⟨(hn, AL), p = \(P_h\), q ≤ 0.5⟩
In this setting, the attacker’s beliefs can be updated to p = 1 and q = 0.
방어자가 어떤 유형을 선택하든 허니팟/일반 유형의 경우 각각 \(b_d-c_h\), 0보다 높은 보상을 얻을 수 없다.
3) (x, y) = (0, 1)
a separating strategy in which the honeypot type sends n but the normal type sends h.
attacker exactly infers defender type from the message sent A is a BR to h and L is a BR to n
⟨(nh, LA), p = \(P_h\), q ≤ 0.5⟩
But, not an eqbm this normal type would deviate to n
4) (x, y) = (0, 0)
a pooling strategy in which both types send message n
q = \(P_h\) < 0.5 but p is unrestricted
⟨(nn, AL), p ≥ 0.5, q = \(P_h\)⟩
But, not an eqbm this honeypot type would deviate to h
If p < 0.5, attacker will Attack whether defender orders Honeypot or Normal
So defender has an incentive to debate.
In the normal type, attacker has no incentive to debate because defender gets \(-c_a\) or 0 from n.
So there is no PBE when p is less than 0.5.
comments #2
Intuitive criterion
1) 우선, out-of-equilibrium을 제한함으로써, 직관적이지 않은 평형을 제거할 수 있다.
(off-the-equilibrium이라는 용어가 CHO, I. AND KREPS, D. (1987) 논문에서는 out-of이라 쓰임)
2) 평형을 구성하는 것은“해석(interpretations)”의 영향을 받으며,
해석이란, 평형에서 벗어난 메시지에 대해 제2의 플레이어가 줄 수 있는 것을 의미
(기존 평형을 이탈해서 더 높은 수준을 얻을 수 있는지를 의미하는 것으로 해석함)
defender type이 Honeypot, Normal에서 각각 signal h, n일 때 Cho and Kreps’ (1987) Intuitive Criterion을 만족하는지 확인한다.
1. Check if the pooling equilibrium in which both types of defender have ‘signal h’ survives the Cho and Kreps’ (1987) Intuitive Criterion.
1) if \(P_h\) > 0.5, <hh, LA>
Cho와 Kreps의 (1987) 직관적인 기준의 첫 번째 단계에서,
equilibrium dominated되는 off-the-equilibrium messages를 제거한다.
Honeypot-type defender에서, normal signal이 (honeypot signal 대비) 평형 utility level을 향상시킬 수 있는지를 확인해야 한다. 즉,
\(u_d^*(signal h|Honeypot)\) < \(Max u_d(signal n|Honeypot)\)
- 좌변의 equilibrium payoff가 \(-c_h\)
- 우변의 Highest payoff from deviating towards signal n, \(b_d-c_h\)
But this condition is not satisfied: 확실히 defender는 signal h의 평형 상태에서 \(-c_h\)의 보수를 얻고, signal n으로 이탈하는 것에서 얻을 수 있는 보수는 \(b_d-c_h\)을 얻기 때문에 이 유형은 signal h에서 signal n으로 벗어날 것이다.
\(u_d^*(signal h|Normal)\) > \(Max u_d(signal n|Normal)\)
- 좌변의 equilibrium payoff가 \(-c_n\)
- 우변의 Highest payoff from deviating towards signal n, 0
attacker가 Attack이 아닌 Leave without attack을 선택한다면 이 조건은 실제로 충족될 수 있다.
Normal defender는 이 pooling equilibrium에서 \(-c_n\) 대신 0의 보수를 얻을 것이다.
따라서 defender에게 이 separating PBE에서 벗어날 incentives가 존재한다.
따라서 attacker의 belief는, signal n의 off-the-equilibrium message를 관찰한 후, \(\Theta(signal n)\) = {Honeypot, Normal} 두 경우 모두 존재하기에 제한된 기준을 설정할 수 없다.
2) if \(P_h\) < 0.5, <hh, AL>
First step:
\(u_d^*(signal h|Honeypot)\) < \(Max u_d(signal n|Honeypot)\)
- 좌변의 equilibrium payoff가 \(b_d-c_h\)
- 우변의 Highest payoff from deviating towards signal n, \(b_d-c_h\)
But this condition is not satisfied: 확실히 defender는 signal h의 평형 상태에서 \(b_d-c_h\)의 보수를 얻고, signal n으로 이탈하는 것에서 얻을 수 있는 보수 또한 \(b_d-c_h\)으로 동일하다.
따라서 이 유형은 signal h에서 벗어나지 않을 것이다.
\(u_d^*(signal h|Normal)\) > \(Max u_d(signal n|Normal)\)
- 좌변의 equilibrium payoff가 \(-c_a-c_n\)
- 우변의 Highest payoff from deviating towards signal n, 0
attacker가 Attack이 아닌 Leave without attack을 선택한다면 이 조건은 실제로 충족될 수 있다.
Normal defender는 이 pooling equilibrium에서 \(-c_a-c_n\) 대신 0의 보수를 얻을 것이다.
따라서 defender에게 이 separating PBE에서 벗어날 incentives가 존재한다.
Second step:
따라서 attacker의 belief는, signal n의 off-the-equilibrium message를 관찰한 후, \(\Theta(signal n)\) = {Normal}로 제한될 수 있다.
즉, attacker는 defender가 signal n을 선택하는 것을 관찰한다면, 공격자는 방어자가 Normal Type을 선택했다고 믿을 것이다.
그 이유는, signal h의 pooling equilibrium에서 벗어나서 이익을 얻을 수 있는 유일한 defender 유형이기 때문이다.
이러한 맥락에서, 이 조건은 Normal type에 대해 유지된다.
attacker는 믿음에 따라 signal n을 받을 경우, Attack하는 것이 node를 Leave하는 것보다 더 큰 payoff \((b_s > -c_p)\)를 얻기 때문에, defender 또한 더 큰 payoff를 얻을 수 있는 signal n으로 벗어난다. \((-c_a-c_n < -c_a)\)
따라서 signal h에 대한 pooling equilibrium은 Cho and Kreps의 직관적인 기준에 의해 살아남지 못한다.
2. Check if the pooling equilibrium in which both types of defender have ‘signal n’ survives the Cho and Kreps’ (1987) Intuitive Criterion.
1) if \(P_h\) > 0.5, <nn, AL>
First step:
Cho와 Kreps의 (1987) 직관적인 기준의 첫 번째 단계에서,
equilibrium dominated되는 off-the-equilibrium messages를 제거한다.
Honeypot-type defender에서, honeypot signal이 (normal signal 대비) 평형 utility level을 향상시킬 수 있는지를 확인해야 한다. 즉,
\(u_d^*(signal n|Honeypot)\) < \(Max u_d(signal h|Honeypot)\)
- 좌변의 equilibrium payoff가 \(-c_h\)
- 우변의 Highest payoff from deviating towards signal h, \(b_d-c_h\)
attacker가 Leave without attack이 아닌 Attack을 선택한다면 이 조건은 실제로 충족될 수 있다.
Honeypot defender는 이 pooling equilibrium에서 \(-c_h\) 대신 \(b_d-c_h\)의 보수를 얻을 것이다.
따라서 defender에게 이 PBE에서 벗어날 incentives가 존재한다.
\(u_d^*(signal n|Normal)\) > \(Max u_d(signal h|Normal)\)
- 좌변의 equilibrium payoff가 0
- 우변의 Highest payoff from deviating towards signal h, \(-c_n\)
But this condition is not satisfied: 확실히 defender는 signal n의 평형 상태에서 0의 보수를 얻고, signal h으로 이탈하는 것에서 얻을 수 있는 보수는 \(-c_n\)으로 이 유형은 signal n에서 벗어나지 않을 것이다.
Second step:
따라서 attacker의 belief는, signal h의 off-the-equilibrium message를 관찰한 후, \(\Theta(signal h)\) = {Honeypot}로 제한될 수 있다.
즉, attacker는 defender가 signal h을 선택하는 것을 관찰한다면, 공격자는 방어자가 Honeypot Type을 선택했다고 믿을 것이다.
그 이유는, signal h의 pooling equilibrium에서 벗어나서 이익을 얻을 수 있는 유일한 defender 유형이기 때문이다.
이러한 맥락에서, 이 조건은 Honeypot type에 대해 유지된다.
attacker는 믿음에 따라 signal h을 받을 경우, Leave without attack하는 것이 Attack하는 것보다 더 큰 payoff \((-c_t < -c_p)\)를 얻으나, defender는 payoff가 동일하므로 signal h, n 중 어느 것을 선택해도 상관이 없다. \((-c_h = -c_h)\)
2) if \(P_h\) < 0.5, <nn, AA>
First step:
\(u_d^*(signal n|Honeypot)\) < \(Max u_d(signal h|Honeypot)\)
- 좌변의 equilibrium payoff가 \(b_d-c_h\)
- 우변의 Highest payoff from deviating towards signal h, \(b_d-c_h\)
But this condition is not satisfied: 확실히 defender는 signal h의 평형 상태에서 \(b_d-c_h\)의 보수를 얻고, signal n으로 이탈하는 것에서 얻을 수 있는 보수 또한 \(b_d-c_h\)으로 동일하다.
따라서 이 유형은 signal n에서 벗어나지 않을 것이다.
\(u_d^*(signal n|Normal)\) > \(Max u_d(signal h|Normal)\)
- 좌변의 equilibrium payoff가 \(-c_a\)
- 우변의 Highest payoff from deviating towards signal h, \(-c_n\)
attacker가 Attack이 아닌 Leave without attack을 선택한다면 이 조건은 실제로 충족될 수 있다.
Honeypot defender는 이 pooling equilibrium에서 \(-c_a\) 대신 \(-c_n\)의 보수를 얻을 것이다.
따라서 defender에게 이 PBE에서 벗어날 incentives가 존재한다.
Second step:
따라서 attacker의 belief는, signal n의 off-the-equilibrium message를 관찰한 후, \(\Theta(signal h)\) = {Normal}로 제한될 수 있다.
즉, attacker는 defender가 signal h을 선택하는 것을 관찰한다면, 공격자는 방어자가 Normal Type을 선택했다고 믿을 것이다.
그 이유는, signal h의 pooling equilibrium에서 벗어나서 이익을 얻을 수 있는 유일한 defender 유형이기 때문이다.
이러한 맥락에서, 이 조건은 Normal type에 대해 유지된다.
attacker는 믿음에 따라 signal h을 받을 경우, Attack하는 것이 Leave without attack하는 것보다 더 큰 payoff \((b_s > -c_p)\)를 얻으나, defender는 더 큰 payoff를 얻을 수 있는 기존 signal n에서 벗어나지 않는다. \((-c_a-c_n < -c_a)\)
따라서 signal n에 대한 pooling equilibrium은 Cho and Kreps의 직관적인 기준에 의해 살아남는다.
5. Conclusions
#1. Existence of semi-separating PBEs
\(c_n\)의 값이 0일 때 semi-separating PBE를 만족하는 지점이 존재한다.(조건에 관계없이 모두 semi-separating PBE를 만족한다.)
이는 필요충분조건을 만족하며, \(c_n\)이 0이 아닌 경우 해당 PBE는 존재하지 않는다. (위의 분석(4. Analysis)에서는 귀류법으로 증명했다.)
따라서 이 논문의 모델에서 설정한 파라미터가 일반적인(0이 아닌) 값을 갖는 경우, semi-separating PBE는 존재하지 않는다.
#2. PBE that satisfy the Cho-Kreps criterion
Full-Featured(c) 허니팟 게임에서 다음의 풀링 전략 ((n, n), (A, A))은 Cho and Kreps의 직관적인 기준에 의해 지워지지 않는 PBE이다.
이는 \(P_h\) < 0.5인 상황에서, 허니팟 유형 및 정상 유형이 신호 n을 보낼 때 유지되는 평형이다.
6. References
- Suhyeon Lee, Kwangsoo Cho, and Seungjoo Kim, “Do You Really Need to Disguise Normal Servers as Honeypots?”, In Proceedings of the 40th International Conference on IEEE Military Communications Conference (MILCOM 2022), pp. 166-172, Rockville, MD, US, November 2022.
- CHO, I. AND KREPS, D. (1987), “Signaling games and stable equilibria”, Quarterly Journal of Economics, 102, pp. 179-221.
- Felix Munoz-Garcia, Ana Espinola-Arredondo, “The Intuitive and Divinity Criterion: Interpretation and Step-by-Step Examples,” Journal of Industrial Organization Education, Volume 5, Issue 1, Pages 1–20, ISSN (Online) 1935-5041, DOI: 10.2202/1935-5041.1024, March 2011.
- Muhamet Yildiz, “Signaling”, mit.edu, 14.12 Game Theory
- Cheol Park, “Plausibility of the Intuitive Criterion of Cho and Kreps”
- Felix Munoz-Garcia, Daniel Toro-Gonzalez, Strategy and Game Theory – Practice Exercises with Answers, Springer Texts in Business and Economics, p.305-309