查看原文
其他

长篇详细阐述:基于代码的测试生成技术在召回异常问题中的应用实践

The following article is from 百度智能化测试 Author 车厘子和夹心饼干

导读:线上系统异常问题一直以来都是使人”闻风丧胆”的,传统手段在解决这类问题时面临着相应的技术瓶颈。基于此,探索基于单元测试召回异常问题的方法,实现了一套通用且无人参与的单测生成系统,在百余模块上落地取得了一定的效果。从近代码手段的单元测试着手,围绕基于单测生成技术召回异常问题的应用实践展开。主要介绍该方案0到1的整体建设思路、并从理解代码、构造高覆盖测试用例数据、生成测试用例代码以及分析失败用例这四方面展开介绍。

线上稳定性问题一直以来是备受大家关注的。在影响产品收益或用户体验的同时,也影响着QA的口碑。
为了避免这类问题发生在线上,测试人员有一系列的异常测试召回手段可以采取,常见的有:基于压力测试、基于功能测试、基于单元测试或者基于静态扫描的异常召回手段,然而在足够完备的召回能力下,还是会有问题漏出到线上,这又是为什么呢?
本文提出一种基于白盒手段召回异常问题的通用方法,并以C/C++语言为例,介绍该方法在百度服务端的落地思路。

一、问题分析
带着上面的疑问,本文对业界内现有异常测试手段在高成本、低召回这两个问题维度上进行了对比分析,对比结果如下表1.1所示。

表1.1 业界常用异常测试手段缺点对比分析

整体上看,当前的召回手段存在滞后性或成本高的问题,像基于压力测试的异常召回手段资源消耗较高,基于功能测试的异常召回手段除开发成本较高外,还存在异常场景不易构造等滞后性问题。基于单元测试和静态检查来发现代码问题已是这些手段中缺点相对较少的,接下来更详细地对比下单元测试和静态检查这两种召回异常的手段。
如今,静态检查已是最常见的异常发现手段,其接入成本低,轻量级。以静态扫描方式来检查,不需要编译运行、不占用资源。但其存在以下问题:
  • 滞后性:线上出了问题后才能转化为规则规避同类问题复发。
  • 准召低:规则靠人来设计,对某些场景会存在漏掉或者误报的问题,需要case by case的解决。
  • 不可持续:缺少围绕规则的生态建设,可能出现规则重复开发、缺少规则贡献者、规则上线后无法有效评估等问题。

基于单元测试来召回异常问题有两个缺点开发成本高、依赖人的意识。开发人员针对本次功能中的重要函数,编写其对应的单元测试代码来进行测试。选择哪些函数,验证哪些异常场景都依赖开发人员的经验和主动程度。但它也有以下优点:
  • 测试最小单元,易于构造数据,验证正确性
  • 便于后续功能回归
  • 资源消耗小
  •  能更早发现问题,定位和解决成本低
经过上述分析后,可以得出基于单元测试的优势远大于其缺点的结论,于是大胆假设:能否最大化它的优势,解决依赖『写』和『经验』的问题。——即自动撰写异常的单元测试代码,主动发现代码健壮性问题。
在这一设想下,提出一种可持续的、主被动结合、高ROI的稳定性问题召回漏斗(如图1.1所示),智能UT作为静态代码检查环节后的主动召回手段,动态分析召回问题
图1.1 稳定性召回漏斗图

二、解决思路
2019年初,在对生成用例代码的强诉求下,调研了C/C++语言业界中比较通用且优秀的单测生成工具:C++ test和Wings,在开发成本、召回能力和是否开源三方面进行了对比,对比结果如下表2.1所示。显然,无论是C++ test还是Wings,都无法满足业务线在复杂业务场景下完全自动化对复杂类型函数生成单测代码的诉求以及扩展,因此需要自建单测代码生成能力。
表2.1 业界C/C++单测生成工具调研对比

将开发人员对一个函数撰写单元测试代码的过程进行拆解,各关键步骤如图2.1所示,将整个过程抽象为 “确认待测试函数->分析代码->构造测试数据->生成测试代码” 这4个过程。
  • 确认待测试函数:本次提交的代码中,并非所有的变更或新增函数都需要测试,可以结合函数属性(如构造函数、析构函数等)、修改内容(如测试相关的代码、日志逻辑等无风险函数)。
  • 分析代码:汇总被测函数的代码,如参数(输入参数、内部依赖其它依赖参数)、返回值等信息。
  • 构造测试数据:主动构造被测函数所需的用例数据,无需人工参与。
  • 生成测试代码:主动生成测试被测函数的代码,无需人工参与。
解决思路的关键是通过代码分析等白盒技术来实现一键异常单元测试代码的能力,真实模拟开发人员撰写单元测试代码。
图2.1开发人员实现单测代码编写的过程

三、实现方案
基于上一节分析,整个技术方案设计如图3.1所示,本节重点介绍代码分析、测试用例生成、代码生成能力和执行分析的实现思路。
图3.1 技术方案设计图

3.1 代码分析能力
代码分析的目标是期望能通过静态代码扫描的手段,将复杂的函数代码抽象成结构化的函数特征数据,可以类比编译符号表。基于这份结构化数据能直接感知函数调用方式、变量声明和赋值方式等行为。

3.1.1 代码特征
C/C++语言中,尤其是C++这类面向对象的语言,函数调用和类的声明创建方式和普通变量不同,存在更丰富的语法多样性。首先要明确该语言在代码分析过程中需要获得的信息内容,重点考虑的因素如下:
  • 函数调用:普通函数调用、类的成员函数调用
在调用类的普通成员函数前,需要先实例化类的对象,而非成员函数可直接调用。
  • 变量声明实现:普通变量、class或struct变量、stl变量等

不同变量声明赋值方式都不同,需要能够区分是普通变量还是class、struct、stl变量

  • 修饰符:const、static、virtual、inline等

加了修饰符的变量或函数会影响它的调用、实例化、赋值方式

  • 文件级别信息:头文件,命名空间

头文件和命名空间不全或者缺失会影响测试代码的编译

  • 其它

一些影响赋值、实例化语法的其它属性。如类是否禁用了拷贝/赋值构造函数等。

基于上述思路,最初敲定获取如下代码特征信息:

表3.1 代码特征信息

3.1.2 特征存储
将特征存储以xml文件格式存储,存储为代码结构数据(CodeStructData,CSD),且保证周边模块能基于该份产出获取函数调用方式、变量声明和赋值方式。根据不同类型和赋值方式约定schema,如type、baseType1、parmType等属性,Demo如3.1配置示例。
  • type:实际类型
  • baseType1:该变量实际属于类别,如内置类型、数组类型、STL类型等。
  • parmType:声明类型,生成代码时可直接取该字段作为变量的声明类型。
    3.1  经源码分析得到的CSD配置样例

3.1.3 特征采集
这一环节,期望能在不编译的条件下,以静态代码扫描方式提取代码信息,且工具要轻量、高效、支持开源,以便于后续需求迭代。
在综合对比下,最终选择cppcheck,一个开源的静态代码检查工具,除此之外还可以基于它的符号表来做二次开发。为了采集函数调用链信息和其它全局信息,内部对cppcheck进行了改造,后续会单独介绍,本文不多赘述。采集过程如下图3.2所示。


图3.2 基于cppcheck的代码分析方案示意图

3.2 用例数据生成能力


3.2.1 解决思路

用例数据生成能力属于Fuzzing技术领域中关键的一个环节,常见的fuzz数据手段有基于生成的和基于变异的两种方式。一般会使用覆盖率来衡量fuzz能力,比如函数覆盖、行覆盖或分支覆盖。
  • 基于变异法:根据已知数据样本通过变异的方法,生成测试用例。比如著名的AFL-fuzz技术,其主要处理过程如下图3.3所示:
图3.3 AFL-Fuzz处理过程
  • 基于生成法:根据已知协议或接口规范进行建模,生成测试用例。比如libfuzzer可以在不指定初始数据集下,通过被测目标的接口类型,随机生成字节数据,喂给被测目标。
在生成用例数据时,避免用例爆炸也是生成的条件之一,过多的用例会存在用例无效和运行时效低问题。
本文在传统的基于生成法构造用例数据的基础上,除了被测目标接口协议外,充分利用路径和分支信息来指导fuzz数据,覆盖更多分支内的逻辑,还引入了其它白盒特征,如变量扩散关联性等去降低对无效用例的生成,最后以函数覆盖和分支覆盖作为fuzz能力的度量指标。
解决思路如下图3.4所示,数据生成层由CSD处理模块、路径选择模块、参数选择模块和生成&筛选 模块构成。针对不同类型的变量,选取不同的异常候选集,生成初始用例集合,再经过用例筛选策略得到最终的测试用例集。
图3.4 测试用例生成方案示意图


3.2.2 路径选择

路径选择模块包含表达式约束求解、路径可达分析以及路径合并。这一部分的目的是指导数据生成对分支的覆盖。路径的提取,主要通过遍历上一节提取的程序控制流数据来完成,可以采取深度优化遍历或广度优先遍历,不影响结果。

为了避免路径爆炸,可以先提取出期望测试覆盖的目标,遍历时每次选择一个可以覆盖待测试目标的路径。

  1. 约束求解是指对路径上的分支表达式进行求解计算,分别计算出表达式为真和假时的符号值。这里需要先对表达式进行替换,例如将函数调用替换成变量,便于计算。替换后的表达式可以使用开源的库进行求解,如z3。

  2. 路径可达分析是指以分支如if、while、for、switch为节点,计算节点内求解出的变量值或变量范围,对函数内部各节点进行连接后,得到一个图。结合每个节点变量的范围,对图中的路径进行剔除,删掉不可达的路径。

  3. 路径合并是指将含有交集的节点合并成一条路径,减少后续用例生成数量。如3.1程序代码示例中对_index_i和_index_j构造用例时,构造出{_index_i=1, _index_j=2}来满足同时覆盖17行和22行两个分支的数据。在处理时需要分析出分支内部是否存在return、continue、break这类的跳转或返回关键字,避免出现badcase。

3.1 程序代码示例



3.2.3 候选数据源

各类型的候选异常数据可分为静态数据和动态数据。

  • 静态数据指通过历史经验维护的一份类型边界值和业务边界值数据库。
  • 动态数据指通过业务数据采集和变异算法,基于模块日志、流量等数据源通过插桩的方式挖掘出的业务值或经过变异得到的异常边界值。


3.2.4 用例生成&筛选

基于上述步骤得到各参数候选值集合后,便可对参数之间进行组合,得到用例集合,参数组合的方式直接影响着用例量级,此阶段重点考虑如何避免用例爆炸,减量不减质量
经统计,大约70%以上的软件问题是由一个 或2个参数作用引起的。因此参数因子两两组合就成为了软件测试中一种实施性较强同时又比较有效的方法。如果采用全排列组合方式,在某业务场景下,某类classA类型作为函数形参,假设该classA有1000个成员变量,其成员变量全部为v类型,类型v有4个取值,v=[-1,0,1,-2147483649],那么全排列组合后的用例数据量高达4^1000个。
可见,单纯的全排列组合能保证当前因子组合覆盖的场景最丰富,但会面临case爆炸问题,这不符合实际应用背景。
其实,生成一个最小测试用例集是一个NPC问题,因此学术界一般是将找到一个尽可能小的测试用例集去覆盖所有可能的配对来作为研究目标。本文先后使用两个步骤来减轻用例的量级。
1. 剔除无用属性:基于代码分析减少对无用属性的数据构造。通过分析自定义类型参数其成员属性扩散性,只对类/结构体中实际被用到的成员属性构造数据。
3.2  函数内变量和其成员变量样例

2. 剔除冗余用例采用基于生成的方式,选择一种参数组合算法,生成合适的测试用例。常见的生成技术大体可分为组合设计法、启发式算法、元启发探索法:
  • 组合设计法,一般是围绕正交表或其它代数的思路生成测试用例。
  • 启发式算法一般是逐条地或逐因素扩展地生成测试用例。如经典的AETG算法:首先按贪心算法生成一定数量N个测试用例,然后从这N个测试用例中选择一个能最多覆盖未覆盖配对集合中参数对的用例,将这个用例添加进已经形成的测试用例集T中,直至达到覆盖目标。如IPO算法,通过先水平、再垂直的方式扩充用例。
  • 元启发式算法,如遗传算法、模拟退火、蚁群算法等,大致过程如下图3.5所示。
图3.5 元启发式用例探索大致过程
启发式和元启发式都属于局部搜索算法,不能保证最优但可以保证处理时间。还可以将逐条生成法和元启发方式结合,引入错误风险系数、组合约束和参数优先级等信息,进一步优化组合方式。
本文初期利用逐条生成的方式,基于基础的成对法来减少重复无效的输入。以一个例子简单介绍本文使用的2-Wise testing成对法思路(其原理可参考文末提供的资料):
假定有三个输入变量,X、Y、Z,取值分别为D(X)={x1, x2, x3},D(Y)={y1,y2},D(Z)={z1,z2};
如果用全排列法,得到的测试用例集有3 X 2 X 2 = 12个用例,具体测试用例如下左图3.6所示,通过2-Wise testing处理后仅获得6个用例。
图3.6 全排列用例和成对法算法过程

本文通过上述方法有效剔除了90%以上的无用测试用例数据。最终将保留下来的测试用例以json格式存储,作为测试数据集合,方便扩展和供其它场景使用。数据Demo如下所示,以函数名、func_data、变量名作为key,以具体的参数值作为value。


当前这种生成方式是以参数和参数之间相互独立为假设前提,思路简单,而实际业务场景下,参数和参数之间是可能存在关联的,在生成方式上还有较大提升空间,后期会在当前逐条生成的能力下,引入元启发探索算法,如在该领域效果比较显著的遗传算法或模拟退火算法,在每生成一条测试用例时都调用探索算法,以提升覆盖率和重要覆盖元素为目标,生成有效测试用例集,这也是智能UT中的最重要的『智能』场景之一数据是揭错之本

3.3 代码生成能力


3.3.1 解决思路

代码生成领域目前主要有两个重要方向:程序生成和代码补全。生成测试代码属于程序生成方向,采用深度学习算法生成代码是目前学术界当前比较重要的研究方向,已经基于一些开源的代码作为语料库取得了一定的技术突破,但因存在泛化能力弱的问题,还无法在工业界落地。

在实际技术落地中,程序生成的正确性直接影响测试任务的稳定性,考虑到这一约束,本文目前采用基于语法规则和模板的生成方式来生成测试用例代码。语法规则和代码结构数据正确即可保证生成代码语法正确,达到生成即可编译的目标。

具体实现方案参考如下图3.7所示,将上述步骤得到的代码结构数据和测试用例集合数据下发给代码生成处理模块,模块通过控制层选择不同语言对应的生成器,再根据不同类型选择对应的生成算子。对于可变内容,深度遍历代码结构数据的每一个函数节点、参数节点和全局节点,针对各自节点下的代码信息,获取对应的语法适配生成算子来生成目标代码,从而得到测试用例代码,再结合模板中的固定源码,封装成可编译运行的单测代码。这一过程可以类比编译器结合语法树生成目标代码的过程。

像C/C++语言,生成基于Gtest的死亡测试封装的测试用例代码,测试被测函数是否非预期死亡。还可以基于当前的生成框架,便捷地扩展其它语法规则来生成不同语言不同形式的用例代码。


图3.7 代码生成方案示意图

4.3.2 完整demo展示

如图3.8所示是一个被测源码exlore_filter函数经过代码分析、用例数据生成后得到测试用例代码的过程样例。

图3.8 测试用例集合demo图

4.4 失败用例分析

基于上一节介绍的代码生成能力,可获得可编译的测试用例代码,通过编译适配模块生成编译命令,执行编译后即可得到可执行的测试程序。如何保证运行测试程序后快速获取失败信息,降低人介入的分析成本,是本节重点介绍的内容。
整个分析过程中可能存在的问题如下:
  1. 可读性差:测试用例失败后,其堆栈/crash不完整,或者无用信息太多。像c/c++语言的gtest死亡测试,用例crash后是无堆栈信息打印出来的,常规方式是通过gdb来获取堆栈内容,当堆栈文件过大超过3G时,读取速度会很慢。
  2. 重复的堆栈/crash
  • 同一函数同一代码行问题重复主要是不同用例之间命中的问题重复

例如,如下场景的find函数,在输入用例为{arr=nullptr,len=1}和{arr=nullptr,len=2}时都会命中sum+=arr[0]这一行的crash。


  • 不同代码行问题重复,主要是代码语义相近导致的问题重复

例如如下场景的两个程序片段A和程序片段B,_dest是类Action的成员变量,会在程序运行的其它阶段被赋值。add_to_dest和get_from_dest分别crash在write_dest->write和read_dest->read行。其代码行内容是不同的,但crash的语义是相同的,都是使用了空指针_dest导致程序crash。

 被测代码片段A
被测代码片段B
3. 定位成本高
对新人或不熟悉堆栈文件的人来说,测试用例代码、CR以及堆栈信息都完备的情况下,依然存在跟进排查无头绪的问题。

4. 修复标准不统一
哪些问题一定要修复、哪些问题可以忽略掉,不同业务线缺少统一的标准。

本文通过堆栈内容存储、堆栈内容分析、去重、失败原因预测以及失败问题分级等手段来解决上述问题,解决思路如图3.89所示,每个阶段细节较多,本文不重点展开介绍。


图3.9 堆栈分析过程

3.5 技术架构

面向业务落地需要考虑如何将工具的能力发挥到合适的阶段,做到恰到好处,结合研发开发习惯,我们考虑了如下两方面因素:
  • 存量问题需要修复周期:业务模块直接扫描,会因历史遗留问题过多而产生较大修复成本,需要一定的时间来消化。
  • 迭代时只需要关注变更影响面:在变更流水线上扫描全量代码,对全量代码生成用例会造成资源浪费以及执行效率低的问题。

基于上述考虑,我们将落地方式划分为两种模式:存量和增量
  • 存量:新接入模块建议先跑全量,扫描存量问题,让研发团队出统一修复负责人,进行统一修复,消除存量隐患。也可以在daily任务或全量回归任务中跑存量扫描模式。
  • 增量:是指只针对变更代码,通过白盒分析手段,分析出其影响的代码范围,如直接影响(改动函数)、间接影响(未改动但逻辑上会有影响),只对影响范围内的函数进行测试。在修改代码提交后,可触发流水线跑增量模式的任务。
这里还可以引入风险考量,评估出函数修改内容是否需要测试,剔除掉无风险函数。

基于上述思路,将代码分析、用例数据生成和代码生成能力集成到 如图3.910所示的技术架构中,和百度内部策略中台、数据中台、可视化平台等能力结合,贯彻 “测试准备、测试执行、测试分析到问题定位” 这四个维度,完成基于单测生成的异常召回工具的建设和落地。

图3.10 落地架构图

部分任务结果如图3.11所示,研发人员本地开发提交代码后自动触发流水线绑定的智能UT测试任务,通过报告可查看到crash问题详情,包括失败原因、堆栈内容等。

图3.11 任务执行展示样例图

四、效果

1. 工程效果:
实践:探索出基于单测解决异常问题的通用方案,已在C/C++语言上落地实践,累计生成千万余行测试代码,其它语言进行中
  • 高覆盖:冷启函数覆盖50%+,分支覆盖20%+
  • 低资源:机器资源消耗同系统级测试相比可忽略
  • 低人耗:自动适配UT及测试代码编译能力,无需人工搭建单测框架和维护
2. 业务效果
  • 落地:覆盖140+重点后端模块、lib库
  • 存量召回:召回存量问题900余例
  • 增量召回:增量召回问题200余例

参考资料
1. cppcheck:https://github.com/danmar/cppcheck
2.Fuzzing:https://baike.baidu-com/item/%E6%A8%A1%E7%B3%8A%E6%B5%8B%E8%AF%95/2848962?fr=aladdin
3. z3:https://github.com/Z3Prover/z3
4. all-pairs_testing: https://en.wikipedia.org/wiki/All-pairs_testing
5. 死亡测试:https://github.com/google/googletest/blob/master/googletest/docs/advanced.md#death-tests
6. traceback:实现思路参考https://github.com/zsummer/traceback
7. address sanitizer:https://github.com/google/sanitizers/tree/master/address-sanitizer
(五折,机会难得,
扫二维码直接去京东购买)

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存