杜曉婷，王 楠

1.北京航空航天大學(xué) 自動化科學(xué)與電氣工程學(xué)院，北京 100191

2.杜克大學(xué) 電子與計算機工程學(xué)院，北卡羅萊那 達(dá)勒姆 27708，美國

基于上下文的飛控軟件老化缺陷定位方法研究

杜曉婷1+，王 楠2

1.北京航空航天大學(xué) 自動化科學(xué)與電氣工程學(xué)院，北京 100191

2.杜克大學(xué) 電子與計算機工程學(xué)院，北卡羅萊那 達(dá)勒姆 27708，美國

隨著航空工業(yè)的發(fā)展和飛控軟件復(fù)雜度的提高，對飛控軟件可靠性和實時性的要求也越來越高。軟件老化缺陷中存在一類缺陷，會使系統(tǒng)響應(yīng)逐漸變慢，最終出現(xiàn)失效，嚴(yán)重影響飛控軟件的可靠性和實時性，但目前沒有定位這類缺陷的有效方法。針對這類缺陷的定位，提出了一種基于上下文的飛控軟件老化缺陷定位方法。該方法將飛控軟件的主循環(huán)建模成一棵任務(wù)樹，飛控軟件反復(fù)運行的主循環(huán)抽象成一個任務(wù)樹序列。通過Mann-Kendall Test對任務(wù)樹中心節(jié)點的時間屬性進行趨勢檢測，找到可疑任務(wù)，并根據(jù)任務(wù)樹之間的關(guān)系對可疑任務(wù)進行篩選，定位出含有缺陷的任務(wù)，則該任務(wù)所對應(yīng)的函數(shù)即為缺陷所在的位置。實驗表明，該方法不僅能夠給出缺陷的具體位置，還能給出發(fā)生失效時的調(diào)用上下文。

飛控軟件；老化缺陷；缺陷定位；上下文；任務(wù)樹

1 引言

由于飛控軟件工作環(huán)境比較特殊，相對于一般軟件而言，對實時性和可靠性都有著更高的要求。然而存在一類缺陷，會使飛控軟件響應(yīng)速度逐漸變慢，最終出現(xiàn)失效，對飛行安全帶來嚴(yán)重挑戰(zhàn)，這類缺陷屬于老化缺陷中的一種。

老化缺陷會隨著時間表現(xiàn)出越來越顯著的現(xiàn)象，比如內(nèi)存升高，系統(tǒng)響應(yīng)變慢等，即出現(xiàn)軟件老化。當(dāng)軟件在執(zhí)行過程中遇到老化缺陷時，可能會導(dǎo)致不可預(yù)測的失效，這種失效會對飛控軟件的正常運行造成嚴(yán)重影響，進而威脅飛行安全。為了增加飛控軟件的可靠性，本文針對造成飛控系統(tǒng)響應(yīng)變慢的老化缺陷，根據(jù)飛控軟件運行過程特點，提出了基于上下文的老化缺陷定位方法。

飛控軟件的主要運行過程是定時執(zhí)行一個主循環(huán)，在主循環(huán)中，飛控系統(tǒng)讀取外界傳感器數(shù)據(jù)和駕駛指令，計算并輸出到執(zhí)行機構(gòu)。此外，飛控系統(tǒng)會完成一些額外的工作，比如日志記錄、通訊等。從廣義的角度來看，每一次主循環(huán)都可以看作一個測試用例，輸入是傳感器信號和控制指令，輸出是舵機角度、油門、寫入的日志等。整個運行過程中反復(fù)運行的主循環(huán)，就是一連串測試用例輸入的過程，將這個過程稱為一個測試用例鏈。如果可以把飛控軟件反復(fù)運行的主循環(huán)拆分成不同的子任務(wù)，然后在測試用例鏈運行過程中，檢測這些子任務(wù)隨著測試用例鏈輸入而運行時間變長的情況，就可以利用這些信息來定位老化的源頭，從而找到造成系統(tǒng)響應(yīng)變慢的老化缺陷。

飛控軟件中每一個任務(wù)的執(zhí)行實際上對應(yīng)于一個函數(shù)調(diào)用，因此某一個任務(wù)的執(zhí)行時間逐漸變長，也就說明了該任務(wù)所對應(yīng)的函數(shù)調(diào)用時間逐漸變長，即這個函數(shù)可能含有引起老化的缺陷。然而，這個結(jié)論是不完全的。因為任務(wù)的執(zhí)行或者函數(shù)的調(diào)用存在嵌套關(guān)系，一個函數(shù)的調(diào)用時間出現(xiàn)老化，既可能是該函數(shù)本身的實現(xiàn)有問題，也可能是這個函數(shù)所調(diào)用的函數(shù)的實現(xiàn)有問題。只有當(dāng)人們觀察到其子任務(wù)或子函數(shù)的執(zhí)行時間都沒有出現(xiàn)老化時，才能確定是這個函數(shù)含有缺陷。另外，一個函數(shù)含有缺陷，并不代表每一次運行都會表現(xiàn)出來，缺陷的觸發(fā)可能依賴程序運行的上下文。比如，函數(shù)A的缺陷可能只有在B→A→C這樣的調(diào)用順序下才會觸發(fā)，而在D→A→C這樣的情況下不會觸發(fā)，捕捉這樣的上下文顯然有利于后續(xù)的調(diào)試工作。為了對此類造成飛控系統(tǒng)響應(yīng)變慢的老化缺陷進行定位，并捕捉發(fā)生老化的上下文，本文建立了飛控軟件運行過程的任務(wù)樹模型。通過該模型，將飛控軟件反復(fù)運行的主循環(huán)抽象成一個任務(wù)樹序列。通過分析任務(wù)樹內(nèi)任務(wù)之間的父子關(guān)系，以及這些關(guān)系給缺陷定位帶來的影響，根據(jù)任務(wù)和函數(shù)運行之間的對應(yīng)關(guān)系，提出了針對任務(wù)樹序列來定位老化缺陷的方法。通過該缺陷定位方法，不僅可以找到發(fā)生老化的任務(wù)，還可以找到老化發(fā)生時的函數(shù)調(diào)用上下文，對后續(xù)的調(diào)試過程有非常積極的意義。

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)研究；第3章對飛控軟件的運行過程主循環(huán)進行建模；第4章介紹基于任務(wù)上下文的飛控軟件老化缺陷定位方法的基本思想和方法流程；第5章通過實驗，驗證本文方法的有效性；最后是結(jié)束語。

2 相關(guān)研究

1994年P(guān)arnas[1]首次提出了軟件老化的概念，Huang等人[2]對老化缺陷進行了具體描述：軟件老化是由內(nèi)存膨脹和泄漏，未釋放的文件鎖，數(shù)據(jù)損壞，存儲空間碎片化和舍入誤差的積累等原因造成的。在軟件老化中，錯誤隨著時間積累，導(dǎo)致系統(tǒng)性能下降或出現(xiàn)失效。

目前解決軟件老化問題的方法可以分為兩類：

一類是reactive方法[3]，這種方法是在失效發(fā)生之后，采取一定的恢復(fù)機制嘗試修復(fù)失效，恢復(fù)率較高。但這種方法無法保證在每次出現(xiàn)失效后，始終能夠提供一種令人滿意的恢復(fù)機制來保證軟件的長期運行。

另一類proactive方法與reactive方法不同，這是一種軟件恢復(fù)的方法[2-4]，相比reactive方法效果更好，應(yīng)用也更廣泛。軟件恢復(fù)的主要步驟包括終止程序運行，清理程序的內(nèi)部狀態(tài)和環(huán)境，最后重新啟動該程序。軟件恢復(fù)本質(zhì)上通過對軟件進行恢復(fù)，預(yù)防軟件的老化。由于軟件恢復(fù)需要很高的代價，如何尋找最優(yōu)軟件恢復(fù)時間和最優(yōu)軟件恢復(fù)策略成為研究的重點。這些工作可以分為兩類：基于模型的分析方法和基于測量的分析方法?；谀Ｐ偷姆治龇椒ń⑾到y(tǒng)的數(shù)學(xué)模型[5-9]，通過這些模型確定軟件恢復(fù)的有效性并得到最優(yōu)恢復(fù)方案，模型的精確度取決于捕獲老化信息時所做的假設(shè)。文獻(xiàn)[5]使用馬爾科夫再生隨機Petri網(wǎng)（Markov regenerative stochastic Petri nets，MRSPN）模型來描述系統(tǒng)的行為，并計算出軟件可靠性最大情況下的最優(yōu)恢復(fù)間隔?；谀Ｐ偷幕謴?fù)策略，一般假設(shè)太過理想，在實際的工程領(lǐng)域中不容易驗證。

基于測量的方法通過監(jiān)控軟件系統(tǒng)的操作狀況[9-14]，收集關(guān)鍵性能數(shù)據(jù)，以此來分析軟件的老化程度。文獻(xiàn)[9]給出了一種檢測和估計UNIX操作系統(tǒng)老化的方法，使用基于簡單網(wǎng)絡(luò)管理協(xié)議（simple network management protocol，SNMP）的分布式檢測工具收集系統(tǒng)資源的使用數(shù)據(jù)和系統(tǒng)活動數(shù)據(jù)，應(yīng)用趨勢檢測技術(shù)對這些數(shù)據(jù)進行處理，檢測老化的存在，并使用坡度估計方法計算“資源耗盡時間”。文獻(xiàn)[12]提出了一種基于時間序列的分析方法，檢測和估計一個網(wǎng)絡(luò)服務(wù)器在軟件老化的影響下，系統(tǒng)資源的耗盡時間，并用線性回歸方法對數(shù)據(jù)進行趨勢檢測。

基于目前提出的各種軟件恢復(fù)方法，文獻(xiàn)[15]對各種恢復(fù)策略的代價進行了估計，分析了這些方法對消除軟件老化影響的效果，提出選擇軟件恢復(fù)策略時應(yīng)合理平衡恢復(fù)效果和使用代價二者的關(guān)系，為選擇合適的恢復(fù)策略提供指導(dǎo)。

上述這些方法都只是暫時地延緩了失效時間，并沒有從根本上解決軟件中存在的缺陷，老化缺陷對飛控系統(tǒng)的實時性和可靠性仍然存在很大威脅。如何定位老化缺陷，從而為修復(fù)缺陷提供依據(jù)，是本文要研究的問題。

傳統(tǒng)軟件缺陷定位技術(shù)依賴于對失敗測試用例的分析[16-19]，而對于老化缺陷而言，失效難以復(fù)現(xiàn)，因此失敗測試用例非常少，嚴(yán)重影響了現(xiàn)有的缺陷定位方法的效果。本文針對一類造成飛控軟件響應(yīng)變慢的老化缺陷，結(jié)合飛控軟件運行過程的特點，設(shè)計了一種該類缺陷的定位方法。

3 飛控軟件運行主循環(huán)任務(wù)樹模型

首先對飛控軟件的運行過程進行描述，然后提出缺陷定位的任務(wù)樹模型，并對該模型進行分析。

因為飛控軟件對運行過程的可預(yù)測性要求很高，所以一般不會采用搶占式多任務(wù)調(diào)度器。飛控軟件的主循環(huán)調(diào)度過程如下：在主循環(huán)開始時，先運行與飛行器控制相關(guān)的關(guān)鍵任務(wù)；當(dāng)關(guān)鍵任務(wù)運行完后，如果還有時間，將按照預(yù)先設(shè)定的優(yōu)先級調(diào)度需要CPU時間的任務(wù)；在運行某一任務(wù)之前，先判斷該任務(wù)的運行時間上限是否已經(jīng)超過了主循環(huán)還剩下的時間，如果沒超過，那么正常運行，如果超過了，在本次主循環(huán)中就跳過該任務(wù)?？梢钥闯?，在該調(diào)度策略下，不同任務(wù)的運行時間并不會有交疊。另外，一個任務(wù)通常包含子任務(wù)，比如更新飛行控制狀態(tài)的任務(wù)包含讀取GPS，讀取陀螺儀等子任務(wù)。于是，可以把一次主循環(huán)用一棵任務(wù)樹來表示。

下面給出任務(wù)樹及其相關(guān)定義：

定義1（任務(wù)集，任務(wù)樹，任務(wù)樹序列）將所要討論的所有任務(wù)組成一個集合，叫任務(wù)集。如果選取任務(wù)集的一個子集，用這些任務(wù)構(gòu)成一棵樹，并給每個節(jié)點賦上一個時間屬性，這樣一棵樹叫作任務(wù)樹。如圖1所示，任務(wù)樹的根節(jié)點為飛控軟件運行的主循環(huán)，其余每個節(jié)點代表一個任務(wù)，節(jié)點的第一行是任務(wù)的名字，第二行是任務(wù)的執(zhí)行時間，即該任務(wù)本次的消耗。節(jié)點之間的連線表示任務(wù)的分解，除葉子節(jié)點外，每個節(jié)點還包括一個或多個子節(jié)點，表示每個任務(wù)的完成都是通過一系列子任務(wù)來實現(xiàn)的。在飛控軟件中，飛控主循環(huán)的每一次運行都對應(yīng)著這樣一棵任務(wù)樹。飛控軟件的運行過程中反復(fù)運行的主循環(huán)就構(gòu)成一個任務(wù)樹序列。

任務(wù)樹還滿足一定的性質(zhì)：

（1）父任務(wù)的執(zhí)行時間總是大于等于其所有子任務(wù)的總和。因此當(dāng)某子任務(wù)的執(zhí)行時間變長時，有可能使其所有直系先輩節(jié)點的執(zhí)行時間變長。

（2）不同時間段上的主循環(huán)所對應(yīng)的任務(wù)樹并不相同，這是因為并不是所有的飛行任務(wù)在每次主循環(huán)都會執(zhí)行。有些不緊急的任務(wù)周期會很長，可能長達(dá)幾秒，因而被主循環(huán)執(zhí)行的頻率會很低；而有些緊急任務(wù)的周期可能只有幾毫秒，但卻會被主循環(huán)頻繁執(zhí)行。

定義2（上下文樹，完全上下文樹）關(guān)于任務(wù)t的上下文樹是一棵包含t的任務(wù)樹T，并且在該任務(wù)樹中，t只有直系的祖先節(jié)點，且t叫作任務(wù)樹T的中心節(jié)點。關(guān)于任務(wù)樹T和該任務(wù)樹中的一個任務(wù)t的完全上下文樹ContextT(t)是任務(wù)樹的一棵子樹，該子樹是t的上下文樹，并且包含t的所有后代節(jié)點和T的根節(jié)點。

當(dāng)人們說一個完全上下文樹發(fā)生老化時，表示在一個任務(wù)樹序列中，該完全上下文樹的中心節(jié)點的時間屬性呈現(xiàn)上升趨勢。

基于上文的描述和定義，所考慮的缺陷定位問題可以這樣描述：某一任務(wù)t含有執(zhí)行時間老化的缺陷，將它叫作目標(biāo)任務(wù)。在某一任務(wù)樹序列中，t的執(zhí)行時間僅在某一個上下文樹出現(xiàn)時才可能發(fā)生老化，將它叫作目標(biāo)上下文樹。缺陷定位問題就轉(zhuǎn)化為尋找這樣一棵目標(biāo)上下文樹的問題。

4 基于任務(wù)上下文的飛控軟件老化缺陷定位方法

首先介紹缺陷定位方法的基本步驟，并通過一個例子對該方法進行分析，最后對本文使用的Mann-Kendall趨勢檢測方法進行具體描述。

4.1 缺陷定位方法

Fig.1 Example of task tree圖1 任務(wù)樹的例子

在飛控軟件中，每一個任務(wù)的執(zhí)行對應(yīng)于一個函數(shù)調(diào)用，當(dāng)某一個任務(wù)的執(zhí)行時間逐漸變長，也就說明了該任務(wù)所對應(yīng)的函數(shù)調(diào)用時間逐漸變長。因為任務(wù)的執(zhí)行或者函數(shù)的調(diào)用存在嵌套關(guān)系，一個函數(shù)的調(diào)用時間出現(xiàn)老化，既有可能是該函數(shù)本身的實現(xiàn)有問題，也可能是這個函數(shù)所調(diào)用的函數(shù)的實現(xiàn)有問題。只有當(dāng)其子任務(wù)或子函數(shù)的執(zhí)行時間都沒有出現(xiàn)老化時，才能確定是這個函數(shù)含有缺陷。另一方面，一個函數(shù)含有缺陷，并不代表每一次運行都會表現(xiàn)出來，缺陷的觸發(fā)可能依賴程序運行的上下文。為了給出缺陷的位置并捕捉缺陷觸發(fā)的上下文，利用上文給出的任務(wù)樹模型對飛控軟件的老化缺陷進行定位。如圖2所示，缺陷定位方法共分為6個步驟，下面對這6個步驟進行具體描述。

Fig.2 Procedures of context based fault localization method圖2 基于任務(wù)上下文的缺陷定位方法步驟

（1）對飛控軟件進行插樁，并運行能夠引起老化的失效測試用例。

在飛控軟件的源碼中插入記錄語句，記錄函數(shù)的進入時間和退出時間，以便計算函數(shù)的運行時間，以及生成函數(shù)之間的調(diào)用關(guān)系，這些信息被寫入日志文件中。因為人們只關(guān)心在主循環(huán)中能夠被調(diào)用到的函數(shù)，所以只有這一部分函數(shù)需要被插樁。通過運行能夠引起老化的失效測試用例，可以得到一個記錄所有被插樁函數(shù)進入時間和退出時間的文件。

（2）構(gòu)建任務(wù)樹序列和完全上下文樹序列。

在記錄文件中，可以找到每一次主循環(huán)的開始和結(jié)束時間，對于每一次主循環(huán)的運行，可以根據(jù)各個函數(shù)的進入和退出時間，確定它們之間的調(diào)用關(guān)系，由此生成一棵任務(wù)樹，如圖3所示。其根節(jié)點是main函數(shù)，其余每個節(jié)點都表示一個函數(shù)，從上到下的連線表示函數(shù)之間的調(diào)用關(guān)系。對于每一次主循環(huán)的運行，都生成這樣一棵任務(wù)樹，于是得到一個任務(wù)樹序列。對于任務(wù)樹序列中的每一棵任務(wù)樹，選擇其任意一個節(jié)點生成一棵完全上下文樹，并把相同的完全上下文樹歸并到一個集合里面。然后根據(jù)它們根節(jié)點的進入時間進行排序，這樣就得到了若干完全上下文樹序列，其中每個序列中的完全上下文樹是相同的，不同序列中的完全上下文樹是不同的。

Fig.3 Task tree圖3 任務(wù)樹

（3）對完全上下文樹的中心節(jié)點進行趨勢檢測。

對于每一個完全上下文樹序列，將其中心節(jié)點的運行時間提取出來，組成一個運行時間序列。接下來，對每一個運行時間序列進行趨勢檢測，圖4所示為出現(xiàn)老化現(xiàn)象的完全上下文樹的一個例子，圖中的淺色節(jié)點是這些上下文樹的中心節(jié)點，也是被檢測出運行時間存在上升趨勢的點。那么就可以找到存在上升趨勢的時間序列所對應(yīng)的完全上下文樹，這些上下文樹就是與老化相關(guān)的完全上下文樹。本文使用Mann-Kendall趨勢檢測方法。

（4）提取目標(biāo)上下文樹。

上一步中，得到了若干與老化相關(guān)的完全上下文樹。接下來，需要識別出這些完全上下文樹的包含關(guān)系，對這些完全上下文樹進行篩選，并提取完全上下文樹的公共部分，得到目標(biāo)上下文樹。當(dāng)一棵完全上下文樹包含另一棵完全上下文樹時，前者的中心節(jié)點所表現(xiàn)出來的老化現(xiàn)象很可能是受到后者的影響，因此應(yīng)當(dāng)將前者去掉。得到已經(jīng)去掉含有子樹的完全上下文樹的集合后，最后一步就是去掉這些完全上下文樹的多余節(jié)點。在前面的步驟，考慮了每一個中心節(jié)點運行的全部上下文，然而缺陷的觸發(fā)有可能只依賴部分的上下文，甚至根本不依賴上下文。這一步中，只需要提取出上一步獲得的集合中所有樹的公共部分，就能找到真正與缺陷相關(guān)的上下文，也就是需要尋找的目標(biāo)上下文樹。

如圖4，樹（3）的中心節(jié)點的時間屬性之所以呈上升趨勢，是因為樹（3）的中心節(jié)點a調(diào)用了樹（2）的中心節(jié)點b，所以a的老化現(xiàn)象很可能是b帶來的，需要排除掉樹（3）。同理，需要把樹（2）、（3）、（5）、（6）都去掉。去掉這些完全上下文樹后的集合如圖5所示。對圖5中的完全上下文樹提取公共部分后，得到的目標(biāo)上下文樹如圖6所示。于是，定位到了引起老化的缺陷所在的位置：任務(wù)t所對應(yīng)的函數(shù)。不僅如此，還給出了這種缺陷觸發(fā)所依賴的上下文：從b到t的調(diào)用。

Fig.4 Sets of aging full context trees圖4 發(fā)生老化的完全上下文樹集合

從上述步驟可以看到，基于任務(wù)樹的缺陷定位方法能夠通過完全上下文樹之間的包含關(guān)系，排除因為受其他任務(wù)影響而老化的任務(wù)，有效減少false positive的產(chǎn)生。另外，該方法還通過完全上下文樹之間的共性，給出了與老化密切相關(guān)的調(diào)用上下文。

4.2 基于Mann-Kendall的老化趨勢檢測

Mann-Kendall趨勢檢測方法[20]是最廣泛使用的非參數(shù)檢驗方法，不要求樣本必須服從一定分布，且檢驗不受個別異常值的干擾，計算簡便。本文關(guān)注的是任務(wù)樹中的某一節(jié)點的時間屬性是否有遞增的趨勢。對于每一個完全上下文樹序列，將其中心節(jié)點的運行時間（退出時間減去進入時間）提取出來，組成一個運行時間序列，通過Mann-Kendall對每一個運行時間序列進行趨勢檢測，篩選出被檢測到具有上升趨勢的運行時間序列。

Fig.5 Sets of aging full context trees after filtering subtrees圖5 去掉含有子樹的完全上下文樹集合

Fig.6 Goal context tree圖6 目標(biāo)上下文樹

設(shè)運行時間序列為{xt:t=1,2,…,n}；原假設(shè)H0：時間序列{xt}沒有變化趨勢；備擇假設(shè)H1：時間序列{xt}有變化趨勢。統(tǒng)計量S的計算如式（1）所示：

其中，l＞k，sgn為符號函數(shù)。

如果時間序列x1,x2,…,xn中不存在相同數(shù)值，S的方差為：

如果時間序列x1,x2,…,xn中存在m組相同數(shù)值，其中tp為第p組對應(yīng)的數(shù)值，S的方差為：

對S標(biāo)準(zhǔn)化，可得：

5 實驗分析

本文通過在開源飛控軟件Ardupilot上人工植入老化缺陷，利用上文提出的缺陷定位方法進行缺陷定位實驗，驗證算法的有效性。首先對實驗對象及實驗設(shè)計與實現(xiàn)過程進行描述，然后將收集到的實驗數(shù)據(jù)通過Mann-Kendall進行趨勢檢測，最后對實驗結(jié)果進行分析。

5.1 實驗對象

Ardupilot是一套無人機自動飛行控制系統(tǒng)，支持多旋翼飛行器、固定翼飛機和傳統(tǒng)直升機。系統(tǒng)由固定翼/多旋翼載機、APM飛行控制板、數(shù)傳模塊、電子羅盤、各類傳感器和地面站組成。雖然不如載人飛行器的飛控軟件復(fù)雜，但是它也有近20萬行代碼（不包括實時操作系統(tǒng)Nuttx的代碼和底層驅(qū)動的代碼），足夠滿足本次實驗的要求。更重要的是，無論是Ardupilot還是客機的飛控軟件，它們的主要運行過程都是一個反復(fù)執(zhí)行的主循環(huán)，本文提出的缺陷定位方法正是基于飛控軟件的這個特點。

5.2 實驗設(shè)計與結(jié)果分析

首先，對Ardupilot進行了插樁，即在函數(shù)入口處和出口處插入了語句記錄函數(shù)的進入和退出，并且記錄了響應(yīng)的進入時間和退出時間。在調(diào)度器、硬件抽象層和主循環(huán)這些經(jīng)常運行的66個函數(shù)中進行了插樁。接下來，在Ardupilot的Copter::motors_output函數(shù)中植入一個模擬老化的缺陷，即加入了一個隨著運行次數(shù)增加的延遲。將修改好的程序?qū)懭胍粋€無人機中，然后飛行該無人機10min。最后，將無人機的日志文件取出。依據(jù)該記錄文件，可以計算函數(shù)的運行時間并確定它們的調(diào)用關(guān)系。根據(jù)這些信息，每一次Ardupilot主循環(huán)的運行都可以建模成一棵任務(wù)樹，圖7和圖8給出了這種任務(wù)樹的兩個例子。其中的節(jié)點對應(yīng)著一個函數(shù)（或任務(wù)），其編號和具體函數(shù)的對應(yīng)關(guān)系如表1所示。

Fig.7 Example 1 of main loop task tree圖7 主循環(huán)任務(wù)樹的樣例1

Fig.8 Example 2 of main loop task tree圖8 主循環(huán)任務(wù)樹的樣例2

通過運行實驗，收集任務(wù)樹，提取完全上下文樹序列，得到每一個完全上下文樹序列中的中心節(jié)點的運行時間，組成一個運行時間序列。并使用Mann-Kendall趨勢測試對所有長度大于100的完全上下文樹序列進行測試（長度太小難以進行趨勢檢測），其中α值取10-7。

實驗表明有兩個完全上下文樹中心節(jié)點的時間屬性呈現(xiàn)上升趨勢，如表2所示。共有兩個完全上下文樹表現(xiàn)出了顯著的老化，它們的中心節(jié)點分別是Copter::fast_loop和Copter::motors_output，所對應(yīng)的完全上下文樹分別如圖9和圖10?？梢钥吹?，中心節(jié)點為Copter::fast_loop的完全上下文樹完全包含了中心節(jié)點為Copter::motors_output的完全上下文樹，因此前者應(yīng)該去掉，這是由于前者之所以發(fā)生老化是因為后者的影響。排除掉前者后，就找到了真正發(fā)生老化的任務(wù)或函數(shù)，即Copter::motors_output，圖10為其調(diào)用的上下文。

Table1 Function names and their number表1 編號和函數(shù)名對應(yīng)關(guān)系

Table2 Results of trend test表2 趨勢測試結(jié)果

最終的定位結(jié)果與植入的缺陷位置是一致的，因此說明了基于上下文的缺陷定位方法的有效性。

6 結(jié)束語

本文提出了一種針對飛控軟件中一類造成系統(tǒng)響應(yīng)變慢的老化缺陷的定位方法。根據(jù)飛控軟件的運行特點，建立了任務(wù)樹模型。通過對飛控軟件中部分函數(shù)進行插樁，并運行會使軟件老化的測試用例，分析得到若干任務(wù)樹序列和完全上下文樹序列。使用Mann-Kendall趨勢檢測方法對完全上下文樹序列的時間屬性進行趨勢檢測，證明了老化的存在。最后通過識別包含關(guān)系篩選完全上下文樹，去除完全上下文樹中的多余節(jié)點，提取出目標(biāo)上下文樹。此外，以Ardupilot為實驗對象，本文設(shè)計并進行了實驗。實驗結(jié)果表明，本文方法不僅能定位出老化缺陷的位置，還能給出發(fā)生老化時的調(diào)用上下文，對后續(xù)的調(diào)試有很大幫助。

在對飛控軟件缺陷定位方法的研究中，人們僅僅針對單缺陷問題進行了研究，沒有分析多個老化缺陷存在時的缺陷定位方法。此外，本文只分析了造成飛控軟件響應(yīng)變慢的一類缺陷。內(nèi)存泄露缺陷與使飛控軟件響應(yīng)變慢的缺陷類似，這類缺陷的失效也有一個積累的過程，但它們并不一定會使系統(tǒng)響應(yīng)變慢，因為這類缺陷的觸發(fā)并不會像與響應(yīng)時間有關(guān)的缺陷一樣有一個向上傳播的過程，所以無法使用本文提出的缺陷定位方法。未來將針對上述兩個問題做進一步研究。

Fig.9 Afull context tree with a central node Copter::fast_loop圖9 中心節(jié)點為Copter::fast_loop的完全上下文樹

Fig.10 Afull context tree with a central node Copter::motors_output圖10 中心節(jié)點為Copter::motors_output的完全上下文樹

[1]Parnas D L.Software aging[C]//Proceedings of the 16th International Conference on Software Engineering,Sorrento,Italy,May 16-21,1994.Washington:IEEE Computer Society,1994:279-287.

[2]Huang Y,Kintala C,Kolettis N,et al.Software rejuvenation:analysis,module and applications[C]//Proceedings of the 25th International Symposium on Fault-Tolerant Computing,Pasadena,USA,1995.Washington:IEEE Computer Society,1995:381-390.

[3]Candea G,Cutler J,FoxA.Improving availability with recursive microreboots:a soft-state system case study[J].Performance Evaluation,2004,56(1/4):213-248.

[4]Trivedi K S,Vaidyanathan K.Software aging and rejuvenation[J].Wiley Encyclopedia of Computer Science and Engineering,2008:1-8.

[5]Garg S,PuliafitoA,Telek M,et al.Analysis of software rejuvenation using Markov regenerative stochastic Petri net[C]//Proceedings of the 6th International Symposium on Software Reliability Engineering,Toulouse,France,Oct 24-27,1995.Washington:IEEE Computer Society,1995:180-187.

[6]Garg S,PuliafitoA,Telek M,et al.Analysis of preventive maintenance in transactions based software systems[J].IEEE Transactions on Computers,1998,47(1):96-107.

[7]Trivedi K S,Vaidyanathan K,Go?eva-Popstojanova K.Modeling and analysis of software aging and rejuvenation[C]//Proceedings of the 33rd Annual Simulation Symposium,Washington,Apr 16-22,2000.Washington:IEEE Computer Society,2000:270-279.

[8]Bao Yujuan,Sun Xiaobai,Trivedi K S.Aworkload-based analysis of software aging,and rejuvenation[J].IEEE Transactions on Reliability,2005,54(3):541-548.

[9]Castelli V,HarperR E,Heidelberger P,et al.Proactive management of software aging[J].IBM Journal of Research and Development,2001,45(2):311-332.

[10]Garg S,Van MoorselA,Vaidyanathan K,et al.Amethodology for detection and estimation of software aging[C]//Proceedings of the 9th International Symposium on SoftwareReliability Engineering,Paderborn,Germany,Nov 4-7,1998.Washington:IEEE Computer Society,1998:283-292.

[11]Vaidyanathan K,Trivedi K S.Ameasurement-based model for estimation of resource exhaustion in operational software systems[C]//Proceedings of the 10th International Symposium on Software Reliability Engineering,Boca Raton,USA,Nov 1-4,1999.Washington:IEEE Computer Society,1999:84-93.

[12]Li Lei,Vaidyanathan K,Trivedi K S.An approach for estimation of software aging in a Web server[C]//Proceedings of the 2002 International Symposium on Empirical Software Engineering,Nara,Japan,Oct 3-4,2002.Washington:IEEE Computer Society,2002:91-100.

[13]AvritzerA,CzeksterR M,Distefano S,et al.Software aging and rejuvenation for increased resilience:modeling,analysis and applications[M]//Resilience Assessment and Evaluation of Computing Systems.Berlin,Heidelberg:Springer,2012:167-183.

[14]Grottke M,Li L,Vaidyanathan K,et al.Analysis of software aging in a Web server[J].IEEE Transactions on Reliability,2006,55(3):411-420.

[15]Alonso J,MatiasR,Vicente E,et al.Acomparative experimental study of software rejuvenation overhead[J].Performance Evaluation,2013,70(3):231-250.

[16]Li Wei,Zheng Zheng,Hao Peng,et al.Predicate executionsequence based fault localization algorithm[J].Chinese Journal of Computers,2013,36(12):2406-2419.

[17]Hao Peng,Zheng Zheng,Zhang Zhenyu.et al.Self-adaptive fault localization algorithm based on predicate execution information analysis[J].Chinese Journal of Computers,2014,37(3):500-511.

[18]PytlikB,Renieris M,Krishnamurthi S,et al.Automated fault localization using potential invariants[J].arXiv preprint cs/0310040,2003.

[19]Xuan Jifeng,Monperrus M.Learning to combine multiple ranking metrics for fault localization[C]//Proceedings of the 2014 International Conference on Software Maintenance and Evolution,Victoria,Canada,Sep 28-Oct 3,2014.Washington:IEEE Computer Society,2014:191-200.

[20]GilbertR O.Statistical methods for environmental pollution monitoring[M].Hoboken,USA:John Wiley&Sons,Inc,1987.

附中文參考文獻(xiàn)：

[16]李偉,鄭征,郝鵬,等.基于謂詞執(zhí)行序列的軟件缺陷定位算法[J].計算機學(xué)報,2013,36(12):2406-2419.

[17]郝鵬,鄭征,張震宇,等.基于謂詞執(zhí)行信息分析的自適應(yīng)缺陷定位算法[J].計算機學(xué)報,2014,37(3):500-511.

Context Based Fault Localization Method for Flight Control SoftwareAging Defects

DU Xiaoting,WANG Nan.Context based fault localization method for flight control software aging defects.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1214-1223.

DU Xiaoting1+,WANG Nan2
1.School ofAutomation Science and Electrical Engineering,Beihang University,Beijing 100191,China
2.School of Electrical and Computer Engineering,Duke University,Durham,North Carolina 27708,USA
+Corresponding author:E-mail:xiaoting_2015@buaa.edu.cn

With the development of aviation industry and the higher complexity of flight control software,the requirements of the reliability and real-time performance become higher.This paper investigates a special type of aging defects which will affect the reliability and real-time performance of software systems,due to the reason that it will result in the slow response on software systems.However,there is no effective method to address this type of defects for flight control software.Inspired by that,this paper proposes a context based fault localization method.First of all,the main loop of the flight control software is modelled as a task tree,then the repeated running processes of the main loop can be considered as a task tree series.By utilizing Mann-Kendall Test,the time attribute of the central node of the task tree is detected to find the suspicious task.Thereafter,according to the relationship among the task tree series,suspicious tasks are selected to locate defects.The function of suspicious task is the location of the defect.Finally,an experiment is implemented and the results show that the proposed method can not only locate the defect,but also give the call context.

flight control software;aging defect;fault localization;context;task tree

was born in 1990.He

the M.S.degree in aero-nautical engineering from Beihang University.Now he is a Ph.D.candidate at School of Electrical and Computer Engineering,Duke University.His research interests include software dependability modeling and software fault localization. 王楠（1990—），男，四川沐川人，美國杜克大學(xué)博士研究生，主要研究領(lǐng)域為軟件測試建模，缺陷定位。

DU Xiaoting was born in 1992.She is an M.S.candidate at Beihang University.Her research interests include software testing and software fault localization.杜曉婷（1992—），女，山東濟寧人，北京航空航天大學(xué)碩士研究生，主要研究領(lǐng)域為軟件測試，缺陷定位。

A

：TP311

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-19,http://www.cnki.net/kcms/detail/11.5602.TP.20161019.1458.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1214-10

10.3778/j.issn.1673-9418.1609021

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056