周睿
摘 要： 国内的软件测试研究目前还基本停留在比较基础的理论方法和管理方法上，没有在软件测试技术上取得突破。基于当前流行的Clang编译器前端，在抽象语法树生成的过程中运用不同的规则标识各语句结构，同时进行中间结构的改造和校正，得到一个有效的、高正确性的程序结构分析器。程序结构分析器的设计为实现一个有理论基础的综合性白盒测试工具奠定了坚实的底层数据支持。
关键词： Clang编译器； 抽象语法树； 程序结构分析； 软件测试
中图分类号：TP311.1 文献标志码：A 文章编号：1006-8228（2016）10-54-03
Design of program structure analyzer based on Clang compiler
Zhou Rui
（Shaanxi institute of technology， Xi'an， Shaanxi 710300， China）
Abstract： At present， the research of software testing in China is still in the basic stage of theoretical methods and management methods， and it has not made any breakthrough in the software testing technology. Based on the front end of current popular Clang compiler， using different rules to identify the structure of statement in the abstract syntax tree generation process， and to carry out the reform and correction of the intermediate structure， an effective program structure analyzer with high accuracy is obtained. The design of program structure analyzer lays a solid underlying data support for realizing a theory based comprehensive white box testing tool.
Key words： Clang compiler； abstract syntax tree； program structure analysis； software testing
0 引言
程序结构分析器的实现离不开一个高效的编译前端作支持，而编译技术到目前为止在各领域得到了广泛的应用。从银行的管理软件到高性能计算，大多数都是高级语言进行编写完成，然后通过静态或动态编译最终在计算机上运用。目前比较流行的编译器是在Apple上使用的LLVM/Clang编译器、由GNU开发的程序语言编译器GCC用于Linux系统下编程、IBM公司研制开发的Java编译器Jikes、Inter公司开发的Open Research Compile，还有常见的MSVC、Borland c、myeclipse和jbuilder等等[3-4]。
程序中的缺陷检测是编译器的一项重要任务，也是目前研究的热点和探讨的核心问题。要识别各种错误包括：变量未定义、类型检验、语义错误以及内存泄漏和违规等，就必须在程序分析方面投入更多精力进行设计研究。在保证可靠性和安全性的同时也要减少分析工具的误报，从而避免给程序员带来不必要的麻烦，节约时间，提高效率。因此，编译器技术中静态或动态的程序分析对识别程序中的错误和缺陷有着重要的作用，不过现在面临的问题还不少，出现了许多新的挑战[5]。
1 clang的静态分析器
现有的Clang静态分析器已经完成了过程内分析（Intra-ProceduralAnalysis）和路径诊断（Path Diagnostics）两个大模块。其中已实现的过程内分析功能包括源代码级别的控制流图、流敏感的数据流解析器、路径敏感数据流分析引擎、死存储检查和接口检查。而路径诊断信息模块已经提供路径诊断客户端（提供开发新bug报告的抽象接口、独立于生成过程的可视报告、HTML诊断报告）、缺陷报告器（为前一个模块服务）[6]。
1.1 静态分析概述
静态分析（static analysis）[1]是指在不执行的情况下对代码进行评估的过程。静态分析非常强大，这是因为它允许对多种可能性进行快速参考量。一个静态分析工具能够探查大量“如果……将会……”的假定情况，而不必为所有这些假定进行计算，进而执行这些代码。静态分析技术非常适合于识别安全问题。
⑴ 静态分析工具彻底而一致地进行检查，而不管程序员的检查角度和代码的复杂程度。
⑵ 通过对代码本身的检查，静态分析工具往往能指出安全问题的根源，而不仅仅是指出某种症状。
⑶ 静态分析能够在开发早期发现错误，甚至，在程序首次运行之前就可以发现。及早发现错误，不仅仅减少了修补错误所付出的费用，而且这种快速反馈周期有助于程序的完善。
⑷ 当安全研究人员发现一种新攻击时，静态分析工具可以很容易地对大量代码进行重新检查，从而将了解这种新的攻击能不能针对这些代码而成功实施。
对于静态分析技术，最普遍的不满意见是：这些工具产生太多的无用信息，尤其是产生太多误报（程序中实际不存在问题时，却报告了问题）。但是从安全的角度来看，漏报（程序中存在问题，而安全分析工具却没有报告这个问题）问题更为严重。误报的代价是对报告结果的审查浪费时间，但漏报的代价就远远不止这些。
1.2 静态分析路线[7]
静态分析工具内部的工作流程，包括数据结构、分析技术、规则以及报告结果的方式等，了解这些技术路线对于创建自己的静态分析工具会有重要帮助。图1说明了所有针对安全的静态分析工具的工作方式。
2 生成clang项目
2.1 获取clang
由于clang只是LLVM前端（front-end）的实例，所以获取clang时亦需要获取LLVM。从LLVM官网www.llvm.org上，可以下载到LLVM 3.0与clang 3.0，对应：
llvm-3.0.tar.gz
clang-3.0.tar.gz
2.2 获取并安装cmake
随LLVM源码发布的，并没有VS 2010的工程文件，而是需要先使用工具cmake生成其工程文件。从http：//www.cmake.org/上，可以下载到cmake 2.8.6安装文件：cmake-2.8.6-win32-x86.exe。
3 相关技术
3.1 语法树解析
在..＼clangLex＼Lexer.cpp文件中对所有预处理后的字符进行标记，并放入缓冲存储器。一个标记（Token）主要包括：SourceLocation、UintData、Kind、Flags几个部分，分别表示标记开始和结束的位置、长度、种类以及指示位。这样为下面的语法分析打下基础。
在＼clangParse＼ParseAST.cpp中：
void clang：：ParseAST（Sema &S， bool PrintStats） {
… …
while （！P.ParseTopLevelDecl（ADecl）） {
if （ADecl）
Consumer->HandleTopLevelDecl（ADecl.get（））；
}；
… …
} 是生成抽象语法树和结构分析的代码关键部分
在分析过程中程序的开始处..＼tools＼clang＼tools＼
driver＼driver.cpp文件中的main函数，设置在项目clang的属性—配置属性—调试中的命令参数为-c 文件路径。但是这个命令跟踪后不能到达语法分析的真正代码处，不方便直接进行单步调试，需要进行命令转换。首先将断点加在Res=TheDriver.ExecuteCompilation（*C， FailingCommand）语句处开始单步跟踪，直到＼lib＼Support＼Windows＼Program.inc文件中的BOOL rc=CreateProcess（path.c_str（），command，NULL，NULL，TRUE， 0，envblock，NULL， &si， &pi）语句处，参数command中的命令才是真正需要的，形如-cc1 -triple i686-pc-win32 -emit-obj，通过这个命令我们就可以对clang编译器进行跟踪调试。
其他主要的调试命令：
-cc1 -ast-dump-xml 文件路径（语法树与XML格式输出）
-cc1 -print-stats 文件路径（得到语法分析后的汇总信息）
-E 文件路径（获得预处理文件）
-S 文件路径（获得汇编代码）
-o 文件路径（获得可执行文件）
3.2 预处理器的设计
编译器提供的预处理器，在预处理完成后，已经使得程序的很多信息丢失了，例如某一个block块在展开后就无法知道这个块在源文件中的精确位置信息，这样不满足设计的要求，因为在对被测试程序进行分析时，只存储一些重要结构的统计信息，并不存储任何源代码，只存储一些block块或者函数的绝对位置信息，当用户采用视图查看程序的时候，代码都是动态加载的。因此需要一个满足我们要求的预处理器，该预处理器除了能够按照预处理规则和预定义符号对源码进行展开外，还需要通过特定的宏来对元素的精确位置进行矫正。
4 总体设计
得到了分析器的需求信息后，需要对分析器系统进行总体的结构设计，主要包括文件、类、函数以及变量的结构分析。
⑴ 文件的结构分析
文件的结构分析主要包括类、函数、全局变量、静态变量、文件中包含的块，以及空白行、注释行等相关信息的统计。
⑵ 类的结构分析
类的结构分析主要包括对基类、友元类、友元函数、注释和空白行等信息的统计，还有私有变量、共有变量、受保护变量、私有函数、共有函数、受保护函数、构造函数，以及析构函数的名称和类型的记录。
⑶ 函数的结构分析
函数的结构分析主要包括函数的调用关系、变量的引用、修改和使用，以及复杂度、注释行、可见段，函数中所包含的条件和分支的计算与统计。
⑷ 变量的结构分析
变量的结构分析主要包括变量名称、类型、变量所在文件的路径和所在类的记录。
将分析结果呈现在用户界面上，如图2所示。
5 总结
本文对程序结构分析器国内外研究现状进行了较为深入的分析，着重对现有的结构分析器核心技术进行了研究，探讨了存在的不足以及需要解决的问题。提出了一个更有效、可靠的基于源码的程序结构分析器，分别从文件、类、函数、变量四个方面完成了整个结构分析器的设计。为软件测试理论到实践的应用打下了一个坚实的基础。本文的设计也是研发白盒测试工具的核心部分，为了使大规模的程序结构分析更为实用、有效，今后还需要在方法上进行适度的改进和完善。
参考文献（References）：
[1] [美]鲁德著，杜大鹏等译编.编程逻辑与结构化程序设计[M].
水利水电出版社，2004.
[2] 张海藩，牟永敏.面向对象程序设计实用教程[M].清华大学出
版社，2001.
[3] 刘磊.程序分析技术[M].机械工业出版社，2005.
[4] 马瑞新.基础c++程序分析与设计[M].大连理工大学出版社，
2007.
[5] 刘宇君，C++程序设计案例分析[M].北京：清华大学出版社，
2011.
[6] 章磊.Clang上的C/C++过程间分析和漏洞发掘[D].中国科
学技术大学，2009.
[7] 杨宇，张健.程序静态分析技术与工具[J].计算机科学，
2004.2.
