Research Of Software Subgraph Pattern Mining Algorithms Based On Software Execution Graph

With the increasing of software scale and application fields,software quality and safety has become a crucial issue.A large amount of data is generated during software running,in order to make better use of the data and improve the software quality as well as guarantee the software security,data mining is applied to the study of software structure characteristics,and becomes a hot and interesting research direction.We focus on the dynamic trajectory of the software in this paper,and use the graph mining technology to dig out the subgraph patterns which the users are interested in from the massive execution path of the software.It can be used to enhance the software performance,to analyze the software structure and to dig out software vulnerabilities?Firstly,the behavior characteristics of the software are modeled based on the software dynamic execution trajectory.Each time the function call is treated as a software execution graph which forms the software execution graph database,and then the graph database is scanned and merged into a software-weighted execution graph.Secondly,in order to dig out the subgraphs that are frequently called during the execution of the software,we propose a maximum frequent subgraph mining algorithm which based on software execution graph database.The binary code is adopted to record the situation of each edge which is obtained by scanning the database only once.And then the edge will be classified according to the binary code,and then expand the edges on the basis of this classification and pruning strategies,finally we can get the most frequent subgraphs.Thirdly,for more targeted mining,the weight is introduced into the graph mining which allows the user to adjust according to the prior knowledge.In addition,inspired by the thought of important nodes,the importance measure and the module independence measure are proposed.And then we put forward a weighted feature subgraph mining algorithm based on software weighting graph,two metrics are used as a basis for expansion,and ultimately dig out the subgraphs which the users are interested in.Finally,the two algorithms proposed in this paper are implemented and experimentedon the real data set.At the same time,the performance of the algorithm in terms of running time,scalability and the results of mining are analyzed.