Databases Reference
In-Depth Information
In other words, the watermark is modeled by the percentage of positive
confidence violators present in
S
i
for a given confidence factor
c
and confidence
violators hysteresis (
v
false
,v
true
). Encoding the single bit (see Figure 8),
b
,
into
S
i
is therefore achieved by minor alterations to some of the data values
in
S
i
such that the number of positive violators (
v
c
(
S
i
)) is either (a) less than
v
false
×|
S
i
|
if
b
= 0, or (b) more than
v
true
×|
S
i
|
if
b
= 1. The alterations
are then checked against the change tolerances,
G
, specified by the user.
encode
(bit, set,
v
false
,
v
true
,c)
compute
avg
(
set
),
δ
(
set
)
compute
v
c
(
set
)
if
v
c
(
set
)
satisfies
desired bit value
return
true
if
(bit)
compute
v
∗
← v
true
− v
c
(
set
)
alter
v
∗
items close to the stddev boundary so that they become
>v
true
else
(!bit) case is similar
compute
v
c
(
set
)
if
v
c
(
set
)
satisfies
desired bit value
return
true
else rollback
alterations (distribution shifted too much?)
return
false
Fig. 8.
Single Bit Encoding Algorithm (illustrative overview).
At detection time the secret subsets are reconstructed and the individual
bits are recovered according to the single-bit mark encoding convention. This
yields the original
e
-bit string. If
e
is larger than the size of the watermark,
error correction was deployed to increase the encoding resilience. The wa-
termark string can be then recovered by applying error correction decoding
to this string, e.g., majority voting for each watermark bit. This process is
illustrated in Figure 9.
In [27,33] and [34] the authors discuss a proof of concept implementation.
It is worth mentioning here due to its consumer-driven design (see Figure
10). In addition to a watermark to be embedded, a secret key to be used
for embedding, and a set of relations/attributes to watermark, the software
receives as input also a set of external
usability plugin modules
. The role of
these plugins is to allow user defined query metrics to be deployed and queried
at run-time without recompilation and/or software restart. The software uses
those metrics to re-evaluate data usability after each atomic watermarking
step.
Constraint metrics can be specified either as SQL queries, stored proce-
dures or simple Java code inside the plug-in modules. Constraints that arise
from the schema (e.g., key constraints), can easily be specified in a form sim-
