基于k-truss的复杂软件关键模块识别方法
技术领域
1.本发明属于软件模块识别技术领域，尤其涉及一种基于k-truss的复杂软件关键模块识别方法。
背景技术：2.现代软件的开发与维护往往遵循着规范的软件开发周期来执行。常见的软件开发周期分为五个阶段，分别是：可行性研究阶段、需求分析阶段、软件设计阶段、软件测试阶段和软件维护阶段。其中，软件维护阶段是整个软件开发周期中持续时间最长的一个阶段，软件维护的过程决定了用户使用体验的好坏与软件能否持久稳定运行。作为软件维护的主要人员，开发者需要在理解软件的基础上对软件运行过程中出现的问题或即将出现的问题进行定位和排查。然而由于软件开发过程中需求、人员和资源等因素变化的不确定性，导致开发者在面对陌生软件维护工作时会遇到较大阻力。
3.p.meyer、h.siy和s.bhowmick提出一个使用k-core算法探测网络关键模块的方法。该方法首先根据软件静态依赖关系对软件经行建模，从而形成一个软件模块网络。网络中的每个节点代表软件中的一个功能模块，而连接两个节点的边则用以表示两个类之间的依赖关系。k-core算法是一种子图挖掘算法，其对子图的结构做出了一定限制，即子图的每个节点至少与该子图中的其他k个节点有关联。在此限制下，k-core算法能够在软件网络中挖掘符合指定核心度的紧密子图结构。其中k的值存在上限kmax，k-core算法在挖掘kmax-core的过程中能对软件模块网络中的每个节点的核心度进行计算并排序。最后该方法将核心度排名前3％的节点及其对应边作为关键模块网络进行输出。该方法的缺点是其使用的k-core算法对图结构的紧密程度要求不高，会导致最终得到的子图结构中存在较多次要节点信息，最终影响挖掘效率。
4.sehgal和kaur等人提出pagerank算法用来对网络关键模块进行探测。该方法基于的假设为，一个节点的核心度可随其相连节点进行一定程度的传播。在算法的初始阶段，其通过各个节点之间的关系对网络进行构建，并为每个节点设置一个pr(pagerank)值，表示其被访问的概率。而后该算法对pr值进行多轮迭代直至趋于稳定，从而获得每个节点的重要性排名。该方法不足在于其随机跳转的机制不符合现实情况，且迭代过程中的参数需要进行大量的实验计算，并不具有高效性。
技术实现要素：5.本发明目的在于提供一种基于k-truss的复杂软件关键模块识别方法,以解决上述的技术问题。
6.为解决上述技术问题，本发明的基于k-truss的复杂软件关键模块识别方法的具体技术方案如下：
7.一种基于k-truss的复杂软件关键模块识别方法，包括如下步骤：
8.步骤1：对原始软件预处理并转换为格式化软件模块网络：分析原始软件中各个模
块之间的依赖关系，将其转换为算法可识别的软件模块网络；
9.步骤2：使用k-truss算法对软件模块网络进行结构分析并挖掘关键节点：将软件模块网络输入到k-truss算法中，获取关键节点的相关信息；
10.步骤3：关键类识别输出：根据设定阈值将k-truss子图中的节点进行提取并输出。
11.进一步地，所述步骤1包括如下具体步骤：
12.将类作为关键模块识别的最小粒度，简称关键类，对原始软件进行预处理，将软件项目文件中的无关文件进行排除，仅保留后缀名为“.java”的文件用以生成软件模块网络,对软件模块网络进行定义：
13.smn＝(n，e，t)
14.其中，n表示网络的节点集合，包含软件中的类和抽象接口元素，e表示网络的边集合，包含各个节点之间的关系，t是一个三元组集合，表示边集合中各个边的属性及类型。
15.进一步地，所述步骤1包括对各个节点之间的关系类型定义，包括继承关系、实现关系、依赖关系、关联关系；所述继承关系指一个类a继承另一个类b，在java中以extends关键字实现；所述实现关系指一个类a实现一个接口b的功能，在java中以implements关键字实现；所述依赖关系指一个类a中使用了类b，其中类b作为类a的方法参数；所述关联关系指一个类的实例a使用了另一个类的实例b。
16.进一步地，所述步骤1包括一个源代码片段转化为软件模块网络的过程，每个类对应一个节点，若源代码中的两个类之间存在继承关系、实现关系、依赖关系、关联关系的一种关系，则在软件模块网络的对应节点之间增加一条边，使用上述规则进行转化，得到软件模块网络smn。
17.进一步地，所述步骤2包括如下具体步骤：
18.对于软件模块网络图smn＝(n，e，t)，图中任意一条边可表示为ei＝(u，v)，其中ei表示边，u和v分别表示这条边连接的两个节点，定义支持度support(ei)用来表示边ei在图中参与构成的三角形的个数，定义图kt是图smn的一个子图，若kt满足图中任意一条边的支持度support均满足support(ei)≥k-2，则称kt为一个k-truss子图。
19.进一步地，所述步骤3包括如下具体步骤：
20.获得k-truss子图后，对子图中的节点进行关键度排序，对于图中的任意节点，对其关键度进行如下定义：
[0021][0022]
其中，criv表示节点v的关键度值，m表示包含该节点的k-truss子图中节点数最小的子图所对应的k值，nm和n
m+1
分别表示m-truss和(m+1)-truss子图所包含的节点数量，若(m+1)-truss子图不存在，则n
m+1
取0；
[0023]
最后，根据上述方法计算出每个节点及其对应模块的关键度值并进行排序，选取前n个模块信息进行输出，n值根据需求确定。
[0024]
本发明的基于k-truss的复杂软件关键模块识别方法具有以下优点：本发明采用k-truss算法，该算法对子图结构的紧密程度要求更高，能减少输出结果中次要节点信息的比重，提升挖掘效率；本方法对节点的关系进行了定义，且实现简单；本发明采用k-truss算法对结构化模块网络中的模块节点进行重要性分析并探测其中的关键模块，而后提供给开
发者，从而提高开发者理解软件的效率，最终提高软件维护的质量。
附图说明
[0025]
图1为本发明的方法总览图；
[0026]
图2为本发明的smn生成示意图；
[0027]
图3为本发明的smn
ant
示意图；
[0028]
图4(a)为k-truss生成中的图g示意图；
[0029]
图4(b)为k-truss生成中的3-truss子图示意图；
[0030]
图4(c)为k-truss生成中的4-truss子图示意图；
[0031]
图5(a)为smn
ant
的k-truss子图生成中的3-truss子图示意图；
[0032]
图5(b)为smn
ant
的k-truss子图生成中的4-truss子图示意图；
[0033]
图5(c)为smn
ant
的k-truss子图生成中的5-truss子图示意图；
[0034]
图5(d)为smn
ant
的k-truss子图生成中的6-truss子图示意图；
[0035]
图5(e)为smn
ant
的k-truss子图生成中的7-truss子图示意图。
具体实施方式
[0036]
为了更好地了解本发明的目的、结构及功能，下面结合附图，对本发明一种基于k-truss的复杂软件关键模块识别方法做进一步详细的描述。
[0037]
对于现代软件而言，其整体通常由各类模块组合而成，故开发者可以通过模块作为他们理解软件的重点对象。关键模块是指实现软件核心功能的模块，对关键模块的识别和探测可以有效的提升开发者理解复杂软件的效率。k-truss是一种分层次递进的子图结构，其对图结构进行了约束，要求图中的每条边至少属于(k-2)个三角形。在此条件约束下的k-truss图结构能有效地反映整个图网络的可连接性、中心度等指标。同时相较于其他类似算法，k-truss由于其更为严格的结构定义约束，使其能更为有效地过滤无用信息，从而提高对图网络分析和研究的效率。本发明采用k-truss算法对结构化模块网络中的模块节点进行重要性分析并探测其中的关键模块，而后提供给开发者，从而提高开发者理解软件的效率，最终提高软件维护的质量。
[0038]
为了获取复杂软件中的关键模块信息列表(以下简称关键模块列表)，我们使用k-truss算法对预处理后的模块网络进行分析挖掘。为了获取能够被本方法使用的模块网络，我们会对原始软件进行预处理从而方便转换。如图1所示，本方法在使用过程中共有以下几个步骤：
[0039]
1)对原始软件预处理并转换为格式化软件模块网络。在这一步骤中，我们需要分析原始软件中各个模块之间的依赖关系，使用设定的规则将其转换为算法可识别的软件模块网络。
[0040]
2)使用k-truss算法对软件模块网络进行结构分析并挖掘关键节点。在该步骤中，我们将软件模块网络输入到k-truss算法中，获取关键节点的相关信息。
[0041]
3)关键类识别输出。该步骤中，我们根据设定阈值将k-truss子图中的节点进行提取并输出。
[0042]
方法具体步骤：
[0043]
1)原始软件预处理与软件网络生成
[0044]
下文中，我们会以开源软件apache ant为例，展示方法的各个步骤。由于apache ant是由java语言编译而成，所以我们遵循java软件的特点，将类作为我们关键模块识别的最小粒度(以下简称关键类)。
[0045]
原始软件由软件源代码文件和配置文件等内容组成。在java软件中，软件的核心代码、逻辑及依赖关系通常存在于后缀名为“.java”的文件中。为了以最大效率保证关键类信息的探测，本方法在对java面向对象软件进行关键类探测时，会对原始软件进行预处理，将软件项目文件中的无关文件进行排除，仅保留后缀名为“.java”的文件用以生成软件模块网络。首先，我们对软件模块网络(software module network)进行定义：
[0046]
smn＝(n，e，t)
[0047]
其中，n表示网络的节点集合，包含软件中的类和抽象接口等元素。e表示网络的边集合，包含各个节点之间的关系。t是一个三元组集合，表示边集合中各个边的属性及类型。我们对各个节点之间的关系类型定义如表1所示：
[0048]
表1.节点关系类型表
[0049][0050][0051]
图2描述了一个源代码片段转化为软件模块网络的过程。图的上半部分是源代码的内容，其中包含有六个java类，分别为human,student,address,book,live和freelive，图的下半部分为转化后的软件模块网络图。图中的六个节点与源代码中的六个java类相对应，若源代码中的两个类之间存在表1描述的关系，则在软件模块网络的对应节点之间增加一条边。
[0052]
其中student类继承自human类，与book类存在依赖关系，并与address类存在关联关系，故student节点分别与human、book和address节点存在边关系。freelive类为live类的接口实现，并与address类存在关联关系，故freelive节点分别与live和address节点存在边关系。最终通过转化我们得到了源代码对应的smn图。
[0053]
对于apache ant软件的源代码而言，我们使用上述规则进行转化，可以得到如图3所示的软件模块网络smn
ant
。为了方便程序处理和图片展示，我们为每个类及其对应的节点进行了编号，图中的数字为每个节点对应的编号。
[0054]
2)k-truss算法分析及关键节点挖掘
[0055]
对于软件模块网络图smn＝(n，e，t)，图中任意一条边可表示为ei＝(u，v)，其中ei表示边，u和v分别表示这条边连接的两个节点。定义支持度support(ei)用来表示边ei在图中参与构成的三角形的个数。定义图kt是图smn的一个子图，若kt满足图中任意一条边的支持度support均满足support(ei)≥k-2，则称kt为一个k-truss子图。
[0056]
如图4(a)所示，图g为一个包含10个节点和17条边的无向图，根据上述规则，我们删除节点7和节点9以及它们连接的边，即可得到图4(b)所示的3-truss子图，根据上文定义可知，3-truss子图中的每条边都属于1个三角形。而后我们继续删除3、6、8和10节点以及它们连接的边，即可得到图4(c)所示的4-truss子图，图中的每条边都属于2个三角形。
[0057]
对于apache ant，其处理过程如图5(a)-图5(e)所示：
[0058]
我们首先将步骤1)中生成的软件模块网络smn
ant
作为输入，根据前文提到的定义和步骤，得到如图5(a)所示的3-truss子图，而后对3-truss子图进一步分解，得到子图4-truss，并以此类推。最终，我们得到了共计五个k-truss子图(k＝3,4,5,6,7)。
[0059]
3)关键类识别输出
[0060]
获得k-truss子图后，我们需要对子图中的节点进行关键度排序。对于图中的任意节点，我们对其关键度进行如下定义：
[0061][0062]
其中，criv表示节点v的关键度值，m表示包含该节点的k-truss子图中节点数最小的子图所对应的k值，nm和n
m+1
分别表示m-truss和(m+1)-truss子图所包含的节点数量。若(m+1)-truss子图不存在，则n
m+1
取0。
[0063]
最后，我们根据上述方法计算出每个节点及其对应模块(类)的关键度值并进行排序，选取前n个模块(类)信息进行输出(n值根据需求确定)。
[0064]
可以理解，本发明是通过一些实施例进行描述的，本领域技术人员知悉的，在不脱离本发明的精神和范围的情况下，可以对这些特征和实施例进行各种改变或等效替换。另外，在本发明的教导下，可以对这些特征和实施例进行修改以适应具体的情况及材料而不会脱离本发明的精神和范围。因此，本发明不受此处所公开的具体实施例的限制，所有落入本技术的权利要求范围内的实施例都属于本发明所保护的范围内。
技术特征：1.一种基于k-truss的复杂软件关键模块识别方法，其特征在于，包括如下步骤：步骤1：对原始软件预处理并转换为格式化软件模块网络：分析原始软件中各个模块之间的依赖关系，将其转换为算法可识别的软件模块网络；步骤2：使用k-truss算法对软件模块网络进行结构分析并挖掘关键节点：将软件模块网络输入到k-truss算法中，获取关键节点的相关信息；步骤3：关键类识别输出：根据设定阈值将k-truss子图中的节点进行提取并输出。2.根据权利要求1所述的基于k-truss的复杂软件关键模块识别方法，其特征在于，所述步骤1包括如下具体步骤：将类作为关键模块识别的最小粒度，简称关键类，对原始软件进行预处理，将软件项目文件中的无关文件进行排除，仅保留后缀名为“.java”的文件用以生成软件模块网络,对软件模块网络进行定义：smn＝(n，e，t)其中，n表示网络的节点集合，包含软件中的类和抽象接口元素，e表示网络的边集合，包含各个节点之间的关系，t是一个三元组集合，表示边集合中各个边的属性及类型。3.根据权利要求2所述的基于k-truss的复杂软件关键模块识别方法，其特征在于，所述步骤1包括对各个节点之间的关系类型定义，包括继承关系、实现关系、依赖关系、关联关系；所述继承关系指一个类a继承另一个类b，在java中以extends关键字实现；所述实现关系指一个类a实现一个接口b的功能，在java中以implements关键字实现；所述依赖关系指一个类a中使用了类b，其中类b作为类a的方法参数；所述关联关系指一个类的实例a使用了另一个类的实例b。4.根据权利要求3所述的基于k-truss的复杂软件关键模块识别方法，其特征在于，所述步骤1包括一个源代码片段转化为软件模块网络的过程，每个类对应一个节点，若源代码中的两个类之间存在继承关系、实现关系、依赖关系、关联关系的一种关系，则在软件模块网络的对应节点之间增加一条边，使用上述规则进行转化，得到软件模块网络smn。5.根据权利要求4所述的基于k-truss的复杂软件关键模块识别方法，其特征在于，所述步骤2包括如下具体步骤：对于软件模块网络图smn＝(n，e，t)，图中任意一条边可表示为e
i
＝(u，v)，其中e
i
表示边，u和v分别表示这条边连接的两个节点，定义支持度support(e
i
)用来表示边e
i
在图中参与构成的三角形的个数，定义图kt是图smn的一个子图，若kt满足图中任意一条边的支持度support均满足support(e
i
)≥k-2，则称kt为一个k-truss子图。6.根据权利要求5所述的基于k-truss的复杂软件关键模块识别方法，其特征在于，所述步骤3包括如下具体步骤：获得k-truss子图后，对子图中的节点进行关键度排序，对于图中的任意节点，对其关键度进行如下定义：其中，cri
v
表示节点v的关键度值，m表示包含该节点的k-truss子图中节点数最小的子图所对应的k值，n
m
和n
m+1
分别表示m-truss和(m+1)-truss子图所包含的节点数量，若(m+
1)-truss子图不存在，则n
m+1
取0；最后，根据上述方法计算出每个节点及其对应模块的关键度值并进行排序，选取前n个模块信息进行输出，n值根据需求确定。
技术总结本发明属于软件模块识别技术领域，公开了一种基于K-Truss的复杂软件关键模块识别方法，包括：步骤1：对原始软件预处理并转换为格式化软件模块网络：分析原始软件中各个模块之间的依赖关系，将其转换为算法可识别的软件模块网络；步骤2：使用K-Truss算法对软件模块网络进行结构分析并挖掘关键节点：将软件模块网络输入到K-Truss算法中，获取关键节点的相关信息；步骤3：关键类识别输出：根据设定阈值将K-Truss子图中的节点进行提取并输出。本发明采用K-Truss算法对结构化模块网络中的模块节点进行重要性分析并探测其中的关键模块，再提供给开发者，从而提高开发者理解软件的效率，最终提高软件维护的质量。最终提高软件维护的质量。最终提高软件维护的质量。
技术研发人员：汪烨 周澳回 宋师哲 姜波
受保护的技术使用者：浙江工商大学
技术研发日：2022.03.17
技术公布日：2022/7/5
