基于非定長編碼和滑動窗口的隱私保護記錄鏈接方法

葉曉東，趙迎迎，孫永奇*，趙思聰，劉真

（1.北京交通大學計算機與信息技術學院，北京 100044；2.交通大數據與人工智能教育部重點實驗室，北京 100044；3.北京航天晨信科技有限責任公司，北京 102308）

0 引言

跨不同數據庫的信息融合已成為銀行、醫療、國家安全等不同應用領域進行決策活動的重要手段［1］。從多個數據庫中識別和鏈接對應于同一實體對象的類似記錄被稱為記錄鏈接，其可促進應用領域的高效數據分析，從而提高領域決策的準確性。目前，越來越多的記錄鏈接操作發生在跨組織數據庫中用于識別來自不同組織數據庫的相似記錄，以針對同一實體對象進行信息補充［2-4］。例如，通過鏈接銀行和保險公司持有的數據庫可以幫助生成更為完整的用戶畫像，從而更好地為用戶提供個性化服務。然而，被鏈接的數據庫中往往存儲著用戶的敏感信息，且用戶不希望這些敏感信息在參與鏈接的不同組織間共享［5-6］。

隱私保護記錄鏈接（PPRL）［7］技術可以實現跨不同數據庫的記錄鏈接計算，并且不會在組織間共享包含任何敏感信息的數據庫實體信息。在PPRL 計算中，會對數據庫中各實體信息進行編碼或加密來生成各實體信息對應的隱私保護記錄，以用于跨數據庫的記錄匹配計算。另外，PPRL 要求參與匹配計算的任何組織或其他組織都不會破壞被鏈接數據庫中代表實體信息的記錄。PPRL 中普遍利用布隆過濾器（BF）［8］進行編碼計算。BF 編碼具有實現簡單且能有效計算記錄間相似性的優點，被廣泛應用于許多實際PPRL 的計算過程［9-10］。然而，已有研究表明BF 編碼極易受到隱私攻擊［11-12］。

本文提出一種基于非定長編碼和滑動窗口的隱私保護記錄鏈接技術，簡稱為VSW 方法，基于VSW實現跨數據庫的隱私保護記錄鏈接計算。本文的主要工作如下：

1）提出一種非定長編碼的隱私保護記錄生成方法，通過對實體信息進行非定長編碼來隱藏位數組的頻率信息，從而避免頻率攻擊。

2）提出一種基于滑動窗口的記錄鏈接方法，利用快速過濾策略僅通過簡單計算即可過濾大部分不匹配的記錄，從而使記錄鏈接計算更加高效。

3）提出一種基于雙向滑動窗口的精確匹配計算方法，以實現不同記錄的精確匹配并進一步提高記錄鏈接計算的效率。

4）在公開數據集上進行實驗，以驗證VSW 方法的準確性和安全性。

1 相關研究

PPRL 技術的提出使跨不同數據庫的實體信息整合被廣泛應用于諸多領域，有助于各領域為用戶提供更加個性化的服務。目前，PPRL 主要包括基于典型BF 編碼、基于加固BF 編碼的PPRL 技術以及其他的PPRL 技術。

1.1 基于典型BF 編碼的PPRL 技術

目前，典型的BF 編碼技術被廣泛應用于PPRL計算中，用于生成被比較數據庫的隱私保護記錄。BF 是一種由一個長度為mbit 的位數組與k個獨立的哈希函數構成的能節省空間的數據結構。BF 位數組的初始長度為0，當插入元素時，該元素經哈希函數執行k次哈希計算產生k個哈希值，并以哈希值作為位數組中的下標將所有對應的比特值由0 置為1。在基于BF 的PPRL 中，通常從實體信息中提取qgram 再將其散列成BF 編碼。由于其編碼效率和屬性值的近似匹配，BF 幾乎已成為PPRL 的編碼標準。這里q-gram 是q位相鄰字符對，例如“jack”，其q=2的q-gram 列表為［‘j’，‘ja’，‘ac’，‘ck’，‘k’］。

然而，由于BF 編碼是由基于實體信息的q-gram映射到比特位置而得到的，攻擊方可以學習關于如何執行編碼的信息，使編碼值被重新識別。此外，在編碼數據庫中頻繁出現的敏感值可能導致BF 中的頻繁比特模式被識別，甚至可以使用模式挖掘技術找到單個頻繁q-gram。因此，BF 編碼方式容易遭受攻擊，存在數據庫實體信息被攻擊泄露的風險。

1.2 基于加固BF 編碼的PPRL 技術

為了提高安全性，近年來研究人員已提出許多加固的BF 編碼技術應用于PPRL 中。如文獻［13］提出一種基于向量折疊和逐位XOR 運算相結合的BF加固技術。首先將BF 編碼均分成b1和b2兩半，然后b1和b2對每個位應用逐位XOR 運算并組合成新的加固BF 編碼。這種對應位置的逐位XOR 運算可確保2 個原始位置的輸入值不可能被恢復，有效提高了安全性。加鹽（Salting）是另一種加固BF 編碼技術，由文獻［14］提出，在每個q-gram 被散列之前為其添加一個額外的（字符串）值來避免對BF 的隱私攻擊，這些字符串通?；谝恍┎灰赘淖兊膶傩灾荡_定，如出生年、出生地等，使得大多數頻繁出現的q-gram 與鹽值連接在一起，會變得不那么頻繁。

另外，有研究人員利用Markov 鏈為頻繁出現的q-gram 隨機添加額外的q-gram，有效避免了頻率攻擊［15］。該方法對于q-gram 中每個獨特的q隨機選擇c個其他q-gram，基于它們在q之后出現的概率與q一起編碼，其中，c是在加固技術中使用的鏈長參數。但是，當c值較大時會降低鏈接質量。

Rule 90［16］是一種一維細胞自動機，規則比較簡單，有一個一維單元陣列（開或關），每個單元的下一個狀態是該單元的2 個相鄰單元的異或?；谒牟豢赡嫘?，文獻［15］提出一種使用Rule 90 作為BF 編碼的強化技術。

文獻［17］使用滑動窗口和重采樣的方法來選擇原始BF 中的某些比特，并對這些選擇的比特進行逐位XOR 運算生成新比特值，從而提高安全性。

1.3 其他PPRL 技術

除BF 編碼外，已有許多新型編碼方式被成功應用于PPRL 中。文獻［18］提出一種基于最小哈希的制表方法（TMH），在小規模數據集上的實驗結果表明，TMH 方法在提高匹配精確率的同時能有效保護數據隱私。但與BF 編碼相比，這種制表哈希編碼方法的計算復雜度較高，因此不適用于大數據規模的PPRL 計算。文獻［19］提出一種新的編碼方法，使用兩步散列過程將敏感值編碼為整數集。這種方法實現了更高質量的相似性計算，且能有效抵御頻率攻擊，但是無法抵御相似性圖攻擊。

此外，文獻［20］提出了兩種新的隱私保護字符串匹配方法：第一種方法通過改變q-gram 的順序來提高編碼的私密性，q-gram 的順序移位隱藏了它們在字符串中的實際位置，這使得基于位置的頻率分析更加困難；另一種字符串匹配方法（SRA）將每個q-gram 編碼成固定長度的位數組，并在編碼q-gram列表的位數組的開頭和結尾位置分別添加隨機位數組，這種操作可以隱藏實際的子字符串位置和編碼字符串的長度，從而提高了對手識別已編碼到位陣列中的原始字符串值的難度。然而，SRA 方法的時間開銷較大，且固定長度的q-gram 編碼方法會帶來比特模式被識別的風險。另外，SRA 方法只能進行子字符串的匹配，不能用來計算2 個字符串的整體相似性，因此不能用于隱私保護記錄的鏈接計算。

針對BF 編碼對q-gram 位置不敏感以及容易受到頻率攻擊的問題，本文對SRA 方法進行改進，提出一種基于非定長編碼和滑動窗口的隱私保護記錄鏈接方法VSW。該方法通過對實體信息進行非定長編碼來隱藏位數組頻率信息，從而防御頻率攻擊。此外，在計算2 個字符串的整體相似性時，通過基于滑動窗口的精確匹配方法提高記錄鏈接效率。

2 問題定義

不同用戶持有的數據庫中都存儲了一定數量的實體信息，各實體信息都對應唯一對象，而位于不同數據庫的兩條實體信息可能是指向同一對象。各用戶希望在不向其他用戶或服務器泄露本地數據庫中任何實體信息的前提下實現本地數據庫與其他數據庫中實體信息的匹配。例如，銀行數據庫中各實體信息記錄著用戶的姓名、身份證號、銀行卡號、存款、交易記錄等，保險公司數據庫中各實體信息記錄著用戶的姓名、身份證號、投保類型等，銀行和保險公司就可以通過匹配它們數據庫中的實體信息得到用戶更完整的畫像。

上述應用都可以基于所提VSW 方法來安全、高效地實現記錄的精確鏈接。令A、B 為2 個不同的用戶，DA、DB為A、B 各自持有的數據庫，則VSW 方法基于A、B 的協商秘密和非定長編碼計算得到DA、DB對應的隱私保護記錄索引WA、WB，并對其中的記錄執行匹配計算，為各用戶返回一個匹配的記錄鏈接列表LA、LB。其中，相關定義如下：

定義1（隱私保護記錄索引）DA或DB中每條實體信息都唯一對應著索引中的一條記錄，其由記錄id 和一串定長且僅包含0 和1 的字符串構成。

圖1 相關定義示例Fig.1 Examples of relevant definitions

定義2（匹配記錄鏈接列表）對于匹配記錄鏈接列表LA、LB內同一位置的2 個元素ida、idb，它們在WA、WB內分別對應的記錄ra、rb的相似度大于閾值dice∈［0，1］。

當WA、WB內2 個記錄ra、rb的相似度大于dice 時，則認為它們對應的實體信息是匹配的。如圖1 所示，LA、LB為DA、DB的匹配記錄鏈接列表，則DA、DB中idi、idt標記的2 條實體信息匹配，且WA、WB內idi和idt標記的2 個記錄相似度值大于閾值dice。

在隱私保護記錄鏈接計算過程中，使用Dice 系數作為鏈接標準，其為一種計算不同集合相似度的度量函數，取值范圍為［0，1］。Dice 系數具體計算公式如下：

其中：|X∩Y| 是集合X和Y之間的交集；|X|和|Y|分別表示X和Y中元素的個數。

3 VSW 方法

本節將詳細描述利用VSW 方法執行隱私保護記錄鏈接的計算過程及算法實現。

3.1 VSW 方法概述

基于VSW 的隱私保護記錄鏈接方法包括2 個階段，即基于非定長編碼的隱私保護記錄生成和基于滑動窗口的記錄鏈接計算，分別簡稱為記錄生成階段和記錄鏈接階段。圖2 所示為VSW 方法的整體框架。

圖2 VSW 方法整體框架Fig.2 Overall framework of VSW method

2 個階段的詳細計算過程如下：

一個課堂的精彩在于看到這些去回應，重新讓這些斷裂的點連續起來，形成一種內在的節奏和旋律。這種節奏和旋律是一種和諧的聲音。如果沒有這些矛盾，也就沒有和諧的聲音，只是一些平淡、索然無味、形式上看似和諧的東西。但只有所有的矛盾和沖突背后的張力，才能凸顯出和諧的美，就像我們看到光是因為有黑暗一樣。

1）記錄生成階段

用戶A 和B 首先進行協商配置，包括協商公有秘密s、字符表E的內容、q-gram 生成方式、位數組的初始及最大長度lmin和lmax以及記錄長度l，然后各用戶執行如下步驟：

（1）基于協商的字符表E及q-gram 生成各自的q-gram 字符串庫QE。

（2）基于公有秘密s為QE中各q-gram 字符串生成定長位數組表TE。

（3）基于私有秘密進行定長編碼，構建隨機位數組表TR。

（4）對初始的位數組表TE進行非定長編碼，將其轉換為非定長位數組表。

（5）基于TE、TR為DA和DB中的對象構建隱私保護記錄索引WA和WB。

2）記錄鏈接階段

服務器得到用戶A、B 發送的隱私保護記錄索引WA、WB后，執行如下步驟進行記錄鏈接計算：

（1）首先取出WA中的一條記錄ra，然后與WB中各記錄rb進行快速過濾計算，若rb一定不與ra匹配，則將rb快速過濾掉。

（2）若ra與rb可能匹配，則 繼續針對ra與rb執行精確匹配計算，計算兩者相似度并判斷是否大于閾值，若大于閾值，則分別將兩者id 存入匹配記錄鏈接列表LA、LB中。

3.2 基于非定長編碼的隱私保護記錄生成

隱私保護記錄生成的目的是將用戶持有的各實體信息加密編碼為一段具有固定長度的位數組。首先構建一個字符表E，E中包含實體信息中可能出現的所有字符。然后通過字符表E生成包含所有q-gram 字符串的表QE，并根據QE構建2 個位數組表TR和TE。其中：TR表內存儲著隨機位數組，任意用戶的TR表都不與其他所有位數組表相交，防止虛假匹配；TE存儲著QE內所有q-gram 字符串以及對應的編碼。由于使用定長編碼時存在被逆推出q-gram 列表長度的風險，因此本階段采用非定長編碼構建TE·，表內各位數組長度在［lmin，lmax］內變化。有研究表明，足夠大的lmin可以有效抵御頻率攻擊，表1 給出了根據Stirling 公式計算的不同情況下的lmin最優值，其中|E|為字符表E中的元素個數［20］。

表1 不同情況下的lmin最優值 Table 1 The optimal values of lmin in different ituations

在記錄生成過程中，各實體信息的q-gram 列表通過TE表編碼成位數組（稱為有效位數組），并將TR中的隨機位數組填充到有效位數組的首、末端位置，使生成的隱私保護記錄長度相同。這種填充方法可隱藏有效位數組的位置，從而提高記錄的隱私保護程度。

在算法1 的輸入中：D為一個包含所有實體信息的索引，其各元素都為一條實體信息的q-gram 列表；s為所有用戶協商的公有秘密；sd為各用戶持有的私有秘密。初始化3 個數組TE、TR和W后，基于字符表E和設置的q-gram 長度q，利用函數BldQgramSet（）構建一個包含所有可能q-gram 信息的列表QE。在第5 行～第8 行，對于QE中的每個q-gram 字符串qE，利用函數BldBitArr（）構建長度為lmin的位數組bq，并將qE及其bq存入TE。在第9 行～第14 行，當TR長度不大于TE長度時，基于用戶的私有秘密sd構建長度為lmin的隨機位數組bt，并判斷bt是否存在于當前及其他所有用戶的TE和TR表中，若不存在，則將bt存入TR表。在第15行～第18 行，對TE中各qE及其bq，利用BldExtBitArr（）為qE生成額外隨機位數組（長度≤lmax-lmin）并將其補充至bq末尾位 置得 到，并 用更 新TE［qE］的 值。在 第19 行～第26 行，針對索引D中存儲的每條實體信息，即id→gramL，通過搜索TE表，為其生成有效位數組并存入temL 中。然后基于TR利用BldPPRBitArr（）將有效位數組（長度為len（temL））補充成長度為l的隱私保護記錄bf，并將其存入索引W中。最后輸出生成的隱私保護記錄索引W。

圖3 舉例說明了隱私保護記錄生成的過程。首先基于用戶約定的共有秘密，對QE中各字符串qE進行加密并生成長度為6 的位數組bq，構建初始定長的位數組表TE；然后對表TE進行非定長計算得到新的非定長位數組表TE，如圖3 左側所示。對于DA中的記錄“jack”，首先計算其q-gram 表［_j，ja，ac，ck，k_］；然后搜索非定長的TE表，將各實體信息編碼為長度不同的有效位數組“100010110001001001001100101 010110100011110100101”（有效長度為48）；接著將TR中的隨機位數組“101101”和“101010”分別填充在有效位數組的首、末端位置，從而得到一個長度為60的隱私保護記錄；最后將記錄id、隱私保護記錄和有效位長度存入隱私保護記錄索引WA中。

圖3 隱私保護記錄生成示例Fig.3 Example of privacy protection record generation

3.3 基于滑動窗口的記錄鏈接計算

鏈接計算的目標是根據為用戶生成的隱私保護記錄索引WA和WB，進行兩索引內記錄的鏈接計算，分別為用戶生成一個匹配的記錄鏈接列表LA、LB。為提高記錄鏈接計算的效率，在2 條記錄比較過程中，以其中一條為基準，設計快速過濾計算，過濾掉一定不匹配的記錄，并對未被過濾的記錄執行精確匹配計算，進一步判斷記錄是否匹配。在計算過程中同時采用基于滑動窗口的計算策略，根據基準記錄設置定長窗口，并使其按特定步長進行滑動比較，進一步加速匹配計算過程。

用戶A 和B 的隱私保護記錄鏈接計算過程如算法2 所示。輸入為用戶的隱私保護記錄索引WA和WB以及給定的相似度系數dice，輸出為各用戶的記錄鏈接列表LA和LB。對WA中的每一條記錄ra，遍歷WB中每條記錄rb并判斷2 條記錄是否匹配。首先，進行快速過濾計算（第5 行），快速判斷rb是否與ra一定不匹配，若一定不匹配，則RecFiltComp（）返回值為false，否則返回true；然后，如果返回值為true，則繼續精確判斷計算（第7 行），即執行函數DetailComp（），并 返回ra和rb的相似度系 數值v；最后，若v≥dice，則2 條記錄鏈接成功并將各自的編號ida和idb分別存入列表LA和LB中。

3.3.1 快速過濾計算

快速過濾計算用于快速判斷WB中某一記錄rb是否一定不與WA中記錄ra匹配。由于實體信息對應q-gram 列表的長度以及q-gram 對應位數組長度均存在最小值，因此可以計算出隱私保護記錄中有效位數組的最短長度。當最短有效位超過50%時，記錄的中間部分總會有一個子集，其中的位數組均是有效位，在這部分進行初步篩查可以有效避免隨機位數組帶來的干擾。對于ra和rb這2 個需要鏈接的記錄，在ra的絕對有效位數組上進行滑動窗口查找，對與rb不匹配的部分進行計數。當ra和rb的不匹配位數大于最大不匹配位數時說明不匹配（如圖4 所示），其中最大不匹配位數可以通過dice 系數計算得出。通過這種方法，大部分不匹配的記錄會被快速淘汰。

圖4 快速過濾計算示例Fig.4 Example of computation of rapid filtering

算法3 給出了快速過濾函數RecFiltComp（）的詳細計算過程。第1 行根據2 個記錄各自的有效位長度lena和lenb及指定的相似度系數dice 計算ra和rb的最大不匹配位數count；第2 行～第3 行獲取ra的絕對有效位數組workbits 并初始化一個長度為lw的滑動窗口；第5 行～第14 行從字符串workbits 的第0 位開始以lw為步長滑動窗口，curbits 為位于當前窗口位置的字符串，若curbits 位于rb內，則更新rb，即將從0 位到當前curbits 的所有字符從rb中刪除，否則，累加不匹配字符串數并判斷其是否大于count，若大于，則2 個記錄一定不匹配，返回false。當窗口滑動到workbits 的最末尾位置時num ≤ count，則返回true并結束計算。

3.3.2 精確匹配計算

對于通過了快速過濾的記錄rb，繼續以記錄ra為基準進行精確匹配以計算2 個記錄的相似度。精確匹配基于雙向滑動窗口策略執行，當定位到一段同時位于ra、rb內的有效字符串時，以有效字符串位置為參考構建沿左、右方向且長度不同的滑動窗口以確定最長的匹配字符串。如圖5（a）所示，首先設置長度為lw的滑動窗口，從基準記錄首位開始以步長step 向右滑動，以定位窗口字符串curbita在rb的位置；然后分別以匹配字符串curbita的頭、尾為起點，對ra、rb執行雙向不等長窗口的滑動搜索，并動態更新匹配字符串長度直至滿足結束條件，如圖5（b）所示。精確匹配是從基準記錄的首位開始向右滑動窗口來定位有效字符串，滑動步長step≤窗口長度lw。為了能保證精確匹配同時盡可能地提高計算效率，對于ra、rb內有效字符串的左側字符串，分別以長度1 和步長1 向左滑動窗口搜索，對于右側字符串，則以步長為lw的滑動窗口向右快速搜索。

圖5 精確匹配計算示例Fig.5 Example of exact matching calculation

算法4 給出了針對記錄ra和rb的精確匹配計算過程。首先初始化滑動窗口及滑動步長lw和step，從ra第0 位開始移動并獲取位于窗口內的字符串curbita，若curbita不位于rb內，則以步長step 更新位置值i，否 則獲取curbita在rb內的起始位置ps；然后第10 行分別以i和ps為參考位置進行ra和rb內的左移計算（步長為1）得到左匹配位數lecount，第11 行分別以i和ps為參考位置進行ra和rb內的右移計算（步長為lw）得到右 匹配位 數ricount，loca和locb分別為ra和rb內滑動窗口的新起始位置；最后更新rb及匹配的位數組總數sum，同時計算ra和rb的相似度值v。

4 位置敏感性與安全性分析

4.1 位置敏感性

位置敏感性是指算法對于僅存在元素順序差異的q-gram 列表是否會產生不同的編碼。BF、TMH 等方法采用哈希映射的方式進行編碼，編碼結果僅與q-gram 和哈希函數有關，而與q-gram 順序無關，因此無法區分具有不同元素順序的q-gram 列表。例如，對于字符串“330310”和“310330”，由于2 個字符串生成的q-gram 列表元素相同，BF 等方法將生成完全相同的隱私保護記錄，無法區分2 個字符串。而VSW 方法是按照順序進行編碼，保留了位置信息，在上述情況下，只會識別到“310”，這種位置敏感性使其能獲得更高的匹配精確度。

4.2 安全性

本文假定服務器和用戶之間是誠實且好奇的（honest-but-curious）［21-22］。誠實是 指用戶 不會偽 造數據，服務器也不會對參與者上傳的數據進行攻擊、破譯或逆向工程等惡意操作。好奇是指服務器方對用戶的原始數據有一定程度的好奇，并且可能會繞過一些安全措施直接訪問用戶的原始數據。因此，本文約定用戶不能將字典和秘密提供給服務器，用戶間不能直接或通過服務器訪問對方的隱私保護位數組。這時服務器雖然持有所有用戶的隱私保護記錄索引和索引中每個位數組的有效位數，但是不知道有效部分起始位置，且沒有用戶協商的秘密，所以無法破解位數組信息。由于使用非定長編碼，服務器即使知道記錄的有效位長度也無法推測出對應q-gram 列表的長度。用戶之間雖然在協商過程中擁有相同的非定長位數組表TE，但是無法獲得對方基于私有秘密生成的隨機位數組表TR，從而保護了用戶的數據隱私。

目前對于BF 的大多數攻擊是通過分析BF 集合中位模式的頻率和相應q-gram 頻率，從而獲得qgram 與某個數值模式頻率之間的相關性，BF 的非均勻Hamming 權重分布容易遭受頻率攻擊［23］。而本文提出的基于非定長編碼的VSW 方法在隱私保護記錄生成的過程中使用隨機函數，確保了記錄服從均勻分布，非定長也使得相較于SRA 方法更難被攻擊者分析頻率和有效位長度，且通過在有效位數組的前、后端添加隨機位數組隱藏了有效位置，從而有效防御了頻率攻擊。

基于相似圖的PPRL 攻擊［24］是將純文本值生成的圖與編碼值生成的圖進行比較，目的是基于節點特征確定純文本值和編碼值之間的對應關系。相似圖攻擊的成功與否取決于2 個相似圖的可比性，因此，常規的計算編碼之間精確相似性的PPRL 方法都可能受到相似性攻擊。VSW 方法也可計算相似性，但是由于在有效位數組前后添加了隨機位數組，使得純文本值和編碼值之間沒有了對應關系，因此也可以防御相似圖攻擊。

另一種攻擊方式是通過對編碼進行聚類提取出特定特征［25］，例如常見的q-gram 組合。為了分析這種攻擊的有效性，需要考慮隱私保護記錄的位分布（bit distribution）。有研究表明，如果編碼具有接近多維正態分布的分布，則任意聚類方法都不會產生準確且分離良好的聚類，從而使其抗攻擊能力更強［26］。在第5.2 節，將通過比較隱私保護記錄與正態分布的接近程度來評估VSW 方法抵御聚類攻擊的安全性能。

5 實驗結果與分析

本節針對VSW 方法進行實驗測試和驗證，并對實驗結果進行詳細分析。本節實驗包括兩部分：第一部分對VSW 方法進行詳細測試，確定使得VSW性能達到最佳的參數；第二部分基于調優參數對比測試VSW 方法和其他3 種方法的性能。

5.1 實驗數據及評價指標

5.1.1 實驗數據集及實驗環境

本節實驗采用的數據集為北卡羅來納州選民登記名單（NCVR），該數據集中的記錄是真實的個人信息，可從 ftp：//alt.ncsbe.gov/ data/上下載。

實驗的硬件環境為：Intel Core i7-6700 處理器，主 頻3.40 GHz，4 核，16 GB 內 存。軟件環境為：Windows 10 操作系統（64 位），PyCharm 開發平臺，所有算法均采用 Python 語言實現。

5.1.2 評價標準

實驗通過召回率（RRecall）、準確率（PPrecision）和運行時間評價所有算法的運行結果。準確率為在匹配的記錄中正確匹配記錄數量的比例，如式（2）所示；召回率為正確匹配記錄占全部應匹配記錄數量的比例，如式（3）所示。

其中：TTP是正確匹配的記錄數量；FFP是錯誤匹配的記錄數量；FFN是應該匹配但未能匹配的記錄數量（即正類預測為負類的數量）。

5.1.3 參數優化

對有效位數組最短長度、滑動窗口大小、滑動窗口步長分別進行測試，數據集大小為 5×103條記錄。為了測試鏈接質量，模仿現實生活中可能出現的錄入問題對數據集中的實體信息進行隨機修改，具體修改包括：

1）以1/20 的概率轉置2 個相鄰字符。

2）以1/60 的概率刪除字符。

3）以1/60 的概率將一個字符加倍。

4）以1/60 的概率用鍵盤上的相鄰字符替換某字符。

表2 展示了有效位數組的最短長度變化時VSW方法的時間消耗及對快速過濾策略錯誤率的影響，其中錯誤率是指一條不匹配的記錄未被成功過濾掉的概率。由表2 可見，當有效位數組的最短長度增大時，快速過濾計算的錯誤率逐漸降低。但當有效位數組的最短長度越大時，每條記錄有效位長度的波動范圍會越小，這會影響q-gram 列表長度的取值區間大小，進而降低記錄鏈接的安全性。因此，在第5.2 節的對比實驗中將有效位數組的最短長度設定為整個記錄長度的60%。

表2 有效位數組最短長度對計算效率和錯誤率的影響 Table 2 Effect of minimum length of effective bit array on computational efficiency and error rate

表3 中展示了精確匹配計算中，滑動窗口長度變化時對精確匹配計算的時間消耗、召回率以及準確率的影響，其中設置步長與滑動窗口長度相同。由表3 可見，當滑動窗口長度變小時，準確率不變，均為100%，召回率在逐漸增大，但時間消耗也在變大。為平衡實時性和召回率，在第5.2 節的對比實驗中將滑動窗口長度設定為12 bit。

表3 精確匹配中滑動窗口長度變化對算法的影響 Table 3 Effect of sliding window length changes on algorithms in accurate matching

表4 中展示了精確匹配計算中，滑動窗口滑動步長變化時對精確匹配計算的時間消耗、召回率以及準確率的影響，其中設置滑動窗口長度為12 bit。由表4 可見，當滑動步長增大時，準確率仍保持不變，均為100%，召回率在降低，但時間消耗逐漸降低。為平衡實時性和召回率，在第5.2 節的對比實驗中將滑動窗口步長設定為8 bit。

表4 精確匹配中滑動窗口步長變化對算法的影響 Table 4 Effect of sliding window step size changes on algorithms in accurate matching

5.2 VSW 方法與其他方法的對比實驗

本節將從編碼和匹配時間、匹配精確度以及抗攻擊性等方面，對VSW 方法與其他3 種典型方法（BF、TMH、SRA）進行對比實驗。在對比方法中：第1 種是典型的BF 編碼方 法［8］，參數設置為l=1 024 bit，k=30，q=2；第2 種方法是文獻［18］提出的TMH 編碼方法，實驗中使用8 個制表鍵，每個鍵長度為64 bit，生成記錄長度為l=1 024 bit；第3 種方法SRA 本身不具備記錄鏈接功能，本文通過累加其計算出的匹配位數進行相似度計算。VSW 方法中記錄長度l=1 024 bit，窗口長度為12 bit，滑動步長為8 bit，有效位數組長度占比最小為60%。采用非定長編碼生成用戶記錄時，根據用戶間協商的公有秘密構建非定長位數組表TE，表內各位數組長度在［16，20］內變化，如果變化范圍過大，會導致隱私保護記錄匹配精度降低。

1）編碼和匹配時間

圖6 展示了4 種方法在數據集NCVR 上編碼計算的運行時間結果，圖中橫軸為數據集大小，分別包含103條、104條和105條記錄，縱軸為編碼計算的時間消耗，用對數表示。從中可以看出：VSW 方法與SRA 編碼方法相近，只需要查找TR和TE表即可快速生成記錄，在3 種規模數據下的編碼計算運行時間相似，都達到了最佳；BF 和TMH 均需要進行多次函數映射，運行時間較長。

圖6 數據集規模變化時4 種編碼方法的運行時間Fig.6 The runtime of four encoding methods when the dataset size changes

圖7 展示了單次匹配計算中4 種方法的時間消耗情況，圖中縱軸為對數表示的平均查詢時間。從中可以看出，在單次匹配計算中，BF 和TMH 由于只需要按位比較，因此時間消耗最少，SRA 計算的時間消耗最大，性能最差，而VSW 由于采用了滑動窗口的快速過濾和精確匹配算法，相較于SRA 大幅提升了匹配速度，但與BF 和TMH 相比仍然偏慢。

圖7 4 種方法單次匹配的平均查詢時間Fig.7 Average query time for single matching of four methods

2）匹配精確度

圖8 展示了4 種方法相似度計算過程中編碼相似度與q-gram 相似度平均差值的變化情況。其中，TMH 使用Jaccard 相似度，其他方法使用Dice 相似度。VSW 方法為了能夠計算低相似度情況，只使用精確匹配。從圖8 可以看出：VSW 方法相較于BF 和TMH 方法有更精確的相似度，一方面是因為哈希碰撞將不同的q-gram 散列到了相同的位置，而VSW 方法是按順序編碼，避免了哈希沖突；另一方面，BF 和TMH 不具備位置敏感性，對于僅存在元素順序差異的q-gram 列表會產生相同的編碼，而VSW 具有位置敏感性，可以達到更高的相似度計算精度。由于SRA 采用定長編碼與順序編碼相結合的方式，其匹配精確度最高。VSW 方法的匹配精確度與SRA 相比略低，主要原因是VSW 使用了非定長編碼，通過犧牲一定的匹配精度來提高隱私性。

圖8 4 種方法相似度計算平均差值變化情況Fig.8 The variation of average difference in similarity calculation of four methods

3）抗攻擊性

為定量分析VSW 方法的抗聚類攻擊能力，采用隱私保護記錄與正態分布的接近程度作為評價標準［26］。將每條隱私保護記錄分割成64 條16 bit 的二進制串，對其進行歸一化，再通過Shapiro-Wilk 檢驗方法判斷其與正態分布N（0，1）之間的相似性，當結果值越接近1 時，編碼的分布就越類似于正態分布。表5 展示了4 種方法的抗聚類攻擊能力實驗結果，可以看出VSW 方法具有更高的安全性。主要原因是VSW 在非定長編碼過程中使用隨機函數，保證了位數組每一位0 和1 的概率相同，從而使得在本實驗中的編碼分布與正態分布相似，提高了防御聚類攻擊的能力。

表5 4 種方法的抗聚類攻擊能力對比 Table 5 Comparison of the anti cluster attack capability of four methods

6 結束語

本文提出一種基于非定長編碼和滑動窗口的隱私保護記錄鏈接方法VSW，以實現跨不同數據庫實體信息的隱私保護記錄鏈接計算。首先，利用非定長編碼將實體信息加密為長度相同的位數組，為各用戶構建隱私保護記錄索引，該編碼方式具有位置敏感性，可提高記錄鏈接的匹配精度；然后，基于滑動窗口對生成的隱私保護記錄索引進行記錄鏈接計算，先采用快速過濾策略高效過濾掉一定不匹配的大部分記錄，再對過濾得到的記錄進行精確匹配計算得到記錄的相似度值，其中均采用滑動窗口策略進行加速。在公開數據集上的實驗結果表明，VSW方法編碼效率較高且擴展性較好。在安全性方面，由于VSW 方法采用了非定長編碼方式，可以有效抵御頻率攻擊、圖攻擊和聚類攻擊。在隱私保護性能方面，VSW 方法也達到了較優的效果。但是，相較于BF 方法，VSW 的計算效率較差，下一步將針對該問題對VSW 的計算性能進行改進。