基于改進m-invariance算法的動態數據發布機制?

歐家祥 張俊瑋 曹 湘 丁 超

（1.貴州電網有限公司電力科學研究院 貴陽 550002）（2.上海電力學院計算機科學與技術學院 上海 200090）

1 引言

隨著全球信息化時代的快速發展，社會生活中的信息量呈現爆炸式的增長，每天都有大量的信息在社會上傳播。這些信息通常都含有一些個人不希望被公開的敏感數據，而針對這些敏感數據的攻擊則時有發生，如何保護用戶的信息安全已經成為信息時代下的一個熱點話題，這其中的一個關鍵點就是如何在保證數據可用性減少信息損失和降低用戶信息泄露風險之間找到平衡。表格是一種常見的信息載體，許多數據都是以視圖的形式發布，針對視圖信息的隱私保護研究已經取得了豐碩的成果，形成了多種多樣的匿名機制，其中K-匿名模型［1～3］是針對靜態數據發布的一種經典模型，而m-invariance模型［4］是針對動態數據發布的一種經典模型，但m-invariance模型存在一些缺陷，例如對新增數據保護不足，通信開銷偏大等，針對這些缺陷，我們在m-invariance模型的基礎上提出了改進措施。

2 K-匿名模型

K-匿名技術最早由Samarati P和Sweeney L提出，其基本思想是使同一等價類中的各個元組彼此之間無法區分，從而達到隱私保護的目的。如果一個數據表中每條記錄的準標識符屬性都至少出現K次，那么則稱該數據表滿足k-匿名。由于對數據表采取了泛化處理［5～6］，攻擊者只有K 分之一的概率判斷出某條記錄屬于哪個用戶，由此也就保護了用戶的隱私安全。如下所示，表1是一份原始數據表，表2是一個滿足2-匿名的數據表。

表1 原始數據表

表2 匿名處理后發布的數據表

為了保護用戶的隱私，通常在數據發布時會將用戶的標識符屬性（姓名）去掉，這樣就算攻擊者知道用戶的背景知識（年齡，崗位）也只有1/2的概率得到用戶的敏感信息（薪水）。K-匿名模型建立在MDAV算法［7］的基礎上，主要采用了泛化隱匿和微聚集技術，將某條記錄隱藏在一個包含了K條記錄的等價類中，在這個等價類中所有記錄的準標識符屬性經過泛化處理之后都相同，這樣就有效地降低了用戶敏感信息被攻擊者獲取的風險。

K-匿名技術適用于數據靜態發布場景下，而在實際應用過程中，數據經常會發生變更（增加，刪除，修改），在這樣的情況下，如果直接對發生變更的數據表進行K-匿名操作，則攻擊者可以通過比對前后兩次匿名化數據表的差異來找出用戶的敏感信息。比如下面這種情況，公司一名部門主管離職了，又引進了一名新的部門主管，那么原始數據表和匿名處理之后的數據表如表3和表4所示。

表3 更新后的原始數據表

表4 匿名處理之后的數據表

由表3、4可以清楚地知道，有一名部門主管的薪水發生了變化，那么攻擊者就很容易知道剛加入公司的這名主管的薪水是11000元，同樣也可以推斷出剛剛離職的那名主管的薪水是12000元，由于只有蔡坤的薪水未發生變動，也就可以輕易地推斷出蔡坤的薪水是10000元。由此可見，在動態數據發布場景下，直接利用K-匿名算法重新匿名數據表，不僅要對表格進行重新計算，過程繁瑣，而且還有泄露用戶隱私的風險?；谶@種情況，人們開始致力于研究適用于動態數據發布場景下［8～10］的改進K-匿名算法。

3 m-invariance算法

針對K-匿名算法不適用于動態數據發布的情況，Xiao和Tao提出了m-invariance算法，要求每個QI（準標識符）組中的敏感屬性至少有m種不同的取值，而且需保證每條記錄在其生命周期內，其所在的QI組包含相同的敏感屬性值。要滿足以上要求，當表格數據需要更新時（新增，刪除，修改），為了使某條記錄所在的等價類中的敏感屬性的集合保持不變，如果新增加的記錄正好可以替代被刪除記錄，那么則可以直接將該新增記錄添加到被刪除記錄所在的等價類中，如果不滿足以上條件，則需要在表格中添加偽造記錄C1和C2，以保證其滿足m-invariance算法的規則。表5就是在原有數據的基礎上增加一條記錄刪除一條記錄后采用m-in?variance算法得出的匿名化表格（正式發布時姓名一欄刪除，下同）。

表5 經過m-invariance算法處理后的表格

從表5可以看出，通過添加偽造數據C1和C2，蔡坤所在等價類中的敏感屬性值的集合未發生變化，通過將雷軍放入第四個等價類中，添加偽造記錄C2以滿足至少含有m個不同敏感屬性值的要求，這樣攻擊者便無法根據更新前后表格數據的差異來推測出蔡坤的薪水是多少。

3.1 m-invariance算法原理

定義1（表集合）對發布時間n（n≥1）來說，已發布的表的集合U（n）包含了在發布時間1…n之間對應的原始表中的所有的記錄。即：（j）。在連續發布情況中，發布T（*n）時需要保證U（n）中的每條記錄的敏感信息不被泄露。

定義2（簽名）定義QI*代表T（*J）的QI組（J∈[1，n]），QI*的簽名是QI*敏感屬性值的集合。

定義3（m-unique）一個泛化的表是m-unique的，如果表中每個QI組有不少于m條記錄，并且這些記錄的敏感屬性的取值都不同。

定義4（m-invariance規則）如果滿足以下條件，則一個發布序列T（*1）…T*(n)是m-invariance的：

1）T*(J )是 m-unique的，J∈［1，n］。

2）對于任意的個體記錄r，其發布周期為［x，y］，那么QIx…QIy對應的簽名相同。QIx…QIy為Tx…Ty中r所在組的QI值。也就是說，m-invari?ance的基本原理是：在每個記錄的生命跨度中，該記錄所在QI組始終含有相同的敏感屬性集合，并且集合中的敏感值各不相同。

3.2 m-invariance規則分析

m-invariance算法的匿名化過程采用了偽造泛化方法。因為數據中包含了偽造數據，偽造泛化方法是傳統泛化方法的特殊情形。m-invariance規則規則與當前大部分隱私規則相比，有以下優點。

1）當前的隱私規則大多只考慮了數據的一次發布的問題，或者只考慮了新記錄添加之后的連續發布問題。m-invariance方法解決了表中舊記錄刪除與新記錄添加之后的連續發布問題，防止了連續發布中的隱私攻擊，保證攻擊者隱私攻擊成功的概率低于1/m。

2）m-invariance方法在發布表中加入了少量的偽造數據，保證每條記錄生命跨度中所在組的敏感屬性集合不變。表中的數據信息不會有太大的誤差，而且有效地保護了數據的安全，防止了隱私攻擊。

通過前面的實例分析，我們也可以看到一些m-invariance算法存在的缺陷［11～13］，在上述實例中，當數據表中的數據發生增減變化后，m-invariance算法可以很好地保護未發生變化的數據（蔡坤），但是對于新加入的數據（雷軍），如果加入的偽造數據敏感屬性值太容易被攻擊者識別（如上例中，如果攻擊者知道部門主管的工資都在10000元以上，那么添加進的敏感屬性值為9000元的偽造記錄就很容易被攻擊者所識破）那么添加的用以迷惑攻擊者的偽造記錄便失去了意義，如果我們添加的偽造記錄敏感屬性值與新加入記錄的敏感屬性值太過接近（比如就設在11000元附近），那么攻擊者就能很容易地得出雷軍的薪水在11000元附近，即這樣添加偽造記錄不能抵御同質性攻擊。在研究了m-in?variance算法和其他改進型算法［14～16］的基礎下，針對要添加的與新加入數據分配到同一個等價類中的偽造數據的敏感屬性值的設置采用一種新的取值的辦法，以避免以上兩種情況出現給攻擊者以可乘之機。

4 改進的m-invariance算法

針對以上出現的問題，對于新添加進來的數據，我們考慮可以以一個實際敏感屬性值為中心的區間來代替實際的敏感屬性值，同時為了降低信息損失，保證信息的可用性，區間跨度由數據發布者自行選取合適的值（這里我們給出一個參考值域，區間兩端點值偏離中心10%），例如在上面的例子中，我們可以以一個跨度為1000的值域［10500---11500］來代替新添加的敏感屬性值11000，對于此等價類中的偽造記錄我們也可以采取相同的處理方式，不過區間的中心需要向左或者向右作適當的偏移處理，在這里我們取區間中心向左偏移500，區間跨度1000不變，即新的敏感值區間為［1000---11000］，經過上述替換操作，新生成的匿名表如表6所示。

通過新生成的匿名表可以看出，經過區間泛化處理之后，對于新添加的記錄，犧牲了一部分數據的可用性，換來的是有效地保護了用戶敏感信息的安全性，而對于被刪除的記錄而言，如果有合適的新添加的記錄可以替代，則將此新添加記錄分配到被刪除記錄所在等價類中，如果沒有合適的新增記錄可以代替，那么則按原m-variance算法規則處理，通過添加偽造記錄以保證其所在等價類中的敏感值屬性集合保持不變。

表6 新生成的匿名化數據表

4.1 算法流程圖

對于新增記錄的處理方式如圖1所示，當有記錄添加進表格時，首先檢查該新增記錄是夠可以代替被刪除記錄，即將該記錄插入到被刪除記錄所在的等價類中是否滿足m-invariance規則，如果滿足，則直接將該新增記錄替換被刪除記錄插入到其所在等價類中，如果沒有記錄被刪除或者該新增記錄不能替代被刪除記錄，那么就將該記錄分配到一個新的等價類中，同時將其敏感屬性值進行區間泛化并添加合適的偽造記錄，最后輸出更新后的匿名表格。

圖1 新增記錄的情況

對于記錄被刪除的處理方式如圖2所示，當有記錄被刪除時，首先檢查是否有新增記錄可以替代該被刪除記錄，即用新增記錄替代被刪除記錄添加到其所在等價類中后滿足m-invariance規則，如果滿足，則直接用新增記錄替換該被刪除記錄。如果沒有新增加的記錄或者新增記錄不滿足上述條件，則添加對應的滿足m-invariance規則的偽造記錄替換該被刪除記錄，最后輸出更新后的匿名表格。

圖2 有記錄被刪除的情況

4.2 算法安全性分析

對于被刪除的記錄來說，如果沒有合適的新增記錄可以代替，可以選擇用敏感屬性值相同的偽造記錄來代替，插入到原來的等價類中，以保證該等價類中所有記錄的敏感屬性值的集合保持不變，這樣對于被刪除的記錄和該等價類中的其他記錄，攻擊者無法通過前后表格數據的更新來獲取其所想要的敏感信息，起到了有效的保護作用。而對于新增加的記錄而言，如果可以代替被刪除的記錄添加到其原來的等價類中，那么同樣也可以有效地避免被攻擊者竊取敏感信息，如果不能代替，則將敏感屬性值進行區間泛化劃分到新的等價類中，對該等價類中添加的偽造數據同樣進行區間泛化，這樣既可以降低只采用一個區間泛化（只對要添加的記錄進行泛化而不添加偽造記錄）區間跨度過大而導致的信息可用性損失，也可有效降低區間跨度過小而導致的敏感信息泄露的風險。表7比較了K-匿名模型、m-invariance模型和改進的m-invariance模型對于表格中的三種數據類型（新增數據、刪除數據、保留數據）的保護性能（×表示不能保護，√表示可以保護）。

表7 三種匿名模型對不能數據類型的保護性能比較

4.3 算法優越性分析

相較于經典的m-invariance算法，通過以上分析我們可以看出，該新算法具有以下優點：

1）通過對新增數據的敏感值屬性進行泛化處理，有效地保護了新增記錄敏感信息的安全性。

2）通過對偽造記錄進行泛化處理，有效降低了信息損失度，同時降低了新增記錄敏感信息暴露風險。

3）可以有效避免背景知識攻擊，攻擊者無法通過表格更新帶來的前后差異根據已掌握的個人信息精確地推測出某條記錄的敏感屬性值。

4）在通信開銷方面，由于如果新增記錄可以代替被刪除記錄則可以將其直接插入到被刪除記錄所在的等價類中，則可以有效地減少偽造記錄的加入，由此可以有效降低表格所占用的存儲空間，大大降低了通信開銷。

5 結語

鑒于經典的m-invariance算法在視圖數據動態發布場景下存在的一些缺陷，本文在m-invari?ance算法的基礎上基于泛化思想提出了一種改進型算法以使其更加適用于數據動態發布模式。通過對該算法運行結果的分析可以看出，該算法在數據動態發布場景下對用戶的敏感信息具有較強的保護能力，克服了原m-invariance算法的一些不足，對保護動態發布場景下的視圖化數據具有一定的參考價值。