Algorithmic techniques for encoding permutations and permutation graphs for watermarking software, image, audio, and text

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 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.

Στη σύγχρονη εποχή το διαδίκτυο αποτελεί αναπόσπαστο τεχνολογικό μέσο βοήθειας των δραστηριοτήτων της καθημερινής μας ζωής, καθώς χρησιμοποιείται για τη διεκπεραίωση σύνθετων, και συχνά χρονοβόρων, επαγγελματικών και καθημερινών εργασιών. Η συνεχής και συχνή χρήση του διαδικτύου, ο όγκος της ψηφιακής πληροφορίας που διακινείται μέσω αυτού, το εύρος της ηλικιακής διαστρωμάτωσης χρήσης του, και επιπλέον οι πολλαπλοί κίνδυνοι της προσωπικής ασφάλειας των χρηστών του, απαιτούν αυξημένα και τεχνολογικά ευφυή μέτρα προστασίας αυτού.Η ψηφιακή υδατοσήμανση (ή, υδατοσήμανση) είναι μια τεχνική για την προστασία της πνευματικής ιδιοκτησίας ενός ψηφιακού αντικειμένου. Η ιδέα είναι απλή: ένα μοναδικό αναγνωριστικό, το οποίο ονομάζεται υδατόσημα, ενσωματώνεται στο ψηφιακό αντικείμενο προκειμένου να χρησιμοποιηθεί για την απόδειξη της αυθεντικότητας ή αναγνώριση της ταυτότητας του ψηφιακού αντικειμένου από τους ιδιοκτήτες του. Ένα ψηφιακό αντικείμενο μπορεί να είναι ψηφιακός ήχος, εικόνα, κείμενο, ή λογισμικό, και το υδατόσημα ενσωματώνεται στο ψηφιακό αντικείμενο εισάγοντας σε αυτό τροποποιήσεις που δεν είναι ορατές και δεν γίνονται αντιληπτές. Για να είναι αποδοτική μια προτεινόμενη τεχνική υδατοσήμανσης, θα πρέπει να ενσωματώνει αποτελεσματικά το υδατόσημα στα ψηφιακά δεδομένα του αντικειμένου και να το εξάγει επιτυχώς, ακόμη και αν το αντικείμενο αυτό έχει υποστεί τροποποιήσεις, δηλαδή έχει δεχθεί επιθέσεις από κακόβουλους χρήστες με σκοπό την μη-εφικτή ή ανεπιτυχή εξαγωγή του υδατόσημου.Η παρούσα διδακτορική διατριβή πραγματεύεται θέματα σχετικά με την σχεδίαση αποτελεσματικών και εύκολα υλοποιήσιμων συστημάτων κωδικοποίησης για την υδατοσήμανση λογισμικού και ψηφιακών μέσων, όπως είναι η εικόνα, ο ήχος, και το κείμενο. Στα έως σήμερα ερευνητικά αποτελέσματα ψηφιακής υδατοσήμανσης, κάθε προτεινόμενη τεχνική κωδικοποίησης και ενσωμάτωσης εφαρμόζεται συνήθως σε ένα συγκεκριμένο είδος ψηφιακού αντικειμένου O. Πιο συγκεκριμένα, τεχνικές κωδικοποίησης που έχουν εφαρμοστεί για την υδατοσήμανση ενός ψηφιακού αντικειμένου O, δεν μπορούν να εφαρμοστούν, τουλάχιστον εύκολα, σε ένα διαφορετικό αντικείμενο O'. Για παράδειγμα, η βασική ιδέα μιας τεχνικής που χρησιμοποιήθηκε στην υδατοσήμανση ενός λογισμικού P, δεν μπορεί να εφαρμοστεί αποτελεσματικά στην εικόνα I, στον ήχο S ή ακόμα σε ένα κείμενο Τ. Η σημαντική συνεισφορά της παρούσας διατριβής έγκειται στη σχεδίαση αποτελεσματικών αλγοριθμικών τεχνικών κωδικοποίησης ενός υδατόσημου w σε μια αυτοαναστρέφουσα μετάθεση (ή, SiP) π*, καθώς και στην ενσωμάτωση της αυτοανατρέφουσας μετάθεσης π* σε διαφορετικά ψηφιακά αντικείμενα, όπως λογισμικό, εικόνα, ήχος, και κείμενο, χρησιμοποιώντας διαφορετικές αναπαραστάσεις της ίδιας μετάθεσης π*. Οι δομές δεδομένων που χρησιμοποιούνται για την αναπαράσταση της SiP, όπως επίσης και οι τεχνικές κωδικοποίησης, ενσωματώνουν σημαντικές ιδιότητες που δίνουν τη δυνατότητα σχεδίασης συστημάτων κωδικοποίησης που ανιχνεύουν αποτελεσματικά ένα πλήθος κακόβουλων επιθέσεων.Στο πρώτο μέρος της διατριβής, παρουσιάζονται τα βασικά ερευνητικά αποτελέσματα για την κωδικοποίηση αριθμητικών υδατοσημάτων σε γραφήματα μέσω της αυτοαναστρέφουσας μετάθεσης (SiP) π*, καθώς και αλγόριθμοι πολλαπλής κωδικοποίησης. Εισάγουμε αρχικά την έννοια των διτονικών (bitonic) μεταθέσεων και στη συνέχεια παρουσιάζουμε τον αλγόριθμο Encode_W.to.SiP για την κωδικοποίηση ενός ακεραίου αριθμού w σε μια αυτοαναστρέφουσα μετάθεση π*, όπως επίσης και τον αντίστοιχο αλγόριθμο αποκωδικοποίησης Decode_SiP.to.W, με παράλληλη αναφορά στις σημαντικές ιδιότητες μιας αυτοαναστρέφουσας μετάθεσης π*. Στη συνέχεια, ορίζουμε τη βασική γραφοθεωρητική συνιστώσα του προτεινόμενου συστήματος κωδικοποίησης, την οποία ονομάζουμε αναγώγιμο μεταθετικό γράφημα (reducible permutation graph ή, PRG), περιγράφουμε τις φάσεις κωδικοποίησης ενός υδατόσημου σε αναγώγιμο μεταθετικό γράφημα F[π*], καθώς και τη δομή του γραφήματος F[π*]. Πιο συγκεκριμένα, παρουσιάζουμε τους αλγορίθμους Encode_SiP.to.RPG-I και -II για την κωδικοποίηση μιας αυτοαναστρέφουσας μετάθεσης π* σε ένα αναγώγιμο μεταθετικό γράφημα F[π*], καθώς και τους αντίστοιχους αλγορίθμους αποκωδικοποίησης Decode_RPG.to.SiP-I και -II. Τέλος, αναφέρουμε τις ιδιότητες του αναγώγιμου μεταθετικού γραφήματος F[π*] και αποδεικνύουμε ότι κακόβουλες επιθέσεις στο γράφημα F[π*], όπως μετονομασία κόμβων και τροποποίηση ακμών, μπορούν να ανιχνευτούν αποτελεσματικά.Επεκτείνουμε τη κλάση των γραφημάτων που κωδικοποιούν ένα υδατόσημα προτείνοντας έναν πιθανοτικό αλγόριθμο κωδικοποίησης (randomized algorithm), ο οποίος δέχεται ως είσοδο μια αυτοαναστρέφουσα μετάθεση π* και κωδικοποιεί αυτή σε διαφορετικά συμπληρωματικά αναγώγιμα γραφήματα (complement-reducible graphs) ή cographs C1[π*], C2[π*], …, Cn[π*]. Στη συνέχεια, παρουσιάζουμε τον αλγόριθμο Encode_Cograph.to.RPG, καθώς και τον αντίστοιχο αλγόριθμο αποκωδικοποίησης, ο οποίος μετατρέπει ένα cograph Ci[π*] σε ένα αναγώγιμο μεταθετικό γράφημα Fi[π*] χρησιμοποιώντας τη δομή του και σημαντικές αλγοριθμικές ιδιότητες της μοναδιαίας δενδρικής αναπαράστασης (cotree) ενός cograph. Επομένως, μπορούμε να κωδικοποιήσουμε ένα αριθμητικό υδατόσημα w σε πολλά αναγώγιμα μεταθετικά γραφήματα F1[π*], F2[π*], …, Fn[π*], n ≤ 2. Η ενσωμάτωση πολλαπλών αντιγράφων που κωδικοποιούν το ίδιο υδατόσημα σε ένα ψηφιακό αντικείμενο καθιστά αυτό πιο ανθεκτικό σε κακόβουλες επιθέσεις.Στο δεύτερο μέρος της διατριβής, παρουσιάζονται αλγοριθμικές τεχνικές υδατοσήμανσης λογισμικού, ψηφιακής εικόνας, ήχου, και κειμένου, οι οποίες βασίζονται στα δομικά στοιχεία που αναπτύχθηκαν και παρουσιάστηκαν στο πρώτο μέρος. Αρχικά, παρουσιάζεται το μοντέλο δυναμικής υδατοσήμανσης λογισμικού, το οποίο ονομάζουμε WaterRPG, και αναλύονται οι δομικές και λειτουργικές συνιστώσες του, και στη συνέχεια παρουσιάζεται ο αλγόριθμος ενσωμάτωσης Embed_RPG.to.CODE του υδατοσήματος στο κώδικα ενός προγράμματος P, προκύπτοντας έτσι το υδατοσημασμένο πρόγραμμα Pw, καθώς και ο αλγόριθμος εξαγωγής Extract_CODE.to.RPG του υδατοσήματος από τον κώδικα του προγράμματος Pw. Η βασική ιδέα του προτεινόμενου συστήματος υδατοσήμανσης βασίζεται στη συστηματική τροποποίηση κατάλληλων κλήσεων συναρτήσεων ενός προγράμματος P, χρησιμοποιώντας συνθήκες ελέγχου και αδιαφανή κατηγορήματα, έτσι ώστε η εκτέλεση του υδατοσημασμένου προγράμματος Pw με μια συγκεκριμένη είσοδο Ikey να επιστρέφει ένα δυναμικό γράφημα κλήσεων από το οποίο μπορεί εύκολα να κατασκευαστεί το γράφημα F[π*]. Το προτεινόμενο μοντέλο έχει υλοποιηθεί σε προγράμματα που έχουν αναπτυχθεί στη γλώσσα προγραμματισμού Java, και η υλοποίησή του εμπεριέχει δύο προσεγγίζεις: την naive και την stealthy προσέγγιση. Τέλος, το προτεινόμενο μοντέλο αξιολογήθηκε χρησιμοποιώντας διάφορα κριτήρια για την εκτίμηση της αποτελεσματικότητάς του.Στη συνέχεια, παρουσιάζουμε τεχνικές υδατοσήμανσης ψηφιακής εικόνας βασιζόμενες στο μετασχηματισμό ενός υδατοσήματος w ή, ισοδύναμα, μια αυτοαναστρέφουσα μετάθεση π* μήκους n* από αριθμητική μορφή σε δισδιάστατη (2Δ-αναπαράσταση) χρησιμοποιώντας τις ιδιότητες της αυτοαναστρέφουσας μετάθεσης π*. Η 2Δ-αναπαράσταση μιας αυτοαναστρέφουσας μετάθεσης μπορεί να ενσωματωθεί αποτελεσματικά σε μια ψηφιακή εικόνα, καθώς η εικόνα αποτελεί ένα διασδιάστατο αντικείμενο. Η βασική ιδέα των προτεινόμενων αλγορίθμων υδατοσήμανσης εικόνας έγκειται στην απεικόνιση της αυτοαναστρέφουσας μετάθεσης π* σε έναν n* x n* πίνακα A*, στη χρήση της πληροφορίας που είναι αποθηκευμένη σε συγκεκριμένες θέσεις του πίνακα A*, και στην τροποποίηση των αντίστοιχων περιοχών της ψηφιακής εικόνας I στο πεδίο των συχνοτήτων, παράγοντας έτσι την υδατοσημασμένη εικόνα Iw. Οι αλγόριθμοι ενσωμάτωσης και εξαγωγής του υδατοσήματος σε μια ψηφιακή εικόνα αξιολογήθηκαν πειραματικά σε ένα σύνολο ψηφιακών εικόνων τύπου JPEG, με διαφορετικά χαρακτηριστικά, διαφορετικά μεγέθη, και διαφορετικές αναλογίες, δίνοντας θετικά αποτελέσματα καθώς το υδατόσημα εξάγεται επιτυχώς ακόμη και στην περίπτωση που η εικόνα υφίσταται υψηλή συμπίεση.Έχοντας παρουσιάσει τις τεχνικές υδατοσήμανσης ψηφιακών εικόνων και καθότι ο ψηφιακός ήχος είναι ένα μονοδιάστατο σήμα, παρουσιάζουμε ένα μετασχηματισμό του υδατοσήματος w ή, ισοδύναμα, της αυτοαναστρέφουσας μετάθεσης π* μήκους n*, από την αριθμητική του μορφή στη 1Δ μορφή (1Δ-αναπαράσταση) και στη συνέχεια παρουσιάζουμε τον αλγόριθμο που ενσωματώνει το w στο ψηφιακό ήχο. Πιο συγκεκριμένα, οι προτεινόμενοι αλγόριθμοι ενσωματώνουν μια αυτοαναστρέφουσα μετάθεση π* μήκους n* σε ένα ηχητικό σήμα S, απεικονίζοντας τα στοιχεία του π* σε ένα μονοδιάστατο πίνακα B* μήκους n'=n* x n*, και στη συνέχεια με βάση τα στοιχεία του πίνακα B* τροποποιούμε το ηχητικό σήμα S στο πεδίο των συχνοτήτων, επιστρέφοντας τελικά το υδατοσημασμένο ηχητικό σήμα Sw. Ο αλγόριθμος εξαγωγής του υδατοσήματος βασίζεται στον εντοπισμό των σημείων στο Sw που έχουν τροποποιηθεί, γεγονός που μας δίνει τη δυνατότητα να ανακατασκευάσουμε την 1Δ-αναπαράσταση του π*, και επομένως να πάρουμε το υδατόσημα w.Βασιζόμενοι στις τρεις διαφορετικές αναπαραστάσεις μιας αυτοαναστρέφουσας μετάθεσης, δηλαδή την 1Δ-αναπαράσταση, τη 2Δ-αναπαράσταση, και την RPG-αναπαράσταση (ήτοι η κωδικοποίηση της μετάθεσης π* σε ένα αναγώγιμο μεταθετικό γράφημα F*[π*]), παρουσιάζουμε τους αλγορίθμους Embed_SiP.to.PDF-I, Embed_SiP.to.PDF-II, και Embed_RPG.to.PDF, αντίστοιχα, για την ενσωμάτωση ενός υδατοσήματος w (ή ισοδύναμα μιας αυτοαναστρέφουσας μετάθεσης π* ή ενός αναγώγιμου μεταθετικού γραφήματος F*[π*]) σε ένα ψηφιακό κείμενο T τύπου PDF. Οι αλγόριθμοι ενσωμάτωσης και εξαγωγής αξιολογήθηκαν πειραματικά σε διαφορετικά PDF αρχεία.Το κείμενο της διατριβής ολοκληρώνεται συνοψίζοντας τα ερευνητικά αποτελέσματά μας, προτείνοντας μελλοντικές επεκτάσεις, καθώς και ανοιχτά ερευνητικά προβλήματα στην περιοχή της ψηφιακής υδατοσήμανσης και γενικότερα στην περιοχή της απόκρυψης πληροφορίας.