Tài liệu Nghiên cứu và phát triển kỹ thuật thủy vân cơ sở dữ liệu quan hệ

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN LƯU THỊ BÍCH HƯƠNG NGHIÊN CỨU VÀ PHÁT TRIỂN KỸ THUẬT THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN LƯU THỊ BÍCH HƯƠNG NGHIÊN CỨU VÀ PHÁT TRIỂN KỸ THUẬT THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH VÀ HỆ THỐNG TÍNH TOÁN Mã số: 62.46.35.01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Bùi Thế Hồng HÀ NỘI – 2014 LỜI CẢM ƠN Để hoàn thành luận án này, tôi đã nhận được sự giúp đỡ rất tận tình các Thầy, Cô giáo trong Viện Công nghệ thông tin - Viện Hàn Lâm Khoa học và Công nghệ Việt Nam và trường ĐHSP Hà Nội 2. Tôi xin gửi lời cảm ơn các Thầy, Cô giáo trong Viện Công nghệ thông tin và trường ĐHSP Hà Nội 2 đã tạo điều kiện học tập, nghiên cứu, giúp đỡ tôi rất nhiều trong quá trình làm luận án. Đặc biệt tôi xin cảm ơn PGS.TS. Bùi Thế Hồng đã tận tình hướng dẫn chỉ bảo cho tôi trong toàn bộ quá trình học tập, nghiên cứu đề tài và giúp tôi hoàn thành bản luận án này. Hà Nội, ngày tháng năm 2014 Nghiên cứu sinh Lưu Thị Bích Hương i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn khoa học của PGS.TS. Bùi Thế Hồng. Các kết quả được viết chung với các đồng tác giả đã được sự chấp thuận của các tác giả trước khi đưa vào luận án. Các số liệu, kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả luận án Lưu Thị Bích Hương ii MỤC LỤC LỜI CẢM ƠN ...................................................................................................ii LỜI CAM ĐOAN .............................................................................................ii MỤC LỤC ........................................................................................................iii Bảng các ký hiệu, chữ viết tắt ........................................................................... v Danh sách bảng ...............................................................................................vii Danh sách hình vẽ ..........................................................................................viii MỞ ĐẦU ........................................................................................................... 1 Chương 1. THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ ................................... 9 1.1. Các khái niệm về cơ sở dữ liệu ........................................................... 9 1.1.1. Cơ sở dữ liệu................................................................................. 9 1.1.2. Mô hình dữ liệu quan hệ ............................................................... 9 1.1.3. Thuộc tính, miền thuộc tính và kiểu thuộc tính.......................... 10 1.1.4. Quan hệ, lược đồ quan hệ ........................................................... 10 1.1.5. Khoá của quan hệ ....................................................................... 11 1.2. Một số khái niệm về thủy vân cơ sở dữ liệu quan hệ ........................ 12 1.2.1. Thủy vân ..................................................................................... 12 1.2.2. Thủy vân cơ sở dữ liệu quan hệ.................................................. 12 1.2.3. Khóa thủy vân............................................................................. 13 1.2.4. Lược đồ thủy vân ........................................................................ 14 1.2.5. Sự cần thiết của các kỹ thuật thủy vân cơ sở dữ liệu quan hệ.... 15 1.3. Các yêu cầu của thủy vân trên cơ sở dữ liệu quan hệ ....................... 17 1.3.1. Khả năng có thể phát hiện .......................................................... 17 1.3.2. Tính bền vững và dễ vỡ .............................................................. 18 1.3.3. Khả năng cập nhật dữ liệu .......................................................... 18 1.3.4. Tính ẩn và hiện ........................................................................... 18 1.3.5. Phát hiện mù ............................................................................... 19 1.4. Ứng dụng của thủy vân cơ sở dữ liệu quan hệ .................................. 19 1.4.1. Bảo vệ bản quyền ....................................................................... 19 1.4.2. Đảm bảo sự toàn vẹn .................................................................. 20 1.4.3. Giấu vân tay ................................................................................ 21 1.5. Những tấn công trên thủy vân cơ sở dữ liệu quan hệ........................ 21 1.5.1. Cập nhật thông thường ............................................................... 21 1.5.2. Tấn công có chủ đích .................................................................. 22 1.6. Các lược đồ thủy vân cơ sở dữ liệu quan hệ ..................................... 23 1.6.1. Bảo vệ bản quyền cơ sở dữ liệu quan hệ .................................... 23 1.6.2. Đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ ........................ 27 1.7. Kết luận chương 1 ............................................................................. 30 Chương 2. PHÁT TRIỂN LƯỢC ĐỒ THỦY VÂN BẢO VỆ BẢN QUYỀN CHO CƠ SỞ DỮ LIỆU QUAN HỆ................................................................ 31 2.1. Xây dựng lược đồ thủy vân dựa vào việc chèn thêm ảnh nhị phân .. 31 2.1.1. Xây dựng lược đồ thủy vân ........................................................ 33 iii 2.1.2. Đánh giá độ phức tạp .................................................................. 36 2.1.3. Chứng minh tính đúng đắn ......................................................... 36 2.1.4. Đánh giá thử nghiệm .................................................................. 38 2.1.5. Kết luận....................................................................................... 40 2.2. Phát triển lược đồ thủy vân dựa vào bit ý nghĩa nhất (MSB) ........... 40 2.2.1. Cải tiến lược đồ thủy vân ........................................................... 42 2.2.2. Tính bền vững và chi phí về thời gian và bộ nhớ ....................... 46 2.2.3. Đánh giá thử nghiệm .................................................................. 48 2.2.4. Kết luận....................................................................................... 50 2.3. Kết luận chương 2 ............................................................................. 50 Chương 3. XÂY DỰNG LƯỢC ĐỒ THỦY VÂN ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ ...................................................... 51 3.1. Phân nhóm quan hệ ........................................................................... 51 3.2. Phát triển lược đồ thủy vân với thuộc tính phân loại ........................ 53 3.2.1. Cải tiến lược đồ thủy vân ........................................................... 54 3.2.2. Đánh giá độ phức tạp .................................................................. 58 3.2.3. Chứng minh tính đúng đắn ......................................................... 58 3.2.4. Cân đối giữa số bộ trong quan hệ và số nhóm ........................... 60 3.2.5. Đánh giá thử nghiệm .................................................................. 63 3.2.6. Kết luận....................................................................................... 65 3.3. Thủy vân với dữ liệu kiểu số ............................................................. 66 3.3.1. Lược đồ thủy vân ........................................................................ 66 3.3.2. Khoanh vùng các giả mạo .......................................................... 69 3.3.3. Khôi phục dữ liệu gốc ................................................................ 69 3.3.4. Chứng minh tính đúng đắn của thuật toán khôi phục ................ 71 3.3.5. Kết luận....................................................................................... 73 3.4. Xây dựng lược đồ thủy vân với dữ liệu kiểu văn bản ....................... 73 3.4.1. Một số định nghĩa ....................................................................... 73 3.4.2. Tư tưởng ..................................................................................... 74 3.4.3. Xây dựng lược đồ thủy vân ........................................................ 75 3.4.4. Phân tích tính đúng đắn .............................................................. 81 3.4.5. Đề xuất lược đồ thủy vân để khoanh vùng giả mạo ................... 84 3.4.6. Đánh giá thử nghiệm .................................................................. 88 3.4.7. Kết luận....................................................................................... 88 3.5. Kết luận chương 3 ............................................................................. 89 Kết luận và hướng phát triển ........................................................................... 90 Danh mục các công trình của tác giả .............................................................. 91 Tài liệu tham khảo ........................................................................................... 92 iv Bảng các ký hiệu, chữ viết tắt Ký hiệu Ý nghĩa của ký hiệu R Lược đồ quan hệ r Quan hệ thuộc lược đồ R  Số thuộc tính của quan hệ  Số bộ của quan hệ g Số nhóm của quan hệ ri Bộ thứ i trong quan hệ r ri.Aj Giá trị thuộc tính thứ j của bộ thứ i K Khóa thủy vân Gk Nhóm thứ k qk Số bộ trong nhóm Gk P Thuộc tính khóa chính của quan hệ Aw Thuộc tính kiểu văn bản có thể chứa nhiều từ Hi Thuộc tính kiểu văn bản có tác động cao thứ i Li Thuộc tính kiểu văn bản có tác động thấp thứ i H(Kri.A1ri.A2 ….ri.A Giá trị băm khóa K cùng với các giá trị thuộc tính của bộ ri rw Quan hệ thuỷ vân được tạo ra trong quá trình thuỷ vân  Tham số tạo thủy vân  Tham số phát hiện thủy vân W1j W2i W*1j W*2i V 1j Thủy vân được nhúng vào thuộc tính thứ j của tất cả các bộ trong một nhóm (thủy vân thuộc tính/cột) Thủy vân được nhúng vào tất cả các thuộc tính của bộ thứ i trong một nhóm (thủy vân bộ/dòng) Thủy vân được trích từ thuộc tính thứ j của tất cả các bộ trong một nhóm đã thủy vân Thủy vân được trích từ tất cả các thuộc tính của bộ thứ i trong một nhóm đã thủy vân Kết quả xác nhận thủy vân đối với W1j v V 2i Kết quả xác nhận thủy vân đối với W 2i n Số thuộc tính kiểu văn bản có tác động thấp trong quan hệ m Số thuộc tính kiểu văn bản có tác động cao trong quan hệ ei Giá trị thứ i trên đường chéo chính của ma trận thủy vân Wj Ký tự thủy vân thứ j ATOC() Converter() Substring(x,p,q) tH tmod tif Hàm chuyển mã Unicode thành ký tự Hàm chuyển từ dạng số sang dạng nhị phân Hàm lấy ra q ký tự của x từ vị trí thứ p Chi phí sinh một số ngẫu nhiên của hàm băm Chi phí của phép mod Chi phí của phép if tdelA Chi phí cho phép xóa một thuộc tính tbit Chi phí cho việc gán/so sánh một bit tcount Chi phí gán/cập nhật một con đếm tsort Chi phí cho việc đổi chỗ hai bộ mcount Số bit cần thiết để ghi một con đếm mtuple Số bit để ghi một bản sao của một bộ mwkey Số bit ghi khóa thủy vân mpkey Số bit ghi giá trị khóa chính LSB Bit ít ý nghĩa nhất (Least Significant Bit) MSB Bit ý nghĩa nhất (Most Significant Bit) MAC Mã chứng thực thông điệp (Message Authentication Code) CA MD5 Cơ quan đăng ký bản quyền (Certificate Authority) Thuật toán MD5 (Message Digest algorithm 5) vi Danh sách bảng Bảng 1.1. Biểu diễn quan hệ r...................................................................................11 Bảng 3.1. Tỷ lệ phát hiện đối với các tấn công trên một bộ giá trị ..........................64 Bảng 3.2. Kết quả thử nghiệm ..................................................................................88 vii Danh sách hình vẽ Hình 1. Phân loại các kỹ thuật giấu tin.......................................................................3 Hình 2. Thủy vân trên đồng dolla của Mỹ .................................................................4 Hình 1.1. Sơ đồ mô tả lược đồ thủy vân cơ sở dữ liệu quan hệ cơ bản....................15 Hình 2.1: (a) Ảnh nhị phân và giá trị thập phân tương ứng. (b) Thuộc tính văn bản sau khi được thủy vân, trong đó các chỉ số là số thứ tự các dấu cách đơn và DS là dấu cách đúp. .............................................................................................................32 Hình 2.2. Ảnh nhị phân sử dụng để thủy vân. (a) ảnh IOIT 12x4 (b) ảnh Smiley 8x8 ............................................................................................................................. 38 Hình 2.3. Kết quả tấn công thêm ..............................................................................39 Hình 2.4. Kết quả tấn công xóa ................................................................................39 Hình 2.5. Kết quả tấn công thay đổi dữ liệu .............................................................40 Hình 2.6. Tấn công thêm bộ đối với  ......................................................................48 Hình 2.7. Tấn công sửa bộ đối với  ........................................................................49 Hình 2.8. Tấn công xóa bộ đối với  ........................................................................49 Hình 3.1. Tỷ lệ phát hiện đối với các tấn công thêm nhiều bộ.................................64 Hình 3.2. Tỷ lệ phát hiện đối với các tấn công xóa nhiều bộ ...................................65 Hình 3.3. Tỷ lệ phát hiện đối với các tấn công sửa nhiều bộ ...................................65 viii MỞ ĐẦU 1. Tính cấp thiết của đề tài Cơ sở dữ liệu là một trong những lĩnh vực được tập trung nghiên cứu và phát triển của CNTT nhằm giải quyết các bài toán quản lý, tìm kiếm thông tin trong những hệ thống lớn, đa dạng, phức tạp cho nhiều người sử dụng trên máy tính điện tử. Cùng với sự ứng dụng mạnh mẽ CNTT vào đời sống xã hội, kinh tế, quốc phòng, … việc nghiên cứu cơ sở dữ liệu đã và đang ngày càng phát triển phong phú và đa dạng. Năm 1970, E.F. Codd đã đề xuất ra mô hình dữ liệu quan hệ với cấu trúc hoàn chỉnh đã tạo nên cơ sở toán học cho các vấn đề nghiên cứu cơ sở dữ liệu. Cuộc cách mạng thông tin dữ liệu số đã đem lại những thay đổi sâu sắc trong xã hội và trong cuộc sống. Những thuận lợi thông tin dữ liệu số mang lại cũng đề ra những thách thức và cơ hội mới cho quá trình đổi mới. Sự ra đời những phần mềm có tính năng mạnh, các thiết bị mới như máy ảnh kỹ thuật số, máy quét chất lượng cao, máy in, máy ghi âm kỹ thuật số, …, đã với tới thế giới tiêu dùng rộng lớn để sáng tạo, xử lý và thưởng thức các dữ liệu số. Mạng Internet toàn cầu đã biến thành một xã hội ảo nơi diễn ra quá trình trao đổi thông tin trong mọi lĩnh vực chính trị, quân sự, quốc phòng, kinh tế, thương mại… Và chính trong môi trường mở và tiện nghi như thế xuất hiện những vấn nạn, tiêu cực đang rất cần đến các giải pháp hữu hiệu cho vấn đề an toàn thông tin như nạn ăn cắp bản quyền, nạn xuyên tạc thông tin, truy nhập thông tin trái phép... Trong bối cảnh như vậy, việc thực thi quyền sở hữu dữ liệu và đảm bảo sự toàn vẹn dữ liệu là một yêu cầu quan trọng đòi hỏi các giải pháp đồng bộ, bao gồm các khía cạnh về kỹ thuật, về tổ chức và cả luật pháp. Đi tìm giải pháp cho những vấn đề này không chỉ giúp ta hiểu thêm về công nghệ phức tạp đang phát triển rất nhanh này mà còn đưa ra những cơ hội kinh tế mới cần khám phá. Một trong các giải pháp nhiều triển vọng là giấu tin, được nghiên cứu phát triển trong thời gian gần đây. Để hiểu rõ về nguồn gốc của thuỷ vân, trước tiên chúng ta tìm hiểu phương pháp giấu thông tin, thuỷ vân là một thành phần của phương pháp giấu tin. 1 Giấu tin là kỹ thuật nhúng một lượng thông tin số nào đó vào trong một đối tượng dữ liệu số khác. Một trong những yêu cầu cơ bản của giấu tin là đảm bảo tính chất ẩn của thông tin được giấu đồng thời không làm ảnh hưởng đến chất lượng của dữ liệu gốc. Do kỹ thuật giấu tin mới được hình thành trong thời gian gần đây nên những nhu cầu liên quan đến vấn đề giấu tin vẫn chưa được giải quyết một cách triệt để. Nhiều phương pháp mới, theo nhiều khía cạnh khác nhau đã và đang được tiến hành nghiên cứu, đề xuất. Chính vì vậy, sự phân loại các kỹ thuật là thực sự cần thiết. Dựa trên việc thống kê sắp xếp các công trình đã công bố trên một số tạp chí, cùng với thông tin về tên và tóm tắt nội dung của các công trình đã công bố trên Internet, có thể chia lĩnh vực giấu tin ra làm hai hướng lớn, đó là giấu tin bí mật và thủy vân. Nếu như thủy vân liên quan đến ứng dụng giấu các mẩu tin ngắn nhưng đòi hỏi độ bền vững lớn của thông tin cần giấu (trước các biến đổi thông thường của dữ liệu) thì giấu tin bí mật lại liên quan tới ứng dụng che giấu các bản tin đòi hỏi độ bí mật và dung lượng càng lớn càng tốt. Đối với từng hướng lớn này, quá trình phân loại theo các tiêu chí khác có thể tiếp tục được thực hiện, ví dụ dựa theo ảnh hưởng các tác động từ bên ngoài có thể chia thuỷ vân thành hai loại, một loại bền vững với các tác động sao chép trái phép, loại thứ hai lại cần tính chất hoàn toàn đối lập dễ bị phá huỷ trước các tác động nói trên. Cũng có thể chia thuỷ vân theo đặc tính, một loại cần được che giấu để chỉ có một số người tiếp xúc với nó có thể thấy được thông tin, loại thứ hai đối lập, cần được mọi người nhìn thấy. Năm 1999, sau hội nghị quốc tế lần thứ hai về giấu tin năm 1998, Petitcolas F.A. P. đưa ra tổng quan về giấu tin và đã được chấp nhận rộng rãi trong giới nghiên cứu được mô tả chi tiết trong hình 1. Các thành tựu đạt được trong lĩnh vực nghiên cứu này đã bắt đầu được áp dụng hiệu quả cho mục đích bảo vệ bản quyền, chống sao chép, phân tán trái phép các sản phẩm trong môi trường số hoá và nhiều mục đích khác. Nhiều phương pháp giấu tin khác nhau đã được đề xuất, mỗi phương pháp có những ưu điểm, nhược điểm riêng và thích hợp cho một nhóm ứng dụng nào đó. 2 Giấu tin là một công nghệ mới, phức tạp đang được tập trung nghiên cứu ở nhiều nước trên thế giới như Đức, Mỹ, Ý, Canada, Nhật Bản,… Tuy nhiên, các kết quả đã đạt được vẫn chưa giải quyết được hết những yêu cầu đặt ra của thực tế. Công việc hiện nay của các nhà khoa học là tập trung giải quyết các vấn đề mới được đặt ra và hệ thống lí thuyết chính xác cho vấn đề giấu tin. Một trong những vấn đề của giấu tin đang được các nhà khoa học quan tâm đến là thủy vân. Information hiding Giấu tin watermarking Thuỷ vân số steganography Giấu tin mật Intrinsic Giấu tin có xử lý Pure Giấu tin đơn thuần Imperceptible Watermarking Thuỷ vân ẩn Robust Copyright marking Thuỷ vân bền vững Visible Watermarking Thuỷ vân hiện Fragile Watermarking Thuỷ vân dễ vỡ Imperceptible Watermarking Thuỷ vân ẩn Visible Watermarking Thuỷ vân hiện Hình 1. Phân loại các kỹ thuật giấu tin Khái niệm thủy vân đã ra đời từ lâu. Năm 1282, thủy vân đã được các công nhân nhà máy giấy sử dụng ở Italia. Các tờ giấy sẽ mỏng hơn và có hoa văn trên đó. Điều này giúp các xưởng sản xuất giấy đánh dấu bản quyền trên tờ giấy của họ làm ra. Đến thế kỷ 18, thủy vân đã có nhiều ứng dụng ở châu Âu và Mỹ trong việc xác thực bản quyền hay chống tiền giả. Thuật ngữ thủy vân bắt nguồn từ một loại mực vô hình và chỉ hiện lên khi nhúng vào nước. Hình 2 là một ví dụ về thủy vân. Thủy vân số được coi là ra đời từ năm 1954 với bằng sáng chế của Emile Hembrooke. Tuy nhiên, nghiên cứu thủy vân vẫn chưa được đặt ra như một lĩnh vực nghiên cứu độc lập cho tới những năm 1980 và khái niệm thủy vân chỉ được hoàn thiện vào giữa những năm 90 của thế kỷ 20. Năm 1990, Tanaka, Tirkel A.Z., Rankin G.A., Schyndel R.G.van, Ho W.J., Mee N.R.A và năm 1993 Osborne C.F. lần lượt đưa ra những đề xuất đầu tiên về thủy vân số. Đến năm 1995, Caronni G. tiếp tục đề xuất về vấn đề bảo vệ bản 3 quyền cho ảnh số bằng thủy vân, khi đó chủ đề này mới bắt đầu được quan tâm và từ đó nhúng thủy vân số đã phát triển tốc độ nhanh với nhiều hướng nghiên cứu và phương pháp thực hiện khác nhau. Nhúng thủy vân được ứng dụng trong nhiều lĩnh vực như bảo vệ quyền sở hữu, đảm bảo sự toàn vẹn dữ liệu, điều khiển việc sao chép, xác nhận giấy tờ, hay truyền đạt thông tin khác, … trong đó ứng dụng phổ biến là cung cấp bằng chứng về bản quyền tác giả của các dữ liệu số bằng cách nhúng các thông tin bản quyền và đảm bảo sự toàn vẹn dữ liệu. Hình 2. Thủy vân trên đồng dolla của Mỹ Agrawal và Kiernan (2002) [7] đưa ra những đề xuất đầu tiên về kỹ thuật thủy vân trên cơ sở dữ liệu quan hệ bởi nhu cầu cấp thiết của người chủ dữ liệu đó muốn bảo vệ chúng trước những tấn công bên ngoài. Các tác giả đã đề xuất một lược đồ thủy vân trong đó dữ liệu có thể chấp nhận những thay đổi nhỏ mà không ảnh hưởng đến giá trị sử dụng của chúng. Cho đến nay, mới có một vài cách tiếp cận đối với bài toán thuỷ vân cơ sở dữ liệu quan hệ được đề xuất. Có thể tiếp cận các bài toán thủy vân dựa theo các tiêu chí khác nhau như sau: - Thông tin thủy vân: Là dữ liệu (ví dụ như hình ảnh, văn bản,...) được nhúng vào trong các lược đồ thủy vân [10], [24]. - Thay đổi giá trị của dữ liệu: Lược đồ thủy vân có thể làm thay đổi giá trị của dữ liệu [7], [16], [25] hoặc không thay đổi giá trị của dữ liệu [7], [35], [46]. - Kiểu dữ liệu: Lược đồ thủy vân được phân loại dựa trên các kiểu dữ liệu [7], [10], [32]. 4 - Phát hiện – Xác minh: Quá trình phát hiện - xác minh được thực hiện một cách mù (blind) hay không mù, nó có thể được thực hiện công khai (bởi bất cứ ai) hoặc bí mật (chỉ có chủ sở hữu) [34], [35]. - Mục đích của thủy vân: Các lược đồ thủy vân khác nhau được thiết kế để phục vụ cho các mục đích khác nhau, cụ thể là: bảo vệ bản quyền, đảm bảo sự toàn vẹn hay phát hiện giả mạo [12], [35], khoanh vùng, chứng minh quyền sở hữu, phát hiện kẻ phản bội… Đối với các lược đồ thủy vân dùng để bảo vệ bản quyền cho cơ sở dữ liệu quan hệ thông thường sẽ là thủy vân bền vững. Ngược lại, thủy vân dễ vỡ dùng để đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ. Luận án sẽ tập trung vào nghiên cứu và phát triển các kỹ thuật thủy vân cơ sở dữ liệu quan hệ theo hướng phục vụ cho mục đích bảo vệ bản quyền và đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ. Nói chung, các kỹ thuật thuỷ vân ngay từ khi mới ra đời đã nhận được sự quan tâm rất lớn của các nhà khoa học. Các kỹ thuật thuỷ vân đã được nghiên cứu và áp dụng trong nhiều môi trường dữ liệu khác nhau như: dữ liệu đa phương tiện (image, text, audio, video, . . .), các sản phẩm phần mềm. Trong các môi trường dữ liệu đó thì dữ liệu đa phương tiện (đặc biệt là image) được nghiên cứu và áp dụng sớm nhất và là môi trường chiếm tỷ lệ chủ yếu. Tuy nhiên, vấn đề thuỷ vân dữ liệu quan hệ chưa được sự chú ý nghiên cứu. Do cơ sở dữ liệu quan hệ có nhiều ngữ cảnh ứng dụng trong đó dữ liệu trở nên một tài sản quan trọng, vì vậy vấn đề về quyền sở hữu và đảm bảo sự toàn vẹn dữ liệu phải được thực thi một cách cẩn thận. Ví dụ dữ liệu về thời tiết, dữ liệu về thị trường chứng khoán, dữ liệu về hành vi của khách hàng, dữ liệu về điều tra dân số, dữ liệu y học và khoa học. Việc nhúng thuỷ vân vào dữ liệu quan hệ có thể thực hiện được bởi trong thực tế, các dữ liệu thật có thể chấp nhận một dung sai nhỏ mà vẫn không ảnh hưởng đáng kể đến giá trị sử dụng của chúng. Cho dù có khá nhiều các kết quả đã đạt được về thủy vân dữ liệu đa phương tiện, nhưng cho đến nay vẫn còn rất nhiều thách thức kỹ thuật mới đối với lĩnh vực thủy vân các cơ sở dữ liệu quan hệ bởi vì các dữ liệu quan hệ và các dữ liệu đa phương tiện khác nhau ở khá nhiều khía cạnh quan trọng. Chẳng hạn như, các phần khác nhau của một đối tượng đa phương tiện không thể cắt bỏ hoặc thay thế 5 một cách tùy ý mà không gây ra những thay đổi trong đối tượng. Ngược lại, việc thêm, bớt và cập nhật các bộ của một bảng quan hệ lại là những phép toán chuẩn trong cơ sở dữ liệu. Do những khác nhau này mà các kỹ thuật được phát triển cho các dữ liệu đa phương tiện không thể được sử dụng trực tiếp để thủy vân các quan hệ. Bảo vệ bản quyền, xác thực thông tin, nhận dạng các đặc trưng duy nhất của dữ liệu quan hệ hiện đang là một nhu cầu cấp thiết và là thách thức mới đối với các kỹ thuật thuỷ vân trên cơ sở dữ liệu quan hệ. Việc quản lý bản quyền và đảm bảo sự toàn vẹn các dữ liệu quan hệ bằng thuỷ vân đã và đang trở thành một chủ đề quan trọng trong các nghiên cứu về cơ sở dữ liệu. Thủy vân cơ sở dữ liệu quan hệ đang nhận được nhiều sự quan tâm cũng như nghiên cứu của các chuyên gia trên thế giới và trong nước. Cho đến nay, các nhà khoa học ở Việt Nam đã có một số công trình đã được công bố có áp dụng kỹ thuật thuỷ vân, trong đó chủ yếu tập trung vào dữ liệu đa phương tiện, nhiều nhất là thủy vân ảnh [2], [4], [5], [6]. Những năm gần đây, xu hướng nghiên cứu về thủy vân cơ sở dữ liệu quan hệ mới thực sự được các nhà khoa học trong nước quan tâm. Trong đó, vấn đề bảo vệ bản quyền và đảm bảo sự toàn vẹn của cơ sở dữ liệu là những vấn đề được quan tâm nhiều hơn cả. Xuất phát từ thực tế trên, luận án lựa chọn đề tài “Nghiên cứu và phát triển kỹ thuật thủy vân cơ sở dữ liệu quan hệ”, nhằm nghiên cứu các kỹ thuật thủy vân đối với cơ sở dữ liệu quan hệ trong ứng dụng bảo vệ bản quyền và đảm bảo sự toàn vẹn dữ liệu. 2. Mục tiêu và phương pháp nghiên cứu của luận án Thủy vân cơ sở dữ liệu quan hệ có hai ứng dụng quan trọng nhất là bảo vệ bản quyền và đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ. Do mỗi kiểu dữ liệu của cơ sở dữ liệu quan hệ có những đặc điểm riêng, cho nên đòi hỏi khi thủy vân các kỹ thuật thủy vân phải phù hợp với những đặc điểm của dữ liệu được thủy vân. Xuất phát từ thực tế đó, mục tiêu nghiên cứu chính của luận án là nghiên cứu, phát triển và xây dựng các kỹ thuật thủy vân trong ứng dụng bảo vệ bản quyền cơ sở dữ liệu quan hệ và đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ. 6 Trên cơ sở nghiên cứu sự cần thiết của các bài toán thủy vân cơ sở dữ liệu quan hệ và mục tiêu nghiên cứu chính của luận án, phương pháp nghiên cứu của luận án được xác định là: - Tìm kiếm và nghiên cứu tài liệu liên quan, tiến hành phân tích, đánh giá và đưa ra những cải tiến, đề xuất. - Phát triển các kết quả nghiên cứu về mặt lý thuyết, trên cơ sở cài đặt thử nghiệm, đánh giá và đưa ra những phương pháp, kỹ thuật mới, cải tiến. - Trao đổi, thảo luận và báo cáo tại các hội thảo, hội nghị khoa học,… 3. Những đóng góp mới của luận án - Cải tiến và đánh giá thử nghiệm đối với các lược đồ thủy vân trong ứng dụng bảo vệ bản quyền, bao gồm: Thủy vân dựa vào việc chèn thêm ảnh nhị phân; Thủy vân dựa vào bit ý nghĩa nhất (MSB). - Chứng minh tính đúng đắn của cách chia nhóm quan hệ dựa vào khóa thủy vân và khóa chính của bộ trong các thuật toán nhúng và thuật toán phát hiện của các lược đồ thủy vân dùng để đảm bảo sự toàn vẹn dữ liệu. - Lược đồ thủy vân cải tiến với thuộc tính phân loại đảm bảo sự toàn vẹn dữ liệu. Chứng minh tính đúng đắn của lược đồ thủy vân cải tiến. Cân đối số bộ trong quan hệ và số nhóm để tăng tính bền vững của thủy vân và tối đa số các bộ có thể tiếp tục được sử dụng. - Đề xuất lược đồ thủy vân với dữ liệu kiểu văn bản. Chứng minh tính đúng đắn của lược đồ thủy vân đề xuất. Phát triển tiếp lược đồ thủy vân này, luận án xây dựng lược đồ thủy vân có thể khoanh vùng các giả mạo và chứng minh tính đúng đắn của lược đồ. 4. Bố cục luận án Bố cục của luận án bao gồm: Phần mở đầu, ba chương nội dung, kết luận chung và tài liệu tham khảo. Chương 1. Tổng quát về cơ sở dữ liệu quan hệ và bài toán thủy vân cơ sở dữ liệu quan hệ, phân tích tình hình nghiên cứu về thủy vân cơ sở dữ liệu quan hệ trên thế giới. 7 Chương 2. Trình bày các kỹ thuật thủy vân cơ sở dữ liệu quan hệ trong ứng dụng bảo vệ bản quyền cho cơ sở dữ liệu quan hệ. Cải tiến và đánh giá thử nghiệm hai lược đồ thủy vân dùng trong bảo vệ bản quyền là thủy vân dựa vào việc chèn ảnh nhị phân và dựa vào bit ý nghĩa nhất. Chứng minh tính đúng đắn của các thuật toán trong lược đồ thủy vân dựa vào việc chèn thêm ảnh nhị phân. Chương 3. Cải tiến lược đồ thủy vân với thuộc tính phân loại, chứng minh tính đúng đắn của các thuật toán trong lược đồ thủy vân. Xây dựng hai lược đồ thủy vân với dữ liệu kiểu văn bản, đồng thời cũng chứng minh tính đúng đắn của các lược đồ thủy vân. Lược đồ đề xuất được dùng để phát hiện và khoanh vùng giả mạo nếu có. Các kết quả chính của Luận án được công bố trong các công trình khoa học (1)-(9). Các kết quả này cũng đã được trình bày tại các seminar Viện Công nghệ thông tin – Viện Hàn Lâm KH&CN Việt Nam, trường ĐHSP Hà Nội 2, Hội thảo quốc gia “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông” và Hội nghị quốc gia “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin – FAIR”. 8 Chương 1. THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ 1.1. Các khái niệm về cơ sở dữ liệu Mục này trình bày các khái niệm cơ bản nhất về mô hình dữ liệu quan hệ do E.F. Codd đề xuất [1], [51], [52]. 1.1.1. Cơ sở dữ liệu Định nghĩa 1.1: Cơ sở dữ liệu Cơ sở dữ liệu (database) là một hệ thống các thông tin có cấu trúc được lưu trữ trên các thiết bị lưu trữ thứ cấp (băng từ, đĩa từ…) nhằm thoả mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng hay nhiều chương trình ứng dụng với nhiều mục đích khác nhau. 1.1.2. Mô hình dữ liệu quan hệ Trong quá trình thiết kế và xây dựng các hệ quản trị cơ sở dữ liệu, người ta tiến hành xây dựng các mô hình dữ liệu. Mô hình dữ liệu phải được thể hiện được các mối quan hệ bản chất của các dữ liệu mà dữ liệu này phản ánh các mối quan hệ và các thực thể trong thế giới thực. Mô hình dữ liệu phản ánh khía cạnh cấu trúc logic mà không đi sâu vào khía cạnh vật lý của cơ sở dữ liệu. Mô hình dữ liệu là một sự hình thức hóa toán học với một tập ký hiệu để mô tả dữ liệu và một tập các phép toán được sử dụng để thao tác các dữ liệu này. Khi xây dựng các mô hình dữ liệu cần phân biệt các thành phần cơ bản sau: - Thực thể: Là đối tượng có trong thực tế mà chúng ta cần mô tả các đặc trưng của nó. - Thuộc tính: Là các dữ liệu thể hiện các đặc trưng của thực thể. - Ràng buộc: Là các mối quan hệ logic của các thực thể. Ba thành phần trên được thể hiện ở hai mức: - Mức loại dữ liệu: là sự khái quát hóa các ràng buộc, các thuộc tính, các thực thể cụ thể. - Mức thể hiện: Là một ràng buộc cụ thể, hoặc là các giá trị thuộc tính, hoặc là một thực thể cụ thể. Trên thực tế có một số mô hình dữ liệu đã được nghiên cứu: 9 - Mô hình dữ liệu mạng: Thể hiện trực tiếp các ràng buộc tùy ý giữa các loại bản ghi. Là mô hình dữ liệu được biểu diễn bởi một đồ thị có hướng. - Mô hình dữ liệu quan hệ: Các ràng buộc được thể hiện qua các quan hệ tức là bảng giá trị. Mô hình dựa trên lý thuyết tập hợp và đại số quan hệ. Vì tính chất chặt chẽ của toán học về lí thuyết tập hợp nên mô hình này đã mô tả dữ liệu một cách rõ ràng, uyển chuyển và trở thành rất thông dụng. - Mô hình dữ liệu hướng đối tượng: Cho phép biểu diễn dữ liệu tự nhiên và sát với thực tế hơn cả. Tuy nhiên cho đến nay, chưa có một cơ sở toán học tốt hình thức hóa ở mức cao, chặt chẽ đối với mô hình này. Mô hình dữ liệu quan hệ do E.F. Codd đề xuất năm 1970 là cơ sở cho hầu hết các hệ thống cơ sở dữ liệu hiện tại. Mô hình dữ liệu quan hệ được quan tâm là vì nó được xây dựng trên cơ sở toán học chặt chẽ. Mô hình dữ liệu quan hệ cung cấp các khái niệm chặt chẽ được hình thức hóa cao, cho phép áp dụng các cộng cụ toán học, các thuật toán tối ưu trên mô hình dữ liệu quan hệ. Mô hình dữ liệu quan hệ được trừu tượng hóa cao và chỉ dừng ở mức logic. 1.1.3. Thuộc tính, miền thuộc tính và kiểu thuộc tính Định nghĩa 1.2: Thuộc tính, miền giá trị của thuộc tính - Thuộc tính là đặc trưng của quan hệ. - Tập tất cả các giá trị có thể có của thuộc tính Ai gọi là miền giá trị của thuộc tính đó, ký hiệu: Dom(Ai) hay viết tắt là: D A i Ví dụ 1.1: Nhânviên(MaNV, Ten, NgSinh, Đchi) Dom(MaNV) = {char(5)}; Dom(Ten) = {char(10)}; Dom(NgSinh) = {date}; Dom(Đchi) = {‘HN’, ‘HP’, ‘VP’, …}. Mỗi một thuộc tính đều phải thuộc một kiểu dữ liệu. Kiểu dữ liệu có thể là vô hướng - là các kiểu dữ liệu cơ bản như chuỗi, số, logic, ngày tháng,… hoặc các kiểu có cấu trúc được định nghĩa dựa trên các kiểu dữ liệu đã có sẵn. 1.1.4. Quan hệ, lược đồ quan hệ Định nghĩa 1.3: Quan hệ Cho U = {A1, A2, …, A} là một tập hữu hạn không rỗng các thuộc tính. Mỗi thuộc tính Ai (i =1, 2, …, ) có miền giá trị là Dom(Ai). Khi đó r là một tập các bộ 10