编译前端分析自动构件化代码可靠性加强方法*

葛红美，徐 超+，何炎祥

1.南京审计大学 工学院，南京 211815

2.武汉大学 计算机学院，武汉 430072

1 引言

嵌入式系统主要以应用控制为主，根据具体的应用需求来制定系统的功能、结构、体积、组成等，具有系统内核小、专用性强、运行环境复杂、系统集成度高、运行稳定可靠、时效性高等特点[1-2]。随着信息时代的高速发展，嵌入式系统得到了最为广泛的应用。小到电子手表、家用电器、自助取款机，大到汽车、火车、飞机、火箭，嵌入式系统已经深入到经济、教育、科技和军事的方方面面[3]。

对于嵌入式系统而言，可靠性是不容忽视的重要问题。嵌入式系统一旦出现故障，将会严重威胁到人们的生命财产和国防安全。在美国，仅仅因为一枚价值45美分的极小的集成电路失效，令北美防空联合司令部指挥中心两次发出虚假的进攻警报，造成一千枚洲际弹道导弹处于初级戒备状态，全体军官待命，多架战斗机起飞。在欧洲，由于火箭设计师们忽略了软件的可靠性，只重视火箭硬件的可靠性设计，导致火箭惯性制导系统软件出现规格和设计错误，造成阿里亚那火箭升空40秒后自爆，损失5亿英镑。在美国，1983年科罗拉多州洪水泛滥，正是由于计算机发出错误预告，导致水库被冲垮。在意大利，由于计算机设备存在故障，国家数据库被破坏6秒钟，需要6年才能修复。在中国，2011年7月23日甬温线发生动车追尾事故，由于信号设备存在安全故障，造成35死210伤的悲剧。从以上事例可以看出，系统软件的安全性、可靠性在嵌入式系统中占重要地位，如何加强嵌入式系统可靠性具有十分重要的研究价值，如何提高嵌入式系统的可靠性已经成为不容忽视的重要问题。

嵌入式系统软件的可靠性是系统中非常重要的组成部分。随着嵌入式系统智能化程度的不断增强，嵌入式系统越来越复杂，其实现方式已由初始的汇编实现改为了高级语言（主要是C语言）实现。因此，要加强嵌入式系统的可靠性，首先必须对代码进行加强，即提升代码的可靠性，减少漏洞。

本文以编译前端的语法语义分析为基础，结合构件化技术，提出了一种多层次迭代分析可构件化代码识别方法。该方法对C语言实现的嵌入式系统源代码进行分析，通过对比当前源代码和可靠构件代码的相似性，找出其中相似度高的代码块。然后借助于人机交互技术，将其中某些未经验证的程序转为可靠构件的实现，利用可靠构件的可靠性获得源代码可靠性的加强。

本文组织结构如下：第2章介绍了编译前端分析技术和构件化方法的相关背景知识；第3章重点阐述了基于编译前端分析自动构件化代码加强方法；第4章通过模拟实验验证了可靠性加强方法的效果；最后对全文进行了总结。

2 相关背景

2.1 基于编译的代码可靠性加强方法

由于源程序是嵌入式系统软件的基本输入，源程序本身的可靠程度直接决定了最终生成的目标代码的质量。而编译前端通过语法语义分析，掌握了源代码结构和语义的全面信息，是对源程序较为全面的一种分析技术，因此不少学者以编译器为基础，对源代码加强方法进行研究。目前的研究主要集中于代码安全漏洞防范和代码安全属性证明这两方面。

2.1.1 代码漏洞防范技术

此类研究主要针对代码中某种常见的安全漏洞，通过在编译过程中对代码进行修改，来防范安全漏洞可能引发的恶意攻击。此类研究具有代表性的就是针对最常见的缓冲区溢出攻击的StackGuard[4]和StackShield[5]方法。StackGuard通过编译过程对程序进行修改，使其每次在调用函数时，将返回地址压栈后，再将一个随机产生字压栈。当函数调用完毕后，查看此随机字是否被修改，若改动，说明有溢出攻击发生，则报警并停止程序运行。StackShield使用了另一种技术，它更改程序使其在运行时创建一个特别的堆栈，用来存储函数返回地址的一份拷贝，并在受保护的函数开头和结尾分别增加一段代码，开头处代码用来将函数返回地址拷贝到这个特殊堆栈中，而结尾处代码则用来将返回地址从特殊堆栈中拷贝回原程序运行堆栈。

代码安全属性证明方法研究主要针对编译过程中程序的可靠性证明问题。其最具代表性的工作就是由Carnegie Mellon大学的Necula和Lee提出的携带证明的代码（proof carrying code，PCC）[6-7]，此方法主要用于验证代码是否遵循预先定义的某些安全性条件。PCC提出了一种程序验证框架，首先在代码发送方，根据用户所提安全条件，对代码进行分析，产生一种安全形式化证明信息，并将此信息“证书”附加于原始代码上形成携带证明的代码；在代码接收方，根据相同安全条件，参照PCC中的“证书”，对代码进行验证，如果通过验证，则认为此代码是可靠的，允许执行。PCC中安全条件均采用一阶逻辑谓词进行描述，证明过程采用逻辑推理的方法，代码验证通过类型检查机制实现。PCC主要用于移动通信中代码的验证。PCC对源代码没有做任何修改，只是将安全性证明信息附加在代码中，供代码使用者验证所用。但是PCC存在“证书”代码量过大的问题，一般为待验证代码量的3到7倍，严重影响了验证效率。与PCC相似，Cornell大学的Kozen带领的研究小组提出了ECC（efficient code certification）[8-9]，一种简单有效的程序验证方法。ECC也可以看作是一种携带证明的代码验证方法，只是它的“证书”不是完整的形式化证明过程，而只是一些证明的引导信息。ECC可以保证通过验证的代码具有控制流安全、内存安全、堆栈安全等特性。最重要的是，ECC可采用对已有编译器进行修改的方式实现。虽然ECC对代码安全性的描述能力没有PCC强，但是其证明过程更加简单，验证过程效率更高。该类方法还可以应用于编译器本身的可靠性验证、编译优化可靠性验证以及运行嵌入式系统可靠性加强[10-18]。

2.1.2 构件化

构件化开发是将一个个相对独立的、被充分证明为可靠的构件，通过给定的标准接口进行组装，形成满足对应功能软件的开发方法。它不但能有效提升软件开发效率，而且由于每个构件已经经过了充分验证，有效避免了不同软件开发人员由于个人编程经验不足而导致的不可靠性，使得生成的软件具有较高的质量。不少国内外公司和组织制定了相应的构件标准，如微软的COM、Oracle的JavaBean、OMG组织的CORBA（common object request broker architecture）等。

但构件是严格封装的，完全使用构件化进行嵌入式系统开发在一定程度上限制了软件开发的灵活性，这对于希望尽可能高效地利用各种资源的嵌入式系统是极其不利的。因此，如果能够在已有源代码的基础上提取出其中可构件化的代码进行优化，不但保持了嵌入式程序的灵活性，而且对于嵌入式程序可靠性的提升将有着显著作用。

本文将结合构件化软件开发的方法，通过对源程序的分析，提取出其中可构件化成分，然后选择最合适的构件进行映射，以最大程度提升源程序的质量。其中，可构件化代码识别和使用何种构件进行代码映射是确保源程序质量最为关键的两个步骤，本文将重点研究这两个过程。

2.2 编译前端分析自动构件化代码加强方法

为提高源程序本身的可靠性，缓解由于程序员本身经验缺乏导致的代码不可靠性以及实现的低效率性，本文设计了一种基于编译前端分析自动构件化的代码加强技术。该方法首先对编译器前端预处理器之后的源程序进行分析，然后借助于一套可靠构件库，根据其结构特征，采用模糊匹配的方式，从源程序中识别出与可靠构件相似程度高的代码块。

由于采用的是基于程序结构相似度进行的模糊匹配，识别的源程序并不一定具备可构件化的能力。而且同一段代码也许会有针对不同使用场景的多种实现方式，对于识别的源程序模块具体该使用哪个可靠构件进行替换需要程序员根据具体的应用场景才能确定。因此，在识别了可构件化的程序片段后，将利用人机交互的方式确定该程序片段是否可以使用可靠构件进行替换，以及使用哪个构件进行替换更为合适。

该方法的总体框架如图1所示，主要包括两个过程：多层次迭代分析可构件化代码识别和基于人机交互的功能模块构件化映射。

2.2.1 多层次迭代分析可构件化代码识别方法

对于可构件化代码识别过程，本文拟采用一种多层次迭代分析的方法对源程序中可构件化部分进行识别。该方法以函数为识别的基本单位，从最底层函数（即函数调用关系图中的叶子节点）开始，依次向上迭代分析，利用可靠构件集查找源程序中可构件化部分。

如图1所示，首先对预处理后代码进行分析，构件函数调用关系图（函数调用图中每个节点表示源程序中一个函数，每条边表示函数调用关系）。然后，对该图中第0层节点进行分析，计算该节点同可靠构件集中的每个构件在程序结构上的相似度，并保存相似度大于阈值的节点作为该节点可选构件。接着分析第1层中的节点，识别其中可构件化的节点保存到可靠构件化映射表中。以此迭代分析，直到第n层。其中，第n层节点是指该节点到最远叶子节点的路径上经过的节点数目。

在该步骤中，代码相似度检测是核心，本文主要基于文献[21]中使用的代码相似度计算方法，检测包含以下3个步骤：

（1）分析源程序，将其转化为具有数据流和控制流信息的抽象中间表示形式，如抽象语法树（abstract syntax tree，AST）；

（2）应用变换法则对中间表示形式进行规范化处理，以便降低理解的复杂度；

Fig.1 Code reliability enhancement method based on automatic component and compiler front-end analysis图1 基于编译前端分析自动构件化代码加强方法

（3）分析规范化处理结果，识别出程序中包含的语义及知识信息，然后进行分析与推理，获取程序设计者的意图。

但由于待检测的代码是可能包含缺陷的嵌入式代码，在步骤（2）进行代码规则化处理时，忽略了以下3类语句：

（1）如果控制语句是针对数组索引值的判断或空指针的判断，则忽略该控制语句；

（2）如果内存申请与释放语句（如malloc、free等），则忽略该语句；

（3）如果是针对指针赋值为空的操作，则忽略该语句。

同时，由于本文的可靠构件主要是基于函数进行封装的，在对函数进行分析时，不再进行递归展开，而是将其作为一个普通顺序节点进行处理。

代码之间的相似度按照规模相似度SizeS、结构相似度StructS、语句相似度StateS和知识点相似度PivotS这4个维度进行计算，具体公式如下：

算法1描述了多层次迭代分析查找源代码与可靠构件相似代码的具体过程。

算法1多层次迭代分析可构件化算法

下面详细分析4个维度相似度的计算方法及权重选择策略。

2.2.2 规模相似度

规模相似度计算时将程序分为4种类型：循环语句、选择语句、赋值语句和其他语句。然后遍历AST树，统计各类语句节点的个数，得到待检测代码规模向量Vs和所有可靠构件代码规模向量Vt。最后按照式（2）计算规模相似度。

规模相似度主要衡量不同代码块之间各种类型语句在数量上的一致性，并不分析具体语义。

2.2.3 结构相似度

结构相似度主要衡量待检测代码AST树与可靠构件代码AST树在树结构上的相似度。

定义两棵树T1、T2的节点对(v1,v2)是匹配节点，当且仅当：（1）v1与v2具有相同的符号，即相同的类型、运算符、被调用的函数名；（2）v1、v2的父节点是匹配节点对；（3）假设w1和w2是匹配节点对，v1与w1是兄弟节点，v2与w2是兄弟，那么如v1在w1前出现，则v2在w2前出现；（4）v1至多能和T2中的1个节点匹配，v2至多能和T1中的1个节点匹配。

因此，求待检测代码与可靠构件代码结构相似度问题，即可转为两棵AST树节点匹配问题。本文将借助文献[21]的方法对结构匹配程度进行计算，最后按照式（3）计算结构相似度。其中StructMatch（S,T）表示树S（待检测代码的AST树）和树T（可靠构件代码的AST树）匹配的节点数目。

2.2.4 语句相似度和知识点相似度

语句相似度和知识点相似度主要是为了进一步突出语义的相似性而增加的额外维度。程序语义通常由表达式或者功能函数进行描述，因此语句相似度则强调比较待检测代码与可靠构件代码在表达式上的相似程度，而知识点相似度则强调比较待检测代码与可靠构件代码在函数调用方面的相似度。它们都是在结构相似度的基础上，专门针对表达式节点、函数调用节点的相似程度重新进行计算得到的。

具体计算时，算法依次遍历匹配AST树，获得待检测代码中表达式节点和函数调用节点的数目Gst和Gpv。然后遍历结构相似节点，如果该节点是表达式节点，则将valuest加1；如果是相同函数调用节点，则将 valuepv值加1。最后分别根据式（4）和式（5）计算语句相似度和知识点相似度。

2.2.5 权重参数的选择

由于规模相似度主要衡量不同代码块之间各种类型语句在数量上的一致性，并不分析具体语义，其权重值不宜设置较大。

同时，语句相似度和知识点相似度均是在结构相似度的基础上针对语义进行的强化，因此这两个维度的值也不宜设置较大。

结构相似度既包含了代码形式上的相似，同时也兼顾了语义方面的内容，其对于代码相似度的评估最为全面，因此其权重值可以设置为较大值。

在实验时，将 u1、u3、u4的值设置为0.1，将 u2的值设置为0.7。

2.3 基于人机交互的功能模块构件化映射

在对识别的可构件化代码进行构件化的过程中，本文拟采用人机交互的方式提高构件转换的质量。它以识别的可靠构件映射表M为输入，通过人机交互信息生成器将识别的可构件化程序部分及其可选的构件以友好的方式展示给程序员，并将程序选择好的结果传递给人机交互构件化转换模块，以生成通过构件化处理后加强的源程序，获得源代码本身质量的加强。

为获得较好的人机交互效果，需要将识别的构件与对应的程序片段以简单而精确的方式显示出来。为此，本文根据构件本身的特点，将构件的适用场景、需要的前提条件等应用相关的信息以xml的形式保存，当需要使用该构件时再通过xml解析器将信息分层显示，以便于程序员选择。

具体算法如算法2所示。

算法2人机交互的功能模块构件化映射方法

3 实验结果与分析

要提升源代码的可靠性，最重要的是尽可能地消除源代码中的漏洞。由于可靠构件是已经被证明的无漏洞代码，本文通过将源代码中可能存在漏洞的代码替换为语义等价的可靠构件，从而实现源代码可靠性的加强。因此，要获得源代码可靠性的加强，最关键的任务是自动识别出源代码中与漏洞代码对应的语义等价的可靠构件。

因此本文以Mibench[19]为基准测试用例集，以LLVM 3.9.0[20]为基础编译器，主要针对可靠构件识别的正确性和全面性，对基于编译前端分析自动构件化代码加强方法进行了实验，选择相似度值大于80%的值作为相似代码。其中代码相似性参数分别设置为：

为便于评估该方法的有效性，本文对Mibench测试用例集中的源程序进行了修改，人为加入了一些不可靠的代码，包括数组越界访问、野指针、空指针、内存泄漏四方面漏洞，每个测试用例中每种漏洞20个，并依据程序功能模块设计了对应的可靠构件库。

图2显示了本文方法相对于文献[21]方法对相似代码识别准确率的提升值。测试用例i类型j的漏洞，其识别准确度提升率V的计算如式（6）：

其中，SemSimloc(i,k)表示本文方法针对测试用例i第k个漏洞与对应的可靠构件源代码的相似度；SemSim[21](i,k)表示文献[21]的方法针对测试用例i第k个漏洞与对应的可靠构件源代码的相似度。

Fig.2 Recognition accuracy contrast图2 识别准确率对比

由以上实验结果可以看出，本文方法针对漏洞代码在规则化部分对文献[21]的方法进行了修正，因此获得的漏洞代码与可靠构件代码的相似度明显高于文献[21]。其中，野指针类漏洞识别度提升值最高达到了70%左右（即tiff2bw），最低也达到了10%左右（即ipell），平均识别率约为35%；对于内存泄漏类漏洞，识别度提升值最高达到了80%左右（即jpeg），最低也达到了35%左右（如crc32、fft），平均识别率约为55%；而针对数组越界、空指针类型的漏洞，由于增加了分支节点，修改了控制结构，使得在计算相似度时，本文方法比文献[21]方法有明显改善，对于数据越界和空指针类漏洞，大部分测试用例漏洞代码与可靠代码的相似度，本文方法比文献[21]方法提升了1倍以上，而对于测试用例dijkstra、gsm、blowfish的空指针类漏洞，jpeg和tiff2bw的数组越界类漏洞，识别相似度提升值均超过1.5倍，blowfish的空指针类漏洞，识别相似度提升值甚至接近2倍，有效提升了可靠构件对不可靠代码的自动匹配。

图3、图4分别显示了本文方法获得各测试用例对于注入漏洞的召回率和准确率。其中，正确率=提取出的正确漏洞数/提取出的漏洞总数；召回率=提取出的正确漏洞数/注入的漏洞总数。

Fig.3 Recall rate of vulnerability detection图3 漏洞检测的召回率

Fig.4 Correct rate of vulnerability detection图4 漏洞检测的正确率

由图3可以看出，由于本文方法是基于结构相似性进行对比，对于引起结构变化的漏洞，如空指针类的漏洞，需要增加对应的判断条件分支语句，召回率相对较低。但嵌入式系统控制语句较多，较小的结构差异不会对总体的相似度造成较大影响，因此总体的漏洞召回率较高，最低召回率可以达到85%（如测试用例jpeg、dijkstra），而其他的测试用例召回率均在90%以上。而对于其他类型的漏洞，所有测试用例的召回率均在90%以上，平均召回率超过了95%，特别是数值越界类漏洞，所有测试用例的召回率都达到了100%。由此可见，本文方法能够有效识别漏洞代码与对应的可靠构件，便于实现自动替换。

由图4可以看出，虽然程序函数块较多，但由于结构相似度大的块较少，本文方法检测的正确率较高，检测的正确率最低达到了87.2%（即测试用例basicmath），最高的达到了100%（即测试用例ispell、crc32、fft），平均约为94.5%，能够有效减少无效的人机交互，保证了本文方法的可用性和高效性。

4 结束语

随着嵌入式系统应用范围的不断扩大，特别是其广泛应用于关系国际民生的关键领域，其可靠性越来越受到人们的关注。针对嵌入式系统的可靠性，设计了一种基于编译前端分析自动构件化代码加强方法。本文方法结合构件化软件开发的思路，通过对源程序的分析，自动提取出其中可构件化成分，然后通过人机交互选择最合适的可靠构件进行映射，以最大程度提升源程序的质量。

实验结果表明，本文方法能够有效找出其中90%以上的漏洞，且正确率高达94.5%，这对于提升源程序本身的可靠性是十分有利的。

当然，可靠构件库本身的建立也是一个需要研究的方面。在实际应用中，一方面可以通过有经验的工程师根据应用领域的特点事先给出，然后利用完备的测试完成库的构建；另一方面可以在实践中根据具体的应用情况，将稳定可靠的代码块作为可靠构件入库。在后续的工作中将对可靠构件库的构建进行深入研究。