Thủy văn cơ sở dữ liệu quan hệ

52(4): 56 - 59<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 4 - 2009<br /> <br /> THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ<br /> Bùi Thế Hồng, Nguyễn Thị Thu Hằng (Viện Công nghệ Thông tin)<br /> Lưu Thị Bích Hương (Đại học Sư Phạm Hà Nội 2)<br /> Tóm tắt<br /> Trong báo cáo này, chúng tôi trình bày một kết quả nghiên cứu về kỹ thuật thủy vân hiệu quả sử dụng<br /> các bit ít ý nghĩa nhất (LSB) của một số giá trị thuộc tính và tiến hành thử nghiệm, đánh giá thuật toán đã<br /> cài đặt đối với một số phép toán cập nhật và tấn công thông thường trên cơ sở dữ liệu. Các kết quả thử<br /> nghiệm cho thấy, thuật toán thủy vân cơ sở dữ liệu dựa vào các LSB là bền vững đối với các tấn công<br /> thêm và bớt các bộ nhưng không bền vững đối với các tấn công sửa đổi các giá trị thuộc tính.<br /> <br /> I. Giới thiệu<br /> Bảo vệ bản quyền, nhận thực thông tin, nhận<br /> dạng các đặc trưng duy nhất của dữ liệu quan hệ<br /> hiện đang là một nhu cầu cấp thiết và là thách thức<br /> mới đối với các kỹ thuật thuỷ vân trên cơ sở dữ<br /> liệu quan hệ. Việc quản lý bản quyền các dữ liệu<br /> quan hệ bằng thuỷ vân đã và đang trở thành một<br /> chủ đề quan trọng trong các nghiên cứu về cơ sở<br /> dữ liệu. Thuỷ vân các dữ liệu quan hệ có những<br /> thách thức kỹ thuật đáng kể và có các ứng dụng<br /> thực tế có ý nghĩa xứng đáng được quan tâm thích<br /> đáng từ phía cộng đồng những người nghiên cứu<br /> cơ sở dữ liệu.<br /> Trong báo cáo này, chúng tôi trình bày một kết<br /> quả nghiên cứu về kỹ thuật thủy vân sử dụng các<br /> bit ít ý nghĩa nhất (LSB) của một số giá trị thuộc<br /> tính và tiến hành thử nghiệm, đánh giá thuật toán<br /> đã cài đặt đối với một số tấn công thông thường<br /> trên cơ sở dữ liệu.<br /> II. Kỹ thuật thuỷ vân sử dụng các bít ít ý nghĩa<br /> nhất<br /> Các bít ít ý nghĩa nhất (LSB – Least<br /> Significant Bits) ở đây là các bít ở bên phải nhất<br /> của một chuỗi bít. Ví dụ, trong chuỗi bít 1110 thì<br /> bít ít ý nghĩa nhất là 0, hoặc với số bít ít ý nghĩa<br /> nhất là 3 thì số bít ít ý nghĩa nhất trong chuỗi bít<br /> 1000101 là 101.<br /> Kỹ thuật LSB này chỉ đánh dấu các thuộc tính<br /> kiểu số và giả thiết là các thuộc tính được đánh<br /> dấu này có thể chấp nhận những thay đổi nhỏ ở<br /> một số giá trị và những thay đổi nhỏ này không lộ<br /> rõ. Tất cả các thuộc tính số của một quan hệ không<br /> nhất thiết đều phải được đánh dấu. Người chủ của<br /> <br /> dữ liệu này sẽ quyết định thuộc tính nào là phù<br /> hợp cho việc đánh dấu.<br /> Việc đánh dấu ở đây tức là chọn ra các bộ, các<br /> thuộc tính và các giá trị tương ứng với các bộ, các<br /> thuộc tínhđó. Sau đó, ta sẽ thay đổi các bít ít ý<br /> nghĩa nhất của giá trị đó. Những thay đổi này sẽ<br /> tạo thành thuỷ vân.<br /> Ý tưởng cơ bản của kỹ thuật này là đảm bảo tại<br /> một số vị trí bít của một số thuộc tính trong một số<br /> bộ có chứa các giá trị nhất định. Các bộ, các thuộc<br /> tính trong một bộ, các vị trí bít trong một thuộc<br /> tính và các giá trị bít nhất định này đều phải được<br /> xác định một cách chính xác và logic dưới sự kiểm<br /> soát của một khoá bí mật K của chủ nhân quan hệ.<br /> Mẫu bít này sẽ hình thành ra thuỷ vân. Chỉ duy<br /> nhất chủ nhân của khoá bí mật mới có thể tìm lại<br /> được thuỷ vân với xác suất cao.<br /> 1.Mô hình thuỷ vân<br /> Giả sử có một quan hệ R với lược đồ R(P, A0 , .<br /> . . , Av-1), trong đó P là thuộc tính khoá chính, A0 , .<br /> . . , Av-1 là  thuộc tính đều có thể được chọn để<br /> thuỷ vân. Chúng đều là các thuộc tính kiểu số và<br /> các giá trị của chúng có tính chất là những thay đổi<br /> ở  bít ít ý nghĩa nhất của chúng đều không cảm<br /> nhận được. Ký hiệu r.Ai là giá trị của thuộc tính Ai<br /> trong bộ r  R .<br />  là một tham số điều khiển xác định số các bộ<br /> cần được đánh dấu,     . Người ta có thể cân<br /> đối<br /> với  để xác định mức độ của các sai số<br /> được sinh ra trong các giá trị của một thuộc tính.<br /> Nếu ít bộ hơn được đánh dấu thì có khả năng phải<br /> đưa vào những thay đổi lớn hơn trong các giá trị<br /> của các thuộc tính được đánh dấu.<br /> <br /> <br /> <br /> 1<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 52(4): 56 - 59<br /> <br /> Nhúng<br /> thuỷ vân<br /> <br /> Dữ liệu được<br /> thuỷ vân, RW<br /> <br /> Kênh tấn<br /> công<br /> <br /> Dữ liệu bị<br /> <br /> 4 - 2009<br /> <br /> Phát hiện<br /> thuỷ vân<br /> <br /> tấn công , R’W<br /> <br /> Dữ liệu, R<br /> Khoá bí mật, K<br /> <br /> Thuỷ vân được phát hiện<br /> <br /> Hình 1: Mô hình thuỷ vân sử dụng các bít ít ý nghĩa nhất<br /> <br /> 2. Thuật toán nhúng thuỷ vân<br /> Ký hiệu<br /> <br /> Mô tả<br /> <br /> <br /> <br /> Số các bộ trong quan hệ<br /> <br /> <br /> <br /> Số các thuộc tính trong quan hệ sẵn<br /> sàng để đánh dấu<br /> <br /> <br /> <br /> Số các bit ít ý nghĩa nhất sẵn sàng để<br /> đánh dấu trong một thuộc tính<br /> <br /> 1<br /> <br /> Tỷ lệ các bộ được đánh dấu<br /> <br /> <br /> <br /> Số các bộ được đánh dấu<br /> <br /> <br /> <br /> Mức ý nghĩa của phép thử để phát<br /> hiện một thủy vân<br /> <br /> <br /> <br /> Số lượng tối thiểu các bộ được đánh<br /> dấu một cách đúng đắn cần thiết để<br /> phát hiện thuỷ vân.<br /> <br /> Hình 2: Các ký hiệu được dùng trong kỹ thuật LSB<br /> <br /> 2.1 Mã chứng thực thông điệp<br /> Mã chứng thực thông điệp (MAC – Message<br /> Authenticated Code) là hàm băm một chiều phụ<br /> thuộc vào khoá.<br /> Hàm băm một chiều H là hàm thao tác trên<br /> một thông điệp đầu vào có độ dài tuỳ ý M và trả<br /> lại một giá trị băm có độ dài cố định h, tức là h =<br /> H(M). Hàm này có thêm các đặc điểm sau:<br /> Với M đã cho, thì có thể dễ dàng tính được h<br /> Với h đã cho, thì khó có thể tính được M để<br /> H(M) = h<br /> Với M đã cho, thì khó có thể tìm được một<br /> thông điệp khác M0 để H(M) = H(M0).<br /> <br /> MD5 và SHA là hai lựa chọn tốt cho H.<br /> Cho F là một MAC dùng để ngẫu nhiên hoá<br /> các giá trị của thuộc tính khoá chính r.P của bộ<br /> r và trả lại một giá trị nguyên trong một miền<br /> rộng. F được gieo giống với một khoá bí mật K chỉ<br /> người chủ dữ liệu được biết. Ta có thể sử dụng<br /> hàm MAC được coi là an toàn như sau:<br /> F(r.P) = H(K o H(K o r.P))<br /> trong đó: o biểu diễn phép ghép.<br /> 2.2 Thuật toán<br /> Input: Khoá bí mật K chỉ có chủ cơ sở dữ liệu<br /> biết, và các tham số  ,  ,  cũng được chủ cơ sở<br /> dữ liệu xác định.<br /> Output: Bộ dữ liệu được thuỷ vân.<br /> Với mỗi bộ r  R thì<br /> 1. nếu (F(r.P) mod  = = 0) // đánh dấu bộ này<br /> 2. i = F(r.P) mod  //đánh dấu thuộc tính Ai<br /> 3. j = F(r.P) mod <br /> // đánh dấu bít thứ j<br /> 4. r.Ai = mark(r.P, r.Ai , j)<br /> 5. mark(primary_key pk, number v, bit_index j)<br /> trả lại number<br /> 6. first_hash = H( K o pk)<br /> 7. nếu (first_hash mod 2 = = 0)<br /> 8. đặt bít ít ý nghĩa nhất thứ j của v bằng 0,<br /> 9. ngược lại<br /> 10. đặt bít ít ý nghĩa nhất thứ j của v bằng 1.<br /> trả lại v<br /> Dòng 2 cho biết bộ đang xét có được chọn để<br /> đánh dấu không. Với một bộ được chọn, dòng 3 sẽ<br /> <br /> 2<br /> <br /> 52(4): 56 - 59<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> xác định thuộc tính nào sẽ được đánh dấu trong số<br />  thuộc tính ứng cử viên. Đối với thuộc tính đã<br /> chọn, dòng 4 xác định vị trí bít nào trong số  bít<br /> ít ý nghĩa nhất sẽ được đánh dấu.<br /> Thủ tục mark đặt bít đã chọn bằng 0 hoặc 1 tuỳ<br /> thuộc vào giá trị của hàm băm thu được từ dòng 7.<br /> Kết quả của dòng 9 (dòng 11) hoặc là giữ nguyên giá<br /> trị của thuộc tính hoặc giảm đi (tăng lên) 1. Tức là,<br /> việc thuỷ vân đơn giản chỉ làm giảm một số giá trị<br /> của một thuộc tính trong khi lại làm tăng một số giá<br /> trị khác và giữ nguyên một số không đổi.<br /> Các cơ sở dữ liệu thường cho phép các thuộc<br /> tính chấp nhận các giá trị null. Nếu trong quá trình<br /> đánh dấu mà gặp phải một giá trị null của thuộc<br /> tính đã chọn thì sẽ không đánh dấu giá trị này và<br /> giữ nguyên hiện trạng của nó.<br /> 2.3 Thuật toán phát hiện thuỷ vân<br /> Giả sử người chủ dữ liệu nghi ngờ quan hệ S<br /> do tên tấn công đưa ra có thể được ăn cắp từ quan<br /> hệ gốc R. Tập các bộ, và các thuộc tính trong S có<br /> thể là một tập con của R. Ta giả sử rằng tên tấn<br /> công không bỏ thuộc tính khoá chính hoặc thay<br /> đổi giá trị của khoá chính vì khoá chính chứa<br /> những thông tin có giá trị và việc thay đổi nó sẽ<br /> làm giảm ý nghĩa sử dụng của cơ sở dữ liệu theo<br /> quan điểm của người dùng.<br /> Input: Các tham số K,  ,  ,  có các giá trị như<br /> khi nhúng thuỷ vân,<br />  là mức ý nghĩa của phép thử do người phát<br /> hiện chọn trước.<br /> Output: Thuỷ vân được phát hiện.<br /> 1. totalcount = matchcount = 0<br /> 2. Với mỗi bộ s  S thì<br /> 3. nếu (F(s.P) mod  = = 0) // bộ này đã được<br /> đánh dấu<br /> 4. i = F(s.P) mod  // thuộc tính Ai đã được đánh<br /> dấu<br /> 5. j = F(s.P) mod  // bít thứ j đã được đánh dấu<br /> 6. totalcount = totalcount + 1<br /> 7. matchcount = matchcount + match(s.P, s.Ai, j)<br /> 8.  = threshold(totalcount,  )<br /> 9. nếu (matchcount   ) thì nghi ngờ bị ăn cắp<br /> 10. match(primary_key pk, number v, bit_index j)<br /> trả lại số nguyên<br /> <br /> 4 - 2009<br /> <br /> 11. first_hash = H(K o pk)<br /> 12. nếu (first_hash mod 2 = = 0)<br /> 13. trả lại 1 nếu bít ít ý nghĩa nhất thứ j của v là 0,<br /> ngược lại trả lại 0.<br /> 14. ngược lại<br /> 15. trả lại 1 nếu bít ít ý nghĩa nhất thứ j của v là<br /> 1, ngược lại trả lại 0.<br /> Thuật toán phát hiện thuỷ vân này mang tính<br /> xác suất với các phép thử ngẫu nhiên. Dòng 3 xác<br /> định liệu bộ s đang xét có phải đã được đánh dấu<br /> trong lúc nhúng thuỷ vân hay không. Dòng 4 và 5<br /> xác định thuộc tính và vị trí bít đã phải được đánh<br /> dấu. Sau đó, trình con match so sánh giá trị bít<br /> hiện tại với giá trị bít đã phải được đặt cho bít này<br /> khi nhúng thuỷ vân. Như vậy, cho đến dòng thứ 8<br /> ta sẽ biết được có bao nhiêu bộ được thử<br /> (totalcount) và có bao nhiêu bộ trong số đó chứa<br /> giá trị mong đợi (matchcount). Về mặt xác suất thì<br /> chỉ có một lượng tối thiểu nhất định các bộ có<br /> chứa các bít trùng với các bít đã đánh dấu. Giá trị<br /> matchcount được so sánh với số đếm tối thiểu tính<br /> được từ hàm ngưỡng đối với phép thử thành công<br /> ở mức ý nghĩa  đã chọn. Kỹ thuật này được<br /> phân tích, đánh giá bằng xác suất nhị thức tích lũy.<br /> - Xác suất nhị thức tích luỹ:<br /> Các phép thử độc lập lặp đi lặp lại được gọi là<br /> các phép thử Bernoulli nếu chỉ có hai kết quả có<br /> thể đối với mỗi phép thử và xác suất của chúng là<br /> như nhau trong suốt quá trình thử.<br /> Cho b(k; n, p) là xác suất mà n phép thử<br /> Bernoulli với xác suất thành công là p và xác<br /> suất thất bại là q  1  p trong k lần thành công<br /> và n  k lần thất bại.<br /> n<br /> (1)<br /> b(k ; n, p)    p k q n k<br /> k<br /> <br /> n<br /> n!<br /> 0  k  n (2)<br /> <br />  <br /> <br /> <br /> k <br /> <br /> k!(n  k )!<br /> <br /> Ký hiệu số lần thành công trong n lần thử là<br /> Sn. Xác suất để có ít nhất k lần thành công trong<br /> n lần thử, còn gọi là xác suất nhị thức tích luỹ,<br /> được tính như sau: n<br /> PS n  k   b(i; n, p)<br /> (3)<br /> i k<br /> Để ngắn gọn, ta địnhnnghĩa:<br /> B(k; n, p) :=  b(i; n, p)<br /> (4)<br /> i k<br /> - Hàm ngưỡng:<br /> <br /> <br /> <br /> 3<br /> <br /> 52(4): 56 - 59<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Giả sử khi chạy thuật toán phát hiện thuỷ<br /> vân, totalcount =  . Điều này có nghĩa là chủ<br /> dữ liệu xem xét ở  bít và quan sát số các bít<br /> mà giá trị của chúng trùng với giá trị được gán<br /> bởi thuật toán nhúng.<br /> Xác suất để có ít nhất  bít trong  bít ngẫu<br /> nhiên - với đặc điểm là mỗi bít bằng 0 hoặc bằng 1<br /> với xác suất như nhau, độc lập với các bít khác –<br /> trùng với giá trị đã được gán là B(  ;  , 1/2). Nói<br /> cách khác, xác suất để ít nhất  bít trùng khớp với<br /> cơ hội ngang bằng nhau là B(  ;  , 1/2). Do đó,<br /> thủ tục con:<br /> Subroutine threshold(  ,  ) return count<br /> trả lại  nhỏ nhất sao cho B(  ;  , 1/2)   .<br />  = min { t : B( t ;  , 1/2 )   }.<br /> III. Thử nghiệm và kết luận<br /> Chúng tôi đã tiến hành cài đặt kỹ thuật LSB<br /> này với quan hệ cơ sở dữ liệu thử nghiệm gồm 150<br /> bộ và 12 thuộc tính. Chẳng hạn, chọn số bít ít ý<br /> nghĩa nhất là 1, số thuộc tính sẵn sàng để đánh dấu<br /> là 12, và tham số điều khiển xác định số bộ cần<br /> đánh dấu là 10 thì kết quả thu được có 18 bộ được<br /> đánh dấu. Khi chưa có tấn công gì, thuật toán phát<br /> hiện cũng cho ta kết quả là matchcount =<br /> totalcount = 18.<br /> Khi thêm một số bộ dữ liệu mới vào thì kết<br /> quả cũng thu được là matchcount = totalcount =<br /> 18 và thử với các mức ý nghĩa  khác nhau thì sẽ<br /> cho ta các ngưỡng  như sau:<br />  = 0.1<br /> <br /> thì  = 13 < matchcount<br />  = 0.01 thì  = 15 < matchcount<br /> <br />  = 0.001 thì  = 16 < matchcount<br /> <br />  = 0.0001 thì  = 17 < matchcount<br /> <br /> Khi thay đổi một số giá trị thuộc tính thì:<br /> matchcount = 14 < totalcount = 18, và với  =<br /> 0.1 thì  = 13 < matchcount, với  = 0.01 thì <br /> = 15 > matchcount<br /> Với tấn công thêm thì hầu như không có thay<br /> đổi gì đáng kể tới dữ liệu đã được thủy vân. Còn<br /> với tấn công thay đổi thì có ảnh hưởng đáng kể tới<br /> dữ liệu đã được nhúng và có thể làm mất thủy vân.<br /> Như vậy, kỹ thuật LSB này bền vững đối với<br /> tấn công thêm (bớt) hơn đối với tấn công thay đổi.<br /> Chúng tôi dự định tiếp tục nghiên cứu, tìm ra<br /> những kỹ thuật thủy vân bền vững hơn và tiến<br /> <br /> 4 - 2009<br /> <br /> hành cài đặt chúng trên dữ liệu thực để có thể áp<br /> dụng vào thực tiễn.<br /> Tài liệu tham khảo<br /> [1]. Phạm Hữu Khang, Đoàn Thiện Ngân, Hoàng Đức<br /> Hải, “C# 2005 Lập trình cơ bản”, NXB Lao động xã<br /> hội (2006).<br /> [2]. R. Agrawal, J. Kiernan, “Watermarking Relational<br /> Databases” in Proceedings of the 28th VLDB<br /> Conference, Hong Kong, China, 2002.<br /> [3].R. Agrawal, P. J. Haas, and J. Kiernan.<br /> “Watermarking relational data: framework, algorithms<br /> and analysis*”. The VLDB Journal (2003).<br /> [4]. M. Shehab, E. Bertino, A. Ghafoor. “Watermarking<br /> Relational Databases using Optimization Based<br /> Techniques”. CERIAS Tech Report 2006-41.<br /> <br /> 4<br /> <br /> 52(4): 3 - 12<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 4 - 2009<br /> <br /> Summary<br /> In the paper, we presented a research result on the effective watermark technique based on the least significant bits<br /> of some numerical attributes of a relation and implemented an exprimental program for evaluating the robustness of<br /> the technique against update operation and some attacks. The experimetal resuls show that the technique based on<br /> LSB is robust against the deletion and the addition of tuples but not robust against the change operation.<br /> <br /> 5<br /> <br />