基于Clang編譯器的程序結構分析器設計

周睿

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

關鍵詞： 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 引言

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

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

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

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

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

靜態(tài)分析（static analysis）[1]是指在不執(zhí)行的情況下對代碼進行評估的過程。靜態(tài)分析非常強大，這是因為它允許對多種可能性進行快速參考量。一個靜態(tài)分析工具能夠探查大量“如果……將會……”的假定情況，而不必為所有這些假定進行計算，進而執(zhí)行這些代碼。靜態(tài)分析技術非常適合于識別安全問題。

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

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

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

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

對于靜態(tài)分析技術，最普遍的不滿意見是：這些工具產生太多的無用信息，尤其是產生太多誤報（程序中實際不存在問題時，卻報告了問題）。但是從安全的角度來看，漏報（程序中存在問題，而安全分析工具卻沒有報告這個問題）問題更為嚴重。誤報的代價是對報告結果的審查浪費時間，但漏報的代價就遠遠不止這些。

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

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

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源碼發(fā)布的，并沒有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函數(shù)，設置在項目clang的屬性—配置屬性—調試中的命令參數(shù)為-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）語句處，參數(shù)command中的命令才是真正需要的，形如-cc1 -triple i686-pc-win32 -emit-obj，通過這個命令我們就可以對clang編譯器進行跟蹤調試。

其他主要的調試命令：

-cc1 -ast-dump-xml 文件路徑（語法樹與XML格式輸出）

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

-E 文件路徑（獲得預處理文件）

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

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

3.2 預處理器的設計

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

4 總體設計

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

⑴ 文件的結構分析

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

⑵ 類的結構分析

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

⑶ 函數(shù)的結構分析

函數(shù)的結構分析主要包括函數(shù)的調用關系、變量的引用、修改和使用，以及復雜度、注釋行、可見段，函數(shù)中所包含的條件和分支的計算與統(tǒng)計。

⑷ 變量的結構分析

變量的結構分析主要包括變量名稱、類型、變量所在文件的路徑和所在類的記錄。

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

5 總結

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

參考文獻（References）：

[1] [美]魯?shù)轮?，杜大鵬等譯編.編程邏輯與結構化程序設計[M].

水利水電出版社，2004.

[2] 張海藩，牟永敏.面向對象程序設計實用教程[M].清華大學出

版社，2001.

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

[4] 馬瑞新.基礎c++程序分析與設計[M].大連理工大學出版社，

2007.

[5] 劉宇君，C++程序設計案例分析[M].北京：清華大學出版社，

2011.

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

學技術大學，2009.

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

2004.2.