石劍君 劉法旺 計(jì)衛(wèi)星 楊玚

摘 要：提出一種基于頭文件復(fù)用的大規(guī)?？勺僀代碼增量式分析方法。以Linux內(nèi)核代碼為例，首先統(tǒng)計(jì)和分析了大規(guī)模C代碼中的頭文件包含情況。然后根據(jù)頭文件包含順序，構(gòu)建C代碼分析的頭文件加載樹(shù)。最后，按照頭文件加載樹(shù)增量地分析C代碼。實(shí)驗(yàn)結(jié)果表明，與原有的代碼分析方法相比，本方法可以極大地提升大規(guī)?？勺僀代碼分析的效率。

關(guān)鍵詞：大規(guī)模C代碼;可變代碼;代碼分析

中圖分類號(hào)：V211 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2021.03.023

本文著錄格式：石劍君，劉法旺，計(jì)衛(wèi)星，等.大規(guī)?？勺僀代碼增量式分析方法[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

目前，大規(guī)模C程序已廣泛存在于實(shí)際生產(chǎn)實(shí)踐中，例如，Linux 內(nèi)核、Apache HTTP Server和Mozilla Firefox等程序的代碼規(guī)模已超過(guò)百萬(wàn)行，甚至達(dá)到幾千萬(wàn)行。相比于普通程序，大規(guī)模C程序的開(kāi)發(fā)、管理和維護(hù)都變得更加困難。

為了對(duì)程序進(jìn)行優(yōu)化，自動(dòng)發(fā)現(xiàn)程序中存在的潛在問(wèn)題，研究人員提出了靜態(tài)分析和動(dòng)態(tài)分析等程序分析技術(shù)[1-2]。靜態(tài)程序分析是程序分析中一種有效的技術(shù)手段，它主要指在不運(yùn)行程序的情況下，從源代碼中提取程序的結(jié)構(gòu)化信息，再進(jìn)行進(jìn)一步分析和處理。通過(guò)靜態(tài)程序分析，開(kāi)發(fā)人員可以在開(kāi)發(fā)階段即可發(fā)現(xiàn)代碼中存在的潛在問(wèn)題，從而實(shí)現(xiàn)代碼優(yōu)化、缺陷檢測(cè)和修復(fù)，提升程序開(kāi)發(fā)的效率。靜態(tài)程序分析通常需要借助于編譯器前端工具解析源代碼，首先通過(guò)預(yù)處理、詞法分析和語(yǔ)法分析等步驟，從源代碼或者中間代碼中提取出抽象語(yǔ)法樹(shù)、函數(shù)調(diào)用圖和控制流圖等，再利用抽象解釋[3]、數(shù)據(jù)流分析[4]和符號(hào)執(zhí)行[5]等方法對(duì)源代碼進(jìn)行分析。

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

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

1 可變代碼解析

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

C程序的編譯過(guò)程包含預(yù)處理、詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等環(huán)節(jié)，其中，程序靜態(tài)分析主要關(guān)注中間代碼生成之前的過(guò)程，即編譯器前端的執(zhí)行過(guò)程。預(yù)處理階段主要對(duì)源文件中的頭文件包含、宏定義和條件編譯等預(yù)處理部分進(jìn)行處理。詞法分析階段的任務(wù)是對(duì)輸入符號(hào)串形式的源程序進(jìn)行處理，依次掃描源程序中的每個(gè)字符，識(shí)別出源程序中有獨(dú)立意義的語(yǔ)言單詞，最后輸出token流。語(yǔ)法分析是依據(jù)語(yǔ)言的語(yǔ)法規(guī)則，對(duì)詞法分析結(jié)果進(jìn)行語(yǔ)法檢查，通常語(yǔ)法分析的結(jié)果是一個(gè)抽象語(yǔ)法樹(shù)，是源碼的一種中間表示形式。

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

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

對(duì)使用了大量編譯預(yù)處理指令的C語(yǔ)言程序進(jìn)行分析是C程序分析和應(yīng)用過(guò)程中面臨的重點(diǎn)問(wèn)題之一。例如，在C程序代碼重構(gòu)的過(guò)程中，需要保證不同條件編譯分支的代碼都得到正確處理[6]。另外，目前很多集成開(kāi)發(fā)環(huán)境如Visual Studio等都提供了即時(shí)語(yǔ)法檢查的功能，能夠在用戶輸入代碼的同時(shí)對(duì)代碼進(jìn)行全面的分析和檢測(cè)，如果輸入代碼包含了條件編譯指令，則應(yīng)盡可能地檢測(cè)出不同分支的具體問(wèn)題[7]。以上這些應(yīng)用場(chǎng)景要求建立一個(gè)能夠分析可變性代碼的代碼分析工具。

2 相關(guān)工作

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

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

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

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

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

3 增量式可變代碼解析

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

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

3.1 Linux kernelv3.19頭文件復(fù)用情況

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

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

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

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

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

算法1：頭文件加載樹(shù)構(gòu)建buildTree

輸入：根節(jié)點(diǎn)root、某個(gè)C文件ci的include列表hl、遞歸深度depth

輸出：更新后的頭文件加載樹(shù)

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不同，本文提出的解析方法從頭文件加載樹(shù)的根節(jié)點(diǎn)開(kāi)始，首先對(duì)每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的頭文件內(nèi)容進(jìn)行解析，然后對(duì)解析器進(jìn)行復(fù)制，在同一個(gè)狀態(tài)下分別對(duì)該節(jié)點(diǎn)對(duì)應(yīng)的C文件進(jìn)行解析。如果該節(jié)點(diǎn)有多個(gè)子節(jié)點(diǎn)，則也需要對(duì)解析器進(jìn)行復(fù)制，以對(duì)后續(xù)的節(jié)點(diǎn)分別進(jìn)行遍歷和解析。

具體過(guò)程如算法2所示。

算法2：文件解析算法parse

輸入：根節(jié)點(diǎn)root，可變代碼解析器P

輸出：更新后的頭文件加載樹(shù)

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

該算法首先對(duì)當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的頭文件進(jìn)行分析，然后檢查當(dāng)前節(jié)點(diǎn)是否有C文件，如果有的話就對(duì)分析器進(jìn)行拷貝，對(duì)每個(gè)C文件進(jìn)行分析并輸出分析結(jié)果。處理完當(dāng)前節(jié)點(diǎn)后，檢查當(dāng)前節(jié)點(diǎn)是否有多個(gè)節(jié)點(diǎn)，如果有多個(gè)節(jié)點(diǎn)，則同樣需要對(duì)分析器進(jìn)行拷貝，以隔離的狀態(tài)遞歸處理不同的分支。當(dāng)前節(jié)點(diǎn)如果只有一個(gè)子節(jié)點(diǎn)，則可以直接基于當(dāng)前的分析器狀態(tài)繼續(xù)分析。

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

4 實(shí)驗(yàn)評(píng)估及結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

本文以Linux kernel v3.19源代碼為實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)環(huán)境為Windows 10操作系統(tǒng)，CPU為Intel i7-7700，內(nèi)存為16GB。本方法利用已有的可變代碼解析工具SuperC實(shí)現(xiàn)對(duì)Linux kernel v3.19代碼的解析，SuperC的版本為2.4.0。

4.2 性能評(píng)估

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

實(shí)驗(yàn)結(jié)果表明，用原方法解析內(nèi)核代碼的時(shí)間為91小時(shí)，而采用本方法時(shí)解析時(shí)間僅為56小時(shí)。表2列出了解析不同Linux內(nèi)核目錄時(shí)，本方法與SuperC解析的時(shí)間對(duì)比。整體上來(lái)講，與原方法相比，本方法解析Linux內(nèi)核代碼所需的時(shí)間大大縮短了，平均加速比達(dá)到1.59。

圖7展示了C文件中包含的頭文件序列長(zhǎng)度與這些頭文件序列被復(fù)用的次數(shù)的關(guān)系。從圖7中可以看出，在Linux kernel v3.19代碼中，頭文件被包含的最長(zhǎng)序列長(zhǎng)度為29，且只有2個(gè)C文件中包含了如此多的頭文件數(shù)目。被復(fù)用次數(shù)最多的頭文件序列長(zhǎng)度為2，復(fù)用次數(shù)多達(dá)439次。

5 結(jié)論

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

參考文獻(xiàn)

[1] 陸申明，左志強(qiáng)，王林章.靜態(tài)程序分析并行化研究進(jìn)展[J].軟件學(xué)報(bào)，2020，31（5）：7-18.

[2] 陳廳.動(dòng)態(tài)程序分析技術(shù)在軟件安全領(lǐng)域的研究[D].成都：電子科技大學(xué)，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重構(gòu)C++程序物理設(shè)計(jì)[J].軟件學(xué)報(bào)，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.