灰洞檢測:基于鏈路質量估計的看門狗算法

蔣 錕，汪 蕓

(東南大學計算機科學與工程學院，江蘇 南京 211189)

0 引言

近年來，無線傳感器網絡(Wireless Sensor Network)成為重要的研究熱點。無線傳感器網絡是由大量部署在監測區域內具有感知、計算、存儲和無線通信能力的微型節點組成的自組織分布式網絡。這些節點協作地采集被感知對象的相關信息，并通過短距離多跳的無線通信方式將采集的數據傳輸到基站做進一步的分析和處理。無線傳感器網絡被設計成為可以大范圍、長期對監測區域進行全面感知和精確控制的特殊自組織網絡。

無線傳感器網絡中的安全問題日漸被研究者關注?；叶垂羰亲罹呔W絡性能破壞力的威脅之一。無線傳感器網絡的報文依靠網絡中的節點彼此多跳接力傳輸，通常報文傳輸包括路由發現、路由回復和數據報文傳輸3個階段。傳感器網絡的自組織性允許節點的自由加入和退出，因此難以控制網絡中節點的可信程度。此外傳感器網絡中的節點通常部署在惡劣的區域，這使得傳感器網絡的節點易于被俘獲從而成為惡意節點。當惡意節點成為通信路徑上的中間節點后，在數據報文傳輸過程中，惡意節點通過故意丟棄報文對網絡通信實施攻擊，該攻擊又分為黑洞(Black Hole)和灰洞(Gray Hole)兩種攻擊類型。黑洞攻擊指網絡中的惡意節點在數據報文傳輸過程中，丟棄所有收到的數據報文。而灰洞攻擊選擇性丟棄數據報文，因此灰洞比黑洞更加隱蔽，更難以檢測?；叶垂敉ǔе戮W絡報文吞吐量下降、報文重傳率高，甚至造成網絡報文傳輸無法進行。

現有的檢測算法主要依靠統計節點的接收轉發行為來檢測灰洞。傳感器網絡本身的鏈路質量比一般網絡差，因此現有方法會產生較大的誤差，尤其當傳感器網絡處于惡劣條件下，鏈路質量問題會導致很高的誤報漏報率。本文的核心思路就是通過估計鏈路質量來修正統計結果以提高檢測正確率。

1 相關工作

1.1 鏈路質量估計

傳感器網絡與傳統網絡的一個顯著區別是網絡的動態鏈路質量特性。鏈路質量表現在通信雙方的范圍不規則不對稱，通信強度隨時間變化等方面。在質量差的通信鏈路上會有較高的自然丟包概率，選擇差鏈路質量的路由路徑會導致網絡吞吐量下降200%甚至更多［1］。準確的鏈路質量估計能夠幫助傳感器網絡節點選擇正確的路由，從而大幅優化網絡性能。

鏈路質量可以通過多個度量進行估計，如接收信號強度(RSS)、發送延時、數據包接收率(PRR)等。期望發送數指標(ETX)是最常用的鏈路質量指標，它衡量成功轉發一個報文所需的期望報文數，它的倒數為鏈路轉發成功率。此外還有其他一些指標:鏈路的不對稱指標(ETF)［2］;ETOP［3］考慮節點位置對鏈路質量的影響;Competence［4］、L-NT［5］、ENT［6］、端到端成功率［7］、數據包所需數［8］、EDR［9］等。

本文提出的檢測算法需要鏈路間的轉發成功率，也就是ETX指標的倒數，所以本文采用廣為使用的4-bits協議。4-bits協議［10］使用4 bits來綜合考慮物理層、鏈路層、網絡層的信息估計鏈路質量。該方法使用物理信號強度和網絡層擁塞程度信息做鏈路過濾，再根據鏈路層信標報文的收發統計數據來估計ETX指標。

1.2 灰洞攻擊檢測

Watchdog［11］是最早的檢測灰洞攻擊的方法，該方法中，數據傳輸的上游和下游節點的共同一跳鄰居充當看門狗節點，該節點使用混雜模式監聽介質來統計下游轉發上游節點報文的行為。如果發現下游的丟包率高于某閾值則斷定下游為惡意節點從而采取其他措施將其排除出路由。

此后有許多改進型的看門狗算法用來提高檢測準確率。文獻［12］通過選擇多個看門狗共同協作來檢測黑洞攻擊。文獻［13］提出將網絡分段，看門狗節點的檢測結果只在分段網絡中有效，這樣有效降低錯誤檢測結果在全網內的擴散。文獻［14］在路由路徑旁邊構造一條由看門狗組成的旁信道，旁信道作為主路由的參照，能夠比較出主路由中哪個節點處發生了丟包從而檢測出惡意節點。

上述看門狗算法都需要監聽上下游節點的轉發行為，根據監聽到的統計結果進行判斷。事實上，在傳感器網絡中，突發的碰撞等原因會導致鏈路質量急劇下降而使得上下游之間以及看門狗與上下游之間的轉發、監聽行為無法完成，這些自然丟包使得檢測誤報、漏報率顯著增加。

一些跨層的檢測算法考慮到了鏈路質量問題引起的誤報、漏報問題。文獻［15］使用有限狀態自動機對丟包原因進行建模，該模型中主要考慮RTS/CTS模型的沖撞概率以及鏈路錯誤概率來推導出惡意丟包概率。文獻［16］通過使用上下兩節點共同監督中間節點的模式，能夠有效降低數據包在節點間鏈路自然丟失引起的誤報率。上述2種方法都是使用排除法來推導出惡意節點的丟包概率，但是丟包原因可能有更多可能性，難以用排除法來窮盡。

本文通過使用鏈路質量估計協議估計鏈路轉發成功率，這比排除法更加通用，并且由于不用計算每種丟包原因的概率而使得健壯性更好。

2 檢測算法

2.1 模型假設

本文假設網絡中的節點沒有能量限制，每個節點都分配了公私密鑰對，并且知道其它所有節點的公鑰。這些公鑰用來保證網絡中的包不被篡改。路由的源節點和目的節點都是可靠節點。惡意節點的選擇性丟包概率與信道的自然丟包率是獨立的。信道的自然丟包率服從高斯分布。惡意節點之間相互獨立，沒有合謀攻擊。

2.2 路由選擇

源節點需要將數據發給目的節點時，會先建立一條路由。本文使用4-bits鏈路質量估計協議獲得一條從源節點到目的節點的最佳鏈路質量的路由。該協議要求節點定期與周邊鄰居交換信標報文來估計鏈路質量指標ETX。路由生成時期，每個節點估計自己到目的節點的總ETX，每個節點選擇下一跳節點中到目的節點ETX最小的節點作為轉發節點。路由選擇階段估計出的鏈路質量是該鏈路的自然鏈路質量，因為此階段惡意節點不會主動丟包以確保自己盡可能被選為路由節點。

路由路徑上的每個節點都成為其下游的主看門狗，此外根據需要還可以為其下游選擇k個輔看門狗，輔看門狗是主看門狗與其下游的公共一跳鄰居，將公共一跳鄰居按照鏈路質量排序后選擇前k個。對于每個路由節點(除源節點和目的節點外)，它至少有一個主看門狗，至多有k個輔看門狗。

2.3 檢測算法設計

為方便表達，首先介紹下文將要使用的符號。recva，b指節點 a 從節點 b 接收到的報文數。senda，b指節點a發送給節點b的報文數。鏈路質量lqa，b表示節點a發報文給節點b，節點b能正確接收到的概率。圖1給出一個典型的看門狗應用場景，節點a通過節點b給節點c發報文，看門狗節點w是節點a與節點b的共同一跳鄰居，能夠監聽到節點a發報文給節點b和節點b發報文給節點c。對于看門狗w，節點a稱為上游節點，節點b稱為下游節點。

圖1 看門狗應用場景

經典的看門狗算法中，每個看門狗節點通過比較下游節點的丟包率和設定的閾值來判定下游節點是否是惡意丟包節點。下游節點的丟包率按如下公式計算:

式(1)中，nu為下游節點正確收到上游節點發的報文數，nd為下游節點轉發的報文數?？撮T狗將自己從上游節點收到的報文數recvw，a近似為下游正確接收的報文數nu，而將從下游節點收到的報文數recvw，b近似為下游轉發的報文數nd，據此來近似計算下游節點的丟包率。

不難看出，在上述近似計算中，經典看門狗算法依賴的兩個觀察值都可能由于鏈路質量而導致誤報、漏報。如圖1中，上游a確實發了一個報文給下游b，而此時鏈路(a，w)突然出現碰撞等鏈路問題導致w沒有監聽到該動作，此時nu的估計值變小，導致計算出的Pd變小，使得漏報率上升。反之，下游b確實如實地轉發了上游的報文，而w因為鏈路(b，w)的鏈路質量問題沒有監聽到該動作，這將導致nd的估計值變小，導致計算出的Pd變大，使得誤報率上升。另外，即使看門狗對上下游的監測信息是正確的，但是由于鏈路(a，b)的鏈路質量導致下游沒有正確接收到上游的報文，這會導致誤報率上升。

本文的基本思想是通過鏈路質量估計協議估計出每條鏈路的鏈路質量，再用鏈路質量去修正統計觀察值，以更加準確地估計下游丟包率。修正方法如下:

看門狗節點自身記錄了它與鄰居間鏈路質量，但是沒有上下游之間的鏈路質量lqa，b，在4-bits鏈路質量估計協議中，a發給b的每個報文中的ETX字段記錄了兩者之間的鏈路質量，那么看門狗監聽到上游發給下游的報文，即可根據 ETX字段值計算出 lqa，b。判斷下游是否為惡意節點的依據是:

源節點每發送N個報文啟動一次檢查過程。在此過程中，源節點發送原始的檢測報文，每個收到該報文的節點將其判斷結果追加到原始報文后面，追加格式為［id，wid，，MACid］，id 為自身 id，wid 為被其監測的下游節點id是對wid監測的判斷結果，MACid是用于防止報文被修改的數字簽名。輔看門狗從主看門狗處接收檢測報文，將其對下游的判斷追加之后再返回給主看門狗。主看門狗依次將檢測報文發給輔看門狗，等輔看門狗全部追加判斷后再追加其判斷，最后將此報文發給下一跳節點。以圖1中的節點a為例，a從上游收到檢測報文M后的動作:

最終路徑中所有節點的判斷結果會匯總到目的節點，目的節點首先驗證信息摘要以確保報文沒有被篡改，然后計算最終的判決，如果節點被不少于一半的看門狗懷疑，那么這個節點被最終判為惡意節點。目的節點將判為惡意節點的id組裝成預警報文，再反向發往源節點，收到預警報文的節點發現其鄰居id在預警報文中，就將該鄰居從路由表中剔除。

2.4 參數優化

本小節主要關注閾值τ的優化，使得檢測的誤報率和漏報率最低。

在路由選擇階段，看門狗估計其監測節點的自然丟包率X1，其概率分布為 X1～N(μ1，)。該階段惡意節點為了能夠被選擇加入路由，不會主動丟包，因此此時估計出的是檢測節點的自然丟包率的概率分布。數據發送階段，看門狗估計其監測對象的總丟包率的概率分布X2～N(μ2，)。

假設該檢測對象是惡意節點，其惡意丟包率為mdr，由于自然丟包和惡意丟包是獨立事件，那么惡意節點的總丟包率為X2=1-(1-mdr)(1-X1)=X1+mdr(1-X1)。如圖2所示，此時X2＞X1，并且惡意節點的丟包率mdr越大，總丟包率X2與自然丟包率X1之間的差距越大。

圖2 最優閾值理論推導

檢測的誤報率是由自然丟包率X1超過閾值τ而引起的，即圖2中的斜線陰影區域面積。同理，檢測的漏報率是由總丟包率X2低于閾值τ而引起的，即圖2中的豎線陰影區域面積。當閾值增大時，斜線陰影區域面積減小而豎線陰影區域面積增大，即檢測誤報率降低而漏報率增大，反之亦然。最優閾值τ*應該使得檢測的誤報、漏報率之和最小。因此最佳閾值計算方法如下:

其中 fX1和 fX2分別為 X1和 X2的概率密度函數，Pfalsenegative和Pfalsepositive分別是檢測誤報率和漏報率。

路由選擇階段后，系統只知道自然丟包率X1的分布，此時將閾值設置為τ1使得誤報率低于概率Pinit，即 τ1=minτ［Pfalsenegative(τ)≤Pinit］，此后當網絡檢測出惡意節點后，獲得惡意節點的丟包概率分布X2，即可計算出當前最優閾值，經過迭代逼近τ*。

3 性能評估

本文的檢測算法在TinyOS中實現，并且在Tiny-OS自帶的TOS仿真平臺進行仿真實驗。本文的實驗拓撲如圖3所示，節點6和節點1分別為源、目的節點。實驗場景分為以下3種:場景1是單惡意節點場景，節點3為惡意節點;場景2為間隔多惡意節點場景，節點3和節點5為惡意節點;場景3為連續多惡意節點場景，節點3和節點4為惡意節點。惡意節點丟包率mdr為33%。經典看門狗算法的判斷閾值為20%。

圖3 實驗拓撲

本文主要和經典看門狗算法做性能比較，因為本文主要改進經典看門狗算法的最基礎的鏈路部分，其他基于看門狗的改進算法主要是對看門狗個數、拓撲等方面改進，這些改進方法都可以使用本文提出的方法，因此本文直接和經典看門狗算法做比較。本文的評價標準是算法的正確率(Correctness Ratio)、誤報率(False Negative Ratio)、漏報率(False Positive Ratio)和準確率(Accuracy Ratio)。正確率指算法正確判斷節點是惡意節點或正常節點的概率，誤報率指算法將正常節點判為惡意節點的概率，漏報率指算法將惡意節點判為正常節點的概率，準確率指算法將惡意節點判為惡意節點的概率。實驗的每個數據都是重復運行100次得到的均值。

圖4(a)是單惡意節點場景下的算法性能比較。隨著自然丟包率X1的增加，因為=mdr(1-X1)，所以自然丟包率X1和惡意節點總丟包率X2之間的距離減小，這使得分辨出兩者的難度增大，因此圖4(a)中算法的正確率都呈現下降趨勢，但是基于鏈路質量的看門狗算法下降趨勢較為緩慢;其次由于X2=mdr+X1(1-mdr)，隨著自然丟包率X1的增加，惡意節點總丟包率X2會增大，而經典看門狗算法的閾值固定，基于鏈路質量的看門狗算法迭代更新閾值較慢，根據公式(7)可以推出算法的漏報率會降低，所以圖4(a)中算法的準確率會隨著自然丟包率的增大而提高，但是根據公式(6)可以推出算法的誤報率會增加，圖4(a)顯示出經典看門狗算法會犧牲大量的誤報率來提高準確率，而本文的算法則通過犧牲一點準確率來保證算法的總正確率。圖4(b)是間隔多惡意節點場景下的性能比較。該場景下的性能趨勢與圖4(a)基本一致，但是多惡意節點會導致算法正確率隨著自然丟包率的增長而惡化得比單惡意節點快，說明多惡意節點之間的丟包模型會相互影響，不是完全獨立的。圖4(c)是連續多惡意節點場景下的性能比較，可以看到該場景下的性能與間隔多惡意節點場景下的性能趨勢基本一致，主要原因是惡意節點之間是獨立的，惡意節點之間沒有合謀攻擊，惡意節點只是如實地反應自己的監測結果。

圖4 算法性能比較

圖5 不同閾值下的檢測結果

圖5展現的是不同閾值下的檢測結果。在場景1下，自然丟包率為20%?？梢钥吹诫S著閾值τ的增大，檢測誤報率 Pfalsenegative(τ)會減小，而漏報率Pfalsepositive(τ)會增大，準確率是先增大后減小的趨勢。根據第2.4節參數優化的計算，可以計算出此時的最佳閾值τ*=0.336。實驗結果與第2.4節的理論分析基本符合。

4 結束語

本文提出的基于鏈路質量的看門狗算法通過估計鏈路質量來修正看門狗的檢測結果，能夠有效地降低由于鏈路質量而引起的誤報、漏報率，本文提出的最優閾值理論，能夠有效地根據網絡環境調整參數，最小化誤報、漏報概率，提高算法正確率。網絡環境越惡劣(網絡自然丟包率越高)，本文的算法越有優勢。在未來的工作中，將研究看門狗數量、拓撲對檢測結果的影響以及多個惡意節點間的合謀攻擊的檢測。

［1］De Couto D S J，Aguayo D，Bicket J，et al.A high-throughput path metric for multi-hop wireless routing［J］.Wireless Networks，2005，11(4):419-434.

［2］Sang L，Arora A，Zhang H.On exploiting asymmetric wireless links via one-way estimation［C］//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2007:11-21.

［3］Jakllari G，Eidenbenz S，Hengartner N，et al.Link positions matter:A noncommutative routing metric for wireless mesh networks［J］.IEEE Transactions on Mobile Computing，2012，11(1):61-72.

［4］Lin S，Zhou G，Whitehouse K，et al.Towards stable network performance in wireless sensor networks［C］//Proceedings of the 30th IEEE Real-Time Systems Symposium.2009:227-237.

［5］Zhang H，Sang L，Arora A.Comparison of data-driven link estimation methods in low-power wireless networks［J］.IEEE Transactions on Mobile Computing，2010，9(11):1634-1648.

［6］Draves R，Padhye J，Zill B.Comparison of routing metrics for static multi-hop wireless networks［J］.ACM SIGCOMM Computer Communication Review，2004，34(4):133-144.

［7］Gnawali O，Yarvis M，Heidemann J，et al.Interaction of retransmission，blacklisting，and routing metrics for reliability in sensor network routing［C］//Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.2004:34-43.

［8］Cerpa A，Wong J L，Potkonjak M，et al.Temporal properties of low power wireless links:Modeling and implications on multi-hop routing［C］//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2005:414-425.

［9］Gu Y，He T.Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links［C］//Proceedings of the 5th International Conference on Embedded Networked Sensor Systems.2007:321-334.

［10］Fonseca R，Gnawali O，Jamieson K，et al.Four-bit wireless link estimation［C］//Proceedings of the 6th Workshop on Hot Topics in Networks.2007.

［11］Marti S，Giuli T J，Lai K，et al.Mitigating routing misbehavior in mobile ad hoc networks［C］//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.2000:255-265.

［12］Patcha A，Mishra A.Collaborative security architecture for black hole attack prevention in mobile ad hoc networks［C］//Proceedings of the 2003 IEEE Radio and Wireless Conference.2003:75-78.

［13］Nasser N，Chen Y.Enhanced intrusion detection system for discovering malicious nodes in mobile ad hoc networks［C］//Proceedings of the 2007 IEEE International Conference on Communications.2007:1154-1159.

［14］Li X，Lu R，Liang X，et al.Side channel monitoring:Packet drop attack detection in wireless ad hoc networks［C］//Proceedings of the 2011 IEEE International Conference on Communications.2011.

［15］Hayajneh T，Krishnamurthy P，Tipper D，et al.Detecting malicious packet dropping in the presence of collisions and channel errors in wireless ad hoc networks［C］//Proceedings of the 2009 IEEE International Conference on Communications.2009:1062-1067.

［16］Shila D M，Cheng Y，Anjali T.Channel-aware detection of gray hole attacks in wireless mesh networks［C］//Proceedings of the 28th IEEE Conference on Global Telecommunications.2009:3998-4003.