臺灣博碩士論文加值系統

本論文主要探索數位浮水印技術應用於資料庫的保護上的成效，這樣的技術稱之為資料庫浮水印技術。數位浮水印技術是一種資訊隱藏技術, 它可分為兩個部分，一個是以保護資料版權為目的的強韌型浮水印技術，而另一個是以偵測完整性為目的的碎型浮水印技術。針對資料庫而言可以藉由這兩種浮水印技術來達到對資料庫內容的版權驗證或完整性驗證的目的。目前的資料庫浮水印的研究都需要更改表格內的資料值以達到嵌入浮水印的目的，然而，資料庫內的資料大多是敏感性的資料，一旦經過修改之後其所代表的意義將跟著被破壞。因此，本論文提出一個基於不破壞資料庫內的資料意義之原則即可達成保護目的的資料庫浮水印技術方法。這個方法利用找出每筆值組的特徵值後與一張數位浮水印影像內的像素值做個別的結合來達到嵌入強韌型浮水印目的，同時利用每筆值組的特徵做配對成組的法則並藉由比對以達成嵌入碎型浮水印的目的。實驗結果證明本方法除了具備驗證資料庫的擁有者之版權的功能外也具有偵測資料庫內的資料是否遭受到竄改的功能。
另一方面，本論文還提出兩個可逆式的資料庫浮水印技術來保護資料庫裡的資料。這兩個方法可以在取回浮水印的時候將因嵌入而遭受到修改的資料還原回原始資料，並透由取出來的浮水印來證明資料庫的所有權或驗證資料庫的完整性。第一個方法從每個屬性中擷取出特徵值並利用這些特徵值建立一棵四元樹以產生可逆式的浮水印嵌入技術。當使用者做完資料庫的驗證處理之後，除了可以藉由取出的資訊值還原浮水印以達版權所有的驗證功能外，還可以將資料庫裡的資料完整的恢復。實驗結果顯示本方法在不同機率的竄改攻擊與屬性欄位值被調換的攻擊之下仍可取出清晰的浮水印影像以證明版權所有。第二個方法利用了De-clustering分群的方法達成可逆式的浮水印技術。本方法從每一個屬性擷取的特徵值做分成四群，每一群各自代表著不同的浮水印資訊。之後利用每一屬性的特徵值與相對映的浮水印資訊的所屬群內的各個特徵值做差值比較，使用差值較小的特徵替換原始特徵值來達到嵌入浮水印的目的。使用者除了可以藉由取回的浮水印做完整性驗證的功能外，同時還可以將嵌入過浮水印的資料還原回原值。實驗結果顯示本方法除了可以藉由取出的浮水印驗證資料的完整性外，還在可以在取出驗證資訊後100%的還原資料庫裡的資料。

關鍵詞：數位浮水印技術、版權保護、資料庫浮水印、雙重浮水印技術、所有權驗證、完整性驗證、可逆式浮水印技術、De-Clustering Technique

This thesis focuses on digital watermarking and its applications in database protection. Digital watermarking is a kind of information hiding techniques, it can partition into two parts: one is robust watermarking for copyright protection, the other is fragile watermarking for tampering detection. Database watermarking is used to protect the database by embedding digital watermarks into the protected database. Hence digital watermarking can be used to achieve database ownership verification and tampering detection. In recent years, most existing database watermarking schemes altered the data of tables to embed watermarks. However, most data in a database are sensitive. When some data are modified, it would let the data become useless. Hence, how to embed watermark without modifying any data is very important. In this thesis, a database watermarking schemes is proposed that it embed watermark into databases without destroying any protected data’s meaning. This scheme extracts a feature from each tuple to combine with each pixel of a watermark image for embedding a robust watermark, and the features of each couple of t uples are compared to embed a fragile watermark by an embedding rule. The experimental results showed that the proposed scheme can not only copyright verification but also tampering detection, and have a significant achievement.
In addition, this thesis proposed two reversible watermarking schemes to protect database. These schemes can restore original data after extracting watermark and verify ownership or integrity according to extracting watermark. The first scheme is a robust reversible watermarking scheme by building quart-tree to embed a watermark. The first reversible watermarking scheme utilizes extracting features from every attributes to build quarter-tree. When user verified ownership according to the extracted watermark, the data in the database can restore its original value. The experimental results showed that the first reversible watermarking scheme can not only achieve copyright verification by extracting watermark under different alteration rate attacks and attribute out-of-order attacks but also restore original data after extracting watermark image. The second scheme is a fragile reversible watermarking by using de-clustering technique to embed a watermark. The second reversible watermarking scheme utilizes extracting features from every attribute to group four groups for representing watermark information. It utilizes features of every attributes to find the small least value from the corresponding watermark group and utilizes the fined value to change the original feature of the attribute for embedding watermark. When users verified database integrity according to the extracted watermark, the data can restore the original value in the same time. The experimental results showed that the second reversible watermarking scheme not only verifies integrity of database but also restores original data in 100% rate after extracting watermark.

Keywords: Digital watermarking, copyright protection, database watermarking, dual watermarking, ownership verification, integrity verification, reversible watermarking, de-clustering technique.

Contents
Abstract in Chinese I
Abstract in English Ⅲ
Acknowledgement Ⅴ
Contents Ⅵ
List of Tables Ⅸ
List of Figures Ⅹ
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Database Content Verification 3
1.3 Database Ownerships Protection 3
1.4 Thesis Organization 4
Chapter 2 Preliminaries 5
2.1 Robust Database Watermarking 5
2.2 Fragile Database Watermarking 6
2.3 Related Works 6
2.3.1 Robust Database Watermarking 6
2.3.1.1 Watermark Relational Database 6
2.3.1.2 Rights Protection for Categorical Data 8
2.3.1.3 Watermarking Relational Database Using Watermark Image 10
2.3.2 Fragile Database watermarking 12
2.3.2.1 A Fragile Watermarking Scheme for Detecting Malicious Modifications of Database Relations 12
2.3.2.2 Tamper Detection and Localization for Categorical Data Using
Fragile Watermarks 15
2.3.2.3 A Database Watermarking Technique for Temper Detection 17
2.4 De-Clustering Technique 19
Chapter 3 A Dual Database Watermarking Scheme for Malicious Tampering
Detection and Copyright Protection 21
3.1 The Proposed Scheme 21
3.1.1 Assumptions 21
3.1.2 Watermark Embedding 23
3.1.2.1 Fragile Watermark Embedding 23
3.1.2.2 Robust Watermark Embedding 24
3.1.2.3 Watermark Detection 26
3.2 Experimental Results 28
3.2.1 Emulation Experiments 28
3.2.2 Alteration Attacks 29
3.2.3 Attribute Cutting Attacks 34
3.3 Summary 34
Chapter 4 A Reversible Watermarking Scheme for Database Copyright
Protection 36
4.1 The Proposed Scheme 36
4.1.1 Assumptions 36
4.1.2 Embedding Procedure 37
4.1.2.1 Building The Reversible Quart-Tree 37
4.1.2.2 Embedding Procedure 40
4.1.3 Extracting Procedure 42
4.2 Experimental Results 43
4.2.1 Alternation Attacks 44
4.2.2 Attribute Out-of-Order Attacks 46
4.3 Comparisons and Discussions 47
4.4 Summary 52
Chapter 5 A Reversible Watermarking Scheme for Integrity Verification Using De-Clustering Technique 53
5.1 The Proposed Scheme 53
5.1.1 Assumptions 53
5.1.2 Embedding Procedure 54
5.1.2.1 Grouping Phase by De-Clustering 54
5.1.2.2 Embedding Phase 55
5.1.3 Extracting Procedure 60
5.2 Experimental Results 61
5.2.1 Alternation Attacks 62
5.2.2 Attribute Out-of-Order Attacks 63
5.3 Comparisons and Discussions 64
5.4 Summary 66
Chapter 6 Conclusions and Future Works 67
6.1 Conclusions 67
6.2 Future Works 68
Bibliography 70


List of Tables
Table 3.1 Notations 22
Table 4.1 Notations of Symbol Parameters 37
Table 5.1 The Important Parameters of The Notations 54
Table 5.2 Comparisons Between Guo et al.’s Scheme and The Proposed Scheme 66


List of Figures
Figure 2.1 The Relational Table 7
Figure 3.1 Gray-Lvel Watermark 31
Figure 3.2 Watermark Detection Rates under Different Percentage of Random Alternation Attacks 31
Figure 3.3 Watermark Detection Rates under Different Numbers of Tuples of Random Alternation Attacks 31
Figure 3.4 Watermark Lost Detection under Random Alteration Attacks 32
Figure 3.5 Watermark Detection under Random Alternation of 5% Tuples 32
Figure 3.6 Watermark Detection under Random Alternation of 0.05% Tuples 32
Figure 3.7 Watermark Detection under Random Alternation of 10% Tuples 33
Figure 3.8 Watermark Detection under Random Alternation of 30% Tuples 33
Figure 3.9 Watermark Detection under Random Alternation of 50% Tuples 33
Figure 3.10 Watermark Detection under Random Alternation of 90% Tuples 34
Figure 4.1 An Example of Frequency Talbe 38
Figure 4.2 A Reversiable Quart-Tree Constructed from Figure 4.1 39
Figure 4.3 The Experimental Results in Different Alternation Attacks 45
Figure 4.4 The Experimental Results in Huge Alteration Attacks 46
Figure 4.5 The Experiment Results in Different Attriubte Out-of-Order Attacks 47
Figure 4.6 Rose Watermark is Used in Comparison Experiment 49
Figure 4.7 The Comparison Experiment of Different Tampered Rates Between The Agrawal et al.’s Method and The Proposed Scheme 49
Figure 4.8 The Comparison Experiment of Various Attribute Out-of-Order attacks Between The Agrawal et al.’s Method and The Proposed Scheme 51
Figure 4.9 Recovery Data Rate under Various Random Alternation Attacks 51
Figure 5.1 An Example of The Grouped Result 54
Figure 5.2 The Experimental Result in Different Modification Ratio Attacks 63
Figure 5.3 The Experimental Result in Different Attribute Out-of-Order Attacks 63
Figure 5.4 Recovery Data Rate under Various Random Alternation Attacks 66

[1]R. Agrawal and J. Kiernan, "Watermark Relational Databases," in Proceedings of the 28th international conference on Very Large Data Base, Hong Kong, 2002, pp. 155-166.
[2]R. Agrawal, P.J. Hass, and J. Kiernan, "Watermarking Relational Data: Framework, Algorithms and Analysis, " The VLDB Journal, Vol. 12, No. 2, 2003, pp. 157-169.
[3]M. T. Fang, R. C. T. Lee, and C. C. Change, "The Idea of De-Clustering and Its Applications," in Proceedings of the 12th international conference on Very Large Data Base, Kyoto, 1986, pp. 181-188.
[4]G. Gautam and B. B Chaudhuri, "A Novel Genetic Algorithm for Automatic Clustering," Pattern Recognition Letters, Vol. 25, 2004, pp. 173-187.
[5]F. Guo, J. Wang, and Di Li, "Fingerprinting Relational Databases," in Proceedings of the 2006 ACM symposium on Applied computing table of contents, Dijon, April 2006,pp. 487 – 492.
[6]H. Guo, Y. Li, A. Liu, and S. Jajodia, "A Fragile Watermarking Scheme for Detecting Malicious Modifications of Database Relations," Information Sciences, Vol. 176, No. 10, May 2006, pp. 1350-1378.
[7]H. Guo, Y. Li, and S. Jajodia, "Chaining Watermarks for Detecting Malicious Modifications to Streaming Data,” Information Sciences, Vol. 177, No. 1, 1 January 2007, pp. 281-298.
[8]M. Huang, J. Cao, Z. Peng, and Y. Fang, "A New Watermark Mechanism for Relational Data," in Proceedings of the 4th International Conference on Computer and Information Technology, Shanghai , September 2004, pp. 946 – 950.
[9]L. Kaufman and P.J Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley and Sons, 1990.
[10]E. Lin and E. Delp, "A Review of Fragile Image Watermarks," in Proceedings of the Multimedia and Security Workshop (ACM Multimedia’99), October 30-Novermeber 5, 1999, pp. 25-29.
[11]Y. Li, H. Guo, and S. Jajodia, "Tamper Detection and Localization for Categorical Data Using Fragile Watermarks," in Proceedings of the 4th ACM Workshop on Digital Rights Management, Washington DC, 2004, pp. 73 – 82.
[12]Y. Li, V. Swarup, and S. Jajodia, "Fingerprinting Relational Databases: Schemes and Specialties, " IEEE Transactions on Dependable and Secure Computing, Vol. 2, No. 1, January- March 2005, pp. 34 – 45.
[13]Y. Li and R. H. Deng, "Publicly Verifiable Ownership Protection for Relational Databases, " in Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security Table of Contents, Taiwan, March 2006, pp. 78 – 89.
[14]Z. M. Lu, D. G. Xu, and S. H. Sun, "Multipurpose Image Watermarking Algorithm Based on Multistage Vector Quantization," IEEE Transactions Image Processing, Vol. 14, No. 6, June 2005, pp. 822-831.
[15]J. MacQueen, "Some Methods for Classification and Analysis of Multivariate Observations," in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, 1967, pp. 281-297.
[16]M. H. Tsai, H. Y. Tseng, and C. Y. Lai, "A Database Watermarking Technique for Temper Detection," in Proceedings of the 9th Joint Conference on Information Sciences, Kaohsiung, Taiwan, October 2006.
[17]R. Sion, M. Atallah, and S. Prabhakar, "Rights Protection for Relational Data," in Proceedings of ACM SIGMOD 2003, San Diego, 2003, pp. 98 – 109.
[18]R. Sion, M. Atallah, and S. Prabhakar, "Rights Protection for Categorical Data," IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 7, 2005, pp. 912-926.
[19]Z. H. Zhang, X. M. Jin, J. M. Wang, and D.Y. Li, "Watermarking Relational Database Using Image," in Proceedings of the 3rd International Conference on Machine Learning and Cybernetics, Beijing, 2004, pp. 1739- 1744.