編譯前端分析自動構件化代碼可靠性加強方法*

葛紅美，徐 超+，何炎祥

1.南京審計大學 工學院，南京 211815

2.武漢大學 計算機學院，武漢 430072

1 引言

嵌入式系統(tǒng)主要以應用控制為主，根據具體的應用需求來制定系統(tǒng)的功能、結構、體積、組成等，具有系統(tǒng)內核小、專用性強、運行環(huán)境復雜、系統(tǒng)集成度高、運行穩(wěn)定可靠、時效性高等特點[1-2]。隨著信息時代的高速發(fā)展，嵌入式系統(tǒng)得到了最為廣泛的應用。小到電子手表、家用電器、自助取款機，大到汽車、火車、飛機、火箭，嵌入式系統(tǒng)已經深入到經濟、教育、科技和軍事的方方面面[3]。

對于嵌入式系統(tǒng)而言，可靠性是不容忽視的重要問題。嵌入式系統(tǒng)一旦出現(xiàn)故障，將會嚴重威脅到人們的生命財產和國防安全。在美國，僅僅因為一枚價值45美分的極小的集成電路失效，令北美防空聯(lián)合司令部指揮中心兩次發(fā)出虛假的進攻警報，造成一千枚洲際彈道導彈處于初級戒備狀態(tài)，全體軍官待命，多架戰(zhàn)斗機起飛。在歐洲，由于火箭設計師們忽略了軟件的可靠性，只重視火箭硬件的可靠性設計，導致火箭慣性制導系統(tǒng)軟件出現(xiàn)規(guī)格和設計錯誤，造成阿里亞那火箭升空40秒后自爆，損失5億英鎊。在美國，1983年科羅拉多州洪水泛濫，正是由于計算機發(fā)出錯誤預告，導致水庫被沖垮。在意大利，由于計算機設備存在故障，國家數(shù)據庫被破壞6秒鐘，需要6年才能修復。在中國，2011年7月23日甬溫線發(fā)生動車追尾事故，由于信號設備存在安全故障，造成35死210傷的悲劇。從以上事例可以看出，系統(tǒng)軟件的安全性、可靠性在嵌入式系統(tǒng)中占重要地位，如何加強嵌入式系統(tǒng)可靠性具有十分重要的研究價值，如何提高嵌入式系統(tǒng)的可靠性已經成為不容忽視的重要問題。

嵌入式系統(tǒng)軟件的可靠性是系統(tǒng)中非常重要的組成部分。隨著嵌入式系統(tǒng)智能化程度的不斷增強，嵌入式系統(tǒng)越來越復雜，其實現(xiàn)方式已由初始的匯編實現(xiàn)改為了高級語言（主要是C語言）實現(xiàn)。因此，要加強嵌入式系統(tǒng)的可靠性，首先必須對代碼進行加強，即提升代碼的可靠性，減少漏洞。

本文以編譯前端的語法語義分析為基礎，結合構件化技術，提出了一種多層次迭代分析可構件化代碼識別方法。該方法對C語言實現(xiàn)的嵌入式系統(tǒng)源代碼進行分析，通過對比當前源代碼和可靠構件代碼的相似性，找出其中相似度高的代碼塊。然后借助于人機交互技術，將其中某些未經驗證的程序轉為可靠構件的實現(xiàn)，利用可靠構件的可靠性獲得源代碼可靠性的加強。

本文組織結構如下：第2章介紹了編譯前端分析技術和構件化方法的相關背景知識；第3章重點闡述了基于編譯前端分析自動構件化代碼加強方法；第4章通過模擬實驗驗證了可靠性加強方法的效果；最后對全文進行了總結。

2 相關背景

2.1 基于編譯的代碼可靠性加強方法

由于源程序是嵌入式系統(tǒng)軟件的基本輸入，源程序本身的可靠程度直接決定了最終生成的目標代碼的質量。而編譯前端通過語法語義分析，掌握了源代碼結構和語義的全面信息，是對源程序較為全面的一種分析技術，因此不少學者以編譯器為基礎，對源代碼加強方法進行研究。目前的研究主要集中于代碼安全漏洞防范和代碼安全屬性證明這兩方面。

2.1.1 代碼漏洞防范技術

此類研究主要針對代碼中某種常見的安全漏洞，通過在編譯過程中對代碼進行修改，來防范安全漏洞可能引發(fā)的惡意攻擊。此類研究具有代表性的就是針對最常見的緩沖區(qū)溢出攻擊的StackGuard[4]和StackShield[5]方法。StackGuard通過編譯過程對程序進行修改，使其每次在調用函數(shù)時，將返回地址壓棧后，再將一個隨機產生字壓棧。當函數(shù)調用完畢后，查看此隨機字是否被修改，若改動，說明有溢出攻擊發(fā)生，則報警并停止程序運行。StackShield使用了另一種技術，它更改程序使其在運行時創(chuàng)建一個特別的堆棧，用來存儲函數(shù)返回地址的一份拷貝，并在受保護的函數(shù)開頭和結尾分別增加一段代碼，開頭處代碼用來將函數(shù)返回地址拷貝到這個特殊堆棧中，而結尾處代碼則用來將返回地址從特殊堆棧中拷貝回原程序運行堆棧。

代碼安全屬性證明方法研究主要針對編譯過程中程序的可靠性證明問題。其最具代表性的工作就是由Carnegie Mellon大學的Necula和Lee提出的攜帶證明的代碼（proof carrying code，PCC）[6-7]，此方法主要用于驗證代碼是否遵循預先定義的某些安全性條件。PCC提出了一種程序驗證框架，首先在代碼發(fā)送方，根據用戶所提安全條件，對代碼進行分析，產生一種安全形式化證明信息，并將此信息“證書”附加于原始代碼上形成攜帶證明的代碼；在代碼接收方，根據相同安全條件，參照PCC中的“證書”，對代碼進行驗證，如果通過驗證，則認為此代碼是可靠的，允許執(zhí)行。PCC中安全條件均采用一階邏輯謂詞進行描述，證明過程采用邏輯推理的方法，代碼驗證通過類型檢查機制實現(xiàn)。PCC主要用于移動通信中代碼的驗證。PCC對源代碼沒有做任何修改，只是將安全性證明信息附加在代碼中，供代碼使用者驗證所用。但是PCC存在“證書”代碼量過大的問題，一般為待驗證代碼量的3到7倍，嚴重影響了驗證效率。與PCC相似，Cornell大學的Kozen帶領的研究小組提出了ECC（efficient code certification）[8-9]，一種簡單有效的程序驗證方法。ECC也可以看作是一種攜帶證明的代碼驗證方法，只是它的“證書”不是完整的形式化證明過程，而只是一些證明的引導信息。ECC可以保證通過驗證的代碼具有控制流安全、內存安全、堆棧安全等特性。最重要的是，ECC可采用對已有編譯器進行修改的方式實現(xiàn)。雖然ECC對代碼安全性的描述能力沒有PCC強，但是其證明過程更加簡單，驗證過程效率更高。該類方法還可以應用于編譯器本身的可靠性驗證、編譯優(yōu)化可靠性驗證以及運行嵌入式系統(tǒng)可靠性加強[10-18]。

2.1.2 構件化

構件化開發(fā)是將一個個相對獨立的、被充分證明為可靠的構件，通過給定的標準接口進行組裝，形成滿足對應功能軟件的開發(fā)方法。它不但能有效提升軟件開發(fā)效率，而且由于每個構件已經經過了充分驗證，有效避免了不同軟件開發(fā)人員由于個人編程經驗不足而導致的不可靠性，使得生成的軟件具有較高的質量。不少國內外公司和組織制定了相應的構件標準，如微軟的COM、Oracle的JavaBean、OMG組織的CORBA（common object request broker architecture）等。

但構件是嚴格封裝的，完全使用構件化進行嵌入式系統(tǒng)開發(fā)在一定程度上限制了軟件開發(fā)的靈活性，這對于希望盡可能高效地利用各種資源的嵌入式系統(tǒng)是極其不利的。因此，如果能夠在已有源代碼的基礎上提取出其中可構件化的代碼進行優(yōu)化，不但保持了嵌入式程序的靈活性，而且對于嵌入式程序可靠性的提升將有著顯著作用。

本文將結合構件化軟件開發(fā)的方法，通過對源程序的分析，提取出其中可構件化成分，然后選擇最合適的構件進行映射，以最大程度提升源程序的質量。其中，可構件化代碼識別和使用何種構件進行代碼映射是確保源程序質量最為關鍵的兩個步驟，本文將重點研究這兩個過程。

2.2 編譯前端分析自動構件化代碼加強方法

為提高源程序本身的可靠性，緩解由于程序員本身經驗缺乏導致的代碼不可靠性以及實現(xiàn)的低效率性，本文設計了一種基于編譯前端分析自動構件化的代碼加強技術。該方法首先對編譯器前端預處理器之后的源程序進行分析，然后借助于一套可靠構件庫，根據其結構特征，采用模糊匹配的方式，從源程序中識別出與可靠構件相似程度高的代碼塊。

由于采用的是基于程序結構相似度進行的模糊匹配，識別的源程序并不一定具備可構件化的能力。而且同一段代碼也許會有針對不同使用場景的多種實現(xiàn)方式，對于識別的源程序模塊具體該使用哪個可靠構件進行替換需要程序員根據具體的應用場景才能確定。因此，在識別了可構件化的程序片段后，將利用人機交互的方式確定該程序片段是否可以使用可靠構件進行替換，以及使用哪個構件進行替換更為合適。

該方法的總體框架如圖1所示，主要包括兩個過程：多層次迭代分析可構件化代碼識別和基于人機交互的功能模塊構件化映射。

2.2.1 多層次迭代分析可構件化代碼識別方法

對于可構件化代碼識別過程，本文擬采用一種多層次迭代分析的方法對源程序中可構件化部分進行識別。該方法以函數(shù)為識別的基本單位，從最底層函數(shù)（即函數(shù)調用關系圖中的葉子節(jié)點）開始，依次向上迭代分析，利用可靠構件集查找源程序中可構件化部分。

如圖1所示，首先對預處理后代碼進行分析，構件函數(shù)調用關系圖（函數(shù)調用圖中每個節(jié)點表示源程序中一個函數(shù)，每條邊表示函數(shù)調用關系）。然后，對該圖中第0層節(jié)點進行分析，計算該節(jié)點同可靠構件集中的每個構件在程序結構上的相似度，并保存相似度大于閾值的節(jié)點作為該節(jié)點可選構件。接著分析第1層中的節(jié)點，識別其中可構件化的節(jié)點保存到可靠構件化映射表中。以此迭代分析，直到第n層。其中，第n層節(jié)點是指該節(jié)點到最遠葉子節(jié)點的路徑上經過的節(jié)點數(shù)目。

在該步驟中，代碼相似度檢測是核心，本文主要基于文獻[21]中使用的代碼相似度計算方法，檢測包含以下3個步驟：

（1）分析源程序，將其轉化為具有數(shù)據流和控制流信息的抽象中間表示形式，如抽象語法樹（abstract syntax tree，AST）；

（2）應用變換法則對中間表示形式進行規(guī)范化處理，以便降低理解的復雜度；

Fig.1 Code reliability enhancement method based on automatic component and compiler front-end analysis圖1 基于編譯前端分析自動構件化代碼加強方法

（3）分析規(guī)范化處理結果，識別出程序中包含的語義及知識信息，然后進行分析與推理，獲取程序設計者的意圖。

但由于待檢測的代碼是可能包含缺陷的嵌入式代碼，在步驟（2）進行代碼規(guī)則化處理時，忽略了以下3類語句：

（1）如果控制語句是針對數(shù)組索引值的判斷或空指針的判斷，則忽略該控制語句；

（2）如果內存申請與釋放語句（如malloc、free等），則忽略該語句；

（3）如果是針對指針賦值為空的操作，則忽略該語句。

同時，由于本文的可靠構件主要是基于函數(shù)進行封裝的，在對函數(shù)進行分析時，不再進行遞歸展開，而是將其作為一個普通順序節(jié)點進行處理。

代碼之間的相似度按照規(guī)模相似度SizeS、結構相似度StructS、語句相似度StateS和知識點相似度PivotS這4個維度進行計算，具體公式如下：

算法1描述了多層次迭代分析查找源代碼與可靠構件相似代碼的具體過程。

算法1多層次迭代分析可構件化算法

下面詳細分析4個維度相似度的計算方法及權重選擇策略。

2.2.2 規(guī)模相似度

規(guī)模相似度計算時將程序分為4種類型：循環(huán)語句、選擇語句、賦值語句和其他語句。然后遍歷AST樹，統(tǒng)計各類語句節(jié)點的個數(shù)，得到待檢測代碼規(guī)模向量Vs和所有可靠構件代碼規(guī)模向量Vt。最后按照式（2）計算規(guī)模相似度。

規(guī)模相似度主要衡量不同代碼塊之間各種類型語句在數(shù)量上的一致性，并不分析具體語義。

2.2.3 結構相似度

結構相似度主要衡量待檢測代碼AST樹與可靠構件代碼AST樹在樹結構上的相似度。

定義兩棵樹T1、T2的節(jié)點對(v1,v2)是匹配節(jié)點，當且僅當：（1）v1與v2具有相同的符號，即相同的類型、運算符、被調用的函數(shù)名；（2）v1、v2的父節(jié)點是匹配節(jié)點對；（3）假設w1和w2是匹配節(jié)點對，v1與w1是兄弟節(jié)點，v2與w2是兄弟，那么如v1在w1前出現(xiàn)，則v2在w2前出現(xiàn)；（4）v1至多能和T2中的1個節(jié)點匹配，v2至多能和T1中的1個節(jié)點匹配。

因此，求待檢測代碼與可靠構件代碼結構相似度問題，即可轉為兩棵AST樹節(jié)點匹配問題。本文將借助文獻[21]的方法對結構匹配程度進行計算，最后按照式（3）計算結構相似度。其中StructMatch（S,T）表示樹S（待檢測代碼的AST樹）和樹T（可靠構件代碼的AST樹）匹配的節(jié)點數(shù)目。

2.2.4 語句相似度和知識點相似度

語句相似度和知識點相似度主要是為了進一步突出語義的相似性而增加的額外維度。程序語義通常由表達式或者功能函數(shù)進行描述，因此語句相似度則強調比較待檢測代碼與可靠構件代碼在表達式上的相似程度，而知識點相似度則強調比較待檢測代碼與可靠構件代碼在函數(shù)調用方面的相似度。它們都是在結構相似度的基礎上，專門針對表達式節(jié)點、函數(shù)調用節(jié)點的相似程度重新進行計算得到的。

具體計算時，算法依次遍歷匹配AST樹，獲得待檢測代碼中表達式節(jié)點和函數(shù)調用節(jié)點的數(shù)目Gst和Gpv。然后遍歷結構相似節(jié)點，如果該節(jié)點是表達式節(jié)點，則將valuest加1；如果是相同函數(shù)調用節(jié)點，則將 valuepv值加1。最后分別根據式（4）和式（5）計算語句相似度和知識點相似度。

2.2.5 權重參數(shù)的選擇

由于規(guī)模相似度主要衡量不同代碼塊之間各種類型語句在數(shù)量上的一致性，并不分析具體語義，其權重值不宜設置較大。

同時，語句相似度和知識點相似度均是在結構相似度的基礎上針對語義進行的強化，因此這兩個維度的值也不宜設置較大。

結構相似度既包含了代碼形式上的相似，同時也兼顧了語義方面的內容，其對于代碼相似度的評估最為全面，因此其權重值可以設置為較大值。

在實驗時，將 u1、u3、u4的值設置為0.1，將 u2的值設置為0.7。

2.3 基于人機交互的功能模塊構件化映射

在對識別的可構件化代碼進行構件化的過程中，本文擬采用人機交互的方式提高構件轉換的質量。它以識別的可靠構件映射表M為輸入，通過人機交互信息生成器將識別的可構件化程序部分及其可選的構件以友好的方式展示給程序員，并將程序選擇好的結果傳遞給人機交互構件化轉換模塊，以生成通過構件化處理后加強的源程序，獲得源代碼本身質量的加強。

為獲得較好的人機交互效果，需要將識別的構件與對應的程序片段以簡單而精確的方式顯示出來。為此，本文根據構件本身的特點，將構件的適用場景、需要的前提條件等應用相關的信息以xml的形式保存，當需要使用該構件時再通過xml解析器將信息分層顯示，以便于程序員選擇。

具體算法如算法2所示。

算法2人機交互的功能模塊構件化映射方法

3 實驗結果與分析

要提升源代碼的可靠性，最重要的是盡可能地消除源代碼中的漏洞。由于可靠構件是已經被證明的無漏洞代碼，本文通過將源代碼中可能存在漏洞的代碼替換為語義等價的可靠構件，從而實現(xiàn)源代碼可靠性的加強。因此，要獲得源代碼可靠性的加強，最關鍵的任務是自動識別出源代碼中與漏洞代碼對應的語義等價的可靠構件。

因此本文以Mibench[19]為基準測試用例集，以LLVM 3.9.0[20]為基礎編譯器，主要針對可靠構件識別的正確性和全面性，對基于編譯前端分析自動構件化代碼加強方法進行了實驗，選擇相似度值大于80%的值作為相似代碼。其中代碼相似性參數(shù)分別設置為：

為便于評估該方法的有效性，本文對Mibench測試用例集中的源程序進行了修改，人為加入了一些不可靠的代碼，包括數(shù)組越界訪問、野指針、空指針、內存泄漏四方面漏洞，每個測試用例中每種漏洞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 識別準確率對比

由以上實驗結果可以看出，本文方法針對漏洞代碼在規(guī)則化部分對文獻[21]的方法進行了修正，因此獲得的漏洞代碼與可靠構件代碼的相似度明顯高于文獻[21]。其中，野指針類漏洞識別度提升值最高達到了70%左右（即tiff2bw），最低也達到了10%左右（即ipell），平均識別率約為35%；對于內存泄漏類漏洞，識別度提升值最高達到了80%左右（即jpeg），最低也達到了35%左右（如crc32、fft），平均識別率約為55%；而針對數(shù)組越界、空指針類型的漏洞，由于增加了分支節(jié)點，修改了控制結構，使得在計算相似度時，本文方法比文獻[21]方法有明顯改善，對于數(shù)據越界和空指針類漏洞，大部分測試用例漏洞代碼與可靠代碼的相似度，本文方法比文獻[21]方法提升了1倍以上，而對于測試用例dijkstra、gsm、blowfish的空指針類漏洞，jpeg和tiff2bw的數(shù)組越界類漏洞，識別相似度提升值均超過1.5倍，blowfish的空指針類漏洞，識別相似度提升值甚至接近2倍，有效提升了可靠構件對不可靠代碼的自動匹配。

圖3、圖4分別顯示了本文方法獲得各測試用例對于注入漏洞的召回率和準確率。其中，正確率=提取出的正確漏洞數(shù)/提取出的漏洞總數(shù)；召回率=提取出的正確漏洞數(shù)/注入的漏洞總數(shù)。

Fig.3 Recall rate of vulnerability detection圖3 漏洞檢測的召回率

Fig.4 Correct rate of vulnerability detection圖4 漏洞檢測的正確率

由圖3可以看出，由于本文方法是基于結構相似性進行對比，對于引起結構變化的漏洞，如空指針類的漏洞，需要增加對應的判斷條件分支語句，召回率相對較低。但嵌入式系統(tǒng)控制語句較多，較小的結構差異不會對總體的相似度造成較大影響，因此總體的漏洞召回率較高，最低召回率可以達到85%（如測試用例jpeg、dijkstra），而其他的測試用例召回率均在90%以上。而對于其他類型的漏洞，所有測試用例的召回率均在90%以上，平均召回率超過了95%，特別是數(shù)值越界類漏洞，所有測試用例的召回率都達到了100%。由此可見，本文方法能夠有效識別漏洞代碼與對應的可靠構件，便于實現(xiàn)自動替換。

由圖4可以看出，雖然程序函數(shù)塊較多，但由于結構相似度大的塊較少，本文方法檢測的正確率較高，檢測的正確率最低達到了87.2%（即測試用例basicmath），最高的達到了100%（即測試用例ispell、crc32、fft），平均約為94.5%，能夠有效減少無效的人機交互，保證了本文方法的可用性和高效性。

4 結束語

隨著嵌入式系統(tǒng)應用范圍的不斷擴大，特別是其廣泛應用于關系國際民生的關鍵領域，其可靠性越來越受到人們的關注。針對嵌入式系統(tǒng)的可靠性，設計了一種基于編譯前端分析自動構件化代碼加強方法。本文方法結合構件化軟件開發(fā)的思路，通過對源程序的分析，自動提取出其中可構件化成分，然后通過人機交互選擇最合適的可靠構件進行映射，以最大程度提升源程序的質量。

實驗結果表明，本文方法能夠有效找出其中90%以上的漏洞，且正確率高達94.5%，這對于提升源程序本身的可靠性是十分有利的。

當然，可靠構件庫本身的建立也是一個需要研究的方面。在實際應用中，一方面可以通過有經驗的工程師根據應用領域的特點事先給出，然后利用完備的測試完成庫的構建；另一方面可以在實踐中根據具體的應用情況，將穩(wěn)定可靠的代碼塊作為可靠構件入庫。在后續(xù)的工作中將對可靠構件庫的構建進行深入研究。