有向复杂网络结构熵的软件动态执行关键节点挖掘算法

Structure Entropy of Directed Complex Network Based Key Node Mining Algorithm in Software Dynamic Execution

软件缺陷具有继承性和传递性,根据软件动态执行的结构及节点间的关联关系,挖掘软件执行过程的关键点,对于软件缺陷的预防和排除具有重要意义.本文提出一种有向复杂网络结构熵的软件动态执行关键节点挖掘算法,首先,基于复杂网络思想将软件动态行为映射为有向复杂网络模型,进而引入结构熵的概念,根据节点的全局出度和入度,提出面向缺陷结构脆弱性和结构传播性的向下结构熵和向上结构熵的计算方法,并分别计算全局向下结构熵和向上结构熵的平均值,将满足平均结构熵的关键节点排名.最后,在开源软件数据集Cflow和Tar的最新版本上进行实验,与其它中心性算法对比并在SIR模型进行验证,在单个节点排名和前10名节点的关键性挖掘上证明了算法的有效性和优越性.

Software defect has the characteristics of inheritance and transmissibility,according to the structure of software dynamic execution and the node relationships,mining key nodes in software implementation process is of great significance to prevent and eliminate defects. In this paper,an algorithm called SDKS( Structure Entropy of Directed Complex Network based Key node mining algorithm in Software dynamic execution) is proposed. Inspired by the idea of complex network,we first map software dynamic behavior to complex network model. Then,the concept of structure entropy is introduced. Based on the global node out-degree and in-degree,the structural vulnerability and propagation of software defect oriented method for dow nward structure entropy and upward structure entropy calculation is designed,as well as the global average dow nward structure entropy and upward structure entropy,and the nodes satisfying global average dow nward structure entropy and upward structure entropy are sorted respectively as vulnerability and propagation key nodes. Finally,experiments are performed on the newest version of open source software Cflowand Tar,comparison is made with other centrality algorithms and verified on SIR model,which proves the effectiveness and superiority of our algorithm in single node ranking and the total key performance of the top-10 nodes.