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

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）插桩策略：

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

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

分支覆