Abstract
Internet technology, in modern communities, has become an indispensable tool for everyday life since most people use it on a regular basis and do many daily activities online. This frequent use of the internet means that measures taken for internet security are indispensable since the web is not risk-free. One of those risks is the fact that the web is an environment where intellectual property is under threat since a huge amount of digital data are transferred every day, and thus such data may end up on a user who falsely claims ownership.Digital watermarking (or, simply, watermarking) is a technique for protecting the intellectual property of a digital object; the idea is simple: a unique identifier, which is called watermark, is embedded into a digital object which may be used to verify its authenticity or the identity of its owners. A digital object may be audio, picture, video, text, or software, and the watermark is embedded into object's data through the introduction of errors n ...
Internet technology, in modern communities, has become an indispensable tool for everyday life since most people use it on a regular basis and do many daily activities online. This frequent use of the internet means that measures taken for internet security are indispensable since the web is not risk-free. One of those risks is the fact that the web is an environment where intellectual property is under threat since a huge amount of digital data are transferred every day, and thus such data may end up on a user who falsely claims ownership.Digital watermarking (or, simply, watermarking) is a technique for protecting the intellectual property of a digital object; the idea is simple: a unique identifier, which is called watermark, is embedded into a digital object which may be used to verify its authenticity or the identity of its owners. A digital object may be audio, picture, video, text, or software, and the watermark is embedded into object's data through the introduction of errors not detectable by human perception; note that, if the object is copied then the watermark also is carried in the copy. Efficient watermarking techniques should be able to embed and successfully extract the watermark, even after the digital object has been attacked, i.e., it has been subjected to transformations by malicious users that aim to mislead the watermark extractor.The issues addressed in this thesis concern the design of efficient and easily implementable codec systems for watermarking software and digital media, such as image, audio, and text. Previous works on digital watermarking propose specific encoding techniques for a specific type O of a digital object, i.e., the main idea of a proposed technique for watermarking a digital object of type O cannot be efficiently applied to a different digital object of type O'; for example, the main idea of a proposed technique for watermarking a software (application program) P, cannot be efficiently applied to image I, audio (signal) S or even text T. In our work, we overcome such a drawback by proposing algorithmic techniques for encoding a watermark w into a self-inverting permutation (or, SiP for short) π*, and then embedding the self-inverting permutation π* into different digital objects, i.e., software, image, audio, and text, by using different representations of the same SiP π*. The data structures used to represent the SiP, as well as the encoding techniques, encompasses important properties allowing us to design a codec system which efficiently detect attacks.In the first part of the thesis, presents the basic research on encoding watermark members as graph structures through the use of self-inverting permutations (SiP) and algorithms for multiple encodings. We introduce the notion of a bitonic permutation, and present our algorithm Encode_W.to.SiP for encoding an integer w as a self-inverting permutation π*, along with the corresponding decoding algorithm Decode_SiP.to.W, and discuss important properties of the self-inverting permutation π*. Then, we define the main graph-based data component of our codec system, namely reducible permutation graphs (or, PRG for short), describe the two operational phases of our codec system, and present the structure of our system's reducible permutation graph F[π*]. We next present the two algorithms, namely Encode_SiP.to.RPG-I and -II for encoding the self-inverting permutation π* as a reducible permutation flow-graph F[π*] along with the corresponding decoding algorithms Decode_RPG.to.SiP-I and -II. Finally, we present the properties of the reducible permutation flow-graph F[π*] and show that node-label or edge modifications on the graph F[π*] can be efficiently detected.We extended the class of graphs that encode a watermark by proposing a randomized encoding algorithm which takes as input a self-inverting permutation π* and encodes the same permutation π* into several cographs C1[π*], C2[π*], …, Cn[π*]. Then, we present the algorithm Encode_Cograph.to.RPG, along with its corresponding decoding algorithm, which embeds a cograph into an RPG by exploiting the structure and some important algorithmic properties of its cotree. Thus, having such encoding algorithms, we can encode a watermark number w into many RPGs F1[π*], F2[π*], …, Fn[π*], n ≤ 2. A digital object can be made more resilient to attacks if multiple copies of the same watermark w are embedded into it.The second part of the thesis, presents how the different components of our codec system can be used for watermarking software, digital images and audio, as well as, digital text. Initially, we present our dynamic software watermarking model WaterRPG; we first describe its structural and operational components and then the embedding algorithm Embed_RPG.to.CODE and the extracting algorithm Extract_CODE.to.RPG. The main idea behind the proposed watermarking model is a systematic modification of appropriate function calls of the program P, through the use of control statements and opaque predicates, so that the execution of the watermarked program Pw with a specific input gives a dynamic call-graph from which the watermark graph F[π*] can be easily constructed. Then, we implement our watermarking model in real Java application programs and show two main watermarking approaches supported by the WaterRpg model, namely naive and stealthy. We also evaluate our model under several software watermarking assessment criteria.Next, we present our image watermarking technique where a watermark w or, equivalently, a self-inverting permutation π* of length n*, is transformed from a numerical form to a 2D form (i.e., 2D-representation) through the exploitation of self-inverting permutation properties. The 2D-representation can be efficiently marked on an image I resulting thus the watermarked image Iw. The main idea of the proposed algorithms is that a self-inverting permutation π* is embedded into an image I by first mapping the elements of π* into an n* x n* matrix A* and then using the information stored in A* to mark specific areas of image I in the frequency domain resulting the watermarked image Iw. We have evaluated the embedding and extracting algorithms by testing them on various and different in characteristics images that were initially in JPEG format and we had positive results as the watermark was successfully extracted even if the image was converted back into JPEG format with various compression ratios.Similarly, since an audio signal is one dimensional object, we present a transformation of a watermark w or, equivalently, a self-inverting permutation π* of length n*, from a numerical form to a 1D form (i.e., 1D-representation) and then an algorithm which embeds w into an audio signal. More precisely, our proposed algorithm embeds a self-inverting permutation π* over the set Nn* into an audio signal S by first mapping the elements of π* into an 1D-matrix B* of length n'=n* x n*, and then, based on the information stored in B*, marking specific areas of audio S in the frequency domain resulting thus the watermarked audio Sw. An efficient algorithm extracts the embedded self-inverting permutation π* from the watermarked audio Sw by locating the positions of the marks in Sw; it enables us to reconstruct the 1D representation of π* and, then, obtain the watermark w.Based on the three different representations of self-inverting permutation (SiP), namely 1D-representation, 2D-representation, and RPG-representation (i.e., the encoding of permutation π* as a reducible permutation graph F*[π*]), we present the algorithms Embed_SiP.to.PDF-I, Embed_SiP.to.PDF-II, and Embed_RPG.to.PDF, respectively, along with the corresponding extracting algorithms, for embedding a watermark number (or, equivalently, a self-inverting permutation π* or a reducible permutation graph F*[π*]) into a PDF document file T. We have evaluated the embedding and extracting algorithms by testing them on various and different in characteristics PDF documents.Finally, we conclude the thesis by summarizing our results, discussing possible future extensions, and proposing open problems for further research in the aria of digital watermarking and, in general, in the aria of information hiding.
show more
