Skip to content

F-ca7/AsterMark

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

34 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

演示视频:https://www.bilibili.com/video/BV1Ue411N7f2/

为研究与解决关系型数据库中的数据版权问题,我&Kun设计并开发了一款名为“AsterMark”、用于嵌入/提取关系型数据库水印的桌面应用软件。(获得第八届中国软件杯一等奖

  1. 通过参考相关学术文献,对于数值型、文本型两大类型数据实现了共五种水印嵌入提取算法;
  2. 实现了LSB(最低有效位)修改算法,保证了数据可用性;
  3. 实现了基于统计量特征最优化的水印算法,使得水印难以被人为剔除;
  4. 实现了空格嵌入、符号修改算法,在保证文本内容不变的情况下嵌入水印;
  5. 实现了基于词性逆序数的文本修改算法,保证文本语义不变,同时使得水印难以被察觉;
  6. 适配当前主流关系型数据库,包括:Mysql、PostgreSql、Sql Server。

核心算法介绍


最优化算法

算法分为水印信息嵌入算法与水印信息提取算法。

水印嵌入算法

流程如下:

Graph1

算法描述:

数据集D通过水印嵌入函数映射成被添加水印数据集Dw,其中,水印嵌入函数需要提供一个只有数据分享者才有资格拥有的密钥Ks,以及唯一标识这个数据集的水印信息。以上的嵌入还受约束条件G的影响。

水印嵌入过程

**第一步:数据集划分。**根据密钥Ks与指定的主键,使用Hash算法得到被Hash离散的主键值,根据模取的结果进行分组,数据集D被划分成m个分组。伪代码如下:

Algorithm: get_partitions

Input: Data set D, Secret Key Ks, Number of partitions m, Key of the tuple p

Output: Partitions S0,...,Sm-1

for i from 0 to m-1 Si = {} for each Tuple r ∈ D, partition(r) = H(Ks||H(r.P||Ks)) mod m insert r into S_partition(r) return S0,...,Sm-1

其中,Hash算法的选取决定了分组中数据元组的散列情况。由于被散列值是主键与密钥的拼接,类型多为字符串,这里我们使用散列效果较好的BKDRHash散列函数。

**第二步:水印嵌入。**在不影响数据可用性的前提下,通过调整分组中每一个元组数据,将水印的一位嵌入到该分组中。

一位水印嵌入:对于给定的含有m个数据元组的分组Si,视其为m维向量。找出一个m维向量△i,与Si向量相加,获得Sim向量,此向量可被认为是被添加水印后的分组Sim。

其中△i向量需要根据约束条件集G去寻找。在此,定义隐藏函数,其中,Si为已知量,△i为变量。当待嵌入水印位为1时,求该函数最大值时,△i对应的值;当待嵌入水印位为0时,求该函数的最小值时,△i对应的值。最后根据所求结果,对原数据进行修改。伪代码如下:

Algorithm: encode_single_bit

Input: Partition Si, Bit bi, Constraints set Gi, Secret parameters set γ,Statistics Xmax, Xmin, Minimum member number ξ

Output: Data set Si+Δi*

if ( |Si|\<ξ ) then return Si
if ( bi==1 ) then
maximize( Θγ(Si+Δi) ) subject to Gi
insert Θγ(Si+Δi) into Xmax
else
minimize( Θγ(Si+Δi) ) subject to Gi
insert Θγ(Si+Δi) into Xmin
return Si+Δi

对于隐藏函数的选取,我们使用

针对该函数进行的最大最小化求解,我们使用模式搜索算法。

模式搜索算法伪代码:

Algorithm: pattern_search

Input: Partition origin_partition, Bit bit, Evaluation function sigmoid(), Length of step step_length, Rate of decay decay_rate, accelerate accelerate, Number of turns turn_num

Output: Partition new_partition while step_length > precision, accelerate_direction = [0,0,0,...,0]

searchByAxis:
while turn < turn_num
 for each data in the Si
 new_data = origin_data + step_length
 if sigmoid(new_data) > sigmoid(origin_data) and bit == 1
 origin_data = new_data
 accelerate_direction[origin_data's index] = 1
 if sigmoid(new_data) < sigmoid(origin_data) and bit == 0
 origin_data = new_data
 accelerate_direction[origin_data's index] = 1
 step_length = step_length\decay_rate
 turn++
searchByPattern
 new_partition = origin_partition + accelerate\accelerate_direction
 if sigmoid(new_partition) > sigmoid(origin_partition) and bit = 1
 	origin_partition = new_partition
 if sigmoid(new_partition) > sigmoid(origin_partition) andbit = 0
 	origin_partition = new_partition

第三步:最优阈值求解:

定义:解码错误概率

要求最优阈值,即求出错概率最小时,T的值。因此,当一次导函数等于0时,且二次导函数大于零时,T的值为最优阈值

通过chi-square检测,并且服从正态分布。因此,最后化简可得

水印提取过程

第一步:根据提供的Ks密钥,对于待提取数据集,划分为m个分组。此处,算法同水印嵌入过程,故不再赘述。

第二步:根据水印嵌入过程中计算得到的最优阈值,与分组中的每个数据元组进行比较,利用投票机制,求出该元组嵌入的水印位的值。

伪代码如下:

Algorithm: detect_watermark

Input: Watermarked data set Dw, Number of partitions m, Secret parameter c, Minimum member number ξ, Secret parameter set Ks, Thouhold T*, Watermark length l

Output: Detected watermark Wd

ones[0,..., l-1] = [0,...,0]
zeros[0,..., l-1] = [0,...,0]
S0,...,Sm-1 = get_partitions(Dw,Ks,m)
for j from 0 to m-1
	if( |Sj| >= ξ )
    i = j mod l
    value = Θ( Sj, 0, c)
    if value >= T
    	ones[i] = ones[i] + 1
    else
    	zeros[i] = zeros[i] + 1
for j from 0 to l-1
    if ones[j] > zeros[j]
    	Wd[j]=1
    else if ones[j] < zeros[j]
    	Wd[j]=0
    else
   		Wd[j]='x'
return Wd

软件界面截图


  • 连接主数据库

  • 数据表展示

  • 嵌入水印

  • 嵌入结果展示

  • 提取水印

  • 提取结果展示