車聯(lián)網(wǎng)數(shù)據(jù)完整性審計方案案例綜述目錄TOC\o"1-3"\h\u26204車聯(lián)網(wǎng)數(shù)據(jù)完整性審計方案案例綜述 1175821.1哈希平衡二叉樹 1102791.2數(shù)據(jù)完整性審計協(xié)議 7130171.2.1基于格的前向安全技術(shù) 787371.2.2車輛用戶數(shù)據(jù)完整性審計方案 8230751.2.3車輛用戶數(shù)據(jù)的動態(tài)更新 121.1哈希平衡二叉樹在實(shí)際的審計方案不應(yīng)忽視數(shù)據(jù)動態(tài)，由于車聯(lián)網(wǎng)中車輛具有高移動性和實(shí)時性，這就使得云存儲數(shù)據(jù)不僅會被訪問，而且會頻繁更新。因此，在我們的方案中有必要引入動態(tài)數(shù)據(jù)結(jié)構(gòu)。先前許多被提出的方案都是基于默克爾哈希樹[16]的。此外，Zhang等人還引入了一種特殊的樹結(jié)構(gòu)，稱為平衡更新樹。平衡更新樹支持許多新特性，如版本控制和刪除恢復(fù)。然而，平衡二叉樹的優(yōu)點(diǎn)并沒有在平衡更新樹中得到充分的利用。同時，在CSP中構(gòu)造了數(shù)據(jù)結(jié)構(gòu)，當(dāng)CSP收到審計請求時，它必須將數(shù)據(jù)塊哈希發(fā)送給第三方審計員，這將導(dǎo)致額外的傳輸和計算開銷。二叉查找樹作為一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，既有鏈表快速插入和刪除操作的特點(diǎn)，又有數(shù)組快速查找的優(yōu)勢，非常適用于本方案中查找數(shù)據(jù)所在區(qū)塊鏈中的地址與動態(tài)更新操作。平衡二叉樹(AVL樹)的查找、插入、刪除操作在平均和最壞情況下都是O(圖1.1哈希平衡二叉樹結(jié)點(diǎn)示意圖哈希平衡二叉樹(HBBT)由RSU構(gòu)建，用于存儲數(shù)據(jù)塊簽名及數(shù)據(jù)塊相關(guān)審計信息在區(qū)塊鏈中得地址，以便審核和動態(tài)上傳。如圖1.1所示，哈希平衡二叉樹的每個結(jié)點(diǎn)包含五項(xiàng)內(nèi)容，第一項(xiàng)為關(guān)鍵字項(xiàng)，第二項(xiàng)存儲該車輛數(shù)據(jù)塊簽名所在區(qū)塊鏈中的地址，第三項(xiàng)存儲該車輛數(shù)據(jù)塊相應(yīng)審計結(jié)果在區(qū)塊鏈中的地址和左右指針項(xiàng)。由車輛ID與數(shù)據(jù)塊ID連接起來，生成哈希值作為關(guān)鍵字，構(gòu)建AVL樹。其中HBBT的體系結(jié)構(gòu)相當(dāng)于AVL樹，如圖1.2所示。圖1.2哈希平衡二叉樹在接收到初始數(shù)據(jù)后，RSU初始化HBBT，并調(diào)整結(jié)構(gòu)使它平衡。保證哈希平衡二叉樹平衡的基本思想如下：每當(dāng)在樹中插入(或刪除)一個結(jié)點(diǎn)時，先檢查其插入路徑上的結(jié)點(diǎn)是否會因?yàn)榇舜尾僮鞫鴮?dǎo)致不平衡。若因此此操作導(dǎo)致了不平衡，則先找到插入路徑上距離插入結(jié)點(diǎn)最近的平衡因子的絕對值大于1的結(jié)點(diǎn)A，再對以A為根的子樹，在保持二叉排序樹特性的前提下，調(diào)整各結(jié)點(diǎn)之間的位置關(guān)系，使其重新達(dá)到平衡。哈希平衡二叉樹的插入過程的前半部分與二叉排序樹相同，但在新結(jié)點(diǎn)插入后，若造成查找路徑上的某個結(jié)點(diǎn)不再平衡，則需要做出相應(yīng)的調(diào)整。可將調(diào)整的規(guī)律歸納為如表1.1所示的下列四種情況。表1.1哈希平衡二叉樹失衡調(diào)整規(guī)律失衡原因調(diào)整規(guī)律在結(jié)點(diǎn)左孩子的左子樹上插入結(jié)點(diǎn)LL平衡旋轉(zhuǎn)在結(jié)點(diǎn)右孩子的右子樹上插入結(jié)點(diǎn)RR平衡旋轉(zhuǎn)在結(jié)點(diǎn)左孩子的右子樹上插入結(jié)點(diǎn)LR平衡旋轉(zhuǎn)在結(jié)點(diǎn)右孩子的左子樹上插入結(jié)點(diǎn)RL平衡旋轉(zhuǎn)(1)LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))：由于在結(jié)點(diǎn)A的左孩子(L)的左子樹(L)上插入了新結(jié)點(diǎn)，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要一次向右的旋轉(zhuǎn)操作。將A的左孩子B向右上旋轉(zhuǎn)代替A成為根結(jié)點(diǎn)，將A結(jié)點(diǎn)向右下旋轉(zhuǎn)成為B的右子樹的根結(jié)點(diǎn)，而B的原右子樹則作為A結(jié)點(diǎn)的左子樹。如圖1.3所示，結(jié)點(diǎn)旁的數(shù)值代表結(jié)點(diǎn)的平衡因子，而用方塊表示相應(yīng)結(jié)點(diǎn)的子樹，下方數(shù)值代表該子樹的高度。圖1.3LL平衡旋轉(zhuǎn)(2)RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))。由于在結(jié)點(diǎn)A的右孩子(R)的右子樹(R)上插入了新結(jié)點(diǎn)，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要一次向左的旋轉(zhuǎn)操作。將A的右孩子B向左上旋轉(zhuǎn)代替A成為根結(jié)點(diǎn)，將A結(jié)點(diǎn)向左下旋轉(zhuǎn)成為B的左子樹的根結(jié)點(diǎn)，而B的原左子樹則作為A結(jié)點(diǎn)的右子樹，如圖1.4所示。圖1.4RR平衡旋轉(zhuǎn)(3)LR平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))。由于在A的左孩子(L)的右子樹(R)上插入新結(jié)點(diǎn)A的平衡因子由1増至2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操作，先左旋轉(zhuǎn)后右旋轉(zhuǎn)。先將A結(jié)點(diǎn)的左孩子B的右子樹的根結(jié)點(diǎn)C向左上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置，然后再把該C結(jié)點(diǎn)向右上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置，如圖1.5所示。圖1.5LR平衡旋轉(zhuǎn)代碼清單1.1LR平衡旋轉(zhuǎn)voidLeftBalance(BiTree*T){BiTreeL,Lr;L=(*T)->lchild;switch(L->bf){case-1://新結(jié)點(diǎn)插入在T的左孩子的右子樹上，為LR型，作雙旋處理Lr=L->rchild;switch(Lr->bf){case1:(*T)->bf=-1;L->bf=0;break;case0:(*T)->bf=L->bf=0;break;case-1:(*T)->bf=0;L->bf=1;break;}Lr->bf=0;L_Rotate(&(*T)->lchild);//先對T的左子樹進(jìn)行左旋處理即RR調(diào)整R_Rotate(T);//再對T進(jìn)行右旋處理即LL調(diào)整}}(4)RL平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))。由于在A的右孩子(R)的左子樹(L)上插入新結(jié)點(diǎn)，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操作，先右旋轉(zhuǎn)后左旋轉(zhuǎn)。先將A結(jié)點(diǎn)的右孩子B的左子樹的根結(jié)點(diǎn)C向右上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置，然后再把該C結(jié)點(diǎn)向左上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置，如圖1.6所示。圖1.6RL平衡旋轉(zhuǎn)當(dāng)RSU生成挑戰(zhàn)信息后，需要對哈希平衡二叉樹進(jìn)行查找，讀取區(qū)塊鏈中存儲的相應(yīng)車輛數(shù)據(jù)塊的審計信息，看該數(shù)據(jù)塊在一定時間段內(nèi)是否被挑戰(zhàn)過，如果被挑戰(zhàn)過，我們認(rèn)為這個數(shù)據(jù)塊的完整性得到保證，短時期內(nèi)被CSP惡意篡改的概率可以忽略，因此該數(shù)據(jù)塊可以不參與本輪挑戰(zhàn)。哈希平衡二叉樹的查找算法如代碼清單1.2所示。代碼清單1.2哈希平衡二叉樹的查找算法intSearchTree(PNoderoot,dataTypekey){ if(root->keyValue==key){ return1; } elseif(key>root->keyValue&&root->rightChild){ returnSearchTree(root->rightChild,key); } elseif(key<root->keyValue&&root->leftChild){ returnSearchTree(root->leftChild,key); } else{ return0; }}在哈希平衡二又樹上進(jìn)行查找的過程與在二叉查找樹上進(jìn)行查找的過程相同。因此，在査找結(jié)點(diǎn)的過程中，與給定值進(jìn)行比較的關(guān)鍵字個數(shù)不會超過樹的深度。假設(shè)以n?表示深度為?的平衡樹中含有的最少結(jié)點(diǎn)數(shù)。顯然,有n0=0,n1=1,n2=2并且有n?1.2數(shù)據(jù)完整性審計協(xié)議1.2.1基于格的前向安全技術(shù)在我們的方案中，需要提前設(shè)置預(yù)先指定的總時間周期數(shù)目γ。我們利用格基委托技術(shù)NewBasisDel在各個時間段內(nèi)靈活地更新私鑰。更具體地來說，客戶端首先運(yùn)行NewBasisDel演化出在每個時間段i=1,2,…,γ私鑰，允許其產(chǎn)生一系列的私鑰SKIDu||1,SKIDu||2,…,SKIDu||γ,其中IDu=idu||γ，其中idu表示客戶端的標(biāo)識符信息。根據(jù)IDu、當(dāng)前時間i和相關(guān)的哈希函數(shù),對應(yīng)的在每一個時間段i的公鑰1.2.2車輛用戶數(shù)據(jù)完整性審計方案我們的數(shù)據(jù)完整性審計方案由以下九個多項(xiàng)式時間算法組成:(1)算法Setup：系統(tǒng)初始化算法由以下四個步驟組成。車輛首先對數(shù)據(jù)文件進(jìn)行預(yù)處理，將數(shù)據(jù)文件F成l個數(shù)據(jù)塊F={F1,F2,…,Fl}，其中每個系統(tǒng)設(shè)置離散的高斯分布χ。對于每一個時間周期i=1,2,…γ，為了確保SamplePre和NewBasisDel的正確執(zhí)行，系統(tǒng)分別設(shè)置了兩組安全高斯參數(shù)δ=(系統(tǒng)設(shè)置了四個抗碰撞哈希函數(shù)H1:{0,1}?→?qm×m,KGC運(yùn)行TrapGen(q,n)生成主公私密鑰對(A??qn×m,最后，系統(tǒng)初始化輸出系統(tǒng)公共參數(shù)Ω=A,(2)算法KeyExtract：KGC輸入Ω，IDu=id計算公鑰AIDu||1運(yùn)行NewBasisDel(A，RIDKGC以類似的方式生成云存儲服務(wù)器的公鑰AC=A(RIDC(3)算法KeyUpdate:作為輸入Ω、當(dāng)前時間周期i和客戶端在以前的時間周期τ的私鑰TIDu||τ，其中計算在時間周期為τ時的公鑰AIDu||計算RIDu||τ→i=H1(IDu|(4)算法MBlind：該算法用于盲化車輛數(shù)據(jù)塊。車輛IDv隨機(jī)選擇秘密種子k1∈Zp并使用帶有密鑰f的安全哈希函數(shù)去計算盲因子BFname=fk1((5)算法Aut?Gen:對于數(shù)據(jù)文件F'=F1',F2',…,Fl'，1≤計算向量λi,k計算ρj=H3(IDl|j運(yùn)行SamplePre(AIDu||認(rèn)證器集表示為Ψi(6)算法CCStorage：當(dāng)CSP收到盲數(shù)據(jù)，它重新計算盲因子BFname。然后計算{Fj|j1≤j(7)算法ProofGen：該算法用于RSU生成審計挑戰(zhàn)消息，具體過程如下所示：選擇一個全集{1,2,…,l}的隨機(jī)c個元素子集選擇一個隨機(jī)二進(jìn)制字符串υi=υ一旦接收到c?al={j,υi,j}j∈L,云服務(wù)器計算合并消息μi'=(8)算法ProofVerify：收到響應(yīng)審計證明Proof1={i計算n個向量λi,k計算ηi計算內(nèi)部產(chǎn)品?￡k=<ηi檢查驗(yàn)證方程H4wi(9)算法C?eckLog：根據(jù)系統(tǒng)公共參數(shù)集Para和RSU的審計日志，該算法輸出true或false來表示審計結(jié)果是否正確。算法1.1檢查審計日志輸入：Para，{輸出：c?ec1:forj=0ton2:θ3:λ4:(η5:fork=1tondo6:?7:endfor8:?￡9:if(H4w10:result'←11:else12:result'←13:endif14:ifresult'