黃 晨，董 燕，王小麗，虞礪琨

(北京控制工程研究所，北京100190)

基于表格的中斷數(shù)據(jù)沖突靜態(tài)分析方法*

黃 晨，董 燕，王小麗，虞礪琨

(北京控制工程研究所，北京100190)

中斷沖突問題是星載嵌入式軟件較為典型的缺陷之一，由于中斷沖突發(fā)生的不確定性和隨機(jī)性，在動態(tài)測試過程中難以復(fù)現(xiàn)和定位.介紹一種基于表格的中斷沖突靜態(tài)分析方法，專門針對數(shù)據(jù)關(guān)聯(lián)性、操作關(guān)聯(lián)性、時序沖突以實例的方式給出分析方法和過程，并總結(jié)幾種預(yù)防中斷沖突常見的設(shè)計策略和方法.相比較動態(tài)測試需要在特定的場景才能發(fā)現(xiàn)的數(shù)據(jù)沖突問題，靜態(tài)分析方法在設(shè)計和測試階段實施更加容易、高效.

中斷沖突;數(shù)據(jù)關(guān)聯(lián)性;操作關(guān)聯(lián)性;時序沖突

0 引言

星載嵌入式軟件多為中斷驅(qū)動型，即主程序加中斷的程序結(jié)構(gòu)，屬于非常典型的實時并發(fā)軟件，要求能夠?qū)崟r處理各種隨機(jī)任務(wù)和完成多種計算活動.但是由于中斷觸發(fā)的隨機(jī)性和不確定性，在設(shè)計和實現(xiàn)過程中很容易引入軟件錯誤，導(dǎo)致一系列不易追蹤且難以發(fā)現(xiàn)和定位的嚴(yán)重軟件故障.針對某些特定的數(shù)據(jù)或者時序才會出現(xiàn)的訪問沖突問題，如果用例設(shè)計不當(dāng)或者測試結(jié)果數(shù)據(jù)分析不當(dāng)時較難發(fā)現(xiàn)，此時采用靜態(tài)的分析方法反而更容易發(fā)現(xiàn)和定位.

目前中斷沖突、數(shù)據(jù)競爭等相關(guān)問題在工程和研究領(lǐng)域引起了諸多關(guān)注，文獻(xiàn)［1］提出了一種基于啟發(fā)式的靜態(tài)中斷數(shù)據(jù)競爭檢測方法，能夠自動推斷中斷優(yōu)先級狀態(tài)、中斷使能狀態(tài)和內(nèi)存訪問狀態(tài)等信息，提高人工確認(rèn)結(jié)果的效率.文獻(xiàn)［2］提出了一種基于變量訪問序模式的中斷數(shù)據(jù)競爭檢測方法，針對單變量訪問序模式，基于抽象解釋，提出一種支持過程間分析、中斷并發(fā)分析的高效檢測方法.文獻(xiàn)［1-2］的研究重點在于提高計算機(jī)自動識別代碼通用數(shù)據(jù)競爭沖突的準(zhǔn)確性、高效性.文獻(xiàn)［3］專門針對C51語言軟件中幾種較為典型的中斷資源訪問沖突問題進(jìn)行分析研究，其實施與選用的編譯器具有較大的關(guān)系.

有些數(shù)據(jù)沖突場景依賴于應(yīng)用背景僅通過工具是較難或者無法發(fā)現(xiàn)的，為避免自動分析工具在分析時出現(xiàn)遺漏情況，且不依賴于選用的編譯器，本文詳細(xì)描述了一種基于表格的中斷沖突分析方法，在制定中斷屬性和資源分析列表的基礎(chǔ)上，結(jié)合具體實例給出數(shù)據(jù)相關(guān)性、操作相關(guān)性和時序沖突分析方法，從沖突問題產(chǎn)生的機(jī)理上給出分析和解釋，最后給出了幾種常見的預(yù)防規(guī)避措施.

1 中斷沖突基本模型

雖然中斷能較好地滿足實時性的要求，但是如果對中斷的實現(xiàn)機(jī)理認(rèn)識不清或者使用不當(dāng)，也會引入軟件錯誤，比如中斷沖突問題.所謂中斷沖突即主程序和中斷之間，或者可嵌套的兩個中斷:低優(yōu)先級和高優(yōu)先級中斷同時對同一個資源(如內(nèi)存單元)進(jìn)行訪問，且至少有一個訪問是寫操作［1］.

沖突體現(xiàn)在代碼針對某個或某些共享資源發(fā)生了競爭訪問而造成程序錯誤［4］.如果某個資源在被讀取的過程中“被打斷”進(jìn)行寫操作或在被寫的過程中“被打斷”進(jìn)行讀取或重寫操作，則可能存在訪問沖突.“被打斷”包括主程序中的資源被某個中斷服務(wù)子程序打斷、一個中斷服務(wù)子程序的資源被某個高級中斷服務(wù)子程序打斷等情況［5-8］，因此，中斷沖突需要結(jié)合中斷及優(yōu)先級分析.通常，中斷程序使用的資源主要包括:單字節(jié)變量、多字節(jié)變量、緩沖區(qū)、數(shù)組、I/O端口、寄存器等.

圖1 中斷沖突基本模型Fig.1 Basic model of interrupt conflict

2 表格分析法

基于靜態(tài)的分析過程，針對中斷中使用的資源進(jìn)行逐一分析，即針對所有中斷服務(wù)子程序中訪問的資源，逐一分析其在主程序(含其調(diào)用的子模塊)、各個中斷服務(wù)子程序的訪問情況，以確定資源訪問過程中是否存在沖突.實際使用過程中，采用表格分析法:

1)以表格的形式列出所有中斷服務(wù)子程序使用的資源，中斷服務(wù)子程序使用資源包括該服務(wù)程序調(diào)用的所有子模塊中使用的資源，一個中斷服務(wù)子程序的優(yōu)先級及引用的資源，如表1所示.

表1 中斷屬性表Tab.1 Summary table of interrupt property

2)以表格的形式說明中斷服務(wù)子程序中使用的每個資源的引用關(guān)系表，如表2所示，并逐一進(jìn)行分析.

針對主程序和中斷子程序訪問共享資源時，列舉出所有的讀寫操作方式，如:只讀、只寫、讀寫.

采用上述對資源的分析方法，容易發(fā)現(xiàn)如下典型的訪問沖突:

1)多字節(jié)的變量、緩沖區(qū)、數(shù)組、I/O端口等數(shù)據(jù)訪問沖突.一個多字節(jié)變量被主程序讀取過程中(如讀完第一個字節(jié))，被中斷打斷并對該變量進(jìn)行賦值操作，在中斷返回后主程序繼續(xù)讀第二字節(jié)，導(dǎo)致主程序獲取的多字節(jié)數(shù)據(jù)高低字節(jié)不同步，發(fā)生數(shù)據(jù)跳變;

表2 中斷程序使用資源的引用關(guān)系總結(jié)表Tab.2 Resources using of interrupt program references

2)寄存器訪問沖突:主程序給某個寄存器賦值后，被中斷打斷并對該寄存器進(jìn)行其他賦值操作，在中斷返回后主程序使用該寄存器數(shù)值時，使用的數(shù)據(jù)是被中斷意外改寫后的數(shù)據(jù)，并不是之前賦值的數(shù)據(jù).

3 分析改進(jìn)

采用上述表格檢測法能夠較好的識別和發(fā)現(xiàn)一些中斷沖突問題，另外還存在一些更為復(fù)雜的情況僅采用上述方法是較難發(fā)現(xiàn)的，在此針對數(shù)據(jù)相關(guān)性、操作關(guān)聯(lián)性和時序沖突進(jìn)行專門的說明.

3.1 數(shù)據(jù)相關(guān)性分析

關(guān)聯(lián)資源可分為兩種類型:同一物理對象但標(biāo)識參數(shù)不同的資源;不同物理對象但數(shù)值要求同步和統(tǒng)一的資源.

第2章羅列的資源是基于源代碼的參數(shù)形式存在，如果僅僅采用最基礎(chǔ)的表格分析法，針對同一物理對象但標(biāo)識參數(shù)不同的設(shè)計代碼，會造成資源引用總結(jié)的不全面或不正確，最終導(dǎo)致沖突分析的遺漏;針對不同物理對象但數(shù)值要求同步和統(tǒng)一的設(shè)計代碼，會造成資源引用的分離，導(dǎo)致沖突分析的錯誤.下面通過實例具體說明這兩種情況.

實例1.同一物理對象但標(biāo)識參數(shù)不同的資源

如代碼中有定義#define AAA_reg((unsigned char xdata*)aaareg)，則在針對AAA_reg、aaareg的訪問應(yīng)該當(dāng)做同一個資源進(jìn)行引用總結(jié)，多維度考慮是否存在訪問沖突，采用表格法列舉針對這兩個標(biāo)識參數(shù)的引用關(guān)系.

基于表格分析法羅列出所有共享資源名稱，采用自動分析工具對具有相同物理地址的標(biāo)識參數(shù)進(jìn)行檢測，如果某些標(biāo)識參數(shù)對應(yīng)的物理地址相同，則認(rèn)為它們是關(guān)聯(lián)變量.針對這種類型的關(guān)聯(lián)變量，分析過程中調(diào)整它們在表格中的位置，放置在相鄰行中，并做綁定合并標(biāo)記(以虛線分割)，以表明這些變量為同一物理對象，作為同一個對象資源，根據(jù)沖突原理進(jìn)行分析.

實例2.不同物理對象但數(shù)值要求同步和統(tǒng)一情況1(變量與計算結(jié)果相互關(guān)聯(lián))

3個溫度參數(shù)T1～T3及它們的溫度平均值T0，針對T0～T3應(yīng)該作為不可分開的資源進(jìn)行引用總結(jié)，建立它們的引用關(guān)系表，多維度考慮是否存在訪問沖突.

采用表格分析法針對T0～T3的引用關(guān)系逐一分析是不會發(fā)現(xiàn)訪問沖突的，針對這種情況在分析時，需要將T0～T3放置在相鄰行中，并做綁定合并標(biāo)記(以虛線分割)，以表明這些變量為同一物理對象，作為同一個對象資源，根據(jù)沖突原理進(jìn)行分析.

表3 不同標(biāo)識但映射對象相同的識別Tab.3 The recognition of objects with different identification but same identity mapping

實例3.不同物理對象但數(shù)值要求同步和統(tǒng)一情況2 (多個變量的物理意義相互關(guān)聯(lián))

指令內(nèi)容DATACMD及其指令編號CMDNO，是固定配對使用的，兩者是不可分開的資源，建立它們的引用關(guān)系表，如果單獨分析參數(shù)，沒有明顯的訪問沖突.

表5 變量物理意義相互關(guān)聯(lián)Tab.5 The physical meaning of interrelated variables

數(shù)據(jù)關(guān)聯(lián)性分析改進(jìn):基于表格分析法中羅列的所有資源名稱，結(jié)合軟件背景和代碼結(jié)構(gòu)，分析所列資源中的數(shù)據(jù)關(guān)聯(lián)性，確認(rèn)哪些資源存在同步關(guān)系，即代碼針對它們的操作必須同步，不能被打斷，將存在數(shù)據(jù)關(guān)聯(lián)性的資源放到相鄰的位置處，綁定合并后進(jìn)行沖突分析.針對數(shù)據(jù)關(guān)聯(lián)性問題在動態(tài)測試中不易發(fā)現(xiàn)，由于中斷發(fā)生的不確定，只有在被打斷函數(shù)的特定位置產(chǎn)生中斷，且中斷中存在寫操作時才會發(fā)生問題，采取數(shù)據(jù)關(guān)聯(lián)性分析更容易發(fā)現(xiàn)上述問題.

3.2 操作關(guān)聯(lián)性分析

上述方法僅僅是基于資源的分析方法，而沒有針對資源引用的一組操作涉及到的多條語句的關(guān)聯(lián)性進(jìn)行分析，即代碼中的某幾條語句為相互關(guān)聯(lián)的操作，操作計算過程一旦被打斷中間數(shù)據(jù)被改寫，則會造成操作錯誤.

實例4.計算過程使用的變量相互關(guān)聯(lián)

主程序使用單字節(jié)變量time進(jìn)行計算，time在中斷服務(wù)子程序中會被賦值改寫.如果僅采用基本的表格分析法羅列的資源進(jìn)行引用，無法發(fā)現(xiàn)訪問沖突，是正常的代碼邏輯設(shè)計.

主程序:

在考慮操作關(guān)聯(lián)的情況下，會發(fā)現(xiàn)語句(1)和語句(2)中使用的time必須是同一時刻的數(shù)值，如果(1)和(2)之間發(fā)生中斷改寫time會導(dǎo)致(1)中計算timer1使用的time值與(2)計算使用的time不一致，timer2計算錯誤.

操作關(guān)聯(lián)性分析改進(jìn):針對一個資源的多個或一組操作涉及到的多條語句，需要分析這些操作中使用的資源是否必須是同一時刻的數(shù)據(jù)，該點針對復(fù)雜運算時尤為重要.為解決該問題，需要增加如下分析工作:

針對每個資源，分析其在每個范圍內(nèi)(如主程序范圍內(nèi)，某個中斷服務(wù)子程序范圍內(nèi))的具體操作語句，確認(rèn)這些操作語句的關(guān)聯(lián)性.對于存在關(guān)聯(lián)操作的語句需要綁定到一起，確保在執(zhí)行過程中不會出現(xiàn)被打斷改寫的情況出現(xiàn).針對操作關(guān)聯(lián)性問題在動態(tài)測試中也不易發(fā)現(xiàn)，與數(shù)據(jù)關(guān)聯(lián)性問題類似，需要構(gòu)造特定的場景才會發(fā)生問題.

3.3 時序沖突分析

前面描述的內(nèi)容歸根到底均為數(shù)據(jù)訪問沖突，而時序訪問更復(fù)雜.如果不同模板(穿插中斷)針對同一個資源或某些資源進(jìn)行寫-讀，這些讀寫在正常情況下滿足一定的流程(即分析確認(rèn)不是數(shù)據(jù)沖突，而是軟件的一個正確處理過程，正常情況下該時序不會被打斷)，此時需要考慮是否存在破壞正常流程的入口條件，即如果一個正常流程存在被意外打斷的外部條件，則當(dāng)前資源的訪問處理流程就存在時序訪問沖突.

實例5.通過時序控制端口輸出

主程序往IO1寫數(shù)據(jù)，查看反匯編對應(yīng)的寫操作過程分為2步，先寫低字節(jié)，再寫高字節(jié)，如果寫的過程被T0打斷，則導(dǎo)致主程序和中斷中的兩次寫均失效:①主程序中寫入的低字節(jié)被中斷T0中的寫覆蓋，主程序?qū)懭氲牡妥止?jié)無效;②中斷T0中寫入的高字節(jié)在從T0中斷返回后被主程序?qū)懭氲母咦止?jié)覆蓋，中斷T0中寫入的高字節(jié)無效.

結(jié)合物理需求和代碼設(shè)計思想，正常情況下，主程序中的寫與中斷T0中的寫間隔是滿足一定要求的，主程序不會存在隨機(jī)被T0打斷的可能，主程序和中斷T0寫IO1的間隔為100 ms(見表6中是否存在數(shù)據(jù)沖突及相關(guān)說明一列).

進(jìn)一步分析操作過程和時序關(guān)系，確認(rèn)是否存在外界輸入，造成上述正常操作流程被打斷的可能(見表6中是否存在時序訪問沖突一列).

表6 時序訪問分析實例表Tab.6 Timing access violation example

時序沖突分析改進(jìn):對于具有特定時序要求的資源進(jìn)行時序訪問沖突分析，分析正常流程和外界輸入可能打亂正常流程的情況，在表格中增加時序沖突一列進(jìn)行說明.針對時序沖突問題如果采用特定的輸入流程在動態(tài)測試中也不易發(fā)現(xiàn)問題，需要在動態(tài)測試過程中加大、加強(qiáng)各種外界輸入的測試，測試用例以不同的發(fā)送的時間、最小的時間間隔、覆蓋所有的指令輸入，以驗證程序?qū)崿F(xiàn)的正確性.

4 預(yù)防及規(guī)避措施

針對存在訪問沖突的資源，為預(yù)防沖突發(fā)生，軟件必須有對應(yīng)的預(yù)防措施和設(shè)計策略.針對一些沖突類型，常見的設(shè)計策略如下:

(1)關(guān)中斷

讀/寫過程關(guān)中斷是常見的數(shù)據(jù)訪問沖突預(yù)防措施，在可能產(chǎn)生中斷的位置關(guān)閉相應(yīng)中斷，以保證數(shù)據(jù)訪問不被打斷，尤其是多字節(jié)數(shù)據(jù)和關(guān)聯(lián)性操作語句，采用該措施是非常有效的.

關(guān)中斷措施在具體實施時，需要特別注意如下兩方面問題:確認(rèn)當(dāng)前關(guān)中斷不能意外被打開，如此時關(guān)閉了某一個中斷，但在另一個未被關(guān)的中斷服務(wù)子程序中打開了該關(guān)閉中斷，造成當(dāng)前關(guān)中斷操作失效;結(jié)合軟件需求確認(rèn)當(dāng)前關(guān)中斷時間是否影響軟件性能要求，如關(guān)中斷時間太長影響軟件對中斷的響應(yīng)時間，造成其他功能失效.

一般情況下，軟件初始化完成之前必須關(guān)中斷，以保證初始化的完整性.

(2)設(shè)置中斷發(fā)生標(biāo)記

設(shè)置中斷發(fā)生標(biāo)記的方式為在讀數(shù)據(jù)之前設(shè)置該標(biāo)記為零，讀寫完成后判斷該標(biāo)記是否置位(該標(biāo)記在中斷服務(wù)子程序中寫該數(shù)據(jù)后置位)，如果置位，則重新讀取該數(shù)據(jù)，以保證當(dāng)前數(shù)據(jù)是最新的同步數(shù)據(jù)，而不會出現(xiàn)跳變.該方法通常用于多字節(jié)資源進(jìn)位的處理，而且僅限于資源讀取操作.

(3)互斥量機(jī)制

該機(jī)制決定了當(dāng)前共享資源在任何情況下都不會出現(xiàn)訪問沖突.當(dāng)訪問資源的模塊在任務(wù)處理完后將擁有的互斥對象交出，以便其他模塊得以訪問.

(4)乒乓存儲

乒乓存儲是一個常常應(yīng)用于數(shù)據(jù)流控制的處理技巧，輸入數(shù)據(jù)流通過“輸入數(shù)據(jù)選擇單元”將數(shù)據(jù)流分配到兩個數(shù)據(jù)緩沖區(qū)，一個模塊對一個數(shù)據(jù)緩沖區(qū)進(jìn)行都操作過程中，另一個模塊對另一個數(shù)據(jù)緩沖區(qū)進(jìn)行寫操作，避免數(shù)據(jù)沖突，提高處理效率.

(5)現(xiàn)場保護(hù)

現(xiàn)場保護(hù)是寄存器訪問沖突常用的手段，具體實現(xiàn)是在中斷服務(wù)子程序的入口處將當(dāng)前寄存器值壓到堆棧區(qū)，在出口處再從堆棧中彈出保存值到對應(yīng)的寄存器.具體實施時需要注意堆棧的壓入和彈出順序，以及個數(shù)上的一致性.

5 總結(jié)

本文描述了一種基于表格的中斷沖突靜態(tài)分析方法，專門針對中斷沖突分析中的幾個復(fù)雜問題:數(shù)據(jù)相關(guān)性、操作相關(guān)性和時序沖突問題提出了分析措施和策略，對于數(shù)據(jù)相關(guān)和操作相關(guān)的資源合并綁定到一起進(jìn)行分析;對于具有時序要求的資源增加時序沖突分析，考慮正常流程被外界輸入打亂的可能.需要注意的是，在分析過程中需要結(jié)合代碼具體的應(yīng)用背景和實際物理意義進(jìn)行分析.最后總結(jié)了幾種常見中斷沖突的預(yù)防設(shè)計措施，希望做到從設(shè)計層面開始有效避免中斷沖突問題.

這種基于表格的中斷數(shù)據(jù)沖突靜態(tài)分析方法實施容易、高效，已經(jīng)應(yīng)用于實際測試過程中，并取得了較好的效果，能夠發(fā)現(xiàn)諸多動態(tài)測試中不易發(fā)現(xiàn)的沖突問題.

［1］ 段永顥，陳睿.基于啟發(fā)式的靜態(tài)中斷數(shù)據(jù)競爭檢測方法［J］.計算機(jī)工程與設(shè)計，2013，34(1):140-145.DUAN Y H，CHEN R.Heuristic static data race detection for interrupt-driven software［J］.Computer Engineering and Design，2013，34(1):140-145.

［2］ 陳睿，楊孟飛，郭向英.基于變量訪問序模式的中斷數(shù)據(jù)競爭檢測方法［J］.軟件學(xué)報，2016，27(3): 547-561.CHEN R，YANG M F，GUO X Y.Interrupt data race detection based on shared variable access order pattern ［J］.Journal of Software，2016，27(3):547-561.

［3］ 侯成杰.航天器C51語言軟件中斷資源沖突分析方法［J］.空間控制技術(shù)與應(yīng)用，2015，41(4):58-62.HOU C J.Interrupt resource conflict analysis for spacecraft C51 language software［J］.Aerospace Control and Application，2015，41(4):58-62.

［4］ BRYLOW D，PALSBERG J.Deadline analysis of interrupdriven software［J］.IEEE Transactions on Software Engineering，2004，30(10):634-655.

［5］ COOPERIDER N.Data-flow analysis for interrupt-driven microcontroller software［D］//Doctor of Philosophy，the University of Utah，2008.

［6］ Advanced methods in automated software test［C］// IEEE conference on software maintenance.New York: IEEE，1990.

［7］ ENGLER D，ASHERAFL K，RACE X.Effective static detection of aceconditions and deadlocks［C］//Scott M，Petcrson L.Proceedings of the 19thACM Symposium on Operating System Principles.Boiton Landing:ACM press，2003:237-252.

［8］ 吳萍，陳意云，張健.多線程程序中斷沖突的靜態(tài)檢測［J］.計算機(jī)研究與發(fā)展，2006，43(2):329-335.WU P，CHEN Y Y，ZHANG J.Static data-race detection for multithread programs［J］.Journal of Computer Research and Development，2006，43(2):329-335.

Static Analysis Method for Table-Based Interruption Data Conflictions

HUANG Chen，DONG Yan，WANG Xiaoli，YU Likun
(Beijing Institute of Control Engineering，Beijing 100190，China)

Interrupt conflict is one of the typical defects in the board embedded software，due to the interruption of uncertainty and randomness of conflict，which are difficult to reproduce and positioned in the dynamic testing process.A static analysis method of interrupt conflict is described on the form of sheet，specifically for data association，operational relevance，timing violations.Several examples are given to illustrate the method and process.Several interrupt conflict prevention strategies and methods are also summarized.Data conflict problems in specific scenario are hard to be found.Compared to dynamic test，static analysis methods in the design and testing stages are easier and more efficient to implement.

interrupt conflict;data association;operating relevance;timing conflict

TP311.5

A 文章編號:1674-1579(2016)05-0057-06

10.3969/j.issn.1674-1579.2016.05.011

黃 晨(1983—)，女，工程師，研究方向為軟件測試;董 燕(1972—)，女，高級工程師，研究方向為軟件測試;王小麗(1983—)，女，高級工程師，研究方向為軟件測試;虞礪琨(1987—)，女，工程師，研究方向為軟件測試.

*國家自然科學(xué)基金資助項目(91118007).

2016-05-16