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

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