Databases Reference
In-Depth Information
wm
(attribute, wm key, mark data[],
plugin handler, db primary key, subset size,
v
false
,
v
true
,c)
sort attribute
←
sort on normalized hash
(wm key,db primary key,wm key)
for
(i=0; i
<
length
(
attribute
)
subset size
;i++)
subset bin
←
next
subset size elements from sort attribute
compute
rollback data
encode
(mark data[i % mark data.length], subset bin,
v
false
,
v
true
,c)
propagate
changes into attribute
if (not
goodness plugin handler.isSatisfied(new data,changes))
then
rollback
rollback data
continue
else
commit
map[i] = true
subset boundaries[i] = subset bin[0]
return
map, subset boundaries
Fig. 6.
Watermark Embedding (version using subset markers and detection maps
shown).
secret keyed cryptographic hash
H
of the primary key attribute (
K
). Based
on this value, compose a criteria (e.g.,
H
(
K, key
)) mod
e
= 0) for selecting a
set of “special” tuples such that they are uniformly distributed and average a
total number of
e
=
length
(
attribute
)
/subsetsize
. These special tuples are
going to be used as subset “markers”. Each subset is defined as the elements
between two adjacent markers, having on average
subset size
elements. The
detection phase will then rely on this construction criteria to re-discover the
subset markers. This process is illustrated in Figure 6.
Encoding the individual mark bits in different subsets increases the ability
to defeat different types of transformations including sampling (
A1
) and/or
random data addition (
A2
), by “dispersing” their effect throughout the data,
as a result of the secret ordering. Thus, if an attack removes 5% of the items,
this will result in each subset
S
i
being roughly 5% smaller. If
S
i
is small
enough and/or if the primitive watermarking method used to encode parts
of the watermark (i.e., 1 bit) in
S
i
is made resilient to these kind of minor
transformations then the probability of survival of most of the embedded
watermarks is accordingly higher. Additionally, in order to provide resilience
to massive “cut” attacks, the subsets are made to be of sizes equal to a given
percent
of the overall data set, i.e., not of fixed absolute sizes.
Note:
If enough additional storage is available, these subsets can be in fact
constructed differently: given a secretly keyed cryptographic hash function
with discrete output values in the interval [1
,e
], apply it, for each tuple, to
the primary key attribute value and let its output determine which subset
