周睿

摘 要： 國(guó)內(nèi)的軟件測(cè)試研究目前還基本停留在比較基礎(chǔ)的理論方法和管理方法上，沒(méi)有在軟件測(cè)試技術(shù)上取得突破?；诋?dāng)前流行的Clang編譯器前端，在抽象語(yǔ)法樹(shù)生成的過(guò)程中運(yùn)用不同的規(guī)則標(biāo)識(shí)各語(yǔ)句結(jié)構(gòu)，同時(shí)進(jìn)行中間結(jié)構(gòu)的改造和校正，得到一個(gè)有效的、高正確性的程序結(jié)構(gòu)分析器。程序結(jié)構(gòu)分析器的設(shè)計(jì)為實(shí)現(xiàn)一個(gè)有理論基礎(chǔ)的綜合性白盒測(cè)試工具奠定了堅(jiān)實(shí)的底層數(shù)據(jù)支持。

關(guān)鍵詞： Clang編譯器； 抽象語(yǔ)法樹(shù)； 程序結(jié)構(gòu)分析； 軟件測(cè)試

中圖分類號(hào)：TP311.1 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

程序結(jié)構(gòu)分析器的實(shí)現(xiàn)離不開(kāi)一個(gè)高效的編譯前端作支持，而編譯技術(shù)到目前為止在各領(lǐng)域得到了廣泛的應(yīng)用。從銀行的管理軟件到高性能計(jì)算，大多數(shù)都是高級(jí)語(yǔ)言進(jìn)行編寫(xiě)完成，然后通過(guò)靜態(tài)或動(dòng)態(tài)編譯最終在計(jì)算機(jī)上運(yùn)用。目前比較流行的編譯器是在Apple上使用的LLVM/Clang編譯器、由GNU開(kāi)發(fā)的程序語(yǔ)言編譯器GCC用于Linux系統(tǒng)下編程、IBM公司研制開(kāi)發(fā)的Java編譯器Jikes、Inter公司開(kāi)發(fā)的Open Research Compile，還有常見(jiàn)的MSVC、Borland c、myeclipse和jbuilder等等[3-4]。

程序中的缺陷檢測(cè)是編譯器的一項(xiàng)重要任務(wù)，也是目前研究的熱點(diǎn)和探討的核心問(wèn)題。要識(shí)別各種錯(cuò)誤包括：變量未定義、類型檢驗(yàn)、語(yǔ)義錯(cuò)誤以及內(nèi)存泄漏和違規(guī)等，就必須在程序分析方面投入更多精力進(jìn)行設(shè)計(jì)研究。在保證可靠性和安全性的同時(shí)也要減少分析工具的誤報(bào)，從而避免給程序員帶來(lái)不必要的麻煩，節(jié)約時(shí)間，提高效率。因此，編譯器技術(shù)中靜態(tài)或動(dòng)態(tài)的程序分析對(duì)識(shí)別程序中的錯(cuò)誤和缺陷有著重要的作用，不過(guò)現(xiàn)在面臨的問(wèn)題還不少，出現(xiàn)了許多新的挑戰(zhàn)[5]。

1 clang的靜態(tài)分析器

現(xiàn)有的Clang靜態(tài)分析器已經(jīng)完成了過(guò)程內(nèi)分析（Intra-ProceduralAnalysis）和路徑診斷（Path Diagnostics）兩個(gè)大模塊。其中已實(shí)現(xiàn)的過(guò)程內(nèi)分析功能包括源代碼級(jí)別的控制流圖、流敏感的數(shù)據(jù)流解析器、路徑敏感數(shù)據(jù)流分析引擎、死存儲(chǔ)檢查和接口檢查。而路徑診斷信息模塊已經(jīng)提供路徑診斷客戶端（提供開(kāi)發(fā)新bug報(bào)告的抽象接口、獨(dú)立于生成過(guò)程的可視報(bào)告、HTML診斷報(bào)告）、缺陷報(bào)告器（為前一個(gè)模塊服務(wù)）[6]。

1.1 靜態(tài)分析概述

靜態(tài)分析（static analysis）[1]是指在不執(zhí)行的情況下對(duì)代碼進(jìn)行評(píng)估的過(guò)程。靜態(tài)分析非常強(qiáng)大，這是因?yàn)樗试S對(duì)多種可能性進(jìn)行快速參考量。一個(gè)靜態(tài)分析工具能夠探查大量“如果……將會(huì)……”的假定情況，而不必為所有這些假定進(jìn)行計(jì)算，進(jìn)而執(zhí)行這些代碼。靜態(tài)分析技術(shù)非常適合于識(shí)別安全問(wèn)題。

⑴ 靜態(tài)分析工具徹底而一致地進(jìn)行檢查，而不管程序員的檢查角度和代碼的復(fù)雜程度。

⑵ 通過(guò)對(duì)代碼本身的檢查，靜態(tài)分析工具往往能指出安全問(wèn)題的根源，而不僅僅是指出某種癥狀。

⑶ 靜態(tài)分析能夠在開(kāi)發(fā)早期發(fā)現(xiàn)錯(cuò)誤，甚至，在程序首次運(yùn)行之前就可以發(fā)現(xiàn)。及早發(fā)現(xiàn)錯(cuò)誤，不僅僅減少了修補(bǔ)錯(cuò)誤所付出的費(fèi)用，而且這種快速反饋周期有助于程序的完善。

⑷ 當(dāng)安全研究人員發(fā)現(xiàn)一種新攻擊時(shí)，靜態(tài)分析工具可以很容易地對(duì)大量代碼進(jìn)行重新檢查，從而將了解這種新的攻擊能不能針對(duì)這些代碼而成功實(shí)施。

對(duì)于靜態(tài)分析技術(shù)，最普遍的不滿意見(jiàn)是：這些工具產(chǎn)生太多的無(wú)用信息，尤其是產(chǎn)生太多誤報(bào)（程序中實(shí)際不存在問(wèn)題時(shí)，卻報(bào)告了問(wèn)題）。但是從安全的角度來(lái)看，漏報(bào)（程序中存在問(wèn)題，而安全分析工具卻沒(méi)有報(bào)告這個(gè)問(wèn)題）問(wèn)題更為嚴(yán)重。誤報(bào)的代價(jià)是對(duì)報(bào)告結(jié)果的審查浪費(fèi)時(shí)間，但漏報(bào)的代價(jià)就遠(yuǎn)遠(yuǎn)不止這些。

1.2 靜態(tài)分析路線[7]

靜態(tài)分析工具內(nèi)部的工作流程，包括數(shù)據(jù)結(jié)構(gòu)、分析技術(shù)、規(guī)則以及報(bào)告結(jié)果的方式等，了解這些技術(shù)路線對(duì)于創(chuàng)建自己的靜態(tài)分析工具會(huì)有重要幫助。圖1說(shuō)明了所有針對(duì)安全的靜態(tài)分析工具的工作方式。

2 生成clang項(xiàng)目

2.1 獲取clang

由于clang只是LLVM前端（front-end）的實(shí)例，所以獲取clang時(shí)亦需要獲取LLVM。從LLVM官網(wǎng)www.llvm.org上，可以下載到LLVM 3.0與clang 3.0，對(duì)應(yīng)：

llvm-3.0.tar.gz

clang-3.0.tar.gz

2.2 獲取并安裝cmake

隨LLVM源碼發(fā)布的，并沒(méi)有VS 2010的工程文件，而是需要先使用工具cmake生成其工程文件。從http：//www.cmake.org/上，可以下載到cmake 2.8.6安裝文件：cmake-2.8.6-win32-x86.exe。

3 相關(guān)技術(shù)

3.1 語(yǔ)法樹(shù)解析

在..＼clangLex＼Lexer.cpp文件中對(duì)所有預(yù)處理后的字符進(jìn)行標(biāo)記，并放入緩沖存儲(chǔ)器。一個(gè)標(biāo)記（Token）主要包括：SourceLocation、UintData、Kind、Flags幾個(gè)部分，分別表示標(biāo)記開(kāi)始和結(jié)束的位置、長(zhǎng)度、種類以及指示位。這樣為下面的語(yǔ)法分析打下基礎(chǔ)。

在＼clangParse＼ParseAST.cpp中：

void clang：：ParseAST（Sema &S， bool PrintStats） {

… …

while （！P.ParseTopLevelDecl（ADecl）） {

if （ADecl）

Consumer->HandleTopLevelDecl（ADecl.get（））；

}；

… …

} 是生成抽象語(yǔ)法樹(shù)和結(jié)構(gòu)分析的代碼關(guān)鍵部分

在分析過(guò)程中程序的開(kāi)始處..＼tools＼clang＼tools＼

driver＼driver.cpp文件中的main函數(shù)，設(shè)置在項(xiàng)目clang的屬性—配置屬性—調(diào)試中的命令參數(shù)為-c 文件路徑。但是這個(gè)命令跟蹤后不能到達(dá)語(yǔ)法分析的真正代碼處，不方便直接進(jìn)行單步調(diào)試，需要進(jìn)行命令轉(zhuǎn)換。首先將斷點(diǎn)加在Res=TheDriver.ExecuteCompilation（*C， FailingCommand）語(yǔ)句處開(kāi)始單步跟蹤，直到＼lib＼Support＼Windows＼Program.inc文件中的BOOL rc=CreateProcess（path.c_str（），command，NULL，NULL，TRUE， 0，envblock，NULL， &si， &pi）語(yǔ)句處，參數(shù)command中的命令才是真正需要的，形如-cc1 -triple i686-pc-win32 -emit-obj，通過(guò)這個(gè)命令我們就可以對(duì)clang編譯器進(jìn)行跟蹤調(diào)試。

其他主要的調(diào)試命令：

-cc1 -ast-dump-xml 文件路徑（語(yǔ)法樹(shù)與XML格式輸出）

-cc1 -print-stats 文件路徑（得到語(yǔ)法分析后的匯總信息）

-E 文件路徑（獲得預(yù)處理文件）

-S 文件路徑（獲得匯編代碼）

-o 文件路徑（獲得可執(zhí)行文件）

3.2 預(yù)處理器的設(shè)計(jì)

編譯器提供的預(yù)處理器，在預(yù)處理完成后，已經(jīng)使得程序的很多信息丟失了，例如某一個(gè)block塊在展開(kāi)后就無(wú)法知道這個(gè)塊在源文件中的精確位置信息，這樣不滿足設(shè)計(jì)的要求，因?yàn)樵趯?duì)被測(cè)試程序進(jìn)行分析時(shí)，只存儲(chǔ)一些重要結(jié)構(gòu)的統(tǒng)計(jì)信息，并不存儲(chǔ)任何源代碼，只存儲(chǔ)一些block塊或者函數(shù)的絕對(duì)位置信息，當(dāng)用戶采用視圖查看程序的時(shí)候，代碼都是動(dòng)態(tài)加載的。因此需要一個(gè)滿足我們要求的預(yù)處理器，該預(yù)處理器除了能夠按照預(yù)處理規(guī)則和預(yù)定義符號(hào)對(duì)源碼進(jìn)行展開(kāi)外，還需要通過(guò)特定的宏來(lái)對(duì)元素的精確位置進(jìn)行矯正。

4 總體設(shè)計(jì)

得到了分析器的需求信息后，需要對(duì)分析器系統(tǒng)進(jìn)行總體的結(jié)構(gòu)設(shè)計(jì)，主要包括文件、類、函數(shù)以及變量的結(jié)構(gòu)分析。

⑴ 文件的結(jié)構(gòu)分析

文件的結(jié)構(gòu)分析主要包括類、函數(shù)、全局變量、靜態(tài)變量、文件中包含的塊，以及空白行、注釋行等相關(guān)信息的統(tǒng)計(jì)。

⑵ 類的結(jié)構(gòu)分析

類的結(jié)構(gòu)分析主要包括對(duì)基類、友元類、友元函數(shù)、注釋和空白行等信息的統(tǒng)計(jì)，還有私有變量、共有變量、受保護(hù)變量、私有函數(shù)、共有函數(shù)、受保護(hù)函數(shù)、構(gòu)造函數(shù)，以及析構(gòu)函數(shù)的名稱和類型的記錄。

⑶ 函數(shù)的結(jié)構(gòu)分析

函數(shù)的結(jié)構(gòu)分析主要包括函數(shù)的調(diào)用關(guān)系、變量的引用、修改和使用，以及復(fù)雜度、注釋行、可見(jiàn)段，函數(shù)中所包含的條件和分支的計(jì)算與統(tǒng)計(jì)。

⑷ 變量的結(jié)構(gòu)分析

變量的結(jié)構(gòu)分析主要包括變量名稱、類型、變量所在文件的路徑和所在類的記錄。

將分析結(jié)果呈現(xiàn)在用戶界面上，如圖2所示。

5 總結(jié)

本文對(duì)程序結(jié)構(gòu)分析器國(guó)內(nèi)外研究現(xiàn)狀進(jìn)行了較為深入的分析，著重對(duì)現(xiàn)有的結(jié)構(gòu)分析器核心技術(shù)進(jìn)行了研究，探討了存在的不足以及需要解決的問(wèn)題。提出了一個(gè)更有效、可靠的基于源碼的程序結(jié)構(gòu)分析器，分別從文件、類、函數(shù)、變量四個(gè)方面完成了整個(gè)結(jié)構(gòu)分析器的設(shè)計(jì)。為軟件測(cè)試?yán)碚摰綄?shí)踐的應(yīng)用打下了一個(gè)堅(jiān)實(shí)的基礎(chǔ)。本文的設(shè)計(jì)也是研發(fā)白盒測(cè)試工具的核心部分，為了使大規(guī)模的程序結(jié)構(gòu)分析更為實(shí)用、有效，今后還需要在方法上進(jìn)行適度的改進(jìn)和完善。

參考文獻(xiàn)（References）：

[1] [美]魯?shù)轮糯簌i等譯編.編程邏輯與結(jié)構(gòu)化程序設(shè)計(jì)[M].

水利水電出版社，2004.

[2] 張海藩，牟永敏.面向?qū)ο蟪绦蛟O(shè)計(jì)實(shí)用教程[M].清華大學(xué)出

版社，2001.

[3] 劉磊.程序分析技術(shù)[M].機(jī)械工業(yè)出版社，2005.

[4] 馬瑞新.基礎(chǔ)c++程序分析與設(shè)計(jì)[M].大連理工大學(xué)出版社，

2007.

[5] 劉宇君，C++程序設(shè)計(jì)案例分析[M].北京：清華大學(xué)出版社，

2011.

[6] 章磊.Clang上的C/C++過(guò)程間分析和漏洞發(fā)掘[D].中國(guó)科

學(xué)技術(shù)大學(xué)，2009.

[7] 楊宇，張健.程序靜態(tài)分析技術(shù)與工具[J].計(jì)算機(jī)科學(xué)，

2004.2.