SOFTWARE 2021
软  件第42卷 第3期
2021年
Vol. 42, No.3
目前，大规模C 程序已广泛存在于实际生产实践中，例如，Linux 内核、Apache HTTP Server 和Mozilla Firefox 等程序的代码规模已超过百万行，甚至达到几千万行。相比于普通程序，大规模C 程序的开发、管理和维护都变得更加困难。
为了对程序进行优化，自动发现程序中存在的潜在
问题，研究人员提出了静态分析和动态分析等程序分析技术[1-2]。静态程序分析是程序分析中一种有效的技术手段，它主要指在不运行程序的情况下，从源代码中提取程序的结构化信息，再进行进一步分析和处理。通过
静态程序分析，开发人员可以在开发阶段即可发现代码
中存在的潜在问题，从而实现代码优化、缺陷检测和修复，提升程序开发的效率。静态程序分析通常需要借助于编译器前端工具解析源代码，首先通过预处理、词法分析和语法分析等步骤，从源代码或者中间代码中提取出抽象语法树、函数调用图和控制流图等，再利用抽象解释[3]、数据流分析[4]和符号执行[5]等方法对源代码
进行分析。
然而，大规模C 程序的静态代码解析过程面临诸多
挑战：（1）C 程序中广泛存在头文件包含、宏定义和条
基金项目：本研究得到了2019年工业互联网创新发展工程项目“车联网安全综合服务平台”支持。
作者简介：石剑君（1991―），女，河南邓州人，博士，研究方向：程序分析与优化；计卫星（1980―），男，陕西咸阳人，博
士，副教授，研究方向：并行与高性能计算、程序分析与优化；杨玚（1980―），男，江苏徐州人，博士，高级工程
师，研究方向：软件与网络安全。
通讯作者：刘法旺（1981―），男，河南商城人，博士，高级工程师，研究方向：智能网联汽车安全。
大规模可变C 代码增量式分析方法
石剑君1  刘法旺2  计卫星1  杨玚3
（1.北京理工大学计算机学院，北京  100081；
2.工业和信息化部装备工业发展中心，北京  100846；
3.中国软件评测中心，北京  100086）
摘　要：提出一种基于头文件复用的大规模可变C 代码增量式分析方法。以Linux 内核代码为例，首先统计和分析了大
规模C 代码中的头文件包含情况。然后根据头文件包含顺序，构建C 代码分析的头文件加载树。最后，按照头文件加载树增量地分析C 代码。实验结果表明，与原有的代码分析方法相比，本方法可以极大地提升大规模可变C 代码分析的效率。
关键词：大规模C 代码；可变代码；代码分析中图分类号：V211
文献标识码：A
DOI ：10.3969/j.issn.1003-6970.2021.03.023
本文著录格式：石剑君，刘法旺，计卫星，等.大规模可变C代码增量式分析方法[J].软件,2021,42(03):079-085
Incremental Parsing Method for Large-scale Variable C Source Code
SHI Jianjun 1, LIU Fawang 2, JI Weixing 1, YANG Yang 3
(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, fi rstly, we summarize and analyze the included header fi les in large-
scale C source code. Then, header fi le loading trees are built according to the inclusion order of header fi les. Finally, the C source code is parsed incrementally based on the header fi le loading trees. The experimental results show that compared with the traditioanl code parsing methods, our method can greatly improve the effi  ciency of large-scale
variable C source code parsing.
【Key words】：large-scale C source code;variable code;code parsing
基金项目论文
软 件
第42卷 第3期SOFTWARE
件编译等预处理指令，增加了代码的可变性，代码解析的难度也随之增大；（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定义和未定义两种情况。现有的编译器在遇到条件编译时只选择其中的一个条件分支进行编译，无法支持可变代码的分析，因此需要设计特定的工具支持可变代码的分析。
图2展示了一段简单的可变C代码的解析过程。该代码在#ifdef A条件成立时，执行“#defi ne X 4”。否则，则执行“#defi ne X 5”。在该可变代码的解析过程中，主要包含词法分析、语法分析和处理系统三个部分。其中，第一部分是可以分析条件编译指令的词法分析器，其作用是将代码片段转为带有条件的token流。对于上述示例生成的token流中，在#ifdef A 之后的
图1 Linux kernel v3.19中一段可变代码示例Fig.1 An example of variable code in Linux kernel v3.19
图2 可变C代码分析示例
Fig.2 An example of variable C code parsing
石剑君  刘法旺  计卫星等：大规模可变C代码增量式分析方法
所有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 Cfl ow[9]和Clang[10]等，这些工具虽然可以分析C程序源文件的集合并输出各函数之间的图表依赖关系，但对源码中的条件编译指令等可变代码的解析存在一定的局限性。例如，Cfl ow无法直接对目录进行递归分析，只能支持文件级的代码分析，并且不同文件中的重名函数都被视为同一个函数。
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通过修改词法分析器，使其可以解析未经过预处理的代码，得到
图3 不同条件的宏定义代码片段示例Fig.3 An example of conditional macro defi nition
图4 SuperC解析可变代码示例Fig.4 An example of variable code parsed by SuperC
软 件
第42卷 第3期SOFTWARE
带有条件的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进行内核代码解析的开销非常大。
图5 Linux kernel v3.19中一段嵌套的条件代码示例Fig.5 An example of nested conditional code in Linux
kernel v3.19
3.1 Linux kernelv3.19头文件复用情况Linux内核是典型的大规模C语言程序，以3.19版本为例，其中包括54180个文件，18406489行代码，并且包括了923640个宏定义和41398个条件编译指令，而多个宏定义嵌套和条件编译嵌套会导致更加复杂的代
石剑君  刘法旺  计卫星等：大规模可变C代码增量式分析方法
码结构。虽然TypeChef和SuperC给出了可变代码分析与提取的可行方案，但是对如此大规模代码的分析仍然需要较长的时间。从另一个角度考虑，大规模代码也为可变代码解析加速提供了其他的可能。对Linux内核代码进行仔细分析发现，尽管内核代码中大量的条件编译指令，但这些条件编译指令大多存在于头文件中，且在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_perfl ib.c 在编译的过程中都需加载头
上述头文件都只需被解析1次。
图6 Linux kernel v3.19中头文件复用示例Fig.6 An example of header fi les included in Linux kernel
v3.19
基于上述思路，本文提出的增量式可变代码解析的具体工作流程如算法1所示，首先扫描所有的C文件，获取包含的文件列表。为了保证语义的正确性，本文只获取每一个C文件开始部分连续包含的文件，遇到代码部分则立即停止。然后对于每个C文件的include列表，从树的根节点开始查对应深度的头文件，如果已经在某条路径上发现，则直接复用，否则创建一个新的节点和分支路径。头文件加载树的每个节点对应一个头文件，并且可能包含到达该节点的所有C文件。
算法1：头文件加载树构建buildTree
输入：根节点root、某个C文件ci的include列

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。