特征约束之软件设计论文

1源代码信息抽取

设计模式识别是对程序源代码信息进行分析，抽取出其中所运用的设计模式，是软件逆向工程的一部分。因此，设计模式识别的对象一般为面向对象程序系统的源代码信息。本文以Java源代码为设计模式识别目标，结合Java语言的特点进行源代码信息的抽取。

1．1源代码信息抽取

根据DPDLXS语言的定义规则，将设计模式的特征信息描述为类角色Roles、类之间关系Relations和自定义类型TypeRep3个部分。源代码信息的抽取也遵循DPDLXS语言的定义规则，解析为类角色Roles和类之间关系Relations。其中，一个类角色Roles又分为类属性Attribute和类操作Operation子元素以及各自的属性。根据Java语言的特点和设计模式描述语言DPDLXS的定义规则，给出了源代码信息抽取流程，如图1所示。

1．2类无向图和连通分量

对源代码进行设计模式的识别往往都是以一个工程或一个面向对象程序系统为一个整体进行分析，其中包含了数量庞大的类文件。然而，一个设计模式所参与的类角色只有3－5个左右，为了匹配一个设计模式的特征而去遍历整个工程的类文件显然是不可取的。根据设计模式的结构特征，构成一个设计模式的每个角色类至少与其他角色类存在一种关系，包括一般化关系（Generation）、关联关系（Association）、聚合关系（Aggrega－tion）、合成关系（Composition）和依赖关系（Dependency）。从图论的角度上来说，如果把每一个类角色看成是一个顶点（Vertex），类角色之间的任何一种关系看成是两个顶点之间的一条边（Edge），整个设计模式类图就可以看成是一个无向图，而且是一个任意两个顶点都连通的连通图（ConnectedGraph）［11］。同理，待识别的整个工程的源代码类图就可以看成是一个庞大的无向图，如图2所示；无向图中的每一个极大连通子图都是一个连通分量（ConnectedComponent）［11］，如图3所示。因此，匹配的某一设计模式特征的待识别类候选集合一定是该工程无向图中一个顶点数目大于等于设计模式角色类数目的连通分量。2．3关联度通过引用图论中无向图和连通分量的概念，将设计模式的识别从源代码中匹配特定设计模式特征转化成在无向图中查找满足顶点数目的连通分量。通过过滤不满足该设计模式角色类数目的连通分量可以减小候选集合，从而减小搜索空间，提高识别效率。然而，在信息抽取的初级阶段并不知道待识别工程源代码无向图的连通分量。为了方便遍历无向图从而得到该无向图的连通分量，本文将待识别源代码的无向图表示成一种链式存储结构———邻接表［11］。本文根据从源代码信息中抽取出的类之间关系信息来构建无向图，得到无向图的顶点集合V和代表类之间关系的边集合VR。将集合V中的每一个顶点都表示成一个头结点，如图4（a）所示；根据集合VR中顶点之间的关系构建该头结点包含的表结点，如图4（b）所示，从而得到图2中无向图对应的邻接表，如图5所示。运用邻接表这种链式存储结构，从第一个头结点开始遍历可以得到无向图的所有连通分量。无向图连通分量的具体深度遍历算法如下：Step1遍历头结点，设置该头结点的visited为true；若该头结点的链域为空而且是第一个头结点，则结束；若不是第一个头结点则返回上一层表结点，跳到Step4；若链域不为空则继续下一步。Step2遍历链域所指向的表结点，根据表结点的邻接点域找到下一个头结点。Step3若该头结点的visited为true，则返回上一层表结点，跳到Step4；否则跳到Step1。Step4遍历表结点的链域，若链域不为空则跳到Step2；若链域为空，则返回上一层表结点并判断是否存在上一层，若存在则跳到Step4；否则结束。该算法一次遍历结束后，所有遍历到的顶点集合就是一个连通分量。然后寻找下一个visited为false的头结点作为第一个结点继续遍历，直到遍历完所有头结点。利用该算法对图5所示邻接表进行遍历可以得到两个连通分量，其顶点集合分别为：S1｛A，C，B，E｝和S2｛D｝。每一次遍历都可以得到一个连通分量，每个连通分量都是待识别源代码类图中至少与其他类存在一个关系的所有类集合。该集合中的类彼此之间存在着可能构成某种设计模式的类关系。因此，本文提出用关联度（Correlation）的概念来衡量和唯一标识待识别源代码之间的这种联系。每一个关联度值标识了一个连通分量，连通分量中的各个类拥有相同的关联度值，其集合称为关联类集合。

2设计模式识别

在完成源代码信息抽取（包括类信息、类的属性和操作，特别是根据类之间的关系构建了关联类集合）之后，需要根据具体设计模式特征来检测和识别源代码中运用的设计模式。

2．1设计模式识别流程

为了减小设计模式识别的搜索空间，本文在源代码信息抽取阶段将待识别源代码类组合成一个个关联类集合。根据设计模式角色类之间的关系特征可以得出：只有同一个关联类集合中存在该设计模式的所有角色类，并且关联类之间符合对应角色类之间的所有关系特征，才能判定关联类集合运用该设计模式。因此，首先可以根据设计模式角色类数目过滤类数目不足的关联类集合；其次可以根据设计模式所蕴含的角色类之间的关系特征过滤不满足类之间关系类型和关系数目的集合；最后根据设计模式的具体特征约束遍历满足条件的候选关联类集合，得出最终的识别结果。具体的识别流程如图6所示。

2．2基于关联度和特征约束的设计模式识别算法

根据本文提出的源代码类角色信息间关联度的概念以及设计模式识别的流程，充分利用关联类集合和设计模式特征约束来减小设计模式识别的搜索空间，可以得出基于关联度和特征约束的设计模式识别算法DETECT＿DESIGNPA＝TTERNS，具体描述如算法1所示。

3结果和分析

根据所提出的源代码信息抽取流程以及基于关联度和特征约束的设计模式识别算法，本文对Junit、JHotDraw和Jrefactory3个开源应用程序进行信息抽取和部分设计模式的识别。

3．1工厂方法模式

基于提出的源代码信息抽取流程（见图1），本文从源代码文件数目、类、属性、方法和类之间的关系数目以及源代码行数等方面对3个开源应用程序源代码进行信息抽取。其抽取结果如表1所列。从表1的抽取结果可以看出，这3个开源应用程序在文件数目以及代码复杂性等方面各不相同。类之间存在的关系越多，体现了源代码结构复杂度越高，同时也意味着可能运用了更多的设计模式。

3．2设计模式识别结果

针对表1的源代码信息抽取结果，我们利用基于关联度和特征约束的设计模式识别算法，结合待识别设计模式的具体特征约束，依据本文的设计模式识别流程得出Junit、JHot－Draw和JreFactory的部分设计模式识别结果，如表2所列。通过对部分设计模式识别结果分析得出，该设计模式识别方法还存在一定的不足：（1）对设计模式识别的准确率有待提高。待识别源代码类结构和设计模式之间的特征匹配如果不够充分就会增加识别结果的错误肯定率；反之，则会增加识别结果的错误否定率。（2）对设计模式异构体或变体的识别考虑不足。每一个设计模式虽然都有一个标准和公认的结构特征，但往往有多种不同的特征表现形式，例如观察者（Ob－server）模式。这种不同的表现形式可以称为异构体或变体，这对设计模式的识别提出了更高的要求。因此，今后需要对设计模式异构体之间的特征做更细致的分析，从而得到更准确高效的设计模式识别方法。结束语本文利用DPDLXS语言描述设计模式信息和待抽取的源代码信息，提出源代码间关联度的概念，构建基于关联度的关联类集合，旨在减小设计模式的搜索空间，一定程度上提高识别效率；根据设计模式的特征约束和构建的关联类集合，提出基于关联度和特征约束的设计模式识别算法；最后，将该设计模式识别算法应用于Junit、JHotDraw和JreFactory3个开源应用程序的设计模式识别，结果表明该设计模式识别算法具有较高的召回率和效率。

作者：古辉 张炜星 金鹏 顾杰杰 单位：浙江工业大学计算机科学与技术学院