Databases Reference
In-Depth Information
correct watermark, at least
ω
−
τω
embedded bits must be toggled. Thus,
the false miss rate is
B
(
ω
1;
ω, p
). An attacker has to flip a significant
portion of tuples in order to get a high probability of success in this attack.
Agrawal and Kiernan's scheme relies on the following assumptions to main-
tain its robustness. First, the watermarked relation has a primary key at-
tribute that either does not change or else can be recovered. The rationale
behind this is that a primary key attribute contains essential information and
that modification or deletion of this information will substantially reduce the
value of the data. With this assumption, the watermark detection is robust
against tuple insertion/deletion and it is not affected by tuple reorganization.
Second, the names of some, if not all, of the watermarked attributes either do
not change or else can be recovered in watermark detection. Under the above
two assumptions, the scheme is robust against attribute operations including
insertion, deletion, and reorganization.
−
τω
−
4.2 Fragile Watermarking
The purpose of fragile watermarking is not to protect copyright, but to detect
and localize possible attacks that modify a distributed or published database.
Li, Guo, and Jajodia's scheme [13] is an example of fragile watermarking
scheme. This scheme embeds a watermark by manipulating the order of the
tuples in each group, where the watermark is computed by hashing all tuple
values in a group. Any change to the underlying data can be detected with a
high probability in watermark detection. Assuming that
q
is the number of tu-
ples in a group, the false hit/miss rate is
1
2
2
in Li, Guo, and Jajodia's scheme,
1
and
2
ln
q
!
in its extended version with the maximal embedding capacity.
Li, Guo, and Jajodia's fragile watermarking scheme can be further ex-
tended to encode watermark information not only to the order of tuples, but
also to the order of attributes. The fundamental assumption is that re-shuing
rows or columns in relational databases will not degrade the quality of data
due to the essential properties of relational data
1
. This extension of the scheme
can further increase the precision in tamper localization in the case that the
database relation consists of a large number of attributes (and tuples).
In such an extension, all attributes are securely divided into a number of
groups, just as all tuples are securely divided into a number of groups. The
only difference is that the attribute grouping is based on attribute name hash
(more precisely, hash of a secret key concatenated with attribute name and
relation name), while the tuple grouping is based on primary key hash. For
each block of data that corresponds to a particular group of tuples and a
1
The essential properties that are widely recognized for relational data include:
(i) Entries in columns are single-valued; (ii) Columns values are of the same
type of data; (iii) Each row has a unique primary key; (iv) Each column has a
unique attribute name; (v) The sequence of columns is insignificant; and (vi) The
sequence of rows is insignificant.
