Đả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óm tắt Đả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: ... 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....o ω 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. en...r 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)...

pdf11 trang | Chia sẻ: havih72 | Lượt xem: 177 | Lượt tải: 0download
Nội dung tài liệu Đả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ải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
ề 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

File đính kèm:

  • pdfdam_bao_su_toan_ven_cua_co_so_du_lieu_quan_he_voi_cac_du_lie.pdf