基于复杂网络的软件关键节点和关键路径挖掘方法研究

发布时间：2018-01-24 02:38

本文关键词： 复杂网络软件执行网络关键节点关键路径图序列　出处：《燕山大学》2016年博士论文　论文类型：学位论文

【摘要】：随着信息化时代的来临,软件已经被应用到人们生活的各个不同方面,不断改变着人们的交流和生活方式。而在这个过程中,软件系统的结构也越来越复杂化,多样化。随之带来的软件安全性问题也越来越受到研究者们的重视。研究者们从多个角度多个层次对复杂软件系统的安全性进行度量研究,例如从软件的拓扑结构方面进行分析研究。如何将复杂软件系统的拓扑结构抽象为软件执行网络模型,如何更加快速地发现对软件执行过程影响较大的关键节点,如何更好地区分具有相似结构的关键节点,如何快速地发现软件执行关键路径等问题也成为现今主要研究工作之一。为了解决上述提到的问题,本文对软件网络中关键节点和关键路径挖掘进行了研究,并辅以一些开源的软件作为实验对象进行分析研究。首先,为了更好地度量软件的拓扑结构,现将软件系统的执行转换为软件网络。将软件功能模块定义为节点,模块之间的调用依赖关系抽象为边,并将它们之间的调用次数设为边上的权值,以此来构建软件有向加权网络模型。使用GNU编译工具和pvtrace追踪工具来获得软件的执行路径情况,并将结果转换成三列矩阵,对其进行节点度以及度分布等一系列的特性分析。其次,根据复杂网络中相继故障原理,网络中节点的关键性程度决定其影响软件正常运行的大小。本文在软件有向加权网络模型的基础上,提出了一种基于相继故障原理的关键节点挖掘算法。该算法深度遍历软件执行网络中的各个节点,通过计算故障节点的影响力度来衡量该节点的关键性,并对其进行等级划分和排序操作。再次,使用上述关键节点度量挖掘方法时,可能会出现多个节点处于同一等级的情况。针对这一现象,本文提出了一种基于PageRank和介数度量方法的关键节点挖掘算法。该算法首先使用测试用例形成结果图集合,然后利用频繁子图挖掘方法确定关键节点集合,最后为了获得更准确地软件执行网络中关键节点,将熵运用到PageRank和介数两个方法度量中,并对节点进行排序。最后,为了挖掘软件执行过程中的关键路径,本文提出了一种关键路径挖掘算法。在这一过程中,按照软件执行网络中边出现情况生成对应的0/1边序列,并将形成的边序列存放到有向图矩阵中。利用序列频繁阀值和边重复率大小,去除不符合规则的边,从而获得软件执行网络的关键路径。对于上述提到的算法,本文以多种开源软件进行实验分析,发现能够这些研究方法能够更有效地挖掘软件中起到重要作用的关键节点和关键路径。
[Abstract]:With the advent of the information age, software has been applied to different aspects of people's lives, constantly changing people's communication and lifestyle. In this process, the structure of software systems is becoming more and more complex. The problem of software security has been paid more and more attention to by researchers, who measure the security of complex software systems from many angles and levels. For example, from the aspect of software topology analysis, how to abstract the topological structure of complex software system into software execution network model. How to find the key nodes which have a great influence on the software execution process more quickly, and how to better distinguish the key nodes with similar structure. How to quickly discover the critical path of software execution has become one of the main research work. In order to solve the above mentioned problems, this paper studies the key nodes and critical path mining in the software network. And with some open source software as experimental object to analyze and study. First, in order to better measure the software topology. Now the execution of the software system is transformed into the software network. The software function module is defined as the node, the call dependency between the modules is abstracted as the edge, and the number of calls between them is set to the weight of the edge. In this way, the software directed weighted network model is constructed, and the execution path of the software is obtained by using the GNU compiler tool and the pvtrace tracing tool, and the result is converted into a three-column matrix. A series of characteristics such as node degree and degree distribution are analyzed. Secondly, according to the principle of sequential fault in complex network. The critical degree of nodes in the network determines the size of the normal operation of the software. This paper is based on the software directed weighted network model. A key node mining algorithm based on sequential fault principle is proposed, which deeply traverses every node in the software execution network, and measures the key of the node by calculating the influence of the fault node. Thirdly, when we use the above key node metric mining method, there may be more than one node in the same level. In this paper, a key node mining algorithm based on PageRank and medium metric is proposed, which uses test cases to form the result graph set. Then we use frequent subgraph mining method to determine the set of key nodes. Finally, in order to obtain more accurate software execution network key nodes, entropy is applied to the measurement of PageRank and medium. Finally, in order to mine the critical path in the process of software execution, this paper proposes a key path mining algorithm. The corresponding 0/1 edge sequences are generated according to the occurrence of the edges in the software execution network, and the resulting edge sequences are stored in the directed graph matrix. The irregular edges are removed by using the sequence frequent threshold values and the size of the edge repetition rate. In order to obtain the critical path of software execution network. For the above mentioned algorithms, this paper uses a variety of open source software for experimental analysis. The key nodes and critical paths which play an important role in the software can be more effectively mined by these research methods.
【学位授予单位】：燕山大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】