[發(fā)明專利]基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法

有效

• 申請?zhí)枺?/td>: 202110395631.8
• 申請日: 2021-04-13
• 公開（公告）號: CN113076319B
• 公開（公告）日: 2022-05-06
• 發(fā)明（設(shè)計）人: 杜瑞忠;張玉晴
• 申請（專利權(quán)）人: 河北大學(xué)
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F21/62
• 代理公司: 石家莊國域?qū)＠虡?biāo)事務(wù)所有限公司 13112
• 代理人: 胡素梅

本發(fā)明提供了一種基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法。該方法包括如下步驟：首先生成填充數(shù)據(jù)庫，利用離群值檢測技術(shù)選擇符合條件的偽文件對真實數(shù)據(jù)庫進行填充，文件與關(guān)鍵字的對應(yīng)關(guān)系用位圖索引表示。接著根據(jù)更新操作對填充數(shù)據(jù)庫進行動態(tài)修改，如果更新操作為添加，若更新后該關(guān)鍵字對應(yīng)的文件數(shù)最多，則根據(jù)此數(shù)量對其他關(guān)鍵字進行填充；否則減少對該關(guān)鍵字的填充，直到該關(guān)鍵字的頻率減少到和更新操作前一樣。如果更新操作為刪除，則增加對該關(guān)鍵字的填充，直到該關(guān)鍵字的頻率增加到和更新操作前一樣。該填充方法適用于動態(tài)可搜索加密方案，可以防止數(shù)據(jù)泄露，比如抵抗基于關(guān)鍵字頻率推斷的攻擊，提高方案的安全性。

技術(shù)領(lǐng)域

本發(fā)明涉及可搜索加密技術(shù)領(lǐng)域，具體地說是一種基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法。

背景技術(shù)

隨著網(wǎng)絡(luò)的快速發(fā)展以及大數(shù)據(jù)時代的到來，本地存儲與計算資源不能滿足人們的需求，云存儲與計算技術(shù)迅速發(fā)展起來。為了保證數(shù)據(jù)的安全性，通常會把數(shù)據(jù)加密后上傳到云服務(wù)器。然而，在密文數(shù)據(jù)上執(zhí)行搜索是非常困難的。因此可搜索加密(SE,Searchable Encryption)技術(shù)被提出。早期的SE方案都是靜態(tài)的，不支持?jǐn)?shù)據(jù)庫動態(tài)更新，比如對上傳的文件添加或刪除，這限制了SE方案的應(yīng)用。為了解決這一問題，動態(tài)對稱可搜索加密(DSSE,Dynamic Searchable Symmetric Encryption)技術(shù)被提出。

然而DSSE方案存在數(shù)據(jù)泄露的問題，比如基于關(guān)鍵字頻率推斷的攻擊(如計數(shù)攻擊)可以很容易地從訪問模式中識別查詢關(guān)鍵字，即查詢結(jié)果，數(shù)據(jù)庫填充技術(shù)是解決上述問題簡單且有效的措施，并且適合真實的大數(shù)據(jù)集。近年來，填充算法的研究重點主要在如何設(shè)計高效的填充方案，然而現(xiàn)有的填充算法都不適用于動態(tài)數(shù)據(jù)庫。如何設(shè)計一個高效且適用于DSSE方案的填充方案成為一種迫切的需求。

發(fā)明內(nèi)容

本發(fā)明的目的就是提供一種基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法，本方法適用于DSSE方案，可以根據(jù)動態(tài)更新操作更新填充數(shù)據(jù)庫，提升動態(tài)更新的效率，并且可以有效防止數(shù)據(jù)泄露，提升DSSE方案的安全性。

本發(fā)明是這樣實現(xiàn)的：一種基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法，包括以下步驟：

a、生成填充數(shù)據(jù)庫；

根據(jù)原始數(shù)據(jù)庫每個關(guān)鍵字的填充計數(shù)，對原始數(shù)據(jù)庫進行聚類，利用現(xiàn)有的最優(yōu)分區(qū)算法來創(chuàng)建具有最優(yōu)填充比的關(guān)鍵字集群，集群中每個關(guān)鍵字按照頻率最大的關(guān)鍵字填充至相同的數(shù)量。根據(jù)每個關(guān)鍵字需要填充偽文件的數(shù)量隨機生成偽文件進行填充，直到所有關(guān)鍵字填充到最大填充計數(shù)為止，由填充的偽文件生成填充數(shù)據(jù)庫，并生成相應(yīng)索引。

b、根據(jù)更新操作動態(tài)調(diào)整填充數(shù)據(jù)庫；

更新操作要么為對關(guān)鍵字的添加操作，要么為對關(guān)鍵字的刪除操作；

若操作為添加，則首先需要判斷添加后的關(guān)鍵字對應(yīng)的文件數(shù)量是否最多(即關(guān)鍵字頻率是否最大)，若是則根據(jù)此關(guān)鍵字頻率對其他關(guān)鍵字進行填充；否則需要對填充數(shù)據(jù)庫中此關(guān)鍵字對應(yīng)的填充文件嘗試刪除，即減少對該關(guān)鍵字的填充。

若操作為刪除，則需要對填充數(shù)據(jù)庫中未填充此關(guān)鍵字的偽文件嘗試填充，即增加對該關(guān)鍵字的填充。

在嘗試性刪除或嘗試性填充過程中，均需要通過局部離群因子(LOF)來進行離群值檢測，即：對嘗試更改的偽文件進行離群值檢測，如果沒有被識別為離群值，則更改此偽文件并更新填充數(shù)據(jù)庫以及對應(yīng)索引；若被識別為離群值，則回滾到修改前的狀態(tài)，并選擇下一個偽文件進行嘗試更改，再檢測，依次循環(huán)，直至更改成功。

無論哪一操作，在更改成功后均需要判斷是否每個關(guān)鍵字的頻率均相同，即判斷每一關(guān)鍵字對應(yīng)的真實文件與填充的偽文件數(shù)量之和是否均相同，如果是，則更新操作完成，否則，循環(huán)執(zhí)行更改操作。

其中，生成索引的依據(jù)如下：