章志明，鄧建剛

江西師范大學 軟件學院，南昌 330022

1 引言

無線傳感器網(wǎng)絡已經(jīng)廣泛應用于軍事、醫(yī)療、工業(yè)和環(huán)境監(jiān)測等各個領域[1]。但是在一些敏感領域需要采取一些措施來保證基站收集到的傳感數(shù)據(jù)的可信性[2]。由于溯源數(shù)據(jù)記錄了一個數(shù)據(jù)包在網(wǎng)絡傳輸中整個路徑上所有轉(zhuǎn)發(fā)或融合節(jié)點的相關(guān)信息，基站可以通過收集包含溯源信息的數(shù)據(jù)包就能夠恢復出整個數(shù)據(jù)包的傳輸路徑，因此溯源數(shù)據(jù)被認為是一種有效的方法來評估數(shù)據(jù)的真實可靠性[3]。由于傳感器節(jié)點計算、通信和存儲空間有限，因此必須設計有效的溯源數(shù)據(jù)方案。

近年來國內(nèi)外學者提出了一些有效的溯源數(shù)據(jù)方案[3-8]。為了記錄路徑上每個轉(zhuǎn)發(fā)節(jié)點的溯源信息，最基本方法是把每個節(jié)點的溯源信息直接附加到數(shù)據(jù)包上[4]，但這種方法隨著路徑長度的增加，溯源數(shù)據(jù)的大小將呈線性增加。為了減小溯源數(shù)據(jù)的大小，文獻[5]設計了一組基于概率包標記的溯源數(shù)據(jù)方案，在這些方案中，傳輸路徑上的每個節(jié)點以一定的概率，把自己的信息附加到數(shù)據(jù)包上，但基于概率包標記方案，基站需要收集到足夠多的包含溯源信息的數(shù)據(jù)包才能恢復出整個數(shù)據(jù)包的傳輸路徑。為了減少收集數(shù)據(jù)包的數(shù)量，同時減小溯源數(shù)據(jù)的大小，文獻[3,6-9]提出了基于壓縮技術(shù)的無線傳感器網(wǎng)絡溯源數(shù)據(jù)方案，文獻[3,6]提出基于布隆過濾器的溯源數(shù)據(jù)方案，但布隆過濾器存在假陽性的問題。為了解決布隆過濾器存在假陽性的問題，文獻[7]提出了一種基于算術(shù)編碼的無損壓縮溯源數(shù)據(jù)方案，文獻[8]提出一種基于數(shù)字字典的溯源數(shù)據(jù)方案，但該方案需要每個中間轉(zhuǎn)發(fā)節(jié)點存儲一個字典表，額外增加了網(wǎng)絡負擔。文獻[3-6]的溯源數(shù)據(jù)大小都會隨著路徑長度的增加而增大，并且大多數(shù)方案只考慮了溯源數(shù)據(jù)的修改或偽造攻擊，都沒有考慮多個惡意節(jié)點合謀對溯源數(shù)據(jù)發(fā)起插入、刪除和不標注等攻擊，并且不能定位到發(fā)起攻擊的惡意節(jié)點位置。

本文基于正交碼和消息鑒別碼鏈，提出一種安全有效的溯源數(shù)據(jù)傳輸方案（orthogonal code-based provenance scheme，OP）。在OP方案中，傳輸路徑上的節(jié)點收到數(shù)據(jù)包時不是把自己的溯源數(shù)據(jù)直接加入到數(shù)據(jù)包中，而是把自己的溯源數(shù)據(jù)與數(shù)據(jù)包中原有的溯源數(shù)據(jù)做正交碼加運算形成一個固定長度的常量，同時計算相關(guān)溯源數(shù)據(jù)的消息鑒別碼，并形成一個新的固定長度的消息鑒別碼鏈，最后更新數(shù)據(jù)包中的溯源數(shù)據(jù)域?；荆╞ase station,BS）收到一個包含溯源數(shù)據(jù)的數(shù)據(jù)包后，取出相關(guān)的溯源數(shù)據(jù)，恢復出可能的數(shù)據(jù)包傳輸路徑，并使用消息鑒別碼鏈對可能傳輸路徑進行驗證，驗證通過則為正確的傳輸路徑，否則通過執(zhí)行惡意節(jié)點定位算法來定位到發(fā)起攻擊的惡意節(jié)點位置。

本文的主要貢獻有：（1）基于正交碼和消息鑒別碼鏈，提出一種安全有效的溯源數(shù)據(jù)傳輸方案（OP方案）。OP方案只需要一個數(shù)據(jù)包就能恢復出數(shù)據(jù)包的傳輸路徑，并且溯源數(shù)據(jù)的大小與路徑的長度無關(guān)。（2）OP方案不僅能抵抗單個惡意節(jié)點修改或偽造溯源數(shù)據(jù)攻擊，還能抵抗多個惡意節(jié)點合謀發(fā)起的刪除、插入溯源數(shù)據(jù)等攻擊，并能定位到發(fā)起攻擊的惡意節(jié)點位置。（3）性能分析及實驗仿真表明，與現(xiàn)有的方案相比，隨著路徑長度的增加，方案在存儲空間、能量消耗等方面具有明顯優(yōu)勢。

2 相關(guān)工作

目前國內(nèi)外學者已經(jīng)提出了一些有效的溯源數(shù)據(jù)方案，這些方案大體可分為基本溯源數(shù)據(jù)方案、基于概率包標記和壓縮技術(shù)等溯源數(shù)據(jù)方案。

Hasan等人[4]提出了一種基本的溯源數(shù)據(jù)方案，在該方案中，每個節(jié)點把自己的溯源數(shù)據(jù)直接附加到數(shù)據(jù)包上，并對自己的溯源數(shù)據(jù)進行數(shù)字簽名，當BS收到含有溯源數(shù)據(jù)數(shù)的數(shù)據(jù)包后，依次取出每個節(jié)點的溯源數(shù)據(jù)，最終恢復出傳輸路徑。這種溯源數(shù)據(jù)方法隨著路徑長度的增加，溯源數(shù)據(jù)的大小將呈線性增加。

為了減小溯源數(shù)據(jù)的大小，Alam等人[5]設計了三種基于概率包標記的溯源數(shù)據(jù)方案，這三種溯源數(shù)據(jù)方案基本思想都是一樣：數(shù)據(jù)包傳輸路徑上的每個節(jié)點以一定的概率，把自己的溯源數(shù)據(jù)附加到數(shù)據(jù)包上，BS只要收集到足夠多的包含溯源信息的數(shù)據(jù)包就能恢復出整個數(shù)據(jù)包的傳輸路徑，三種方案不同在于分別利用位置序列、初等乘法和Rabin指紋技術(shù)對溯源數(shù)據(jù)進行編碼。為了減少能量的消耗，Alam等人[10]還提出了一種概率包標記的溯源數(shù)據(jù)方案，但是該方案沒有采用任何安全機制來保證數(shù)據(jù)的安全性。

為了減少收集數(shù)據(jù)包的數(shù)量，同時減小溯源數(shù)據(jù)的大小，文獻[3,6-7]提出了基于壓縮技術(shù)的無線傳感器網(wǎng)絡溯源數(shù)據(jù)方案。Sultana等人[3,6]提出基于布隆過濾器的溯源數(shù)據(jù)方案（bloom filter-based provenance scheme，BFP），在BFP方案中，每個數(shù)據(jù)包被初始化一個布隆過濾器，用于存儲路徑上每個節(jié)點的溯源數(shù)據(jù)，當收到包含布隆過濾器的數(shù)據(jù)包后，BS從數(shù)據(jù)包的布隆過濾器中取出并驗證溯源數(shù)據(jù)，最后恢復出傳輸路徑。但基于布隆過濾器的方案存在假陽性問題,為了解決布隆過濾器的假陽性問題，Hussain等人[7]提出了一種基于算術(shù)編碼的無損壓縮溯源數(shù)據(jù)方案，該方案利用算術(shù)編碼技術(shù)把路徑上每個節(jié)點的溯源數(shù)據(jù)壓縮成一個0到1之間的小數(shù)，然后把壓縮后的溯源數(shù)據(jù)附加到數(shù)據(jù)包上依次傳送給BS。該方案中，溯源數(shù)據(jù)的大小不直接依賴于傳輸路徑的長度，而是取決于節(jié)點出現(xiàn)在數(shù)據(jù)包傳輸路徑上的概率，概率越大，則溯源數(shù)據(jù)越小。為了獲取每個節(jié)點出現(xiàn)在數(shù)據(jù)包傳輸路徑上的概率，首先需要一個時間周期觀察、計算每個節(jié)點出現(xiàn)在數(shù)據(jù)包傳輸路徑上的次數(shù)。

為了解決基于有損壓縮的溯源數(shù)據(jù)方案存在溯源數(shù)據(jù)的大小隨著傳輸路徑長度增加而增大的問題，Wang等人[8]提出了一種基于字典的溯源數(shù)據(jù)方案。在該方案中，每條路徑用一條獨一無二的字典索引表示，一個數(shù)據(jù)包的溯源數(shù)據(jù)就用此數(shù)據(jù)包傳輸路徑的字典索引來表示，因為一條固定大小的路徑字典索引可以代表一條任意長度的傳輸路徑，所以數(shù)據(jù)包的溯源數(shù)據(jù)是一個與路徑長度無關(guān)的常量值。但是在該方案中，每一個節(jié)點需要存儲、維護一張經(jīng)過該節(jié)點的路徑索引字典表。Wang等人[9]還提出了一種基于動態(tài)貝葉斯網(wǎng)絡的溯源數(shù)據(jù)壓縮方案來解決基于有損壓縮的溯源數(shù)據(jù)方案存在的問題。

3 系統(tǒng)模型

3.1 正交碼

正交碼（orthogonal code）被廣泛應用于無線通訊、信息隱藏等領域[11-12]。對于正交碼的詳細定義請參考文獻[13]，正交碼的產(chǎn)生請參考文獻[14]，在此不進行詳細描述。正交碼具有以下三種特性：

（1）任意兩個相異的正交碼做內(nèi)積運算，其運算結(jié)果為0。例如，如果A、B為兩個相異的正交碼，則：

（2）任意一個正交碼與其本身做內(nèi)積運算，其運算結(jié)果為1。例如，如果A為一正交碼，則：

（3）正交碼具有可累加性，K個正交碼相加后，仍保持有（1）、（2）項的特性。例如，如果有A、B、C、D四個相異正交碼，S為A、B、C三個正交碼相加后的值，則：

從式（1）中可以判斷，A包含在S中，從式（2）中可以判斷，D不包含在S中。

3.2 網(wǎng)絡模型

整個傳感器網(wǎng)絡由n個普通節(jié)點、m個惡意節(jié)點和一個BS組成。每個節(jié)點i在部署之前都被分配一個與BS共享的對稱密鑰Ki,BS，分配一個獨一無二的正交碼作為身份標記IDi，這個身份標記就是節(jié)點附加到數(shù)據(jù)包上的溯源數(shù)據(jù)。假設在網(wǎng)絡被部署到目標區(qū)域后，每個節(jié)點不再移動，所有節(jié)點形成一棵以BS為根的樹形結(jié)構(gòu)，在網(wǎng)絡運行過程中，可能一些節(jié)點由于能量耗盡而死亡，從而引起網(wǎng)絡路徑發(fā)生變化，因此，每隔一段時間，BS將及時更新整個網(wǎng)絡的拓撲結(jié)構(gòu)。當節(jié)點感知到數(shù)據(jù)后，將通過多跳的方式把數(shù)據(jù)發(fā)送給BS，在數(shù)據(jù)包被發(fā)送給BS的過程中，每個中間轉(zhuǎn)發(fā)節(jié)點或數(shù)據(jù)融合節(jié)點將把自己的溯源數(shù)據(jù)附加到數(shù)據(jù)包上傳給下一個節(jié)點，當BS收到一個包含溯源數(shù)據(jù)的數(shù)據(jù)包，將根據(jù)溯源數(shù)據(jù)恢復出數(shù)據(jù)包的溯源路徑也即傳輸路徑。數(shù)據(jù)包的傳輸路徑分成兩種，一種是簡單路徑，如圖1（a）所示，節(jié)點n1把感知的數(shù)據(jù)分別通過節(jié)點n2、n3傳送給BS，其簡單傳輸路徑用(n1,n2,n3)表示；另一種是樹狀路徑，如圖1（b）所示，節(jié)點n4、n5分別把感知的數(shù)據(jù)發(fā)送給n6,n6對收到的數(shù)據(jù)及自己感知的數(shù)據(jù)進行融合再分別通過節(jié)點n7傳送給BS，其樹狀路徑用((n4,n5),n6,n7)表示。國內(nèi)外學者對于傳感數(shù)據(jù)的產(chǎn)生、融合已經(jīng)提出了許多方案[15-16]，本文在此不進行詳細描述，本文主要關(guān)注如何安全、有效地生成、傳送和恢復溯源數(shù)據(jù)。本文假設基站的計算、存儲和通信能力都不受限制，并且假設敵人只能俘獲普通傳感節(jié)點，而不能俘獲基站。為了方便閱讀和說明，表1對本文所用到的符號進行了描述。

Fig.1 Transmission path graphs of data packet圖1 數(shù)據(jù)包的傳輸路徑圖

Table 1 Notation definition of proposed scheme表1 符號定義表

3.3 攻擊模型與安全目標

假設在網(wǎng)絡中，除了BS不會被俘獲，其余的普通節(jié)點都有可能被俘獲，節(jié)點一旦被俘獲，攻擊者可以很容易地獲取其中的安全信息，如身份、密鑰等，并以俘獲節(jié)點為惡意節(jié)點發(fā)起一系列攻擊，這些攻擊不但會使BS做出錯誤的決策，而且會消耗大量網(wǎng)絡的寶貴資源，惡意節(jié)點能發(fā)起以下攻擊：

（1）惡意節(jié)點可以否認自己的溯源數(shù)據(jù)。

（2）惡意節(jié)點能修改數(shù)據(jù)包上的溯源數(shù)據(jù)。

（3）一個或多個惡意節(jié)點能單獨或合謀刪除數(shù)據(jù)包上的溯源數(shù)據(jù)。例如，在圖2（a）中，惡意節(jié)點n4試圖刪除節(jié)點n3的溯源數(shù)據(jù)，使路徑變成{n1,n2,n4,n5,n6}。路徑上多個惡意節(jié)點也可能合謀刪除數(shù)據(jù)包上的溯源數(shù)據(jù)，例如，在圖2（b）中，惡意節(jié)點n2和n4試圖合謀刪除節(jié)點n3的溯源數(shù)據(jù)，使路徑變成{n1,n2,n4,n5,n6}。

Fig.2 Malicious nodes attack graphs(black nodes represent malicious nodes and white nodes represent normal nodes)圖2 惡意節(jié)點攻擊示意圖（黑色節(jié)點表示惡意節(jié)點，白色節(jié)點表示正常節(jié)點）

（4）一個或多個惡意節(jié)點能故意不標注自己的溯源數(shù)據(jù)，從而達到欺騙BS的目的。例如，在圖2（c）中，惡意節(jié)點n3和n4故意不把自己的溯源數(shù)據(jù)增加到數(shù)據(jù)包上，此時，路徑變成{n1,n2,n5,n6}。

（5）多個惡意節(jié)點能合謀往數(shù)據(jù)包上插入一條或多條溯源數(shù)據(jù)。例如，在圖2（d）中，惡意節(jié)點n3和n4合謀往數(shù)據(jù)包上插入了一條惡意節(jié)點n4的溯源數(shù)據(jù)，此時路徑變成{n1,n2,n3,n4,n5,n6}。

本文提出方案的安全目標是能抵抗惡意節(jié)點發(fā)起的以上攻擊。

4 安全有效的溯源數(shù)據(jù)方案

本文提出的溯源數(shù)據(jù)方案（OP方案）具體分為產(chǎn)生溯源數(shù)據(jù)、恢復溯源數(shù)據(jù)和驗證溯源數(shù)據(jù)三個步驟。

4.1 產(chǎn)生溯源數(shù)據(jù)

溯源數(shù)據(jù)產(chǎn)生是指數(shù)據(jù)包傳輸路徑上每個節(jié)點生成自己的溯源數(shù)據(jù)并把溯源數(shù)據(jù)附加到數(shù)據(jù)包上的過程。整個數(shù)據(jù)包傳輸路徑上包含三種節(jié)點：產(chǎn)生數(shù)據(jù)包的源節(jié)點、僅轉(zhuǎn)發(fā)數(shù)據(jù)包的轉(zhuǎn)發(fā)節(jié)點和融合數(shù)據(jù)的融合節(jié)點。接下來將分別詳細描述這三種節(jié)點產(chǎn)生溯源數(shù)據(jù)的過程。

（1）源節(jié)點產(chǎn)生溯源數(shù)據(jù)

當源節(jié)點S想要發(fā)送傳感數(shù)據(jù)給BS，在生成完數(shù)據(jù)包后，它將在數(shù)據(jù)包上創(chuàng)建四個字段用于存儲數(shù)據(jù)包的溯源數(shù)據(jù)，字段格式如表2所示。其中，Seq-Number字段存放當前數(shù)據(jù)包的標識，Count字段存放源節(jié)點距離BS的跳數(shù)，Provenance字段存放節(jié)點的溯源數(shù)據(jù)，MAC字段存放溯源數(shù)據(jù)的消息鑒別碼。創(chuàng)建完存儲溯源數(shù)據(jù)的字段后，節(jié)點S產(chǎn)生一個數(shù)據(jù)包序列號SN存入Seq-Number字段，使Count字段的值為1，把PVS=IDS作為溯源數(shù)據(jù)存入Provenance字段，計算MACS=CKS,BS(PVS)作為溯源數(shù)據(jù)的消息鑒別碼并存入MAC字段，最后把包含溯源數(shù)據(jù)的數(shù)據(jù)包發(fā)送給下一個節(jié)點。圖1（a）中的數(shù)據(jù)源節(jié)點n1產(chǎn)生的溯源數(shù)據(jù)如表2所示。

Table 2 Provenance of source noden1表2 源節(jié)點n1的溯源數(shù)據(jù)

（2）轉(zhuǎn)發(fā)節(jié)點產(chǎn)生溯源數(shù)據(jù)

當一個中間轉(zhuǎn)發(fā)節(jié)點ni收到序列號為SN的數(shù)據(jù)包，它將更新Count字段的值，使Count=Count+1，計算PVi=PVi-1+IDi作為溯源數(shù)據(jù)并更新Provenance字段，計算MACi=MACi-1⊕CKi,BS(PVi)作為溯源數(shù)據(jù)的消息鑒別碼并更新MAC字段，最后把更新后數(shù)據(jù)包發(fā)送給下一個節(jié)點。圖1（a）中的節(jié)點n2和n3產(chǎn)生的溯源數(shù)據(jù)分別如表3和表4所示。

Table 3 Provenance of forwarding noden2表3 轉(zhuǎn)發(fā)節(jié)點n2的溯源數(shù)據(jù)

Table 4 Provenance of forwarding noden3表4 轉(zhuǎn)發(fā)節(jié)點n3的溯源數(shù)據(jù)

（3）融合節(jié)點產(chǎn)生溯源數(shù)據(jù)

當一個融合節(jié)點nj收到孩子節(jié)點nj1和nj2發(fā)送的數(shù)據(jù)，它首先把nj1、nj2和自己的數(shù)據(jù)融合、生成新的數(shù)據(jù)包，然后分別從nj1和nj2原來數(shù)據(jù)包中取出溯源數(shù)據(jù)，使Count=Count+1，并把Count值存入新融合數(shù)據(jù)包的Count字段，計算PVj=PVj1+PVj2+IDj作為新的溯源數(shù)據(jù)并存入新融合數(shù)據(jù)包的Provenance字段，計算MACj=MACj1⊕MACj2⊕CKj,BS(PVj)作為溯源數(shù)據(jù)的消息鑒別碼并存入新融合數(shù)據(jù)包的MAC字段，最后把新融合數(shù)據(jù)包發(fā)送給下一個節(jié)點。圖1（b）中的節(jié)點n6產(chǎn)生的溯源數(shù)據(jù)如表5所示。

4.2 恢復溯源數(shù)據(jù)

當BS收到一個節(jié)點nt發(fā)送的數(shù)據(jù)包，它取出數(shù)據(jù)包Count字段的值，設為Length，取出Provenance字段的值，設為PVt，然后以節(jié)點nt為根節(jié)點，在網(wǎng)絡中進行深度優(yōu)先搜索（depth first search，DFS），找到M條長度為Length的路徑集合P[M]。然后在P[M]集合中找出一條或多條路徑，使這一條或多條路徑上的所有節(jié)點的身份標記IDi與PVt分別做正交碼的內(nèi)積運算，結(jié)果都等于1，因為根據(jù)正交碼的特性，如果都等于1，可知這一條或多條路徑上的所有節(jié)點的溯源數(shù)據(jù)都在PVt中，則這一條或多條路徑就是此數(shù)據(jù)包的可能傳輸路徑，如果傳輸路徑是多條，則把這多條路徑合并成一條具有樹型結(jié)構(gòu)的融合路徑。如果P[M]集合中沒有一條路徑上的所有節(jié)點的身份標記IDi與PVt分別做正交碼的內(nèi)積運算，結(jié)果都等于1，表示此數(shù)據(jù)包受到攻擊，BS將立即丟棄該數(shù)據(jù)包。具體查找數(shù)據(jù)包的可能傳輸路徑算法如算法1所示，根據(jù)算法1，圖1（a）是一條簡單的可能傳輸路徑，用(n1,n2,n3)表示，圖1（b）是一條樹狀的可能傳輸路徑，用((n4,n5),n6,n7)表示。

Table 5 Provenance of forwarding noden6表5 轉(zhuǎn)發(fā)節(jié)點n6的溯源數(shù)據(jù)

算法1查找數(shù)據(jù)包的可能傳輸路徑

輸入：M條長度為Length的路徑集合P[M]；數(shù)據(jù)包的溯源數(shù)據(jù)PVt。

輸出：數(shù)據(jù)包的可能傳輸路徑(transmission path,TP)

4.3 驗證溯源數(shù)據(jù)

溯源數(shù)據(jù)具體驗證算法如算法2所示。BS根據(jù)算法1得到數(shù)據(jù)包的可能傳輸路徑（TP），依次從路徑TP中取出節(jié)點的身份標記IDi，按照4.1節(jié)產(chǎn)生溯源數(shù)據(jù)的方法，依次計算得到各節(jié)點的溯源數(shù)據(jù)和對應的消息鑒別碼PV=[PV1',PV2',…,PVt']，MAC=[MAC1',MAC2',…,MACt']；然后從收到的數(shù)據(jù)包中取出Provenance字段的值，設為PVt，取出MAC字段的值，設為MACt；最后比較MACt'是否與MACt相等，如果相等，則表示路徑TP上所有節(jié)點的溯源數(shù)據(jù)是真實的，否則表示路徑TP上節(jié)點的溯源數(shù)據(jù)被篡改。如果節(jié)點的溯源數(shù)據(jù)被篡改，BS將從路徑TP的最后一個節(jié)點nt開始向前依次驗證每個節(jié)點的溯源數(shù)據(jù)，從而定位到發(fā)起攻擊的惡意節(jié)點位置，具體惡意節(jié)點定位算法如算法3所示。

算法2溯源數(shù)據(jù)驗證算法

輸入：數(shù)據(jù)包的可能傳輸路徑TP；數(shù)據(jù)包MAC字段的值MACt。

輸出：驗證通過返回True，否則返回False。

從路徑TP恢復出的溯源數(shù)據(jù)PV=[PV1',PV2',…,PVt']；

從路徑TP恢復出的消息鑒別碼MAC=[MAC1',MAC2',…,MACt']。

算法3惡意節(jié)點定位算法

輸入：從路徑TP恢復出的溯源數(shù)據(jù)PV=[PV1',PV2',…,PVt']；從路徑TP恢復出的消息鑒別碼MAC=[MAC1',MAC2',…,MACt']；數(shù)據(jù)包MAC字段的值MACt。

輸出：惡意節(jié)點ni。

5 安全性分析

3.3節(jié)分析了攻擊者一旦俘獲了網(wǎng)絡中的某些節(jié)點，將以俘獲節(jié)點為惡意節(jié)點發(fā)起一系列攻擊，這些攻擊不但會使BS做出錯誤的決策，而且會消耗大量網(wǎng)絡的寶貴資源。本章將討論本文提出的OP方案如何抵抗3.3節(jié)提出的惡意節(jié)點發(fā)起的圖2所示的一系列攻擊。

定理1任何一個節(jié)點都不能否認自己的溯源數(shù)據(jù)。

證明每個節(jié)點ni往數(shù)據(jù)包的溯源數(shù)據(jù)字段上更新自己的溯源數(shù)據(jù)時，同時用自己與BS共享的對稱密鑰Ki,BS計算對應的消息鑒別碼。假如一個惡意節(jié)點ni往溯源數(shù)據(jù)字段上更新自己的溯源數(shù)據(jù)PVi=PVi-1+IDi時，用前一個節(jié)點ni-1的消息鑒別碼MACi-1來代替自己對PVi計算的消息鑒別碼MACi，以此來否認自己的溯源數(shù)據(jù)，則根據(jù)算法2和算法3就能驗證并定位到節(jié)點ni，因此任何一個節(jié)點不能否認自己的溯源數(shù)據(jù)。

定理2任何一個惡意節(jié)點不能修改數(shù)據(jù)包溯源數(shù)據(jù)字段上的溯源數(shù)據(jù)而不被檢測。

證明一個惡意節(jié)點ni收到它前一個節(jié)點ni-1發(fā)送的溯源數(shù)據(jù)，它既可以修改溯源數(shù)據(jù)PVi-1，也可以修改PVi-1的消息鑒別碼MACi-1。當它僅修改PVi-1時，根據(jù)算法1將不能恢復出任何一條可能的傳輸路徑TP，BS將丟棄該數(shù)據(jù)包；當它僅修改消息鑒別碼MACi-1時，則根據(jù)算法2和算法3就能驗證并定位到節(jié)點ni，因此任何一個惡意節(jié)點不能修改數(shù)據(jù)包溯源數(shù)據(jù)字段上的溯源數(shù)據(jù)而不被檢測。

定理3任何一個或多個惡意節(jié)點不能單獨或合謀從數(shù)據(jù)包溯源數(shù)據(jù)字段上刪除一條或多條溯源數(shù)據(jù)而不被檢測。

證明一個或多個惡意節(jié)點收到數(shù)據(jù)包時，刪除數(shù)據(jù)包溯源數(shù)據(jù)字段上的一條或多條溯源數(shù)據(jù)有兩種情況。

第一種情況是惡意節(jié)點ni刪除它前面的一個或多個節(jié)點的溯源數(shù)據(jù)。例如，在圖2（a）中，惡意節(jié)點n4試圖刪除節(jié)點n3的溯源數(shù)據(jù)，在這種情況下，因為n4收到n3發(fā)送給它的溯源數(shù)據(jù)PV3為節(jié)點n4前面所有節(jié)點的身份標記值做正交碼加運算得到的一個新的正交碼值，即PV3=PV1+PV2+ID3，所以它沒辦法從PV3中刪除節(jié)點n3身份標記值；同樣溯源數(shù)據(jù)的消息鑒別碼MAC3=MAC1⊕MAC2⊕CK3,BS(PV3)，由于它沒有節(jié)點n3與BS共享的對稱密鑰K3,BS，不能計算出PV3的消息鑒別碼CK3,BS(PV3)，因此它也沒辦法從MAC3中刪除節(jié)點n3的消息鑒別碼CK3,BS(PV3)。

第二種情況是多個惡意節(jié)點合謀刪除它們之間的一個或多個節(jié)點的溯源數(shù)據(jù)。例如，在圖2（b）中，惡意節(jié)點n2和n4試圖合謀刪除節(jié)點n3的溯源數(shù)據(jù)，當n2收到溯源數(shù)據(jù)時它直接把數(shù)據(jù)包發(fā)送給另一個惡意節(jié)點n4，通過跳過節(jié)點n3從而達到刪除節(jié)點n3的溯源數(shù)據(jù)的目的。在這種情況下，傳輸路徑TP={n1,n2,n4,n5,n6}，路徑長度為5。BS收到數(shù)據(jù)包后，通過深度優(yōu)先（DFS）搜索，找到1條長度為5的路徑集合P[1]={n2,n3,n4,n5,n6}，然后根據(jù)算法1可知路徑集合P[1]中沒有任何一條有效的傳輸路徑，表示此數(shù)據(jù)包受到攻擊，BS將立即丟棄該數(shù)據(jù)包。

綜上所述，任何一個或多個惡意節(jié)點不能單獨或合謀從數(shù)據(jù)包溯源數(shù)據(jù)字段上刪除一條或多條溯源數(shù)據(jù)而不被檢測。

定理4任何一個或多個惡意節(jié)點不能故意不標注自己的溯源數(shù)據(jù)而不被檢測。

證明一個或多個惡意節(jié)點收到溯源數(shù)據(jù)時，它可以故意不標注自己的溯源數(shù)據(jù)。例如，在圖2（c）中，惡意節(jié)點n3和n4故意不把自己的溯源數(shù)據(jù)更新到數(shù)據(jù)包溯源數(shù)據(jù)字段上，以此達到欺騙BS的目的。在這種情況下，傳輸路徑TP={n1,n2,n5,n6}，路徑長度為4。BS收到數(shù)據(jù)包后，通過深度優(yōu)先（DFS）搜索，找到1條長度為4的路徑集合P[1]={n3,n4,n5,n6}，然后根據(jù)算法1可知路徑集合P[1]中沒有任何一條有效的傳輸路徑，表示此數(shù)據(jù)包受到攻擊，BS將立即丟棄該數(shù)據(jù)包，因此任何一個或多個惡意節(jié)點不能故意不標注自己的溯源數(shù)據(jù)而不被檢測。 □

定理5多個惡意節(jié)點不能合謀往數(shù)據(jù)包溯源數(shù)據(jù)字段上插入一條或多條溯源數(shù)據(jù)而不被檢測。

證明一個惡意節(jié)點收到溯源數(shù)據(jù)時，可以與路徑外的另一個或多個惡意節(jié)點合謀往數(shù)據(jù)包溯源數(shù)據(jù)字段上插入一條或多條溯源數(shù)據(jù)。例如，在圖2（d）中，惡意節(jié)點n3和n4合謀往數(shù)據(jù)包溯源數(shù)據(jù)字段上插入了一條不在本次數(shù)據(jù)包傳輸路徑上的惡意節(jié)點n4的溯源數(shù)據(jù)。在這種情況下，傳輸路徑TP={n1,n2,n3,n4,n5,n6}，路徑長度為6。BS收到數(shù)據(jù)包后，通過深度優(yōu)先搜索，找到長度為6的但不包括節(jié)點n4的路徑集合，假設圖（d）中的節(jié)點n1前面還有一個節(jié)點n0，則通過深度優(yōu)先搜索出的路徑集合P[1]={n0,n1,n2,n3,n5,n6}，然后根據(jù)算法1可知路徑集合P[1]中沒有任何一條有效的傳輸路徑，表示此數(shù)據(jù)包受到攻擊，BS將立即丟棄該數(shù)據(jù)包，因此多個惡意節(jié)點不能合謀往數(shù)據(jù)包溯源數(shù)據(jù)字段上插入一條或多條溯源數(shù)據(jù)而不被檢測。 □

6 性能分析

本文提出的OP方案將與文獻[4,6]及基于簡單消息鑒別碼的MP（message authentication code-based provenance scheme）方案在存儲空間和能量消耗方面進行比較。文獻[6]提出一種基于布隆過濾器的方案（bloom filter-based provenance scheme，BFP），它使用一個固定大小的布隆過濾器來嵌入傳輸路徑上所有節(jié)點的溯源數(shù)據(jù)。文獻[4]提出了一種安全的溯源數(shù)據(jù)方案（secure provenance scheme，SSP）。為了方便比較，與文獻[6]一樣，把SSP方案中每個節(jié)點i的溯源數(shù)據(jù)簡化為Pi=＜ni,hash(Di),Ci＞，其中ni表示節(jié)點的身份標記，hash(Di)表示對數(shù)據(jù)進行哈希運算，Ci=Sign(ni,hash(Di)|Ci-1)表示對ni,hash(Di),Ci-1的數(shù)字簽名。與文獻[6]一樣，也考慮一種基于簡單消息鑒別碼的方案MP，在MP方案中傳輸路徑上的每個節(jié)點ni依次把自己的身份標記IDi和身份標記的消息鑒別碼直接附加到數(shù)據(jù)包中。

6.1 存儲開銷

假設從源節(jié)點到基站的傳輸路徑長度為L，文獻[4]的SSP方案和基于簡單消息鑒別碼的MP方案中的一個節(jié)點身份標記長度為2 Byte，本文提出的OP方案的一個節(jié)點身份標記長度為4 Byte，一個數(shù)據(jù)包序列號（Seq-Number）長度為12 bit，數(shù)據(jù)包中源節(jié)點距離BS的跳數(shù)（Count）用12 bit存儲。在文獻[6]的BFP方案中，一個數(shù)據(jù)包的溯源數(shù)據(jù)需要的存儲開銷為-L×ln(Pfp)/(ln2)2，其中Pfp為布隆過濾器假陽性概率。在文獻[4]中，使用SHA-1作為加密哈希算法，產(chǎn)生固定長度為160 bit的哈希值，使用文獻[17]的數(shù)字簽名方法，產(chǎn)生長度為160 bit的數(shù)字簽名，則SSP方案中，一個數(shù)據(jù)包的溯源數(shù)據(jù)需要的存儲開銷為L×42 Byte。在基于簡單消息鑒別碼的方案MP中，使用文獻[18]的方法產(chǎn)生長度為4 Byte的消息鑒別碼，則MP方案中，一個數(shù)據(jù)包的溯源數(shù)據(jù)需要的存儲開銷為L×6 Byte。在本文提出的OP方案中，一個數(shù)據(jù)包的溯源數(shù)據(jù)由4個字段組成，如表2所示，即一個數(shù)據(jù)包的溯源數(shù)據(jù)可表示為＜SNi,count,PVi,MACi＞。其中，SNi表示長度為12 bit的數(shù)據(jù)包序列號（Seq-Number）；count表示長度為12 bit的源節(jié)點距離BS的跳數(shù)；PVi表示傳輸路徑上所有節(jié)點的身份標記IDi做正交碼的加運算得到的結(jié)果，根據(jù)正交碼加運算性質(zhì)，任意多個正交碼做加運算的結(jié)果其長度不變，即一個節(jié)點身份標記IDi長度為4 Byte，則PVi的長度仍然為4 Byte；MACi表示長度為128 bit的消息鑒別碼。因此在本文提出的OP方案中，一個數(shù)據(jù)包的溯源數(shù)據(jù)需要的存儲開銷為23 Byte。綜上所述，BFP方案、SSP方案和MP方案都與傳輸路徑長度有關(guān)，隨著傳輸路徑長度增加，其存儲開銷也隨之增加。而OP方案的PVi是正交碼做加運算的結(jié)果，其值是固定長度，MACi是多個消息鑒別碼做異或運算的結(jié)果，其值也是固定長度，因此OP方案的溯源數(shù)據(jù)存儲開銷為一個常量。表6描述了本文提出的OP方案與BFP方案、SSP方案、MP方案的具體存儲開銷，其中L表示從源節(jié)點到基站的傳輸路徑長度。

Table 6 Comparison of storage overhead表6 存儲開銷比較表

6.2 能量消耗

節(jié)點能量的消耗主要是對數(shù)據(jù)包的接收和發(fā)送，與數(shù)據(jù)包的大小直接相關(guān)。假設數(shù)據(jù)包的傳輸路徑長度為L，在BFP方案、SSP方案和MP方案中，一個數(shù)據(jù)包的溯源數(shù)據(jù)需要的存儲開銷分別為-L×ln(Pfp)/(ln2)2、L×42 Byte和L×6 Byte，其相應的能量消耗也分別與 -L×ln(Pfp)/(ln2)2、L×42 Byte和L×6 Byte成比例增加。而在本文提出的OP方案中，溯源數(shù)據(jù)存儲開銷為一個常量，顯然，隨著傳輸路徑長度增加，OP方案的能量消耗要比其他方案要少很多。

6.3 計算開銷

本節(jié)將分析本文提出的OP方案的計算開銷。由于OP方案假設BS的計算、存儲和通信能力都不受限制，因此不討論BS恢復和驗證溯源數(shù)據(jù)的計算開銷，只分析數(shù)據(jù)源節(jié)點、融合節(jié)點和中間轉(zhuǎn)發(fā)節(jié)點的計算開銷。本文不考慮節(jié)點收集數(shù)據(jù)、產(chǎn)生數(shù)據(jù)包和把數(shù)據(jù)存入數(shù)據(jù)包等基本操作，重點分析節(jié)點的計算操作。用OP_Add表示執(zhí)行一次正交碼的加運算，OP_XOR表示執(zhí)行一次異或運算，OP_MAC表示執(zhí)行一次計算消息M的消息鑒別碼運算。OP方案的計算開銷主要由源節(jié)點產(chǎn)生溯源數(shù)據(jù)，轉(zhuǎn)發(fā)節(jié)點產(chǎn)生溯源數(shù)據(jù)和融合節(jié)點產(chǎn)生溯源數(shù)據(jù)三部分組成。

（1）源節(jié)點產(chǎn)生溯源數(shù)據(jù)。源節(jié)點產(chǎn)生溯源數(shù)據(jù)的主要計算操作為計算一次自己身份標記的消息鑒別碼，因此源節(jié)點的計算開銷為：

（2）轉(zhuǎn)發(fā)節(jié)點產(chǎn)生溯源數(shù)據(jù)。當轉(zhuǎn)發(fā)節(jié)點i收到數(shù)據(jù)包時，它的主要計算操作為：將自己的溯源數(shù)據(jù)IDi與數(shù)據(jù)包中的溯源數(shù)據(jù)PVi-1做正交碼加運算，得到一個固定長度的常量值PVi作為新的溯源數(shù)據(jù)，然后計算PVi的消息鑒別碼，并與數(shù)據(jù)包中的原消息鑒別碼MACi-1做異或運算，得到新的溯源數(shù)據(jù)的消息鑒別碼MACi。因此，轉(zhuǎn)發(fā)節(jié)點的計算開銷為：

（3）融合節(jié)點產(chǎn)生溯源數(shù)據(jù)。當一個融合節(jié)點j收到m個孩子節(jié)點發(fā)送的數(shù)據(jù)包，它的主要計算操作為：將自己的溯源數(shù)據(jù)IDj與m個孩子節(jié)點發(fā)送的數(shù)據(jù)包中的溯源數(shù)據(jù)做正交碼加運算，得到一個固定長度的常量值PVj作為新的溯源數(shù)據(jù)，然后計算PVj的消息鑒別碼，并與m個孩子節(jié)點發(fā)送的數(shù)據(jù)包中的原消息鑒別碼做異或運算，得到新的溯源數(shù)據(jù)的消息鑒別碼MACj。因此，融合節(jié)點的計算開銷為：

綜上所述，OP方案的計算開銷主要是執(zhí)行了正交碼的加運算、異或運算和計算消息鑒別碼運算，其中正交碼的加運算本質(zhì)上是一種類似于異或運算的操作，而異或運算和計算消息鑒別碼運算都是密碼學中最基本的輕量級操作，因此OP方案是一種輕量級的安全有效方案。

7 仿真實驗

仿真實驗環(huán)境是在TinyOS-2.1.2的TOSSIM平臺上進行，在Tiny OS上配置Power TOSSIMz插件來仿真節(jié)點能量的消耗。100個節(jié)點隨機分布在100 m×100 m的正方形區(qū)域內(nèi)，在節(jié)點被部署之前，按文獻[16]的方法為每個節(jié)點分配一個獨一無二的正交碼作為節(jié)點的身份編號，BS作為目的節(jié)點放置在區(qū)域的中心位置，節(jié)點部署之后將不再移動。隨機選取網(wǎng)絡的一些節(jié)點作為數(shù)據(jù)源節(jié)點、融合節(jié)點和惡意節(jié)點，其他節(jié)點作為中間轉(zhuǎn)發(fā)節(jié)點。數(shù)據(jù)源節(jié)點每隔1 s通過多跳的方式向BS發(fā)送一次數(shù)據(jù)，每個數(shù)據(jù)包的長度為256 Byte。當惡意節(jié)點成為中間轉(zhuǎn)發(fā)節(jié)點后，它將以一定的概率篡改轉(zhuǎn)發(fā)的數(shù)據(jù)包。對于每個設置的參數(shù)，取仿真50次得到的平均值。

7.1 性能指標

與文獻[6]一樣，本節(jié)從以下幾方面對方案的性能進行仿真評估。

（1）驗證錯誤率

當BS收到源節(jié)點發(fā)送的數(shù)據(jù)包，它將執(zhí)行算法1和算法2恢復和驗證數(shù)據(jù)包中的溯源數(shù)據(jù)，由于溯源數(shù)據(jù)被惡意節(jié)點篡改或網(wǎng)絡拓撲結(jié)構(gòu)的改變，使得溯源數(shù)據(jù)不正確，從而驗證失敗。假設BS總共收到L個數(shù)據(jù)包，其中有d個數(shù)據(jù)包的溯源數(shù)據(jù)不正確，則驗證錯誤率。

（2）平均溯源數(shù)據(jù)大小

假設BS收到L個數(shù)據(jù)包，平均溯源數(shù)據(jù)大?。╝verage provenance size，APS）是指L個數(shù)據(jù)包的溯源數(shù)據(jù)長度的平均值，即：

其中，PRi表示數(shù)據(jù)包Pi的溯源數(shù)據(jù)長度值。

（3）總能量消耗

假設網(wǎng)絡中共有L個節(jié)點，總能量消耗（total energy consumption，TEC）是指L個節(jié)點能量消耗總和，即：

其中，ECi表示節(jié)點ni的能量消耗。

7.2 仿真結(jié)果

當BS收到源節(jié)點發(fā)送的數(shù)據(jù)包，它將試圖恢復和驗證數(shù)據(jù)包中的溯源數(shù)據(jù)，從而恢復數(shù)據(jù)的完整傳輸路徑。由于網(wǎng)絡拓撲結(jié)構(gòu)的改變或溯源數(shù)據(jù)被惡意節(jié)點篡改，使得溯源數(shù)據(jù)不正確，從而驗證失敗。圖3（a）描述了路徑長度分別為2、4、6、8、10、12和14跳，OP方案與BFP方案的驗證錯誤率。從圖3（a）中可以看出，當BFP方案的布隆過濾器大小為20 Byte，路徑長度大于8跳時，驗證錯誤率要明顯高于OP方案，這是由于布隆過濾器存在假陽性的問題，即把不在集合中的元素錯判成集合中的元素，從而在一定程度上影響了BFP方案的驗證錯誤率。圖3（b）描述了路徑中存在惡意節(jié)點，并且惡意節(jié)點篡改數(shù)據(jù)的概率q分別為0.1、0.2和0.3的情況下，路徑長度為8跳，數(shù)據(jù)包個數(shù)分別從0到60時，OP方案的驗證錯誤率。從圖3（b）中可以看出，隨著惡意節(jié)點篡改數(shù)據(jù)概率增大，驗證錯誤率也越來越大，但是隨著數(shù)據(jù)包個數(shù)的增加，驗證錯誤率將趨于穩(wěn)定，例如，當數(shù)據(jù)包個數(shù)超過40個時，驗證錯誤率都接近于0.02。

Fig.3 Verification error rate圖3 驗證錯誤率

圖4描述了OP方案、BFP方案、SSP方案和MP方案包在路徑長度分別為2、4、6、8、10、12和14跳時的平均溯源數(shù)據(jù)大小。在SSP方案和MP方案中，傳輸路徑上的每個節(jié)點收到數(shù)據(jù)包時都是直接把自己的溯源數(shù)據(jù)加入到數(shù)據(jù)包中，因此溯源數(shù)據(jù)大小與傳輸路徑長度直接相關(guān)，隨著傳輸路徑長度增加，其平均溯源數(shù)據(jù)大小呈線性增加。雖然BFP方案的溯源數(shù)據(jù)大小也與傳輸路徑長度相關(guān)，但沒有SSP方案和MP方案明顯。而在本文提出的OP方案中，傳輸路徑上的每個節(jié)點收到數(shù)據(jù)包時不是直接把自己的溯源數(shù)據(jù)加入到數(shù)據(jù)包中，而是把自己的溯源數(shù)據(jù)與數(shù)據(jù)包中的溯源數(shù)據(jù)做正交碼加和異或運算，其結(jié)果是一個固定長度值。從圖4中可以看出，當路徑長度大于4跳時，OP方案的平均溯源數(shù)據(jù)大小要明顯低于MP方案，當路徑長度小于10跳時，OP方案的平均溯源數(shù)據(jù)要略大于BFP方案，但當路徑長度大于10跳時，OP方案的平均溯源數(shù)據(jù)要小于BFP方案。

Fig.4 Average provenance size under different path lengths圖4 不同路徑長度下的平均溯源數(shù)據(jù)大小

圖5描述了路徑長度分別為2、4、6、8、10、12和14跳，OP方案、BFP方案和MP方案總能量消耗。從圖5中可以看出，當路徑長度超過8跳時，MP方案能量消耗急劇增加，遠遠大于OP和BFP方案，這是由于MP方案中每個數(shù)據(jù)包的溯源數(shù)據(jù)大小與路徑長度呈線性關(guān)系。從圖5中可以看出，當路徑長度超過8跳時，OP方案總能量的消耗要小于BFP方案。

8 總結(jié)

Fig.5 Total energy consumption under different path lengths圖5 不同路徑長度下的總能量消耗

本文利用正交碼和消息鑒別碼鏈，提出一種安全有效的溯源數(shù)據(jù)傳輸方案（OP方案）。OP方案把正交碼作為身份標記ID（溯源數(shù)據(jù)），當傳輸路徑上的一個節(jié)點ni收到數(shù)據(jù)包時把自己的溯源數(shù)據(jù)與數(shù)據(jù)包中的溯源數(shù)據(jù)做正交碼加運算，產(chǎn)生一個固定長度的溯源數(shù)據(jù)作為數(shù)據(jù)包的新溯源數(shù)據(jù)，并且形成一個新的固定長度的消息鑒別碼鏈。通過溯源數(shù)據(jù)的正交加運算，OP方案只需要一個數(shù)據(jù)包就能恢復出數(shù)據(jù)包的傳輸路徑，并且溯源數(shù)據(jù)的大小與路徑的長度無關(guān)。通過消息鑒別碼鏈，OP方案不僅能抵抗單個惡意節(jié)點修改或偽造溯源數(shù)據(jù)攻擊，還能抵抗多個惡意節(jié)點合謀發(fā)起的刪除、插入溯源數(shù)據(jù)等攻擊，并能定位到發(fā)起攻擊的惡意節(jié)點位置。性能分析及實驗仿真表明與現(xiàn)有的方案相比，隨著路徑長度的增加，方案在存儲空間、能量消耗等方面也具有明顯優(yōu)勢。