Sentomist：通過癥狀挖掘檢測傳感器網絡的瞬態錯誤

Abstract

在摘要部分首先介紹了

無線傳感網絡應用程序：事件驅動、看似簡單、以復雜的并發模型執行的，很容易產生錯誤，特別是瞬態錯誤(瞬態錯誤：會產生，持續的時間不長)

瞬態錯誤產生的原因：傳感網程序中具有隱式依賴關系的事件過程交錯執行時很可能產生瞬態錯誤；而且這種瞬態錯誤隱藏的很深，現有的測試工具不只很難檢測這種瞬態錯誤，連這種瞬態錯誤的癥狀也很難識別。

論文提出了一種新的用于識別傳感網程序瞬態錯誤的工具Sentomist，這篇文章核心部分就是講解了sentomist實現的基本思想，主要包括：

1)將程序的運行流程根據事件過程劃分區間
2)區間特征屬性的選取
3)采用一類支持向量機這種異常檢測算法劃分正常區間和異常區間
這三個部分的內容到后面都會詳細介紹

之后論文采用sentomist對三個傳感網程序進行測試，發現sentomist確實能夠有效檢測程序中的瞬態錯誤 Introduce

接著introduce部分介紹了
1、傳感器程序會有bug的原因：
1)傳感器程序是基于事件驅動模式、并以復雜的并發模型運行的：根據的硬件中斷執行相應的事件過程。怎么理解事件驅動和并發模型呢？因為傳感器對能耗的要求很高，它不能一直處于激活狀態，只有當相應的系統中斷發生時，才會去執行相應的事件過程，而沒有中斷發生的時候就可能處于低能耗的睡眠狀態，這個就是所謂的事件驅動。
2)而且在一個事件過程執行過程中如果發生了新的系統中斷，就會發生搶占，轉而去執行新事件過程，這就可能引起了兩個事件過程的交錯執行，很容易產生瞬態錯誤
2、論文還說了當具有隱式依賴關系的處理事件過程在交錯執行的時候，很可能產生錯誤，而且這種錯誤本生具有短暫性，要檢測這種瞬態bug和識別瞬態bug的癥狀都是很困難的
3、Sentomist方法的基本思想
1)sentomist設計的一個核心觀點是：含有瞬態錯誤的傳感網程序行為與正常的傳感網程序行為有差異，可以采用離群值作為瞬態錯誤的檢測指標。
2)Sentomist方法的基本思想是基于這樣一個流程的：sentomist根據指定的中斷事件處理劃分區間；這些區間中所發生的正常程序行為應具有統計相似性、而偶然性的程序行為可能含有瞬態錯誤；而且sentomist以程序指令的執行計數作為區間特征屬性；sentomist根據指令計數對這些區間進行聚類，把離群值作為瞬態錯誤區間的檢測指標(值越大，表示含有瞬態錯誤的可能性越高)，對于這些離群值越大的區間采用人工的方式來檢測該區間是否包含了瞬態錯誤。

3)Sentomist的實現是基于TinyOS的，TinyOS是一種專門為無線傳感器網絡設計的操作系統

WSN應用程序的并發模型
1、這里首先介紹了事件過程的概念，事件過程就是事件處理的特定應用程序邏輯。
也就是說當發生一個系統中斷時，微控制單元(MCU)會自動調用相應中事件處理邏輯(也就是事件過程)，其實意思就是特定的事件過程可以處理特定的系統中斷。
2、無線傳感器網絡操作系統(TinyOS)實現事件過程的兩個機制：中斷處理器+ 任務
1)中斷處理器：中斷處理器怎么理解呢，當系統中斷發生，會啟動一個特定的中斷處理器實例處理相應的系統中斷。
但是只靠中斷處理器處理系統中斷是不行的，原因是在執行一些很耗時操作的時候，一個中斷處理器實例可能會霸占整個MCU資源，這是不允許的，這就引進了任務的概念
2)task實質上就是一種延時操作，中斷處理器可以post任務、任務也可以post任務；任務的是通過FIFO方式執行的；新的中斷處理器可以搶占任務
接下來看一個的事件過程的完整實例
3、圖1講解：一個的事件過程的完整實例

通過這個圖的講解就能比較清楚的理解了事件驅動、并發模型、事件過程、事件處理器、任務這些概念以及事件過程的交錯執行了
接下來我們用“數據污染”這個傳感器程序例子來講解為什么這種事件過程的交錯執行很容易引入瞬態錯誤

一個動態實例：數據污染
1、這個傳感網程序的功能是接受和發送傳感器節點獲取的數據。
傳感器節點獲取到周圍環境的數據，會產生一個ADC(模擬數字轉換器)中斷，相應的ADC中斷處理器會調用這個readDone方法將數據存儲到packet結構體中的data數組中，數組大小為3，當接收到了三個數據以后，把這個數據包發送出去，因為包的發送用到了用到了網絡，是個比較耗時的操作，這里把這個提交數據包的操作定義為任務延時操作
(例子講解)
2、通過這個例子就能發現瞬件過程的交錯執行很有可能產生瞬態錯誤，而且這種錯誤要復現的話挺困難的，因為剛好要在執行9-11代碼的時候產生一個新的事件中斷，概率很小；而且錯誤的癥狀也不明顯，譬如說這里只是把數據偷換了而已，并不會引起程序崩潰，其他功能模塊的還是正常執行。

所以要采用一個合適的傳感網程序的檢測方法，要求既能將瞬態錯誤的的癥狀顯現出來，又能識別瞬態錯誤；這里采用的方法是

通過機器學習的方法自動挖掘錯誤癥狀
1、這里首先總結正常事件過程的執行模式：因為大部分正常執行的事件過程是沒有交錯的，可能引起瞬態錯誤的交錯執行的事件過程發生的概率還是比較少的
譬如正常模式：ADC中斷—中斷處理完成；這個是事件處理器中沒有提交任務情況的執行模式；
會在事件處理器中提交任務的模式是：ADC中斷—提交任務—中斷完成—運行任務；
事件過程交錯執行模式：ADC中斷—提交任務—中斷完成—新的ADC中斷—中斷完成—運行任務，這種交錯執行模式就可以定義成一個離群值、
2、Sentomist的錯誤癥狀挖掘的完整流程：
首先Sentomist將傳感網程序程序的可執行代碼還有測試場景作為輸入，運行程序得到程序執行軌跡
Sentomist將程序執行軌跡分解成一系列的區間——這里每一個區間對應了一個事件過程實例
之后再調用一個異常檢測算法找出可能含有瞬態錯誤的區間，
最后采用人工檢測的方式檢測事件過程是否包含瞬態錯誤。
要想實現上面整個sentomist執行流程，就需要解決一下三個主要問題：
3、實現Sentomist的三個主要問題
1)怎么將程序的執行軌跡流劃分區間
2)對區間特征屬性怎么選取
3)錯誤區間的檢測算法
首先來看一下第一個問題是怎么解決的
根據事件過程實例劃分區間
1、由于之前說過，大部分的事件過程的執行模式都是相似的，劃分之后的區間也應該具有的統計相似性。因此這里根據事件過程實例劃分區間

2、這里首先介紹幾個基本的概念
1)事件處理區間的定義：一個事件處理區間對應著一個事件過程實例(開始：相應的事件處理器啟動；結束：若最后一個task執行完成或者事件處理器退出)
2)事件過程的生命周期序列定義：包括以下四個過程：int(n)(第n個中斷處理器的入口)、postTask、runTask、reti(中斷處理器的出口)，
3)Int-reti串：從中斷處理器的入口到中斷處理器的出口，也就是途中的t0-t3
3、在劃分區間的時候遇到的一個問題就是，區間的開始位置很好定位，它對應著一個特定中斷處理器的入口，但是它的結束位置卻很難定位主要是因為不知道在處理過程中提交了多少個任務、什么時候提交的的、任務什么時候開始執行、任務什么時候task結束、而且還有可能存在交錯執行）
4、這里就引入了三個準則用于找出區間的結束位置，這三個準則都是根據傳感網程序中任務的實現機制抽象出來的
1) 規則1描述了任務的執行方式：FIFO隊列
2)規則2描述了int-reti串(也就是中斷處理器)中提交的任務序列
3)規則3描述了在任務中提交的任務序列

5、區間的識別方式：首先根據規則2可以確定int-reti串中提交的任務序列，再根據規則1確定相應的runTask序列；規則3又可以確定在任務中提交任務序列，最后再根據規則1確定相應的的runTask序列；最后一個runTask執行完畢位置就表明區間的結束位。
總而言這，區間的劃分就是根據事件過程實例來劃分的，初始位置就是中斷處理器的入口，結束位置就是最后一個任務的執行的結束。

根據事件過程實例得到事件處理區間之后，還要對區間進行抽象得到區間的特征屬性，這樣就能用相關機器學習的方法自動挖掘區間的錯誤癥狀，這里就是我么你要解決的第二個問題了：區間特征屬性的選取策略
區間特征屬性的選取策略
1、區間特征屬性的選取策略有很多種，譬如說函數的調用序列、特定函數的調用次數，這里采用的特征選取策略是指令的執行計數。
2、我們知道一個指令對應了一條機器碼語句，指令的執行計數就是程序執行全部的機器碼、這就有點像程序的語句覆蓋。
1) 選擇這個作為的區間的特征屬性是因為：
①：這種抽象方式對所有的傳感網程序都適用
②：而且這里還說了，機器學習的方法同坐這種特征選舉方式能夠有效的捕獲瞬態錯誤癥狀，從而區分正常區間和異常區間。
2) 我們來看一下這個例子來理解一下怎么把程序的執行計數作為區間的特征屬性，還是以數據污染這個程序威力：傳感器節點接受到一個數據后，這場的指令執行是：5,6,9語句各執行一次；但是如果是事件過程交錯執行的時候，5,6,9指令會執行兩次；像這種執行了兩次的模式就可以看成可能含有瞬態錯誤的異常區間。
異常檢測算法：一類支持向量機
之前區間劃分好了，區間的特性屬性也選取好了，接下來是要對區間進行分類，找出可能包含瞬態錯誤的異常區間，這里采用的異常檢測算法是：一類支持向量機。
1、支持向量機：就是一中分類算法，簡單的來說支持向量機找到一個超平面將一組點或者數據分成不同的兩類
2、一類支持向量機：
1)根據大部分事件過程實例區間都屬于的正常區間，應具有統計相似性、少部分的異常區間可能含有瞬態錯誤。
2)采用one-Class SVM就能是找到一個邊界劃分正常區間和異常區間。
3)而且它能夠對大部分未分類的樣例特征建模，然后根據邊界值決定一個樣例是否屬于離群值。
4)但是這種劃分并不是很十分嚴格，有可能產生誤報。意思就是說對于異常區間，它的離群值越大，就代表它含有瞬態錯誤的可能性越大而已，而不能斷定這個異常區間一定包含有瞬態錯誤
Evaluation
論文通過三個實驗研究sentomist對瞬態錯誤檢測的有效性
1、數據采集傳感網程序——數據污染
2、多跳數據轉發傳感網程序——包丟失
3、兩個共存的交互協議——對硬件資源的競爭

這三個例子的事件過程對應的硬件中斷分別是ADC中斷、SPI中斷還有時間中斷

這里無線傳感器模擬器采用的是Avrora，主要是因為Avrora對傳感器節點的能和交互的模擬十分精確，這就很好的滿足了捕獲瞬態錯誤發生的實時性要求

在Sentomist中整合了Avrora，就能實現前端數據的采集和獲取程序執行的流程，再根據相應的事件過程實例劃分區間、在獲取區間指令執行的計數，最后采用one-Class SVM 算法分類和排序找出可能含有瞬態錯誤的區間。

總結

以上是生活随笔為你收集整理的TinyOS论文11：Sentomist的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。