Frontiers in Computer Education

Frontiers in Computer Education – Wang (ed.)

© 2015 Taylor & Francis Group, London, ISBN 978-1-138-02797-8

A study in watermarking relational databases based on genetic algorithms

Qingtao Wu

School of Art & Design, Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou, China

Pengsong Duan

Zhengzhou University Software Institute, Zhengzhou, China

Jinfa Shi

Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou, China

ABSTRACT: This paper studies a novel scheme of watermarking relational databases for copyright protection

based on genetic algorithms. In this algorithm, a GA is used in a watermark signal processes, and associated

novel watermark insertion algorithms and detection algorithms are proposed. Thus, the watermark signal in this

method is expected to be more meaningful and has closer correlative relationship to the copyright holder. The

experimental results verify that the proposed algorithm is feasible, effective, and robust.

1 INTRODUCTION

Relational database watermarking protects the intel-

lectual property in today’s internet-based application

environments and in many content distribution appli-

cations. We present a mechanism for proof of own-

ership based on the secure embedding of a robust

imperceptible optimization watermark in relational

database. Based on the rational database watermark,

researches in database watermarks are being con-

ducted by people such as R. Agrawal and R. Sion.

Including previous research into watermarking, they

pay attention to arithmetic embedding and extracting.

A Genetic Algorithm (GA) is a search technique

that is based on the principles of natural selection or

survival of the fittest. Genetic algorithms are one of

the best ways to solve a problem about which little is

known objectively and functions directly in the search.

Then, by using evolving operations such as crossover,

mutation, and selection, the GA creates successive

generations of solutions that evolve and inherit the pos-

itive characteristics of their parents and thus gradually

approach optimal or near-optimal solutions. By using

the objective function directly in the search, GA’s can

be effectively applied in nonconvex, highly nonlinear,

and complex problems.

The main contributions to this work include: pre-

senting an effective GA technique to generate water-

mark signal; and present a new technique to insert

and detect watermarks using a mark bit position,

together with a decision-making algorithm by pattern

matching. In order to improve robustness, the scheme

embeds a watermark into the database for several times

and recovers the detected watermark by a majority

voting mechanism.

2 ALGORITHMS FOR WATERMARKING

RELATIONAL DATABASES

In this section, the watermark embedding and extrac-

tion algorithms are presented. We assume that some

minor changes of some attributes values can be toler-

ated. And we will embed copyright information into

these attributes. We consider the character copyright

information as a sequence of 0 and 1, the marks of 0 and

1 are small errors in the relational data. All the marks

of 0 and 1 represent integrated copyright information.

The problem of watermarking relational databases can

be modelled as follows.

Suppose relation R contains a primary key P and

numerical attributes A0, A1,…, Av-1. Assume that it

is acceptable to change one of ξ Least Significant

Bits (LSB). Copyright information which will con-

vert as a sequence of 0 and 1 is to be embedded into

relation R for the purpose of copyright protection.

Table 1 summarizes the important parameters used in

our algorithms.

Our technique aims to mark only numeric attributes.

The data owner is responsible for deciding which

attributes are suitable for marking. He also helps

to decide two important parameters ξ and γ, which

describe the limits of modification to a database. We

also suppose the adversary should not remove or mod-

ify the primary key attributes for the integrity and

availability of the database. An attacker cannot guess

61