Algorithmic techniques for encoding permutations and permutation graphs for watermarking software, image, audio, and text
Authors: Χρόνη Μαρία 
Published: September 2021

Στη σύγχρονη εποχή το διαδίκτυο αποτελεί αναπόσπαστο τεχνολογικό μέσο βοήθειας των δραστηριοτήτων της καθημερινής μας ζωής, καθώς χρησιμοποιείται για τη διεκπεραίωση σύνθετων, και συχνά χρονοβόρων, επαγγελματικών και καθημερινών εργασιών. Η συνεχής και συχνή χρήση του διαδικτύου, ο όγκος της ψηφιακής πληροφορίας που διακινείται μέσω αυτού, το εύρος της ηλικιακής διαστρωμάτωσης χρήσης του, και επιπλέον οι πολλαπλοί κίνδυνοι της προσωπικής ασφάλειας των χρηστών του, απαιτούν αυξημένα και τεχνολογικά ευφυή μέτρα προστασίας αυτού.Η ψηφιακή υδατοσήμανση (ή, υδατοσήμανση) είναι μια τεχνική για την προστασία της πνευματικής ιδιοκτησίας ενός ψηφιακού αντικειμένου. Η ιδέα είναι απλή: ένα μοναδικό αναγνωριστικό, το οποίο ονομάζεται υδατόσημα, ενσωματώνεται στο ψηφιακό αντικείμενο προκειμένου να χρησιμοποιηθεί για την απόδειξη της αυθεντικότητας ή αναγνώριση της ταυτότητας του ψηφιακού αντικειμένου από τους ιδιοκτήτες του. Ένα ψηφιακό αντικείμενο μπορεί να είναι ψηφιακός ήχος, εικόνα, κείμενο, ή λογισμικό, και το υδατόσημα ενσωματώνεται στο ψηφιακό αντικείμενο εισάγοντας σε αυτό τροποποιήσεις που δεν είναι ορατές και δεν γίνονται αντιληπτές. Για να είναι αποδοτική μια προτεινόμενη τεχνική υδατοσήμανσης, θα πρέπει να ενσωματώνει αποτελεσματικά το υδατόσημα στα ψηφιακά δεδομένα του αντικειμένου και να το εξάγει επιτυχώς, ακόμη και αν το αντικείμενο αυτό έχει υποστεί τροποποιήσεις, δηλαδή έχει δεχθεί επιθέσεις από κακόβουλους χρήστες με σκοπό την μη-εφικτή ή ανεπιτυχή εξαγωγή του υδατόσημου.Η παρούσα διδακτορική διατριβή πραγματεύεται θέματα σχετικά με την σχεδίαση αποτελεσματικών και εύκολα υλοποιήσιμων συστημάτων κωδικοποίησης για την υδατοσήμανση λογισμικού και ψηφιακών μέσων, όπως είναι η εικόνα, ο ήχος, και το κείμενο. Στα έως σήμερα ερευνητικά αποτελέσματα ψηφιακής υδατοσήμανσης, κάθε προτεινόμενη τεχνική κωδικοποίησης και ενσωμάτωσης εφαρμόζεται συνήθως σε ένα συγκεκριμένο είδος ψηφιακού αντικειμένου 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 αρχεία.Το κείμενο της διατριβής ολοκληρώνεται συνοψίζοντας τα ερευνητικά αποτελέσματά μας, προτείνοντας μελλοντικές επεκτάσεις, καθώς και ανοιχτά ερευνητικά προβλήματα στην περιοχή της ψηφιακής υδατοσήμανσης και γενικότερα στην περιοχή της απόκρυψης πληροφορίας.