白 爍，周 晴

（1.中國科學(xué)院國家空間科學(xué)中心 北京100190；2.北京理工大學(xué) 北京100181；3.中國科學(xué)院大學(xué) 北京100190）

嵌入式軟件資源沖突自動檢測系統(tǒng)設(shè)計

白 爍1，3，周 晴1，2

（1.中國科學(xué)院國家空間科學(xué)中心 北京100190；2.北京理工大學(xué) 北京100181；3.中國科學(xué)院大學(xué) 北京100190）

由于在眾多的軟件測試工具中，能自動檢測共享資源沖突的軟件非常少，而共享資源沖突問題是嵌入式軟件研制中最常犯的、最不易發(fā)現(xiàn)、隱藏最深的問題之一，同時該問題一旦發(fā)生，帶來的影響后果也極為嚴(yán)重，可能導(dǎo)致軟件無法正常運行。為了解決這一問題，本文分析了共享資源沖突情況，并提出了一種針對嵌入式軟件共享資源沖突問題檢測的方案，使用C#語言編程，實現(xiàn)了自動檢測系統(tǒng)，并進行了相關(guān)驗證。

軟件測試；資源沖突；自動檢測；嵌入式軟件

目前嵌入式軟件應(yīng)用越來越廣泛。軟件規(guī)模日益龐大、結(jié)構(gòu)趨于復(fù)雜，對軟件測試水平提出了更高的要求[1]。在嵌入式系統(tǒng)中，由于系統(tǒng)高實時性要求，經(jīng)常使用嵌入式實時操作系統(tǒng)和中斷技術(shù)，使專用軟件操作更加靈活，功能更加強大，但同時這也可能會導(dǎo)致共享資源沖突。這種沖突在早期不易被人發(fā)現(xiàn)，在運行中一旦發(fā)生造成的后果是嚴(yán)重的，可能引入系統(tǒng)崩潰[2]。目前對于軟件共享資源沖突檢測的軟件少之又少，主要通過人工代碼走查來檢測資源沖突，過于依賴測試人員的個人經(jīng)驗，漏檢概率較大[3]?；凇霸鐪y試、早發(fā)現(xiàn)”的原則[4]，本設(shè)計采用靜態(tài)分析的方法，通過詞法分析、語法分析、語義分析以及軟件并發(fā)性分析，在軟件開發(fā)早期對代碼進行自動檢測，判斷是否存在共享資源沖突問題[5]。本系統(tǒng)主要針對嵌入式軟件中最常用的 80C51系統(tǒng)和VxWorks系統(tǒng)而設(shè)計的。

1 共享資源沖突情況分析

1.1 資源沖突類型分析

資源沖突產(chǎn)生的根本原因是在嵌入式軟件中存在不同優(yōu)先級的任務(wù)或中斷，低優(yōu)先級任務(wù)運行至任意位置隨時可能被高優(yōu)先級任務(wù)或中斷打斷。若軟件對共享資源保護不足，即資源在使用（引用或修改）前未關(guān)中斷，使用后開中斷，將導(dǎo)致不同級別任務(wù)使用的同一資源數(shù)據(jù)不一致或不完整，甚至錯誤。

資源沖突歸為3種類型：引用——修改沖突，修改——引用沖突，修改——修改沖突[6]。

1）引用——修改沖突即正在運行的函數(shù)中引用某共享資源時，被響應(yīng)的高優(yōu)先級函數(shù)或中斷函數(shù)修改了該共享資源。如圖1所示，圖1左中的函數(shù)引用了共享資源a，圖1右中的優(yōu)先級高的中斷函數(shù)中修改了共享資源a，會造成資源引用沖突。Start函數(shù)中y運行的結(jié)果并不是期望的8，而是中斷修改后的1。

圖1 引用--修改沖突

2）修改——引用沖突即正在運行的函數(shù)中修改某共享資源時，被響應(yīng)的高優(yōu)先級函數(shù)或中斷函數(shù)引用了該共享資源。如圖2所示，左圖中的函數(shù)修改了共享資源a，當(dāng)i=1，a[1]=1；之后被優(yōu)先級高的中斷打斷，右圖中的優(yōu)先級高的中斷函數(shù)中引用了共享資源a，出現(xiàn)數(shù)組b并不與數(shù)組a一致（a[3]= {1，2，3}，b[3]={1，0，0}），導(dǎo)致數(shù)組b獲取數(shù)組a數(shù)據(jù)不完整。

圖2 修改--引用沖突

3）修改——修改沖突即正在運行的函數(shù)中修改某共享資源時，被響應(yīng)的高優(yōu)先級函數(shù)或中斷函數(shù)修改了該共享資源。如圖3所示，左圖中的函數(shù)修改了共享資源a，當(dāng)i=1，a[1]=1；之后被優(yōu)先級高的中斷打斷，右圖中的優(yōu)先級高的中斷函數(shù)中也修改了共享資源a[0]，會造成資源不一致。Start函數(shù)中數(shù)組a運行結(jié)果并不是期望的0、1、2，而變?yōu)?、1、2。

1.2 共享資源分析

通過分析，歸納出以下幾種發(fā)生沖突的共享資源的形式：

圖3 修改--修改沖突

1.2.1 單字節(jié)變量

嵌入式軟件中，在內(nèi)部存儲區(qū)定義的單字節(jié)變量，若未進行資源保護，會引起引用——修改；在外部存儲區(qū)定義的單字節(jié)變量，通過編譯后實質(zhì)也是執(zhí)行多條語句，則可能會發(fā)生引用——修改、修改——引用或修改——修改類型3種類型的共享資源沖突。

1.2.2 多字節(jié)變量

共享資源是多字節(jié)變量，如果未進行資源保護，也會發(fā)生同類錯誤。如圖4所示的CPU為80C32單片機的代碼實例中，變量X_PowerOnCount定義為整型2字節(jié)，由于指令數(shù)據(jù)都是按字節(jié)操作，主程序讀取X_PowerOnCount實際是分為兩步，先讀低字節(jié)再讀高字節(jié)。期間若發(fā)生中斷，中斷服務(wù)程序改寫該變量， 程序會出錯。 假定主程序訪問變量X_PowerOnCount值為0x12FC時，主程序首先讀取了低字節(jié) 0xFC，此時中斷發(fā)生該變量改寫為0x1310，中斷返回后主程序讀取的值為0x13FC，導(dǎo)致主函數(shù)代碼執(zhí)行出錯，發(fā)生引用——修改沖突。

圖4 代碼實例

1.2.3 寄存器地址（包括宏定義的地址）

在嵌入式軟件中，軟件可以直接讀取寄存器地址（包括宏定義的地址）的數(shù)據(jù)，因此寄存器地址（包括宏定義的地址）也是一種共享資源。下面給出一個寄存器地址發(fā)生共享資源沖突的例子。圖5為某嵌入式軟件的主循環(huán)程序流程圖，圖6為該嵌入式軟件的其中一個中斷服務(wù)程序流程圖。由圖5和圖6可以看出，當(dāng)主循環(huán)從“讀取CAN狀態(tài)寄存器（B）”到“關(guān)閉中斷”準(zhǔn)備發(fā)送數(shù)據(jù)幀前，中斷服務(wù)程序判斷CAN芯片不為發(fā)送狀態(tài)且芯片發(fā)送緩沖區(qū)為空閑，則向CAN芯片寫入一幀數(shù)據(jù)。當(dāng)中斷服務(wù)程序執(zhí)行結(jié)束后，主循環(huán)從被中斷語句繼續(xù)執(zhí)行，這是主循環(huán)依據(jù)“讀取CAN狀態(tài)寄存器（B）”獲得的過時狀態(tài)，判斷出CAN芯片不是發(fā)送狀態(tài)且芯片發(fā)送緩沖區(qū)為空閑，主循環(huán)錯誤地向CAN芯片寫入一幀新數(shù)據(jù)。因此，造成由于中斷已向CAN芯片寫入一幀數(shù)據(jù)，發(fā)送尚未正常結(jié)束時主循環(huán)又向其寫入另一幀數(shù)據(jù)，導(dǎo)致先寫入的數(shù)據(jù)被覆蓋或后寫入的數(shù)據(jù)丟失。發(fā)生修改——修改沖突。

圖5 主循環(huán)程序流程圖

1.2.4 形 參

上述單字節(jié)、多字節(jié)公共變量、寄存器地址在函數(shù)中，若以形參方式進行傳遞，可能在被調(diào)用的函數(shù)內(nèi)發(fā)生引用或修改，若未進行資源保護，可能會造成隱式的共享資源沖突。

1.2.5 指 針

共享資源是大塊數(shù)據(jù)，軟件通常采用指針方式來操作大塊數(shù)據(jù)，同理在對大塊數(shù)據(jù)進行讀寫操作時，若未進行保護，也會造成資源沖突，引起數(shù)據(jù)不完整或不正確。

圖6 中斷服務(wù)程序流程圖

2 系統(tǒng)實現(xiàn)方案

本系統(tǒng)針對上述類型沖突完成自動檢測，采用C#語言，使用SQL Server數(shù)據(jù)庫記錄中間結(jié)果。系統(tǒng)的體系結(jié)構(gòu)分為前端的winform界面、后端的數(shù)據(jù)搜索以及數(shù)據(jù)分析。從前端界面加載代碼，由后端程序處理數(shù)據(jù)，再由前端界面顯示結(jié)果。系統(tǒng)的總體流程圖如圖7所示。

圖7 系統(tǒng)流程圖

1）詞法分析

對源程序文本文件進行掃描，提煉關(guān)鍵詞，詞是語言中具有獨立意義的最小單位。對關(guān)鍵詞進行詞法分析，識別包括關(guān)鍵字、標(biāo)識符、運算符、界符、常量和變量等。

由于除C語言中固定的關(guān)鍵字外，程序員可能會自定義變量類型和關(guān)鍵字（例如：#define LOCALstatic；typedefsigned charINT8），所以也需要掃描、識別出程序員自定義的變量類型及關(guān)鍵字。此外，還需查找出程序員聲明的結(jié)構(gòu)體以及共用體，以便進行語法分析時使用。

2）語法分析

本系統(tǒng)采用自頂向下的語法分析方法，即給定文法G和源程序串r。從G的開始符號S出發(fā)，通過反復(fù)使用產(chǎn)生式對句型中的非終結(jié)符進行替換 （推導(dǎo)），逐步推導(dǎo)出r。在完成詞法分析基礎(chǔ)上，進一步進行語法分析，包括：

① 提取出該源代碼中所有的函數(shù)，并獲取每個函數(shù)的基本信息，包括函數(shù)名稱、函數(shù)所在文件，函數(shù)所在的任務(wù)。

②利用①中的分析結(jié)果進行二次分析，獲取該程序中所有任務(wù)的信息，包括任務(wù)名稱、任務(wù)優(yōu)先級及每個任務(wù)所調(diào)用的函數(shù)。

③ 分析形成源代碼程序中聲明的所有的共享資源，包括資源名稱及資源類型。

④ 利用以上三條分析結(jié)果，獲取所有共享資源的使用情況，包括共享資源名稱、使用該資源的函數(shù)、所在的任務(wù)名稱及讀寫情況。

3）語義分析

在語法分析基礎(chǔ)上，進行一步分析獲得所有共享資源的使用情況，包括共享資源名稱、使用該資源的函數(shù)、所在的任務(wù)名稱及共享資源在不同函數(shù)中讀寫情況。中斷服務(wù)程序也可看成是一種任務(wù)。

4）軟件并發(fā)性分析

本階段是一個邏輯判斷過程，依據(jù)前文提及的共享資源沖突分析形成沖突規(guī)則集，對共享資源使用情況進行規(guī)則檢查，分析是否有同一共享資源同時出現(xiàn)在了兩個優(yōu)先級不同的任務(wù)中。若違反規(guī)則則給出初步警告。

根據(jù)給出的警告信息，逐條返回到優(yōu)先級較低的函數(shù)中，查看被測軟件在使用該資源前是否關(guān)閉中斷或者禁止高優(yōu)先級任務(wù)搶占，若沒有則提醒該共享資源會發(fā)生沖突。

3 結(jié) 論

根據(jù)以上方案，編程實現(xiàn)了針對C51系統(tǒng)及VxWorks系統(tǒng)檢測共享資源沖突的測試工具。本設(shè)計對某嵌入式軟件的源代碼進行共享資源沖突測試，結(jié)果顯示該系統(tǒng)可以提示出該軟件的源代碼中可能發(fā)生的包括引用——修改、修改——引用及修改——修改這三種類型的共享資源沖突問題的共享資源名稱及使用該共享資源的函數(shù)及所在任務(wù)、讀寫操作等信息。本系統(tǒng)可對單字節(jié)變量、多字節(jié)變量、形參及寄存器地址類型的共享資源進行自動檢測。下一階段將完成對指針類型的共享資源進行檢測。

[1]單錦輝，姜瑛，孫萍.軟件測試研究進展[J].北京大學(xué)學(xué)報：自然科學(xué)版，2005（1）：134-145.

[2]王雅文，宮云戰(zhàn)，楊朝紅.軟件測試工具綜述[J].北京化工大學(xué)學(xué)報，2007（S1）：1-4.

[3]金凌紫.面向?qū)ο筌浖y試技術(shù)進展[J].計算機研究與發(fā)展，1998（1）：6-13.

[4]宋穎.面向嵌入式C的軟件缺陷檢測技術(shù)的研究與實現(xiàn)[D].北京：北京郵電大學(xué)，2011.

[5]文昌辭，王昭順.軟件測試自動化靜態(tài)分析研究[J].計算機工程與設(shè)計，2005（4）：987-989.

[6]楊芳，齊璇，董麗，等.嵌入式軟件中斷系統(tǒng)資源沖突檢測技術(shù)研究[J].計算機工程與設(shè)計，2010，31（23）：5036-5038.

[7]人杰.計算機軟件測試技術(shù)[M].北京：清華大學(xué)出版社，1992.

[8]航天.航天型號軟件測試[M].北京：宇航出版社，1999.

[9]朱少民.軟件測試方法和技術(shù)[M].北京：清華大學(xué)出版社有限公司，2005.

[10]R.·帕頓（美），Patton R，周予濱，等.軟件測試[M].北京：機械工業(yè)出版社，2002.

[11]鞠秀娟，趙明.軟件自動化測試概述及應(yīng)用工具分析[J].計算機應(yīng)用，2007，27（B06）:317-318.

[12]楊宇，張健.程序靜態(tài)分析技術(shù)與工具[J].計算機科學(xué)，2004，31（2）:171-174.

[13]張健.精確的程序靜態(tài)分析[J].計算機學(xué)報，2008，31（9）:1549-1553..

[14]錫滋.軟件可靠性，安全性與質(zhì)量保證 [M].北京：電子工業(yè)出版社，2002.

[15]蔡開元.軟件可靠性工程基礎(chǔ)[M].北京：清華大學(xué)出版社，1995.

Design of resource conflicts detection system for embedded software

BAI Shuo1，3，ZHOU Qing1，2
（1.National Space Science Center.CAS，Beijing 100190，China 2.Beijing Institute of Technology，Beijing 100181，China；3.University of Chinese Academy of Sciences，Beijing 100190，China）

Among the many software testing tools，the number of detecting shared resources conflict is very small，but the problem of shared resource conflict is often happened and is hard to be discovered，which can lead to serious consequences.In order to find the problem of the software as soon as possible，the conflicts are firstly analyzed，and then a scheme of testing shared resource conflicts for embedded software is brought forward，which can realize automatic detection.

software testing；resource conflicts；automatic detection；embedded software

TN0

：A

：1674－6236（2017）05-0061-04

2016-01-21稿件編號：201601192

白 爍（1990—），女，河北衡水人，碩士研究生。研究方向：軟件測試。