基于条件随机场的软件变更影响分析方法*

蔡鑫奇 王 瑞* 石 亮 牟 迪 马春宇

1. 中国航天系统科学与工程研究院，北京100048 2. 首都师范大学 信息工程学院, 北京100048

变更影响分析(Change Impact Analysis，CIA)[1]指采用特定手段确定或预测引入某种软件变更对目标软件系统产生的潜在影响，它是软件演化与维护的重要内容，尤其是对增量式变更的软件维护。目前对该领域的研究主要集中于软件需求变更和软件程序实体变更2方面，经过多年的发展，已形成了不少研究成果。针对变更影响，一些专家学者相继提出了不同的分析方法[2-4]并应用于软件调试与测试分析中。针对早期的需求变更，O′Neal[5]提出一种基于跟踪性的变更影响分析方法，利用需求跟踪关系追溯影响集，确定受影响的元素；Hassine等人[6]利用用例图(UCM)来构建需求层变更集各元素与其他组件的依赖关系，从而进行影响分析；Shiri等人[7]结合用例图(UCM)和形式概念分析(FCA)对需求层进行建模，利用UCM构建需求依赖轨迹，用FCA收集这些轨迹信息，从而构造依赖关系，进行影响分析。但这些方法分析的对象限于需求分析阶段，无法适用于代码层的变更分析。而对程序设计和编码阶段的变更，则主要分为基于跟踪性分析和基于依赖性分析2类方法[4]，这些方法关注程序代码中存在的继承、方法调用和程序实体间的依赖关系，并通过计算程序实体关系建立影响传播路径，从而确定影响集。Lehnert[4,8]和孙小兵等人[9]对代码层上的变更影响分析方法做了总结，这些方法选用了不同的中间表示来计算影响集，但分析的对象限于编码阶段，且未能较好区分不同实体的受影响程度。Arvanitou[10]在他的博士论文中讨论了软件开发中不同质量度量方法在变更影响分析中的应用，但未具体提出一种变更影响的度量。

综上所述，现有变更影响分析方法多种多样，从分析阶段、类型和层次等不同角度研究了不同变更对软件构件的影响。然而大多数方法存在着一些问题： 1)分析对象受限，需求分析、设计和编码阶段分离，不能同时涵盖所有的软件构件实体；2)研究实体属性参与变更传播过程的建模精度不高，分析不全面；3)变更传播模型对传播路径和元素影响程度缺乏定量的描述与度量。

针对以上问题，提出一种基于条件随机场的分析方法，将概率模型应用于变更传播过程的分析，通过概率描述的方式衡量实体受变更影响的程度。首先引入实体的文本特性，建立词项图模型，并对实体依赖关系进行分类和形式化建模，得到状态序列分析所需的判别条件及特征向量，实现词项图的词到向量的转换，生成条件随机场的词向量和特征函数，进而计算传播序列的概率评分，定量描述影响程度。实验结果表明：提出的基于条件随机场的分析方法及设计的算法能有效地解决上述问题，提出的概率评分指标Pscore较好地刻画了软件实体及依赖链的受影响程度，为软件更新维护与测试人员提供重要的决策参考信息。

1 软件实体依赖建模

软件实体是对所有软件构件在结构和内容上的一种抽象，如软件需求文档、程序代码各粒度层次的结构(如包、类、方法和变量等)均可看作软件实体。实际开发中各种实体在发生依赖关系时，均通过以词作为名称参与功能模块的实现，因此软件实体具有显著的文本特征。

众多国内外学者对软件实体依赖关系提出了不同的分类标准，对此Lehnert[8]在他的文章中作了总结。这些方法都很好地描述了不同依赖关系的特点，但是大多数局限于软件开发过程的某一阶段，未能覆盖需求分析、设计和编码阶段全过程。因此，本文在前人对依赖关系分类的研究基础上，提出一种新的分类方案，如表1将依赖关系分为5种并进行形式化建模，采用判别函数对依赖关系进行特征向量化。

在变更传播过程中，只有转移特征向量取值为1的依赖能够对变更传播做出有效贡献。由上述5种依赖关系的定义和特征化表达可知，5种依赖中的演化依赖是不参与变更传播过程的，因此在研究变更传播过程时只考虑其余4种依赖对应的转移特征的影响，具体将在3.2节介绍，此外，这4种依赖关系从作用的软件实体层次或粒度来看，一致性依赖、使用依赖、细化依赖及结构依赖层次与粒度依次降低，对变更传播的影响程度也依次降低。

2 基于词项图的软件实体集成框架

2.1 词项图

图(Graph)是计算机科学中的一个非常重要的概念，已广泛应用于信息领域，它用图形化的语言表示一组物体之间的关系。词项图(Graph of Terms)是一种以词为基本元素的图，它描述了文本信息实体间的关系及实体属性，一般以1个三元组G=(V,E,C)(节点集V，边集E，关联函数C)表示词项图，包含节点(Node)和边(Edge)。词项图常被应用于信息检索(IR)领域，如Napoletano等人[11]利用词项图进行文本分类，王明文等人[12]利用词项图进行文本信息检索的研究。借鉴这种文本信息图结构，结合软件实体的结构特性，以词项图作为软件实体的载体，构建软件实体及其依赖关系，具有良好的可视化效果。

表1 5种依赖关系

本文基于词项图设计一种软件实体词项依赖图(Terms Graph of Entity Dependency，下文简称词项图TG)，以描述软件构件之间的依赖关系，这种依赖图是有向无环图，所以存在着多种传播路径，有关传播过程的分析将在3.2节详细介绍。

2.2 软件实体集成框架

作为整个软件变更影响分析过程的重要输入，软件实体建模(包括抽取与集成)是不可或缺的一步，本文基于词项图的基本概念提出了一种软件实体集成框架，如图1所示。假设从软件开发过程中获取到了需求文档的某项需求ri与某粒度下的程序实体ei(如面向对象语言下的class)，则分别形成实体群R={ri|i=1,…,m}和E={ei|i=1,…,n}。在软件开发全周期过程中会产生2部分主要的软件实体群：1)利用UML等辅助工具分析得到的软件需求文档；2)来自各种IDE开发的程序源码。按词项图的定义，将提取的异构软件实体映射成图数据表示，并嵌入词项图模型，存于模型库中。

建模过程主要包含2个阶段：1)对软件实体及依赖关系的提取，通常用UML表示；2)数据转换，将软件构件以特征词的形式映射成节点，并附带属性，如节点中心性，将依赖关系映射为有向边，形成词项依赖图。

图1 软件实体集成框架

本文对建模过程形成的词项图模型设计了如式(1)所示的数据结构，用于图模型库数据存储。

Template=E[+/-]DepE′

(1)

其中：E和E′分别为始实体和终实体；Dep为依赖关系，“+”表示正向依赖(E→E′)，“-”表示反向依赖(E′→E)。本文称这种数据结构为依赖元(Dependency Meta)，属于图数据，可用矩阵存储。

3 基于条件随机场的变更影响分析模型

3.1 条件随机场

条件随机场(Conditional Random Fields，CRF)是Lafferty等人[13]于2001年提出的一种判别式概率模型，该模型可将结构化输出(SO)的分布表示成一个高维输入向量(HdIV)的函数[14]，其中HdIV通常是包含节点特征或局部特征的序列，而SO的分布则是具有条件依赖的概率分布，这使得解决具有状态转移的序列问题成为可能，且CRF在许多自然语言处理任务如分词[15]、命名实体识别等[16]上具有显著的优势。

这里给出数学定义：假设有随机变量X与Y，P(Y|X)是给定X的条件下Y的条件概率分布，若随机变量Y构成一个马尔科夫随机场，则称条件概率分布P(Y|X)是条件随机场。当X和Y有相同的结构，即：X=(X1,X2,…,XN) ，Y=(Y1,Y2,…,YN)，这种情况下称作线性链条件随机场(linear-CRF)。式(2)给出了linear-CRF的参数化形式，即在给定线性随机变量序列X的条件下线性随机变量序列Y的条件概率分布，其中sk(yi,x,i)与tl(yi-1,yi,x,i)为特征函数，参数λk和μl为特征函数相应的权重系数，Z(x)为规范化因子，具有式(3)的形式。

(2)

(3)

3.2 基于条件随机场的变更传播过程分析

变更传播过程的分析是变更影响分析的关键内容。图2是由相关联的依赖元序列化构成的一条线性链，表示软件实体依赖链，长度为L(如L=4，即链上有N=5个实体节点，依次为Ei-2,Ei-1,Ei,Ei+1,Ei+2)。假定实体节点Ei-2为发生变更的起始位点(变更影响传播的起点)，记为Start；实体节点Ei+2为变更影响的终止位点(变更影响传播的终点)，记为Stop。此外，为简化描述，将未发生变更且未受变更影响的状态设为S0=0，发生变更或受到变更影响的状态为S1=1。在上述规定下，只有当传播链上所有节点的状态均为1时，变更才能从Start传播至Stop，此时链上所有实体属于影响集。

图3 基于线性链条件随机场的变更传播模型

Sutton等人[14]将条件随机场理解成结构化数据生成模型的一种判别模拟，笔者基于此，以条件随机场模拟变更传播影响过程。如图3，假设存在一个liner-CRF，用于描述变更传播过程，其传播链的实体依赖序列为X:x1,x2,…,xN，对应的传播状态序列为Y:y1,y2,…,yN，变更传播及影响的范围可用影响集EIS表达，而影响程度是变更测试人员更加关心的内容，这里以依赖链的liner-CRF条件概率作为衡量影响程度的指标，具有式(4)所示的参数化形式，其中k=1,2,…,K1，l=1,2,…,K2，i=1,2,…,N。模型构建中涉及2个特征函数及其权重的设置，具体如下：

(4)

1)状态特征函数(State Character Function，SCF)

sk(yi,x,i)是定义在实体集ES(Ei∈ES)上的特征函数，其取值只与当前实体节点的状态有关，用以刻画实体自身的属性，故称状态特征函数。这里假设模型含有K1个SCF及其对应的权重系数。

词项图中与软件实体直接相邻的实体节点个数会影响变更传播过程，具体而言：某实体的邻节点越多，则其受变更涟漪影响更大。这里用网络节点的中心性来度量实体节点的这种属性，定义为节点入度(in-degree)与出度(out-degree)之和：

CenV(Xi)=indegree(Xi)+outdegree(Xi)。

这里用节点中心性表征软件实体的状态特征，并作为模型的状态特征函数参与传播过程，经归一化处理后得到如式(5)的状态特征函数(取值在(0,1)内)。

(5)

2)转移特征函数(Transition Character Function，TCF)

tl(yi-1,yi,x,i)是定义在实体节点间(Ei-1,Ei)的特征函数，其取值与当前实体节点和前一节点之间的依赖关系有关，用以描述变更在相邻实体之间的转移特性，故称转移特征函数。这里假设模型含有K2个TCF及其权重系数。

结合上文对依赖关系的讨论，实际只有4种实体依赖关系(一致性依赖、使用依赖、结构依赖和细化依赖)参与了变更的传播，即传播模型具有式(6)所示的4个转移特征函数。

(6)

为简化模型，并与上文对依赖关系的特征化表示相一致，在模型计算时规定转移特征函数取值0或1。实际每个“实体对”在同一时间下仅存在一种依赖关系，这使得整个模型序列的每条依赖边在参与变更传播过程中仅对该依赖边的TCF做贡献，其余TCF均无效(即取值0)。

3)特征权重设计

参数λk和μl(λk,μl∈(0,1])分别表示状态特征函数sk和转移特征函数tl的权重，代表了模型对2个特征函数的信任程度。令ω(t)代表特征函数权重，该权重在[ω0,ω0+Δω](⊆[0,1])上变化，具有式(7)的形式：

(7)

其中：ω0为初始权重；Δω为梯度；t为调控因子；T为最大调控因子，一般T取模型特征函数总个数，这里取5。

对于SCF，其在一定程度上描述了实体自身对变更传播的影响程度，在权重设计时我们将λk设置成λ=1，以完全肯定节点中心性对传播过程的贡献，令ω0+Δω=1，即λ=ω(5)。由上文知模型的4个转移特征函数对应权重Wcd>Wud>Wrd>Wsd，式(7)中的ω(t)与t正相关，故将μl设置成：

μ1=ω(4),μ2=ω(3),μ3=ω(2),μ4=ω(1)

3.3 基于条件随机场的变更影响分析(CRFCIA)

3.3.1 实施规则

综上，在具体分析变更带来的影响过程中，应遵循以下实施规则：

1)依赖链受到变更影响的前提是链上实体集必须包含变更实体，否则影响集为空集，这是第一步判断；

2)当依赖链上存在演化依赖时，该依赖链参与变更传播的有效长度缩短，从依赖元始实体向前的部分为有效依赖链(Valid Dependency Chain，VDC)，若不存在演化依赖，则整条依赖链作为有效依赖链；

3)当变更传播至某依赖元时，定义依赖方向为正，则有以下判断：若依赖元为结构依赖，则变更可双向传播，即始、终实体有一者受变更影响，另一个必受影响(本文暂不考虑变更类型的影响)，若依赖元为一致性依赖或细化依赖，则变更正向传播，若依赖元为使用依赖，则变更反向传播；

4)有效依赖链上，若依赖元的变更传播方向与变更实体所在依赖元相同，则该依赖元的始、终实体属于影响集，否则其终实体不属于影响集，且其始实体作为此传播链的终止位点。从变更实体开始至终止位点之间的同向传播依赖元构成变更传播链，传播链上的所有实体均是影响集中的元素；

5)实体状态特征函数由实体的节点中心性度量，只与实体在词项图中的分支状态有关；

6)依赖元的转移特征函数由依赖元始、终实体共同决定，只与依赖关系类型有关，且除演化依赖外其他依赖关系均影响变更的传播过程；

7)每条传播链均有一个基于CRF的条件概率评分，用来描述变更传播影响程度，该评分越大，说明影响程度越大，则该依赖链上的实体需要被测试的可能性更大。

3.3.2 基于CRF的变更影响分析算法

通过图1的集成框架得到了TG-Models库，库中的依赖元可通过依赖关系的传递连接成依赖链，而所有依赖链的集合便构成实体词项图。在进行影响分析之前，先将词项图转换成依赖链的集合，也即存在依赖关系的实体构成的线性链，如图3中的实体序列。基于上述变更传播过程的讨论和前一小节的分析规则，本文设计了基于CRF的变更影响分析算法，如算法1，其中函数CRFScore(X, Y)的功能是计算传播链条件概率，用于衡量变更传播的影响程度。

算法1 基于CRF的软件变更影响分析算法(CRFCIA)Input ce, TGMStore //变更实体ce和实体词项图TGMStoreOutput EIS, Pscore //预估影响集EIS和变更影响程度Pscore Set Pscore = set of score based on CRF //基于CRF的概率评分Set dces = set of entity in dependency-chain //依赖链实体集Set pces = set of entity in propagation-chain //传播链实体集Set X = a dependency sequence of entities //实体依赖序列Set Y = a state sequence of propagation //传播状态序列与X同构01. dces = graph2chain(TGMStore); //取依赖链实体集02. EIS = initially empty-set; //初始化EIS为空集03. Pscore = initially empty-set; //初始化Pscore04. Set Y = a sequence of 1; //传播状态全为1,即全链受影响05. for (each dces) { //对依赖链遍历06. if (dces contains ce) { //依赖链实体集包含变更实体07. for (each dep-meta of dces) { //对依赖元遍历08. if (dep-meta.dep is ed) { //当依赖元为演化依赖09. dces=dces(entities before dep-meta.ine);}//取有效依赖链10. else dces = dces; } //不存在演化依赖时dces为有效依赖链11. if (dep-meta.dire == ce’s) { //传播方向与变更依赖元相同12. pces.add(dep-meta); //则该依赖元属于传播链,加入pces13. else end for; } //否则该依赖元为Stop14. EIS = merge(EIS, pces); } //将传播链实体集并入EIS15. X = index(pces); //取传播链对应实体的坐标16. Pscore[] = CRFScore(X, Y); } //调用CRFScore()计算评分17. else EIS = empty-set, Pscore = null; //变更无影响18. end } return EIS, Pscore; //返回EIS和Pscore函数CRFScore(DepSequence X, PropagationState Y): Input X, Y //实体依赖序列X,传播状态序列YOutput Pscore //变更影响程度 Set scf = state character function //状态特征函数Set tcf = transition character function //转移特征函数Set parameter(ω0, delω, T)01. Pscore = initially empty-set; //初始化Pscore02. for (each x of X) {03. Cen(x) = indegree(x)+outdegree(x); //实体节点中心度04. scf(x) = normalize(Cen(x)); //归一化得到状态特征函数05. tcf(x) = t(x); end } //由依赖关系确定转移特征函数06. for (t=1:T)07. W[] =ω0 + delω ∗ (t/T)^2; //得特征函数权重08. F = sum(W[0:T-2]∗scf(x), x) + sum(W[T-1]∗tcf(x), x);09. Z(X) = sum(exp(F), y); //规范化因子10. Pscore = exp(F) / Z(X); 11. return Pscore; //返回Pscore

4 实验

4.1 原型系统

如图4所示是本文设计的一个原型系统，用于检验所提出的方法与算法的可行性及在实际分析中的准确性。该系统的结构与功能组成如下：

图4 原型系统组成

1)软件实体集成模块：该模块根据本文第2节的软件实体集成框架，对软件构件(需求设计文档、源代码等)进行预处理，抽取实体及依赖关系，构建实体词项依赖图库；

2)变更影响分析模块：此模块是系统的核心，利用前一模块生成的依赖图和给定的变更集，经过CRFCIA算法计算影响集EIS和变更影响程度的指标分数Pscore，得到结果数据报文；

3)输出可视化模块：该模块将分析生成的报文转为用户容易理解的图表等数据。

4.2 实例研究

为了更好地说明本文方法及原型系统的正确性与可操作性，这里选取某软件项目作为实例研究的对象展开实验。该软件由C++语言实现，假设不考虑成员变量的变更影响，共覆盖需求分析、设计与编码阶段的14个软件构件，经简化处理后的UML结构如图5所示。在Doxygen工具的辅助下，通过原型系统的TGMF模块得到所有依赖元信息并按图6所示的list数据结构存储于词项图模型库TGMStore，对应的实体词项依赖图见图7。

图5 需求分析、设计与编码阶段的软件构件UML结构图

图6 依赖元list数据

图7 实体词项依赖图

实验中设置变更集，取其中的变更实体R1，执行CRFCIA算法，将依赖元和变更实体作为输入，参数配置：取ω0=0.5，Δω=0.5，T=5，得到如表2所示的测试结果。实际依赖链长度及链上实体不同，其对应的受影响程度也不同，从实验结果能看出Pscore很好地刻画了这种差异，即Pscore越大，对应依赖链实体受影响程度越大。根据实验计算得到的Pscore和EIS，得到以下结论：

1)当变更实体为R1时的影响集为各序列影响集的并集，所以R1的EIS为{R2,E1,E2,E3,E4,E5,E6,E7,E8,E9}；

2)依赖链越长，链上实体受变更影响程度越大，变更涟漪效应越明显；

3)实际软件变更测试时优先测试Pscore较大的依赖链，重点测试节点中心度高的实体模块。

表2 实验测试结果(当变更点为R1)

5 结论

软件变更影响分析是软件变更维护工作的重要内容，其主要目标为：1)自动反馈变更集对应的影响集，初步定位受影响位点；2)计算软件开发中实体依赖链的受影响程度，为变更维护测试人员提供直观的评价信息以快速做出决策。围绕这2点，本文基于条件随机场理论提出1种新的变更影响分析方法，从实体依赖关系出发构建词项依赖图，并将这种依赖图映射成线性条件随机场，利用概率模型描述影响程度，并用概率评分Pscore进行定量刻画。实验表明CRFCIA方法在变更影响分析上是可行且准确的。

利用条件随机场等概率模型的思想来解决软件依赖提取、变更影响分析等软件变更维护问题，是一个值得研究且有应用价值的方向，尤其在敏捷开发模式下，为软件开发与测试的高效化、精准化提供了一种值得借鉴的技术途径。未来将针对CRFCIA算法的应用及智能化改进展开进一步的研究。