基于扩展调用图的软件系统结点重要度评价方法

摘要

一种基于扩展调用图的软件系统结点重要度评价方法，涉及软件工程领域，所述方法适用于软件系统，可以给出整个软件系统内函数和数据结点的重要度指标，并按照重要度指标进行排序，从而迅速找到软件系统中的关键结点。方法的主要步骤如下：编译源代码得到目标文件；从目标文件出发，构建软件系统所有本地代码的扩展调用图；对扩展调用图进行分析，利用结点排序算法计算扩展调用图中每个结点的重要度指标，该指标即表明结点在软件系统中的重要度。本发明具有应用范围广、准确度高、评价合理、自动化程度高、使用方便等特点。

主权项

一种基于扩展调用图的软件系统结点重要度评价方法，其特征在于，是在计算机中依次按以下步骤实现的：步骤(1)：编译软件系统的源代码，生成可重定位的目标文件；步骤(1.1)：获得软件源代码，在编译配置文件中增加编译选项使编译器把每个函数、每个数据对象编译到单独的段中，所述数据对象既包括源代码中定义的全局和静态变量，也至少包括编译器生成的虚函数表，所述函数和数据对象统称为“实体”；步骤(1.2)编译所述软件源代码生成可重定位的目标文件；步骤(2)：按以下步骤构造有向的所述软件系统的扩展调用图：步骤(2.1)：对步骤(1)得到的所述目标文件，读取以下信息：所述目标文件中所有的内含所述实体的段的名称集合SS，所述目标文件中定义的所有符号中包含的全局符号及其名称GS，并以全局符号名——段名关联表的形式存储，头和尾都属于同一个所述目标文件的有向边形成的集合AF，头属于所述的目标文件，尾为暂未被解析的符号的有向边，所述有向边中每一个元素表示为(u,sym)，其中u属于所属目标文件中所有包含着所述实体的段的集合，sym为一个所述有向边外部符号的名，表示被实体u引用，但所述外部符号sym是一个不在同一个所述目标文件中定义的实体；步骤(2.2)，根据步骤(2.1)中所得到的全部信息，合并为一个软件系统全局的有向图，从而得到所述软件系统的扩展调用图的V和E，其中：V为所有所述目标文件中所有所述实体的段的名称集合SS的并集，是一个结点集，其中，每一个结点v的名称用一个由目标文件名和段名组成的二元组表示，E为有向边集E：E＝E1∪E2，其中:E1为所有所述目标文件的AF的并集，代表头和尾都属于同一个目标文件的所有有向边的集合，E2为头和尾属于不同的目标文件的所有有向边形成的集合，按以下方法得到：令遍历每一个目标文件中，头属于相同目标文件，但尾为暂未解析的全局符号的有向边的集合AU，对有向边中每一个元素(u,sym)，查找所有所述目标文件的所有外部符号的名称以及所述全局符号所在段的名称的GS集合，得到所有头和尾不在同一目标文件中的所有名称为sym的全局符号的所述实体集合S[sym]，把目标文件中的一个结点u和结点v共同组成的所有二元组(u,v)|v∈S[sym]加入所述集合E2，再把E1与E2两个集合取并集，得到所述有向边集合E，其中，每一个元素是一对结点(u,v)，对应于所述软件系统扩展调用图中一条从结点u到结点v的有向边，当且仅当结点u的重定位数据中有相对结点v的重定位记录时，在所述软件系统扩展调用图中才存在一条目标文件之间从结点u指向含有段的名称为结点v的有向边，所述两个目标文件允许是相同的，也允许是不同的；步骤(2.3)，按以下步骤得到入口结点集R：步骤(2.3.1)，令步骤(2.3.2)，把与程序启动代码对应的所述实体作为一个结点加入所述入口结点集R，步骤(2.3.3)，把通过动态绑定使用的所述实体作为一个结点加入所述入口结点集R，步骤(2.4)，把从步骤(2.1)～步骤(2.3)得到的V、E、R表示为一个所述软件系统的扩展调用图G＝(V,E,R)；步骤(3)，按如下结点排序算法分析步骤(2)给出的所述软件系统扩展调用图G，计算所述软件系统中每个结点的重要度，步骤如下：定义：NR为入口结点集R中入口结点的数量；L(v)为以结点v为源结点的边数，称为结点v的出度；L(u)为以结点u为源结点的边数，称为结点u的出度，集合Leaf＝{v|L(v)＝0,且v∈V}，或者Leaf＝{u|L(u)＝0,且u∈V}，表示所有出度为0的结点的集合；当用结点u表示所处的结点，且结点u为结点v的前驱结点的条件是存在一条源结点为u，目的结点为v的边；B_v为结点v的所有前驱结点u的集合；Rank(v)为结点v的重要度，Rank(v)为一个在0～1之间的实数；ε为容错因子，设Rank^t和Rank^t+1为相邻的两次迭代时计算得出的Rank值，迭代计算终止计算的条件为：$\sqrt{{\Sigma }_{v\in V}{[{\mathrm{Rank}}^{t+1}\left(v\right)-{\mathrm{Rank}}^t\left(v\right)]}^2}<ϵ,ϵ=0.001,$步骤(3.1)，赋予结点集V中的每个结点一个初始Rank值，对入口结点赋值1/NR，非入口结点赋予为0；步骤(3.2)，对于不包括所有所述入口结点在内的结点集中的每个结点v，计算t+1时刻的重要度值：${\mathrm{Rank}}^{t+1}\left(v\right)={\Sigma }_{u\in B_v}{\mathrm{Rank}}^t\left(u\right)/L\left(u\right);$对于所述入口结点集R中的每个结点r，Rank^t+1(r)为所有所述前驱结点u的重要度之和再加上所有所述出度为零的节点的重要度之和，表示为：${\mathrm{Rank}}^{k+1}\left(r\right)={\Sigma }_{u\in B_r}{\mathrm{Rank}}^t\left(u\right)/L\left(u\right)+{\Sigma }_{u\in Leaf}{\mathrm{Rank}}^t\left(u\right)/NR;$步骤(3.3)，按下如公式计算重要度误差$\sqrt{{\Sigma }_{v\in V}{[{\mathrm{Rank}}^{t+1}\left(v\right)-{\mathrm{Rank}}^t(v\left)\right]}^2},$步骤(3.4)判断步骤(3.3)得到的重要度误差是否小于容错因子ε，若误差不小于ε，返回步骤(3.2)，直到满足误差小于ε，若误差小于ε，则终止计算；步骤(3.4)，排序并输出每个结点的最终Rank值，即结点的重要度。