大規?？勺僀代碼增量式分析方法

石劍君 劉法旺 計衛星 楊玚

摘 要：提出一種基于頭文件復用的大規?？勺僀代碼增量式分析方法。以Linux內核代碼為例，首先統計和分析了大規模C代碼中的頭文件包含情況。然后根據頭文件包含順序，構建C代碼分析的頭文件加載樹。最后，按照頭文件加載樹增量地分析C代碼。實驗結果表明，與原有的代碼分析方法相比，本方法可以極大地提升大規?？勺僀代碼分析的效率。

關鍵詞：大規模C代碼;可變代碼;代碼分析

中圖分類號：V211 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2021.03.023

本文著錄格式：石劍君，劉法旺，計衛星，等.大規?？勺僀代碼增量式分析方法[J].軟件，2021，42（03）：079-085

Incremental Parsing Method for Large-scale Variable C Source Code

SHI Jianjun1， LIU Fawang2， JI Weixing1， YANG Yang3

（1.School of Computer Science， Beijing Institute of Technology， Beijing? 100081;

2.Ministry of Industry and Information Technology Equipment Industry Development Center， Beijing? 100846;

3.China Software Testing Center， Beijing? 100086）

【Abstract】：An incremental code parsing technique for large-scale variable C source code is proposed. Taking the Linux kernel source code as an example， firstly， we summarize and analyze the included header files in large-scale C source code. Then， header file loading trees are built according to the inclusion order of header files. Finally， the C source code is parsed incrementally based on the header file loading trees. The experimental results show that compared with the traditioanl code parsing methods， our method can greatly improve the efficiency of large-scale variable C source code parsing.

【Key words】：large-scale C source code;variable code;code parsing

目前，大規模C程序已廣泛存在于實際生產實踐中，例如，Linux 內核、Apache HTTP Server和Mozilla Firefox等程序的代碼規模已超過百萬行，甚至達到幾千萬行。相比于普通程序，大規模C程序的開發、管理和維護都變得更加困難。

為了對程序進行優化，自動發現程序中存在的潛在問題，研究人員提出了靜態分析和動態分析等程序分析技術[1-2]。靜態程序分析是程序分析中一種有效的技術手段，它主要指在不運行程序的情況下，從源代碼中提取程序的結構化信息，再進行進一步分析和處理。通過靜態程序分析，開發人員可以在開發階段即可發現代碼中存在的潛在問題，從而實現代碼優化、缺陷檢測和修復，提升程序開發的效率。靜態程序分析通常需要借助于編譯器前端工具解析源代碼，首先通過預處理、詞法分析和語法分析等步驟，從源代碼或者中間代碼中提取出抽象語法樹、函數調用圖和控制流圖等，再利用抽象解釋[3]、數據流分析[4]和符號執行[5]等方法對源代碼進行分析。

然而，大規模C程序的靜態代碼解析過程面臨諸多挑戰：（1）C程序中廣泛存在頭文件包含、宏定義和條件編譯等預處理指令，增加了代碼的可變性，代碼解析的難度也隨之增大;（2）大規模C程序的規模龐大，代碼解析的開銷較大。例如，Linux內核的源代碼規模已超過2700萬行，對如此龐大規模的代碼進行解析，將面臨巨大的時間和空間開銷。盡管研究人員提出很多可用于C程序靜態源代碼解析的工具，然而卻難以直接用于大規模C代碼分析的過程中。

本文提出一種基于頭文件復用的大規模C代碼增量式解析方法，用于解析含有可變代碼的大規模C代碼。該解析方法主要通過分析大規模代碼中頭文件的復用情況，構建出用于代碼解析的頭文件加載樹，按照頭文件加載順序解析C代碼，無需重復解析大量頭文件，從而提升了大規模C代碼解析的效率。

1 可變代碼解析

為了使程序具有較好的可讀性和可維護性，能夠在不同的軟硬平臺上編譯運行，C程序中通常包含了大量的宏定義和條件編譯等預處理指令。在C程序編譯時，編譯器首先完成宏替換，并根據條件編譯的不同分支，選擇相應的代碼塊進行編譯，從而生成不同的目標程序。在C程序中，這些預處理指令控制了代碼的可變性（Variability），因此，包含了預處理指令的代碼也稱為可變代碼或可配置代碼。

C程序的編譯過程包含預處理、詞法分析、語法分析、中間代碼生成、代碼優化和目標代碼生成等環節，其中，程序靜態分析主要關注中間代碼生成之前的過程，即編譯器前端的執行過程。預處理階段主要對源文件中的頭文件包含、宏定義和條件編譯等預處理部分進行處理。詞法分析階段的任務是對輸入符號串形式的源程序進行處理，依次掃描源程序中的每個字符，識別出源程序中有獨立意義的語言單詞，最后輸出token流。語法分析是依據語言的語法規則，對詞法分析結果進行語法檢查，通常語法分析的結果是一個抽象語法樹，是源碼的一種中間表示形式。

本文關注的靜態代碼解析過程與編譯器前端分析過程的不同在于：對于給定的具有可變性的C程序源代碼，編譯器在進行前端分析時只是根據預設的宏定義對部分源代碼進行處理，所生成的目標代碼中并沒有考慮條件宏的所有定義。本文所提出的代碼分析方法則關注C代碼中可變代碼的解析，即在代碼解析的過程中，需要解析不同編譯條件下的所有代碼。如圖1所示的Linux kernel v3.19中的一段代碼，如果CONFIG_CMA已經被定義，則編譯器會選擇1040行和1041行#ifdef和#else之間的代碼進行編譯;否則會選擇1043行#else和#endif之間的代碼進行編譯。然而為了支持代碼審查，幫助開發人員走讀代碼，理解源碼結構和內容，以及對代碼進行可視化，可變代碼分析需要解析1039到1044行之間的所有代碼，需要同時考慮CONFIG_CMA定義和未定義兩種情況?，F有的編譯器在遇到條件編譯時只選擇其中的一個條件分支進行編譯，無法支持可變代碼的分析，因此需要設計特定的工具支持可變代碼的分析。

圖2展示了一段簡單的可變C代碼的解析過程。該代碼在#ifdef A條件成立時，執行“#define X 4”。否則，則執行“#define X 5”。在該可變代碼的解析過程中，主要包含詞法分析、語法分析和處理系統三個部分。其中，第一部分是可以分析條件編譯指令的詞法分析器，其作用是將代碼片段轉為帶有條件的token流。對于上述示例生成的token流中，在#ifdef A之后的所有token都會帶有一個條件A的標簽，直到相應的#endif結束。對于條件#ifdef A和#ifdef B嵌套的情況，token中的條件標簽就會使用 A∧B這樣的標識。對于#if ? #elif ? #else ? #endif也會有相應的條件標簽標識。對于圖2中的輸入程序“2*3+X”，經過詞法分析得到的token流為“2·*·3·+·4A·5?A”。第二部分是語法分析，其目標是根據詞法輸出的token流生成可以標識編譯條件的抽象語法樹，如圖2中語法分析所生成的抽象語法樹。語法分析器基于帶有條件標簽的token流進行分析，產生選擇結點，用?來標識，其中左子樹代表定義 A的解析結果，右子樹代表沒有定義A的情況。第三部分是可以解析帶有條件分支的抽象語法樹的分析器，可以對抽象語法樹做進一步解析處理。

對使用了大量編譯預處理指令的C語言程序進行分析是C程序分析和應用過程中面臨的重點問題之一。例如，在C程序代碼重構的過程中，需要保證不同條件編譯分支的代碼都得到正確處理[6]。另外，目前很多集成開發環境如Visual Studio等都提供了即時語法檢查的功能，能夠在用戶輸入代碼的同時對代碼進行全面的分析和檢測，如果輸入代碼包含了條件編譯指令，則應盡可能地檢測出不同分支的具體問題[7]。以上這些應用場景要求建立一個能夠分析可變性代碼的代碼分析工具。

2 相關工作

目前常用的靜態分析工具如GCC[8]、GNU Cflow[9]和Clang[10]等，這些工具雖然可以分析C程序源文件的集合并輸出各函數之間的圖表依賴關系，但對源碼中的條件編譯指令等可變代碼的解析存在一定的局限性。例如，Cflow無法直接對目錄進行遞歸分析，只能支持文件級的代碼分析，并且不同文件中的重名函數都被視為同一個函數。

Doxygen[11]是一個用于程序文檔生成的工具，可以收集程序源碼中關于函數和變量的信息。Doxygen支持多種流行的編程語言，如C、Object-C、C#和Java等。Doxygen可以解析源碼文件的代碼結構，并輸出文件中遇到的符號的交叉引用，包括函數、變量和結構體類型的引用關系。利用Doxygen分析源碼，可以為每個源文件輸出一個包含源碼結構的XML文件。結合Graphviz繪圖工具，Doxygen可以生成程序源碼的函數調用關系圖，Doxygen依照配置文件還可以產生HTML、Tex和XML等多種格式的輸出文檔，其中HTML中用有向圖表示了函數之間的調用關系。然而，Doxygen無法支持可變代碼的解析。

為了獲取源碼中條件編譯所有可能分支下的代碼信息，Christian Kastner等人提出一個新的分析框架TypeChef[12]，它主要由三個部分組成：第一部分是可以分析條件編譯指令的詞法分析器，其作用是將代碼片段轉為帶有條件的token流。第二部分是語法分析，其目標是根據詞法輸出的token流生成可以標識編譯條件的抽象語法樹。第三部分是可以解析帶有條件分支的抽象語法樹的分析器，可以對抽象語法樹做進一步解析處理。從以上三個步驟可以發現，TypeChef通過修改詞法分析器，使其可以解析未經過預處理的代碼，得到帶有條件的token流，然后再用語法分析器將token流轉為帶有條件的抽象語法樹，最后再對抽象語法樹進行分析，這樣可以更加全面地分析源碼中的符號信息。以Linux內核代碼為例，Linux內核源碼根據條件編譯可以產生不同的目標代碼，其中的代碼可變性與源代碼中定義的宏有關，在配置文件中設置的宏可以控制具體的目標代碼。對于配置文件中的宏，TypeChef用Waterloo大學的Czarnecki開發的提取Linux內核配置變量的工具[13-15]來提取源碼中相關的宏定義，并且選擇在配置變量定義的情況下獲取源碼文件[16]。TypeChef解析了Linux kernel v2.6.33.3版本中X86架構下的源代碼，根據該工具得到6065個配置宏定義，在配置宏定義的情況下得到7665個源碼文件（總共有899萬行非空行代碼）。

紐約大學Paul Gazzillo等人也提出一種解析原理與TypeChef類似的工具SuperC[17]。SuperC也是經過修改詞法分析器、語法分析器，使其可以分析未經過預處理的代碼，得到一個可以完整地表示程序結構的抽象語法樹。SuperC解析C程序主要包括三個步驟：詞法分析、預處理、語法分析。（1）詞法（Lexing）分析的輸入是C語言源碼，輸出是帶有條件的token 流。（2）預處理過程是分析token，得到一個宏符號表，存儲所有的宏以及宏相關的條件。例如，圖3所示的代碼片段：由于宏const_debug在不同條件下定義不一樣，所以const_debug就會被存儲多份，并且存儲的每個宏都會帶有其定義的條件。對于含有歧義的代碼，預處理器也是會存儲不同的版本。（3）語法分析是解析預處理之后的token。語法分析器是LR分析器的變體，與LR分析器的不同之處在于遇到條件分支可以通過創建子分析器來分析另一個分支路徑，在兩個分析器狀態值一樣的情況下再合并。子分析器與主分析器有相同的下推分析棧（分析棧中記錄了迄今為止所移進或歸約出的全部文法符號，即記錄了從分析開始到目前為止的整個分析歷史）。

當在相同狀態下有相同的輸入時就會合并解析器，但該工具在合并過程中必須保證每個子分析器所分析的代碼結構是完整的。如圖4所示的代碼片段：第8行滿足了分析器合并條件，但是由于子分析器中分析的是5-7行，該段代碼的C語言結構是不完整的，因此，SuperC不會在第8行合并，而是在第9行處理完之后再合并，保證了子分析器中的代碼語法的正確性，最后得到一個可以表示源碼條件分支的抽象語法樹。SuperC與TypeChef一樣，也是通過修改詞法分析與語法分析使其可以解析沒有經過預處理的源碼，得到源碼中的所有符號信息。但這種經過修改的解析器都有各自的局限性，在使用時需要很復雜的配置，尤其對于Linux內核這樣復雜的項目，配置更是困難，因此其可用性較低。

3 增量式可變代碼解析

盡管研究人員提出了TypeChef和SuperC等方法可以用于大規模C代碼的解析，這兩個工具重新設計了編譯器前端的詞法分析器和語法分析器，構建了帶條件的語法分析樹，將源代碼的編譯條件帶到了語言的中間代碼表示中，從而為程序的進一步分析處理奠定了良好的基礎。但是由于Linux代碼的規模過于龐大，這些工具的使用配置復雜，用戶很難準確配置，并輸出期望的結果。

圖5顯示了Linux kernel v3.19中的一段可變代碼，該代碼片段中包含了條件編譯指令#ifdef CONFIG_ACPI和#ifdef CONFIG_X86，其二者之間存在嵌套關系。在解析該代碼片段的過程中，很多可變代碼解析工具如SuperC等遇到第一個條件編譯指令#ifdef CONFIG_ACPI時，需要克隆一個新的編譯實例以實現不同條件編譯分支的編譯和解析。當遇到嵌套的第二個條件編譯指令#ifdef CONFIG_X86，需要再次克隆一個新的編譯器實例，從而使得代碼解析的時間開銷大大增加。而Linux內核這樣的大規模復雜C代碼包含大量的條件編譯指令，因此，利用SuperC進行內核代碼解析的開銷非常大。

3.1 Linux kernelv3.19頭文件復用情況

Linux內核是典型的大規模C語言程序，以3.19版本為例，其中包括54180個文件，18406489行代碼，并且包括了923640個宏定義和41398個條件編譯指令，而多個宏定義嵌套和條件編譯嵌套會導致更加復雜的代碼結構。雖然TypeChef和SuperC給出了可變代碼分析與提取的可行方案，但是對如此大規模代碼的分析仍然需要較長的時間。從另一個角度考慮，大規模代碼也為可變代碼解析加速提供了其他的可能。對Linux內核代碼進行仔細分析發現，盡管內核代碼中大量的條件編譯指令，但這些條件編譯指令大多存在于頭文件中，且在C代碼編譯的過程中，很多頭文件被多次包含，頭文件的重復解析大大降低了代碼解析的效率。本文統計了Linux kernel v3.19代碼中頭文件的包含次數，表1展示了被包含次數最多的10個頭文件。其中，頭文件module.h被包含的次數最多，達到6911次。除此之外，init.h、kernel.h和slab.h被包含的次數也超過了5000余次。

3.2 基于頭文件復用的增量式解析方法

uperC等代碼解析工具在分析每個C文件代碼時需要合并所有的頭文件代碼再進行分析。因此，盡管一個頭文件可能被多個C文件包含，但在解析不同C文件的過程中，該頭文件都會再次被解析，導致代碼解析的開銷大大增加。本文提出一種基于頭文件復用的增量代碼解析方法，首先分析內核C代碼中頭文件的復用情況，然后，在解析每個C文件的過程中，如果頭文件被復用，則直接獲取頭文件的解析結果，而不再重復解析該頭文件。由于在每個C文件中，頭文件是按順序被加載的，頭文件之間可能存在依賴關系，因此，本方法首先以Linux內核中頭文件的加載順序構建加載樹，再按照頭文件加載樹依次增量解析C文件代碼。

如圖6所示的頭文件加載樹，樹中的每個非葉子結點（矩形）代表頭文件，葉子結點（橢圓形）代表要解析的C文件，頭文件之間的邊代表加載順序，頭文件與C文件之間的邊代表從根結點出發到達此C文件的頭文件都被包含于該C文件中。因此，按照圖中的加載順序進行解析，所有的頭文件和C文件只需要被解析一次。例如，C文件arch/sparc/lib/atomic32.c、drivers/acpi/ac.c、drivers/acpi/sbs.c和drivers/acpi/processor_perflib.c 在編譯的過程中都需加載頭文件module.h，而drivers/acpi/ac.c、drivers/acpi/sbs.c、drivers/acpi/processor_perflib.c 在編譯時都需加載頭文件module.h、init.h、kernel.h、slab.h 和types.h，因此，在解析這些C文件時，原有的解析方法將對module.h解析4次，對init.h、kernel.h、slab.h和types.h分別解析3次，而按照本文的方法，上述頭文件都只需被解析1次。

基于上述思路，本文提出的增量式可變代碼解析的具體工作流程如算法1所示，首先掃描所有的C文件，獲取包含的文件列表。為了保證語義的正確性，本文只獲取每一個C文件開始部分連續包含的文件，遇到代碼部分則立即停止。然后對于每個C文件的include列表，從樹的根節點開始查找對應深度的頭文件，如果已經在某條路徑上發現，則直接復用，否則創建一個新的節點和分支路徑。頭文件加載樹的每個節點對應一個頭文件，并且可能包含到達該節點的所有C文件。

算法1：頭文件加載樹構建buildTree

輸入：根節點root、某個C文件ci的include列表hl、遞歸深度depth

輸出：更新后的頭文件加載樹

Begin：

If depth == length（hl） Then

root.cFileList.append（ci）

return

End

hf ← hl[depth]

If hf not in root.children Then

Create a new node n

n.hFile ← hf

root.children ← root->children.append（n）

Else

n ← find node from roots children list using hf

End If

buildTree（n， hl， depth+1）

End

與SuperC不同，本文提出的解析方法從頭文件加載樹的根節點開始，首先對每個節點對應的頭文件內容進行解析，然后對解析器進行復制，在同一個狀態下分別對該節點對應的C文件進行解析。如果該節點有多個子節點，則也需要對解析器進行復制，以對后續的節點分別進行遍歷和解析。

具體過程如算法2所示。

算法2：文件解析算法parse

輸入：根節點root，可變代碼解析器P

輸出：更新后的頭文件加載樹

Begin：

Parse root.hFile

For c in root.cFiles

P ← Deep copy p

Parse c using P

End For

If root has one child Then

Parse（n， P）

Else

For each n in roots children list

P ← Deep copy p

Parse（n， P）

End For

End If

End

該算法首先對當前節點對應的頭文件進行分析，然后檢查當前節點是否有C文件，如果有的話就對分析器進行拷貝，對每個C文件進行分析并輸出分析結果。處理完當前節點后，檢查當前節點是否有多個節點，如果有多個節點，則同樣需要對分析器進行拷貝，以隔離的狀態遞歸處理不同的分支。當前節點如果只有一個子節點，則可以直接基于當前的分析器狀態繼續分析。

事實上，Linux內核中頭文件的復用情況更加復雜，而頭文件中的宏定義和條件編譯等預處理指令是代碼解析中最耗時的部分，因此，采用本文的方法可以大大縮短C代碼解析的時間。

4 實驗評估及結果

4.1 實驗環境

本文以Linux kernel v3.19源代碼為實驗數據。實驗環境為Windows 10操作系統，CPU為Intel i7-7700，內存為16GB。本方法利用已有的可變代碼解析工具SuperC實現對Linux kernel v3.19代碼的解析，SuperC的版本為2.4.0。

4.2 性能評估

為了評估本章提出的基于頭文件復用的增量代碼解析方法的有效性，分別用本方法和SuperC工具解析Linux kernel v3.19的源代碼，并將其代碼解析的時間進行了對比。

實驗結果表明，用原方法解析內核代碼的時間為91小時，而采用本方法時解析時間僅為56小時。表2列出了解析不同Linux內核目錄時，本方法與SuperC解析的時間對比。整體上來講，與原方法相比，本方法解析Linux內核代碼所需的時間大大縮短了，平均加速比達到1.59。

圖7展示了C文件中包含的頭文件序列長度與這些頭文件序列被復用的次數的關系。從圖7中可以看出，在Linux kernel v3.19代碼中，頭文件被包含的最長序列長度為29，且只有2個C文件中包含了如此多的頭文件數目。被復用次數最多的頭文件序列長度為2，復用次數多達439次。

5 結論

本文設計了一種用于大規?？勺僀代碼增量式解析的方法。本方法基于頭文件復用設計了可用于C代碼增量解析的文件加載樹。以Linux kernel v3.19為例，與傳統的可變C代碼解析方法相比，本文提出的代碼解析方法可以更加高效快速地解析大規?？勺僀代碼。

參考文獻

[1] 陸申明，左志強，王林章.靜態程序分析并行化研究進展[J].軟件學報，2020，31（5）：7-18.

[2] 陳廳.動態程序分析技術在軟件安全領域的研究[D].成都：電子科技大學，2013.

[3] GANGE G，NABAS J A，SCHACHTE P，et al.Abstract interpretation over non-lattice abstract domains[C]//International Static Analysis Symposium. Springer， Berlin， Heidelberg，2013： 6-24.

[4] REPS T，HORWITZ S，SAGIV M.Precise interprocedural dataflow analysis via graph reachability[C]//Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages.1995：49-61.

[5] TRABISH D，MATTAVELLI A，RINETZKY N，et al. Chopped symbolic execution[C]//Proceedings of the 40th International Conference on Software Engineering. 2018：350-360.

[6] 周天琳，史亮，徐寶文，等.Refactoring C++Programs Physically重構C++程序物理設計[J].軟件學報，2009，20（003）： 597-607.

[7] Visual studio.https：//visualstudio.microsoft.com/.

[8] Gcc，the gnu compiler collection.http：//gcc.gnu.org/.

[9] Gnu cflow.http：//www.gnu.org/software/cflow/.

[10] Clang：a C language family frontend for LLVM. http：//clang.llvm.org/.

[11] Doxygen.http：//www.doxygen.org/.

[12] KASTNER C，GIARRUSSO P G，RENDELende T，et al.Variability-aware parsing in the presence of lexical macros and conditional compilation[J].Acm Sigplan Notices，2011，46（10）：805-824.

[13] SAKAGUCHI S，TAKAHASHI T，HATA H，et al.Variability modeling in the real：a perspective from the operating systems domain[C]//Proceedings of the IEEE/ACM international conference on Automated software engineering， 2010：73–82.

[14] SHE S，LOTUFO R，BERGER T，et al.Reverse engineering feature models[C]//Proceedings of the 33rd International Conference on Software Engineering，2011：461-470.

[15] SHE S，LOTUFO R，BERGER T，et al.The Variability Model of The Linux Kernel[C]//International Workshop on Variability Modelling of Software-intensive Systems， 2010：45-51.

[16] BERGER T，SHE S，LOTUFO R，et al.Feature-to-code mapping in two large product lines[C]//International Conference on Software Product Lines：Going Beyond， 2010：498-499.

[17] GAZZILLO P，GRIMM R.SuperC：parsing all of C by taming the preprocessor[C]//ACM Sigplan Conference on Programming Language Design and Implementation， 2012：323-334.