Bài giảng Bảo mật cơ sở dữ liệu: Chương 5 của Trần Thị Kim Chi

CHƯƠNG 5

Mục tiêu

 Chúng ta đi sâu vào các vấn đề suy diễn

trên các CSDL thống kê.

 Thảo luận một số kỹ thuật bảo vệ cơ bản:

 Kỹ thuật dựa vào khái niệm  Kỹ thuật dựa vào hạn chế  Kỹ thuật dựa vào gây nhiễu

 Đánh giá chung về đặc trưng của các kỹ

thuật này.

Nội dung

4.1 Giới thiệu 4.2 Các khái niệm cơ bản và giả định 4.3 Một số kiểu tấn công suy diễn 4.4 Các kỹ thuật chống suy diễn 4.4.1 Các kỹ thuật khái niệm 4.4.2 Các kỹ thuật dựa vào hạn chế 4.4.3 Các kỹ thuật dựa vào gây nhiễu

4.5 Khung làm việc chung dành cho việc so sánh các kỹ thuật chống suy diễn

4.1 Giới thiệu

 CSDL thống kê (SDB) là một CSDL chứa các bản ghi nhạy cảm mô tả về các cá nhân nhưng chỉ các câu truy vấn thống kê (như: COUNT, SUM, MEAN, MAX, MIN…) mới được trả lời, ngoài các câu truy vấn này thì những truy vấn vào các mục dữ liệu riêng sẽ không được đáp lại

Ví dụ một số câu truy vấn thống kê

 COUNT:

 Select count(*) from Nhanvien

(Trả lại tổng số lượng các bg trong table)  Select count(Luong) AS count_Luong from

Nhanvien

 Select count(Distinct Luong) from Nhanvien

(Trả lại số lượng các loại lương phân biệt nhau)

 select count(*) from nhanvien where

Luong<=1000

Ví dụ một số câu truy vấn thống kê

 SUM:

 Select SUM(Luong) as sum_Luong from Nhanvien  Select SUM(Distinct Luong) as sum_Luong from

Nhanvien

 Select Chucvu, Sum(Luong) from Nhanvien GROUP

BY chucvu

 Select HoTen, chucvu, Luong from nhanvien

ORDER by chucvu Compute SUM(Luong) by chucvu (Thêm cột tổng lương với từng kiểu chức vụ)

Ví dụ một số câu truy vấn thống kê

 AVG:

 Select AVG(Luong) AS avg_Luong from Nhanvien  Select AVG(Luong) AS avg_Luong from Nhanvien

where Luong>1000

 Select AVG(distinct Luong) AS avg_Luong from

Nhanvien

 Select

chucvu,

AVG(Luong)

avg_Luong,

SUM(Luong) as sum_luong from Nhanvien Group by chucvu Order by chucvu

Ví dụ một số câu truy vấn thống kê

 MIN:

 Select MIN(Luong) from Nhanvien  Select MIN(Distinct Luong) from Nhanvien

 MAX

 Select MAX(Distinct Luong) from Nhanvien  Select MAX(Luong) from Nhanvien

4.1 Giới thiệu

 Ứng dụng của SDB (Statistical Database): CSDL điều tra dân số, CSDL về số người tử vong, về kế hoạch kinh tế, CSDL thống kê về khám chữa bệnh, CSDL về các vụ tai nạn ô tô, CSDL về công nhân, CSDL thống kê về tội phạm…

 Ví dụ:

4.1 Giới thiệu

 Vấn đề bảo vệ SDB: Vấn đề chính trong bảo vệ SDB là dàn xếp giữa các yêu cầu cá nhân và quyền của các tổ chức để biết và xử lý thông tin => vấn đề suy diễn trong SDB.

 Suy diễn: trong một SDB có nghĩa là có thể thu được các thông tin bí mật trong các thực thể đơn lẻ, bằng cách lợi dụng các câu truy vấn thống kê.

4.1 Giới thiệu

 Một SDB chắc chắn bị lộ: nếu người sử dụng phát hiện được một cá nhân có một đặc điểm cụ thể nào đó, nghĩa là người dùng biết cá nhân này được biểu diễn trong SDB có một số giá trị thuộc tính nào đó.  Một SDB hoàn toàn không bị

lộ: nếu người sử dụng biết được một cá nhân cụ thể không nắm giữ một đặc điểm nào đó.

4.1 Giới thiệu

 Các đặc tính của SDB cần được bảo vệ:

 SDB tĩnh: SDB không thay đổi trong suốt thời

gian tồn tại của chúng.

 SDB động: thay đổi liên tục theo sự thay đổi của dữ liệu thực, cho phép sửa đổi, nghĩa là được phép chèn hoặc xoá các thực thể để phản ánh các thay đổi động của thế giới thực (ví dụ các CSDL nghiên cứu trực tuyến, lớp học trực tuyến khi bổ sung thành viên,…).

4.1 Giới thiệu

 SDB trực tuyến (online): trong đó người sử dụng nhận được các phản hồi thời gian thực cho các câu truy vấn thống kê của mình.

 SDB ngoại tuyến (offline): trong đó người sử dụng không biết khi nào các thống kê của họ được xử lý, việc SDB bị lộ sẽ khó khăn.

4.1 Giới thiệu

 Kiến thức làm việc (working knowledge) là tập các mục thông tin liên quan đến các giá trị thuộc tính trong SDB và các kiểu thống kê có sẵn trong SDB

 Kiến thức bổ sung của người

sử dụng (sumplementary knowledge): Người sử dụng có thể có kiến thức bổ sung về các cá nhân được biểu diễn trong SDB. Họ hoàn toàn có thể lợi dụng kiến thức này cho các mục đích suy diễn.

Mô hình làm lộ SDB

Ví dụ về làm lộ một SDB Ví dụ 1 (lộ chính xác)

Ví dụ 2 (lộ xấp xỉ)

Ví dụ 2

Nội dung

 4.1 Giới thiệu  4.2 Các khái niệm cơ bản và giả định  4.3 Một số kiểu tấn công suy diễn  4.4 Các kỹ thuật chống suy diễn  4.4.1 Các kỹ thuật khái niệm  4.4.2 Các kỹ thuật dựa vào hạn chế  4.4.3 Các kỹ thuật dựa vào gây nhiễu

 4.5 Khung làm việc chung dành cho việc so

sánh các kỹ thuật chống suy diễn

4.2 Các khái niệm cơ bản và các giả định

 CSDL thống kê (SDB): ta xem xét cấu trúc của một

SDB là một dạng quan hệ, giả sử là R.  N là số bản ghi: Xi là bản ghi thứ i  M là số thuộc tính: A1, A2, …, AM  Xij là giá trị của thuộc tính Aj trong bản ghi xi  Mỗi thuộc tính Aj (1j M) có thể có |Aj | giá

trị.

4.2 Các khái niệm cơ bản và các giả định

 Ví dụ về một SDB:

 SDB về công nhân (Lương):

Tên ID Chức vụ Phòng Tuổi Giới tính Lương

Nam 01 Nhân viên Maketing 29 M 3500

Lan 02 Trưởng phong Kế hoạch F 33 6200

Huệ 03 Nhân viên Kế hoạch F 27 4000

04 Minh Giám sát viên Maketing M 24 3600

05 Quỳnh Nhân viên Kế hoạch 24 F 2900

4.2 Các khái niệm cơ bản và các giả định

 SDB về các vụ tai nạn ô tô

HoTen

Tuoi Đ/C

MauXe LoaiXe

ThoiGian CoLoi SayRuou

Xanh

Honda

13.30

Nguyễn Văn Tài

Đỏ

Toyota

6.25

Lê sỹ Hoàng

Hoàng Văn Minh

Trắng

Audi

17.45

Vũ Bình Minh

Vàng

Volkswagon 3.30

Trần Quang Hòa

Xanh

Honda

6.30

4.2 Các khái niệm cơ bản và các giả định

 SDB về các Sinh viên

Địa chỉ Phụ cấp Lớp Tên

Nghiện ma túy Giới tính

M Minh HN 500 1 Toán1

M Hải HD 0 0 Toán2

F Tuyết NĐ 300 0 Tin1

M Nam BG 100 3 Tin2

F Phương NA 200 1 Toán2

F Hạnh HT 100 0 Toán1

4.2 Các khái niệm cơ bản và các giả định

 SDB vĩ mô về các Sinh viên

Toán1

Toán2

Tin1

Tin2

M

500

100

F

100

200

300

Tổng cộng

600

200

300

100

Tổng phụ cấp theo giới tính và theo lớp

Các khái niệm cơ bản và các giả định

 SDB về đảng viên

MaDV

HoTen

DiaChi

ChucVu

Luong

DangVien

MA01

Trần Văn Nguyên

Hà Nội

Trưởng phòng

3000

MA02

Nguyễn Thị Hoa

Hải Phòng

Nhân viên

2000

MA03

Vũ Văn Hiển

Hà Nội

Phó Giám đốc

4000

MA04

Trần Thị Mai

Nghệ An

Trưởng phòng

3000

MA05

Nguyễn Quang Huy

Hải Phòng

Giám đốc

5000

MA06

Trần Văn Hải

Hà Nam

Nhân viên

2000

MA03

Lê Minh Sơn

Nam Định

Nhân viên

2500

Các khái niệm cơ bản và các giả định

 SDB vĩ mô về Công nhân (count)

BSD Table

Năm sinh

Giới tính

Mã phòng

Phong1

Phong2

Phong3

1941-1951

1952-1962

>1962

Các khái niệm cơ bản và các giả định

 Công thức đặc trưng: được ký hiệu bởi một chữ cái viết hoa (A,B,C,...), đây là một công thức lôgíc, trong đó các giá trị thuộc tính được kết hợp với nhau thông qua các toán tử Boolean như OR, AND, NOT (,,). Ví dụ:

C=(GioiTinh=F)((MaPhong=Phong1) (MaPhong=Phong2)) (NamSinh<1965)  Tập truy vấn (query set): Một công thức đặc trưng sẽ xác định một tập các bản ghi trong SDB, và tập bản ghi này được gọi là tập truy vấn. Ký hiệu là X(C).

Ví dụ

(1)

Cho công thức: xy [( Thủ_trưởng(x, y)  Thủ_trưởng(y, x))  Cùng_phòng(y, x)]  Giả sử có tập người D = {Khang , Phong, Mai, Lan, Long}, D làm thành miền thể hiện của công thức. Các quan hệ hai ngôi Thủ_trưởng và Cùng_phòng có ý nghĩa rõ ràng trên tập D. Công thức (1) là đúng nếu năm người Khang , Phong, Mai, Lan, Long làm việc trong cùng phòng và có một người là trưởng phòng.

Các khái niệm cơ bản và các giả định

Một số câu truy vấn thống kê

 Count(C)=X(C)

 Df

 Rfreg(C)

 Avg(C,Aj)  Ma

 d  df

Các khái niệm cơ bản và các giả định

 Khái niệm bậc: Một thống kê gồm m thuộc tính khác

nhau được gọi là thống kê bậc m. Ví dụ, thống kê: Count ((GioiTinh = F) (MaPhong = Phong1)) là một thống kê bậc 2. Count(All) hay Count(*) chỉ là một thống kê bậc 0.

 Khái niệm thống kê nhạy cảm: Thống kê được tính toán trên một thuộc tính bí mật trong tập truy vấn có kích cỡ bằng 1 là thống kê nhạy cảm. Ví dụ:

COUNT(AGE >50) =1 SUM(Salary, age>50) là thống kê nhạy cảm

Giới thiệu CSDL suy diễn (Deductive Database)

 Khái niệm CSDL suy diễn: Khái niệm về CSDL suy diễn cũng được nhiều nhà nghiên cứu đề cập theo hướng phát triển các kết quả mà Green đã đạt được vào năm 1969 về các hệ thống hỏi – đáp.

 Xuất phát từ quan điểm lý thuyết, các CSDL suy diễn có thể được coi như các chương trình logic với sự khái quát hoá khái niệm về CSDL quan hệ. Đó là cách tiếp cận của Brodie và Manola vào năm 1989, của Codd vào năm 1970, của Date vào năm 1986, của Gardarin và Valdurier vào năm 1989 và của 32 Ullman vào năm 1984.

Giới thiệu CSDL suy diễn (Deductive Database)  CSDL suy diễn là CSDL có khả năng suy diễn ra một số sự kiện (tri thức) mới từ những sự kiện (tri thức) đã có, đã được lưu trữ trong CSDL ban đầu.  CSDL suy diễn được sử dụng nhiều trong các hệ quyết định, hệ chuyên gia. Nó có khả năng lưu trữ số lượng lớn thông tin và khả năng suy diễn trên các thông tin đó.

 Các hệ CSDL suy diễn được xem như sự tích hợp của dữ liệu (như trong một hệ CSDL) và tri thức (như trong một hệ chuyên gia).

4.1 Giới thiệu

Cấu trúc CSDL suy diễn

 Cấu trúc chung của một CSDL suy diễn gồm 3 phần chính: tập các sự kiện (facts), tập các luật suy diễn (rules) và các RBTV

Cấu trúc CSDL suy diễn

Cấu trúc CSDL suy diễn:  Tập các sự kiện (facts): Sự kiện là vị từ mô tả một sự thật, cho phép biểu diễn thông tin cơ sở được biết là đúng trong CSDL.

Cấu trúc CSDL suy diễn

Cấu trúc CSDL suy diễn:  Tập các luật suy diễn (rules) Luật suy diễn cũng là các vị từ diễn tả quy luật suy diễn mà ta công nhận chúng.

 Luật suy diễn được trình bày dưới dạng một mệnh đề. Nó cho phép suy diễn ra các sự kiện mới từ những sự kiện được lưu trữ trong CSDL.

Cấu trúc CSDL suy diễn

Cấu trúc CSDL suy diễn:  RBTV: cho phép để xác định giá trị hợp lệ cho các bộ trong các quan hệ.

 CSDL suy diễn cho phép diễn tả các RBTV thông thường như trong các mô hình CSDL khác như: ràng buộc khóa chính, khóa ngoại, ràng buộc miền giá trị ( ràng buộc kiểu).

Các thành phần của CSDL suy diễn

Một CSDL ngoại diên (Extension Database- EDB)  EDB là một CSDL quan hệ tiêu chuẩn như mọi hệ CSDL truyền thống, được xây dựng trên một tập các lược đồ quan hệ, có khả năng lưu trữ một khối lượng lớn dữ liệu.

 Các dữ liệu trong EDB gọi là các sự kiện (facts), mỗi sự kiện là một bộ của một quan hệ, có thể cập nhật (thêm/sửa/xóa) như là các bộ trong CSDL quan hệ.  Các sự kiện biểu diễn các thông tin cơ sở (được cho

là đúng trong CSDL)

Các thành phần của CSDL suy diễn

Một CSDL ngoại diên (Extension Database- EDB)  EDB là một CSDL quan hệ tiêu chuẩn như mọi hệ CSDL truyền thống, được xây dựng trên một tập các lược đồ quan hệ, có khả năng lưu trữ một khối lượng lớn dữ liệu.

là đúng trong CSDL)

Các thành phần của CSDL suy diễn

Biểu diễn CSDL ngoại diên (Extension Database- EDB)  Ví dụ: sự kiện phát biểu rằng Mai là mẹ của Bách và Dương

là bố của Tân được biểu diễn bởi:  Mẹ (Mai, Bách)  Bố (Dương, Tân)

 Một CSDL suy diễn chỉ chứa các sự kiện cơ sở, tức là các sự kiện trong EDB, đó là các công thức nguyên tố, trong đó các hạng thức ti đều là các hằng.

 Tân từ ứng với sự kiện cơ sở gọi là tân từ cơ sở, là tân từ cùng tên và các đối là các biến. Chẳng hạn với hai sự kiện trên ta sẽ có các tân từ cơ sở tương ứng là  Mẹ (x, y)  Bố (x, y)

Các thành phần của CSDL suy diễn

Một CSDL nội hàm (Intension Database-IDB)  IDB là một CSDL chứa các thông tin nội hàm, lưu trữ một tập các luật, cho phép định nghĩa thông tin mới từ các thông tin được lưu trữ là các sự kiện. Có 2 loại luật được lưu trữ trong IDB:  Các luật suy diễn (deductive rules): cho phép suy ra các

sự kiện mới từ các sự kiện được lưu trữ trong EDB.

 Các ràng buộc toàn vẹn (integrity constraints): được viết dưới dạng các luật, phát biểu các điều kiện mà mỗi trạng thái của CSDL phải thỏa.

Các thành phần của CSDL suy diễn

Một CSDL nội hàm (Intension Database-IDB) Ví dụ Các luật suy diễn (deductive rules):

 “nếu x là Bố của y thì x là Cha_mẹ của y”  “nếu x là Mẹ của y thì x là Cha_mẹ của y”,

 sẽ định nghĩa tân từ dẫn xuất mới “Cha_mẹ(x, y)” được biểu

diễn là:  Cha_mẹ (x, y) Bố (x, y) (đọc: x là cha mẹ của y nếu x là bố của y)  Cha_mẹ (x, y)  Mẹ (x, y)

 Các sự kiện ứng với các tân từ dẫn xuất gọi là các sự kiện dẫn xuất, cũng được coi là đúng. Các sự kiện này được coi là các thông tin nội hàm, và không được lưu trữ trong CSDL suy diễn.

Các thành phần của CSDL suy diễn

Kết luận: một CSDL suy diễn D là một bộ ba

D = {F, DR, IC}

trong đó:  F là tập hữu hạn các sự kiện cơ sở (hay sự kiện),  DR là tập hữu hạn các luật suy diễn và  IC là tập hữu hạn các ràng buộc toàn vẹn.  Tập F là CSDL ngoại diên (EDB), còn DR và IC làm

thành CSDL nội hàm (IDB).

Các thành phần của CSDL suy diễn

Kết luận: một CSDL suy diễn D là một bộ ba

D = {F, DR, IC}

thành CSDL nội hàm (IDB).

Các thành phần của CSDL suy diễn

Thí dụ: Cho một CSDL suy diễn mô tả các mối quan hệ trong một gia tộc.  EDB : Các sự kiện cơ sở

 Mẹ (Mai, Bách)  Bố (Dương, Tân)  Bố (Phát, Mai)

Các thành phần của CSDL suy diễn

Thí dụ: Cho một CSDL suy diễn mô tả các mối quan hệ trong một gia tộc.  EDB : Các sự kiện cơ sở

 Mẹ (Mai, Bách)  Bố (Dương, Tân)  Bố (Phát, Mai)

Các thành phần của CSDL suy diễn

Thí dụ: Cho một CSDL suy diễn mô tả các mối quan hệ trong một gia tộc. ICs : Các ràng buộc toàn vẹn:  IC1(x)  Cha_mẹ (x, x)  IC2(x)  Bố (x, y)  Mẹ (x, z)  Chú ý rằng tân từ không nhất quán cũng có thể chứa biến, nhằm xác định cá thể vi phạm ràng buộc toàn vẹn.

Các thành phần của CSDL suy diễn

Ngôn ngữ thao tác CSDL suy diễn  CSDL suy diễn có thể được hiểu là kết quả của việc áp dụng logic và trí tuệ nhân tạo vào lĩnh vực CSDL truyền thống. Ngôn ngữ được dùng để định nghĩa nội dung và cấu trúc thông tin trong CSDL suy diễn là ngôn ngữ Datalog (logic cho dữ liệu).

 Datalog là ngôn ngữ lập trình logic (tương tự như Prolog) được phát triển dựa trên cơ sở Logic tân từ cấp một. Ngôn ngữ Datalog thao tác trên các tân từ ngoại diên (hay tân từ cơ sở) là tên của các quan hệ trong CSDL ngoại diên (EDB) và tân từ nội hàm (hay tân từ dẫn suất) là tên của các quan hệ trong CSDL nội hàm (IDB). Một CSDL suy diễn được biểu diễn bởi một chương trình Datalog

Các thành phần của CSDL suy diễn

Ngôn ngữ thao tác CSDL suy diễn  Hệ quản trị CSDL suy diễn phải có tất cả các chức năng của một hệ QTCSDL thông thường, có thể cho phép khai thác và quản lý CSDL một cách tập trung hoặc phân tán, đảm bảo tính tin cậy và an toàn dữ liệu.

 Hệ quản trị CSDL suy diễn còn cho phép suy diễn ra các sự kiện mới (là các sự kiện dẫn suất của các tân từ nội hàm) từ các sự kiện đã có bằng việc sử dụng các quy tắc và các luật logic

 Hệ quản trị CSDL suy diễn cung cấp một thủ tục xử lý câu hỏi, có khả năng trả lời các câu hỏi được phát biểu theo các khung nhìn cũng như theo các tân từ cơ sở.

Các thành phần của CSDL suy diễn

Ví dụ: Xem xét một số câu hỏi trong Datalog trên CSDL suy diễn: 1. ? Tổ_tiên (Dương, Mai).  - trả về giá trị đúng (True) nếu Dương là tổ tiên của Mai. Câu trả lời

là sai (False) trong trường hợp trái lại.

2. ? Tổ_tiên (Dương, x).  - trả về tập tất cả những người x nhận Dương là tổ tiên (tập các con

cháu của Dương). 3. ? Tổ_tiên (x, Mai).  - trả về tập tất cả những người x là tổ tiên của Mai (tập cha mẹ, ông

bà, cụ kỵ...của Mai).

4. ? Tổ_tiên (y, Mai)  Tổ_tiên (y, Dương)  - trả về tập tất cả những người y là tổ tiên chung của Mai và Dương. 51

Các thành phần của CSDL suy diễn

Biểu diễn khung nhìn trong CSDL suy diễn:  Trong CSDL suy diễn, các khung nhìn tương ứng với các tân từ dẫn xuất, và được định nghĩa nhờ vào các luật suy diễn. Chẳng hạn ta có khung nhìn “Bà” được định nghĩa bởi một luật suy diễn có đầu luật là tân từ Bà (x, y):

Bà (x, y)  Mẹ (x, z)  Cha_mẹ (z, y)

 Khung nhìn được gọi là “đệ quy”, nếu nó được định nghĩa bởi các luật đệ quy, là các luật mà có tân từ ở đầu luật cũng xuất hiện trong thân luật.

Tổ_tiên (x, y)  Cha_mẹ (x, y) Tổ_tiên (x, y)  Cha_mẹ (x, z)  Tổ_tiên (z, y)

Các thành phần của CSDL suy diễn

Ưu điểm của khung nhìn trong CSDL suy diễn:  Khung nhìn cung cấp một biện pháp bảo vệ vì chúng ngăn ngừa người dùng truy cập tới dữ liệu bên ngoài khung nhìn của họ.

 Làm đơn giản giao diện người dùng, vì có thể bỏ qua

những dữ liệu không liên quan đến người dùng.  Ví dụ: Bà(x, y) Mẹ(x, z)  Cha_mẹ(z, y),  thì khung nhìn Bà(x, y) chỉ cung cấp thông tin về người bà x và người cháu y, còn thông tin về cha mẹ (tức z) được che dấu bởi định nghĩa của khung nhìn.

Các thành phần của CSDL suy diễn

Ưu điểm của khung nhìn trong CSDL suy diễn:  Khung nhìn hỗ trợ tính độc lập logic của dữ liệu, vì nó cho phép thay đổi cấu trúc logic của dữ liệu trong CSDL suy diễn, mà không cần phải tiến hành các thay đổi tương ứng cho các luật khác.  Ví dụ: giả sử tân từ cơ sở Bố (x, y) phải được thay bằng hai tân từ Bố1(x, y) và Bố2(x, y), mỗi tân từ chứa một tập con các xuất hiện của Bố(x, y), khi đó ta xem Bố(x, y) là một tân từ khung nhìn được định nghĩa bởi:

Bố (x, y)  Bố1 (x, y) Bố (x, y)  Bố2 (x, y),  thì ta không cần phải thay đổi các luật tham chiếu tới tân từ gốc Bố (x,

Nguyên lý của thuật toán suy diễn

 Thuật toán suy diễn là một thủ tục để chứng minh một công thức T từ tập các công thức {A1, A2, ...,An} đã được biết là đúng.

 T còn được gọi là định lý cần chứng minh, còn A1, A2, ...,An gọi là các tiên đề. Nếu tồn tại một chứng minh của T từ {A1, A2, ...,An}thì ta ký hiệu:

{A1, A2, ...,An}├ T.

 Một quy tắc suy diễn là một quy tắc cho phép sinh ra một công thức từ hai hoặc nhiều công thức. Có 2 qui tắc suy diễn: Quy tắc suy diễn Modus ponens và Quy tắc riêng biệt hóa

Nguyên lý của thuật toán suy diễn

Quy tắc suy diễn Modus ponens.  Modus ponens (phương pháp khẳng định): Cho một luật P Q (được thừa nhận là đúng), nếu quan sát được sự kiện P (là đúng) thì suy diễn ra sự kiện Q (là đúng).

Ký hiệu quy tắc Modus ponens:

 Quy tắc “đảo” của Modus ponens là quy tắc Modus

tollens, còn gọi là “phương pháp phủ định”

Ký hiệu quy tắc Modus tollens:

Nguyên lý của thuật toán suy diễn

Thí dụ Quy tắc suy diễn Modus ponens. 1. Suy diễn theo quy tắc Modus ponens:  Luật: Nếu hôm nay là thứ bẩy thì tôi sẽ đến thư viện. (P 

 Quan sát: Hôm nay là thứ bẩy. (P)  Suy diễn: Vậy tôi sẽ đến thư viện. (Q). 2. Suy diễn theo quy tắc Modus tollens:  Luật: Nếu hôm nay là thứ bẩy thì tôi sẽ đến thư viện. (P 

 Quan sát: Hôm nay tôi không đến thư viện. (Q).  Suy diễn: Vậy hôm nay không phải là thứ bẩy. ( P)

Nguyên lý của thuật toán suy diễn

Quy tắc riêng biệt hóa  Quy tắc riêng biệt hóa cho phép suy ra F(a) từ công thức: x

F(x). Một cách trực quan, có nghĩa là nếu F(x) đã được chứng minh (là đúng) với mọi giá trị của x, thì F(a) cũng được chứng minh.

 Ký hiệu quy tắc riêng biệt hóa:

Một số kiểu tấn công suy diễn

 Một số tấn công suy diễn thống kê

 Xét CSDL thống kê về công nhân sau::

Chức vụ Phòng Tuổi Giới tính Lương Tên ID

Nhân viên Maketing 29 F 3500 Nam 01

Trưởng phong Kế hoạch 33 M 6200 Lan 02

Nhân viên Kế hoạch 27 4000 Huệ 03

Minh Giám sát viên Maketing 24 F 3600 04

05 Quỳnh Nhân viên Kế hoạch 24 F 2900

Một số kiểu tấn công suy diễn

 Tấn công trực tiếp: Ví dụ SELECT Ten FROM Employees WHERE Luong>4.360 => Giải pháp: Dùng bộ lọc thống kê

 Tấn công dựa vào đếm

Đây là loại tấn công bằng cách kết hợp giá trị đếm với giá trị tổng để thu được thông tin bí mật.Ví dụ:

COUNT ( ChucVu= ‘Trưởng phòng’, Phong=‘Kế hoạch’) =1 SUM (Salary, (ChucVu= ‘Trưởng phòng’, Phong=‘Kế hoạch’))

4.3 Một số kiểu tấn công suy diễn

 Tấn công dựa vào trình theo dõi (…)  Tấn công hệ tuyến tính (…)

Nội dung

 4.5 Khung làm việc chung dành cho việc so sánh các

kỹ thuật chống suy diễn

Các kỹ thuật kiểm soát suy diễn

 Các kỹ thuật chống suy diễn:

Từ sự phân loại tổng quát các kỹ thuật chống suy diễn do Denning và Schlorer (1983) và Adam, Wortmann (1989) đưa ra, ta có thể phân loại các kỹ thuật này thành:  Kỹ thuật khái niệm  Kỹ thuật dựa vào hạn chế  Kỹ thuật dựa vào gây nhiễu  Kỹ thuật gây nhiễu dữ liệu  Kỹ thuật gây nhiễu đầu ra

Kỹ thuật khái niệm

 Làm việc ở mô hình khái niệm của SDB, để

tìm ra các tấn công suy diễn có thể có

 Gồm hai kỹ thuật:  Mô hình lưới  Phân hoạch khái niệm

Kỹ thuật khái niệm

 Mô hình lưới: do Denning và Schlorer đề

xuất, 1983.  Là một mô hình khái niệm cung cấp nền tảng cho việc phát hiện những tấn công suy diễn có thể xảy ra với SDB.

 Xuất phát từ thông tin thống kê được gộp ở nhiều mức khác nhau có thể gây dư thừa dữ liệu => người dùng có thể khám phá dữ liệu nhạy cảm.

Kỹ thuật khái niệm

 Mô hình lưới:

 Dựa vào cấu trúc lưới  Các bảng m-chiều (0<=m<=N, N là số thuộc tính của bảng SDB): là các bảng được gộp dữ liệu từ một hay nhiều thuộc tính.

 Tính trên một thống kê nào đó như: COUNT,

SUM, AVG,…

Kỹ thuật khái niệm

 Ví dụ: mô hình lưới cho SDB về công nhân (N=3) (Bảng SDB về công nhân như sau)

BSD Table

Năm sinh

Giới tính

Mã phòng

Phong1

Phong2

Phong3

Bảng 3-chiều

1941-1951

1952-1962

>1962

Kỹ thuật khái niệm

 Ví dụ: (thống kê Count)

 Các bảng 2-chiều

BS Table

Giới tính

Năm sinh

1941-1951

F 4

27 16

1952-1962 >1962

30 30

BD Table

SD Table

Mã phòng

Năm sinh

Giới tính

Mã phòng Phong2

Phong1

Phong1 Phong2

Phong3

Phong3 3

1941-1951

11 32

12 12

M F

37 41

22 12

6 11

1952-1962 >1962

Kỹ thuật khái niệm

 Ví dụ: (thống kê Count)

 Các bảng 1-chiều

Giới tính

Năm sinh

Mã phòng

1941-1951

Phòng1

Phòng2

Phòng3

1952-1962

>1962

 Bảng 0-chiều:

129

Kỹ thuật khái niệm

 Cấu trúc lưới:

 Ưu điểm: là một mô hình an toàn hiệu quả cho nghiên cứu các vấn đề suy diễn và các phương pháp kiểm soát suy diễn. Với nhiều bảng ở các mức gộp khác nhau, ta có thể phân tích:  Các kiểu tấn công suy diễn bằng câu truy vấn

COUNT, SUM, AVERAGE,…

 Các tấn công kiểu kết hợp các câu truy vấn khác

nhau để suy diễn ra dữ liệu nhạy cảm…

 So sánh các kiểm soát suy diễn: hạn chế tập truy vấn

và gây nhiễu dữ liệu

Kỹ thuật khái niệm

 Cấu trúc lưới:

 Nhược điểm: mô hình lưới không thể cung cấp tính đầy đủ của cơ sở dữ liệu và không phù hợp với cơ sở dữ liệu động, vì khi cập nhật SDB ta phải cập nhật tất cả các bảng trong mô hình lưới, do đó rất tốn công.

Kỹ thuật khái niệm

 Phân hoạch khái niệm: do Chin và

Ozsoyoglu đề xuất, 1981.  Giải quyết các vấn đề chống suy diễn trong giai

đoạn thiết kế khái niệm của SDB.

 Dựa vào việc định nghĩa tập các cá thể của SDB tại mức khái niệm, được gọi là các lực lượng (populations).

 Dựa vào các điều kiện cần kiểm tra nhằm tránh

suy diễn

Kỹ thuật khái niệm

 Phân hoạch khái niệm:

 Hình sau minh hoạ mô hình khái niệm của một cơ sở dữ liệu thống kê về công nhân - Employee SDB, trong đó lực lượng Employee được phân tách thành 5 lực lượng con, tuỳ thuộc vào các thuộc tính “giới tính” và "Dept- Code“-Mã phòng.

 Lực lượng nguyên tử A-Population là lực

lượng không phân tách được nữa

4.4.1 Kỹ thuật khái niệm

 Phân hoạch khái niệm:

Employee

Female

Dept2

Male

Dept3

Dept1

Male Employee Dept1

Male Employee Dept2

Female Employee Dept1

Male Employee Dept3

Female Employee Dept2

Female Employee Dept3

Kỹ thuật khái niệm

 Phân hoạch khái niệm:

 Để hỗ trợ việc xác định các yêu cầu an toàn thống kê trong mô hình khái niệm này, người ta đã đề xuất hệ thống tiện ích quản lý an toàn thống kê (SSMF) gồm có 3 module, cụ thể là PDC, UKC và CEC:

 PDC (Xây dựng định nghĩa lực lượng- Population

Definition Construct)

 UKC (Xây dựng trình độ người dùng - User

Knowledge Construct)

 CEC (Bộ thi hành và kiểm tra ràng buộc -

Constraint Enforcer and Checker)

Kỹ thuật dựa vào hạn chế

 Các kỹ thuật này chống suy diễn bằng cách hạn chế các câu truy vấn thống kê theo một điều kiện hạn chế nào đó  Kiểm soát kích cỡ tập truy vấn  Kiểm soát kích cỡ tập truy vấn mở rộng  Kiểm soát chồng lấp tập truy vấn  Kiểm soát dựa vào kiểm toán  Gộp  Kỹ thuật giấu ô  Kỹ thuật kết hợp

Kỹ thuật dựa vào hạn chế

 Kiểm soát kích cỡ tập truy vấn  Kiểm soát kích cỡ tập truy vấn mở rộng  Kiểm soát chồng lấp tập truy vấn  Kiểm soát dựa vào kiểm toán  Gộp  Kỹ thuật giấu ô  Kỹ thuật kết hợp

Kiểm soát kích cỡ tập truy vấn

 Một thống kê q(C) chỉ được phép nếu tập truy vấn

của nó, X(C), thoả mãn quan hệ sau:  k  X(C) N-k  0  k  N/2

 Trong đó, N là tổng số bản ghi trong SDB, k do

DBA định nghĩa.

Kiểm soát kích cỡ tập truy vấn

Query Set Restriction

Query 2

Query 1

Original Database

Query Results

Query 2 Results

Query Results

Query 1 Results

Kiểm soát kích cỡ tập truy vấn

 Kiểm soát này ngăn chặn các tấn công đơn giản, dựa

vào các tập truy vấn rất nhỏ hoặc rất lớn.

 Ví dụ:

 Người dùng yêu cầu thống kê q1 = Count (C) =1, =>

có một cá nhân A thỏa mãn C.

 Đưa ra thống kê q2 = Count (C  C')

 Nếu q2 = 1 => A thỏa mãn C’  Ngược lại, A không thỏa mãn C’

 Đưa ra thống kê khác, ví dụ Sum(C, Ai)

=> Kiểm soát kích cỡ tập truy vấn không cho phép đưa ra

q1, q2.

Kiểm soát kích cỡ tập truy vấn

 Nhược điểm:

 Hạn chế khả năng hữu ích của SDB  Chỉ ngăn chặn được các tấn công đơn giản, khó có thể ngăn chặn được các tấn công phức tạp, như: Trình theo dõi, Tấn công hệ tuyến tính.

Tấn công dựa vào trình theo dõi (Denning&Schlorer)

 Trình theo dõi (Tracker): là một tập các công thức đặc trưng, có thể được sử dụng để đưa thêm bản ghi vào các các tập truy vấn kích cỡ nhỏ, làm cho kích cỡ của chúng nằm trong khoảng [k, N-k]. Thông qua các trình theo dõi có thể tính toán được các thống kê bị hạn chế.

 Giả sử C là công thức đặc trưng người dùng yêu cầu

 T là một trình theo dõi. T thỏa mãn điều kiện:

k<|T|< N-k.

Tấn công dựa vào trình theo dõi (Denning&Schlorer)

Kiểu 1:  Giả thiết:

 User cần tính Count(C)  Công thức C = (AB), và Count (C) = 1.

=> Câu truy vấn này bị cấm

 Tấn công:

 Tính T = A B thỏa mãn k<|T|< N-k.  Tính gián tiếp Count (C):

Count(C)= Count (AB) = Count(A)-Count(AB) Count(C) = Count(A) - Count(T)

Ví dụ SDB về công nhân:

Tên Chức vụ Phòng Tuổi Giới tính Lương ID

Nam Nhân viên Maketing 24 F 3500 01

Lan Trưởng phong Kế hoạch 33 M 6200 02

Huệ Nhân viên Kế hoạch 27 4000 03

Minh Giám sát viên Maketing 24 F 3600 04

05 Quỳnh Nhân viên Kế hoạch 24 F 2900

Phòng Tuổi Giới tính Lương Chức vụ Tên ID

Nhân viên Maketing 24 F 3500 Nam 01

Trưởng phong Kế hoạch 33 M 6200 Lan 02

Nhân viên Kế hoạch 4000 27 Huệ 03

Ví dụ SDB về công nhân:

Minh Giám sát viên Maketing 24 F 3600 04

05 Quỳnh

Nhân viên

2900

24 F

Kế hoạch  C = (Phong=‘Kế hoạch’)(Tuoi =24) (GioiTinh=F)  User cần tính Count(C)

 Count (C) = 1.=> Câu truy vấn này bị cấm (k=1)

 Tấn công:

 Đặt C=(A B )

 A = (Phong=‘Kế hoạch’)  B = (Tuoi =24) (GioiTinh = F)

 Tính T = A B thỏa mãn k

Count(C)= Count (AB) = Count(A)-Count(AB) Count(C) = Count(A) - Count(T)

= 3-2 =1

Tấn công dựa vào trình theo dõi (Denning&Schlorer)

Kiểu 2:  Giả thiết:

 Cần tính Count(C), Count(C)<=k => Thống kê này bị cấm

 Tấn công: (trường hợp này Q = Count)  Chọn T thỏa mãn: k<|T|, | T |< N-k.  Q(D)= Q(All) = Q(T) + Q(T)

(trong trường hợp Q(All) bị cấm )

 d

Ví dụ SDB về các vụ tai nạn môtô

HoTen

Tuoi Đ/C

MauXe

LoaiXe

ThoiGian CoLoi

SayRuou

Tài

Xanh

Honda

13.30

Hoàng

Đỏ

Toyota

6.25

Minh

42 PT

Trắng

Honda

17.45

1

0

Minh

Vàng

Volkswagon

3.30

Hòa

Xanh

Honda

6.30

HoTen

Tuoi

Đ/C MauXe

LoaiXe

ThoiGian

CoLoi

SayRuou

Tài

Xanh

Honda

13.30

Hoàng

Đỏ

Toyota

6.25

Minh

Honda

Trắng

17.45

Ví dụ SDB về các vụ tai nạn môtô

Minh

Vàng

Volkswagon

3.30

Hòa

Xanh

Honda

6.30

 Giả thiết: C = (Ten=‘Minh’) (MauXe=‘Trắng’)

 Count(C)=1, SUM(CoLoi, C)=1 => 2 Câu truy vấn này bị cấm (k=1)

 Tấn công:

 Chọn T = (Tuoi<25) => Count(T)=2, Count(T)=3  Count(All)= Count(T)+Count(T) =5  Count(C) = Count(CVT) + Count(CVT)–Count(All)

= 3 + 3 – 5 = 1

 SUM(CoLoi, C)= Sum(CoLoi, CVTuoi<25) + Sum(CoLoi,

CVTuoi>=25) – Sum(CoLoi,All) = 2 + 3 – 4 = 1.

=> Anh Minh có lỗi trong vụ tai nạn đó!

Tấn công hệ tuyến tính:

 Là loại tấn công bằng cách giải một hệ

phương trình có dạng: HX = Q 1,1x1 + 1,2x2 + . . . + 1,nxN = q1 2,1x1 + 2,2x2 + . . . + 2,NxN = q2

. .

k,1x1 + k,2x2 + . . . + k,nxN = qK Mỗi phương trình tương ứng một câu truy vấn

Tấn công hệ tuyến tính:

 H là ma trận truy vấn

 H[i,j] = 1 nếu bản ghi xjX(Ci), (tương ứng qi)  H[i,j] = 0 nếu ngược lại

 x1 ,..., xN là giá trị của N bản ghi  Q = (q1, ..., qk) là vector của các thống kê đưa ra

Ví dụ SDB về công nhân:

Nam

Nhân viên

Maketing

3500

Tên Chức vụ Phòng Tuổi Giới tính Lương ID

Lan Trưởng phong Kế hoạch 33 M 6200 02

Huệ Nhân viên Kế hoạch 27 4000 03

Minh Giám sát viên Maketing 24 F 3600 04

05 Quỳnh Nhân viên Kế hoạch 24 F 2900

Tên ID Chức vụ Phòng Tuổi Giới tính Lương

Nam 01 Nhân viên Maketing 24 F 3500

Lan 02 Trưởng phong Kế hoạch 33 M 6200

Huệ 03 Nhân viên Kế hoạch 4000 27

Ví dụ SDB về công nhân:

04 24 F 3600 Minh Giám sát viên Maketing

05

24 F

2900

Quỳnh

Nhân viên

Kế hoạch

 C = (Phong=‘Kế hoạch’)(Tuoi =24) (GioiTinh=F)  Cần tính q= Count(C) =1  Tính q1 = Count(Phong=‘Kế hoạch’)  Tính q2 = Count(Phong=‘Kế hoạch’, GioiTinh =M)

 q3= Count(Phong=‘Kế hoạch’, GioiTinh =F)

= q1 – q2 = 3 - 2 =1.

 q =q3 =1

Nam

Nhân viên

Maketing

3500

Tên ID Chức vụ Phòng Tuổi Giới tính Lương

Lan 02 Trưởng phong Kế hoạch 33 M 6200

Huệ 03 Nhân viên Kế hoạch 27 4000

Ví dụ SDB về công nhân:

04 Minh Giám sát viên Maketing 24 F 3600

05

24 F

2900

Quỳnh

Nhân viên

Kế hoạch

 C = (Phong=‘Kế hoạch’)(Tuoi =24) (GioiTinh=F)  Cần tính q= Sum(Luong, C)  Tính q1=X(C1) = Count(Phong=‘Kế hoạch’) = 3  Tính q2 =X(C2) = Count(Phong=‘Kế hoạch’, GioiTinh =M)=2  Sum(Luong, C) = Sum(Luong, C1) – Sum(Luong,C2)

= (6200+4000+2900) – (6200+4000) = 2900.

 Như vậy, kẻ tấn công đã tìm ra lương của người thỏa mãn C.

Tấn công hệ tuyến tính:

 Ví dụ

 Giả sử cần tính q3= Sum(Sex = M  Dept-Code = Dept3 Birth-Year = 1968, Salary), count = 1.

 Tương ứng ta có hệ sau:

 Count1 = 7

 Count2 = 8  Từ đó, tính được: x5 = q2 – q1 = 4.  Và người dùng biết cout (q3) = 1 => tìm được lương của người này

Kiểm soát kích cỡ tập truy vấn

 Ưu điểm:

 Đưa ra kêt quả chính xác  Chỉ chống được tấn công suy diễn đơn giản

 Nhựơc điểm:

 Không chống được một số tấn công phức tạp

như: Trình theo dõi, Hệ tuyến tính.

 Hạn chế khả năng hữu ích của SDB (vì hạn chế

nhiều câu truy vấn)

Kỹ thuật dựa vào hạn chế

Kiểm soát kích cỡ tập truy vấn mở rộng

 Nhược điểm của kiểm soát kích cỡ tập truy vấn là do các công thức đặc trưng liên quan đến nhau (ví dụ: C và T).

 Cải tiến: tăng số lượng các tập truy vấn cần

được kiểm soát.  Cho công thức đặc trưng C  Tìm tập truy vấn ngầm định của C

Kiểm soát kích cỡ tập truy vấn mở rộng

 Cho trước một thống kê bậc m có dạng như sau:

 q(A1 = a1 A2= a2 ...  Am =am) Hoặc:  q(A1 = a1 A2= a2 ...  Am =am)

 Khi đó, tồn tại 2m = Cm

1 +Cm

2 +…+ Cm

m-1 tập 0 + Cm truy vấn ngầm định, tương ứng với các thống kê sau đây:  q(A1 = a1 A2= a2 ...  Am =am)  q(A1 = a1 A2= a2 ...  Am =am)  ...  q(A1= a1 A2= a2 ...  Am =am)  q(A1 = a1 A2= a2 ...  Am =am)  ...  q(A1 = a1 A2= a2 ...   Am =am)

Kiểm soát kích cỡ tập truy vấn mở rộng

 Ưu điểm:

 Chống được các kiểu tấn công: Trình theo dõi, Hệ

tuyến tính

 Nhược điểm:

 Tốn công: phải kiểm tra 2m tập truy vấn ngầm định

(hàm mũ tăng rất lớn theo m).

=> Giải pháp này khó thực hiện  Ngoài tập truy vấn ngầm định, kẻ tấn công có thể sử

dụng những công thức khác liên quan đến tập truy vấn này để tính ra truy vấn yêu cầu.

100

Kiểm soát kích cỡ tập truy vấn mở rộng

 Ví dụ: (tấn công ngoài tập truy vấn ngầm định)  Chúng ta xét 2 thuộc tính Ai và Aj trong SDB  Ai có n giá trị (ai1,..., ain) và Aj có p giá trị (aj1,..., ajp)  Xét câu truy vấn thống kê:  q(Ai  Aj) được tạo thành n x p câu truy vấn con:

 q(Ai=ai1  Aj=aj1),…, q(Ai=ai1  Aj=ajp)  q(Ai=ai2  Aj=aj1),…, q(Ai=ai2  Aj=ajp)  …  q(Ai=ain  Aj=aj1),…, q(Ai=ain  Aj=ajp)

101

Kiểm soát kích cỡ tập truy vấn mở rộng

 Ví dụ: (tấn công ngoài tập truy vấn ngầm định)

 Trong các câu truy vấn trên, giả thiết chỉ có truy

vấn sau là nhạy cảm:

q(Ai=ai1  Aj=aj1) = q(ai1 aj1)  Tập truy vấn ngầm định gồm: 22 =4 tập truy

vấn:  q(ai1  aj1), q(ai1  aj1)  q( ai1  aj1), q( ai1  aj1). => 4 câu truy vấn này sẽ bị cấm theo KS kích cỡ tập

truy vấn mở rộng

102

Kiểm soát kích cỡ tập truy vấn mở rộng

 Ví dụ: (tấn công ngoài tập truy vấn ngầm định)  Tuy nhiên, kẻ tấn công có thể thực hiện như sau:  q(ai1  aj1) = q(aj1) - q(aj1 ai1 )

(Bị cấm) = q(aj1) - [q(aj1ai2)+ ...+ q(aj1ain)]

(Không bị cấm)

103

Kỹ thuật gộp (microaggregation)

 Các câu truy vấn thống kê được tính toán trên các cá thể tổng hợp. Dữ liệu riêng sẽ được nhóm lại thành một khối nhỏ trước khi đưa ra.

 Giá trị trung bình của nhóm gộp sẽ thay thế cho mỗi giá trị riêng của dữ liệu được gộp  Kỹ thuật này giúp ngăn chặn khám phá dữ

liệu riêng.

104

Kỹ thuật gộp (microaggregation)

 Ví dụ: Cục thống kê nông nghiệp quốc gia (NASS) công bố dữ liệu về các nông trường, trang trại. Để bảo vệ chống lại sự khám phá dữ liệu, dữ liệu chỉ được đưa ra ở mức vùng. Dữ liệu tại các nông trại ở mỗi vùng sẽ được gộp để bảo vệ tính riêng tư và tránh bị khám phá.

105

Kỹ thuật gộp (microaggregation)

106

Kỹ thuật gộp (microaggregation)

107

Kỹ thuật gộp (microaggregation)

 Ưu điểm:

 Tránh được việc để lộ thông tin nhạy cảm

 Nhựơc điểm:

 Kết quả đưa ra không chính xác

108

Kỹ thuật Giấu ô (Cell suppression)

 Kỹ thuật này được thiết kế cho các SDB vĩ mô (đưa ra các thống kê trong bảng 2- chiều, ví dụ các thống kê dân số).

 Giấu ô: trong các bảng, giấu đi tất cả các ô tương ứng với các thống kê nhạy cảm và các ô tương ứng với các thống kê có thể gián tiếp khám phá ra các thống kê nhạy cảm (Giấu bổ sung).

109

Kỹ thuật Giấu ô (Cell suppression)

 Tiêu chuẩn giấu ô:

 Thống kê Count: kích cỡ tập truy vấn bằng 1,

nghĩa là Count(C) =1

 Thống kê Sum, tiêu chuẩn nhạy cảm được sử dụng là quy tắc «đáp ứng n, trội k% » . Theo tiêu chuẩn này, một thống kê là nhạy cảm nếu n giá trị thuộc tính của n hoặc ít hơn n bản ghi tạo thành k% hoặc lớn hơn k% trong toàn bộ thống kê Sum đó. Các tham số n và k được giữ bí mật và do DBA xác định.

110

Kỹ thuật Giấu ô (Cell suppression)

 Ví dụ: Giả sử n = 2 và k = 90%

Giới tính

Mã phòng

Tổng lương

Phong1 Phong2 Phong3

M F

135 120

80 360

50 100

265 580

Tổng lương

255

440

150

845 Tổng lương của nam,nữ công nhân trong các phòng

111

Kỹ thuật Giấu ô (Cell suppression)

 Nếu chỉ có 1 công nhân nam làm ở phòng ‘phong3’

thì ta có: (n = 1 và k = 90%) Count(MaPhong = Phong3  GioiTinh=M) = 1 Sum(Lương, MaPhong = Phong3  GioiTinh=M) = 50

 Do đó ô (1,3) là ô nhạy cảm cần phải giấu đi vì

lương của công nhân này tạo thành 100% của toàn bộ tổng lương tại ô đó (với n=1 <2 trội 100%>90%).

112

 Giấu bổ sung ô (2,3) vì nếu lấy tổng của cột 3 trừ đi tổng ở ô (2,3) sẽ tìm được tổng của ô (1,3).

Kỹ thuật Giấu ô (Cell suppression)

 Kết quả:

Giới tính

Mã phòng

Tổng

lương

Phong1

Phong2

Phong3

M F

135 120

80 360

_ _

265 580

Sum

255

440

150

845

113

Kỹ thuật Giấu ô (Cell suppression)

 Tuy nhiên, để an toàn, trên hàng chứa một ô bị

giấu, phải giấu bổ sung thêm 1 ô nữa!

Giới tính

Mã phòng

Tổng

lương

Phong1

Phong2

Phong3

_

M F

135 _

_ _

265 580

Sum

255 360 440

150

845

114

Kỹ thuật Giấu ô (Cell suppression)

 Ưu điểm:

 Chống được các tấn công kết hợp dựa vào

Count và Sum

 Nhược điểm:

 Hạn chế khả năng hữu ích của SDB, vì phải che

giấu một số ô trong CSDL.

115

Các kỹ thuật dựa vào gây nhiễu

 Kỹ thuật gây nhiễu dữ liệu

 Kỹ thuật gây nhiễu đầu ra

116

Data Perturbation

117

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu cố định (fixed perturbation)  Gây nhiễu dựa vào truy vấn

118

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu cố định (fixed perturbation)

 Cho N là kích cỡ của SDB và ta xét thuộc tính Aj.  Mỗi giá trị thực xij (với i =1,...,N) của một thuộc tính

Aj bị thay thế bằng một giá trị gây nhiễu x‘ij x‘ij = xij + ei với i =1,...,N

 Vector e = (x' - x) = (e1,..., eN) là một vector gây

nhiễu ngẫu nhiên

 x = (x1j ,..., xNj), x'=(x‘1j ,..., x‘Nj) là các vector của giá trị thực và giá trị gây nhiễu của các bản ghi trong SDB, dành cho thuộc tính Aj

119

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu cố định (fixed perturbation)

 e = (e1,..., eN), mỗi thành phần ei là các biến ngẫu

nhiên, độc lập tuyến tính.

E(ei) = 0, D(ei) = 2

 Các giá trị của mỗi thuộc tính Aj sẽ được cộng thêm

một vector e ngẫu nhiên.

 Xác suất lỗi trong một câu truy vấn vượt quá giá trị

giới hạn  cho trước là:

 P(|q’(C) – q(C)| )>= | |X(C)| | )<= 2/(|X(C)|2 )  Như vậy |X(C)| càng lớn thì xác suất lỗi càng nhỏ

120

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu cố định (fixed perturbation)  Ưu điểm:

 Chống được nhiều tấn công, kể cả tấn công tính

trung bình (lặp nhiều lần)

 Nhược điểm:

 Chỉ áp dụng cho thuộc tính số  Kết quả trả về không chính xác

121

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu dựa vào truy vấn

 Không yêu cầu tạo một SDB nhiễu  Với mỗi truy vấn được tạo ra trong SDB, một hàm gây nhiễu sẽ được áp dụng với tất cả các thuộc tính của tập truy vấn đó.

 Giả sử thống kê q(C), với mọi giá trị xij thuộc

ij = f(xij).

X(C): x’  Giá trị  = x’

ij – xij là ngẫu nhiên.

122

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu dựa vào truy vấn

 Thống kê Sum:

 Xét thống kê S= q(C) = Sum(C, Aj), n là số

lượng các bản ghi tập truy vấn X(C). = f(xij) = xij + z1 ( xij -

’ với xij

) + z2

 S’ =  z1 và z2 là các biến ngẫu nhiên độc lập được

sinh ra cho mỗi bản ghi

123

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu dựa vào truy vấn

 Thống kê Count:

 Giả sử thống kê Count(C) = m  m’ =

Với E(z3) = 1 và Var(z3) = a2

1 /m,

 và z3 được sinh ngẫu nhiên và độc lập với các

bản ghi xi trong X(C).

 E(m’) = m và Var(m’) = a2

124

Kỹ thuật gây nhiễu dữ liệu

 Gây nhiễu dựa vào truy vấn  Ưu điểm:

 Gây nhiễu dữ liệu nên chống được nhiều tấn

công  Nhược điểm:

 Với mỗi thống kê, lại phải áp dụng một hàm

gây nhiễu f, với gía trị nhiễu=> tốn công, giảm hiệu năng hệ thống.

 Kết quả đưa ra không chính xác.

125

Kỹ thuật gây nhiễu đầu ra

126

Kỹ thuật gây nhiễu đầu ra

 Các kỹ thuật gây nhiễu đầu ra thực hiện sửa đổi trên các kết quả được tính toán chính xác của một câu truy vấn thống kê, trước khi chuyển nó cho người sử dụng.

 Kỹ thuật Làm tròn (rounding)

127

Kỹ thuật gây nhiễu đầu ra

 Kỹ thuật Làm tròn (rounding)

 Kết quả mọi câu truy vấn sẽ được làm tròn:

Q' = r(Q)

 Làm tròn có hệ thống (systematic rounding)  Làm tròn ngẫu nhiên (random rounding)

128

Kỹ thuật gây nhiễu đầu ra

 Làm tròn có hệ thống (systematic rounding)  Q' là một kết quả sửa đổi, nó được tính toán cho

thống kê yêu cầu q(C).

 b'= (b+1)/2 (ký hiệu   chỉ làm tròn xuống số

nguyên gần nhất), giá trị b do Admin chọn.

 d = Q mod b.

 r(Q) =

129

Kỹ thuật gây nhiễu đầu ra

 Làm tròn ngẫu nhiên (random rounding)

 Q' là một kết quả sửa đổi, nó được tính toán cho thống

kê yêu cầu q(C).

 b'= (b+1)/2 (ký hiệu   chỉ làm tròn xuống số

nguyên gần nhất)

 d = Q mod b.

 r(Q) =

 Xác suất p = d/b

130

Kỹ thuật gây nhiễu đầu ra

 Kỹ thuật Làm tròn (rounding)  Ưu điểm: Bảo vệ được những tấn công đơn

giản.

 Nhược điểm:

 Không chống được những tấn công trung bình,

tấn công trình theo dõi

 Kết quả đưa ra cũng không chính xác.

131

Kỹ thuật mẫu ngẫu nhiên

 Cục điều tra dân số Mỹ sử dụng kỹ thuật mẫu ngẫu nhiên để ngăn chặn suy diễn trong các cơ sở dữ liệu thống kê.

 Ý tưởng: của kỹ thuật này là sử dụng các

mẫu bản ghi từ các tập truy vấn tương ứng với các truy vấn thống kê, thay vì lấy mẫu trong toàn bộ SDB.

132

Kỹ thuật mẫu ngẫu nhiên

 Cơ chế cơ bản của kỹ thuật này là thay thế tập truy vấn (có liên quan đến một câu truy vấn thống kê) bằng một tập truy vấn được lấy mẫu (sampled query set) gồm một tập con các bản ghi được chọn lựa chính xác trong tập truy vấn gốc. Sau đó, tiến hành tính toán thống kê yêu cầu trên tập truy vấn mẫu này. Sử dụng một hàm chọn f(C, i) để chọn lựa các bản ghi từ tập truy vấn gốc tương ứng với thống kê q(C) mà người dùng yêu cầu.

133