BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
VIỆN CÔNG NGHỆ THÔNG TIN
LƯU THỊ BÍCH HƯƠNG NGHIÊN CỨU VÀ PHÁT TRIỂN
KỸ THUẬT THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ

LUẬN ÁN TIẾN SĨ TOÁN HỌC
HÀ NỘI – 2014

i

LỜI CẢM ƠN

Để hoàn thành luận án này, tôi đã nhận được sự giúp đỡ rất tận tình các Thầy,
Cô giáo trong Viện Công nghệ thông tin - Viện Hàn Lâm Khoa học và Công nghệ
Việt Nam và trường ĐHSP Hà Nội 2. Tôi xin gửi lời cảm ơn các Thầy, Cô giáo
trong Viện Công nghệ thông tin và trường ĐHSP Hà Nội 2 đã tạo điều kiện học tập,
nghiên cứu, giúp đỡ tôi rất nhiều trong quá trình làm luận án. Đặc biệt tôi xin cảm
ơn PGS.TS. Bùi Thế Hồng đã tận tình hướng dẫn chỉ bảo cho tôi trong toàn bộ quá
trình học tập, nghiên cứu đề tài và giúp tôi hoàn thành bản luận án này.

Hà Nội, ngày tháng năm 2014
Nghiên cứu sinh

Lưu Thị Bích Hương


Danh sách bảng vii

Danh sách hình vẽ viii

MỞ ĐẦU 1

Chương 1. THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ 9

1.1.

Các khái niệm về cơ sở dữ liệu 9

1.1.1.

Cơ sở dữ liệu 9

1.1.2.

Mô hình dữ liệu quan hệ 9

1.1.3.

Thuộc tính, miền thuộc tính và kiểu thuộc tính 10

1.1.4.

Quan hệ, lược đồ quan hệ 10

1.1.5.


1.3.1.

Khả năng có thể phát hiện 17

1.3.2.

Tính bền vững và dễ vỡ 18

1.3.3.

Khả năng cập nhật dữ liệu 18

1.3.4.

Tính ẩn và hiện 18

1.3.5.

Phát hiện mù 19

1.4.

Ứng dụng của thủy vân cơ sở dữ liệu quan hệ 19

1.4.1.

Bảo vệ bản quyền 19

1.4.2.


1.7.

Kết luận chương 1 30

Chương 2. PHÁT TRIỂN LƯỢC ĐỒ THỦY VÂN BẢO VỆ BẢN QUYỀN
CHO CƠ SỞ DỮ LIỆU QUAN HỆ 31

2.1.

Xây dựng lược đồ thủy vân dựa vào việc chèn thêm ảnh nhị phân 31

2.1.1.

Xây dựng lược đồ thủy vân 33

iv

2.1.2.

Đánh giá độ phức tạp 36

2.1.3.

Chứng minh tính đúng đắn 36

2.1.4.

Đánh giá thử nghiệm 38



3.1.

Phân nhóm quan hệ 51

3.2.

Phát triển lược đồ thủy vân với thuộc tính phân loại 53

3.2.1.

Cải tiến lược đồ thủy vân 54

3.2.2.

Đánh giá độ phức tạp 58

3.2.3.

Chứng minh tính đúng đắn 58

3.2.4.

Cân đối giữa số bộ trong quan hệ và số nhóm 60

3.2.5.

Đánh giá thử nghiệm 63

3.2.6.


3.4.1.

Một số định nghĩa 73

3.4.2.

Tư tưởng 74

3.4.3.

Xây dựng lược đồ thủy vân 75

3.4.4.

Phân tích tính đúng đắn 81

3.4.5.

Đề xuất lược đồ thủy vân để khoanh vùng giả mạo 84

3.4.6.

Đánh giá thử nghiệm 88

3.4.7.

Kết luận 88

3.5.

k
Nhóm thứ k
q
k
Số bộ trong nhóm G
k
P Thuộc tính khóa chính của quan hệ
A
w
Thuộc tính kiểu văn bản có thể chứa nhiều từ
H
i
Thuộc tính kiểu văn bản có tác động cao thứ i
L
i
Thuộc tính kiểu văn bản có tác động thấp thứ i
H(K

r
i
.A
1

r
i
.A
2

….r
i


Thủy vân được trích từ thuộc tính thứ j của tất cả các bộ
trong một nhóm đã thủy vân
W
*2
i

Thủy vân được trích từ tất cả các thuộc tính của bộ thứ i
trong một nhóm đã thủy vân
V
1
j
Kết quả xác nhận thủy vân đối với W
1
j

vi

V
2
i
Kết quả xác nhận thủy vân đối với W
2
i

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ệ
e
i

Số bit cần thiết để ghi một con đếm
m
tuple
Số bit để ghi một bản sao của một bộ
m
wkey
Số bit ghi khóa thủy vân
m
pkey
Số bit ghi giá trị khóa chính
LSB Bit ít ý nghĩa nhất (
L
east
S
ignificant
B
it)
MSB Bit ý nghĩa nhất (
M
ost
S
ignificant
B
it)
MAC Mã chứng thực thông điệp (
M
essage
A
uthentication
Code)


Hình 2.1: (a) Ảnh nhị phân và giá trị thập phân tương ứng. (b) Thuộc tính văn bản
sau khi được thủy vân, trong đó các chỉ số là số thứ tự các dấu cách đơn và DS là
dấu cách đúp. 32

Hình 2.2. Ảnh nhị phân sử dụng để thủy vân. (a) ảnh IOIT 12x4 (b) ảnh Smiley
8x8 38

Hình 2.3. Kết quả tấn công thêm 39

Hình 2.4. Kết quả tấn công xóa 39
Hình 2.5. Kết quả tấn công thay đổi dữ liệu 40

Hình 2.6. Tấn công thêm bộ đối với  48

Hình 2.7. Tấn công sửa bộ đối với  49

Hình 2.8. Tấn công xóa bộ đối với  49

Hình 3.1. Tỷ lệ phát hiện đối với các tấn công thêm nhiều bộ 64

Hình 3.2. Tỷ lệ phát hiện đối với các tấn công xóa nhiều bộ 65

Hình 3.3. Tỷ lệ phát hiện đối với các tấn công sửa nhiều bộ 65
1

MỞ ĐẦU


Giấu tin là kỹ thuật nhúng một lượng thông tin số nào đó vào trong một đối
tượng dữ liệu số khác. Một trong những yêu cầu cơ bản của giấu tin là đảm bảo
tính chất ẩn của thông tin được giấu đồng thời không làm ảnh hưởng đến chất
lượng của dữ liệu gốc.
Do kỹ thuật giấu tin mới được hình thành trong thời gian gần đây nên những
nhu cầu liên quan đến vấn đề giấu tin vẫn chưa được giải quyết một cách triệt để.
Nhiều phương pháp mới, theo nhiều khía cạnh khác nhau đã và đang được tiến
hành nghiên cứu, đề xuất. Chính vì vậy, sự phân loại các kỹ thuật là thực sự cần
thiết.
Dựa trên việc thống kê sắp xếp các công trình đã công bố trên một số tạp chí,
cùng với thông tin về tên và tóm tắt nội dung của các công trình đã công bố trên
Internet, có thể chia lĩnh vực giấu tin ra làm hai hướng lớn, đó là giấu tin bí mật và
thủy vân. Nếu như thủy vân liên quan đến ứng dụng giấu các mẩu tin ngắn nhưng
đòi hỏi độ bền vững lớn của thông tin cần giấu (trước các biến đổi thông thường
của dữ liệu) thì giấu tin bí mật lại liên quan tới ứng dụng che giấu các bản tin đòi
hỏi độ bí mật và dung lượng càng lớn càng tốt. Đối với từng hướng lớn này, quá
trình phân loại theo các tiêu chí khác có thể tiếp tục được thực hiện, ví dụ dựa theo
ảnh hưởng các tác động từ bên ngoài có thể chia thuỷ vân thành hai loại, một loại
bền vững với các tác động sao chép trái phép, loại thứ hai lại cần tính chất hoàn
toàn đối lập dễ bị phá huỷ trước các tác động nói trên. Cũng có thể chia thuỷ vân
theo đặc tính, một loại cần được che giấu để chỉ có một số người tiếp xúc với nó
có thể thấy được thông tin, loại thứ hai đối lập, cần được mọi người nhìn thấy.
Năm 1999, sau hội nghị quốc tế lần thứ hai về giấu tin năm 1998, Petitcolas F.A.
P. đưa ra tổng quan về giấu tin và đã được chấp nhận rộng rãi trong giới nghiên
cứu được mô tả chi tiết trong hình 1.
Các thành tựu đạt được trong lĩnh vực nghiên cứu này đã bắt đầu được áp
dụng hiệu quả cho mục đích bảo vệ bản quyền, chống sao chép, phân tán trái phép
các sản phẩm trong môi trường số hoá và nhiều mục đích khác. Nhiều phương
pháp giấu tin khác nhau đã được đề xuất, mỗi phương pháp có những ưu điểm,

vực nghiên cứu độc lập cho tới những năm 1980 và khái niệm thủy vân chỉ được
hoàn thiện vào giữa những năm 90 của thế kỷ 20.
Năm 1990, Tanaka, Tirkel A.Z., Rankin G.A., Schyndel R.G.van, Ho W.J.,
Mee N.R.A và năm 1993 Osborne C.F. lần lượt đưa ra những đề xuất đầu tiên về
thủy vân số. Đến năm 1995, Caronni G. tiếp tục đề xuất về vấn đề bảo vệ bản
watermarking
Thuỷ vân số
Fragile
Watermarking
Thuỷ vân dễ vỡ
Information
hiding
Giấu tin
Robust
Copyright marking
Thuỷ vân bền vững
steganography
Giấu tin mật
Imperceptible
Watermarking
Thuỷ vân ẩn
Visible
Watermarking
Thuỷ vân hiện
Intrinsic
Giấu tin có xử lý
Pure
Giấu tin đơn thuần
Imperceptible
Watermarking


5

- Phát hiện – Xác minh: Quá trình phát hiện - xác minh được thực hiện một
cách mù (blind) hay không mù, nó có thể được thực hiện công khai (bởi bất cứ ai)
hoặc bí mật (chỉ có chủ sở hữu) [34], [35].
- Mục đích của thủy vân: Các lược đồ thủy vân khác nhau được thiết kế để
phục vụ cho các mục đích khác nhau, cụ thể là: bảo vệ bản quyền, đảm bảo sự toàn
vẹn hay phát hiện giả mạo [12], [35], khoanh vùng, chứng minh quyền sở hữu,
phát hiện kẻ phản bội… Đối với các lược đồ thủy vân dùng để bảo vệ bản quyền
cho cơ sở dữ liệu quan hệ thông thường sẽ là thủy vân bền vững. Ngược lại, thủy
vân dễ vỡ dùng để đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ. Luận án sẽ tập
trung vào nghiên cứu và phát triển các kỹ thuật thủy vân cơ sở dữ liệu quan hệ
theo hướng phục vụ cho mục đích bảo vệ bản quyền và đảm bảo sự toàn vẹn của
cơ sở dữ liệu quan hệ.
Nói chung, các kỹ thuật thuỷ vân ngay từ khi mới ra đời đã nhận được sự
quan tâm rất lớn của các nhà khoa học. Các kỹ thuật thuỷ vân đã được nghiên cứu
và áp dụng trong nhiều môi trường dữ liệu khác nhau như: dữ liệu đa phương tiện
(image, text, audio, video, . . .), các sản phẩm phần mềm. Trong các môi trường dữ
liệu đó thì dữ liệu đa phương tiện (đặc biệt là image) được nghiên cứu và áp dụng
sớm nhất và là môi trường chiếm tỷ lệ chủ yếu. Tuy nhiên, vấn đề thuỷ vân dữ liệu
quan hệ chưa được sự chú ý nghiên cứu. Do cơ sở dữ liệu quan hệ có nhiều ngữ
cảnh ứng dụng trong đó dữ liệu trở nên một tài sản quan trọng, vì vậy vấn đề về
quyền sở hữu và đảm bảo sự toàn vẹn dữ liệu phải được thực thi một cách cẩn
thận. Ví dụ dữ liệu về thời tiết, dữ liệu về thị trường chứng khoán, dữ liệu về hành
vi của khách hàng, dữ liệu về điều tra dân số, dữ liệu y học và khoa học. Việc
nhúng thuỷ vân vào dữ liệu quan hệ có thể thực hiện được bởi trong thực tế, các
dữ liệu thật có thể chấp nhận một dung sai nhỏ mà vẫn không ảnh hưởng đáng kể
đến giá trị sử dụng của chúng.
Cho dù có khá nhiều các kết quả đã đạt được về thủy vân dữ liệu đa phương

Thủy vân cơ sở dữ liệu quan hệ có hai ứng dụng quan trọng nhất là bảo vệ
bản quyền và đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ. Do mỗi kiểu dữ liệu
của cơ sở dữ liệu quan hệ có những đặc điểm riêng, cho nên đòi hỏi khi thủy vân
các kỹ thuật thủy vân phải phù hợp với những đặc điểm của dữ liệu được thủy vân.
Xuất phát từ thực tế đó, mục tiêu nghiên cứu chính của luận án là nghiên cứu,
phát triển và xây dựng các kỹ thuật thủy vân trong ứng dụng bảo vệ bản quyền cơ
sở dữ liệu quan hệ và đảm bảo sự toàn vẹn của cơ sở dữ liệu quan hệ.

7

Trên cơ sở nghiên cứu sự cần thiết của các bài toán thủy vân cơ sở dữ liệu
quan hệ và mục tiêu nghiên cứu chính của luận án, phương pháp nghiên cứu của
luận án được xác định là:
- Tìm kiếm và nghiên cứu tài liệu liên quan, tiến hành phân tích, đánh giá và
đưa ra những cải tiến, đề xuất.
- Phát triển các kết quả nghiên cứu về mặt lý thuyết, trên cơ sở cài đặt thử
nghiệm, đánh giá và đưa ra những phương pháp, kỹ thuật mới, cải tiến.
- Trao đổi, thảo luận và báo cáo tại các hội thảo, hội nghị khoa học,…
3. Những đóng góp mới của luận án
- Cải tiến và đánh giá thử nghiệm đối với các lược đồ thủy vân trong ứng
dụng bảo vệ bản quyền, bao gồm: Thủy vân dựa vào việc chèn thêm ảnh nhị phân;
Thủy vân dựa vào bit ý nghĩa nhất (MSB).
- Chứng minh tính đúng đắn của cách chia nhóm quan hệ dựa vào khóa thủy
vân và khóa chính của bộ trong các thuật toán nhúng và thuật toán phát hiện của
các lược đồ thủy vân dùng để đảm bảo sự toàn vẹn dữ liệu.
- Lược đồ thủy vân cải tiến với thuộc tính phân loại đảm bảo sự toàn vẹn dữ
liệu. Chứng minh tính đúng đắn của lược đồ thủy vân cải tiến. Cân đối số bộ trong
quan hệ và số nhóm để tăng tính bền vững của thủy vân và tối đa số các bộ có thể
tiếp tục được sử dụng.
- Đề xuất lược đồ thủy vân với dữ liệu kiểu văn bản. Chứng minh tính đúng


Chương 1. THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ
1.1. Các khái niệm về cơ sở dữ liệu
Mục này trình bày các khái niệm cơ bản nhất về mô hình dữ liệu quan hệ do
E.F. Codd đề xuất [1], [51], [52].
1.1.1. Cơ sở dữ liệu
Định nghĩa 1.1: Cơ sở dữ liệu
Cơ sở dữ liệu (database) là một hệ thống các thông tin có cấu trúc được lưu
trữ trên các thiết bị lưu trữ thứ cấp (băng từ, đĩa từ…) nhằm thoả mãn yêu cầu khai
thác thông tin đồng thời của nhiều người sử dụng hay nhiều chương trình ứng
dụng với nhiều mục đích khác nhau.
1.1.2. Mô hình dữ liệu quan hệ
Trong quá trình thiết kế và xây dựng các hệ quản trị cơ sở dữ liệu, người ta
tiến hành xây dựng các mô hình dữ liệu. Mô hình dữ liệu phải được thể hiện được
các mối quan hệ bản chất của các dữ liệu mà dữ liệu này phản ánh các mối quan
hệ và các thực thể trong thế giới thực. Mô hình dữ liệu phản ánh khía cạnh cấu
trúc logic mà không đi sâu vào khía cạnh vật lý của cơ sở dữ liệu. Mô hình dữ liệu
là một sự hình thức hóa toán học với một tập ký hiệu để mô tả dữ liệu và một tập
các phép toán được sử dụng để thao tác các dữ liệu này. Khi xây dựng các mô hình
dữ liệu cần phân biệt các thành phần cơ bản sau:
- Thực thể: Là đối tượng có trong thực tế mà chúng ta cần mô tả các đặc trưng
của nó.
- Thuộc tính: Là các dữ liệu thể hiện các đặc trưng của thực thể.
- Ràng buộc: Là các mối quan hệ logic của các thực thể.
Ba thành phần trên được thể hiện ở hai mức:
- Mức loại dữ liệu: là sự khái quát hóa các ràng buộc, các thuộc tính, các thực
thể cụ thể.
- Mức thể hiện: Là một ràng buộc cụ thể, hoặc là các giá trị thuộc tính, hoặc là
một thực thể cụ thể.
Trên thực tế có một số mô hình dữ liệu đã được nghiên cứu:


Ví dụ 1.1: Nhânviên(MaNV, Ten, NgSinh, Đchi)
Dom(MaNV) = {char(5)}; Dom(Ten) = {char(10)};
Dom(NgSinh) = {date}; Dom(Đchi) = {‘HN’, ‘HP’, ‘VP’, …}.
Mỗi một thuộc tính đều phải thuộc một kiểu dữ liệu. Kiểu dữ liệu có thể là vô
hướng - là các kiểu dữ liệu cơ bản như chuỗi, số, logic, ngày tháng,… hoặc các
kiểu có cấu trúc được định nghĩa dựa trên các kiểu dữ liệu đã có sẵn.
1.1.4. Quan hệ, lược đồ quan hệ
Định nghĩa 1.3: Quan hệ
Cho U = {A
1
, A
2
, …, A

} là một tập hữu hạn không rỗng các thuộc tính. Mỗi
thuộc tính A
i
(i =1, 2, …, ) có miền giá trị là Dom(A
i
). Khi đó r là một tập các bộ

11

{r
1
, r
2
, …, r
m



r
1
r
1
.A
1
r
1
.A
2
…
r
1
.A


r
2
r
2
.A
1
r
2
.A
2
…
r

Tập tất cả các thuộc tính trong một quan hệ cùng với mối liên hệ giữa chúng
được gọi là lược đồ quan hệ.
Lược đồ quan hệ R với tập thuộc tính U={A
1
, A
2
, , A

} được viết là R(U)
hoặc R(A
1
, A
2
, , A

).
1.1.5. Khoá của quan hệ
Định nghĩa 1.5: Khóa của quan hệ
Khoá của quan hệ r xác định trên tập thuộc tính U = {A
1
, A
2
, , A

}là tập con
K  U sao cho bất kỳ hai bộ khác nhau t
1
, t
2
 r luôn thoả t

1.2.2. Thủy vân cơ sở dữ liệu quan hệ
Ngày nay, việc sử dụng các cơ sở dữ liệu trong các ứng dụng càng ngày càng
tăng lên đang tạo ra một nhu cầu tương tự đối với thủy vân cơ sở dữ liệu. Internet
hiện đang đưa đến một sức ép rất nặng nề cho những người muốn 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 sử dụng tìm kiếm và truy cập cơ sở dữ liệu từ xa. Mặc dù
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ột mối nguy
hiểm cho những nhà cung cấp dữ liệu trước những kẻ trộm cắp dữ liệu. Do đó,

13

những người cung cấp dữ liệu đòi hỏi phải có công nghệ nhận dạng được những
bản sao các cơ sở dữ liệu của họ bị đánh cắp.
Định nghĩa 1.6: Thủy vân cơ sở dữ liệu quan hệ
Thủy vân cơ sở dữ liệu quan hệ là một kỹ thuật nhúng một số thông tin nào đó
(được gọi là thông tin thủy vân W) vào cơ sở dữ liệu quan hệ nhằm mục đích bảo
vệ bản quyền hoặc đảm bảo sự toàn vẹn cho cơ sở dữ liệu này. Thủy vân có thể ở
dạng ẩn hoặc hiện và có thể là bền vững hoặc dễ vỡ.
Một thuỷ vân có thể được áp dụng cho một cơ sở dữ liệu quan hệ, chẳng hạn
như có các thuộc tính mang một đặc điểm là những thay đổi nhỏ tại một số giá trị
của chúng không làm ảnh hưởng đến các ứng dụng. Ví dụ, dữ liệu khí tượng được
sử dụng để xây dựng các mô hình dự báo thời tiết. Độ chính xác của vectơ gió và
nhiệt độ tương ứng trong dữ liệu này được đo chính xác đến 1.8 m/s và 0.5
o
C. Các
sai số được đưa vào do thuỷ vân có thể dễ dàng được hạn chế trong sự cho phép
của các dữ liệu này. Hay một ví dụ khác các nhà xuất bản sách khi in các bảng
toán học (như các bảng logarit và lịch thiên văn) thường cố ý đưa vào một số lỗi
nhỏ để có thể dễ dàng nhận dạng các bản sao bị ăn cắp.
1.2.3. Khóa thủy vân

ii) với h đã cho, khó tính được M sao cho H(M) = h, và
iii) với M đã cho, khó tìm được một thông điệp khác M
0
sao cho H(M) =
H(M
0
).
Trong các lược đồ thủy vân trình bày ở chương 2 và 3, sẽ dùng hàm băm để
băm khóa cùng với cơ sở dữ liệu. Hàm H(Kr.A) băm khóa K cùng với giá trị
thuộc tính A của bộ r, hàm H(Kr
i
.A
1
r
i
.A
2
….r
i
.A


băm khóa K cùng với các
giá trị thuộc tính của bộ r
i
của cơ sở dữ liệu, trong đólà phép ghép nối. Để đơn
giản trong cách đánh giá độ phức tạp tính toán của các lược đồ thủy vân, luận án
sẽ bỏ qua độ phức tạp tính toán của hàm băm.
Trong thực tế, hai hàm băm thông dụng nhất là MD5 và SHA [40]. Trong
các thử nghiệm, luận án dùng hàm băm MD5.

nay vẫn còn rất nhiều thách thức kỹ thuật mới đối với lĩnh vực thuỷ vân cơ sở dữ
liệu quan hệ bởi vì các dữ liệu quan hệ và các dữ liệu đa phương tiện khác nhau ở
khá nhiều khía cạnh quan trọng. Những khác biệt đó [7] bao gồm:
 Một đối tượng đa phương tiện thường chứa một lượng các bit dư thừa. Vì
vậy, các kỹ thuật thuỷ vân có một cái mặt nạ (vỏ) rất rộng để có thể giấu tin
vào trong. Trong khi đó, một quan hệ cơ sở dữ liệu chứa các bộ, mỗi bộ này
Nhúng thủy
vân
Khóa K
Cơ sở dữ liệu
gốc
Cơ sở dữ liệu đã
nhúng thủy vân
Thông tin thủy vân (W)
Phát hiện
thủy vân
Khóa K
Cơ sở dữ liệu
nghi ngờ
Khẳng định đúng
hoặc sai
Thông tin thủy vân (W)