Databases Reference
In-Depth Information
2.5 The Adversary
Watermarking is a game between the watermarker and malicious Mallory. In
this game, the watermarker and Mallory play against each other within subtle
trade-off rules aimed at keeping the quality of the result within acceptable
bounds. It is as if there exists an impartial referee (the data itself) moderating
each and every “move”. As discussed above, it is important to make this
“referee” an explicit part of the marking process (consumer-driven paradigm).
It is also important to understand Mallory and the adversarial setting.
Once outsourced, i.e., out of the control of the watermarker, data might
be subjected to a set of attacks or transformations; these may be malicious -
e.g., with the explicit intent of removing the watermark - or simply the result
of normal use of the data. An effective watermarking technique must be able
to survive such use. In a relational data framework important attacks and
transformations are:
A1.
Sampling. The attacker (Mallory) can randomly select and use a sub-
set of the watermarked data set that might still provide value for its intended
purpose (“subset selection”). More specifically, here we are concerned with
both (
A1.a
) horizontal and (
A1.b
) vertical data partitioning - in which a
valuable subset of the
attributes
are selected by Mallory.
A2.
Data Addition. Mallory adds a set of tuples to the watermarked set.
This addition is not to significantly alter the useful properties of interest to
Mallory.
A3.
Alteration. Altering a subset of the items in the watermarked data set
such that there is still value associated with the result. In the case of numeric
data types, a special case needs to be outlined here, namely (
A3.a
) a linear
transformation performed uniformly to all of the items. This is of particular
interest as it can preserve significant valuable data-mining related properties
of the data.
A4.
Ulterior Claims of Rights. Mallory encodes an additional watermark
in the already watermarked data set and claims rights based upon this second
watermark.
A5.
Invertibility Attack. Mallory attempts to establish a plausible (wa-
termark,key) pair that matches the data set and then claims rights based on
this found watermark [8, 9].
Given the attacks above, several properties of a successful solution sur-
face. For immunity against
A1
, the watermark has to be likely encoded in
overall data properties that survive sampling, e.g., confidence intervals, sta-
tistical bias. With respect to (
A1.b
) special care has to be taken such that the
mark survives this partitioning. The encoding method has to feature a certain
attribute-level property that could be recovered in such a vertical partition of
the data. We believe that while vertical data partitioning attacks are possible
and also very likely in certain scenarios, often value is to be found in the asso-
ciation between a set of relation attributes. These attributes are highly likely
to survive such an attack, as the final goal of the attacker is to produce a
