Researches Of Software Critical Nodes And Critical Paths Mining Based On Complex Network

With the advent of the information age, the software has been applied in different aspects of people’s lives, which is changing the way people communicating and living with each other. During this process, software structure has become increasingly complex and diversified. The software security issues are taken more and more attention by researchers. Researchers from various angles and multiple levels measure the security of complex software systems, for instance, software topology, how to abstract the topology of complex software to software execution network model, how to find the critical nodes which have more influential in software execution process, how to distinguish the critical nodes with similar structure, how to find the critical path and so on. These problems are became one of the main research works.In order to solve the problems mentioned above, this paper provides researches for mining critical nodes and critical paths in the software network with some open source softwares as experiment object.Firstly, in order to measure the topology structure of softwares, the software execution is converted to the software network. The directed and weighted software network model is built by taking functional modules of software as nodes, the call dependence between modules as edges, and the numbers of calls as weight value. GNU compilation tool and pvtrace tracer tool are used to track software execution path, and results are transformed into three columns matrix. A series of analysis are used to analyze the characteristics of network, such as nodes degree and degree distribution.Secondly, according to the cascading failure principle in complex networks, the nodes’ critical degree determines its influence in software normal running. Based on the directed and weighted software network model, this paper presents a critical node mining algorithm based on cascading failures principle. The algorithm uses depth-first search method to find the nodes in software execution network, the critical nodes are measured by calculating the influence of the affected nodes, and then they are graded and sorted.Thirdly, using the critical nodes measure mining method mentioned above, some nodes with similar structure may appear at the same level. To solve this problem, this paper presents a critical node mining algorithm based on Page Rank and betweenness measure methods. The algorithm uses test cases to form a result set firstly, and then uses the frequent subgraph mining method to determine the critical nodes set. To get the critical nodes in the software execution network more accurately, we put entropy into the measure metrics of Page Rank and betweenness methods, and sort the nodes.Finally, in order to mine critical path in software execution process, this paper proposes a critical path sequence mining algorithm. In this process, the 0/1 edge sequences are generated according to edges of software execution network, and stored in directed graph matrix. By sequence threshold and repetition rate of the edges, some irregular edges are deleted, and then critical paths in software execution network are obtained.Some experiments with open source softwares are provided to analyze the algorithms mentioned above. It is more effectively to find the critical nodes and critical paths in softwares which play important roles.