Establishing an Optimal Network Defense System: A Monte Carlo Graph Search Method

摘要

Establishing a complete network defense system is one of the hot research directions in recent years. Some approaches are based on attack graphs and heuristic algorithms, and others involve game theory. However, some of these algorithms lack clear key parameters, some are much affected by the structure of the graph. In this paper, we propose an algorithm called Monte Carlo Graph Search algorithm (MCGS) based on Monte Carlo Tree Search algorithm, a classic algorithm of game theory. Compared with other methods, our method is generally superior on the cost of time and space and barely affected by the structure of a graph. In addition, the steps of ours are more concise and work well for a graph. We design a system model of multiple attackers and one defender and combine it with our algorithm. A weight vector is designed for each host to describe its key information. After a number of iterations, the algorithm comes to an end along with an established optimal defense system. Experiments show that the algorithm is efficient and able to solve more problems since it is not limited to the structure of graph.