Luận văn Thủy vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu hoá áp dụng thuật toán tìm kiếm theo mẫu

cách truyền thông  19  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tin mật cho nhau mà người khác không thể biết được bởi sau khi giấu thông tin chất lượng ảnh gần như không thay đổi đặc biệt đối với ảnh mầu hay ảnh xám. Ví dụ về vụ việc ngày 11-9 gây chấn động nước Mĩ và toàn thế giới, chính tên trùm khủng bố quốc tế Osma BinLaDen đã dùng cách thức giấu thông tin trong ảnh để liên lạc với đồng bọn, và hắn đã qua mặt được cục tình báo trung ương Mĩ CIA và các cơ quan an ninh quốc tế. Chắc chắn sau vụ việc này, việc nghiên cứu các vấn đề liên quan đến giấu thông tin trong ảnh sẽ rất được quan tâm. b. Giấu tin trong âm thanh(audio) Giấu thông tin trong âm thanh mang những đặc điểm riêng khác với giấu thông tin trong các đối tượng đa phương tiện 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. Để đảm bảo yêu cầu này, kỹ thuật giấu thông tin trong ảnh phụ thuộc vào hệ thống thị giác của con người - HVS còn kỹ thuật giấu thông tin trong âm thanh lại phụ thuộc vào hệ thống thính giác - HAS. Một vấn đề khó khăn là hệ thống thính giác của con người nghe được các tín hiệu ở các dải tần rộng và công suất lớn nên đã gây khó khăn đối với các phương pháp giấu tin trong âm thanh. Nhưng hệ thống thính giác của con người lại kém trong việc phát hiện sự khác biệt các dải tần và công suất, điều này có nghĩa là các âm thanh to, cao tần có thể che giấu được các âm thanh nhỏ thấp một cách dễ dàng. Các mô hình phân tích tâm lí đã chỉ ra điểm yếu trên và thông tin này sẽ giúp ích cho việc chọn các âm thanh thích hợp cho việc giấu tin. Vấn đề khó khăn thứ hai đối với giấu thông tin trong âm thanh là kênh truyền tin. Kênh truyền hay băng thông chậm sẽ ảnh hưởng đến chất lượng thông tin sau khi giấu. Ví dụ để nhúng  20  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên một đoạn java applet vào một đoạn âm thanh (16 bit, 44.100 Hz) có chiều dài bình thường thì các phương pháp nói chung cũng cần ít nhất là 20 bit/s. Giấu thông tin trong âm thanh đòi hỏi yêu cầu cao về tính đồng bộ và tính an toàn của thông tin. Các phương pháp giấu thông tin trong âm thanh đều lợi dụng điểm yếu trong hệ thống thính giác của con người. c. Giấu tin trong phim (video) Cũng giống như giấu thông tin trong ảnh hay trong âm thanh, giấu tin trong phim cũng được quan tâm và được phát triển mạnh mẽ cho nhiều ứng dụng như điều khiển truy cập thông tin, xác thực thông tin và bảo vệ bản quyền tác giả. Ví dụ các hệ thống chương trình trả tiền xem theo đoạn với các đoạn phim (pay per view application). Các kỹ thuật giấu tin trong phim cũng được phát triển mạnh mẽ và cũng theo hai khuynh hướng là thuỷ vân số và giấu thông tin. Nhưng phần này chỉ quan tâm tới các kỹ thuật giấu tin trong phim. Một phương pháp giấu tin trong phim được Cox đưa ra là phương pháp phân bố đều. Ý tưởng cơ bản của phương pháp là phân phối thông tin giấu dàn trải theo tần số của dữ liệu gốc. Nhiều nhà nghiên cứu đã dùng những hàm cosin riêng và các hệ số truyền sóng riêng để giấu tin. Trong các thuật toán đầu tiên thường các kỹ thuật cho phép giấu các ảnh vào trong phim nhưng thời gian gần đây các kỹ thuật cho phép giấu cả âm thanh và hình ảnh vào phim. Ví dụ Swanson đã sử dụng phương pháp giấu theo khối, phương pháp này đã giấu được hai bít vào khối 8*8. Hay gần đây nhất là phương pháp của Mukherjee là kỹ thuật giấu âm thanh vào phim sử dụng cấu trúc lưới đa chiều... Giấu tin là một công nghệ mới phức tạp, đang được các nhà khoa học tập trung nghiên cứu ở nhiều nước trên thế giới như Đức, Mỹ, ý, Canada,  21  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nhật Bản…Tuy nhiên, những kết quả thực nghiệm cho thấy để có thể ứng dụng thực tế thì lĩnh vực này cần phải có thêm thời gian để nghiên cứu thẩm định nhưng các nhà khoa học cũng khẳng định rằng đây là một công nghệ mới đầy hứa hẹn cho vấn đề an toàn và bảo mật thông tin. Công việc hiện nay của các nhà khoa học là đang tập trung xây dựng một hệ thống lí thuyết chính xác cho vấn đề giấu tin, đây là một mảnh đất mới cho các nhà khoa học khám phá. Một trong những kỹ thuật quan trọng của giấu tin đang được rất nhiều các nhà khoa học quan tâm và phát triển nhất, đó là kỹ thuật thuỷ vân (watermark). [3], [11], [12] 1.2. Cơ sở lý thuyết về thuỷ vân 1.2.1. Khái niệm thuỷ vân và nhúng thuỷ vân - Thuỷ vân là một tín hiệu bảo mật và không nhận biết, được nhúng vào dữ liệu gốc để truyền dữ liệu đã nhúng đi.[9] - Nhúng thủy vân (watermarking) là một trong những kỹ thuật giấu dữ liệu hiện đại, là quá trình chèn thông tin vào dữ liệu đa phương tiện nhưng bảo đảm không nhận biết được, nghĩa là chỉ làm thay đổi nhỏ dữ liệu gốc. Thông thường người ta chỉ đề cập đến nhúng thủy vân số. Một tập các dữ liệu số thứ cấp - gọi là mã đánh dấu bản quyền hay thủy vân (watermark), được nhúng vào dữ liệu số sơ cấp - gọi là dữ liệu bao phủ (ví dụ như văn bản, hình ảnh, âm thanh và phim số, ...). Dữ liệu sau quá trình nhúng được gọi là dữ liệu nhúng.[10], [12], [13] 1.2.2. Lịch sử phát triển của thuỷ vân Tanaka (1990), Caronni và Tirkel (1993) lần lượt đưa ra những ấn bản đầu tiên về nhúng thủy vân nhưng chưa nhận được sự quan tâm đúng mức.  22  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Đến năm 1995, 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, đ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. 1.2.3. Mô hình hệ thống tổng quát quá trình nhúng và khôi phục thuỷ vân Hình 1.4. Sơ đồ nhúng thuỷ vân Thuỷ vân Dữ liệu nhúng Dữ liệu bao phủ Mã cá nhân / công cộng Quyết định thuỷ vân Dữ liệu nhúng Thuỷ vân Mã cá nhân / công cộng  23  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 1.5. Sơ đồ khôi phục thuỷ vân Tất cả các phương pháp nhúng thủy vân đều có chung các khối sau: một hệ thống nhúng thủy vân và một hệ thống khôi phục thủy vân. [9], [10], [12], [13] Hình 1.4. trình bày quá trình nhúng thủy vân tổng quát. Đầu vào là thủy vân, dữ liệu cần nhúng và mã cá nhân hay công cộng. Thủy vân có thể ở bất kì dạng nào như chữ số, văn bản hay hình ảnh. Khoá có thể được dùng để tăng cường tính bảo mật, nghĩa là ngăn chặn những người không có bản quyền khôi phục hay phá hủy thủy vân. Các hệ thống thực tế dùng ít nhất là một khoá, thậm chí kết hợp nhiều khoá. Đầu ra là dữ liệu đã được nhúng thủy vân. Quá trình khôi phục thủy vân tổng quát được cho ở hình 1.5. Đầu vào là dữ liệu đã nhúng thủy vân, khoá và dữ liệu gốc (có thể có hoặc không tuỳ thuộc vào phương pháp). Đầu ra hoặc là thủy vân khôi phục được hoặc đại lượng nào đó chỉ ra mối tương quan giữa nó và thủy vân cho trước ở đầu vào. Phụ thuộc vào mục đích và ứng dụng mà các yêu cầu của hệ thống nhúng thủy vân được đặt ra. Với các hệ thống thực tế, chúng đòi hỏi các yêu cầu sau: − Tính không nhận biết: các điều chỉnh gây ra do nhúng thủy vân phải thấp hơn ngưỡng cảm thụ, nghĩa là các mẫu dùng trong nhúng thủy vân chỉ được phép thay đổi nhỏ. − Tính bền vững: đây là một yêu cầu nòng cốt của nhúng thủy vân. − Khôi phục thủy vân cần hoặc không cần dữ liệu gốc. − Trích thủy vân hay kiểm chứng sự tồn tại của thủy vân.  24  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên − Các khoá và bảo mật thủy vân. 1.2.4. Một số ứng dụng của thuỷ vân Một ứng dụng phổ biến của kỹ thuật thuỷ vân là đưa ra một bằng chứng về quyền sở hữu đối với dữ liệu số bằng cách nhúng dấu hiệu mang tính bản quyền vào phim hoặc các sản phẩm ảnh số. Ngoài ra, còn có những ứng dụng khác : - Tự động điều khiển và tự hiệu chỉnh sao chép tài liệu trên Web. Ví dụ một robot tìm web để đánh dấu vào tài liệu và từ đó nhận dạng sản phẩm bất hợp pháp. - Tự động kiểm tra việc truyền nhận sóng vô tuyến. Ví dụ một robot có thể “nghe” một trạm thu phát sóng radio và tìm kiếm những dấu hiệu để biểu thị một phần cụ thể của bản nhạc hoặc lời quảng cáo vừa được phát ra. - Việc mở rộng dữ liệu- để thêm thông tin mang lại lợi ích một cách công khai. - Ứng dụng trong lấy dấu vân tay (cho phép nhận dạng dữ liệu đã phân tán).  25  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chƣơng 2- THUỶ VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU 2.1. Giới thiệu về thuỷ vân cơ sở dữ liệu (database watermarking) Tốc độ phát triển nhanh của Internet và các công nghệ có liên quan đã đưa đến một tiềm năng chưa từng có đối với việc truy cập và phân phối lại các sản phẩm kỹ thuật số. Trong bối cảnh như vậy, việc thực thi quyền sở hữu 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. Mặc dù vẫn chưa có được những giải pháp toàn diện như vậy nhưng trong các năm gần đây, các kỹ thuật thuỷ vân đã đóng vai trò quyết định nhằm giải quyết vấn đề về quyền sở hữu này. Những kỹ thuật như vậy cho phép người chủ dữ liệu có thể nhúng một thuỷ vân ẩn vào dữ liệu. Một thuỷ vân thường mô tả những thông tin có thể được dùng để chứng minh quyền sở hữu dữ liệu, chẳng hạn như tên chủ sở hữu, nguồn gốc, hoặc người tiếp nhận nội dung này. Việc nhúng thông tin an toàn đòi hỏi thuỷ vân được nhúng trong dữ liệu không thể bị làm giả mạo hoặc bị tẩy xoá một cách dễ dàng. Nhúng ẩn có nghĩa là thuỷ vân không thể nhìn thấy được trong dữ liệu. Hơn nữa, việc phát hiện thuỷ vân được thực hiện theo phương pháp mù, tức là không đòi hỏi dữ liệu gốc cũng như thuỷ vân gốc. Đã có một số kỹ thuật thuỷ vân được phát triển để nhúng thủy vân phim, âm thanh, ảnh và dữ liệu văn bản.  26  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Trái lại, vấn đề thuỷ vân dữ liệu quan hệ đã không nhận được sự chú ý thích đáng. Tuy nhiên, 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 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 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 đế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 dữ liệu quan hệ được đề xuất. Tuy nhiên, những kỹ thuật này không bền vững đối với các tấn công thủy vân. Đề tài này trình bày một kỹ thuật thuỷ vân cơ sở dữ liệu quan hệ có độ bền vững cao so với các kỹ thuật khác. Kỹ thuật này bền vững đối với các tấn công xoá, sửa và chèn các bản ghi. [1], [2], [8],[9]  27  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.2. Mô hình chi tiết hệ thống thuỷ vân cơ sở dữ liệu Kỹ thuật tối ưu gồm hai quá trình, quá trình mã hoá và giải mã thuỷ vân. Sơ đồ khối tóm tắt các thành phần chính của mô hình hệ thống thuỷ vân như sau: Hình 2.1: Các thời kỳ mã hoá và giải mã thuỷ vân. Một bộ dữ liệu D được biến đổi thành bộ dữ liệu đã thuỷ vân DW bằng cách dùng hàm mã hoá thuỷ vân, đầu vào khoá bí mật KS chỉ được người chủ sở hữu biết, và một thuỷ vân W. Thuỷ vân làm thay đổi dữ liệu. Tuy nhiên, những thay đổi này được kiểm soát bằng cách sử dụng tập các ràng buộc thích hợp tham chiếu đến tập G. Các ràng buộc này giới hạn lượng thay đổi để có thể thực hiện trên dữ liệu. Quá trình mã hoá thuỷ vân gồm ba bước chính sau: T* KS W’ D W G Dw D’w  1',.....,' mo SS  1,....., mo SS Phân hoạch dữ liệu Phân hoạch dữ liệu Nhúng thuỷ vân Đánh giá ngƣỡng tối ƣu Kênh truyền Giải mã ngƣỡng Bầu chọn theo đa số  28  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bước 1: Phân hoạch dữ liệu: dùng khoá bí mật KS , bộ dữ liệu D được chia thành m phần {So , . . . , Sm-1 } không giao nhau. Bước 2: Nhúng thuỷ vân: Một bít thuỷ vân được nhúng vào mỗi phần bằng cách thay đổi các thống kê phân hoạch trong khi vẫn thỏa mãn các ràng buộc sử dụng trong bộ G. Sự thay đổi này được thực hiện bằng cách giải bài toán tối ưu hoá có ràng buộc. Bước 3: Đánh giá ngưỡng tối ưu: các thống kê bit nhúng được sử dụng để tính toán ngưỡng tối ưu T* - ngưỡng làm cực tiểu hoá khả năng ( xác suất ) xảy ra lỗi giải mã. Bộ dữ liệu đã nhúng thuỷ vân DW được chuyển đi qua các kênh truyền và do đó có thể chịu những tấn công có chủ đích hoặc không có chủ đích nhằm phá huỷ thông tin thuỷ vân. Chú ý rằng những tấn công có chủ đích có thể được thực hiện mà không cần bất cứ sự hiểu biết gì về khoá bí mật KS hoặc bộ dữ liệu D. Giải mã thuỷ vân là quá trình lấy ra thuỷ vân đã nhúng từ bộ dữ liệu đã nhúng thuỷ vân DW, sử dụng khoá bí mật KS và ngưỡng tối ưu T*. Thuật toán giải mã này không rõ ràng bởi bộ dữ liệu gốc D không yêu cầu giải mã thành công thuỷ vân đã nhúng. Quá trình giải mã thuỷ vân được chia thành ba bước chính sau: Bước 1: Phân hoạch bộ dữ liệu: sử dụng thuật toán phân hoạch dữ liệu đã dùng trong phần mã hoá trên, sinh ra các phân vùng dữ liệu. Bước 2: Giải mã ngưỡng: Các thống kê của mỗi phân vùng được đánh giá và bit đã nhúng được giải mã bằng cách dùng lược đồ giải mã ngưỡng dựa trên ngưỡng tối ưu T*.  29  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bước 3: Bầu chọn theo đa số: Các bit thuỷ vân được giải mã sử dụng kỹ thuật bầu chọn theo đa số. Tiếp theo sẽ trình bày chi tiết các kỹ thuật, các thuật toán cho quá trình mã hoá và giải mã thuỷ vân.[9] 2.3. Phân hoạch dữ liệu Thuật toán phân hoạch dữ liệu phân chia bộ dữ liệu thành các phần, các tập hợp con dựa vào khoá bí mật KS . Bộ dữ liệu D là một cơ sở dữ liệu quan hệ với lược đồ ),...,,( 10 AAPD trong đó P là thuộc tính khoá chính, 10 ,..., AA là  thuộc tính dùng để nhúng thuỷ vân và D là số bản ghi trong D . Bộ dữ liệu D được chia thành m phần không giao nhau  10 ,..., mSS , sao cho mỗi phần iS chứa trung bình m D bản ghi từ bộ dữ liệu D . Các phần không giao nhau, tức là, với hai phần bất kỳ iS và jS mà ji  thì  ji SS  . Với mỗi bản ghi Dr  , thuật toán phân hoạch dữ liệu tính toán mã xác thực thông tin ( MAC ) để đảm bảo an toàn và mã này được cho bởi hàm ))||.(||( SS KPrHKH , trong đó Pr. là khoá chính của bản ghi r ,  H là hàm băm an toàn và || là toán tử nối. Sử dụng MAC đã tính, các bản ghi được đưa vào các phân vùng. Với bản ghi r , phân vùng tương ứng được tính như sau: mKPrHKHrpartition SS mod))||.(||()(  Sử dụng đặc tính này của hàm băm để phân phối các bản ghi đồng đều vào các phân vùng, kỹ thuật phân hoạch này chia trung bình m D vào mỗi phân  30  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên vùng. Hơn nữa, kẻ tấn công không thể đoán được các bản ghi đã được đưa vào phân vùng nào nếu không biết rõ về khoá bí mật SK và số phân vùng dữ liệu đã phân hoạch m được giữ bí mật. Không nhất thiết phải giữ bí mật m . Tuy nhiên, việc giữ bí mật có thể gây khó khăn hơn cho kẻ tấn công muốn tái lập các phần đó. Thuật toán phân hoạch dữ liệu được mô tả như sau: Thuật toán: get_partitions Đầu vào: bộ dữ liệu D , khoá bí mật SK , số phân vùng m Đầu ra: Các phân vùng dữ liệu 10 ,..., mSS 1. 10 ,..., mSS  {} 2. for each bản ghi Dr  3. mKPrHKHrpartition SS mod))||.(||()(  4. chèn r vào )(rpartitionS 5. return 10 ,..., mSS Mặc dù hầu hết các dữ liệu quan hệ đều có khóa chính, kỹ thuật này có thể được mở rộng để xử lý trường hợp khi dữ liệu quan hệ không có khoá chính. Giả sử quan hệ thuộc tính đơn,  bit ý nghĩa nhất ( MSB ) của dữ liệu có thể được dùng để thay thế cho khoá chính. Việc sử dụng MSB cho việc nhúng thủy vân sẽ không làm thay đổi  bit ý nghĩa nhất này. Tuy nhiên, nếu quá nhiều bản ghi chia sẻ cùng  bít MSB có thể cho phép kẻ tấn công suy  31  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên luận được thông tin về sự phân phối trong các phần dữ liệu. Trường hợp quan hệ đa thuộc tính, sử dụng các thuộc tính nhận biết thay vì sử dụng khoá chính; ví dụ dữ liệu y học, ta có thể sử dụng tên đầy đủ của bệnh nhân, địa chỉ bệnh nhân, ngày tháng năm sinh của bệnh nhân. Ký hiệu Ý nghĩa m Số phân vùng  Kích thước nhỏ nhất của một phân vùng W Chuỗi bit thuỷ vân {bl-1,…,b0} l Chiều dài của chuỗi bit thuỷ vân Xmax Các thống kê nhúng thuỷ vân cực đại Xmin Các thống kê nhúng thuỷ vân cực tiểu Si Phân vùng dữ liệu thứ i |Si|, n Độ dài của vector Si Ks Khoá bí mật T* Ngưỡng giải mã tối ưu Gi Ràng buộc thứ i i Vector thao tác trong R n Hình 2.2. Bảng biểu diễn các ký hiệu sử dụng trong thuật toán  32  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4. Nhúng thuỷ vân Thuật toán nhúng thuỷ vân bằng cách mã hoá bit có thể coi như một bài toán tối ưu có ràng buộc. Ở đây, thuật toán tìm kiếm theo mẫu được sử dụng để giải bài toán tối ưu. Việc sử dụng thuật toán tối ưu được quyết định tuỳ thuộc thời điểm ứng dụng và các yêu cầu tính toán. Để đơn giản, giả sử các bản ghi trong phân vùng iS chứa thuộc tính số đơn. Trong trường hợp này, mỗi phần iS có thể được biểu diễn bằng một véctơ dữ liệu số n inii ssS  ],...,[ 1 . 2.4.1 Mã hoá bít đơn Cho bít thuỷ vân ib , và véctơ dữ liệu số n inii ssS  ],...,[ 1 . Thuật toán mã hoá bít ánh xạ vectơ dữ liệu iS thành vectơ dữ liệu mới ii W i SS  , trong đó n inii  ],...,[ 1 là vectơ thao tác. Các thao tác bị hạn chế bởi các ràng buộc trong bộ   ipii ggG ,...,1 . Việc mã hoá này dựa trên hàm mã hoá tối ưu gọi là hàm giấu được định nghĩa như sau: Hàm giấu  : n , với  là tập hợp các tham số bí mật do người chủ sở hữu dữ liệu đưa ra. Tập hợp  có thể được xem như là một phần của khoá bí mật. Chú ý rằng khi hàm giấu được áp dụng cho iiS  thì chỉ vectơ thao tác i là biến, trong khi iS và  là các hằng số. Để mã hoá bit ib vào trong tập iS , thuật toán mã hoá bít sẽ làm tối ưu hóa hàm hàm giấu )( iiS  . Bài toán tối ưu hóa sẽ là bài toán cực đại hoặc cực tiểu hàm giấu tùy thuộc vào bit ib :  33  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nếu bít ib =1 thì thuật toán mã hoá bit thực hiện giải bài toán cực đại hoá: i max )( iiS  thoả mãn ràng buộc iG Nếu bít ib =0 thì bài toán đơn giản được chuyển thành bài toán cực tiểu hóa. Giải pháp cho bài toán tối ưu hoá sinh ra vectơ thao tác * i để *)( iiS  tối ưu. Khi đó, bộ dữ liệu mới *ii W i SS  . Việc cực đại hoá cho ib =1 và cực tiểu hoá cho ib =0, đảm bảo rằng các giá trị của hàm *)( iiS  sinh ra trong cả hai trường hợp được đặt ở vị trí có khoảng cách lớn nhất và do đó làm cho bít được chèn bền vững hơn đối với các tấn công, đặc biệt là các tấn công thay đổi dữ liệu. Thuật toán mã hoá bít đơn được mô tả như sau: Thuật toán: encode_single_ bit Đầu vào: Tập dữ liệu Si, Bit bi, Tập ràng buộc Gi, Tập tham số bí mật  , Các tập thống kê Xmax, Xmin Đầu ra: Tập dữ liệu * iiS  1. If ( )( iS then return Si 2. If (b==1) then 3. Maximize ( )( iiS  ) thỏa mãn ràng buộc Gi 4. Chèn *)( iiS  vào Xmax  34  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5. else 6. Minimize ( )( iiS  ) thỏa mãn ràng buộc Gi 7. Chèn *)( iiS  vào Xmin 8. return * iiS  Thuật toán mã hóa bít nhúng bít ib vào phần iS nếu iS . Giá trị của  là kích thước cực tiểu của phân vùng. Việc cực đại hoá và cực tiểu hoá trong thuật toán mã hoá bít làm tối ưu hoá hàm giấu *)( iiS  thoả mãn các ràng buộc trong iG . Các thống kê cực đại hoá và cực tiểu hoá được ghi lại cho mỗi bước mã hoá trong maxX , minX tương ứng như đã được chỉ ra trong các dòng 4 và 7 của thuật toán mã hoá. Các thống kê này được dùng để tính toán các tham số giải mã tối ưu. Tập hợp các ràng buộc iG biểu diễn giới hạn thay đổi cho phép có thể được thực hiện trên các phần tử của iS . Các ràng buộc mô tả không gian khả thi cho vectơ thao tác i với mỗi bước mã hoá bit tùy thuộc vào từng ứng dụng và dữ liệu. Các ràng buộc này tương tự với các ràng buộc được thực hiện trên các thuật toán nhúng thuỷ vân cho âm thanh, hình ảnh, và phim với yêu cầu chủ yếu là thuỷ vân không thể phát hiện được bằng hệ thống nghe nhìn của con người. Ví dụ: Các ràng buộc phạm vi có thể được dùng để kiểm soát sự thay đổi của ij , tức là:  35  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên maxmin ijijij  Kiểu ràng buộc khác có thể yêu cầu bộ dữ liệu đã thuỷ vân duy trì các thống kê nào đó. Ví dụ, trung bình bộ dữ liệu sinh ra bằng trung bình bộ dữ liệu gốc, khi đó ràng buộc có dạng: 0 1   n j ij Một vài ràng buộc khác có thể được tạo ra phụ thuộc vào các yêu cầu ứng dụng. Các ràng buộc này được xử lý bằng thuật toán mã hoá bít dùng các kỹ thuật tối ưu hoá có ràng buộc. Hàm giấu được sử dụng ở đây phụ thuộc vào các thống kê dữ liệu. Các giá trị trung bình và phương sai của bộ dữ liệu mới ii W i SS  tương ứng là )( iiS   và 2 )( iiS   ; gọi tắt là  và 2 . Hình 2.3: Phân phối của tập iiS  trên trục số và các đầu vào tail được khoanh tròn. Điểm tham chiếu :   cref , trong đó )1,0(c là một số thực bí mật, một phần của tập  . Các điểm dữ liệu trong iiS  ở trên ref như là các đầu vào “tail” được mô tả trong hình 2.3.  36  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hàm giấu c được định nghĩa là số đầu vào tail đã chuẩn hoá bằng độ dài của iS , cũng như tail count được chuẩn hoá. Hàm này được tính như sau:    n j refsiic ijijn S 1 }{1 1 )( trong đó : n là độ dài của iS {}1 là hàm chỉ được định nghĩa như sau: Chú ý rằng tham chiếu ref phụ thuộc vào cả  và  , có nghĩa là nó không cố định và thay đổi theo các thống kê iiS  . Tail count )( iic S  được chuẩn hoá phụ thuộc vào phân phối của iiS  và tham chiếu động. Hàm mục tiêu )( iic S  là hàm phi tuyến và không khả vi, do đó bài toán tối ưu hoá trở nên gần với bài toán tối ưu hoá có ràng buộc phi tuyến. Các phương pháp tiếp cận truyền thống dựa vào độ dốc (gradient) không thể áp dụng được cho những bài toán như thế này. Có hai kỹ thuật để giải bài toán tối ưu hóa này là thuật toán di truyền và kỹ thuật tìm kiếm theo mẫu. Luận văn này sử dụng kỹ thuật tìm kiếm theo mẫu. Việc giải bài toán tối ưu hoá này không nhất thiết phải tìm ra lời giải toàn cục bởi vì việc tìm ra lời giải như thế này có thể đòi hỏi một lượng tính toán rất lớn. Mục đích chính ở đây  37  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên là tìm ra lời giải gần tối ưu đảm bảo các giá trị cực tiểu hoá hàm )( iic S  và cực đại hoá hàm )( iic S  cách xa nhau. Thuật toán di truyền được dùng định rõ tổng thể các lời giải tối ưu bằng thời điểm xử lý, trong khi tìm kiếm theo mẫu được dùng để cung cấp một lời giải tối ưu cục bộ không theo thời gian xử lý 2.4.2. Thuật toán tìm kiếm theo mẫu Thuật toán di truyền không tìm ra được tối ưu cục bộ, tuy nhiên thuật toán di truyền yêu cầu một số lượng lớn hàm đánh giá tập trung thành tối ưu toàn cục. Do vậy, giải thuật di truyền được sử dụng chỉ khi thời gian xử lý không yêu cầu chính xác và thuỷ vân được thực hiện độc lập. Kỹ thuật tìm kiếm theo mẫu cho phép thực hiện nhanh hơn. Các phương pháp tìm kiếm theo mẫu là một lớp các phương pháp tìm kiếm trực tiếp cho quá trình tối ưu hoá phi tuyến. Các phương pháp tìm kiếm theo mẫu này đã được sử dụng rộng rãi bởi tính đơn giản và tính thực tế của chúng. Tìm kiếm theo mẫu bắt đầu tại điểm ban đầu và thử hàm mục tiêu tại mẫu các điểm đã định trước xoay quanh điểm với mục tiêu tạo ra thế mới tốt hơn. Sự di chuyển này tương tự việc di chuyển thăm dò. Nếu thử thành công (tức là tạo ra một thế mới tốt hơn), do vậy quá trình này được lặp lại với mẫu xoay quanh điểm mới tốt nhất. Trái lại, kích cỡ của mẫu thử sẽ giảm và hàm mục tiêu được thử lại với điểm hiện tại này. Để cải thiện việc thực hiện việc tìm kiếm theo mẫu, hàm mục tiêu )( iic S  được xấp xỉ bằng các hàm sigmoid trơn như sau:  38  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên    n j ijijrefiic sSigmoid