0 概述

软件测试是软件开发中不可或缺的部分, 也是软件工程方法中的重要环节^[1]。软件测试中的Oracle指测试人员用来判定待测程序的输出结果是否正确的结果参照物。在传统测试技术中, 软件测试人员可以通过比较测试用例的执行结果与预期结果是否一致来验证待测程序功能是否正确。但在很多情况下, 难以获得一个程序的Oracle或者获得Oracle的成本太高, 即形成Oracle问题。

为解决Oracle问题, 文献[2]提出了蜕变测试方法。与传统的软件测试技术不同, 蜕变测试不再关注于比较单个测试用例的执行结果与预期结果是否相同, 而是通过检查待测程序多次执行结果之间的关系来检验待测程序的功能正确性。程序多次执行结果之间应当满足的关系称之为蜕变关系。如果程序多次执行结果不满足蜕变关系, 那么程序的错误就将被检测出来。目前, 蜕变测试已经成功应用于编译器^[3-4]、健康与医疗系统^[5]、嵌入式系统^[6-7]、生物信息系统^[8]、特征建模软件^[9-10]、搜索引擎^[11-12]、数值分析^[13]、服务计算^[14]、仿真软件^[15]等方面的软件测试中, 并且已被证明是有效的。

搜索引擎是指根据一定的策略, 在互联网上搜集、发现信息, 对信息进行理解、提取、组织和处理, 为用户提供检索服务, 从而起到信息导航作用的系统^[16], 是用户从网上获取所需信息的主要途径。但是由于互联网上的信息量过于庞大, 无论是业余的用户还是专业的测试人员, 都无法验证搜索引擎对用户查询返回的结果是否正确, 因此, 搜索引擎是典型的存在Oracle问题的软件。目前, 已经有许多学者将蜕变测试应用于搜索引擎进的测试^[11-12]。

文献[11]从逻辑关系包含、与、或、非等逻辑关系入手, 定义蜕变关系MR_SEARCH、MR_AND、MR_OR、MR_EXCLUDE, 通过比较搜索引擎对于查询项返回的结果数目是否满足蜕变关系, 对搜索引擎的功能正确性进行简单的测试。

文献[12]通过定义5种蜕变关系MPSite、MPTitle、MPReverseJD、SwapJD、Top1Absent对搜索引擎的网页检索能力以及排序能力进行测试, 但该文采用随机生成测试用例的策略, 没有考虑到使用搜索引擎的用户具体从事的行业, 宽泛的实验结果显然不能满足不同行业的从业人员选择一款适用的搜索引擎。

本文将蜕变测试应用于搜索引擎Baidu、Bing和360的功能测试, 选取经济、政治和文化领域的关键词并生成测试用例, 结合搜索引擎操作符定义合适的蜕变关系。在此基础上, 根据实验结果分析搜索引擎对不同领域关键词搜索性能的差异, 为相关行业的从业人员选择搜索引擎提供参考。

1 蜕变测试

首先, 假定有一个程序p, 实现了功能f, 其输入域为D。如果使用传统的测试方法来测试程序p, 首先根据一定的策略生成测试用例集T={t₁, t₂, …, t_n}, 其中, n>0, t_i∈D。然后测试人员将生成的测试用例集作为输入, 运行程序p, 可以得到程序执行结果p(t₁), p(t₂), …, p(t_n)。此时, 如果程序的Oracle是可以获得的, 那么测试人员将会把程序执行结果与程序预期结果f(t₁), f(t₂), …, f(t_n)相比较。如果对于某个i, p(t_i)≠f(t_i), 那么程序p的一个错误就将被检测出来。但是, 如果程序Oracle无法获得或者获得的价格过于昂贵, 那么上述的测试方法就不适用。

蜕变测试的核心思想是根据待测程序的功能属性定义蜕变关系, 然后在原始测试用例的基础上, 根据蜕变关系构造出衍生测试用例。随后执行原始测试用例与衍生测试用例, 观察待测程序关于原始测试用例与衍生测试用例的执行结果是否满足蜕变关系, 如果不满足, 则表明程序有错。

假如一个程序p的功能是计算e^x, 在采用随机实数x测试这个程序的时候就存在Oracle问题。此时, 就可以采用蜕变测试。首先, 定义一个或多个蜕变关系, 此处的一个典型的蜕变关系可以定义为:如果x₁=-x₂, 那么e^x₁×e^x₂=1。假定其中一个原始测试用例为(x₁=5.184 2), 那么根据蜕变关系则可以构造出衍生测试用例(x₂=-5.184 2), 程序执行2次, 计算p(x₁=5.184 2)×p(x₂=-5.184 2), 如果结果不等于1, 那么程序有错。

2 蜕变关系定义

在定义蜕变关系之前, 需要对常用的搜索操作符作简单的介绍。

搜索操作符1:site。该操作符用于将搜索结果局限在某个具体网站或者网站频道, 使用方法是将site置于一个网站或域名之前, 如site:gov, 如果将其添加在搜索项之后, 那么所有搜索引擎返回的查询结果都将是来自域名gov的网页。

搜索操作符2:双引号。该操作符用于关键词搜索, 用于搜索包含确切词组的网页。用法是将搜索项置于双引号之内, 如:“side effect of antibiotics in babies”, 那么搜索引擎返回的搜索结果的网页中应都包含关键词“side effect of antibiotics in babies”。

上述搜索操作符定义示例如图 1所示。

如果用户在输入查询项时没有使用双引号, 那么搜索引擎将自动采用语义搜索, 也就是搜索引擎将尝试理解用户的意思, 并返回查询结果。因此, 即使用户输入的查询项不同, 只要是意思是相同的, 那么搜索引擎返回的结果理论上应是相同的。如查询项“上海的天气”和查询项“天气上海”, 搜索引擎应返回相同的查询结果。

通过筛选, 本文选用文献[12]中定义的符合用户使用习惯的3个蜕变关系来测试搜索引擎, 以给用户提供最为真实的参考。下文将对这3个蜕变关系做出具体的说明。对于蜕变关系的描述, 文献[17-18]均提出使用形式化、标准化模板的方法定义蜕变关系, 但该方法表述复杂, 不容易理解, 具有很大的局限性, 因此, 本文仍使用自然语言对蜕变关系进行描述。

2.1 蜕变关系MR₁

将A作为原始测试用例, 搜索引擎将返回一个非空的原始测试用例结果集(a₁, a₂, …, a_i, …, a_n), 其中n>0, 且a_i是来自域名d_i的网页, 1≤i≤n。不难发现, 搜索引擎对于原始测试用例A返回的结果数量会非常庞大, 然而在日常生活中, 人们对于搜索结果的查看与点击率主要集中在前2页, 即前20条, 因此, 在蜕变关系MR₁中, 只取搜索引擎返回到前20条结果作为研究对象, 则0 < n≤20, 如果返回结果不足20条, 则全取。

根据原始测试用例的查询结果(a₁, a₂, …, a_i, …, a_n), 可以构造出n条衍生测试用例, 构造过程如下:第i条衍生测试用例B_i可分为两部分, 前一部分与原始测试用例A完全相同, 后一部分为site:d_i。

MR₁定义为:如果d_i为来自原始测试用例A查询结果集中a_i的域名, B_i为根据原始测试用例与域名d_i构造的衍生测试用例, FB_i为衍生测试用例B_i的结果集, 那么应满足a_i∈FB_i。其中, 查询项使用双引号, 属于关键词搜索, 测试搜索引擎的网页检索能力。MR₁测试流程如图 2所示, 其中, anomaly表示该组测试用例是否发生异常, 初始值为0, 如果原始测试用例与衍生测试用例的结果不满足蜕变关系, 则将其值置为1, 表示该组测试用例发生异常。

例如:原始测试用例A为“中国一带一路”, Bing共返回14 300条搜索结果, 本文取前20条作为研究对象, 从图 3中可以看出, 返回的第2条搜索结果a₂为:https://baike.baidu.com/item/中国“一带一路”战略研究院/18887339, 其域名为com, 则衍生测试用例可以构造为“中国一带一路”site:com, 并且a₂应包含于生成的衍生测试用例的搜索结果集当中, 否则, 记为一次异常。在执行所有原始测试用例与衍生测试用例之后, 发生异常的次数与衍生测试用例个数的比值, 记为异常率。

2.2 蜕变关系MR₂

MR₂的定义与衍生测试用例的构造与MR₁相似。搜索引擎对于原始测试用例A返回的结果集为(a₁, a₂, …, a_i, …, a_n), 其中, 0 < n≤20。t_i为a_i的标题, 1≤i≤n。衍生测试用例构造方法如下:第i条衍生测试用例B_i的前半部分与A相同, 后半部分为t_i。

MR₂定义为:如果t_i为来自原始测试用例A查询结果集中a_i的标题, B_i为根据原始测试用例与域名t_i构造的衍生测试用例, FB_i为衍生测试用例B_i的结果集, 那么应满足a_i∈FB_i。在查询项中, 既包含双引号括起来的部分, 也包含没有双引号的部分, 测试搜索引擎对抽取网页信息与理解用户意图的能力。测试流程同MR₁。

从图 3中可以看出, 第2条搜索结果a₁的标题为“中国一带一路网”, 那么衍生测试用例可以构造为:“中国一带一路”中国一带一路网, 其中, 原始测试用例使用双引号, 而t_i部分则不使用双引号, 并且a₂应包含于生成的衍生测试用例的搜索结果集当中, 否则, 记为一次异常。

2.3 蜕变关系MR₃

原始测试用例A由A₁和A₂组成, 衍生测试用例只需要将A₁与A₂的顺序颠倒。如原始测试用例为:“中国一带一路”, A₁为“中国”, A₂为“一带一路”, 则衍生测试用例为:“一带一路中国”。

MR₃定义为:如果衍生测试用例仅是将原始测试用例的顺序颠倒, 那么原始测试用例与衍生测试用例的搜索结果应具有很大的交集, 原始测试用例与衍生测试用例查询结果的重复度采用Jaccard系数表示, 其中, Jaccard系数的计算方法为:若原始测试用例的查询结果为R(A), 衍生测试用例的查询结果为R(B), 则Jaccard系数为|X|/|Y|, 其中, X=R(A)∩R(B), Y=R(A)∪R(B)。在此蜕变关系中, 不使用双引号, 搜索引擎自动使用语义搜索, 对于语义相同的查询项, 可以搜索引擎应返回相似的结果, 因此, 原始测试用例结果集与衍生测试用例结果集应有交集。该蜕变关系用于测试搜索引擎的排序稳定性。MR₃测试流程如图 4所示。

3 实验与结果分析 3.1 实验设计

传统的数据库系统返回的都是精确的查询结果, 而且返回的结果数量有限, 搜索引擎与之有较大不同。

一方面, 搜索引擎的数据库随着网络上内容的变化而动态更新^[19], 这就可能导致原始测试用例与衍生测试用例的执行结果不满足蜕变关系。对于这个问题, 采取的解决办法是:在执行完原始测试用例后立即生成并执行衍生测试用例, 减少搜索引擎数据库动态更新的影响。也正是因为数据库的动态变化, 对于搜索引擎的测试结果, 则有可能不可再现, 但是在短期内, 结果也不会发生较大的变化。

另一方面, 尽管搜索引擎可能采用了一定的排序算法^[20-21], 并综合考虑响应速度与准确率等各方面, 将查询到的结果只截取最合适的一部分返回给用户, 但是在日常查询中, 其结果数量仍然较大。解决这个问题的方法是:对于蜕变关系MR₁~MR₃, 只取前20条结果, 因为用户浏览内容基本集中在前20条。文献[12]采用加词法将查询结果控制在20条以内, 而在实际使用过程中则明显不可行, 常规搜索返回的结果显然不可能将查询结果控制在20条以内。只有最大程度上模拟用户行为, 才能使测试结果给用户提供最有价值的参考。

本实验主要寻求以下2个问题的答案:

Q1:不同的搜索引擎对于不同领域的关键词搜索表现是否相同。

Q2:经过多年完善, 不同搜索引擎对于不同语言的搜索性能是否仍然存在差别。

本文实验将从经济、政治和文化3个领域分别对搜索引擎Baidu、Bing和360进行测试, 因此, 使用4个集合:S_nation, S_economy, S_culture, S_politic, 其中, S_nation包含国家GDP排名前15的国家名称, S_economy、S_culture、S_politic分别包含20个经济、文化、政治领域的关键词。随后计算S_nation×S_economy、S_nation×S_culture、S_nation×S_politic, 其中×表示计算笛卡尔积。这样便可以分别得到15×20即300个经济、政治和文化领域的中文测试用例。因为目前英语已成为全球通用语言, 在日常生活中也不可避免地使用到涉及英语的搜索, 所以在获取中文测试用例之后, 将其翻译成英语, 便可以获得对应的300个英文测试用例, 这样便可以从不同的操作剖面进行测试, 更好地模拟用户操作。最终, 可以得到经济、政治、文化领域的300个中文原始测试用例和300个英文原始测试用例, 如表 1所示。

3.2 实验结果

首先需要定义实验中的自变量和因变量。在蜕变关系MR₁~MR₃中, 自变量包括操作剖面(即中文和英文)、搜索引擎(Baidu、Bing和360)和测试用例的类别(经济、政治和文化), 因此可以得到2×3×3=18种组合。蜕变关系MR₁和MR₂的因变量为异常率, 值域为[0.0, 1.0], 蜕变关系MR₃的因变量为原始测试用例与衍生测试用例查询结果的重复度的平均值, 采用平均Jaccard系数表示, 值域同样为[0.0, 1.0]。

3.2.1 MR₁实验结果

图 5为展示蜕变关系MR₁中18种组合的异常率的直方图。在2.1节中提到, MR₁主要测试搜索引擎的网页检索能力, 异常率越低证明搜索引擎的检索能力越好。在实验过程中可以发现, 360搜索并不支持如“site:com”的限定域名的搜索, 如果想要使用搜索操作符site, 需要将域名限制的更加具体, 如site:com.cn。因此, 在蜕变关系MR₁中, 本文将360搜索引擎的异常率统一置为1。从图 5中可以看出, 不同搜索引擎的表现差异很大。Bing搜索引擎的异常率最低, 检索能力最好, 异常率均保持在0.3以下; 而360搜索引擎的异常率最高, 检索能力最差, 因为它不支持该搜索操作, 异常率均为1;Baidu的中文的异常率明显低于英文搜索, Bing搜索引擎的英文搜索异常率总体上低于中文搜索, 而在经济、政治和文化领域, 同种语言的异常率差异较小。

3.2.2 MR₂实验结果

图 6为展示蜕变关系MR₂中18种组合的异常率的直方图。从图 6中可以看出, 查询语言对实验结果有很大的影响, Baidu、Bing和360的中文搜索异常率均显著低于英文检索, 且文化-中文类关键词异常率均保持最低。Bing英文搜索异常率最低, Baidu英文搜索异常率最高, 而在经济、政治和文化领域方面, Baidu、Bing和360的异常率差异较小。

3.2.3 MR₃实验结果

图 7为展示蜕变关系MR₃中18种组合的Jaccard系数的直方图。MR₃主要测试搜索引擎的排序稳定性, 平均Jaccard系数越高证明搜索引擎的排序稳定性越好。从图 7中可以看出, Baidu、Bing和360的排序稳定性相差并不大, 但相对来说, Baidu的排序稳定性略胜一筹, Bing表现稍差。此外, Baidu的中文搜索排序稳定性优于英文搜索, 其中又属文化类关键词搜索稳定性最高, Bing的英文搜索优于中文搜索, 且政治类关键词搜索稳定性最高, 360则无明显规律, 但文化类关键词搜索稳定性最高。

3.3 结果分析

根据实验结果, 可以得到Q1和Q2的答案。

Q1:Baidu、Bing和360搜索引擎对于不同领域的关键词搜索表现有些许差异, 但总体差异不大, 且无明显规律。其中, Bing的异常率最低, Baidu的排序稳定性最高。

Q2:尽管Baidu、Bing和360已经推出多年并经过了多年完善, 但对于不同语言搜索表现仍然存在很大差别, Baidu和360的中文搜索表现明显优于英文搜索, 更适合用于中文检索。

4 结束语

本文选取经济、政治和文化领域的中英文关键词生成测试用例, 运用蜕变测试技术, 对搜索引擎面向不同领域关键词以及不同语言的检索能力和排序稳定性进行测试, 将搜索引擎的性能量化为异常率与Jaccard系数, 为用户提供一个直观的参考。实验结果表明, 在缺少Oracle的软件测试中, 蜕变测试能够降低测试难度, 展示出其强大的适用性。下一步将结合用户使用习惯挖掘搜索引擎的不同特性, 优化实验设计, 以期从更多维度给予用户选择搜索引擎的建议。