基于变量依赖关系模型的变量重要性度量方法
2020-08-03田兴亚牟永敏张志华
田兴亚， 牟永敏， 张志华
(北京信息科技大学网络文化与数字传播北京市重点实验室，北京 100101)
软件系统的运行实质上是程序变量按照程序员指定的逻辑相互影响来执行的。Concas等[1]研究了十余款大型软件系统，发现了软件系统中的变量分布符合幂律分布，具有非常明显的复杂网络特征。为了提高软件系统的安全性，就应该找出那些重要变量，因为一旦这些变量出现问题就会给软件系统带来巨大的损失，如何识别出重要变量是一个非常有价值的研究课题。
在软件开发过程中，软件系统面临各种各样需要变更的情况，包括增加模块、修改模块和删除模块。这些操作通常会涉及对变量的变更，由于变量间存在依赖关系, 使得变量的变更引起其他相关联的变量发生变更，最终引起软件故障。因此挖掘出变量的重要性，降低变量变更的代价，对软件测试和维护具有重要的意义。
在软件系统中, 变量的重要性有所不同。当某个变量发生变更时, 其对于整个程序的影响程度也不同, 尤其是重要的变量发生变化可能会对整个程序产生影响。在软件结构中，衡量一个变量是否重要，最重要的是衡量变量与其他变量的交互程度。在程序中使用的变量都直接或间接地相互影响，因此分析变量间的依赖关系对变量的重要性度量具有重要的作用。
目前，由于中外学者的关注点不同，所以针对不同场景提出了各种依赖关系，主要包括实体依赖关系、类依赖关系、函数依赖关系、语句依赖关系和变量依赖关系等。
Stevens等[2]首先提出用依赖关系来衡量一个构件对另一个构件的依赖程度。依赖程度越高，构件的耦合性越高。为了便于理解各种依赖关系, 研究者们提出许多依赖图的模型来描述各种依赖关系。
黄雅菁等[3]利用软件系统中类和类之间的依赖关系，提出一种基于赋权类依赖图的重构定位方法，定位需要重构的类。成小芹等[4-5]将中介中心性和类依赖关系图相结合度量类重要性，有效地指导了测试资源的分配。
符炜等[6]讨论了函数依赖关系，并结合程序切片技术，基于函数依赖图进行构件抽取。程晓菊等[7]将函数依赖图精简为函数切片依赖图得到与代码变化相关的函数最小集，极大地约简了测试用例集，提高了回归测试的效率。
吴军华等[8-9]提出基于程序依赖图进行程序代码的克隆检测，又采用依赖边类型约束计算近似解，有效地提高了计算性能。
Harman等[10]阐述了变量依赖分析问题与切片之间的关系，并实现了变量依赖关系分析的VADA系统。DaimlerChrysler公司目前正在利用它作为测试用例自动生成方法的一部分。论文引入的方法为变量依赖关系分析增加了一个新的维度，即增加了对重要变量的自动跟踪。
Sadi等[11]提出了一种基于自动生成的依赖图分析变量依赖关系的方法，依赖图描述了程序变量之间的关联关系，其中变量作为图的顶点，变量之间的依赖关系作为图的边。通过自动生成的依赖关系图可以跟踪关键变量，关键变量作为检测程序顺序执行的关键，优于现有的程序分析方法。但是该方法只分析了变量间的数据依赖关系，未考虑变量间控制依赖关系以及函数调用引起的变量依赖关系。
潘亚飞等[12]通过分析变量间的依赖关系，生成变量数据拓扑图。为由变量带来的软件变更问题提供了新的解决方法。
傅妤婧等[13]针对时态实体依赖图提出时态实体依赖关系，并分析时态实体依赖图的节点中心性、节点重要性、节点依赖度和边的重要性等4个度量指标。
节点的重要性度量方法有度中心性[14]、介数中心性、接近中心性[15]、特征向量中心性[16]等。
现有的依赖分析方法大多针对类、函数和语句的粒度来建模，文献[12]虽然分析了变量间的依赖关系，为分析由变量引起的软件变更提供了新思路。但是却未深入分析哪些变量是能对程序产生更深度影响的变量，不能轻易发生变更。论文结合以上研究成果, 提出变量依赖关系模型的定义，并提出基于变量依赖关系模型的变量重要性度量(variable node importance measure，VNIM)方法，通过实验分析，证明了该方法在变量重要性度量方面的优越性。
1 相关定义
定义1变量依赖关系模型(variable dependency model,VDM)：VDM=(V,E)，其中V是VDM模型中所有的变量集合，V={vi|vi∈程序变量}。E是VDM模型中变量之间依赖关系的边集合，E={eij=(vi,vj)|vi,vj∈V} 。其中，eij的定义为
(1)
定义2依赖关系：由控制条件引起的控制依赖和由访问变量引起的数据依赖以及由函数调用引起的函数依赖。
定义3数据依赖(data dependency)：设s为程序P的赋值语句，令vi为在s中被赋值的变量，Ref(s)为在s中被使用的变量集合，若存在变量vj∈Ref(s)，则称变量vi数据依赖于变量vj，记为dd(vi,vj)。数据依赖描述了在赋值语句中左部对右部的依赖关系。
定义4控制依赖(control dependency)：设s1和s2分别为程序P的赋值语句和控制语句，令vi为在s1中被赋值的变量，vj为在s2中控制条件的变量，若s1能否被执行由s2的执行状态决定。则称变量vi控制依赖于变量vj，记为cd(vi,vj)。
定义5函数依赖(function dependency)：变量v的取值依赖于函数F返回值，则称变量v函数依赖于F，记为fd(v,F)。
定义6隐含依赖关系(implicit dependency)：隐含依赖关系是指针变量参与赋值运算(地址赋值运算“&”、指针解引用的赋值运算“*”)引起的变量依赖关系，若变量vi隐含依赖于变量vj，则隐含依赖关系可以表示为id(vi,vj)。指针变量是存储地址类型数据的变量，对于指向同一块内存地址的指针变量而言，通过任意指针改变该内存的数值时，指向该内存的所有指针变量的取值都将被改变，因而它们属于相互依赖的隐含依赖关系。
定义7变量重要性的评判标准：变量是否重要取决于应用场景和用户给定的标准，现针对由变量引起的软件变更场景提出变量重要性的评判标准。
标准1一个变量是重要的当且仅当有很多重要的变量依赖于它。
标准2一个变量是重要的当且仅当它接近变量依赖关系模型的中心。
标准1递归地定义一个变量是否重要取决于 2个要素：①依赖于该变量的变量数量越多，变量越重要；②依赖于该变量的变量重要性越高，变量越重要。根据标准1的定义可知，如果一个变量被很多其他变量依赖，那么对这个变量的修改可能会影响许多依赖于它的变量;如果一个变量被重要的变量依赖，那么对这个变量的修改可能会影响到重要变量从而对软件产生较大的影响。
标准2定义变量的重要性取决于变量的中心性，中心性越高的变量被删除后对变量依赖关系模型的破坏程度就越大，也就说明这些变量越重要。
对于不同类型的代码语句定义了不同的变量依赖关系如表1所示。
表1 不同类型语句的变量依赖关系
2 变量依赖关系模型的构建
2.1 变量依赖关系分析
2.1.1 数据依赖关系分析
变量的数据依赖体现在代码中的赋值语句上，在赋值语句的算术表达式中，等号左侧的变量数据依赖于等号右侧的变量，该语句作用是赋值等操作。如式(2)所示两行赋值语句：
(2)
假设所有的变量有意义，变量c的取值取决于表达式等号的右侧变量a和b。变量a和b的任何变化都会引起变量c的变化，这是变量c对变量a和b的直接依赖。变量e的取值同时受到变量c和d的影响，因此变量a和b通过直接影响变量c，从而间接影响变量e。
2.1.2 控制依赖关系分析
在程序代码中，控制节点体现了程序的逻辑结构，反映了程序执行的走向，包含了变量的控制流和数据流信息。因此，分析控制依赖关系对收集程序的关键信息具有重要作用。图1所示的C程序代码中6～10行为含有控制依赖关系的代码段，变量h的取值控制依赖于变量con。当满足控制语句的判别条件时，函数f的返回值影响变量h，不满足条件时，变量e影响变量h。
图1 C程序片段示例Fig.1 C program fragment example
2.1.3 函数依赖关系分析
函数依赖是一种特殊的数据依赖，由于源代码中的功能块用函数进行封装，所以需要做函数层面的变量依赖关系分析，即需要函数返回值的依赖影响关系。例如intq=f1(5)，f1函数定义如图2所示。
图2 f1函数Fig.2 f1 function
变量q的取值依赖于函数f1的返回值，即q函数依赖于f1中的变量b。在f1函数中，变量b数据依赖于变量c，同时控制依赖于变量a。变量q的函数依赖关系如图3所示。
图3 变量q的函数依赖关系Fig.3 Function dependency of variable q
2.1.4 隐含依赖关系分析
如图4所示，第 4行定义一个整型指针b,并且b指向了a的地址。第5行定义一个整型的指针c并且c指向了b的地址。假设a、b、c的内存地址分别为0x100、0x200、0x300，则三者之间的访问形式如图5所示。
图4 含指针的C程序Fig.4 C program with pointer
图5 指针变量的访问形式Fig.5 Access form of pointer variable
指针b可以通过访问变量a的地址访问到变量a的值，属于直接访问的形式。指针c可以通过b再访问a的地址访问到变量a的值，属于间接访问的形式。假如重新对变量a进行赋值，令a=10，则b和c访问的值也会变为10。因此，指针变量b和c依赖于变量a。令*b=20，通过解引用，可以重新给a赋值为20，同理**c也可以重新给a赋值为20。因此，变量a也依赖于指针变量b和c。由此，可以认为对于指向同一块内存地址的变量而言，它们属于相互依赖关系。
算法1描述了变量间依赖关系的提取算法，此算法的主要目标是查找变量并提取变量间的依赖关系。抽象语法树中含有程序的所有的信息，抽象语法树可以理解为源代码的树形结构，树中的每个节点信息都和源代码的信息一一对应。需要对抽象语法树中的节点进行遍历和解析，提取变量、函数、赋值信息和控制信息等关键信息。根据节点中关键字的不同，定义不同的依赖关系。并将相应的变量和依赖关系类型标签加到结果集中。算法1如下：
算法1 变量间依赖关系的提取算法输入:预处理后的源程序输出:变量依赖关系集合定义:令mark为变量依赖关系类型标签Step1:利用抽象语法树生成工具得到源代码树形结构的数据,源代码的信息和树中的节点信息一一对应。Step2:基于抽象语法树,从 node 的根节点开始遍历,提取变量、函数、赋值信息和控制信息等关键信息。Step3:遍历关键节点,若存在赋值关键字“assign”,则令mark=“dd”;若存在循环控制关键字“for”、“while”或“if”分支控制字,则令mark=“cd”;若存在函数调用关键字“call”,则令mark=“fd”; 若存在指针类型的关键字如“array” 或“pointer”,则令mark=“id”Step4:将变量和相应的依赖关系标签加入到结果集中。Step5:循环上述过程,直到整个对象全部遍历完成。
在图1的示例代码中，变量c数据依赖于a和b，变量e数据依赖于c和d。变量h控制依赖于变量con、函数依赖于f和数据依赖于变量e。对程序变量的依赖关系分析过程如表2所示。
表2 程序变量的依赖关系分析
2.2 变量依赖关系模型构建的方法实现
提取变量间的依赖关系之后，如前文所述，利用变量间的依赖关系生成变量依赖关系模型。变量依赖关系模型的顶点是代码段的变量,边由依赖变量指向被依赖变量。
算法2描述了变量依赖关系模型构建的实现过程。以变量依赖关系集合作为输入，遍历变量依赖关系集合，得到集合中每个变量及其依赖关系；提取变量并绘制变量节点，如果变量i与变量j之间存在依赖关系，提变量依赖关系类型标签，绘制一条从变量i到变量j的边，并把标签的取值赋值给边；循环上述过程直至遍历完成，最终得到变量依赖关系模型。算法2如下：
算法2 变量依赖关系模型构建算法输入:变量依赖关系集合r_array
将算法2应用于图1的示例程序，最终得到变量依赖关系模型。图6绘制了程序从第1～10行变量依赖关系模型的逐步构建过程。
图6 变量依赖关系模型自动生成过程Fig.6 Variable dependency model automatic generation process
变量依赖关系模型是程序中变量信息传播的直接映射，反映了程序中变量的相关依赖信息如控制依赖信息和函数依赖信息等。
变量依赖关系模型的功能如下。
(1)自动跟踪程序中的变量和方法，明确变量和函数调用在整个程序中的分布情况。
(2)跟踪变量在整个程序中的使用情况及其依赖关系，依赖关系包含了变量的数据依赖关系、控制依赖关系、函数依赖关系和指针引起的隐含依赖关系。
(3)可以直观地展示各变量间依赖关系类型及其传播方向。
(4)通过变量依赖关系模型并结合变量的出度和入度可以分析变量在程序中的重要性。
(5)当出现变量问题引起的软件错误时，通过变量依赖关系模型可以快速定位到最可能出错的根源变量，可以有效地指导软件测试活动。
3 基于VDM的变量重要性度量方法
3.1 相关概念
3.1.1 节点中心性
在网络图中，节点中心性(node centrality)可以表示节点在图中与其他节点相关联的程度。中心性越高，与其他节点的关联程度就越高，该节点能够影响到的其他节点就越多。
节点中心性定义如下：
(3)
式(3)中：in(pi)代表在网络图中节点pi的入度；out(pi)表示节点pi的出度；N表示节点总数。
在网络图中，假设节点pi的度为deg(pi)，则节点pi的中心性也可以表示为
(4)
中心性只考虑了节点在网络中的位置，并没有考虑依赖于该节点的节点重要性贡献，也并未考虑节点本身的重要性信息，考虑较为片面。
3.1.2 节点重要性
傅妤婧[13]提出的节点重要性(node importance)与中心性相比，更多地关注了节点的入度。即节点的入度数越大，依赖于该节点的其他节点个数越多，当该节点发生改变时，会有更多的节点直接受到其影响。
定义节点的重要性为直接依赖于该节点的所有节点中心性之和。则节点pi的重要性为
(5)
式(5)中：C(pj)表示依赖于节点pi的节点pj的中心性。
式(5)的节点重要性计算方法除了考虑节点链入数量的因素，还结合了邻接节点的中心性影响因素。但该方法有一个很大的缺陷，假如一个节点没有任何链入，则该节点的重要性为0，这显然是不合理的。该方法一定程度上刻画了节点的重要性，但同时也忽略了很多因素，仅仅考虑邻接节点的数量和中心性情况，以此来衡量节点的重要性，有很大的局限性。
3.1.3 PageRank方法
PageRank方法是Google著名的网页重要性排名算法，该算法是特征向量中心性的一个变种。PageRank值越大表示网页重要性越高。
假设存在节点pi，则其PageRank值计算方式如下：
(6)
式(6)中：M(pi)代表链入节点pi的节点集合；Lo(pj)表示节点pj的链出数；N代表所有的节点总数；α是阻尼系数，针对网页排序其取值一般为0.85。
PageRank方法认为节点是否重要取决于两点：依赖于该节点的数目和这些邻接节点的重要性。但是却忽略了节点的中心性因素，根据节点在网络中所属的位置不同，其对信息传播的作用也是不相同的。
基于上述思想，并结合定义6提出的变量的重要性评判标准，引入了“枢纽性”来衡量变量在变量间信息传播的作用即中心性影响，并结合邻接变量的重要性贡献提出了一种新的基于变量依赖关系模型的变量重要性度量(variable node importance measure,VNIM)方法。
3.2 VNIM方法
重要变量指的是能对程序产生更深度影响的变量，其影响包括对程序信息的传播以及对全局变量的链接作用。PageRank 方法只考虑了邻接节点的重要性贡献，却未考虑节点本身的枢纽性，考虑较为片面。枢纽性是指节点所在位置，反映了节点的中心性影响。针对PageRank存在的局限性问题，提出VNIM方法，方法不仅考虑了邻接节点的重要性贡献，还结合了节点的枢纽性作用。
假设存在变量vi,则其VNIM的计算方式为
(7)
式(7)中：DP(vi)表示依赖于vi的变量集合；IC(vj)表示变量vj对变量vi的重要性贡献度；VNIM0(vi)表示变量vi的初始重要性；H(vi)表示变量vi的枢纽度(hub Degree)。
(8)
式(8)中：N代表所有的变量总数。
重要性贡献度(importance contribution)： 若存在一条变量依赖关系vj→vi，变量vj对变量vi的重要性贡献度为变量vj自身的重要性与其出度的比值，即:
IC(vj)=VNIM(vj)/o(vj)
(9)
式(9)中：o(vj)表示变量vj的出度。
枢纽度H(vi)的定义如下：
H(vi)=C(vi)
(10)
C(vi)的定义曾在式(5)提到，表示变量的中心性。变量的枢纽度等于其中心性，反映了变量在变量间信息传播的作用。
为了消除程序规模对变量重要性的影响，需要对变量的重要度做归一化处理如下：
(11)
变量的VNIM是由所有依赖于该变量的其他变量重要性经过递归算法得到的。除了考虑链入变量的数量及邻接变量的重要性贡献因素，还结合了变量的枢纽性影响，综合两者因素可以获得更好的度量结果。
如果一个变量被很多变量依赖，或被少数几个重要的变量依赖，则变量的重要性较高。因此，有较少链入数的变量可能比有较多链入数的变量重要性更高。同时根据变量枢纽性作用的不同，变量的重要性也不相同。
VNIM方法具有如下性质。
(1)传递性：由于VNIM的计算考虑了邻接变量的重要性贡献因素，因而VNIM方法具有传递性。
假设变量b、c和d依赖于变量a，那么变量a的VNIM与其枢纽度的比值为变量b、c和d对变量a的重要性贡献度与变量a初始重要性之和。
则变量a的VNIM与其枢纽度的比值为
(12)
(2)传递的均匀性：变量的VNIM值均匀地向后传递。
假设变量a和c依赖于变量b，变量a，e和f三个变量依赖变量d。变量a、b、c、d、e和f之间的依赖关系如图7所示。
图7 变量依赖关系示例图Fig.7 Sample diagram of variable dependencies
则变量a、e和f对变量d的重要性贡献度分别为
(13)
邻接变量对变量的重要性贡献度与邻接变量的出度成正比，变量a既依赖于变量b又依赖于变量d，因而变量a对变量d的重要性贡献度为变量a自身的重要性的1/2。
4 实验分析
通过一个VDM示例图将VNIM方法与傅妤婧[13]提出的节点重要性度量方法和PageRank方法进行对比，展示VNIM方法在变量重要性度量方面的准确性。用例图如图8所示。
图8 VDM示例图Fig.8 VDM example diagram
利用本文描述的方法，可以计算出VDM示例图中各个变量的中心性值、NI值、PageRank(PR)值和VNIM值，计算结果如表3所示。
表3 各种指标计算结果
通过计算结果的呈现，可以发现这几种方法对变量重要性的排名结果有所不同。
通过表3可以发现，通过傅妤婧[13]提出的节点重要性度量方法计算得出变量a、g和h的重要性为0，这显然不合理，因为变量a、g和h虽然不被任何其他变量所依赖，但是它们在变量的信息传播中起到了重要的作用。同时，计算结果中出现了很多变量重要性相同的现象，如变量b、c、f和j的重要性完全相同，这是由于NI值的计算方法只关注了其邻接变量的中心性指标，未考虑变量间信息的传播，也未考虑变量本身的重要性信息等，考虑较为片面。而在变量依赖关系模型中，可能会出现大量变量的中心性一致的情况，在程序规模足够大的情况下，可能会导致变量的重要性难以有效区分。
表4为各个变量重要性的排名结果，括号内的数字表示排名的并列情况。由于变量i几乎被所有变量直接或间接地依赖，因而能对程序产生更深度的影响。所以在PageRank方法中，变量i排名第一。傅妤婧[13]提出的节点重要性度量方法只考虑了邻接变量的中心性因素，同样得出变量i最为重要。 而VNIM方法结合邻接变量的重要性贡献以及变量在信息传播的作用，也把变量i排在了第一位。
表4 变量重要性排名结果
虽然三种方法都把变量i排在了第一位，但是其考虑的因素却大大不同，尤其是傅妤婧[13]提出的节点重要性度量方法在变量重要性度量方面有明显缺陷。对比VNIM方法和PageRank方法，排名结果中出现较大差异的为变量a、g和h的重要性排名结果，在PageRank方法中三者重要性相同，而在VNIM方法中的排名为a>g>h。仔细观察图6可以发现，变量a、g和h的入度都为0，出度分别为3、2和1。入度为0表明即没有任何变量依赖于这些变量，由于PageRank重点关注的是邻接变量的重要性贡献和数量，并没有考虑变量的枢纽性影响因素，所以得出三个变量的重要性相等的结论。而VNIM方法既考虑了邻接变量的数量以及重要性贡献，又综合了变量的枢纽性影响因素，因而与前者的排名结果不同。
显然，变量a、g和h的重要性是不同的，虽然不被任何变量依赖，但是变量起到了信息传播的作用，根据变量的中心性不同，其传播作用的大小也不相同。变量a的度更大，起到的枢纽性作用更大，能对程序产生更深度的影响，因而变量a相比变量g和h的重要性要更大一些。同理，变量e的重要性大于变量j，变量a的重要性大于变量b、c和f。
从表4可以看出，PageRank方法和NI方法的排名结果出现了很多变量重要性一致的情况，尤其是NI方法的排名结果最为明显，变量b、c、f和j重要性完全一致。VNIM方法结合了邻接变量的重要性贡献和变量的枢纽性作用，综合衡量变量在程序中的重要性，弥补了其他两个方法的不足，其重要性排序结果更为准确合理。
上述的分析结果说明VNIM方法对比傅妤婧[13]提出的节点重要性度量方法和PageRank方法在评价变量重要性度量方面更加准确有效，变量重要性排序结果更具有实际意义。
在变量依赖关系模型中，衡量变量是否对程序产生了更深度的影响，不仅要考虑依赖于该变量的数量和重要性贡献，还要结合变量在信息传播中的作用。VNIM方法充分利用了变量间的依赖信息，对变量的重要性度量结果更加准确。
5 结论
变量重要性度量是软件测试领域的重要研究点，尤其是在变更影响分析和测试用例的生成、排序和优化方面具有很重要的作用。提出利用变量之间的依赖关系构建变量依赖关系模型。自动生成的变量依赖关系模型描述了变量之间的所有依赖关系，包括数据依赖关系、控制依赖关系、函数依赖关系以及指针引起的隐含依赖关系，并将图论和程序变量重要性度量相结合，基于变量依赖关系模型进行变量的重要性度量。根据变量在变量间信息传播的作用，提出变量“枢纽性”的概念，并通过实验证明了该方法在分析变量重要性度量方面更加有效。
在软件生命周期中，许多软件错误是由变量问题引起的，通过变量依赖关系模型可以快速定位到最可能出错的根源变量。基于变量依赖关系模型变量重要性度量方法，可以更好地评价软件内部变量的重要性，对变更影响分析和测试用例生成提供了新思路，有利于指导软件测试和提高软件的测试效率。
