Đề tài 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 giải thuật di truyền

2.2.1. Theo kiểu dữ liệu (Data type) a) Thuỷ vân dữ liệu kiểu số (watermarking numerical data) có các nghiên cứu của R. Agrawaland J. Kiernan: Watermarking Relational Databases. VLDB, 2002. Giả thiết cơ bản của nghiên cứu này là chấp nhận một lượng thay đổi với các số nhỏ ở  bit ít ý nghĩa nhất của các giá trị dữ liệu kiểu số. Ý tưởng cơ bản là phải đảm bảo rằng các vị trí bit nhúng đó có chứa các giá trị đặc trưng để có thể xác định được bởi khoá bí mật K. Để nhận dạng lại thuỷ vân đã nhúng, người ta đã tiến hành so sánh các giá trị đánh dấu được tính toán với các giá trị bit đã lưu trong cơ sở dữ liệu. Thuỷ vân được nhận dạng nếu tỷ lệ phần trăm trùng lặp lớn hơn một ngưỡng T nào đó cho trước. b) Watermarking categorical data có các nghiên cứu của + R. Sion: Proving ownership over categorical data. ICDE 2004 + E. Bertino, B.C Ooi, Y.Yang, and R. Deng: Privacy and ownership preserving of outsourced medical data. ICDE 2005. Ý tưởng cơ bản của các nghiên cứu này là: đối với mỗi nhóm thuộc tính X nào đó, thay đổi một số giá trị của thuộc tính này thành các giá trị khác sao cho các thay đổi này là chấp nhận được. Các thay đổi này sẽ tuỳ thuộc vào từng ứng dụng cụ thể. 2.2.2. Theo kiểu biến dạng (Distortion) Ba nhà khoa học Y. Li, H. Guo, và S. Jajodia công bố công trình “Tamper Detection and Localization for Categorical Data Using Fragile Watermarks”, DRM 2004. Ý tưởng cơ bản của nghiên cứu này là: Tất cả các bộ được phân hoạch một cách bí mật thành g nhóm thông qua hàm băm H(K,r.P). Một dấu thuỷ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 24 - vân (watermark) khác được nhúng vào mỗi nhóm, vì vậy bất kỳ một thay đổi nào trên dữ liệu đều có thể được nhận dạng và định vị với độ chính xác cao tới cấp nhóm. 2.2.3. Theo độ nhạy (Sensitivity) Hệ thống thuỷ vân có thể được phân thành hai dạng là bền vững và dễ bị phá huỷ thông qua độ nhạy của chúng đối với các tấn công cơ sở dữ liệu + Thuỷ vân bền vững (Robust watermarks) được sử dụng cho bảo vệ bản quyền, chứng mình quyền sở hữu, hoặc chống lại sự sao chép lậu. + Thuỷ vân dễ bị phá huỷ (Fragile watermarks) được sử dụng để định vị và phát hiện sự giả mạo dữ liệu. a) Thủy vân bền vững Có nghiên cứu của tác giả R. Agrawaland J. Kiernan: “Watermarking Relational Databases”. VLDB 2002. Cho B(k;m,p) là xác suất có nhiều hơn k thành công trong m phép thử Bernoulli. Một dấu thuỷ vân được nhận dạng nếu có nhiều hơn một tỉ lệ phần trăm T các bit đã nhúng được nhận dạng chính xác. b) Thủy vân dễ vỡ *) Các tác giả Y. Li, H. Guo, và S. Jajodia công bố công trình “Tamper Detection and Localization for Categorical Data Using Fragile Watermarks”. DRM 2004. Đóng góp của công trình này là: Thuỷ vân được tính toán bằng cách băm tất cả các bộ thành các nhóm Bất kỳ thay đổi nào tới dữ liệu đều có thể được nhận dạng chi tiết đến mức nhóm dữ liệu với tỉ lệ thành công/lỗi là !ln21 g Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 25 - *) Các tác giả H. Guo, Y. Li, A. Liu, và S. Jajodia với công trình “A Fragile Watermarking Scheme for Detecting Malicious Modifications of Database Relations”. IS 2006 Đóng góp của công trình này là cải thiện độ chính xác khi xác định vị trí làm giả trong dữ liệu 2.2.4. Theo thông tin thuỷ vân (watermark information) a) Nhúng một bit đến nhiều bit R. Sion, M. Atallah, và S. Prabhakar với công trình “Rights Protection for Relational Data”. SIGMOD 2003. Thuỷ vân một tập các số thực bằng cách thay đổi các phân phối của nó. Phương pháp này được thực hiện bằng cách: + Sắp xếp các giá trị thông qua khoá được băm của tập các bit ý nghĩa nhất của các giá trị đã được chuẩn hoá. + Phân hoạch chúng thành các tập con không giao nhau + Nhúng một bit thuỷ vân vào một tập con bằng cách thực hiện các thay đổi rất nhỏ, như vậy các đầu ra trong phân phối là nhỏ hơn (hoặc lớn hơn) một ngưỡng nhỏ (hoặc lớn) nào đó. b) Nhúng từ nhiều bit đến cả một dấu vân tay Y. Li, V. Swarup, và S. Jajodia với công trình “Fingerprinting Relational Databases: Schemes and Specialties”. TDSC 2005. Đặc điểm của phương pháp là: + Định danh đối tượng sử dụng dữ liệu + Nhiều bit fingerprint được sử dụng để xác định đối tượng người dùng nào là kẻ gian lận. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 26 - c) Nhúng một thuỷ vân đến nhiều thuỷ vân (from one watermark to multiple watermark) Y. Li, H. Guo, và S. Wang công bố công trình nghiên cứu “A Multi-Bit Watermark for Relational Data”. JDM 2007 Công trình này giải quyết được các giả thiết đặt ra như sau: + Kẻ giả mạo cố tình chèn thêm thuỷ vân khác nữa vào dữ liệu đã được thuỷ vân + Một nhóm người dùng muốn nhúng thuỷ vân riêng của mỗi người vào dữ liệu và xác minh lại quyền sở hữu của họ một cách độc lập. Giải pháp của nghiên cứu này đưa ra là: Mở rộng nghiên cứu của Agrawal và Kiernan là nhúng nhiều thuỷ vân khác nhau W1, W2, W3,… vào dữ liệu với các khoá K1, K2, K3,…khác nhau. 2.2.5. Tính kiểm tra đƣợc Y. Li và R. Deng với công trình “Publicly Verifiable Ownership Protection for Relational Databases”. ASIACCS 2006 Yêu cầu: + Các cách tiếp cận dựa vào khoá mật là không phù hợp với việc cung cấp bản quyền tác phẩm ra công chúng. + Người chủ sở hưu dữ liệu sử dụng một khoá công khai để thực hiện một thuỷ vân công khai. Vì vậy bất kỳ ai cũng có thể sử dụng các khoá công khai này để nhận dạng thuỷ vân đã nhúng. Giải pháp của tác giả đưa ra là: + Công khai khoá + Thuỷ vân (công khai): Khoá chính, bit ý nghĩa nhất được chọn (most significant bit) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 27 - + Dấu xác thực: Số hiệu chủ sở hữu (owner ID), khoá thuỷ vân (key), hàm băm, thời điểm tạo dữ liệu, tính pháp lý, thuộc lĩnh vực nào. 2.2.6. Theo cấu trúc dữ liệu (Data structure) a) Sử dụng khoá chính ảo (Virtual primary key) Y. Li, V. Swarupand S. Jajodia với công trình “Constructing a Virtual Primary Key for Fingerprinting Relational Data”. DRM 2003 Giải quyết vấn đề đặt ra là: Nhiều lược đồ thuỷ vân đều dựa vào sự tồn tại của khoá chính, điều này tồn tại một số nhược điểm như sau: + Không thể áp dụng thuỷ vân trực tiếp với những quan hệ mà không tồn tại khoá chính. + Rất dễ bị tấn công bởi kẻ tấn công đơn giản là thực hiện thay đổi hoặc xoá khoá chính Ý tưởng cơ bản để giải quyết các vấn đề trên được nêu ra trong công trình này là: + Xây dựng khoá chính ảo bằng cách kết hợp các bit ý nghĩa nhất của một số thuộc tính để tạo khoá chỉnh ảo. + Các thuộc tính khác nhau được chọn cho mỗi bộ là dựa vào một khoá bí mật. + Nhược điểm của phương pháp này là làm tăng gấp đôi nguy cơ thất bại khi nhận dạng lại thuỷ vân đã nhúng bởi vì, khi tao ra thêm một khoá chính ảo, một số bit thuỷ vân sẽ được nhúng ít lần hơn các bit khác vào dữ liệu. Điều này làm gia tăng khả năng thất bại trong nhận dạng thuỷ vân nếu bị tấn công. b) Xử lý dữ liệu theo khối (Data cube) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 28 - J. Guo, Y. Li, R. Deng, và K. Chen công bố công trình “Rights Protection for Data Cubes”. ISC 2006 Dữ liệu dạng khối là một dạng dữ liệu phổ biến mà hỗ trợ tốt cho việc khai thác một lượng lớn dữ liệu đa chiều. Thao tác phố biến nhất đối với dữ liệu dạng này là truy vấn tổ hợp. c) Xử lý theo dòng dữ liệu (Streaming data) *) R. Sion, M. Atallah, và S. Prabhakar công bố công trình công trình nghiên cứu “Resilient Rights Protection for Sensor Streams”. VLDB 2004 Ý tưởng của công trình này là sử dụng một số các giá trị cực trị và các giá trị lân cận của nó như là những đối tượng mang các bit thuỷ vân. Lựa chọn các giá trị cực trị và thuỷ vân mọi giá trị lân cận (LSB) dựa trên một khoá bí mật và các bit ý nghĩa nhất của chúng (MSB). Mọi mẫu đều bao gồm đầy đủ các giá trị cực trị và các giá trị lân cận của nó. *) H. Guo, Y. Li, và S. Jajodia với công trình “Chaining Watermarks for Detecting Malicious Modifications to Streaming Data”. IS 2007 Ý tưởng của nghiên cứu này là phân hoạch một luồng dữ liệu dạng số thành các nhóm và nhúng một thuỷ vân vào mỗi nhóm. Việc phân nhóm là dựa vào các điểm động bộ. Một thuỷ vân dùng để nhúng được tính toán bằng cách băm nhóm đã được băm trước đó hiện tại và nhóm đã băm trước đó tiếp theo, từ đó thuỷ vân được móc nối với nhau. Việc nhận dạng thuỷ vân có thể được thực hiện và định vị các thay đổi ngay cả khi một số nhóm đã bị xoá toàn bộ cả nhóm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 29 - CHƢƠNG 3 – NỘI DUNG VÀ CÁC KẾT QUẢ NGHIÊN CỨU 1. Phân hoạch dữ liệu 2. Nhúng thuỷ vân 3. Giải mã thuỷ vân Các mục trong chương này của luận văn sẽ tập trung trình bày các kỹ thuật áp dụng để nhúng thuỷ vân và giải mã thuỷ vân cơ sở dữ liệu quan hệ. Đó là kỹ thuật thuỷ vân cơ sở dữ liệu quan hệ sử dụng kỹ thuật tối ưu hoá như một bài toán tối ưu hoá có ràng buộc, và sử dụng giải thuật di truyền để giải quyết bài toán tối ưu này. Kỹ thuật này bao gồm hai quá trình là mã hoá và giải mã thuỷ vân. Quá trình mã hoá được thực hiện qua các bước [22]: + Phân hoạch dữ liệu + Nhúng thuỷ vân + Đánh giá ngưỡng giải mã Quá trình giải mã thuỷ vân được thực hiện qua các bước + Phân hoạch dữ liệu + Giải mã ngưỡng + Bầu chọn theo đa số Các mục dưới đây sẽ nêu chi tiết cách thức tiến hành. 3.1. Phân hoạch dữ liệu Một số ký hiệu được sử dụng trong luận văn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 30 - 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 Bảng 1. Danh mục các ký hiệu Mục tiêu chính của phần này là trình bày về kỹ thuật phân hoạch, kỹ thuật này sẽ làm tăng tính ngẫu nhiên khi chọn các bộ và phân vào các phân hoạch riêng rẽ. Tính ngẫu nhiên này có độ bảo mật cao được đảm bảo bằng hàm băm mật mã gọi mà mã xác thực thông điệp. Với việc áp dụng kỹ thuật phân hoạch này sẽ làm tăng khả năng bền vững của thuỷ vân trước các tấn công. 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 . Khoá bí mật KS thường được chọn sao cho kẻ tấn công khó có thể đoán ra được, đồng thời đảm bảo sự duy nhất và ổn định trong quá trình tính toán phân hoạch. Vì vậy, giá trị thích hợp nhất dành cho KS là các số nguyên tố càng dài càng tốt, điều này nhằm làm khó cho kẻ tấn công trong việc dò ra khoá bí mật. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 31 - Bộ dữ liệu D là một quan hệ cơ sở dữ liệu với lược đồ D(P, A0,…, Av-1) trong đó + P là thuộc tính khoá chính. + A0,…, Av-1 là v thuộc tính cho việc thuỷ vân và |D| là số bản ghi trong D Bộ dữ liệu D này được chia thành m phần không giao nhau (hay không chồng lên nhau) {S0,…., Sm-1}, sao cho mỗi phần Si 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 2 phần bất kỳ Si và Sj mà i  j 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 trong quá trình phân hoạch và mã này được cho bởi hàm băm H(Ks || H(r.P || Ks)) , trong đó + Pr. là khoá chính của bản ghi r + H() là hàm băm an toàn + || là toán tử nối. Sử dụng MAC đã tính toán, các bản ghi được chia cho các phần. Với bản ghi r , phần được chia của nó được tính như sau: partition(r) = H(Ks || H(r.P || Ks)) mod m Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 32 - Hình 3. 1. Cách phân hoạch bộ dữ liệu Sử dụng đặc tính này để các hàm băm an toàn sinh ra các bản tin được phân phối một cách giống nhau, kỹ thuật phân hoạch này trung bình chứa m D || bản ghi trong mỗi phần của phân hoạch. Hơn thế nữa, một kẻ tấn công không thể đoán trước được các bản ghi đã chia thành các phần mà không biết rõ về khoá bí mật Ks và số phần dữ liệu đã phân hoạch m được giữ bí mật. Giữ m bí mật không phải là đòi hỏi. Tuy nhiên, giữ nó bí mật để gây khó khăn hơn cho kẻ tấn công muốn tái sinh các phần đó. Thuật toán phân hoạch dữ liệu được mô tả như sau: Algorithm: get_partitions Input: bộ dữ liệu D, khoá bí mật Ks, số phần phân hoạch m Output: Các phần dữ liệu S0,…., Sm-1 1. S0,…., Sm-1 {} 2. for each Tuple Dr  3. partition(r)  H(Ks || H(r.P || Ks)) mod m 4. insert r into Spartition(n) 5. return S0,…., Sm-1 r.P Field1 Field 2 … 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . n-1 n S1 S3 S2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 33 - Mặc dù sự có mặt của khoá chính trong quan hệ được thuỷ vân là phổ biến trong dữ liệu quan hệ, kỹ thuật này có thể dễ dàng được mở rộng để xử lý các trường hợp khi quan hệ không có khoá chính. Giả sử quan hệ thuộc tính đơn,  bít ý 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 rằng dữ liệu nhúng thuỷ vân thay đổi sẽ không giống như  bít MSB thay đổi. Tuy nhiên, nếu quá nhiều bản ghi chia sẻ cùng  bít MSB thì có thể cho phép kẻ tấn công suy luận được thông tin về sự phân phối phần dữ liệu. Giải pháp này có thể chọn  để làm cực tiểu hoá các bản sao. *) Các giá trị thực nghiệm của luận văn được tác giả áp dụng như sau: Ký hiệu Ý nghĩa m = 20 Số phân vùng Ks = 97 Khoá bí mật H = MD5 Hàm băm 3.2. Nhúng thuỷ vân Để nhúng thuỷ vân vào cơ sở dữ liệu đã được phân hoạch, quá trình nhúng được tiến hành thông qua bước mã hoá bit đơn để xác định xem bit nào trong chuỗi bit thuỷ vân sẽ được nhúng vào phân vùng cụ thể nào. Việc mã hoá này chính là việc thực hiện giải bài toán tối ưu hoá có ràng buộc áp dụng giải thuật di truyền. Sau quá trình nhúng, kết quả thu được là hai tập thống kê được dùng để tính ngưỡng cho quá trình giải mã thuỷ vân sau này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 34 - Để đơn giản, ta giả sử các bản ghi trong phần phân hoạch 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 như là một véc tơ dữ liệu số   ninii SSS  ,..., . 3.2.1. Mã hoá bit đơn Cho bít thuỷ vân bi, và véc tơ dữ liệu số   ninii SSS  ,..., . [22] 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 như là hàm giấu được định nghĩa như sau: Định nghĩa 1: Hàm giấu  : n , với  là tập hợp các tham số bí mật được quyết định bởi người chủ sở hữu dữ liệu. 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 bi vào trong tập iS , thuật toán mã hoá bít sẽ làm tối ưu hoá hàm hàm giấu )( iiS  . Mục đích của bài toán tối ưu hoá cực đại hoặc cực tiểu hàm giấu dựa vào bít ib : Nếu bít bi=1 thì thuật toán mã hoá bít đi 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 bi = 0 thì bài toán đơn giản được chuyển thành bài toán cực tiểu hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 35 - 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: Algorithm: Encode_single_bit Input: Tập dữ liệu Si, bit bi, tập ràng buộc Gi, tham số bí mật , tập thống kê Xmax, Xmin Output: Tập dữ liệu Si + * i 1. If (|Si| <  ) then return Si 2. If (bi = = 1) then 3. maximize ( )( iiS  ) phụ thuộc vào các ràng buộc Gi 4. insert *)( iiS  into Xmax 5. else 6. minimize ( )( iiS  ) phụ thuộc vào các ràng buộc Gi 7. insert *)( iiS  into Xmin 8. return Si + * i Thuật toán mã hoá bít nhúng bít bi vào phần Si nếu |Si| >  . Giá trị của  biểu diễn kích cỡ phần cực tiểu. 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 36 - 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 sử dụng Gi biểu diễn các biên với những thay đổi cho phép có thể được thực hiện trên các phần tử của Si. Các ràng buộc này mô tả không gian khả thi cho vectơ thao tác i với mỗi bước mã hoá bít. Các ràng buộc này phụ thuộc vào ứng dụng và dữ liệu. Ví dụ đối với dữ liệu là mức tiêu thụ điện sinh hoạt thì có thể có các ràng buộc là các điểm cận để chuyển đổi mức giá tính phí tiêu thụ. Với Việt Nam thời điểm hiện tại (năm 2009) thì các mốc để tính phí tiêu thụ điện là: 50 KW, 100 KW, 150 KW, 200 KW. Các ràng buộc khoảng có thể được dùng để điều khiển độ lớn sự thay đổi cho ij , tức là: maxmin ijijij  Kiểu ràng buộc thú vị 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 thì ràng buộc trong trường hợp này có dạng: 0 1   n j ij Một vài ràng buộc sử dụng 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 . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 37 - Điểm tham chiếu :   cref , trong đó )1,0(c là một số thực bí mật, là 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 đượ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 đượ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 tự động với 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  không tuyến tính và không thể lấy vi phân, vì vậy nó làm cho bài toán tối ưu hoá gần với bài toán tối ưu hoá có ràng buộc không tuyến tính. Các cách tiếp cận truyền thống dựa vào gradient không thể áp dụng được cho những bài toán như thế này. Thuật toán di truyền sẽ được áp dụng để giải bài toán tối ưu hoá này. 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 tối ưu toàn cục bởi vì việc tìm ra lời giải 1 Nếu thoả mãn điều kiện trong {} 0 Các trường hợp còn lại 1{} = Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 38 - 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 của phương pháp là tìm ra lời giải (phương án) gần tối ưu mà đả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. 3.2.2. Áp dụng giải thuật di truyền giải bài toán tối ƣu Thuật toán di truyền (GA) là một kỹ thuật tìm kiếm dựa trên các nguyên tắc chọn ngẫu nhiên hoặc quá trình chọn lọc tự nhiên. Thay vì sử dụng thông tin gradient, GA sử dụng trực tiếp hàm mục tiêu trong việc tìm kiếm. Thuật toán di truyền này sẽ tìm kiếm không gian giải pháp bằng cách duy trì các giải pháp thế. Sau đó, bằng cách sử dụng các hoạt động liên quan như là sự giao nhau, sự biến đổi, và sự lựa chọn, thuật toán di truyền (GA) tạo ra các thế hệ giải pháp thành công – các thế hệ có kế thừa và phát triển các đặc tính tốt của cha mẹ chúng và như thế chúng dần dần tới gần các giải pháp tối ưu hoặc gần tối ưu. Bằng việc sử dụng trực tiếp hàm mục tiêu trong tìm kiếm, thuật toán di truyền có thể được áp dụng một cách có hiệu quả trong các bài toán không lồi, không tuyến tính cao, và phức tạp. Thuật toán di truyền trong tìm kiếm đã thường xuyên được sử dụng để giải các bài toán tối ưu hoá và các bài toán không tuyến tính kết hợp với các ràng buộc hoặc các hàm mục tiêu phức tạp. Thuật toán di truyền không bảo đảm tìm ra tối ưu toàn cục; tuy nhiên nó có vẻ ít đặt bẫy tại vị trí tối ưu hơn các phương pháp tìm kiếm truyền thống dựa vào gradient khi hàm mục tiêu không trơn và nói chung là tốt. GA thường phân tích phần không gian giải pháp rộng hơn các phương pháp thông thường và do đó nó có thể tìm ra các giải pháp khả thi hơn trong các bài toán có ràng buộc nặng. Bài toán dành cho GA là tìm kiếm trên không gian các giả thuyết ứng cử để xác định giả thuyết tốt nhất. Trong GA “giả thuyết tốt nhất” được định Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 39 - nghĩa như là một giả thuyết tối ưu hoá một đại lượng số được định nghĩa trước cho bài toán sắp tới, được gọi là độ thích nghi của giả thuyết. Mặc dù các thuật giải di truyền được thực hiện thay đổi theo bài toán cụ thể, nhưng chúng chia sẻ chung cấu trúc tiêu biểu sau: Thuật giải hoạt động bằng cách cập nhật liên tục tập giả thuyết – được gọi là quần thể. Ở mỗi lần lặp, tất cả các cá thể trong quần thể được ước lượng tương ứng với hàm thích nghi. Rồi quần thể mới được tạo ra bằng cách lựa chọn có xác suất các cá thể thích nghi tốt nhất từ quần thể hiện tại. Một số trong những cá thể được chọn được đưa nguyên vẹn vào quần thể kế tiếp. Những cá thể khác được dùng làm cơ sở để tạo ra các cá thể con bằng cách áp dụng các tác động di truyền: lai ghép và đột biến. Các giả thuyết mới được tạo ra bằng cách áp dụng toán tử lai ghép cho cặp giả thuyết thích nghi nhất và bằng cách tạo ra các đột biến điểm đơn trong thế hệ giả thuyết kết quả. Quá trình này được lặp cho đến khi các giả thuyết thích hợp được phát hiện. Các giả thuyết trong GA thường được thể hiện dưới dạng chuỗi các bit, để chúng có thể dễ dàng được thực hiện bởi các toán tử di truyền: đột biến và lai ghép. Các giả thuyết được thể hiện bởi chuỗi bit này có thể khá phức tạp. Hàm thích nghi (hàm phạt) định nghĩa tiêu chuẩn để xếp hạng các giả thuyết tiềm ẩn và để chọn lọc chúng theo xác suất để đưa vào quần thể thế hệ kế tiếp. Thường các tiêu chuẩn khác có thể được bao hàm, chẳng hạn như độ phức tạp và mức độ tổng quát của luật. Một cách tổng quát hơn, khi giả thuyết chuỗi bit được hiểu như là một thủ tục phức tạp, hàm thích nghi có thể đo hiệu suất tổng của thủ tục kết quả hơn là hiệu suất của các luật riêng biệt. Với bài toàn này, bộ khả thi i là tập hợp các giá trị của i làm thoả mãn tất cả các ràng buộc trong Gi. Thuật toán di truyền trong tìm kiếm không làm việc trực tiếp với các điểm trong bộ i , nhưng có ánh xạ các điểm trong i Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 40 - thành xâu các ký hiệu được gọi là nhiễm sắc thể. Một lược đồ biểu diễn nhị phân đơn giản sử dụng các ký hiệu {0, 1}; mỗi nhiễm sắc thể dài L ký hiệu. Ví dụ một nhiễm sắc thể nhị phân biểu diễn véctơ  inii  ,....,1 có dạng: Mỗi thành phần của i sử dụng n L bít, với n = |Si|. Biểu diễn nhiễm sắc thể này tự động xử lý các ràng buộc khoảng trên i . Ví dụ nếu ij chỉ có thể lấy các giá trị trong khoảng [lij, hij], thì bằng việc ánh xạ các số nguyên trong khoảng [0, 2L/n - 1] thành các giá trị trong khoảng [lij, hij] qua sự tịnh tiến và sự đếm gộp đơn giản, điều này đảm bảo rằng bất cứ hoạt động nào được thực hiện trên nhiễm sắc thể đó, các đầu vào được đảm bảo ở trong khoảng khả thi. Mỗi nhiễm sắc thể có một giá trị tương ứng với hàm mục tiêu, như là sự phù hợp của nhiễm sắc thể. Để xử lý các loại ràng buộc khác, người ta phạt các nhiễm sắc thể không khả thi bằng cách làm giảm giá trị phù hợp của chúng theo hàm phạt )( i - hàm biểu diễn mức độ không khả thi. Không mất tính tổng quát, nếu bài toán tối ưu hoá được giải với các ràng buộc Gi={gi1,…., gip}, thì hàm thích hợp được sử dụng là )()( iiic S   , trong đó  là hệ số phạt và nó được chọn đủ lớn để phạt hàm mục tiêu trong trường hợp i không khả thi. Hàm phạt )( i được tính như sau:    p j iiji g 1 )()( trong đó: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 41 -  ),( iijg biểu diễn lượng không khả thi đối với ràng buộc gij. Ví dụ nếu ràng buộc gij là 0 1   n j ij thì ||||),( 1   n j ijiij g . Thuật toán di truyền ít dùng cho tối ưu cục bộ. Tuy nhiên, thuật toán di truyền yêu cầu một lượng lớn các đánh giá hàm cho hội tụ tới tối ưu toàn cục. Như vậy, thuật toán di truyền được sử dụng trong tìm kiếm chỉ khi thời gian xử lý không đòi hỏi chính xác (khắt khe) và thuỷ vân được thực hiện độc lập. 3.2.3. Thuật toán nhúng thuỷ vân Thuỷ vân là một bộ l bít W=bl-1, . . . , b0 được nhúng vào các phần dữ liệu  10 ,..., mSS . Để việc nhúng thuỷ vân được nhiều lần trong bộ dữ liệu, độ dài thuỷ vân l được chọn sao cho: ml  . Thuật toán nhúng thuỷ vân sẽ nhúng bít ib vào phần kS sao cho ilk mod . Kỹ thuật này đảm bảo mỗi bít thuỷ vân được nhúng       l m lần trong bộ dữ liệu D . Thuật toán nhúng thuỷ vân được mô tả như sau: Algorithm: embed_watermark Input: Tập dữ liệu D, khoá bí mật Ks, số phân vùng m, thuỷ vân W = {b0, …, bl-1} Output: Tập dữ liệu đã nhúng thuỷ vân Dw, ngưỡng tối ưu giải mã T * 1. Dw, Xmax, Xmin  {} 2. S0, …., Sm-1  get_partition(D, Ks, m) 3. for each Partition Sk )( iijg   = 0 Nếu i thoả mãn ràng buộc gij (gij, i ) Trƣờng hợp còn lại Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 42 - 4. i  k mod l 5. w kS  encode_single_bit(bi, Sk, c, Xmax, Xmin) 6. insert w kS  Dw 7. T*  get_optimal_thershold(Xmax, Xmin) 8. return Dw, T * Thuật toán nhúng thuỷ vân sẽ sinh ra các phần  10 ,..., mSS bằng cách gọi hàm get_partitions, sau đó với mỗi phần kS bít thuỷ vân ib được mã hoá bằng cách sử dụng thuật toán mã hoá bít đơn (encode_single_bit). Phần thay đổi sinh ra W kS được chèn vào bộ dữ liệu đã nhúng thuỷ vân. Các thống kê (Xmax, Xmin) được thu thập sau mỗi bít nhúng và được sử dụng bằng thuật toán get_optimal_threshold để tính toán ngưỡng giải mã tối ưu. *) Các giá trị thực nghiệm mà tác giả áp dụng trong luận văn này là : Watermark = 10101 ; //Chuỗi bit thuỷ vân dùng để nhúng c = 0.75; // Tham số bí mật c  = 10; // Kích thƣớc nhỏ nhất của một phân vùng l = 5 // Độ dài thuỷ vân 3.2.4. Đánh giá ngƣỡng giải mã Trong phần này, ta sẽ thảo luận kỹ thuật giải mã bít – kỹ thuật được dùng để lấy ra bít thuỷ vân đã nhúng bi từ phần W iS . Kỹ thuật giải mã bít dựa trên ngưỡng tối ưu T* để làm cực tiểu hoá xác suất xảy ra lỗi giải mã. Với phần dữ liệu W iS , kỹ thuật giải mã bít sẽ tính toán hàm giấu )( WiS và so sánh với ngưỡng giải mã tối ưu T* để giải mã bít đã nhúng ib . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 43 - Nếu )( WiS >T* thì bít được giải mã là 1, ngược lại bít giải mã là 0. Ví dụ: sử dụng hàm giấu đã được mô tả ở các phần trước, kỹ thuật giải mã tính toán tail count đã chuẩn hoá của W iS bằng cách tính toán tham chiếu ref và đếm số đầu vào trong W iS lớn hơn ref. Sau đó, tail count đã chuẩn hoá được so sánh với T*. Giá trị của ngưỡng T* nên được tính toán cẩn thận để làm cực tiểu hoá xác suất xảy ra lỗi giải mã bít. Xác suất xảy ra lỗi giải mã bít được định nghĩa như là xác suất (khả năng) bít nhúng được giải mã sai. Ngưỡng giải mã tối ưu T* được chọn để làm cực tiểu hoá xác suất xảy ra lỗi giải mã. Thời kỳ nhúng bít dựa trên việc cực tiểu hoá hoặc cực đại hoá tail count; các giá trị hàm giấu đã tối ưu hoá này sẽ được tính toán trong suốt thời kỳ mã hoá để tính toán ngưỡng tối ưu T*. Các giá trị hàm giấu cực đại hoá tương ứng với bi = 1 được lưu trong tập Xmax. Tương tự, các giá trị hàm giấu cực tiểu hoá được lưu trữ trong Xmin. Cho errP , 0P và 1P tương ứng là xác suất xảy ra lỗi giải mã, xác suất mã hoá bít =0, và xác suất mã hoá bít =1. Cho eb , db , và )(xf tương ứng là bít được mã hoá, bít được giải mã, và hàm mật độ xác suất. Khi đó, errP được tính như sau: errP = )0,1()1,0(  eded bbPbbP = 01 )0|1()1|0( PbbPPbbP eded  = 01 )0|()1|( PbTxPPbTxP ee  =     T e T e dxbxfPdxbxfP )0|()1|( 01 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 44 - Để cực tiểu hoá xác suất lỗi giải mã ( errP ) đối với ngưỡng T, ta lấy đạo hàm cấp một của errP đối với T để xác định ngưỡng tối ưu T*, như sau:             T e T e err dxbxf T Pdxbxf T P T P )0|()1|( 01 )0|()1|( 01  ee bTfPbTfP Các phân phối )0|( ebxf và )1|( ebxf được đánh giá từ các thống kê của các tập hợp Xmin và Xmax tương ứng. Qua các thí nghiệm về Xmin và Xmax , cho thấy các phân phối )0|( ebxf và )1|( ebxf có dạng chuẩn tắc và như vậy chúng có thể được đánh giá như các phân phối Gaussian ),( 00 N và ),( 11 N một cách tương ứng. Tuy nhiên, sự phân tích sau đây có thể vẫn được thực hiện với các kiểu phân phối khác. P0 có thể được đánh giá bằng |||| || minmax min XX X  , 1P 01 P . Thay thế các biểu thức Gaussian cho )0|( ebxf và )1|( ebxf , thì đạo hàm cấp một của errP có dạng: ) 2 )( exp( 2 ) 2 )( exp( 2 2 0 2 0 0 0 2 1 2 1 1 1            TPTP T Perr Cho đạo hàm cấp một của errP bằng 0, ta sẽ được phương trình bậc 2, có thể tính giá trị ngưỡng tối ưu T* làm cực tiểu hoá errP . Đạo hàm cấp 2 của errP được đánh giá tại T* để đảm bảo điều kiện ( 0 *)( 2 2    T TPerr ) được thoả mãn. 0 2 ln** 2 21 2 0 2 1 2 0 2 0 2 1 01 10 2 1 2 0 2 01 2 102 2 1 2 0 2 1 2 0                   P TT Từ sự phân tích trên, việc chọn ngưỡng tối ưu T* dựa trên các thống kê kết quả thu được của thuật toán nhúng thuỷ vân. Ngưỡng tối ưu T* làm cực Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 45 - tiểu hoá xác suất xảy ra lỗi giải mã và như thế nó sẽ nâng cao độ bền của thuỷ vân được nhúng do khả năng giải mã thành công tăng. Hình 3. 2. Thống kê phân bố tập Xmax, Xmin và cách lấy ngưỡng T* Ở hình trên, đường chấm gạch nằm giữa hai phân phối sẽ làm cực tiểu hoá xác suất xảy ra lỗi giải mã. Xác suất xảy ra lỗi giải mã cũng phụ thuộc vào các ràng buộc sử dụng. Nếu các ràng buộc sử dụng chặt thì lượng thay đổi cho bộ dữ liệu D có thể không đủ cho sự chèn thuỷ vân. Tất cả xác suất xảy ra lỗi giải mã thuỷ vân được làm giảm đi bằng cách nhúng thuỷ vân nhiều lần trong bộ dữ liệu đó, về cơ bản nó là sự lặp lại mã sửa sai. Sau nhiều lần chạy thử nghiệm kết quả giải mã, tác giả của luận văn nhận thấy rằng, ngưỡng giải mã T* sẽ nằm trong miền thuộc phần giao nhau của hai phân phối giải mã ra bit 0 và giải mã ra bit 1. Miền giao nhau này thường nằm ngoài khoảng tin cậy khi tính thống kê của tập Xmax và Xmin. Vì vậy, để Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 46 - đơn giản và tăng tốc độ xử lý tính toán khi lập trình, tác giả đã tính toán giá trị ngưỡng giải mã T* bằng cách lấy giá trị trung bình của các tập thống kê Xmax và Xmin này: + Lấy giá trị cực đại của tập Xmin + Lấy giá trị cực tiểu của tập Xmax T* = 2 )()( minmax XMaxXMin  Theo các kết quả thực nghiệm tác giả nhận thấy rằng, ngưỡng giải mã T* phụ thuộc vào phân phối của tập Xmax và Xmin, nếu phân phối của hai tập này càng cách xa nhau thì sẽ càng làm cực tiểu hoá lỗi giải mã. Điều này phụ thuộc nhiều vào kỹ thuật áp dụng dùng để giải bài toán tối ưu hoá, ở đây là kỹ thuật GA. 3.3. Giải mã thuỷ vân Thuật toán phát hiện thuỷ vân sẽ lấy ra thuỷ vân đã nhúng nhờ các tham số bí mật gồm có: KS, m,  , c, T. Quá trình giải mã thuỷ vân sẽ được thực hiện thông qua ba bước chính: Phân hoạch, giải mã và bầu chọn theo đa số + Phân hoạch tập dữ liệu chứa thuỷ vân: Kỹ thuật phân hoạch này đã được trình bày kỹ trong phần [3.1]. Đầu vào bao gồm: i) Bộ dữ liệu đã thuỷ vân DW ii) Khoá bí mật KS iii) Số phần phân hoạch m Bộ dữ liệu đạt được DW là các phần phân hoạch  10 ,..., mSS . Mỗi phần sẽ chứa một bit thuỷ vân đơn đã được mã hoá trong đó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 47 - + Giải mã để lấy ra bít đã nhúng: Sử dụng lược đồ giải mã ngưỡng dựa vào ngưỡng tối ưu T làm cực tiểu hoá xác suất xảy ra lỗi giải mã như đã nói trong phần [3.2.4]. Nếu kích cỡ phần dữ liệu nhỏ hơn  thì bít giải mã không được thực hiện, ngược lại thì nó được giải mã nhờ lược đồ giải mã ngưỡng. Thuỷ vân 01 ,..., bbW l được nhúng vài lần trong bộ dữ liệu, mỗi bít thuỷ vân được lấy ra vài lần ở nơi mà bít ib được lấy ra từ phần kS với ilk mod . Các bít lấy ra được giải mã nhờ kỹ thuật bầu chọn theo đa số. Mỗi bít ib được lấy ra l m lần . + Kỹ thuật bầu chọn theo đa số: Bit bi được quyết định bởi số lượng bit 0 hay bit 1 trong tổng số bit của bi được giải mã ra. Ví dụ nếu bit b2 được nhúng 10 lần vào cơ sở dữ liệu, sau khi giải mã, kết quả giải mã thuỷ vân thu được giả sử là 7 bit 0 và 3 bit 1. Vậy kết luận của kỹ thuật bình chọn theo đa số là bit b2 là bit 0 (b2 = 0). Với kỹ thuật bầu chọn theo đa số này thuỷ vân nhận được sẽ bền vững trước một số tấn công như chèn thêm dữ liệu, sửa đổi dữ liệu, hoặc ngay cả xoá dữ liệu, bởi vì ngưỡng giải mã được chọn tuân thủ theo nguyên lý xác suất thống kê nhằm làm cực tiểu hoá lỗi giải mã. Thuật toán phát hiện thuỷ vân như sau: Algorithm: detect_watermark Input: Tập dữ liệu đã thuỷ vân Dw, m, c,  , Ks, T *, độ dài thuỷ vân l Output: Chuỗi thuỷ vân đã nhúng WD 1. Set ones[0,.., l-1]  0 //Tập các bit giải mã là bit 1 2. Set zeros[0,.., l-1]  0 //Tập các bit giải mã là bit 0 3. S0,…., Sm-1  get_pertitions(Dw, Ks, m) 4. for j = 0 to m – 1 5. if |Sj|   Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 48 - 6. i  j mod l 7. value  (Sj, 0, c) 8. if value  T* 9. ones[i]  ones[i] + 1 10. else 11. zeros[i]  zeros[i] + 1 12. for j = 0 to l -1 13. if ones[j] > zeros[j] 14. WD[j]  1 15. else if ones[j] < zeros[j] 16. WD[j]  0 17. else 18. WD[j]  x 19. Return WD Trường hợp quan hệ đa thuộc tính thì sự đàn hồi ( bền vững) thuỷ vân được tăng lên do nhúng thuỷ vân trong nhiều thuộc tính. 3.4. Kết quả thực nghiệm Bộ dữ liệu thực nghiệm trong luận văn này là bộ dữ liệu tự tạo được giả định là số liệu điện sinh hoạt của một vùng nào đó, bộ dữ liệu này bao gồm 8000 bộ. Để cho đơn giản trong quá trình cài đặt và thực nghiệm, giả sử bộ dữ liệu chỉ bao gồm 2 trường, một trường là khoá chính của quan hệ, một trường là trường được chọn để nhúng thuỷ vân. Các thông số dùng cho quá trình thí nghiệm bao gồm: + Hàm băm: MD5 + Khoá bí mật: KS = 97 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 49 - + Số phân vùng: m = 30 + Tham số bí mật c = 0.75 + Chuỗi bit đem nhúng (watermark): 10101 + Kích cỡ nhỏ nhất của 1 phân vùng:  = 10 + Số cặp dùng cho quá trình sinh sản của GA: 5 cặp = 10 cá thể + Số thế hệ tiến hoá: 50 + Số cá thể khởi tạo ngẫu nhiên ban đầu: 50 + Ràng buộc thay đổi dữ liệu:  8%% (0.008) Bộ dữ liệu được thiết kế chứa trong file định dạng Excel với tên là Data.xls Tác giả dùng Matlab 7.04 làm môi trường cài đặt ứng dụng. Thí nghiệm được chạy trên hệ thống có cấu hình Intel Pentium IV 2 Ghz, 512 MB Ram. Sau nhiều lần chạy thử nghiệm tác giả nhận thấy, tốc độ giải mã thuỷ vân nhanh hơn gấp nhiều lần tốc độ nhúng thuỷ vân (trung bình từ 10 đến 15 lần). Thử nghiệm với các tấn công kết quả như sau: Thực hiện tấn công mỗi kiểu tấn công 20 lần, mỗi lần tác động trên các số lượng bản ghi khác nhau, kết quả thống kê như bảng 2 dưới đây. Căn cứ vào bảng đã thống kê các tấn công sau các quá trình thực nghiệm tác giả có nhận xét như sau: + Tỉ lệ thành công của kiểu tấn công thay đổi dữ liệu là cao nhất. Khi thay đổi các thông số đầu vào như khoảng cho phép dữ liệu thay đổi là 0.05, số lượng bộ bị thay đổi là 7500 (trên tổng số 8000 bộ) tương đương với trên 90% tổng số bộ bị thay đổi thì tỉ lệ thành công khi giải mã thuỷ vân vẫn là trên 60% (khoảng 63%). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 50 - + Tỉ lệ giải mã thuỷ vân thành công của kiểu tấn công xoá bộ kém hơn so với kiểu tấn công thay đổi dữ liệu. i) Với số lượng bộ cho phép xoá đi là 30% tổng số bộ thì tỉ lệ giải mã thành công là trên 40%. ii) Với 50% số bộ bị xoá thì tỉ lệ giải mã thành công/thất bại là trên 15%. + Tỉ lệ giải mã thuỷ vân thành công/thất bại của kiểu tấn công chèn thêm bộ vào cơ sở dữ liệu là thấp nhất. i) Nếu chèn trung bình khoảng 7.5% đến 8% tổng số bộ vào cơ sở dữ liệu thì tỉ lệ giải mã thành công là 50% ii) Nếu chèn thêm trên 10% (khoảng 12%) số lượng bộ mới vào cơ sở dữ liệu thì tỉ lệ giải mã thành công là 0% Các thông số trên cũng có thể bị thay đổi nếu thay đổi các thông số đầu vào như: Tăng hoặc giảm khoảng thay đổi cho phép trên dữ liệu khi nhúng thuỷ vân; độ ngẫu nhiên của việc tấn công (phá hoại); số lượng phân vùng đi kèm với độ lớn của dữ liệu (tổng số bộ). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 51 - Loại tấn công Số bản ghi bị tác động 100 200 300 500 600 1000 1500 2000 2500 3000 4000 5000 6000 7000 7500 Xoá Thành công (lần) 20 20 18 20 18 14 14 13 8 4 3 1 0 0 0 Thất bại (lần) 0 0 2 0 2 6 6 7 12 16 17 19 20 20 20 Chèn Thành công (lần) 20 20 20 17 10 0 0 0 0 0 0 0 0 0 0 Thất bại (lần) 0 0 0 3 10 20 20 20 20 20 20 20 20 20 20 Sửa Thành công (lần) 20 20 20 18 19 17 19 18 18 18 16 12 11 11 12 Thất bại (lần) 0 0 0 2 1 3 1 2 2 2 4 8 9 9 8 Bảng 2. Thống kê các tấn công với số lần tấn công là 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 52 - KẾT LUẬN VÀ KIẾN NGHỊ Như vậy, để tiến hành thuỷ vân và giải mã thuỷ vân cơ sở dữ liệu quan hệ, quá trình thực hiện cần được tiến hành qua hai phần chính là nhúng thuỷ vân và giải mã thuỷ vân đã nhúng. Việc nhúng thuỷ vân được thực hiện thông qua ba bước nhỏ đó là: Phân hoạch bộ dữ liệu, nhúng thuỷ vân vào các phân hoạch và tính toán ngưỡng tối ưu giải mã. + Mục đích của phân hoạch là chia nhỏ bộ dữ liệu thành các nhóm bản ghi (phân hoạch) sao cho trong mỗi nhóm các bản ghi được chọn trong cơ sở dữ liệu là ngẫu nhiên. Để tăng tính ngẫu nhiên và đảm bảo tính bí mật trong quá trình lựa chọn các bản ghi khi phân vào mỗi phân vùng thì quá trình phân hoạch được thực hiện với hàm băm mật mã (HMAC). Một số dạng hàm băm đáp ứng được các tiêu chí này có thể được áp dụng như MD5, SHA-0, SHA- 1… Việc lựa chọn hàm băm cũng có ảnh hưởng đến tốc độ tính toán khi phân hoạch dữ liệu, điều này tuỳ thuộc vào số word được lựa chọn khi sử dụng các hàm băm này. + Việc nhúng thuỷ vân sẽ được tính toán một cách hợp lý để đảm bảo những thay đổi trong dữ liệu là trong giới hạn cho phép. Thuật toán GA được áp dụng trong phần này nhằm tính toán các giá trị tối ưu để chèn các bit vào các phân hoạch. Việc giải bài toán tối ưu áp dụng giải thuật GA nhằm đưa ra hai tập thống kê Xmax và Xmin sao cho các phân phối trên hai tập này là cách xa nhau, điều này sẽ giúp làm cực tiểu hoá lỗi giải mã, đồng thời cũng là điểm mấu chốt giúp cho kỹ thuật thuỷ vân này đàn hồi hơn trước các tấn công thông thường. + Căn cứ vào hai tập thống kê Xmax và Xmin được lưu lại trong quá trình nhúng bit thuỷ vân, nguyên tắc xác suất thống kê được áp dụng để tính toán ra Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 53 - ngưỡng giải mã tối ưu cho bài toán này. Việc chọn ngưỡng giải mã tối ưu sẽ có ảnh hưởng rất lớn đến tính chính xác của quá trình giải mã, đặc biệt là trong trường hợp dữ liệu đã thuỷ vân bị tấn công. Quá trình giải mã thuỷ vân cũng được thực hiện qua ba bước là: Phân hoạch bộ dữ liệu đã nhúng thuỷ vân, giải mã thuỷ vân, và bình chọn theo đa số. Trong quá trình giải mã thuỷ vân này sẽ sử dụng một số tham số của quá trình nhúng thuỷ vân như các tham số bí mật (số phần phân hoạch, khoá bí mật), các tập thống kê Xmax, Xmin. Với kỹ thuật giải mã dùng phương pháp bình chọn theo đa số thì quá trình giải mã không cần thông tin về dữ liệu gốc những vẫn có thể giải mã ra được thuỷ vân đã nhúng. Mặc dù kỹ thuật thuỷ vân sử dụng GA để giải bài toán tối ưu trong trường hợp này là rất phù hợp, tuy nhiên kỹ thuật GA này chỉ áp dụng trong những ứng dụng với các bài toán không lồi, không tuyến tính cao và không yêu cầu quá khắt khe về thời gian tính toán. Kỹ thuật GA cần được nghiên cứu thêm để cải tiến về tốc độ tính toán cũng như làm giải quyết vấn đề tối ưu hoá tốt hơn nữa. Hướng nghiên cứu tiếp theo để phát triển đề tài theo tác giả đề nghị là: + Cải tiến hàm giấu để GA hội tụ nhanh hơn nhằm làm tăng tốc độ nhúng thuỷ vân. + Cải tiến cách sinh sản của các cá thể trong quần thể để GA có được những kết quả tối ưu tốt hơn. + Cải tiến hàm đánh giá của GA để có được sự đa dạng các cá thể trong quần thể của GA nhằm thu được các cá thể tốt hơn sau mỗi lần tiến hoá. + Nghiên cứu giải pháp để tránh trường hợp tối ưu cục bộ (giả tối ưu). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 54 - PHỤ LỤC Các hàm băm được ứng dụng trong nhiều lĩnh vực, chúng thường được thiết kế phù hợp với từng ứng dụng. Một hàm băm tốt là một phép biến đổi "một chiều", nghĩa là không có một phương pháp thực tiễn để tính toán được dữ liệu vào nào đó tương ứng với giá trị băm mong muốn, khi đó việc giả mạo sẽ rất khó khăn. Một hàm một chiều mật mã học điển hình không có tính chất hàm đơn ánh và tạo nên một hàm băm hiệu quả. Các hàm băm dành cho việc phát hiện và sửa lỗi tập trung phân biệt các trường hợp mà dữ liệu đã bị làm nhiễu bởi các quá trình ngẫu nhiên. Khi các hàm băm được dùng cho các giá trị tổng kiểm, giá trị băm tương đối nhỏ có thể được dùng để kiểm chứng rằng một file dữ liệu có kích thước tùy ý chưa bị sửa đổi. Hàm băm được dùng để phát hiện lỗi truyền dữ liệu. Tại nơi gửi, hàm băm được tính cho dữ liệu được gửi, giá trị băm này được gửi cùng dữ liệu. Tại đầu nhận, hàm băm lại được tính lần nữa, nếu các giá trị băm không trùng nhau thì lỗi đã xảy ra ở đâu đó trong quá trình truyền. Việc này được gọi là kiểm tra dư (redundancy check). * Hàm băm MD5 (Message-Digest algorithm 5) MD5 là một hàm băm để mã hoá với giá trị băm là 128bit. Từng được xem là một chuẩn trên Internet, MD5 đã được sử dụng rộng rãi trong các chương trình an ninh mạng, và cũng thường được dùng để kiểm tra tính nguyên vẹn của tập tin. MD5 được thiết kế bởi Ronald Rivest vào năm 1991 để thay thế cho hàm băm trước đó, MD4 (cũng do ông thiết kế, trước đó nữa là MD2). MD5 có 2 ứng dụng quan trọng: 1/ MD5 được sử dụng rộng rải trong thế giới phần mềm để đảm bảo rằng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 55 - tập tin tải về không bị hỏng. Người sử dụng có thể so sánh giữa thông số kiểm tra phần mềm bằng MD5 được công bố với thông số kiểm tra phần mềm tải về bằng MD5. 2/ MD5 được dùng để mã hoá mật khẩu. Mục đích của việc mã hoá này là biến đổi một chuổi mật khẩu thành một đoạn mã khác, sao cho từ đoạn mã đó không thể nào lần trở lại mật khẩu. Có nghĩa là việc giải mã là không thể hoặc phải mất một khoãng thời gian rất dài (đủ để làm nản lòng kẻ tấn công). Thuật giải MD5 biến đổi một thông điệp có chiều dài bất kì thành một khối có kích thước cố định 128 bits. Thông điệp đưa vào sẽ được cắt thành các khối 512 bits. Thông điệp được đưa vào bộ đệm để chiều dài của nó sẽ chia hết cho 512. Bộ đệm hoạt động như sau: - Trước tiên nó sẽ chèn bit 1 vào cuối thông điệp. - Tiếp đó là hàng loạt bit Zero cho tới khi chiều dài của nó nhỏ hơn bội số của 512 một khoảng 64 bit . - Phần còn lại sẽ được lấp đầy bởi một số nguyên 64 bit biểu diễn chiều dài ban đầu của thông điệp. Thuật toán chính của MD5 hoạt động trên một bộ 128 bit. Chia nhỏ nó ra thành 4 từ 32 bit, kí hiệu là A,B,C và D. Các giá trị này là các hằng số cố định. Sau đó thuật toán chính sẽ luân phiên hoạt động trên các khối 512 bit. Mỗi khối sẽ phối hợp với một bộ. Quá trình xữ lý một khối thông điệp bao gồm 4 bước tương tự nhau, gọi là vòng (“round”). Mỗi vòng lại gồm 16 quá trình tương tự nhau dựa trên hàm một chiều F, phép cộng module và phép xoay trái… Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 56 - Hình bên dưới mô tả một quá trình trong một vòng. Có 4 hàm một chiều F có thể sử dụng. Mỗi vòng sử dụng một hàm khác nhau. Hàm băm MD5 (còn được gọi là hàm tóm tắt thông điệp - message degests) sẽ trả về một chuỗi số thập lục phân gồm 32 số liên tiếp. Dưới đây là các ví dụ mô tả các kết quả thu được sau khi băm. MD5("K6CH") = 56861ffa22479429ba47cffeca03304e MD5("k6ch") = 11df758de80935b75b2a7bc1479aa164 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 57 - TÀI LIỆU THAM KHẢO [1]. “Nghiên cứu và Phát triển Kỹ thuật Thuỷ vân Cơ sở Dữ liệu Quan hệ”, Báo cáo kết quả nghiên cứu của đề tài cơ sở 2008, 12/2008, Phòng CSDL & LT. [2]. Bùi Thế Hồng, Nguyễn Thị Thu Hằng, Lƣu Thị Bích Hƣơng, “Thủy vân cơ sở dữ liệu quan hệ”, Tạp chí Khoa học & Công nghệ, ĐH Thái Nguyên, 2009. [3]. Vũ Ba Đình, “Giấu thông tin trong cơ sở dữ liệu không gian”, Tạp chí nghiên cứu khoa học kỹ thuật và công nghệ Quân sự, số 4, 30-37 [4]. Vũ Ba Đình, Nguyễn Xuân Huy, “Thuộc tính chẵn lẻ áp dụng trong kỹ thuật giấu tin bền vững”, Kỷ yếu Hội thảo FAIR: Nghiên cứu cơ bản và ứng dụng CNTT, NXB KHKT Hà Nội, 2004. [5]. Hoàng Kiếm, “Giải thuật di truyền - Cách giải các bài toán tự nhiên trên máy tính”, NXB Khoa học kỹ thuật, 2000. [6]. Nguyễn Đình Thúc, “Trí tuệ nhân tạo – Lập trình tiến hoá”, Nhà xuất bản Giáo dục. [7]. R. Agrawal, J. Kiernan, “Watermarking Relational Databases” in Proceedings of the 28th VLDB Conference, Hong Kong, China, 2002. [8]. R. Agrawal, P. J. Haas, and J. Kiernan. “Watermarking relational data: framework, algorithms and analysis*”. The VLDB Journal (2003). [9]. R. Sion, M. Atallah, S. Prabhakar.“Watermarking Relational Databases” CERIAS TR 2002-28*. Center for Education and Research in Information Assurance, Computer Sciences, Purdue University, 2002. [10]. R. Sion, M. Atallah, and S. Prabhakar. “Rights Protection for Relational Data”. IEEE Transactions on Knowledge and Data Engineering, 16(6), June 2004. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 58 - [11]. R. Sion, “Proving ownership over categorical data”. ICDE 2004. [12]. E. Bertino, B.C Ooi, Y.Yang, and R. Deng, “Privacy and ownership preserving of outsourced medical data”. ICDE 2005. [13]. Y. Li, H. Guo, and S. Jajodia, “Tamper Detection and Localization for Categorical Data Using Fragile Watermarks”. DRM 2004 [14]. H. Guo, Y. Li, A. Liu, and S. Jajodia, “A Fragile Watermarking Scheme for Detecting Malicious Modifications of Database Relations”. IS 2006 [15]. R. Sion, M. Atallah, and S. Prabhakar, “Rights Protection for Relational Data”. SIGMOD 2003. [16]. Y. Li, V. Swarup, and S. Jajodia, “Fingerprinting Relational Databases: Schemes and Specialties”. TDSC 2005 [17]. Y. Li, H. Guo, and S. Wang, “A Multi-Bit Watermark for Relational Data”. JDM 2007 [18]. Y. Li and R. Deng, “Publicly Verifiable Ownership Protection for Relational Databases”. ASIACCS 2006 [19]. Y. Li, V. Swarupand S. Jajodia, “Constructing a Virtual Primary Key for Fingerprinting Relational Data”. DRM 2003 [20]. J. Guo, Y. Li, R. Deng, and K. Chen, “Rights Protection for Data Cubes”. ISC 2006 [21]. R. Sion, M. Atallah, and S. Prabhakar, “Resilient Rights Protection for Sensor Streams”. VLDB 2004 [22]. M. Shehab, E. Bertino, A. Ghafoor. “Watermarking Relational Databases using Optimization Based Techniques”. CERIAS Tech Report 2006-41. [23]. MichaelArnold, MartinSchmucker, StephenD.Wolthusen, “Techniques and Applications of Digital Watermarking and ContentProtection”, ISBN1-58053-111-3, Tr. 15-53, 2003. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 59 - [24]. Saraju P. Mohanty, “Digital Watermarking : A Tutorial Review”, Dept of Comp Sc and Eng, Unversity of South Florida. 2001. [25]. J.J. Eggers, “Information embedding and digital watermarking”, Standford University, 2002. [26]. Juergen Seitz University of Cooperative Education Heidenheim, Germany, “Digital watermarking for digital media”, ISBN 1-59140-520-3. Tr. 1-35. [27]. YingjiuLi, “Database Watermarking: A Systematic View”, 2008. [28]. f5e5c5b595f5e [29]. [30]. www.watermarkingworld.org.