# A Game-Theoretic Approach for Network Security Using Honeypots
## 3 Materials and Methods
### Problem Formulation
Even if the attacker is using some tools for reconnaissance, not all the information about the hosts and the services which are running on these hosts can be found. Even if there is no possibility to know all the vulnerabilities that coexist on a specific host, the defender can use the MITRE ATT&CK framework with the known vulnerabilities and misconfiguration status. The ATT&CK framework can provide a status report and help the defender better understand the network issues and decide whether to focus on a misconfiguration, security issue or other vulnerabilities [17]  
Our approach is to adopt the partially observable Markov decision process (POMDP) so that we focus on the defender's strategy to deceive the attacker and try to maximize their reward. As stated previously, using scanning tools, the attacker can gain some knowledge about the network in the reconnaissance state, and we can assume that each player can observe the partial state. Thus, we propose a solution for the partially observable stochastic game using the partially observable Markov decision process. Notations:  
\(V\) represents a vulnerability, where \(V=[V_{1},V_{2},V_{3},\ldots,V_{n}]\);  
\(F\) represents all the states in the action space, where \(F=[f_{1},f_{2},f_{3},\ldots,f_{n}]\);  
\(O^{a}\) represents the attacker's observations, where \(O^{a}=[o_{1}^{a},o_{2}^{a},o_{3}^{a},\ldots,o_{n}^{a}]\);  
\(O^{d}\) represents the defender's observations, where \(O^{d}=[o_{1}^{d},o_{2}^{d},o_{3}^{d},\ldots,o_{n}^{d}]\);  
\(B\) represents the belief states, where \(B=[b_{1},b_{2},b_{3},\ldots,b_{n}]\). A vulnerability is represented by a node \(V\) and the edge connecting two nodes \(V_{1}\) and \(V_{2}\) leads us to the statement that a second vulnerability represented by a second node \(V_{2}\) can be exploited only if the first vulnerability \(V_{1}\) is exploited. On their side, the attacker decides which node to attack by exploiting the vulnerability, and on the defender's side, they decide how many honeypots to use and where to deploy them along the graph edge. At this stage, we introduce \(O^{a}\) as an attacker's observation set and \(O^{d}\) as a defender's observation set and  
\[Pr(o_{n}^{a},o_{n}^{d},f_{n}|f_{1},o_{1}^{a},o_{1}^{d}) \tag{10}\]  
as being the probability of transition from state \(f_{1}\) to state \(f_{n}\) while observing \(O^{a},O^{d}\) under actions \(A,D\). \(G^{a}(f,d,a)\) represents the attacker's payoff in state \(f\), so we can assume that  
\[V(b_{n})=max_{a_{n}}[G^{a}(a_{n},f_{n})+\sum_{f\in F}\tau(f_{1},d,f_{n})V(f_{1})] \tag{11}\]  
Introducing in (11) the probable state update function \(\tau(f_{1},d,f_{n})\) connects the belief space to the action space and represents the core component of the function. The state transition and the observation of each transition must be known to calculate this function, and the defender knows the state transition model. Observations are connected to the attacker's actions, which denote the probability of seeing observation \(O\) while transitioning from belief state \(b\) to a state of belief \(b(f)\). \[p_{1}=1-\sum_{t\in T}\frac{a_{t}-h_{t}}{a_{t}}\]0  
The defender can estimate that at a given state \(f\in F\), the attacker played a specific action and calculate the possibility function as follows:  
\[p_{1}=1-\sum_{t\in T}\frac{a_{t}-h_{t}}{a_{t}}\]1  
From the survey in [7], we can see the difference between the two methods presented above by mentioning that the Markov decision process (MDP) can be applied to the visible state when we know everything about the network, but our proposed model using POMDP can be applied to the invisible state when an opponent in a game must observe, collect information and then act. Because the defender cannot be sure about a particular state, they need to determine in which state they are in by perceiving the environment and the concept of the belief state space can be introduced.