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

白 爍，周 晴

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

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

白 爍1，3，周 晴1，2

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

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

軟件測(cè)試；資源沖突；自動(dòng)檢測(cè)；嵌入式軟件

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

1 共享資源沖突情況分析

1.1 資源沖突類(lèi)型分析

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

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

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

圖1 引用--修改沖突

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

1.2 共享資源分析

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

圖3 修改--修改沖突

1.2.1 單字節(jié)變量

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

1.2.2 多字節(jié)變量

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

圖4 代碼實(shí)例

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

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

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

1.2.4 形 參

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

1.2.5 指 針

共享資源是大塊數(shù)據(jù)，軟件通常采用指針?lè)绞絹?lái)操作大塊數(shù)據(jù)，同理在對(duì)大塊數(shù)據(jù)進(jìn)行讀寫(xiě)操作時(shí)，若未進(jìn)行保護(hù)，也會(huì)造成資源沖突，引起數(shù)據(jù)不完整或不正確。

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

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

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

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

1）詞法分析

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

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

2）語(yǔ)法分析

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

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

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

③ 分析形成源代碼程序中聲明的所有的共享資源，包括資源名稱(chēng)及資源類(lèi)型。

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

3）語(yǔ)義分析

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

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

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

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

3 結(jié) 論

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

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

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

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

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

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

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

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

[8]航天.航天型號(hào)軟件測(cè)試[M].北京：宇航出版社，1999.

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

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

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

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

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

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

[15]蔡開(kāi)元.軟件可靠性工程基礎(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稿件編號(hào)：201601192

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