构建软件测试领域不确定性知识图谱

罗浩榕，朱卫星，史涯晴，万进勇

(陆军工程大学 指挥控制工程学院，江苏 南京 210001)

0 引 言

软件测试通过动态和静态的测试技术发现软件缺陷，是软件质量保证的关键活动。在实际软件测试过程中，由于软件测试分析、设计和执行技术的不足，测试用例几乎不可能做到输入域的全部覆盖，因此软件测试的结果并不总是处于可预知的范围内，从历史软件测试资产中获取的软件测试知识具有一定的不确定性。因此，建立软件测试复用系统必须考虑如何表达不确定性知识和求解不确定性问题，尽可能消除测试不确定性。传统的软件测试复用通常基于1991年提出的软件复用3C模型[1]，即被复用工件的概念(concept)、内容(content)、上下文(context)。由于时间和成本的限制，这三个维度的确定性假设可能很难成立，精确且完整的描述软件测试的概念、内容和上下文是非常困难的[2]。2012谷歌提出了知识图谱的概念，对现实世界中的实体、概念、属性及其关系进行建模，与传统的专家知识系统相比有更强的语义表达能力和建模灵活性，在知识存储、检索和推理方面有更大优势。建立专业领域知识图谱通常采用“自上而下”的方式，根据建模需求和业务领域构建领域本体作为知识图谱的模式层，再通过业务数据对本体实例化。为了表达知识的不确定性，模糊知识图谱结合不确定性建模方法扩展经典本体[3-4]，建立不确定性知识的表示和推理机制，在软件测试中不确定性建模方法包括贝叶斯信念网络、粗糙集、模糊逻辑、隐马尔可夫模型等[5]。其中粗糙集可以表示不确定性信息空间中的多属性决策函数，而软件测试过程需要考虑多种属性是典型的多属性决策过程，因此考虑基于粗糙集扩展软件测试资产本体。

1 软件测试中的不确定性

2014年，在SWEBOK 3.0发布的软件工程知识体系中，将软件测试定义为“从一个通常是无限的执行域(集合)中选择合适的、有限的测试用例，对程序所期望的行为进行动态验证的活动过程”。因此用三元组〈I,S,O〉表示软件测试用例T，其中I是被测件输入域，O是被测件输出域，S是被测件的起始状态，另有函数f表示输入域到输出域的映射。那么，对于测试用例任一测试输入都有一个在已知输出域的结果，即预期结果：

T〈I,S,O〉:[∀i∈I→∃f(i)=o∧o∈O]

(1)

当测试结果和缺陷分布未知时，认为软件测试存在不确定性，即对于给定的输入和起始状态，可能出现在已知输出域之外的结果。

UncertaintyT〈I,S,O〉:[∃i∈I→∃f(i)=

r∧r∉O]

(2)

造成软件测试中存在不确定性的主要原因有[5-6]：

●在测试需求分析阶段，由于软件开发阶段，需求建模与真实的用户需求和相应问题领域存在一定差异，软件测试继承了软件需求的差异性。

●测试设计阶段，由于经济成本和时间成本的限制，遍历输入域的详尽测试无法实现。因此，对于每一个被测件都必须选择有限的测试用例子集，这可能无法检测所有的缺陷，造成了一定的不确定性。

●对于许多软件系统例如嵌入式软件，完整地复现用户场景并不现实，因此软件测试通常在模拟测试环境中实施，测试环境与真实环境的差异也引入了不确定性。

2 软件测试模糊知识图谱

具有较大复用价值的软件测试资产主要包括三类：测试需求、测试用例、问题报告。这三类测试资产涵盖了软件测试分析、设计、执行、质量估计的全生命周期，是软件测试知识的集中体现。首先依据本体从三类测试资产中提取软件测试知识实体，形成测试资产知识图谱，结合行业标准中的领域知识形成领域术语图谱，再建立测试资产与领域特征的关联关系，采用基于知识粒度的方法为资产-特征赋予关系置信度。该文面向软件测试资产建立不确定性知识图谱的总体框架如图1所示。

图1 软件测试资产不确定性知识图谱建立总体框架

基于上述总体框架，对测试资产本体、领域术语图谱构建方法、模糊关系置信度计算3个方面进行阐述。

2.1 测试资产本体

软件测试资产中包含大量信息，这些信息可能通过正确的表示和处理转化为适用的知识，应用知识管理方法和原则管理测试资产，可以促进测试过程中的复用[7-8]。软件测试资产主要有三个对象类，即测试需求、测试用例和问题报告。

定义1：测试需求。测试需求确定测试目标、测试内容和质量特性，确定测试充分性要求，提出测试活动应当遵循的基本原则和要求，确定测试资源和技术需求。测试需求(Test Requirement，TR)包括七元组：测试目标(Target，Ta)、被测件描述(Description，De)、测试阶段(Phase，Ph)、测试类型(Type，Ty)、测试环境(Environment，En)、测试方法(Method，Me)、判断规则(Evaluate，Ev)，记为：

TR=〈Ta,De,Ph,Ty,En,Me,Ev〉

(3)

经验表明，同一领域的测试项目往往遵循相同的行业规范、标准等，同一类型软件的使用场景、功能结构、性能要求等存在很大相似性，因此具备了知识复用的基础。

定义2：测试用例。测试用例是指测试人员根据软件需求规格说明和程序内部结构，精心设计出的一组测试输入、执行条件以及预期结果，用于核实软件是否满足某个特定需求。测试用例(Test Case，TC)包括五元组：需求追踪项(Required Trace，Rt)、前提条件(Precondition，Pr)、输入数据(Input Data，In)、执行步骤(Operation Step，Ops)、预期结果(Except Result，Er)，记为：

TC=〈Rt,Pr,In,Ops,Er〉

(4)

测试用例设计是软件测试的核心工作，对测试用例的复用是目前研究最多的，除了查找相似的测试用例直接获取历史经验，还可以归纳形成测试设计模式。

定义3：问题报告。问题报告是对未通过的测试用例进行记录和总结，提出复现软件缺陷的最短路径，分析定位错误。问题报告(Bug Report，BR)包括五元组：用例追踪项(Case Trace，Ct)、实际结果(Actual Result，Ar)、缺陷特征(Bug Character，Bc)、缺陷定位(Bug Location，Bl)、严重程度(Bug Severity，Bs)，记为：

BR=〈Ct,Ar,Bc,Bl,Bs〉

(5)

问题报告中蕴含了测试人员对软件缺陷的总结，可以获取软件缺陷模式知识帮助后续开发人员定位缺陷，对于修复问题具有重要意义。从测试资产原始数据中获取以上三类对象的实例，每条实例作为知识图谱中的一个节点，这些节点按照固有的继承和关联关系相连接，这部分关系由原数据直接得到，不赋予模糊置信度。

2.2 领域术语图谱

软件测试的决策因素主要包括被测件本身的特征、行业特征和软件测试本身特征。因此，将软件资产中的概念分为三类〈Wd,Wt,Ws〉，其中行业概念Wd指被测件应用的问题领域相关概念；软件测试概念Wt指软件测试本身特有概念词汇；软件概念Ws指描述被测软件的特征概念，包括软件架构、接口协议、编程语言等，每一类概念包括若干棵领域术语树。

领域术语树中每个节点代表一条领域术语，节点间存在两类关系：子术语关系、近似术语关系。

3 领域术语图谱构建

领域术语图谱构建过程如图2所示。

图2 领域术语图谱构建过程

①基本术语树构建，基于行业标准等权威数据建立领域概念结构。

根据国标、国军标等行业标准中关于行业领域、软件测试、软件系统的相关定义，构建层次化的术语树。

②候选词提取，基于互信息和左右熵从测试资产语料中发现候选词集[9]。

行业领域的术语词往往与一般词汇不同，通用分词工具的结果可能遗漏一些固有搭配，例如，指挥信息系统可能被分解为三个词：指挥、信息、系统。互信息和左右熵分别计算词的内部凝和度和边界自由度。

词语x和词语y的互信息MI(x,y)体现了两个词之间的依赖程度，其计算方法如下：

(6)

其中，P(x,y)是词语x、y的共现词频，P(x)、P(y)定义类似。互信息越高，说明词语x、y相关性越高，组成术语短语的可能性越大。

词语x的左右熵H(x)指该词左右边界的信息熵，其计算方法如下：

log2P(xb|x))

(7)

其中，A是x的前序词语集，B是x的后序词语集。x的左右熵越大，说明该词的周边词越丰富，自由程度越高，x独立成为一个词的可能性越大。

通过计算互信息和左右熵进一步处理通用分词工具的分词结果，可以发现行业领域的特有词语搭配，这些特有搭配往往就是行业术语。

③规则过滤，筛选去除非词。

由于语料中噪声和算法的误差，前述无监督的候选词抽取结果中可能含有少量的非词，需要通过专家规则进行筛选。

④新词发现，对比软件测试资产语料和背景语料，进一步筛选特征词[10]。

前述通过词频提取的候选词集中除了特有的术语还包括通用的词汇和短语。 因此，对于候选词x，通过对比该词在不同语料中的信息量进行打分，其打分函数定义如下：

(8)

其中，平滑参数μ是一个较小的正数，为了避免在背景语料中x词频为0的情况下得分为无穷大。在该打分函数中，如果词语x在软件测试资产语料中词频PD(x)比在背景语料集中语料Ti的词频PTi(x)更高，那么会得到更高的分数，选择得分前50%的候选词作为特征词。

⑤语义聚类，通过词向量聚类获取近似领域词集[11]。

结合特征词表，在软件测试资产和行业标准语料进行分词并训练一个Word2Vec模型，根据Word2Vec得到的词向量来对词进行聚类。算法以术语树中的节点作为种子词，利用相似的传递性计算近似词集。为了尽量避免迭代过程中的指数偏移，以指数衰减的方式迭代计算词向量余弦相似度，将近似词聚为一类，每一类包含且仅包含一个种子词，连接到基本术语树中的相应节点形成完整的领域术语图谱。相似度计算方法如下：

(9)

(10)

参数α>0是指数衰减常数，决定相似度随迭代的衰减速度。第一轮迭代时，将所有与种子词k相似度N0(x,k)超过阈值的特征词x加入集合；之后每轮迭代将与集合中特征词x相似度Nt(x,y)超过阈值的特征词y加入集合；直到集合元素不再增加时，得到x的近似词集合，将该集合所有元素加入术语树，并与种子词k建立相似关系，最终得到领域术语图谱。

4 基于知识粒度的模糊置信度计算

经典模糊知识系统中，模糊置信度由专家根据先验知识赋予，这种方法较为主观，且在实例较多的知识系统中工作量十分庞大。粗糙集理论是一种处理不精确、不完全数据的数学理论，目前已经广泛应用于机器学习、知识发现、数据挖掘等场景。在经典Pawlak粗糙集理论中，知识指根据特征对论域进行分类所得的子集，知识库定义为一个粗糙近似空间AS=(U,R)，其中U是论域，R是在U上的一族等价关系。

定义4：知识粒度[12]。设AS=(U,R)是一个知识库，R∈R是一个等价关系，R对U划分的等价类集U/R={X1,X2,…,Xn}，那么知识R的知识粒度为：

(11)

知识粒度可以描述知识的分类能力，知识粒度越小，其划分的等价类越精细，那么知识的分类能力越强。软件测试知识的不确定性可以归为两类，一是概率性，即软件测试知识本身具有概率性；二是模糊性，即在知识图谱中用于描述知识的术语不清晰或不准确。以模糊置信度建模特征术语对软件测试资产的影响程度。每一条软件测试资产数据都涉及若干特征术语，这些特征术语体现了该软件测试资产的决策因素，将知识的概率性和模糊性统一以置信度的形式表示。置信度越高表示特征术语w对测试资产A的代表性越强。文中特征术语和软件测试资产的模糊置信度实质上即通过特征术语区分软件测试资产的能力[13-14]，有研究表明决策属性的知识粒度越小则其信息熵越大[15-16]，基于知识粒度计算模糊置信度，评价相应特征对软件测试资产的信息熵影响，也即其决策影响程度是有效可行的。对于每一条资产A，通过三类概念特征集合{wd,wt,ws}表征，这里wd表示资产A中涉及的问题领域概念子集wd∈Wd，wt,ws类似。在图谱中搜索与资产A相关的所有概念，相似概念则合并为一项，通过概念特征集{w1,w2,…,wn}表示一条资产数据。计算术语wi作为资产A特征的模糊置信度分为两步：粗糙近似空间构造、模糊置信度计算。

4.1 粗糙近似空间构造

构造粗糙近似空间AS=(U,R)，即确定论域U和等价关系族R，由于R中的等价关系实际上指特征属性相同或近似而不可区分的论域对象集。因此构造Pawlak粗糙近似空间等价于确定一个知识表达系统S=(U,P,V,f)，其中U为对象的非空有限集合，P是属性的非空有限集合，V是P的值域，f:U×P→V是信息函数为每个对象的每个属性赋值，有∀a∈A,∀x∈U,f(x,a)∈Va。文中特征术语相同的测试资产是不可区分的对象，论域UA为软件测试资产实例集，V为论域中所有测试资产的特征术语全集，P为V的父概念集。若以模糊知识图谱中的测试资产全集为论域，存在两个问题：一是搜索空间过大，计算效率低；二是大部分测试资产与资产A特征无关，大量无关测试资产被分为一类使得知识粒度接近于1，不能有效区分特征术语wi对资产A的分类能力。因此，需要筛选论域，构造与资产A和特征术语wi粗糙近似空间，在软件测试模糊知识图谱GF中确定测试资产实例A与其特征术语wa相关的粗糙近似空间方法如下：

算法 1：软件特征粗糙近似空间构造。

Input：软件测试模糊知识图谱GF、测试资产实例A、A的一个特征术语wa

Output：资产A相关的知识表达系统SA

#搜索特征wi的中心特征k及其父概念K

1 searchk,KfromGF, whichwa≈k∧k∈K

#搜索概念K相关的所有A同类测试资产集UA作为论域

2 for everyk∈K:

3 search allAifromGF, whichAi∽k∧type(Ai)=type(A),

putAiinUA

#搜索条件属性集P及其值域V，信息函数f

4 forAiinUA:

5 searchkij,Kij, whichAij∽kij∧kij∈Kij

6 putKijinP

7 put((Aij,Kij)→kij) inf

8 searchk∈Kij, putkinV

#输出粗糙近似空间

9 output:(UA,P,V,f)

4.2 模糊关系置信度计算

通过概念类K的知识粒度刻画资产A对术语wi(wi∈K)的置信程度，K的知识粒度越小即认为这一类概念对测试资产的划分描述能力越强，是有效的分类特征[15-16]，通过z型模糊器计算得出的A与wi的模糊关系置信度越高。

定义5：概念K的决策能力。以概念K作为条件属性对论域做划分，K的若干子概念{wk1,wk2,…,wkl}，将论域划分为l个等价类。那么K的分类能力CK计算如下：

(12)

定义6：模糊关系置信度。设有测试资产A，wi是表征A的一个概念特征，根据前述粗糙近似空间构造方法得到论域UA和条件属性集P={K,K1,…,Km′}，那么wi与A的模糊关系隶属度为：

μ(A,wi)=zmf(CK)=(1+eρ(CK-θ))-1

(13)

参数ρ、θ决定模糊函数的平滑程度。模糊关系置信度μ(A,wi)∈(0,1)描述了在产生资产A的软件测试活动中，术语wi所代表的领域知识对决策过程的影响程度，置信度越高则影响力越强，在对资产A进行知识推理时，该特征的重要性越高。

5 实例验证

本节通过一个实例验证了该方法的可行性

5.1 实验条件

采用neo4j图形数据库构建实例知识图谱，数据来源于作者所在单位承担的软件测评任务和网络搜集的行业标准等数据，具体见表1。

表1 实验条件

5.2 结果分析

软件测试资产知识图谱中知识实体、关系的情况如表2和表3所示。

表2 知识实体统计

表3 资产知识关系情况

从表2、表3可以发现软件测试资产知识图谱实体关系较为稀疏，知识实体多且分散，如果用关系数据库存储知识实体，一方面不便于建立实体-实体、实体-特征的关联关系，进行复杂条件查询时大量链接操作会极大影响查询效率。另一方面，知识图谱比关系数据库更有利于后续知识推理任务。

领域术语图谱情况如表4所示。

从表4可以看出，由于测试人员撰写不规范，软件测试资产中的领域术语存在大量近似词，模糊化的知识表述对知识复用造成了严重阻碍，直接进行关键词查询可能造成错误或遗漏。领域术语图谱可以视为一种结构化的近义词典，通过先验知识提高了知识实体查询的准确率和查全率，大大减弱了测试知识复用中由测试资产模糊性带来的知识错漏问题。

表4 领域术语图谱实体关系

表5对比了使用关键词查询测试知识实体时，有、无领域术语图谱辅助的两种情况。

表5 准确率/召回率对比

6 结束语

该文设计了一种可以表达不确定性知识的软件测试知识图谱构建框架，能够利用测试需求、测试用例、问题报告三类软件测试资产和行业标准等领域知识建立软件测试知识图谱，提出了一种基于信息量的领域术语挖掘方法，在此基础上构建了领域术语图谱作为软件测试资产的特征。为了强调软件测试中的不确定性，使用通过特征术语的知识粒度建模计算其在软件测试过程中的决策影响程度。通过为软件测试资产的特征赋予模糊置信度，构建了软件测试模糊知识图谱，为后续软件测试不确定知识推理做铺垫。