覆盖测试中高效代码插桩技术的研究
摘要：代码插桩是实现覆盖测试的关键技术之一，而高效的插桩技术对于嵌入式软件的测试来说又是至关重要的。文章在对CodeTeST 中插桩技术研究的基础上，以GCC 作为开发平台，应用并实现了新的插装器，采用增加一个词法语法分析器的方法，提高了插桩的效率。经过实验证明新的插装器具有代码膨胀率小，插桩速度块的优点，在一定程度上做到了高效插桩。
引言
在实现覆盖测试的过程中，往往需要知道某些信息，如：程序中可执行语句被执行（即被覆盖）的情况，程序执行的路径，变量的引用、定义等。要想获取这类信息，需要跟踪被测程序的执行过程，或者是由计算机在被测程序执行的过程中自动记录。前者需要人工进行，效率低下且枯燥乏味；后者则需要在被测程序中插入完成相应工作的代码，即代码插桩技术。如今大多数的覆盖测试工具均采用代码插桩技术。
在对普通应用的软件进行测试时，由于现在电脑的配置越来越高，电脑的运行速度越来越快，代码插桩所引起的问题还不是很明显或者说是在可以接受的范围之内。但是对于嵌入式软件来说这却是致命的问题。因为嵌入式软件的系统资源有限（内存较小、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 中将生成的中间代码表达式以一种双向链表的形式组织起来的，在链表中有一些特殊的节点，这些节点记录了程序的结构信息。