一種連續查詢事件中基于語義的軌跡k-匿名方法

何遠德 黃奎峰

1(西南民族大學語言實驗教學中心 四川 成都 610041)2(重慶三峽醫藥高等專科學校 重慶 404120)

0 引 言

軌跡匿名隱私保護技術是近年來網絡空間安全領域研究的熱點問題之一[1-3]，常用的軌跡匿名技術主要是基于泛化方法的k-匿名查詢技術[4]，該技術要求在發布數據中任一當前軌跡在以半徑為δ的圓柱范圍內，至少包含其他k-1條軌跡，生成一個泛化后的數據包，向客戶端提交虛假軌跡組，從而降低當前查詢軌跡的辨識率。然而當用戶在多個不同時刻k-匿名區域時，例如3個連續查詢事件，軌跡T1={P1、P2、P3、P4}，軌跡T2={P3、P4、P6、P7}，軌跡T3={P3、P8、P9、P10}，攻擊者比較容易推斷發出查詢事件請求的為P3用戶。

針對傳統的k-匿名軌跡隱私保護方法不能直接應用于連續查詢，學者們提出了不同的研究思路和觀點。文獻[5]將真實軌跡位置進行模糊處理，根據歷史數據生成虛假用戶，并提出了虛假軌跡的距離約束和相似性約束。文獻[6]通過匿名框的泛化方法將最初在框中的軌跡繼續保留在接下來多個連續查詢匿名框中，以避免攻擊者對數據信息的推斷和識別。文獻[7]針對關聯查詢攻擊和運動模式推斷攻擊問題，利用路網頂點作為錨點提出一種路網興趣點連續KNN查詢隱私保護方法。以上三種方法都采用了匿名框或路網的方式進行隱私保護，但僅考慮軌跡位置與攻擊點的匹配程度，忽略了背景知識的語義信息。通過空間關聯因素推斷并結合特定的領域背景知識，可以將查詢條件作為關聯最初匿名框的接口，從而對軌跡數據進行攻擊，在語義背景下降低了k-匿名的效果。文獻[8]針對語義位置攻擊和最大運行速度攻擊，將語義軌跡隱私問題定義為k-CS匿名問題，實現基于圖上頂點聚類的近似算法，進而對圖上頂點進行匿名。但這種方法缺少對位置節點語義解釋，缺少一個知識庫模型，攻擊者可以將查詢興趣點所在特定軌跡片段結構作為背景知識進行隱私攻擊，構造出至少相同結構和屬性的軌跡作為攻擊候選集，使目標軌跡導致隱私泄露的概率大于1/k，從而泄露與目標相關的信息[9]。

針對現有軌跡匿名模型難以防范以連續查詢為背景知識的攻擊問題，利用事件本體對軌跡連續查詢進行形式化表示的優點，提出一種連續查詢事件攻擊中基于語義的軌跡匿名方法。該方法引入OWL[10](Ontology Web Language)對軌跡的身份隱私、地理信息和敏感查詢事件進行形式化表示，構建基于事件本體的軌跡匿名模型，利用軌跡綜合相似性和Jena推理引擎，給出基于k-匿名的軌跡聚類方法，實現關于當前軌跡的虛假匿名組，最后用實驗驗證本文方法的有效性和可擴展性。

1 問題定義與模型

1.1 連續查詢事件

定義2結構相似查詢：存在一條軌跡T映射F，對于軌跡結構的每一個屬性，諸如采樣點序列、速度、形狀、轉角、加速等，攻擊者通過對軌跡T的相似結構發現隱私數據。從結構相似性帶來的軌跡攻擊表示為：

其中：εSi強度由結構向量集合Si一致性等因素決定，Contex包含攻擊者通過結構屬性獲取軌跡知識，結構屬性的一致性越高，攻擊者構造出F的可能性越高。

1.2 事件本體[13]

事件本體技術能夠描述某個事件行為的概念及概念之間的關系，形式化表示事件行為的語義邏輯，共享、集成、推理的性能，形成相互連接的無環超圖。事件本體在特定的領域本體內，對某個特定時間或環境下發生的表現出的動作特征的形式化描述。通常用表示，ECS表示事件類集合，包含動作(Action)、對象(Objects)、時間(Time)、地點(Place)、內部狀態(Status)和語言表現(Expression)6 個要素的知識單元。R表示事件關系集合，Rules采用描述邏輯語言表示事件之間的規則集合。本文針對用戶在連續查詢事件中存在被攻擊者通過內容關聯、結構特性和連續查詢獲取隱私問題，構建基于事件的本體模型E-Ontology，用于抵御攻擊者對軌跡數據的隱私竊取。

2 連續查詢事件本體建模

2.1 連續查詢事件本體模型

事件本體能夠對軌跡連續查詢進行可共享的明確的形式化規范化說明，本文根據事件本體定義，結合實際研究需求，擴展模型，將其邏輯結構定義為一個五元組E-Ontology={Contexts, Events, Relations, Rules}，其中：

(1) Contexts是查詢事件本體中的背景知識與概念分類集合，每個Context表示一個背景概念分類，包括軌跡位置信息、地理環境信息、用戶身份和社交關系信息等，所有Context構成一個查詢事件背景知識的樹形分類結構。

(2) Events是查詢攻擊事件行為本體分類集合，存儲各類攻擊事件行為的實例及其屬性。本文所述查詢攻擊事件行為包含內容集、對象集、時間段集、內部狀態集和語言描述集等5個要素，其中，內部狀態集包括觸發條件集和結果集。

(3) Relations表示概念與概念之間的關系集合，不同的事件之間通過關系，形成具有圖結構的事件類網絡。關系集合包括包含關系(is_a)、組成關系(isComposed of)、因果關系(causal)、并發關系(concurrence)、跟隨關系(follow)。

(4) Rules是由邏輯描述語言表示的規則集合，可以通過Contexts、Events、Relations的分類形成推理規則。

2.2 E-Ontology構建

如圖1所示，采用OWL對查詢事件本體進行構建，OWL具有較強的語義性和知識表達能力，可較好地支持Jena推理引擎。具體構建步驟如下：

(1) 定義基礎信息類：基礎信息類包括背景知識類和環境信息類，背景知識類(Contexts Class)為一定區域內的地理信息，包含路網頂點、區域、路段、標識、結構等要素，環境信息類包含氣象環境(降水數據、能見度)和物理環境(壓強、磁場)等要素，這些要素作為基礎數據導入本體結構中形成離線的本體結構。從事件本體中自上而下抽象基本類及其層次關系，class表示類中的本體概念，SubClass表示子類，instance表示查詢事件的實例，例如Channel是Line的子類，Position1是Channel的實例。

(2) 定義事件類：不同的本體存在不同的抽象類，從多個事件類中抽取事件要素和事件關系，表示事件當前的狀態信息和行為特征。例如“Move”是當前查詢事件中軌跡的一個狀態，它包括從當前路網頂點移出和移入的行為特征，用“InMove”和“OutMove”表示。當多次查詢一條軌跡上的路網頂點(P1,P2,P3，…)時，觸發事件本體類中各項子類，遍歷P1,P2,P3,…在事件類中位置，若存在當前查詢軌跡在k個匿名范圍實例內的軌跡結構關系或關聯因果關系，則進行報警請求。

(3) 設置事件實例：事件實例作為事件類和事件要素的擴充，包含事件發生的具體內容和屬性，包含類型、關聯強度、因素及約束條件閾值，用Datatype Property表示，細化查詢事件內容。當連續查詢某個軌跡上的路網頂點時，將這些查詢事件存入匿名集，并不斷擴展事件實例庫。

(4) 定義事件關系：① 包含關系，存在事件類EC1={E1,C1A,C1O,C1T,C1P,C1S,C1E}和EC2={E2,C2A,C2O,C2T,C2P,C2S,C2E}，存在EC1∈EC2，當且僅當C1F∧C2F∧C1I∈C2I∧C1A∧C2A。包含關系存在于事件類之間，如查詢路網線段事件與查詢路網頂點事件屬于包含關系，通常用Ris_a表示；② 組成關系，軌跡事件行為類EC1中的一個實例由事件行為類EC2中的某個實例組成時，則該事件行為類EC1由事件類EC2組成，如“敏感位置查詢”由“身份信息查詢事件”、“停留查詢事件”、“離開查詢事件”等組成。組成關系形式化為Rcomp。③ 因果關系，事件類EC1的實例事件發生以一定的概率導致了事件類EC2的實例事件發生，如果發生的概率大于某一閾值，則該兩類事件類存在因果關系，形式化為Rcause。例如惡意者攻擊發現一條軌跡T上的某個位置P在連續查詢事件出現，用戶位置P的泄露導致身份隱私被獲取，則該事件發生的實例為因果關系。④ 跟隨關系，隨著數據流的時間推移，事件類EQ1實例和EQ2實例先后發生，則為該兩類事件存在跟隨關系，形式化表示為Rfollow。例如查詢軌跡中位置P1的事件實例EQ1后，進而查詢位置P1的事件實例用戶出入信息動態EQ2。⑤ 并發關系，在一定時間段內，存在兩個攻擊事件同時發生或攻擊事件發生重合，形式化為Rconcurrence。

圖1 基于事件本體的軌跡匿名模型

3 基于k-匿名查詢的軌跡聚類方法

由于構建的事件本體模型E-Ontology，在知識推理與服務方面建立在描述邏輯基礎上，對動態事件特征的知識無法應用推理，而基于原子動作的動態描述邏輯推理對本體事件要素的概念、關系、實例和公理的可滿足性推理沒有相關的系統框架可參照。因此，本文提出了一種基于k-匿名查詢的軌跡聚類算法，在計算軌跡片段相似度基礎上，利用KNN在獲取鄰近軌跡的優點以及Jena引擎的推理能力，將與當前軌跡相似的k條軌跡進行聚類，從而形成關于當前軌跡的虛假軌跡匿名組。

3.1 軌跡片段相似度計算

(1) 內容關聯強度計算：當前查詢軌跡內容與E-Ontology中屬性及實例之間的近似度。取當前查詢軌跡T={(Tv1,Tv2),(Tv2,Tv3),…,(Tvi,Tvj)}，針對集合中的每個路網位置節點Tvi名稱對應的本體與E-Ontology中實體名稱的文本相似性(Jaccard相似性[14])，并選擇文本相似性最大的實體作為該位置節點匹配的實體，記內容關聯強度為ε，擴充到當前軌跡片段記為：

(1)

(2) 結構相似度計算：當前攻擊查詢軌跡結構屬性及其實例與E-Ontology中屬性及實例的相似程度。取當前查詢軌跡T={(Tv1,Tv2),(Tv2,Tv3),…,(Tvi,Tvj)}，遍歷E-Ontology，當內容關聯命中E-Ontology實體名稱時，進一步向子節點屬性擴展同時獲取葉節點的實例描述，在E-Ontology中選擇與當軌跡片段實例最相似的文本作為學習節點，并記為η：

擴展到當前軌跡片段則計算為：

(3)

定義3(綜合相似度) 為結構相似度和內容關聯度的權重求和，記為：

Sim(vi,Tvj)=θ×A+(1-θ)×S

(4)

按上述方法，對于任意軌跡的綜合相似度，構成一個k階相似度矩陣RSim=(ri,j)k×k。

3.2 基于k-匿名聚類的軌跡查詢事件服務

為實現當前查詢的軌跡與E-Ontology實例相似度最高的k-1條軌跡，形成一個關于當前軌跡的匿名組，本節在語義本體模型和軌跡相似度的基礎上，實現軌跡的k-匿名。算法的基本思路是：在以半徑為δ的區域內，截取當前查詢軌跡片段，采用綜合相似度計算當前軌跡片段與E-Ontology實體、屬性和實例，選取最大的k-1條軌跡，并遍歷整條軌跡，生成關于當前軌跡的虛假軌跡組。最后將學習到的知識更新到語義本體庫中，作為新的相似匿名實例，從而增強軌跡匿名的語義性。如算法1所示。

算法1基于k-匿名聚類的軌跡查詢事件服務

輸入：當前查詢軌跡Tq，軌跡位置節點V(Tq)，參數k表示k條軌跡，參數θ表示相似權重，Tont表示E-Ontology

輸出： 匿名軌跡組Tp

步驟：

1. Initθ=0.5,V(Tq),Vi,Tont,i=0;

2. OntModelTont=ReasonerFactory.CreateReasoner()

//通過Jena推理引擎獲取E-Ontology實體

3. For EachV(Tq)0

Vi++={V(Tq)}

//通過參數Vi進行增量存儲

//當前軌跡位置節點V(Tq)

Rsim=calculating(Vi,Tont,θ)

//計算當前查詢軌跡片段

//與E-Ontology形成的k階矩陣

min=MinDistance(Rsim)

//取輸入軌跡點距離最小間隔的軌跡

Vij=?,j=0

//初始化k階矩陣的列j

For |Rsim|<=kandj

Vij+=max(Tont.Reasoner(Vi),min)

//通過Jena的Reasoner API獲取相似度最大的軌跡

Tp[]=Vij

//最終結果存入Tp[]

End For

End For

ReturnTp

算法1中，步驟1有關參數選?。航o定當前查詢軌跡Tq，選取相似權重θ=0.5，主要是平衡結構相似度和內容關聯度的權重，參數k表示從當前區域內獲取的k條軌跡，V(Tq)表示軌跡的位置節點編碼，初始化為0，通過參數Vi進行增量存儲，并可以調用Rsim求出k階相似度矩陣，時間復雜度為O(n2)；步驟2通過Jena推理引擎生成E-Ontology模型庫；步驟3先計算當前查詢軌跡片段與E-Ontology形成的k階矩陣，然后實時泛化當前軌跡結點的k匿名數據，將相似度最大的k條軌跡存入當前匿名組，形成關于當前軌跡的虛假軌跡。算法根據軌跡片段相似度將當前查詢軌跡片段將和E-Ontology的實體、屬性和實例相似的軌跡片段進行聚類，進而擴充到整條軌跡。

4 實驗結果分析

4.1 實驗數據

為了驗證本文方法的有效性，考慮經典匿名聚類算法NWA[15]和(k,δ)-anonymity[15]在信息損失、近鄰查詢準確度、執行效率三個方面與本文方法的可比性，由此進行實驗對比分析。實驗數據采用Thomas Brinkhoff基于路網的移動對象生成器和和AIS信息服務平臺共同合成的上海近岸地區移動對象的數據集生成的網絡，包括查詢范圍δ、對象數、軌跡點和數據量，如圖2所示。

圖2 系統中生成的數據集網絡

實驗環境在Intel Core 2 Quad 2.4 GHz Windows 10 系統上運行，服務器架構在IBM 3650xm 上，采用Linux Asia 3x 版本，系統數據庫為IBM DB2，算法采用Java語言和Jena推理包實現?？紤]算法在隨機選取軌跡初始節點會導致匿名結果的差別，實驗重復不少于5次，結果取平均值。

4.2 性能分析

本次實驗從信息損失、查詢準確率和執行效率三個方面與不同的k-匿名方法進行性能比較，通過實驗討論算法的性能。

(1) 信息損失比較。本文方法構成的信息損失來自查詢事件軌跡位置節點的匿名聚類造成的內容泛化和結構隱匿的信息損失。因此，采用用戶錯誤訪問子空間軌跡片段數與當前軌跡片段數之比作為度量軌跡信息損失的標準。

圖3給出了不同方法隨著k值的增加信息損失量的變化，實驗表明：與NWA和(k,δ)-anonymity相比，在k值為8～10時本文方法降低了15%～20%，因為本文方法構建了基于事件本體的匿名模型，針對軌跡信息的語義知識不足進行擴展改進，對輸入軌跡動態判斷，采用Jena推理引擎將當前軌跡與歷史軌跡存儲與一個匿名組保證匿名信息的相對完整性。

圖3 隨著k值增大，三種方法的信息損失率

(2) 查詢精準率。在使軌跡數據匿名隱私保護的同時，又保證用戶查詢的精準性。以基于k-匿名查詢的軌跡聚類方法生成的匿名組Tp與當前真實查詢軌跡Tq為中心進行近鄰查詢，查詢內容為用戶提交的LBS軌跡位置節點請求；Tp和Tq為結果集數量，使用查詢準確率POI來衡量服務質量，其計算方式如下所示：

如圖4所示，隨著k值的增加，在半徑δ為100～600 m的范圍內查詢精準率保持在65%以上，實驗表明：本文方法通過Jena引擎將當前軌跡與E-Ontology匹配，使得在軌跡距離上的劃分粒度更為精細，因此在當前匿名軌跡與實際軌跡的距離較小，誤差在半徑范圍較大時保持平衡。

圖4 不同距離下近鄰查詢精準率

(3) 執行效率。為考察本文算法的執行效率，采用運行時間作為執行效率的度量標準。圖5給出了隨著k的增大，相對于NWA和(k,δ)-anonymity，本文方法的運行時間相對減少并且平均低于20秒。實驗表明：本文對內容和結構獨立計算且只進行一次就生成了k階矩陣，而基于事件本體的匿名模型的計算深度通過Jena API直接調用，效率較高，因此開銷時間較小。

圖5 隨著k值增大，執行時間的變化

5 結 語

本文采用OWL形式化表示軌跡數據及查詢事件，提出一種連續查詢事件中基于語義的軌跡k-匿名方法，構建事件本體模型，并結合軌跡片段相似度計算和Jena推理引擎，提出基于k-匿名查詢的軌跡聚類方法。該方法可以防止攻擊者竊取用戶軌跡數據，維護公共安全。然而數據規模擴大伴隨著k值的增大，軌跡數據的不確定性可能影響推理的準確性，后續工作將在原始數據采集和提高匿名質量及匿名算法方面做深入研究。