## 4 Survey from the Attacker's Perspective
### Related Work
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Type** & **Ref** & **U** & **P** & **C** & **N** & **Policy** & **Description** \\ \hline \multirow{8}{*}{POMDP} & [41] & ✓ & ✓ & \(\times\) & \(\times\) & SARSOP [42] & (1) Introduce beliefs to reflect uncertainty; (2) Excessive computational complexity. \\ \cline{2-8}  & [43] & ✓ & ✓ & \(\times\) & \(\times\) & Improved & (1) Introduce network structure to reduce complexity; (2) Not applicable when structure changes. \\ \cline{2-8}  & [44] & ✓ & \(\times\) & \(\times\) & \(\times\) & Improved RL & Introduce the network information gain to evaluate actions. \\ \cline{2-8}  & [45] & ✓ & ✓ & ✓ & \(\times\) & Improved & Introduce the information decay factor to reflect the influence of the adversary. \\ \cline{2-8}  & [46] & ✓ & ✓ & \(\times\) & \(\times\) & Improved & (1) Path coverage exceeds that of human in small networks; (2) Computational cost exceeds that of human on medium LANs. \\ \hline \multirow{8}{*}{MDP} & [40] & ✓ & \(\times\) & \(\times\) & \(\times\) & - & Modeling as deterministic planning. \\ \cline{2-8}  & [48] & ✓ & \(\times\) & \(\times\) & \(\times\) & Q-learning, Deep & (1) Build a system to simulate attack; (2) Ignore & \\ \cline{2-8}  & [49] & ✓ & \(\times\) & \(\times\) & \(\times\) & DQN with WA [50] & (1) Introduce “WA” to reduce action space; (2) Use graph embedding method to abstract state; (3) Low-dimensional vectors lacks interpretability. \\ \cline{2-8}  & [51] & ✓ & \(\times\) & \(\times\) & \(\times\) & RNN & The RNN algorithm can also work well when the environment changes. \\ \cline{2-8}  & [52] & ✓ & \(\times\) & \(\times\) & \(\times\) & A2C, Q-Learning, SARSA & (1) The A2C algorithm performs better than other algorithms. (2) State representation lacks interpretability. \\ \cline{2-8}  & [53] & ✓ & \(\times\) & \(\times\) & \(\times\) & DQN, PPO & (1) The stability and generalization are discussed for the first time. (2) Current algorithms have poor generalization performance. \\ \hline \multirow{8}{*}{Markov Game} & [54] & ✓ & \(\times\) & ✓ & ✓ & Planning-based & Design dynamic network configurations to compare attack and defense interactions. \\ \cline{2-8}  & [55] & ✓ & \(\times\) & ✓ & \(\times\) & Strategy sets & (1) The adaptability of algorithms to the adversary is verified. (2) The task is far from real world. \\ \cline{2-8}  & [56] & ✓ & \(\times\) & ✓ & ✓ & Q-learning, DQN, XCS [57] & (1) Designed a attack-defense multi-agent system. (2) Different action usages are not discussed. \\ \cline{2-8}  & [58] & ✓ & \(\times\) & ✓ & \(\times\) & DQN & (1) Verify the algorithm’s applicability. (2) The defined model is difficult to scale. \\ \hline \hline \end{tabular} Note: U indicates “Unknown environment”, P indicates “Partial observability”, C indicates “Competitive environment” and N indicates “Non-competitive environment”.  
\end{table} 
Table 1: Survey from the attacker’s perspective. Due to the limited complexity of planning algorithms, some researchers began to use reinforcement learning algorithms to solve this problem. [PERSON] et al. introduce the network information gain to as the signal for evaluating actions' reward [44]. The information gain is equal to \(H(P)=\sum_{j=1}^{|p|}(p_{j}\log p_{j}+(1-p_{j})\log(1-p_{j}))\), where \(P_{j}\) represents the vector of operating system, open service, port, and protection mechanism probability distribution before (after) taking actions. Experiments showed that RL algorithms with information gain are more effective than other algorithms at finding attack paths. In addition to considering an \"unknown environment\", [PERSON] et al. also took into account the influence of the opponent, and proposed an information decay factor to represent the observation of the attacker [59]. The author used the Bernoulli process to model the defender's behaviors, and verified that the Bayesian Reinforcement Learning (BRL) algorithms combined with the information decay factor is significantly better than the baseline algorithm in terms of winning rate and reward.