覆盖测试中高效代码插桩技术的研究

　　引言

　　在实现覆盖测试的过程中，往往需要知道某些信息，如：程序中可执行语句被执行（即被覆盖）的情况，程序执行的路径，变量的引用、定义等。要想获取这类信息，需要跟踪被测程序的执行过程，或者是由计算机在被测程序执行的过程中自动记录。前者需要人工进行，效率低下且枯燥乏味；后者则需要在被测程序中插入完成相应工作的代码，即代码插桩技术。如今大多数的覆盖测试工具均采用代码插桩技术。

　　在对普通应用的软件进行测试时，由于现在电脑的配置越来越高，电脑的运行速度越来越快，代码插桩所引起的问题还不是很明显或者说是在可以接受的范围之内。但是对于嵌入式软件来说这却是致命的问题。因为嵌入式软件的系统资源有限（内存较小、I/O 通道较少等），过大的代码膨胀率将使得程序不能在嵌入式系统中运行；同时嵌入式软件通常具有很强的实时性，程序的输出只在有限的时间内有效，迟到的“正确的”结果是无用的甚至会变成错误的、有害的。

　　代码插桩技术会破坏程序的时间特性等，导致软件执行的错误。因此我们需要更高效的代码插桩技术来完成覆盖测试，尤其是嵌入式软件的覆盖测试。

　　1 插桩技术概述

　　程序插桩技术最早是由J.C. Huang 教授提出的, 它是在保证被测程序原有逻辑完整性的基础上在程序中插入一些探针（又称为“探测仪”），通过探针的执行并抛出程序运行的特征数据，通过对这些数据的分析，可以获得程序的控制流和数据流信息，进而得到逻辑覆盖等动态信息，从而实现测试目的的方法。

　　1.1 插桩方式比较

　　由于程序插桩技术是在被测程序中插入探针，然后通过探针的执行来获得程序的控制流和数据流信息，以此来实现测试的目的。因此，根据探针插入的时间可以分为目标代码插桩和源代码插桩。

　　（1）目标代码插桩的前提是对目标代码进：

　　行必要的分析以确定需要插桩的地点和内容。由于目标代码的格式主要和操作系统相关，和具体的编程语言及版本无关，所以得到了广泛的应用，尤其是在需要对内存进行监控的软件中。但是由于目标代码中语法、语义信息不完整，而插桩技术需要对代码词法语法的分析有较高的要求，故在覆盖测试工具中多采用源代码插桩。

　　（2）源代码插桩是在对源文件进行完整的：

　　词法分析和语法分析的基础上进行的，这就保证对源文件的插桩能够达到很高的准确度和针对性。但是源代码插桩需要接触到源代码，使得工作量较大，而且随着编码语言和版本的不同需要做一定的修改。在后面我们所提到的程序插桩均指源代码插桩。

　　2 程序插桩技术的研究

　　众多的覆盖测试工具中都采用了程序插桩技术，但是各有各的优缺点，而市场上认为比较好的嵌入式测试工具有CodeTest，使用CodeTest工具插装进行测试对目标程序的影响在1%到15%之间。下面对CodeTest 的插桩技术进行的分析。

　　2.1 CodeTest 工具的插桩技术分析

　　Codetest 的插桩过程简单来说分为两步：

　　（1）对源代码进行预编译；被测程序首先会通过CodeTest 的编译驱动器调用程序的原编译器进行预编译，通常是进行宏替换。

　　（2）对预编译后的文件进行插桩，生成插桩后的.C 文件和.IDB 的插桩符号数据库文件；预编译完成后，CodeTest的插装器（即源代码分析程序）据不同的参数对预编译后的源代码进行相应方式的自动插桩，即在需要插桩的位置写入一条赋值语句（如：amc_ctrl=0x74100010）,并把插入的标记送入数据库文件中生成一个符号数据库暂存起来，为以后的分析时调用。然后，CodeTest的编译驱动器会调用原编译器对插桩后的代码进行编译生成可执行目标代码送到目标板上运行。当程序在目标系统运行到插桩点的位置时，目标板的控制总线和地址总线上会出现相应的控制信号和地址信号。当 CodeTest的辅助硬件（信号捕获探头）从控制总线和地址总线上监视到符合以上条件的信号时，CodeTest会主动地从数据总线上把数据捕获回来送到CodeTest的内存中暂存并对这些数据进行预处理，然后将预处理后的数据通过局域网送到工作平台上。通过与前面生成的符号数据库中的数据进行比较，我们就此得知当前程序的运行状态，借此完成对嵌入式软件的性能分析，高级覆盖率分析，内存分析和大容量的代码跟踪。

 　　CodeTest是一个硬件辅助软件的测试与分析工具，它吸取软件打点技术，并对这种技术进行了改善，纯软件工具插入的是一个函数，而 CodeTest插入的是一条赋值语句，它在汇编级也是一条语句，所以它执行的时间非常短，占用的空间也非常少，同时避免了被其它的中断所中断，所以它对目标系统的影响非常小（1%-15%）。

　　2.2 程序插桩的切入点

　　CodeTest 作为一种商品，很多技术不对外公开 ，但是我们仍可以明白其插桩的原理，进而以此为参考对插桩技术做进一步的研究；在国内，虽有很多工具使用了插桩技术，但是都不够高效， 为了方便研究我们选择GCC 作为插桩技术研究的平台。

　　GCC 是一个高度优化，高度可移植，且广泛使用的编译系统。它能处理多种语言，包括C/C++、Fortran、Java、Ada 等多种语言前端，而且后端几乎支持所有的处理器结构。同时GCC作为源码开放的软件，可以自由修改和使用。

图1 是GCC 增加插桩阶段后的编译流程。

　　GCC 编译器的工作流程大致可以分为前端、中端和后端。中端Gimple 层是高版本GCC 中新增加的，是用来对经过词法、语法分析后的程序进行优化和整理的阶段，我们这里可以暂时忽略这个阶段。前端包括预处理和词法、语法分析。

　　预处理通常是做宏替换处理。词法、语法分析的输入是预处理后的文件，输出是AST ，AST 经过优化后产生Gimple Tree，然后交给RTL 模块去处理。RTL（Register Transfer Language）是一种中间语言，作为编译器工作的后端，是GCC内部使用的一种能对实际体系结构作抽象的，与硬件无关的语言。在GCC 中将生成的中间代码表达式以一种双向链表的形式组织起来的，在链表中有一些特殊的节点，这些节点记录了程序的结构信息。

　　GCC 编译器前端的工作完成后，词法语法分析器已经识别完程序的所有特征，因此将词法、语法分析至Gimple 这个阶段作为代码插桩的切入点是完全可行的。然后，GCC 利用中间代码生成会汇编代码时，如果扫描到RTL 中的特殊节点就会根据用户的需要适当的插入一些完成信息采集功能的汇编代码行，从而就可以实现代码插桩。但是这种做法有两个缺点：一是代码的插桩和编译器的结合很紧密，并且在汇编代码的生成过程中需要针对不同的CPU 生成不同的汇编代码，与CPU 的关联性很强，不便于移植；而是，当程序很大时，探针的植入会造成代码的膨胀，及进行信息采集的代码的插入就需要很多时间。

　　由于代码插桩技术中插桩点识别过程中的词法、语法分析只需要识别有限的程序结构特征即可，而对程序中所有的词法语法进行分析是因为由中间代码生成汇编代码时，需要以词法语法分析作为基础，识别出所有的程序结构特征。由此可以知道满足插桩技术要求的词法语法分析器可以比中间代码生成的词法语法分析器简单。生成满足插桩点识别的词法语法分析器的词法语法分析程序的输入为预处理后的源代码文件，输出是插桩后的源代码文件（如图1 所示的灰色部分）。由于新增加的词法语法分析程序仅仅是针对插桩所需识别的词法、语法进行分析，故而需要植入的探针比较少，代码膨胀率自然减小，插桩速度加快，进而整个编译过程就会加快。

　　2.3 插桩程序的设计

　　探针的设计解决了插桩内容的问题，而插桩程序的设计是用来确定插桩位置和插桩策略的，即回答“在哪插”和“如何插”的问题。

　　（1）插桩位置：

　　探针的植入要做到紧凑精干，才能保证在做到收集的信息全面而无冗余，减少代码的膨胀率。因此，在确定插桩位置时，要将程序划分，基本的划分方法是基于“块”结构。

　　按照块结构的划分，探针的植入位置有以下几种情况：

　　a. 程序的第一条语句；b. 分支语句的开始；c. 循环语句的开始；d. 下一个入口语句之前的语句；e. 程序的结束语句；f. 分支语句的结束；g. 循环语句的结束；除此之外，根据覆盖测试要求的不同，插桩的位置除了上面所说的几种情况外，也会随着覆盖测试要求的不同有所变化。

　　（2）插桩策略：

　　插桩策略是解决“如何插”的问题。传统的插桩策略是在所有需要插桩的位置插入探针，在程序运行过程收集所有可能用到得程序信息，将其写入数据库进行分析和处理。这种方法对于大型的程序来说，将会造成相当大的工作量，效率很低，且会造成很大的代码膨胀率。而我们会根据不同的测试要求，每次插入不同的探针，采用相应的插桩策略，这样就减少了代码的膨胀率，保证了程序执行的效率。下面简单介绍几种探针的插桩策略。

　　语句覆盖探针（基本块探针）：在基本块的入口和出口处，分别植入相应的探针，以确定程序执行时该基本块是否被覆盖。

　　分支覆盖探针：C/C++语言中，分支由分支点确定。对于每个分支，在其开始处植入一个相应的探针，以确定程序执行时该分支是否被覆盖。

　　条件覆盖探针：C/C++语言中，if, swich,while, do-while, for 几种语法结构都支持条件判定，在每个条件表达式的布尔表达式处植入探针，进行变量跟踪取值，以确定其被覆盖情况。

　　根据不同测试要求采用不用的插桩策略，每次在不同的位置植入相应的探针，使得每次只是植入有限的探针，这就更大大减少了代码的膨胀率和插桩的速度。

　　3 实验

　　本文采用了一个 1000 行的程序作为被测程序，分别采用使用整体插桩的工具和我们自己开发的工具进行测试，结果发现前者插桩的时间和代码膨胀率分别为3s 和35%，后者插桩的平均时间和平均的代码膨胀率为1s 和8%，插桩时间得到明显提升，代码膨胀率明显减少。

　　采用以上的程序插桩技术，除了常用的覆盖测试策略外，我们还可以实现MC/DC 和LCSAJ 测试。

　　4 结束语

　　本文详细介绍了覆盖测试中的高效代码插桩技术，由此可以看出在实际中覆盖测试分析采用的覆盖策略的多样性决定了程序插桩时需要识别程序的特征的复杂性。同时在软件覆盖测试工具的开发中，如果从软件的分析开始，就有合理的程序划分、适当的选定插桩位置和插桩策略，就可以满足多种测试要求，使得测试能够合理又快速的实现。如果再加上自动化测试工具的支持，那就可以大大提高测试的效率。