Research On Graph Partitioning Problems In Cyberspace Security Analysis

In the information age,the vigorous development of the Internet promotes the progress of society and affects all aspects of our lives.People’s dependence on the Internet has prompted the urgent need for research in the field of cyberspace security.By considering the hosts and servers in the network as points,and the connections or paths between them as edges,computer networks can be abstracted into graphs,which also reveals the close connection between information network science and graph theory.In the research of computer science,researchers often use graph models to depict and analyze networks,and use graph theory to solve practical problems.Among them,graph partitioning method has a very broad application prospect in the research of related problems of network security,such as network decentralization and network stability analysis,etc.At the same time,the graph partitioning theory plays an important role in the graph theory,which has produced many famous research results,and also has important application value in many fields,such as large-scale integrated circuit design.This thesis focuses on the graph partitioning theory in cyberspace security,and mainly analyzes the partitioning modes including feasible partitioning,judicious partitioning and a special class of partitioning-Erd(?)s-Pósa property and transversal set.The importance of the undirected graph model in the application is obvious,and the directed graph model is an effective tool for network security analysis.Therefore,this thesis considers both directed and undirected graphs(including simple graphs and multigraphs).The specific research work and contributions are stated below.1.Transform the network reliability and the problem of decentralization into the partitioning problem of simple graphs and multigraphs under minimum degree constraint,and obtain the conditions to ensure the existence of feasible partitions.Network reliability is closely related to the connectivity of graph theory,and the broadband sharing network approach plays an important role in it.Since centralized network is prone to large-scale network breakdown under attack,people begin to seek for a more stable network mode,and then decentralization gradually becomes the direction of people’s attention.In order to solve this problem,we study the feasible partitioning problem for simple graphs and multigraphs respectively,and consider what kind of minimum degree constraint is needed to satisfy the existence of feasible partitions in Chapter 2.Take the graph G and two vertex assignment functions a,b:V(G)→N\{0,1},if a vertex partition(A,B)satisfies dA(x)≥a(x)for any x∈A,and dB(y)≥b(y)for any y∈B,then(A,B)is called an(a,b)-feasible partition.In view of the feasible partitioning problem,the method of reduction to absurdity and structural analysis is adopted.Firstly,the weight function is defined for the partition,and then the vertex shift operation is performed between the initial two parts to observe the change of the value of the weight function,and then the structure is analyzed to find the contradiction.The degree constraint plays an important role in the calculation of the weight function.The specific research conclusions are described as follows.·Firstly,about some special families of simple graphs,several results are proved:let G be a H-free simple graph,(ⅰ)if H ∈{l5+,{L3+},{F1,1},{F2,0,F0,2}},then the degree constraint dG(x)≥a(x)+b(x)can guarantee the existence of an(a,b)-feasible partition.(ⅱ)if H={C3,C6,H},then the degree constraint dG(x)≥a(x)+b(x)-1 can guarantee the existence of an(a,b)-feasible partition,where H is the graph obtained from K4 by replacing two disjoint edges with two internally disjoint paths of length 2 and 3,respectively.These results can cover many existing conclusions,and have tightness.·Secondly,a counterexample is found to prove the result:let G be a graph that does not contain triangles and K2,3,the degree constraint dG(x)≥a(x)+b(x)-1 does not guarantee the existence of an(a,b)-feasible partition.This conclusion gives a negative answer to Liu and Xu’s question.·Finally,for the multigraph G,if no quadrilaterals share edges with triangles and other quadrilaterals,then the degree constraint dG(x)≥a(x)+b(x)+2μG(x)-3 guarantees the existence of an(a,b)-feasible partition.2.The attack graph model is used to discuss the problem of cyberspace security risk assessment.The judicious partitioning of directed graphs and undirected graphs is studied,and the partitioning method satisfying the optimizations of multiple parameters is found.From the perspective of attackers,cyberspace security risk assessment comprehensively analyzes network conditions to help network administrators clarify the network and improve network security.This problem can be abstracted as a discussion of the attack graph model.In order to solve this problem,the judicious partitioning of directed and undirected graphs is studied in Chapter 3,and it is committed to finding a partition that satisfies optimizations of multiple parameters at the same time.This chapter mainly adopts the method of vertex assignment,and gradually adds disturbances to the appropriate initial assignment until a partition that satisfies the conditions is found.This method has a great advantage:it can control the sizes of the two parts while optimizing multiple parameters.This also makes it easier to set the size conditions for the two parts according to the needs in subsequent applications.The specific research conclusions are described as follows.·For any directed graph D,our main focus is to find a partition that can optimize the values of e(V1,V2)and e(V2,V1)at the same time.We prove that D contains a partition V=V1∪V2 such that |V1|=[n/2]+k and |V2|=[n/2]-k,and min {e(V1,V2),e(V2,V1)} is no less than[([n/2]+k)([n/2]-k)m/n2-ρ/4-1/2],where ρ=maxu,ν∈V|s(u)-s(ν)| and s(u)=d+(u)-d-(u).This conclusion is tight.And the corollary of this theorem for k=0 improves many existing results.·Then for any undirected graph G,we mainly look for a partition that can optimize the values of e(V1)and e(V2)at the same time.We prove that G contains a partition V=V1∪V2 such that |V1|=[n/2]+k and |V2|=[n/2]-k,and max{e(V1),e(V2)}is no more than[([n/2+k)2m/n2+(Δ-δ+1)/4],where Δ and δ are the maximum and minimum degrees of the graph G,respectively.This conclusion is also tight.3.For the purpose of covering the cycle structures in graph networks,study the Birmele-Bondy-Reed conjecture on the Erd(?)s-Pósa property to find small transversal sets,and improve the existing bounds.The existence of cycle structure in a graph network will increase the complexity of analysis and the instability of network system,such as the problem of cycle-containing attack path in network security analysis.Therefore,we consider how to cover the cycle structure in the graph network.This problem is closely related to the well-known problem of feedback sets in theoretical computer science.In order to solve this problem,in Chapter 4,a special partitioning problem—transversal set is studied,and the BirmeléBondy-Reed conjucture on the Erd(?)s-Pósa property is discussed:for any integer l≥3,every graph G without two vertex-disjoint cycles of length at least l contains a set of at most l vertices which meets all cycles of length at least l.We analyse the structure and use Menger’s theorem to present a proof showing that the existence of such a transversal set with at most 3l/2+7/2 vertices.This improves the bounds 2l+3 for Birmelé,Bondy and Reed and 5l/3+29/2 for Meierling,Rautenbach and Sasse.