Đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ với các dữ liệu kiểu văn bản bằng kỹ thuật thủy vân

Tạp chí Tin học và Điều khiển học, T.30, S.1 (2014), 52–62
ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ
VỚI CÁC DỮ LIỆU KIỂU VĂN BẢN BẰNG KỸ THUẬT THỦY VÂN
LƯU THỊ BÍCH HƯƠNG1, BÙI THẾ HỒNG2
1Khoa Công nghệ thông tin, Trường ĐHSP Hà Nội 2; {luuthibichhuong@hpu2.edu.vn}
2Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học & Công nghệ Việt Nam;
{hong@ioit.ac.vn}
Tóm tắt. Bài báo này đề xuất một lược đồ thủy vân mới dùng để đảm bảo sự toàn vẹn cho các cơ
sở dữ liệu quan hệ có các thuộc tính kiểu văn bản. Lược đồ này tạo ra một thủy vân từ các âm tố và
các ký tự đặc biệt của các thuộc tính để nhúng vào một thuộc tính kiểu văn bản có tác động thấp.
Việc chèn một vài ký tự thủy vân không làm ảnh hưởng nhiều tới giá trị của các thuộc tính tác động
thấp nhưng lại giúp phát hiện được các giả mạo và xuyên tạc trong cơ sở dữ liệu đã được thủy vân.
Từ khóa. Thủy vân, thuộc tính không phải số.
Abstract. The paper proposes a new watermarking scheme for integrity protection of relational
databases with text data. This scheme generates a watermark from the vowels, consonants and special
characters of the text attributes then embeds into attributes which are low impact. The embedded
characters do not affect much for these attributes but can help for detection any tempering in the
relation database.
Key words. Watermark, non-Numeric attribute.
1. GIỚI THIỆU
Ngày nay, việc sử dụng các cơ sở dữ liệu (CSDL), đặc biệt là CSDL quan hệ trong các
ứng dụng ngày càng tăng. Tốc độ phát triển Internet và các công nghệ có liên quan hiện đang
đưa đến một sức ép khá nặng nề cho những người bảo vệ dữ liệu trong việc tạo ra các dịch vụ
(thường được gọi là các dịch vụ Web hoặc các tiện ích điện tử) cho phép người dùng có thể
tìm kiếm và truy cập cơ sở dữ liệu từ xa hoặc trong các dịch vụ thuê khoán bên ngoài. Mặc
dù các xu hướng này là hữu ích cho người dùng cuối nhưng nó cũng bộc lộ mối nguy hiểm
cho những nhà cung cấp dữ liệu trước những kẻ trộm cắp và giả mạo dữ liệu. Do đó, những
nhà cung cấp dữ liệu đòi hỏi phải có các công cụ hỗ trợ cho việc bảo vệ bản quyền sản phẩm
của họ, nhận dạng được những bản sao các cơ sở dữ liệu bị đánh cắp hoặc bị xuyên tạc với ý
đồ xấu [1].
Một trong những công cụ rất hữu ích dùng để bảo vệ bản quyền và chống giả mạo đối với
các cơ sở dữ liệu quan hệ đó là kỹ thuật thủy vân số [1, 9, 10]. Hiện tại, đã có khá nhiều lược
đồ thủy vân được đề xuất, trong đó có thể chia thành hai lớp. Một lớp là các lược đồ thủy vân
dùng để bảo vệ bản quyền cho các cơ sở dữ liệu quan hệ, điển hình là lược đồ thủy vân dựa
vào các bit ít ý nghĩa nhất (LSB) [11], lược đồ thủy vân dựa vào các bit ý nghĩa nhất (MSB)
ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ 53
[2] và lược đồ thủy vân dựa vào phương pháp tối ưu hóa các ràng buộc [8]. Lớp thứ hai là các
lược đồ thủy vân dùng để đảm bảo sự toàn vẹn cho các cơ sở dữ liệu quan hệ, như lược đồ
thủy vân với dữ liệu phân loại [6], lược đồ thủy vân với dữ liệu kiểu số [5], hay lược đồ thủy
vân với dữ liệu không phải kiểu số [3]. Trong bài báo [10] chúng tôi đã tiến hành nghiên cứu
vấn đề này và đã đề xuất được một lược đồ thủy vân dễ vỡ dùng để phát hiện các giả mạo
trong các cơ sở dữ liệu quan hệ. Đây là một lược đồ dùng để đảm bảo sự toàn vẹn và khoanh
vùng các giả mạo trong những cơ sở dữ liệu quan hệ với các thuộc tính là kiểu số. Tuy nhiên,
trong thực tế lại có khá nhiều cơ sở dữ liệu quan hệ mà các dữ liệu của chúng lại có các kiểu
không phải kiểu số [3, 6], ví dụ như kiểu văn bản, kiểu memo,... Bài báo này sẽ nghiên cứu
việc đảm bảo sự toàn vẹn cho các cơ sở dữ liệu có các thuộc tính kiểu văn bản bằng thủy vân.
Trong [3], đã đưa ra một lược đồ thủy vân cho dữ liệu không phải số. Lược đồ này đã sử
dụng một khóa bí mật được xây dựng từ các bộ trong quan hệ và các thuộc tính tác động
thấp. Tuy nhiên, nếu biết được thuật toán sinh khóa thì có thể dễ dàng tìm được khóa bí mật
cũng như ma trận thủy vân và vì thế lược đồ này tỏ ra không mấy an toàn.
Khắc phục những nhược điểm đó, bài báo sẽ đề xuất một lược đồ thủy vân mới dùng để
bảo vệ sự toàn vẹn cho các cơ sở dữ liệu quan hệ với dữ liệu kiểu văn bản. Trong lược đồ này,
việc tính ma trận thủy vân dựa vào tư tưởng của [3]. Điểm khác biệt giữa hai lược đồ là lược
đồ đề xuất đưa thêm vào một tham số khóa thủy vân và một phương pháp mới dùng để xác
định các bộ được nhúng.
Trong phần tiếp theo bài báo sẽ trình bày một số định nghĩa cần thiết cho quá trình xây
dựng các thuật toán. Mục 3 trình bày tư tưởng của lược đồ mới, các thuật toán nhúng thủy
vân, phát hiện thủy vân và xác minh sự toàn vẹn của quan hệ. Mục 4 chứng minh tính đúng
đắn của các thuật toán và cuối cùng là phần kết luận.
2. MỘT SỐ ĐỊNH NGHĨA
Trong một lược đồ quan hệ, có một số thuộc tính có ý nghĩa quan trọng và một số thuộc
tính khác có ảnh hưởng không lớn đến giá trị sử dụng cũng như ý nghĩa thực tế. Sau đây sẽ
đưa ra hai định nghĩa để làm rõ hơn về các loại thuộc tính này.
Định nghĩa 1. (Thuộc tính có tác động cao) Một thuộc tính được gọi là thuộc tính tác động
cao hay còn gọi là thuộc tính có ý nghĩa quan trọng nếu nó không cho phép bất kỳ một thay
đổi nào.
Định nghĩa 2. (Thuộc tính có tác động thấp) Một thuộc tính được gọi là thuộc tính tác
động thấp hay còn gọi là thuộc tính ít ý nghĩa nếu nó chấp nhận những thay đổi nhỏ.
Ví dụ, trong một lược đồ quan hệ về nhân sự thì các thuộc tính số chứng minh thư, họ
tên, năm sinh, giới tính, ngày tăng lương là những thuộc tính quan trọng vì bất cứ một thay
đổi nào đối với các thuộc tính này đều ảnh hưởng tới đương sự. Các thuộc tính như quê quán,
nơi sinh có ảnh hưởng không lớn đối với đương sự, vì nếu giả sử có thêm một ký tự vào các
thuộc tính này thì cũng không dẫn đến hiểu lầm hoặc sai lệch nào.
3. LƯỢC ĐỒ THỦY VÂN
3.1. Tư tưởng của lược đồ
Như đã trình bày trong mục 1, có khá nhiều bài báo tập trung vào nghiên cứu các kỹ thuật
thủy vân cơ sở dữ liệu quan hệ có các thuộc tính kiểu số [1, 2, 4, 7] và mới chỉ có một số tác
giả nghiên cứu về thủy vân các CSDL quan hệ có các thuộc tính không phải kiểu số [5, 6].
54 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
Ý tưởng của lược đồ trong bài báo [3] là sinh một khóa bí mật dựa vào tất cả các thuộc
tính không phải số, sau đó nhúng khóa này vào các thuộc tính tác động thấp. Từ ý tưởng này
nhóm tác giả đã phát triển một lược đồ thủy vân mới, trong đó có các thuộc tính có ý nghĩa
quan trọng được chú ý bảo vệ.
Lược đồ này được xây dựng dựa vào một số nhận xét sau đây:
- Trong một lược đồ quan hệ, bao giờ cũng tồn tại một số thuộc tính có ý nghĩa quan trọng
và một số thuộc tính khác có ảnh hưởng không lớn đến giá trị sử dụng cũng như ý nghĩa thực
tế.
- Những thuộc tính có ý nghĩa quan trọng thường hay bị tấn công, xuyên tạc, vì vậy cần
phải phát hiện được những thay đổi đối với các giá trị của các thuộc tính này. Để làm được
điều đó, cần phải sinh ra được một xâu thủy vân có thể đặc trưng được cho các giá trị thuộc
tính có ý nghĩa quan trọng để nhúng vào các thuộc tính có ảnh hưởng không lớn đến giá trị
sử dụng và ý nghĩa thực tế. Khi có bất kỳ một thay đổi nào đối với giá trị của các thuộc tính
có ý nghĩa quan trọng thì giá trị đặc trưng của chúng cũng bị thay đổi theo. Đây chính là dấu
hiệu để có thể phát hiện xem cơ sở dữ liệu có còn toàn vẹn hay không.
Bảng 1. Các ký hiệu được sử dụng trong lược đồ thủy vân
Ký hiệu Ý nghĩa
R Lược đồ quan hệ
r Quan hệ r thuộc lược đồ R
ri Bộ thứ i của quan hệ r
ri.Lj Giá trị của thuộc tính Lj thuộc bộ ri
ω Số bộ trong quan hệ r
K Khóa thủy vân
n Số thuộc tính kiểu văn bản có tác động thấp trong quan hệ
m Số thuộc tính kiểu văn bản có tác động cao trong quan hệ
Hi Thuộc tính kiểu văn bản có tác động cao thứ i
Li Thuộc tính kiểu văn bản có tác động thấp thứ i
W Ma trận thủy vân
ei Giá trị thứ i trên đường chéo chính của ma trận thủy vân W
Wj Ký tự thủy vân thứ j
ATOC() Hàm chuyển mã ASCII thành ký tự
Substring(x, p, q) Hàm lấy ra q ký tự của x từ vị trí thứ p
- Việc nhúng thủy vân vào những thuộc tính có tác động thấp sẽ không làm ảnh hưởng
lớn đến ý nghĩa cũng như giá trị sử dụng của cơ sở dữ liệu. Để giữ bí mật cho thủy vân và
tăng độ nhạy cảm khi xác minh sự toàn vẹn của cơ sở dữ liệu cần phải sử dụng thêm một
khóa thủy vân và một hàm HASH.
Lược đồ thủy vân đề xuất được thiết kế để đảm bảo sự toàn vẹn cho các quan hệ thuộc
lược đồ quan hệ có dạng:
R(H1, H2, ...,Hm, L1, L2, ..., Ln)
trong đó, H1, H2, ...,Hm là các thuộc tính kiểu văn bản có tác động cao còn L1, L2, ..., Ln là
các thuộc tính kiểu văn bản có tác động thấp.
Trong lược đồ thủy vân đề xuất có sử dụng một số ký hiệu được liệt kê trong Bảng 1.
ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ 55
Lược đồ thủy vân dùng để đảm bảo sự toàn vẹn cho các cơ sở dữ liệu quan hệ có các thuộc
tính kiểu văn bản được thực hiện dựa vào 2 thuật toán:
- Thuật toán nhúng thủy vân vào quan hệ.
- Thuật toán phát hiện thủy vân và xác minh sự toàn vẹn.
3.2. Thuật toán nhúng thủy vân
3.2.1. Sinh thủy vân từ các bộ của quan hệ
Đầu tiên chúng ta sẽ sinh thủy vân từ các bộ của quan hệ bằng cách dựa vào khóa thủy
vân, các thuộc tính kiểu văn bản có tác động cao và các thuộc tính kiểu văn bản có tác động
thấp.
- Đối với m thuộc tính có tác động cao, tính tổng mã ASCII của tất cả các nguyên âm,
phụ âm và ký tự đặc biệt trong toàn bộ các thuộc tính [3] và ký hiệu cụ thể là:
V H =
∑
ij{
∑
ASCII của các nguyên âm thuộc ri.Hj , 1 ≤ i ≤ ω; 1 ≤ j ≤ m},
CH =
∑
ij{
∑
ASCII của các phụ âm thuộc ri.Hj , 1 ≤ i ≤ ω; 1 ≤ j ≤ m},
PH =
∑
ij{
∑
ASCII của các ký tự đặc biệt của ri.Hj , 1 ≤ i ≤ ω; 1 ≤ j ≤ m}.
- Đối với n thuộc tính kiểu văn bản có tác động thấp, tính tổng mã ASCII của các nguyên
âm, phụ âm, ký tự đặc biệt và tổng mã ASCII của tất cả các ký tự theo từng thuộc tính [3].
V Lj =
∑
i{
∑
ASCII của các nguyên âm của ri.Lj , 1 ≤ i ≤ ω},
CLj =
∑
i{
∑
ASCII của các phụ âm của ri.Lj , 1 ≤ i ≤ ω},
PLj =
∑
i{
∑
ASCII của các ký tự đặc biệt của ri.Lj , 1 ≤ i ≤ ω},
ALj =
∑
i{
∑
ASCII của tất cả ký tự của ri.Lj , 1 ≤ i ≤ ω}.
- Xây dựng một ma trận đặt tên là D bao gồm 4 hàng và n cột với các thành phần là
Di1, Di2, Di3, Di4 (với i = 1, 2, ..., n) được tính như sau [3]
Di1 = V
H + V Li ,
Di2 = C
H + CLi ,
Di3 = P
H + PLi ,
Di4 = A
L
i .
- Tiến hành chuẩn hóa ma trận D để thu được ma trận chuẩn hóa N theo công thức [3]
Nij =
Dij√∑
D2ij
.
- Xây dựng ma trận thủy vânW bằng cách nhân ma trận chuẩn hóa N với ma trận chuyển
vị NT của nó. Ma trận W thu được là một ma trận vuông kích thước 4 × 4 với các giá trị
trên đường chéo chính là e1, e2, e3, e4. Đây chính là các giá trị đặc trưng của ma trận này [3].
- Điểm khác của lược đồ đề xuất là dùng hàm HASH để băm các giá trị ej sau khi ghép
với khóa thủy vân K và chuyển các giá trị HASH thành các ký tự thủy vân Wj theo công thức
Wj = ATOC(HASH(ej‖K)MOD 224 + 32); j = 1, 2, 3, 4
trong đó, ATOC() là hàm chuyển mã ASCII thành ký tự tương ứng. Sở dĩ phải cộng thêm
32 là vì 31 ký tự đầu tiên trong bảng mã ASCII là các ký tự không in ra được. Khóa K là
bí mật và đối xứng, chỉ người chủ cơ sở dữ liệu được biết và được dùng ở cả quá trình nhúng
56 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
thủy vân và phát hiện thủy vân. Hàm HASH được sử dụng ở đây để đảm bảo rằng khi có
bất cứ một thay đổi nào xảy ra trong cơ sở dữ liệu thì các ký tự thủy vân Wj cũng thay đổi
theo. Đây chính là điều mong muốn đối với các lược đồ thủy vân dùng để đảm bảo sự toàn
vẹn của các cơ sở dữ liệu quan hệ.
3.2.2. Nhúng thủy vân vào các thuộc tính tác động thấp
Có thể có một số lựa chọn để nhúng các ký tự thủy vân đã sinh trên đây tùy thuộc vào
giá trị của n (số các thuộc tính kiểu văn bản có tác động thấp). Nếu n nhỏ hơn hoặc bằng 4
thì lấy n ký tự đầu tiên của thủy vân. Nếu n lớn hơn 4 thì lặp lại các ký tự thủy vân cho đủ
số n ký tự. Cụ thể là:
- Đầu tiên, tiến hành lựa chọn ký tự để nhúng vào trong thuộc tính:
+ Nếu n ≤ 4, đặt w∗i = Wi (i = 1, 2, ..., n).
+ Nếu n > 4, đặt w∗i = W(i MOD 4)+1 (i = 1, 2, ..., n).
- Sau đó, tiến hành xác định vị trí nhúng trong các thuộc tính bằng cách sử dụng hàm
HASH và khóa K.
3.2.3. Thuật toán nhúng thủy vân
Thuật toán 1 dưới đây là giả mã cho qui trình sinh thủy vân và qui trình nhúng thủy vân
vào các quan hệ thuộc lược đồ quan hệ R.
Thuật toán 1. Nhúng thủy vân
Input:
- Quan hệ r thuộc lược đồ R(H1, H2, ...,Hm, L1, L2, ...., Ln). Trong đó, H1, H2, ...,Hm là
các thuộc tính kiểu văn bản có tác động cao, còn L1, L2, ...., Ln là các thuộc tính kiểu văn bản
có tác động thấp.
- Khóa thủy vân K.
Output: Quan hệ r đã nhúng thủy vân.
1. V H = CH = PH = 0
2. for i = 1 to ω do // Tính tổng các mã ASCII của m thuộc tính tác động cao
3. for j = 1 to m do
4. V H = V H +
∑
ASCII của các nguyên âm thuộc ri.Hj
5. CH = CH +
∑
ASCII của các phụ âm thuộc ri.Hj
6. PH = PH +
∑
ASCII của các ký tự đặc biệt của ri.Hj
7. end for
8. end for
9. for j = 1 to n do
10. V Lj = C
L
j = P
L
j = A
L
j // Khởi tạo các tổng mã ASCII cho từng cột
11. for i = 1 to ω do // Tính tổng các mã ASCII cho từng thuộc tính tác động thấp
12. V Lj = V
L
j + ΣASCII của các nguyên âm của ri.Lj
13. CLj = C
L
j + ΣASCII của các phụ âm của ri.Lj
14. PLj = P
L
j + ΣASCII của các ký tự đặc biệt của ri.Lj
15. ALj = A
L
j + ΣASCII của tất cả ký tự của ri.Lj
16. end for
ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ 57
17. end for
18. for i = 1 to n do // Xây dựng ma trận D
19. Di1 = V
L
i + V
H
20. Di2 = C
L
i + C
H
21. Di3 = P
L
i + P
H
22. Di4 = A
L
i
23. end for
24. for i = 1 to n do // Tìm ma trận chuẩn hóa N của D và ma trận chuyển vị NT
25. for j = 1 to 4 do
26. Nij = Dij/SQRT(D
2
i1 + D
2
i2 + D
2
i3 + D
2
i4) // Chuẩn hóa
27. NTij = Nji // Chuyển vị
28. end for
29. end for
30. W = N ∗NT // Sinh các ký tự thủy vân
31. for j = 1 to 4 do
32. Wj= ATOC(HASH(ej‖K) MOD 224) + 32) //Ký tự thủy vân
33. end for
34. Sắp thứ tự Wj theo thứ tự từ điển
35. // Nhúng các ký tự thủy vân Wj vào các thuộc tính tác động thấp
36. XacDinhKyTuNhung(n) // Chọn ký tự trong xâu Wj để nhúng
37. ChuoiVTri = ExtractBit (HASH (K), ω)
38. for j = 1 to n do // Xác định các bộ được nhúng
39. for i = 1 to ω do
40. if (ChuoiVTri i = 1) then
41. Chèn w∗j vào ô ri.Lj
42. end if
43. end for
44. end for
Giả sử có trung bình p kí tự trong mỗi một thuộc tính của một bộ và mỗi bộ có m + n
thuộc tính. Khi đó, việc tính tổng các ký tự có trong một bộ tốn khoảng p(m+n) đơn vị thời
gian. Do p,m, n là hằng số đối với quan hệ nên độ phức tạp tính toán của Thuật toán 1 phụ
thuộc vào số bộ của quan hệ hay O(ω).
Trong Thuật toán 1 đã sử dụng hàm xác định các ký tự thủy vân được nhúng vào các
thuộc tính kiểu văn bản tác động thấp và hàm trích L bit từ xâu bit H.
Function XacDinhKyTuNhung(int n)
1. if n ≤ 4 then
2. for i = 1 to n do
3. w∗i = Wi
4. end for
5. else
58 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
6. for i = 1 to n do
7. w∗i = W(i MOD 4)+1
8. end for
9. end if
Function ExtractBit(H,L)
1. if length (H) ≥ L then
2. ChuoiVTri = {L bit trái nhất của H}
3. else m = L−length (H)
4. ChuoiVTri = H ghép với extractBits (H,m)
5. end if
6. Return ChuoiVTri
3.3. Phát hiện thủy vân và xác minh sự toàn vẹn
Quan hệ r sau khi nhúng thủy vân có thể lưu thông bình thường trong môi trường công
cộng. Khi có nghi ngờ về một sự xuyên tạc hay giả mạo nào đó đối với quan hệ này, người chủ
sở hữu quan hệ có thể tiến hành xác minh bằng thuật toán phát hiện thủy vân. Thuật toán
phát hiện thủy vân của lược đồ được xây dựng trên ý tưởng phát hiện mù và dựa vào khóa
thủy vân K đã được sử dụng khi nhúng thủy vân.
Giả sử r′ là một quan hệ thuộc lược đồ R. Cần kiểm tra xem r′ có phải là bản giả mạo
của quan hệ r đã thủy vân hay không. Thuật toán phát hiện thủy vân và xác minh sự toàn
vẹn được chia làm 2 phần cơ bản:
- Thực hiện qui trình sinh thủy vân trên r′ giống như đã thực hiện trên r trong thuật toán
nhúng thủy vân. Gọi các ký tự được sinh ra từ r′ là Wj với j = 1, 2, 3, 4.
- Theo các qui tắc nhúng thủy vân vào các thuộc tính tác động thấp trong Thuật toán 1, trích
ra các ký tự đã nhúng và gọi các ký tự này là W ′j với j = 1, 2, 3, 4.
So sánh các ký tự trong hai xâu này với nhau. Nếu chúng trùng khớp thì r′ chính là r và
không bị sửa đổi. Nếu ngược lại thì kết luận là r′ chính là r nhưng đã bị sửa đổi.
Thuật toán 2 dưới đây là giả mã cho qui trình phát hiện thủy vân để xác minh xem một
quan hệ r thuộc lược đồ quan hệ R có phải là quan hệ r đã được thủy vân bằng Thuật toán
1 và có còn toàn vẹn hay không?
Thuật toán 2. Thuật toán phát hiện thủy vân và xác minh sự toàn vẹn
Input:
- Quan hệ r′ thuộc lược đồ R(H1, H2, ...,Hm, L1, L2, ...., Ln), trong đó H1, H2, ...,Hm là các
thuộc tính kiểu văn bản có tác động cao, còn L1, L2, ...., Ln là các thuộc tính kiểu văn bản có
tác động thấp.
- Khóa thủy vân K.
Output: Quan hệ r toàn vẹn hoặc quan hệ r đã bị sửa đổi.
1. // Sinh thủy vân từ r′
2. V H = CH = PH = 0
3. for i = 1 to ω do //Tính tổng các mã ASCII của m thuộc tính tác động cao
4. for j = 1 to m do
5. V H = V H + ΣASCII của các nguyên âm thuộc r′i.Hj
ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ 59
6. CH = CH + ΣASCII của các phụ âm thuộc r′i.Hj
7. PH = PH + ΣASCII của các ký tự đặc biệt của r′i.Hj
8. end for
9. end for
10. for j = 1 to n do
11. V Lj = C
L
j = P
L
j = A
L
j
12. for i = 1 to ω do //Tính tổng các mã ASCII cho từng thuộc tính tác động thấp
13. V Lj = V
L
j + ΣASCII của các nguyên âm của r
′
i.Lj
14. CLj = C
L
j + ΣASCII của các phụ âm của r
′
i.Lj
15. PLj = P
L
j + ΣASCII của các ký tự đặc biệt của r
′
i.Lj
16. ALj = A
L
j + ΣASCII của tất cả ký tự của r
′
i.Lj
17. end for
18. end for
19. for i = 1 to n do //Xây dựng ma trận D
20. Di1 = V
L
i + V
H
21. Di2 = C
L
i + C
H
22. Di3 = P
L
i + P
H
23. Di4 = A
L
i
24. end for
25. for i = 1 to n do //Tìm ma trận chuẩn hóa N của D và ma trận chuyển vị NT
26. for j = 1 to 4 do
27. Nij = Dij/ SQRT(D
2
i1 + D
2
i2 + D
2
i3 + D
2
i4) //Chuẩn hóa
28. NTij = Nji //Chuyển vị
29. end for
30. end for
31. W = N ∗NT //Sinh các ký tự thủy vân
32. for j = 1 to 4 do
33. Wj = ATOC(HASH(ej‖K) MOD 224) + 32) //Ký tự thủy vân
34. end for
35. Sắp thứ tự Wj
36. XacDinhKyTuNhung(n); // Xác định các ký tự thủy vân w∗i (i = 1, ..., n)
37. ChuoiVTri = ExtractBit (HASH(K), ω)
38. for i = 1 to n do
39. for j = 1 to 4 do
40. if (ChuoiVTrij = 1) then
41. w′i =substring (r
′
j .Li, j MOD (length (r
′
j .Li)− 1), 1)
42. sort (w′i)
43. end for
44. end for
60 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
45. for i = 1 to n do // Kiểm tra sự toàn vẹn
46. if (w∗i ! = w
′
i) then
47. Quan hệ r đã bị sửa đổi
48. end if
49. end for
50. Quan hệ r toàn vẹn
Tương tự như Thuật toán 1, Thuật toán 2 có độ phức tạp tính toán là O(ω).
4. TÍNH ĐÚNG ĐẮN
Để chứng minh tính đúng đắn của lược đồ đề xuất chúng tôi đưa ra các định lý sau.
Định lý 1. Lược đồ quan hệ R có các thuộc tính văn bản có tác động cao và các thuộc tính
tác động thấp được nhúng thủy vân bằng Thuật toán 1.
Chứng minh. Trong thuật toán 1, đầu tiên sẽ tìm thủy vân từ các bộ của quan hệ bằng cách
dựa vào khóa thủy vân, các thuộc tính kiểu văn bản có tác động cao và các thuộc tính kiểu
văn bản có tác động thấp. Sau đó, sẽ nhúng thủy vân vào các thuộc tính văn bản có tác động
thấp. Do đó để chứng minh Định lý 1 ta cần phải tìm được ma trận thủy vân W và cách
nhúng thủy vân W vào thuộc tính tác động thấp. Thật vậy:
- Đối với m thuộc tính có tác động cao, tính tổng mã ASCII của tất cả các nguyên âm,
phụ âm và ký tự đặc biệt trong toàn bộ các thuộc tính, cụ thể là:
V H = Σij{ΣASCII của các nguyên âm thuộc ri.Hj , 1 ≤ i ≤ ω; 1 ≤ j ≤ m}
CH = Σij{ΣASCII của các phụ âm thuộc ri.Hj , 1 ≤ i ≤ ω; 1 ≤ j ≤ m}
PH = Σij{ΣASCII của các ký tự đặc biệt của ri.Hj , 1 ≤ i ≤ ω; 1 ≤ j ≤ m}
- Đối với n thuộc tính kiểu văn bản có tác động thấp, tính tổng mã ASCII của các nguyên
âm, phụ âm, ký tự đặc biệt và tổng mã ASCII của tất cả các ký tự theo từng thuộc tính, cụ
thể là:
V Lj = Σi{ΣASCII của các nguyên âm của ri.Lj , 1 ≤ i ≤ ω}
CLj = Σi{ΣASCII của các phụ âm của ri.Lj , 1 ≤ i ≤ ω}
PLj = Σi{ΣASCII của các ký tự đặc biệt của ri.Lj , 1 ≤ i ≤ ω}
ALj = Σi{ΣASCII của tất cả ký tự của ri.Lj , 1 ≤ i ≤ ω}
- Ma trận D bao gồm 4 hàng và n cột với các thành phần là Di1, Di2, Di3, Di4 (với
i = 1, 2, ..., n) được tính như sau:
Di1 = V
H + V Li , Di2 = C
H + CLi , Di3 = P
H + PLi , Di4 = A
L
i .
- Chuẩn hóa ma trận D để thu được ma trận chuẩn hóa N theo công thức:
W = N ×NT . (1)
- Ma trận W có các giá trị trên đường chéo chính là e1, e2, e3, e4.
- Dùng hàm HASH các giá trị ej sau khi ghép với khóa thủy vân K. Chuyển các giá trị
HASH thành các ký tự thủy vân Wj theo công thức:
Wj = ATOC (HASH (ej‖K) MOD 224 + 32); j = 1, 2, 3, 4.
- Tiến hành lựa chọn ký tự để nhúng vào trong thuộc tính:
ĐẢM BẢO SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ 61
+ Nếu n ≤ 4, w∗i = Wi (i = 1, 2, ..., n).
+ Nếu n > 4, w∗i = W(i MOD 4)+1, (i = 1, 2, ..., n).
- Xác định vị trí nhúng trong các thuộc tính bằng cách sử dụng hàm HASH với khóa K
ChuoiVTri = ExtractBit (HASH (K), ω). (2)
Từ (1) và (2) ta có điều phải chứng minh. 
Định lý 2. Thuật toán 2 xác định sự toàn vẹn của quan hệ r nếu quan hệ r không bị sửa
đổi.
Chứng minh. Để chứng minh định lý ta sẽ chứng minh Wj và W ′j là trùng khớp. Thật vậy:
- Dựa vào m thuộc tính tác động cao và n thuộc tính tác động thấp tính được ma trận D
bao gồm 4 hàng và n cột với các thành phần là Di1, Di2, Di3, Di4 (với i = 1, 2, ..., n) với
Di1 = V
H + V Li , Di2 = C
H + CLi , Di3 = P
H + PLi , Di4 = A
L
i ,
trong đó V H , V Li , C
H , CLi , P
H , PLi , A
L
i là tổng mã ASCII của các nguyên âm, phụ âm, ký tự
đặc biệt và tổng mã ASCII của tất cả các ký tự theo từng thuộc tính. Suy ra
Wj(j = 1, 2, 3, 4). (3)
- Theo Thuật toán 2, ta có
w′i =substring (r
′
j .Li, j MOD (length (r
′
j .Li)− 1), 1)
Hay w′i sẽ lấy ra chuỗi con gồm một ký tự từ r
′
j .Li. Suy ra bit thủy vân W
′
j (j = 1, 2, 3, 4).
(4)
- Mặt khác, theo giả thiết quan hệ r không bị sửa đổi nên suy ra r′j .Li trùng với rj .Li. (5)
Từ (3), (4) và (5) suy ra Wj trùng với W
′
j . 
5. KẾT LUẬN
Cài đặt và thử nghiệm lược đồ đề xuất với dữ liệu thực tế, kết quả cho thấy nếu sau khi
thủy vân mà không có bất kỳ một thay đổi nào đối với quan hệ thì chương trình luôn khẳng
định là quan hệ toàn vẹn. Ngược lại, chỉ cần thay đổi trong bất kỳ thuộc tính nào của quan
hệ thì kết quả là quan hệ không còn toàn vẹn.
Lược đồ được đề xuất dùng để đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ với các
thuộc tính kiểu văn bản có những ưu điểm sau đây:
- Bền vững: Các giá trị đặc trưng của quan hệ có thể được nhúng trong nhiều thuộc tính có
tác động thấp ở khắp nơi trong quan hệ. Vì vậy rất khó để có thể gỡ bỏ hết các ký tự thủy
vân đã nhúng.
- Nhạy cảm: Luôn phát hiện được bất kỳ một thay đổi nào đối với các giá trị thuộc tính vì
các ký tự thủy vân được sinh ra từ kết quả của hàm HASH đối với mọi giá trị thuộc tính của
quan hệ.
- Phát hiện mù: Quá trình xác minh sự toàn vẹn của quan hệ không đòi hỏi quan hệ gốc và
thủy vân gốc.
- Tính hiệu quả: lược đồ thủy vân dễ dàng đưa vào áp dụng trong thực tế vì các thuật toán
khá đơn giản nhưng lại hiệu quả trong việc xác minh tính toàn vẹn và phát hiện xuyên tạc.
Nhược điểm của lược đồ là dễ bị lộ do các ký tự thủy vân được nhúng trực tiếp và hiện
trong các thuộc tính kiểu văn bản có tác động thấp.
62 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
TÀI LIỆU THAM KHẢO
[1] R. Agrawal, P. J. Haas, and J. Kiernan, A system for watermarking relational databases, Pro-
ceedings of the 2003 ACM SIGMOD International Conference on Management of Data
(SIGMOD ’03), San Diego, California. (ACM Press) 2003 (674–674).
[2] A. Al-Haj, and A. Odeh, Robust and blind watermarking of relational database systems, Journal
of Computer Science 4 (12) (2008) 1024–1029.
[3] R. Bedi, A. Thengade, V. Wadhai, A new watermarking approach for non numeric relational
database, International Journal of Computer Applications (0975 – 8887) 13 (7) (2011)
37–40.
[4] Ch. Arathi, literature survey on distortion based watermarking techniques for databases, Inter-
national Journal of Computer Science & Communication Networks 2 (4) (2012) 456–463.
[5] H. Guo, Y. Li, A. Liu, S. Jajodia, A fragile watermarking scheme for detecting malicious modi-
fications of database relations, Information Sciences 176 (10) (2006) 1350–1378.
[6] Yingjiu Li, Huiping Guo, Sushil Jajodia, Tamper detection and localization for categorical data
using fragile watermarks (DRM’04), Proceedings of the 4th ACM Workshop on Digital
Rights Management, New York, USA ( ACM) 2004 (73–82).
[7] 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 và Công nghệ, trường Đại học Thái Nguyên (4) (2009) 56–65.
[8] Bùi Thế Hồng, Lưu Thị Bích Hương, Thủy vân cơ sở dữ liệu quan hệ bằng kỹ thuật tối ưu, Kỷ
yếu Hội thảo Quốc gia lần thứ XII-Một số vấn đề chọn lọc của Công nghệ Thông tin và
Truyền thông, Biên Hòa, 05-06 tháng 8 năm 2009 (NXB Khoa học và Kỹ thuật, Hà Nội, 2011
(443–457)).
[9] Lưu Thị Bích Hương, Bùi Thế Hồng, Bảo vệ bản quyền công khai cho các cơ sở dữ liệu quan hệ,
Kỷ yếu Hội thảo Quốc gia lần thứ XIII-Một số vấn đề chọn lọc của Công nghệ Thông
tin và Truyền thông, Hưng Yên, 19-20 tháng 8 năm 2010 (NXB Khoa học và Kỹ thuật, Hà
Nội, 2011 (41–50)).
[10] Lưu Thị Bích Hương, Bùi Thế Hồng, Sử dụng thủy vân dễ vỡ để phát hiện và khoanh vùng giả
mạo đối với cơ sở dữ liệu quan hệ, Kỷ yếu Hội thảo Quốc gia lần thứ XIV-Một số vấn đề
chọn lọc của Công nghệ Thông tin và Truyền thông, Cần Thơ, 07-08 tháng 10 năm 2011
(NXB Khoa học và Kỹ thuật, Hà Nội, 2012 (449–509)).
[11] Lưu Thị Bích Hương, Thủy vân cơ sở dữ liệu quan hệ bằng kỹ thuật thủy vân dựa vào các bit ít
ý nghĩa nhất, Tạp chí Khoa học Journal of Science, Trường ĐHSP Hà Nội 2 (16) (2011)
81–90.
Ngày nhận bài 22 - 4 - 2013
Nhận lại sau sửa ngày 06 - 01 - 2014