一種基于MapReduce可公開驗證數據來源的水印算法

常耀輝　隋莉莉　汪傳建

摘 要 本文基于公開驗證數據來源的水印算法，采用MapReduce并行編程框架進行設計，并通過實驗證明了該算法的正確性和有效性。

【關鍵詞】地理數據 公有水印 水印完整性 MapReduce

1 問題提出

地理數據庫是地理信息系統的基礎，由于地理數據的加工涉及大量人力、物力和財力，人們提出各種地理數據水印算法對數據的擁有者進行保護。大多數水印算法都需要進行大量的空間計算以及空間變換，特別是當目標地理數據中地物數較多或者地物形狀較復雜時，進行水印信息的嵌入和檢測都會消耗大量時間。各類水印算法往往關注數據的保真性和魯棒性，而對水印算法的高效率執行卻很少涉及。隨著全球空間數據集的急劇增長，如何既快又好的進行水印的嵌入與檢測成為許多研究人員關注的問題。文獻提出一種可公開驗證數據來源的水印算法，但時間復雜度較高，本文針對水印算法的效率問題，嘗試應用MapReduce架構來解決水印信息的嵌入和檢測的時間效率問題。

2 研究基礎

2.1 預備知識

定義1 地物（Polygon）：一個具有m個頂點的多邊形地物Pi可以描述為Pi={pi1， pi2，… pij， pi（j+1）=pim}，（j=1，2，…m），其中pij對應地物Pi中第j個頂點的二維坐標（pijx，pijy）。對于任意一個地物Pi來說，包含的頂點個數是可變的，我們用變量li來度量。

定義2地理數據集（Dataset）：一個包含n個地物的地理數據集D可描述為D={R，P=}，其中R為參考坐標系，P=表示數據庫中的n個地物。

定義3 簽名信息（Signature）：一個長度為k的用戶簽名信息可描述為S={s1，s2， …， si， si+1=sk}，（i=1，2，…k），其中si表示一個比特位，即si={0|1}。

公式1計算地物中心點：對于任意地物Pi，中心點Pi的x，y坐標由如下公式得出

Oix= pijx，Oiy= pijy （1）

公式2計算地物標識符：對于任意地物Pi，其標示符FIDi由如下方式確定：

FIDi=msb（Oi，h）=msb（Oix，h）||msb（Oiy，h）（2）

其中msb（Oix，h），msb（Oiy，h）和分別表示選取點Oi的橫坐標Oix和縱坐標Oiy的高位h，||表示字符連接操作。

2.2 可公開驗證數據來源的水印算法思想

根據D中的n個地物信息{P1，P2，…，Pn }和長度為k的簽名信息{s1，s2， …， sk}，通過對地物中的數據進行水印信息嵌入，生成一個包含n個二進制向量的集合V（v1，v2，…vn），其中vi（1<=i<=n）為一個二進制向量，與原數據集D中的一個地物Pi相對應。每一向量由向量標識和若干個比特位兩部分組成，Vi中比特位長度和Pi的維數相同，其長度等于對應地物Pi中包含的頂點個數li。對于待驗證的數據集D'，應用水印檢測算法生成二進制向量集合V'，通過比較驗證簽名算法依次比較V和V'，如果相同則認為D'來源合法，否則不合法。

3 算法介紹

MapReduce是由Google提出的一種分布式并行編程框架，是云計算平臺主流的數據處理模型。MapReduce的編程原理是基于“分而治之”的思想，MapReduce將復雜的并行計算過程抽象為兩個函數：Mapper（映射）和Reducer（規約），其中Map階段由多個Mapper實現并行的映射，Reduce階段由多個Reducer實現并行的規約，輸出文件數量與Reducer的數量相同。基于MapReduce的地理數據水印算法流程如圖1所示。

3.1 基于MapReduce的水印嵌入算法

水印嵌入算法主要有2部分組成。通過對數據集D進行數據分片后，交由Map階段完成的主要任務是：完成每一地物的標識fid的計算，同時生成二進制字符串H，等待Reduce階段進行水印嵌入使用。Mapper算法框架如下：

Procedure Embed.Mapper（ ）

Input：Dataset P={P1，P2，…，Pn}，Parameter h

Output：Binary Vector Set H（h1，h2，…hn ）

for all Pi in P do

Oi←comput_Central_Point（Pi ）//計算每一地物Pi的中心點Oi；

Pi.fid←msb（Oi，h）； // 生成地物Pi的標識

Pi.vNum←comput_Vertex_Num（Pi）//計算Pi的頂點數Pi.vNum

H←Hash（Pi_fid，Pi.vNum）//生成長度為Pi.vNum的二進制串

Emit（H）

水印嵌入算法Reduce階段主要工作是：結合簽名信息S，確定每一位水印的嵌入信息，生成二進制向量B，作為向外界發布的公開密鑰。Reducer算算法框架如下：

Procedure Embed.Reducer（ ）

Input ： Pi={P1j，P2j，…，Pin}，SignatureVector S， BinaryVectorSet H Parameter t

Output：Binary Vector B={ b1，b2，…，bn }

for all Pij in Pi do

Pij.fid←msb（Pij，h）// 生成Pi中第J個頂點的標識

s=Hash（Pi.fid||Pij.fid） mod t//獲取需要嵌入水印的位置

Bi [j]=Mid（Pij.fid，s，1）?H[j]?S[j]//Mid函數取Pij.fid的第s位，?代表異或算符

Emit（B）

3.2 基于MapReduce的水印檢測算法

水印檢測算法也有兩部分組成。Map階段完成的任務同水印嵌入階段的Map階段人物類似，不同的是針對的對象為待檢測的數據集P，Mapper算法框架如下：

Procedure Extract.Mapper（ ）

Input ： Dataset P={P1，P2，…，Pn}，Parameter h

Output：Binary Vector H（h1，h2，…hn ）

for all Pi in P' do

Oi←comput_Central_Point（Pi ）//計算每一地物Pi的中心點Oi；

Pi.fid←msb（Oi，h）；// 生成地物Pi的標識

Pi.vNum←comput_Vertex_Num（Pi）//計算Pi的頂點數Pi.vNum

H←Hash（Pi_fid，Pi.vNum）//生成長度為Pi.vNum的二進制串

Emit（H）

水印檢測算法Reduce階段主要工作是：檢測每一位水印的嵌入信息，生成二進制向量V，作為檢測出的驗證向量。算法框架如下：

Procedure Extract.Reducer（ ）

Input ： Pi={P1j，P2j，…，Pin}， Parameter t

Output：Binary Vector V={ v1，v2，…，vn }

for all Pik in Pi do

Pik.fid←msb（Pik，t）// 生成Pi中第k個頂點的標識

v=Hash（Pi.fid||Pik.fid） mod t//獲取需要嵌入水印的位置

Vi [j]=Mid（Pik.fid，v，1）?H[j]//Mid函數取Pik.fid的第s位，?代表異或算符

Emit（V）

得到驗證向量V之后，使用公開密鑰B，調用ExtractSig（B，V）算法得到檢測出的簽名信息S'。其算法思想是將公開密鑰B和檢測出的驗證向量C進行比較，對兩個向量進行遍歷，利用特征向量判別相應的地物是否被修改，得到檢測出的簽名信息S'。

完成上述工作之后，將檢測出的簽名信息S'，與代表數據所有權的簽名信息S進行比較，如果一致即認為數據來源合法，否則不合法。

4 實驗與結論

實驗采用Intel CPU 2.4GHZ，內存8 GB，OS Win8.1宿主機，利用VMware WorkStation虛擬出3臺相同的計算機。三臺虛擬機分別安裝Ubuntu12.04操作系統，1GB內存，并部署Hadoop 0.20.0構成集群，一臺同時為Master和Slave節點，其他為Slave節點。開發環境為Eclipse Luna。實驗數據為原算法的數據集，實驗結果表明，本文算法可以處理大規模地理數據集。

參考文獻

[1] Qingzhan Zhao，Lili Sui，Chuanjian Wang etc.Publicly Verify the Integrity of the Geographical Data Using Publlic Watermarking Scheme [C].GRMSE2013，Wuhan，2013，10.

[2] 汪傳建，葛賀飛，丁卯等.一種基于可變步長量化調制的地理數據庫水印方法[J].計算機研究與發展，2011，48（10）：1960-1971.

[3]彭熠瑋，岳明亮，汪傳建.基于MapReduce的高效地理數據水印方法[J].華中科技大學學報（自然科學版），2012， Vol 10，Sup 1：179-182.

作者單位

石河子大學信息科學與技術學院 新疆維吾爾自治區石河子市 832003