Research, Graph-based Network Security Game

Network security is a comprehensive topic which refers to many subjects, such as computer science, network technology, communication technology, cryptogram technology, information security technology, applied mathematics, theory of numbers, information theory and so on. Network security has been defined as: protect software, hardware and information resource of network system from accidental or malicious destruction, interpolation and revelation, and guarantee the normal operation of network systems and network services without disruption. Along with the expansion of network size and the dynamic development of network, the network security problem has been paid more attention and made a broad research.Essentially, network security is a confrontment between attacker and protector, so, we apply the idea of game theory to network attack and defense in the process of research. A network topology structure can be indicated by a graph. We can study the structure of network by studying the character of the graph. The theory of studying the character of graphs is the graph theory. In the paper we study network security through the related knowledge of graph theory and game theory.All graphs considered in this paper are finite undirected simple graphs G(V, E) with |V(G)| -n and |E(G)| = m. An information networks is represented as an undirected graph G(V,E). The vertices represent the network hosts and the edges represent the communication links. We turn network security problem into a non-cooperative multi-player strategy game on a graph.The paper is divided into six chapters. We mainly study three kind of graph-theoretic network security games, and obtain some results.In the paper we first study game between viral attackers and system protectors, have proven that mixed Nash equilibria can be computed, in polynomial time, for specific graph instances of the attacker-protector game. These graph families include, regular graphs, graphs with perfect matching, non-bipartite graphs. Moreover, in view of another way to attack the network for the attackers, a new attacker-protector model called trial model is proposed, the existence of pure Nash equilibria in trial model is proved, and we compare trial model with edge model and path model given by Mavronicolas.Then, we study inoculation strategic game for victims of viruses. We have analyzed the compution and hardness of pure Nash equilibria in inoculation strategic game for victims of viruses, and have proven that computing the best or worst pure Nash equilibria is hard, but that finding some intermediate Nash equilibria is easy. In particular, a description of how the worst Nash equilibria reacts to changes in the inoculation cost is given. The lower bound and the upper bound of the price of anarchy are proved.In addition, we also study secure transmission game of network data. This paper have proven the existence of the mixed Nash equilibrium theoretically in secure transmission game of network data, which is further illustrated by the experimental results with the specific network topology. And the profit in the point of equilibrium for attacker and protector is maximum.