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

杜曉婷，王 楠

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

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

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

杜曉婷1+，王 楠2

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

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

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

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

1 引言

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

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

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

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

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

2 相關研究

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

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

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

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

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

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

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

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

3 飛控軟件運行主循環任務樹模型

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

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

下面給出任務樹及其相關定義：

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

任務樹還滿足一定的性質：

（1）父任務的執行時間總是大于等于其所有子任務的總和。因此當某子任務的執行時間變長時，有可能使其所有直系先輩節點的執行時間變長。

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

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

當人們說一個完全上下文樹發生老化時，表示在一個任務樹序列中，該完全上下文樹的中心節點的時間屬性呈現上升趨勢。

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

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

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

4.1 缺陷定位方法

Fig.1 Example of task tree圖1 任務樹的例子

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

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

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

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

（2）構建任務樹序列和完全上下文樹序列。

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

Fig.3 Task tree圖3 任務樹

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

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

（4）提取目標上下文樹。

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

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

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

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

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

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

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

Fig.6 Goal context tree圖6 目標上下文樹

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

其中，l＞k，sgn為符號函數。

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

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

對S標準化，可得：

5 實驗分析

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

5.1 實驗對象

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

5.2 實驗設計與結果分析

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

Fig.7 Example 1 of main loop task tree圖7 主循環任務樹的樣例1

Fig.8 Example 2 of main loop task tree圖8 主循環任務樹的樣例2

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

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

Table1 Function names and their number表1 編號和函數名對應關系

Table2 Results of trend test表2 趨勢測試結果

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

6 結束語

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

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

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

Fig.10 Afull context tree with a central node Copter::motors_output圖10 中心節點為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.

附中文參考文獻：

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

[17]郝鵬,鄭征,張震宇,等.基于謂詞執行信息分析的自適應缺陷定位算法[J].計算機學報,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—），男，四川沐川人，美國杜克大學博士研究生，主要研究領域為軟件測試建模，缺陷定位。

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—），女，山東濟寧人，北京航空航天大學碩士研究生，主要研究領域為軟件測試，缺陷定位。

A

：TP311

Received 2016-08,Accepted 2016-10.

CNKI網絡優先出版: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