基于脆弱水印的軌跡數(shù)據(jù)篡改檢測方法

文春雷，汪傳建*，余曉平，王偉強(qiáng)

（1石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院,新疆 石河子 832003；2兵團(tuán)空間信息工程技術(shù)研究中心,新疆 石河子 832003；3兵團(tuán)空間信息工程實驗室,新疆 石河子 832003）

基于脆弱水印的軌跡數(shù)據(jù)篡改檢測方法

文春雷1,2,3，汪傳建1,2,3*，余曉平1，王偉強(qiáng)1,2,3

（1石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院,新疆 石河子 832003；2兵團(tuán)空間信息工程技術(shù)研究中心,新疆 石河子 832003；3兵團(tuán)空間信息工程實驗室,新疆 石河子 832003）

軌跡數(shù)據(jù)是導(dǎo)航與位置服務(wù)系統(tǒng)的核心，是一種重要的數(shù)據(jù)資源。為驗證軌跡數(shù)據(jù)的完整性，檢驗軌跡數(shù)據(jù)是否被篡改，提出一種基于脆弱水印的軌跡數(shù)據(jù)篡改檢測方法。該方法包括水印嵌入算法和水印檢測算法，其中水印嵌入算法和水印檢測算法分別由組水印和軌跡點水印算法組成。嵌入水印時，首先將軌跡數(shù)據(jù)按照分組時間分為若干個組，然后將由組標(biāo)識生成的組水印和由軌跡點坐標(biāo)生成的軌跡點水印分別嵌入到軌跡點坐標(biāo)的最低有效位與次最低有效位。水印檢測時，首先分別對軌跡數(shù)據(jù)進(jìn)行組水印和軌跡點水印檢測，然后通過水印驗證向量的結(jié)果來判定軌跡數(shù)據(jù)的完整性，最后統(tǒng)計篡改檢測率并評估算法的脆弱性。結(jié)果表明，當(dāng)軌跡數(shù)據(jù)以不同的分組和篡改幅度篡改時，其修改檢測率均大于99%，而且該算法可以定位數(shù)據(jù)篡改并識別篡改類型，最后通過實驗驗證了這一點。該方法可為同類軌跡數(shù)據(jù)篡改檢測算法的設(shè)計提供參考。

軌跡數(shù)據(jù)；脆弱水??；數(shù)據(jù)完整性；篡改定位；篡改類型識別

隨著衛(wèi)星、無線網(wǎng)絡(luò)以及定位設(shè)備的發(fā)展，移動物體的軌跡數(shù)據(jù)呈急速增長的趨勢，如交通軌跡數(shù)據(jù)、動物遷徙數(shù)據(jù)、人員移動數(shù)據(jù)等［1］。這些數(shù)據(jù)可以用于移動對象導(dǎo)航、路段內(nèi)車輛流量的監(jiān)控等智能交通的研究，以及城市居民出行行為的分析、數(shù)據(jù)挖掘等研究［2］?；ヂ?lián)網(wǎng)的快速發(fā)展使數(shù)據(jù)的傳遞與交換已經(jīng)變得非常便捷，但是數(shù)據(jù)安全卻面臨新的挑戰(zhàn)：如何保護(hù)數(shù)字產(chǎn)品的版權(quán)，如何驗證數(shù)據(jù)內(nèi)容的完整性，以及如何保障數(shù)據(jù)的擁有者和使用者的權(quán)益等。

數(shù)字水印作為一種新的信息隱藏技術(shù)可以較好的滿足對數(shù)據(jù)的版權(quán)保護(hù)和內(nèi)容完整性驗證的要求。數(shù)字水印技術(shù)是在保證一定數(shù)據(jù)質(zhì)量的前提下將一些標(biāo)識信息 (即數(shù)字水印)直接嵌入數(shù)字媒體中，以達(dá)到確認(rèn)內(nèi)容創(chuàng)建者、購買者、傳送隱秘信息或者判斷載體是否被篡改等目的［3-17］。根據(jù)其魯棒性可分為魯棒水印［4-8］和脆弱水?。?-17］。 其中魯棒水印能抵抗普通數(shù)據(jù)處理或惡意篡改，可用于保護(hù)數(shù)據(jù)版權(quán)，當(dāng)數(shù)據(jù)發(fā)生版權(quán)糾紛時，提取該水印來判斷數(shù)據(jù)的版權(quán)的歸屬。Niu Xiamu等［5］在矢量地理數(shù)據(jù)的冗余點上嵌入水印信息達(dá)到版權(quán)保護(hù)的目的；Wang等［6］提出了基于空間拓?fù)潢P(guān)系的地理數(shù)據(jù)水印方法，該方法將水印信息嵌入到地物的拓?fù)潢P(guān)系中，由于空間拓?fù)潢P(guān)系具有幾何不變性，因此該方法能有效抵抗幾何攻攻擊；Yue Mingliang等［8］提出了1種保護(hù)軌跡數(shù)據(jù)的版權(quán)的算法，該方法引入了1個有限窗口模型，當(dāng)軌跡流數(shù)據(jù)在這個窗口中單向通過時，若連續(xù)2個特征位置出現(xiàn)在同一個處理窗口中則計算特征位置之間的距離，然后將水印嵌入到計算的距離屬性中。脆弱水印對數(shù)據(jù)的篡改非常敏感，數(shù)字媒體受到輕微地改動就會導(dǎo)致水印信息的破壞，因此被廣泛應(yīng)用于檢測數(shù)字產(chǎn)品的完整性，如圖像［10］、音頻［11］、視頻［12］、矢量地理數(shù)據(jù)［13-17］、關(guān)系數(shù)據(jù)庫［17］等。王奇勝等［13］利用矢量地理數(shù)據(jù)自身的特征映射生成脆弱水印，并基于量化思想將數(shù)據(jù)點自身和相鄰數(shù)據(jù)點的水印信息嵌入到數(shù)據(jù)點上，但是該算法不能識別篡改類型。汪傳建等［14］考慮地理數(shù)據(jù)非結(jié)構(gòu)化的特點，提出一種基于脆弱水印的地理數(shù)據(jù)完整性檢驗方法，采用嵌入2次水印的方式把水印信息隱藏在地理數(shù)據(jù)中，檢測地理數(shù)據(jù)完整性并能對數(shù)據(jù)篡改進(jìn)行定位和類型識別。Wang Nana等［15］提出了針對矢量圖形的完整性認(rèn)證算法，將矢量圖形按照線狀實體進(jìn)行分組嵌入水印信息，在篡改定位時可以精確到組。隋莉莉等［16］提出了一種基于脆弱水印的地理數(shù)據(jù)拓?fù)渫暾詸z驗方法，該方法通過地物之間空間相離距離生成水印信息并根據(jù)比值進(jìn)行地物縮放以達(dá)到嵌入水印的目的，通過水印檢測判定地物之間的拓?fù)潢P(guān)系是否被篡改并對篡改進(jìn)行定位。

雖然以上算法［6-17］能對篡改進(jìn)行定位，甚至可識別篡改類型，但是軌跡數(shù)據(jù)作為一種新的數(shù)據(jù)類型，這些算法不能直接應(yīng)用到軌跡數(shù)據(jù)上。在軌跡數(shù)據(jù)版權(quán)方面已有學(xué)者提出算法［7-8］，而在軌跡數(shù)據(jù)完整性保護(hù)方面，研究者較少。而且由于軌跡數(shù)據(jù)的完整性在軍事、導(dǎo)航以及軌跡數(shù)據(jù)挖掘等方面具有重要的作用，所以本研究首次提出了軌跡數(shù)據(jù)的完整性檢測方法。該方法采用兩次嵌入的方式，將組水印和軌跡點水印嵌入到軌跡數(shù)據(jù)中，不但可定位篡改而且可以識別篡改類型。

1 基于脆弱水印軌跡數(shù)據(jù)篡改檢驗方法

1.1 軌跡數(shù)據(jù)的定義和劃分

軌跡數(shù)據(jù)是對移動對象的運(yùn)動過程進(jìn)行采樣得到的數(shù)據(jù)，通常包含采樣位置、時間、運(yùn)動速度等屬性信息，將采樣點按照一定時間尺度排序便形成了移動對象的軌跡［18］。軌跡數(shù)據(jù) DATA={data1，data2，…，dataN}表示N個移動對象軌跡數(shù)據(jù)的集合。1個移動對象的軌跡數(shù)據(jù)實例可被定義為data={id，P}，其中id表示移動對象的編號，P={P1，P2，…，Pn}表示n個軌跡點的集合。Pi={ti，xi，yi}表示 1個移動對象在ti時刻的坐標(biāo)點，其中xi，yi分別表示1個移動對象在ti時刻的經(jīng)度和緯度，i∈{1，2，…，n}。本文所定義的軌跡數(shù)據(jù)為了方便算法的描述，未考慮軌跡數(shù)據(jù)的其他屬性數(shù)據(jù)。軌跡數(shù)據(jù)的實例數(shù)據(jù)如表1所示：

表1 軌跡數(shù)據(jù)分組實例Tab.1 Trajectory data group instance

表1中第一組G1的第一個軌跡點(2008-02-02 14:01:22，116.44516，39.91339)的值分別代表車輛獲取軌跡點的時刻與車輛在這一時刻的經(jīng)度和緯度。

將軌跡數(shù)據(jù)data={id，P}按照分組時間劃分為m個分組之后 data={G1，G2，…，Gm}，1 個分組Gi={P1，P2，…，Pc}內(nèi)有 c 個軌跡點，并且任意兩個組中的數(shù)據(jù)沒有交集。1個分組軌跡點的標(biāo)識Gid=H(id||t1||t2…||tc)，其中H()是一種hash函數(shù)，||是鏈接操作符。數(shù)據(jù)劃分時，1個移動對象的軌跡數(shù)據(jù)有m組，其中分組是私密的，由數(shù)據(jù)所有者保存用于水印提取。如果不知道分組時間，篡改者就很難計算出軌跡點與分組間的歸屬關(guān)系，所以數(shù)據(jù)劃分算法是安全的。經(jīng)過劃分之后，每個分組中平均包含v=n/m個軌跡點。

1.2 檢測方法的概述

從軌跡數(shù)據(jù)的定義可以看出軌跡數(shù)據(jù)DATA是包含多個移動對象的數(shù)據(jù)。當(dāng)增加或刪除1個或多個移動對象的軌跡數(shù)據(jù)時，根據(jù)移動對象的數(shù)目很容易識別這種篡改。當(dāng)對1個或多個移動對象進(jìn)行修改的時，可以根據(jù)水印檢測算法識別篡改類型并定位篡改位置。本文以1個移動對象的軌跡數(shù)據(jù)data為例闡述水印算法：嵌入水印時，首先根據(jù)軌跡數(shù)據(jù)的分組時間將數(shù)據(jù)集劃分為若干個分組，然后分別通過修改該分組中所有軌跡點坐標(biāo)的最低有和次最低有效位嵌入組水印和軌跡點水印。檢測水印時，首先分別從軌跡點坐標(biāo)的最低有效位和低有效位提取組水印和軌跡點水印，然后將生成的水印與提取出的水印進(jìn)行比較，根據(jù)比較結(jié)果來判定數(shù)據(jù)是否被篡改。

1.2.1 水印嵌入

水印嵌入算法的主要思想是將組水印和軌跡點水印分別嵌入到軌跡數(shù)據(jù)的每個分組中。組水印算法是為每個分組生成1個水印信息，然后分別嵌入到該分組中所有軌跡點坐標(biāo)的最低有效位上。軌跡點水印算法是為每個分組生成1個水印信息，然后分別嵌入到該分組中所有軌跡點坐標(biāo)的次最低有效位上。水印生成算法如表2所示，嵌入過程如下：

1)將data中的所有組的標(biāo)識Gid和密鑰K連接起來，作為1個單向哈希函數(shù)的輸入，生成1個二進(jìn)制串W1作為組水印。將data中Gi的所有軌跡點坐標(biāo)除最低2個有效位之外的高位部分坐標(biāo)點的值和密鑰K連接起來，作為1個單向哈希函數(shù)的輸入，生成1個二進(jìn)制串W2作為軌跡點水印。

2)對于分組中的1組數(shù)據(jù)Gi，首先計算其軌跡點個數(shù)len，并根據(jù)組水印W1和軌跡點水印W2分別生成1個長度為len的水印串W1i和W2i，并分別將Gi中的軌跡點坐標(biāo)的最低有效位和次最低有效位修改為W1i和W2i對應(yīng)的水印信息。

3)按順序遍歷data所有分組，重復(fù)第(2)步，完成組水印和軌跡點水印的嵌入。

表2 水印嵌入算法Tab.2 Watermark embedding algorithm

表3 水印生成算法Tab.3 Watermark generation algorithm

1.2.2 水印檢測

軌跡數(shù)據(jù)水印檢測的主要思想是：對待檢測軌跡數(shù)據(jù)data’={id，P}，首先根據(jù)密鑰 K和分組時間將軌跡數(shù)據(jù)劃分為m組 data’={G1’，G2’，...，Gm’}，然后根據(jù)Gi’生成水印并提取水印，最后把生成的水印和提取的水印做比較。水印檢測算法和水印嵌入算法類似，因此對于每個分組Gi，可以構(gòu)造2個水印驗證向量V1和V2，分別保存兩次水印檢測的結(jié)果，并根據(jù)V1和V2的結(jié)果驗證該分組數(shù)據(jù)的完整性。水印檢測算法如表4所示，檢測過程如下：

1)將data’中的所有組的標(biāo)識Gid和密鑰K連接起來，作為1個單向哈希函數(shù)的輸入，生成1個二進(jìn)制串W1作為組水印。將data’中Gi’的所有軌跡點坐標(biāo)除最低2個有效位之外的高位部分坐標(biāo)點的值和密鑰K連接起來，作為1個單向哈希函數(shù)的輸入，生成1個二進(jìn)制串W2作為軌跡點水印。

2)對于Gi’，首先計算其軌跡點個數(shù)len，并根據(jù)組水印W1’生成1個長度為len的水印串W1i和W2i。然后分別將Gi軌跡點坐標(biāo)的最低有效位和次最低有效位連接起來生成 1個二進(jìn)制串W1i’和W2i’。如果W1i與W1i’相等，則V1(i)為真，否則為假；如果W1i’和W2i’相等，則則V2(i)值為真，否則為假。

3)按順序遍歷完data’所有分組，重復(fù)第(2)步，完成水印檢測，得到組驗證向量V1和V2。

水印檢測算法如表4所示。

表4 水印檢測算法Tab.4 Watermark detection algorithm

2 篡改定位和類型識別的方法

通過水印檢測算法，每個Gi得到2個水印驗證向量V1和V2。如果V1和V2的所有值都為真則該數(shù)據(jù)是完整的，否則該組數(shù)據(jù)被修改并定位被修改的數(shù)據(jù)。對于被修改的分組數(shù)據(jù)Gi，可根據(jù)兩個水印驗證向量V1、V2的結(jié)果從而進(jìn)一步識別修改類型。下面以1個移動對象data的軌跡數(shù)據(jù)為例說明如何識別軌跡點篡改類型。

2.1 刪除多個軌跡點數(shù)據(jù)

當(dāng)多個軌跡點數(shù)據(jù)被刪除且軌跡數(shù)據(jù)data的組數(shù)m不變時，假設(shè)G2被修改。根據(jù)水印算法，當(dāng)Gi被刪除時，組水印W1發(fā)生改變，導(dǎo)致W1i均發(fā)生改變，使提取的組水印信息和生成的組水印信息不同，所以水印驗證向量V1的值都為假。軌跡點水印是由每組的軌跡點數(shù)據(jù)生成的，G2的刪除只影響1組，所以水印驗證向量V2的值除了V2(2)為假之外，其他都為真。水印驗證向量V1和V2的結(jié)果如表5所示。

表5 刪除多個軌跡點數(shù)據(jù)時水印驗證向量Tab.5 Watermark verification vector in the case of deleting a group of trajectory point data

由表5可見，當(dāng)V1、V2的數(shù)目沒有變化且V1取值全為假V2取值除了1個為假之外其他全為真時，這種情況無法判斷判斷篡改類型（表5、表6、表7結(jié)果相同），只能定位篡改。當(dāng)多個軌跡點數(shù)據(jù)被刪除且軌跡數(shù)據(jù)data的組數(shù)m改變時，V1、V2的數(shù)量會減少，根據(jù)水印驗證向量V1和V1數(shù)目的減少可以判斷這種篡改類型為刪除。

2.2 插入多個軌跡點數(shù)據(jù)

當(dāng)多個軌跡點數(shù)據(jù)被插入且軌跡數(shù)據(jù)data的組數(shù)m不變時，假設(shè)數(shù)據(jù)插到G2了中。根據(jù)水印算法，當(dāng)G2被插入數(shù)據(jù)時，組水印W1發(fā)生改變，導(dǎo)致W1i均發(fā)生改變，使提取的組水印信息和生成的組水印信息不同，所以水印驗證向量V1的值均為假。軌跡點水印是由每組的軌跡點數(shù)據(jù)生成的，G2中數(shù)據(jù)的插入只影響1組，所以水印驗證向量V2的值除了V2(2)為假之外，其他都為真。水印驗證向量V1和V2的結(jié)果如表6所示。

表6 插入多個軌跡點數(shù)據(jù)時水印驗證向量Tab.6 Watermark verification vector in the case of inserting a group of trajectory point data

由表6可見，當(dāng)V1、V2的數(shù)目沒有變化且V1取值全為假V2取值除了1個為假之外其他全為真時，這種情況無法判斷判斷篡改類型，只能定位篡改。當(dāng)多個軌跡點數(shù)據(jù)被插入且軌跡數(shù)據(jù)data的組數(shù)m改變時，V1、V2的數(shù)量會增加，根據(jù)水印驗證向量V1和V2數(shù)目的增加可以判斷這種篡改類型為插入。

2.3 修改多個軌跡點數(shù)據(jù)

軌跡數(shù)據(jù)的修改分3種情況：第一種是只修改了時間，第二種是只修改了坐標(biāo)點，第三種是同時修改時間和坐標(biāo)點。若只修改了時間，則水印驗證向量V1和V2的數(shù)目不變且V1的值全為假V2的值全為真；若只修改了坐標(biāo)點，則水印驗證向量V1和V2的數(shù)目不變且V1的值全為真，V2中被修改的值均為假；若同時修改了時間和坐標(biāo)點，假設(shè)G2被修改。根據(jù)水印算法，當(dāng)G2被修改時，組水印W1發(fā)生改變，導(dǎo)致W1i均發(fā)生改變，使提取的組水印信息和生成的組水印信息不同，所以水印驗證向量V1的值均為假。軌跡點水印是由每組的軌跡點數(shù)據(jù)生成的，G2中數(shù)據(jù)的修改只影響1組，所以水印驗證向量V2的值除了V2(2)為假之外，其他均為真。水印驗證向量V1和V2的結(jié)果如表7所示。

表7 修改多個軌跡點數(shù)據(jù)時水印驗證向量Tab.7 Watermark verification vector in the caseof modifying a group of trajectory point data

根據(jù)修改軌跡數(shù)據(jù)的3種情況的分析可知，只修改時間或者只修改坐標(biāo)點可以識別篡改類型，當(dāng)時間和坐標(biāo)點同時修改時無法識別篡改類型只能定位篡改。因為data是根據(jù)時間進(jìn)行分組的，當(dāng)時間被篡改（插入，刪除，修改）之后，組數(shù)可能增加、減少或者不變。當(dāng)被修改后的時間不在軌跡數(shù)據(jù)data采集的時間范圍內(nèi)則組數(shù)會增加，否則組數(shù)可能會不變或者減少。

3 實驗結(jié)果與分析

3.1 實驗結(jié)果

軌跡數(shù)據(jù)篡改檢測的目的是判斷軌跡數(shù)據(jù)的完整性并判斷非法的篡改。為了驗證軌跡數(shù)據(jù)分組數(shù)以及不同的篡改幅度(Tampering amplitude，TA)對脆弱水印算法性能的影響，首先以不同的分組時間對軌跡數(shù)據(jù)進(jìn)行分組得到不同版本的軌跡數(shù)據(jù)并分別嵌入水印，然后對嵌入水印的軌跡數(shù)據(jù)實施不同幅度的篡改，最后通過水印檢測計算不同版本的軌跡數(shù)據(jù)所對應(yīng)的篡改檢測率(Percentage of tampering detection，PTD，用百分百的形式表示)。本研究中篡改幅度表示對加水印數(shù)據(jù)實施不同比率的修改，篡改檢測率是檢測出的篡改（水印驗證向量的修改的方式表示）與實際篡改的比值，用于評估算法的脆弱性。用于實驗的軌跡數(shù)據(jù)為微軟T-Drive數(shù)據(jù)［19］，這個軌跡數(shù)據(jù)集大約有1500萬條包含10357出租車1周的軌跡數(shù)據(jù)（用于實驗的軌跡的數(shù)據(jù)為這個數(shù)據(jù)集的部分?jǐn)?shù)據(jù)）。

對嵌入水印之后的軌跡數(shù)據(jù)實施3種不同類型的篡改，當(dāng)篡改強(qiáng)度比較大時一定能看出數(shù)據(jù)的篡改，這樣來評價算法的脆弱性則無意義。因此，在做實驗時采用較小的篡改的強(qiáng)度來評估算法的脆弱性。實驗首先分別以GT=0.5、1、1.5、2、2.5 h(GT 為分組時間group time;h為小時)對軌跡數(shù)據(jù)data分組得到5個版本的data，然后分別嵌入水印并對每個版本的 data分別以 0.01%、0.03%、0.05%、0.07%、0.09%的篡改幅度進(jìn)行篡改，最后統(tǒng)計分析data的篡改檢測率（為重復(fù)5次的平均值）。由于篡改的數(shù)據(jù)比較少，所以插入、刪除、修改的多個軌跡點時可以看出是1種篡改，其結(jié)果如表8所示。

表8 篡改多個軌跡點數(shù)據(jù)的篡改檢測率Tab.8 PTD of tamper multiple trajectory point data

3.2 結(jié)果分析

在相同的篡改幅度下，隨著每組軌跡點個數(shù)的增加，篡改檢測率也增加。因為組水印是由data中的所有組的標(biāo)識Gid和密鑰K連接起來通過哈希函數(shù)生成，軌跡點水印是由分組中軌跡點坐標(biāo)生成的。當(dāng)對嵌入后的軌跡數(shù)據(jù)data’篡改時，水印位發(fā)生變化或者不改變的概率都為1/2。假設(shè)嵌入水印后的軌跡數(shù)據(jù)data’劃分為v組每組有c個軌跡點，則在對data’進(jìn)行篡改之后每個組水印位都不變的概率為1/2c，而水印位發(fā)生改變的概率為1-1/2c，所以對整個軌跡數(shù)據(jù)來篡改后發(fā)生改變的概率為(1-1/2c)v。由于對軌跡數(shù)據(jù)的篡改幅度比較小，可以忽略篡改之后c、v的變化，所以data’劃分后的組數(shù)越少，每組中軌跡點個數(shù)越多，則篡改后水印位發(fā)生改變的概率越大。

3.3 篡改檢測方法的比較

本研究對目前國內(nèi)外在數(shù)據(jù)的篡改研究中提出的各類方法進(jìn)行了分類和對比，并列舉了各類方法的主要優(yōu)點、主要缺點（表9）。

表9 篡改檢測方法比較Tab.9 Comparison of tamper detection methods

由表9可見，表中所對比的方法都能定位篡改，但是文獻(xiàn)［7］的篡改檢測率波動較大，文獻(xiàn)［14］篡改檢測率為100%。因為文獻(xiàn)［9］的的篡改幅度比較大而且未按組進(jìn)行篡改，文獻(xiàn)［14］是按組進(jìn)行篡改的。在篡改幅度較大時一定能識別數(shù)據(jù)的篡改，但這在實際應(yīng)用中可能性較小。較好的篡改算法的標(biāo)準(zhǔn)為：在篡改幅度比較小的情況下，仍能定位篡改。本研究提出的方法主要是從傳統(tǒng)數(shù)據(jù)的篡改檢測方法向時空方向拓展而得到，該方法在篡改幅度較小時仍能定位篡改。總的來說，以上方法均可定位篡改，但在水印嵌入時會修改原始數(shù)據(jù)使數(shù)據(jù)質(zhì)量下降，所以表9中提出的方法適用于精度要求較低的數(shù)據(jù)。

4 總結(jié)

（1）本文提出的算法可以有效的檢測軌跡數(shù)據(jù)的篡改，并實現(xiàn)了對被篡改數(shù)據(jù)的位置定位和篡改類型的識別。

（2）該算法可為軌跡數(shù)據(jù)的篡改檢測提供1個新的思路，具有重要的理論和應(yīng)用價值。

（3）本文提出的算法可以檢測軌跡數(shù)據(jù)的篡改，但該算法仍有一些不足，如：篡改類型的判斷不精確，軌跡數(shù)據(jù)的數(shù)據(jù)量比較大的計算非常耗時。今后將圍繞這兩個問題繼續(xù)完善并優(yōu)化該算法。

［1］Zheng Y.Trajectory data mining:an overview［J］.ACM Transactions on Intelligent Systems and Technology(TIST)，2015，6(3):29.

［2］胡慶武，王明，李清泉.利用位置簽到數(shù)據(jù)探索城市熱點與商圈［J］.測繪學(xué)報，2013，43(3):314-321.

Hu Q W，Wang M，Li Q Q.Urban hotspot and commercial area exploration with check-in data ［J］.Acta Geodaetica et Cartography Sinica，2013，43(3):314-421.

［3］Podilchuk C I，Delp E J.Digital watermarking:algorithms and applications［J］.IEEE Signal Processing Magazine，2001，18(4):33-46.

［4］Barni M，Bartolini F，Cappellini V，et al.A DCT-domain system for robust image watermarking［J］.Signal Processing，1998，66(3):357-372.

［5］Niu X M，Shao C Y，Wang X T.GIS watermarking:hiding data in 2D vector maps ［C］//Intelligent Multimedia Data Hiding.Berlin Heidelberg:Springer，International Publishing,2007:123-155.

［6］Wang C，Peng Z，Peng Y，et al.Watermarking geographical data on spatial topological relations［J］.Multimedia Tools and Applications，2012，57(1):67-89.

［7］Jin X，Zhang Z，Wang J，et al.Watermarking spatial trajectory database［J］.Database Systems for Advanced Applications，2005:56-67.

［8］Yue M，Peng Z，Zheng K，et al.Rights protection for trajectory streams［J］.Database Systems for Advanced Applications，2014:407-421.

［9］Yue M，Peng Z，Peng Y.A fragile watermarking scheme for modification type characterization in 2d vector maps［C］.//Asia-Pacific Web Conference.Berlin Heidelberg:Springer International Publishing，2014:129-140.

［10］Caragata D，El Assad S，Luduena M.An improved fragile watermarking algorithm for JPEG images［J］.AEU-International Journal of Electronics and Communications，2015，69(12):1783-1794.

［11］Zamani M，Manaf A B A.Genetic algorithm for fragile audio watermarking ［J］.Telecommunication Systems，2015，59(3):291-304.

［12］Chen M，He Y，Lagendijk R L.A fragile watermark error detection scheme for wireless video communications［J］.IEEE Transactions on Multimedia，2005，7(2):201-211.

［13］王奇勝，朱長青.一種用于精確認(rèn)證的矢量地理數(shù)據(jù)脆弱水印算法［J］.測繪科學(xué)技術(shù)學(xué)報，2012，29(3):218-221.

Wang Q S，Zhu C Q.Fragile watermarking algorithm for vector geographic data exact authentication［J］.Journal of Geomatics Science and Technology，2012，29(3):218-221.

［14］汪傳建，彭煜瑋，趙慶展，等.基于弱水印的地理數(shù)據(jù)篡改檢驗方法［J］.小型微型計算機(jī)系統(tǒng)，2014，35(12):2628-2632.

Wang C J，Peng Y W，Zhao Q Z，et al.Fragile watermarking scheme for checking the tamper of geographical data［J］.Journal of Chinese Computer Systems，2014，35(12):2628-2632.

［15］Wang N，Men C.Reversible fragile watermarking for locating tampered blocks in 2D vector maps［J］.Multimedia Tools and Applications，2013，67(3):709-739.

［16］隋莉莉，汪傳建.基于弱水印的地理數(shù)據(jù)拓?fù)渫暾詸z驗方法［J］.計算機(jī)科學(xué)，2016，43(2):183-187.

Sui L L，Wang C J.Checking topological integrity of geographic data based on fragile watermarking［J］.Computer Science，2016，43(2):183-187.

［17］Guo H，Li Y，Liu A，et al.A fragile watermarking scheme for detecting malicious modifications of database relations［J］.Information Sciences，2006，176(10):1350-1378.

［18］霍崢,孟小峰.軌跡隱私保護(hù)技術(shù)研究［J］.計算機(jī)學(xué)報,2011,34(10):1820-1830.

Huo Z，Meng X F.A Survey of trajectory privacy-preserving techniques［J］.Chinese Journal of Computers，2011，34(10):1820-1830.

［19］Yuan J，Zheng Y，Zhang C，et al.T drive:driving directions based on taxi trajectories［J］.Information Systems，2010:20,99-108.

Tampering detection of trajectory data based on fragile watermarking

Wen Chunlei1,2,3,Wang Chuanjian1,2,3*,Yu Xiaoping1,Wang Weiqiang1,2,3
(1 College of Information Science and Technology,Shihezi University,Shihezi,Xinjiang 832003,China;2 Geospatial Information Engineering Research Center,Xinjiang Production and Construction Corps,Shihezi,Xinjiang 832000,China;3 Geospatial Information Engineering Laboratory,Xinjiang Production and Construction Corps,Shihezi,Xinjiang 832003,China)

Trajectory data is the important infrastructure of Navigation and location service system,and is an important data resource.In order to verify the integrity of trajectory data and determine whether the trajectory data is tampered or not,a fragile watermarking scheme is proposed.The fragile watermarking scheme includes watermark embedding algorithm and watermark detection algorithm.The watermark embedding algorithm and the watermark detection algorithm are composed of the group algorithm watermark and the track point watermark algorithm respectively.When embedding watermark,first of all the trajectory data is divided into several groups by the group time,then trajectory point coordinates of least significant bit and next least significant bit are embedded by group watermark generated by group identification and the trajectory point watermark generated by a group of trajectory point coordinates.Watermark detection algorithm consists of group watermark detection algorithm and trajectory points watermark detection algorithm.When detecting the watermark,first of all the integrity of trajectory data can be verified by the watermark verification vector's result pattern,and then according to the result of watermark verification vector the detection rate can be revised and the vulnerability of the watermarking algorithm can be evaluated.The results demonstrate that when the trajectory data is tampered with by different group and tamper amplitude,all the modified detection rates are greater than 99%.What's more,the modifications made to trajectory points can be detected and localized,which is also checked by the experimental results.This method can provide a reference for the design of similar methods for trajectory data tamper detection.

trajectory data;fragile watermarking;data integrity;locating tampering position;identifying tampering type

TP311

A

10.13880/j.cnki.65-1174/n.2017.03.021

1007-7383(2017)03-0391-06

2016-11-17

國家自然科學(xué)基金項目（61262021、41361083）

文春雷(1989-)，男，碩士研究生，研究方向為空間信息技術(shù)及應(yīng)用，e-mail：254305068@qq.com。

*通信作者：汪傳建(1977-)，男，副教授，從事時空數(shù)據(jù)安全和數(shù)據(jù)挖掘研究，e-mail：wcj_inf@shzu.edu.cn。