基于非定長(zhǎng)編碼和滑動(dòng)窗口的隱私保護(hù)記錄鏈接方法

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

（1.北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044；2.交通大數(shù)據(jù)與人工智能教育部重點(diǎn)實(shí)驗(yàn)室，北京 100044；3.北京航天晨信科技有限責(zé)任公司，北京 102308）

0 引言

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

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

本文提出一種基于非定長(zhǎng)編碼和滑動(dòng)窗口的隱私保護(hù)記錄鏈接技術(shù)，簡(jiǎn)稱為VSW 方法，基于VSW實(shí)現(xiàn)跨數(shù)據(jù)庫的隱私保護(hù)記錄鏈接計(jì)算。本文的主要工作如下：

1）提出一種非定長(zhǎng)編碼的隱私保護(hù)記錄生成方法，通過對(duì)實(shí)體信息進(jìn)行非定長(zhǎng)編碼來隱藏位數(shù)組的頻率信息，從而避免頻率攻擊。

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

3）提出一種基于雙向滑動(dòng)窗口的精確匹配計(jì)算方法，以實(shí)現(xiàn)不同記錄的精確匹配并進(jìn)一步提高記錄鏈接計(jì)算的效率。

4）在公開數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以驗(yàn)證VSW 方法的準(zhǔn)確性和安全性。

1 相關(guān)研究

PPRL 技術(shù)的提出使跨不同數(shù)據(jù)庫的實(shí)體信息整合被廣泛應(yīng)用于諸多領(lǐng)域，有助于各領(lǐng)域?yàn)橛脩籼峁└觽€(gè)性化的服務(wù)。目前，PPRL 主要包括基于典型BF 編碼、基于加固BF 編碼的PPRL 技術(shù)以及其他的PPRL 技術(shù)。

1.1 基于典型BF 編碼的PPRL 技術(shù)

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

然而，由于BF 編碼是由基于實(shí)體信息的q-gram映射到比特位置而得到的，攻擊方可以學(xué)習(xí)關(guān)于如何執(zhí)行編碼的信息，使編碼值被重新識(shí)別。此外，在編碼數(shù)據(jù)庫中頻繁出現(xiàn)的敏感值可能導(dǎo)致BF 中的頻繁比特模式被識(shí)別，甚至可以使用模式挖掘技術(shù)找到單個(gè)頻繁q-gram。因此，BF 編碼方式容易遭受攻擊，存在數(shù)據(jù)庫實(shí)體信息被攻擊泄露的風(fēng)險(xiǎn)。

1.2 基于加固BF 編碼的PPRL 技術(shù)

為了提高安全性，近年來研究人員已提出許多加固的BF 編碼技術(shù)應(yīng)用于PPRL 中。如文獻(xiàn)［13］提出一種基于向量折疊和逐位XOR 運(yùn)算相結(jié)合的BF加固技術(shù)。首先將BF 編碼均分成b1和b2兩半，然后b1和b2對(duì)每個(gè)位應(yīng)用逐位XOR 運(yùn)算并組合成新的加固BF 編碼。這種對(duì)應(yīng)位置的逐位XOR 運(yùn)算可確保2 個(gè)原始位置的輸入值不可能被恢復(fù)，有效提高了安全性。加鹽（Salting）是另一種加固BF 編碼技術(shù)，由文獻(xiàn)［14］提出，在每個(gè)q-gram 被散列之前為其添加一個(gè)額外的（字符串）值來避免對(duì)BF 的隱私攻擊，這些字符串通常基于一些不易改變的屬性值確定，如出生年、出生地等，使得大多數(shù)頻繁出現(xiàn)的q-gram 與鹽值連接在一起，會(huì)變得不那么頻繁。

另外，有研究人員利用Markov 鏈為頻繁出現(xiàn)的q-gram 隨機(jī)添加額外的q-gram，有效避免了頻率攻擊［15］。該方法對(duì)于q-gram 中每個(gè)獨(dú)特的q隨機(jī)選擇c個(gè)其他q-gram，基于它們?cè)趒之后出現(xiàn)的概率與q一起編碼，其中，c是在加固技術(shù)中使用的鏈長(zhǎng)參數(shù)。但是，當(dāng)c值較大時(shí)會(huì)降低鏈接質(zhì)量。

Rule 90［16］是一種一維細(xì)胞自動(dòng)機(jī)，規(guī)則比較簡(jiǎn)單，有一個(gè)一維單元陣列（開或關(guān)），每個(gè)單元的下一個(gè)狀態(tài)是該單元的2 個(gè)相鄰單元的異或?；谒牟豢赡嫘?，文獻(xiàn)［15］提出一種使用Rule 90 作為BF 編碼的強(qiáng)化技術(shù)。

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

1.3 其他PPRL 技術(shù)

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

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

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

2 問題定義

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

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

定義1（隱私保護(hù)記錄索引）DA或DB中每條實(shí)體信息都唯一對(duì)應(yīng)著索引中的一條記錄，其由記錄id 和一串定長(zhǎng)且僅包含0 和1 的字符串構(gòu)成。

圖1 相關(guān)定義示例Fig.1 Examples of relevant definitions

定義2（匹配記錄鏈接列表）對(duì)于匹配記錄鏈接列表LA、LB內(nèi)同一位置的2 個(gè)元素ida、idb，它們?cè)赪A、WB內(nèi)分別對(duì)應(yīng)的記錄ra、rb的相似度大于閾值dice∈［0，1］。

當(dāng)WA、WB內(nèi)2 個(gè)記錄ra、rb的相似度大于dice 時(shí)，則認(rèn)為它們對(duì)應(yīng)的實(shí)體信息是匹配的。如圖1 所示，LA、LB為DA、DB的匹配記錄鏈接列表，則DA、DB中idi、idt標(biāo)記的2 條實(shí)體信息匹配，且WA、WB內(nèi)idi和idt標(biāo)記的2 個(gè)記錄相似度值大于閾值dice。

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

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

3 VSW 方法

本節(jié)將詳細(xì)描述利用VSW 方法執(zhí)行隱私保護(hù)記錄鏈接的計(jì)算過程及算法實(shí)現(xiàn)。

3.1 VSW 方法概述

基于VSW 的隱私保護(hù)記錄鏈接方法包括2 個(gè)階段，即基于非定長(zhǎng)編碼的隱私保護(hù)記錄生成和基于滑動(dòng)窗口的記錄鏈接計(jì)算，分別簡(jiǎn)稱為記錄生成階段和記錄鏈接階段。圖2 所示為VSW 方法的整體框架。

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

2 個(gè)階段的詳細(xì)計(jì)算過程如下：

一個(gè)課堂的精彩在于看到這些去回應(yīng)，重新讓這些斷裂的點(diǎn)連續(xù)起來，形成一種內(nèi)在的節(jié)奏和旋律。這種節(jié)奏和旋律是一種和諧的聲音。如果沒有這些矛盾，也就沒有和諧的聲音，只是一些平淡、索然無味、形式上看似和諧的東西。但只有所有的矛盾和沖突背后的張力，才能凸顯出和諧的美，就像我們看到光是因?yàn)橛泻诎狄粯印?/p>

1）記錄生成階段

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

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

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

（3）基于私有秘密進(jìn)行定長(zhǎng)編碼，構(gòu)建隨機(jī)位數(shù)組表TR。

（4）對(duì)初始的位數(shù)組表TE進(jìn)行非定長(zhǎng)編碼，將其轉(zhuǎn)換為非定長(zhǎng)位數(shù)組表。

（5）基于TE、TR為DA和DB中的對(duì)象構(gòu)建隱私保護(hù)記錄索引WA和WB。

2）記錄鏈接階段

服務(wù)器得到用戶A、B 發(fā)送的隱私保護(hù)記錄索引WA、WB后，執(zhí)行如下步驟進(jìn)行記錄鏈接計(jì)算：

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

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

3.2 基于非定長(zhǎng)編碼的隱私保護(hù)記錄生成

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

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

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

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

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

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

3.3 基于滑動(dòng)窗口的記錄鏈接計(jì)算

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

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

3.3.1 快速過濾計(jì)算

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

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

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

3.3.2 精確匹配計(jì)算

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

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

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

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

4.1 位置敏感性

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

4.2 安全性

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

本節(jié)針對(duì)VSW 方法進(jìn)行實(shí)驗(yàn)測(cè)試和驗(yàn)證，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。本節(jié)實(shí)驗(yàn)包括兩部分：第一部分對(duì)VSW 方法進(jìn)行詳細(xì)測(cè)試，確定使得VSW性能達(dá)到最佳的參數(shù)；第二部分基于調(diào)優(yōu)參數(shù)對(duì)比測(cè)試VSW 方法和其他3 種方法的性能。

5.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)指標(biāo)

5.1.1 實(shí)驗(yàn)數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

本節(jié)實(shí)驗(yàn)采用的數(shù)據(jù)集為北卡羅來納州選民登記名單（NCVR），該數(shù)據(jù)集中的記錄是真實(shí)的個(gè)人信息，可從 ftp：//alt.ncsbe.gov/ data/上下載。

實(shí)驗(yàn)的硬件環(huán)境為：Intel Core i7-6700 處理器，主 頻3.40 GHz，4 核，16 GB 內(nèi) 存。軟件環(huán)境為：Windows 10 操作系統(tǒng)（64 位），PyCharm 開發(fā)平臺(tái)，所有算法均采用 Python 語言實(shí)現(xiàn)。

5.1.2 評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)通過召回率（RRecall）、準(zhǔn)確率（PPrecision）和運(yùn)行時(shí)間評(píng)價(jià)所有算法的運(yùn)行結(jié)果。準(zhǔn)確率為在匹配的記錄中正確匹配記錄數(shù)量的比例，如式（2）所示；召回率為正確匹配記錄占全部應(yīng)匹配記錄數(shù)量的比例，如式（3）所示。

其中：TTP是正確匹配的記錄數(shù)量；FFP是錯(cuò)誤匹配的記錄數(shù)量；FFN是應(yīng)該匹配但未能匹配的記錄數(shù)量（即正類預(yù)測(cè)為負(fù)類的數(shù)量）。

5.1.3 參數(shù)優(yōu)化

對(duì)有效位數(shù)組最短長(zhǎng)度、滑動(dòng)窗口大小、滑動(dòng)窗口步長(zhǎng)分別進(jìn)行測(cè)試，數(shù)據(jù)集大小為 5×103條記錄。為了測(cè)試鏈接質(zhì)量，模仿現(xiàn)實(shí)生活中可能出現(xiàn)的錄入問題對(duì)數(shù)據(jù)集中的實(shí)體信息進(jìn)行隨機(jī)修改，具體修改包括：

1）以1/20 的概率轉(zhuǎn)置2 個(gè)相鄰字符。

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

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

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

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

表2 有效位數(shù)組最短長(zhǎng)度對(duì)計(jì)算效率和錯(cuò)誤率的影響 Table 2 Effect of minimum length of effective bit array on computational efficiency and error rate

表3 中展示了精確匹配計(jì)算中，滑動(dòng)窗口長(zhǎng)度變化時(shí)對(duì)精確匹配計(jì)算的時(shí)間消耗、召回率以及準(zhǔn)確率的影響，其中設(shè)置步長(zhǎng)與滑動(dòng)窗口長(zhǎng)度相同。由表3 可見，當(dāng)滑動(dòng)窗口長(zhǎng)度變小時(shí)，準(zhǔn)確率不變，均為100%，召回率在逐漸增大，但時(shí)間消耗也在變大。為平衡實(shí)時(shí)性和召回率，在第5.2 節(jié)的對(duì)比實(shí)驗(yàn)中將滑動(dòng)窗口長(zhǎng)度設(shè)定為12 bit。

表3 精確匹配中滑動(dòng)窗口長(zhǎng)度變化對(duì)算法的影響 Table 3 Effect of sliding window length changes on algorithms in accurate matching

表4 中展示了精確匹配計(jì)算中，滑動(dòng)窗口滑動(dòng)步長(zhǎng)變化時(shí)對(duì)精確匹配計(jì)算的時(shí)間消耗、召回率以及準(zhǔn)確率的影響，其中設(shè)置滑動(dòng)窗口長(zhǎng)度為12 bit。由表4 可見，當(dāng)滑動(dòng)步長(zhǎng)增大時(shí)，準(zhǔn)確率仍保持不變，均為100%，召回率在降低，但時(shí)間消耗逐漸降低。為平衡實(shí)時(shí)性和召回率，在第5.2 節(jié)的對(duì)比實(shí)驗(yàn)中將滑動(dòng)窗口步長(zhǎng)設(shè)定為8 bit。

表4 精確匹配中滑動(dòng)窗口步長(zhǎng)變化對(duì)算法的影響 Table 4 Effect of sliding window step size changes on algorithms in accurate matching

5.2 VSW 方法與其他方法的對(duì)比實(shí)驗(yàn)

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

1）編碼和匹配時(shí)間

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

圖6 數(shù)據(jù)集規(guī)模變化時(shí)4 種編碼方法的運(yùn)行時(shí)間Fig.6 The runtime of four encoding methods when the dataset size changes

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

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

2）匹配精確度

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

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

3）抗攻擊性

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

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

6 結(jié)束語

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