›
›

Bài giảng Bảo mật cơ sở dữ liệu - Chương 5: An toàn CSDL thống kê

pdf 136 trang phuongnguyen 2740
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Bảo mật cơ sở dữ liệu - Chương 5: An toàn CSDL thống kê", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_bao_mat_co_so_du_lieu_chuong_5_an_toan_csdl_thong.pdf

Nội dung text: Bài giảng Bảo mật cơ sở dữ liệu - Chương 5: An toàn CSDL thống kê

  1. CHƯƠNG 5 1
  2. 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. 2
  3. 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 3
  4. 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 4
  5. 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 5
  6. 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ụ) 6
  7. 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) as avg_Luong, SUM(Luong) as sum_luong from Nhanvien Group by chucvu Order by chucvu 7
  8. 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 8
  9. 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ụ: 9
  10. 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ê. 10
  11. 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 đó. 11
  12. 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, ). 12
  13. 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. 13
  14. 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. 14
  15. Mô hình làm lộ SDB 15
  16. Ví dụ về làm lộ một SDB Ví dụ 1 (lộ chính xác) 16
  17. Ví dụ 2 (lộ xấp xỉ) 17
  18. Ví dụ 2 18
  19. 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 19
  20. 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ị. 20
  21. 4.2 Các khái niệm cơ bản và các giả định 21
  22. 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): ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 29 M 3500 02 Lan Trưởng phong Kế hoạch 33 F 6200 03 Huệ Nhân viên Kế hoạch 27 F 4000 04 Minh Giám sát viên Maketing 24 M 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900 22
  23. 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 Nguyễn Văn Tài 25 HN Xanh Honda 13.30 1 1 37 HD Đỏ Toyota 6.25 1 0 Lê sỹ Hoàng Hoàng Văn Minh 42 PT Trắng Audi 17.45 0 0 Vũ Bình Minh 32 PT Vàng Volkswagon 3.30 0 1 Trần Quang Hòa 22 HN Xanh Honda 6.30 1 0 23
  24. 4.2 Các khái niệm cơ bản và các giả định  SDB về các Sinh viên Tên Giới Địa chỉ Phụ cấp Nghiện ma Lớp tính túy Minh M HN 500 1 Toán1 Hải M HD 0 0 Toán2 Tuyết F NĐ 300 0 Tin1 Nam M BG 100 3 Tin2 Phương F NA 200 1 Toán2 Hạnh F HT 100 0 Toán1 24
  25. 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 0 0 100 F 100 200 300 0 Tổng cộng 600 200 300 100 Tổng phụ cấp theo giới tính và theo lớp 25
  26. 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 1 MA02 Nguyễn Thị Hoa Hải Phòng Nhân viên 2000 0 MA03 Vũ Văn Hiển Hà Nội Phó Giám đốc 4000 1 MA04 Trần Thị Mai Nghệ An Trưởng phòng 3000 1 MA05 Nguyễn Quang Huy Hải Phòng Giám đốc 5000 1 MA06 Trần Văn Hải Hà Nam Nhân viên 2000 1 MA03 Lê Minh Sơn Nam Định Nhân viên 2500 0 26
  27. 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 M 10 12 0 F 1 0 3 1952-1962 M 12 10 5 F 20 2 8 >1962 M 15 0 1 F 20 10 0 27
  28. 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). 28
  29. Ví dụ Cho công thức: xy [( Thủ_trưởng(x, y)  Thủ_trưởng(y, x))  Cùng_phòng(y, x)] (1)  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. 29
  30. 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 30
  31. 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 31
  32. 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 Ullman vào năm 1984. 32
  33. 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). 33
  34. 4.1 Giới thiệu 34
  35. 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 35
  36. 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. 36
  37. 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. 37
  38. 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). 38
  39. 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) 39
  40. 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) 40
  41. 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) 41  Bố (x, y)
  42. 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. 42
  43. 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. 43
  44. 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). 44
  45. 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). 45
  46. 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) 46
  47. 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) 47
  48. 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. 48
  49. 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 49 diễn bởi một chương trình Datalog
  50. 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ở. 50
  51. 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
  52. 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) 52
  53. 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. 53
  54. 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, y) 54
  55. 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 55
  56. 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: 56
  57. 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 Q)  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 Q)  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) 57
  58. 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: 58
  59. 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:: ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 29 F 3500 02 Lan Trưởng phong Kế hoạch 33 M 6200 03 Huệ Nhân viên Kế hoạch 27 M 4000 04 Minh Giám sát viên Maketing 24 F 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900 59
  60. 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’)) 60
  61. 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 ( ) 61
  62. 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.4.4 Các kỹ thuật dựa vào mẫu ngẫu nhiên  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 62
  63. 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 63
  64. 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 64
  65. 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. 65
  66. 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, 66
  67. 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 M 10 12 0 F 1 0 3 1952-1962 M 12 10 5 F 20 2 8 >1962 M 15 0 1 F 20 10 0 67
  68. 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 M F 1941-1951 22 4 1952-1962 27 30 >1962 16 30 BD Table SD Table ã phòng Mã phòng Năm sinh M Giới tính Phong1 Phong2 Phong3 Phong1 Phong2 Phong3 1941-1951 11 12 3 M 37 22 6 1952-1962 32 12 13 F 41 12 11 >1962 35 10 1 68
  69. Kỹ thuật khái niệm  Ví dụ: (thống kê Count)  Các bảng 1-chiều Giới tính M F 65 64 Năm sinh Mã phòng 1941-1951 26 Phòng1 Phòng2 Phòng3 1952-1962 58 >1962 46 78 34 17  Bảng 0-chiều: 129 69
  70. 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 70
  71. 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. 71
  72. 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 72
  73. 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 73
  74. 4.4.1 Kỹ thuật khái niệm  Phân hoạch khái niệm: Employee Male Female Dept1 Dept2 Dept3 Male Male Male Female Female Female Employee Employee Employee Employee Employee Employee Dept1 Dept2 Dept3 Dept1 Dept2 Dept3 74
  75. 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) 75
  76. Kỹ thuật dựa vào hạn chế 76
  77. 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 77
  78. 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 78
  79. 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. 79
  80. Kiểm soát kích cỡ tập truy vấn Query Set Restriction Query 2 Query 1 Original Database Query 2 Query Results K Results Query 1 K Query Results Results 80
  81. 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. 81
  82. 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. 82
  83. 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. 83
  84. 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) 84
  85. Ví dụ SDB về công nhân: ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 24 F 3500 02 Lan Trưởng phong Kế hoạch 33 M 6200 03 Huệ Nhân viên Kế hoạch 27 M 4000 04 Minh Giám sát viên Maketing 24 F 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900 85
  86. ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 24 F 3500 02 Lan Trưởng phong Kế hoạch 33 M 6200 03 Huệ NhânVí viên dụ SDBKế hoạch về27 côngM nhân:4000 04 Minh Giám sát viên Maketing 24 F 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900  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<Coun(T)=2< 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) = 3-2 =1 86
  87. 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) 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 87
  88. Ví dụ SDB về các vụ tai nạn môtô HoTen Tuoi Đ/C MauXe LoaiXe ThoiGian CoLoi SayRuou Tài 25 HN Xanh Honda 13.30 1 1 Hoàng 37 HD Đỏ Toyota 6.25 1 0 Minh 42 PT Trắng Honda 17.45 1 0 Minh 19 PT Vàng Volkswagon 3.30 0 1 Hòa 22 HN Xanh Honda 6.30 1 0 88
  89. HoTen Tuoi Đ/C MauXe LoaiXe ThoiGian CoLoi SayRuou Tài 25 HN Xanh Honda 13.30 1 1 Hoàng 37 HD Đỏ Toyota 6.25 1 0 Minh Ví 42dụ SDBPT Trắng về cácHonda vụ tai17.45 nạn môtô1 0 Minh 19 PT Vàng Volkswagon 3.30 0 1 Hòa 22 HN Xanh Honda 6.30 1 0  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 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,All) = 2 + 3 – 4 = 1. => Anh Minh có lỗi trong vụ tai nạn đó! 89
  90. 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 90
  91. 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 91
  92. Ví dụ SDB về công nhân: ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 29 F 3500 02 Lan Trưởng phong Kế hoạch 33 M 6200 03 Huệ Nhân viên Kế hoạch 27 M 4000 04 Minh Giám sát viên Maketing 24 F 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900 92
  93. ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 24 F 3500 02 Lan Trưởng phong Kế hoạch 33 M 6200 03 Huệ NhânVí viên dụ SDBKế hoạch về27 côngM nhân:4000 04 Minh Giám sát viên Maketing 24 F 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900  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) q1 0x1 1x 2 1x3 0x 4 1x5 3 q2 0x1 1x 2 1x3 0x 4 0x5 2 q3= Count(Phong=‘Kế hoạch’, GioiTinh =F) = q1 – q2 = 3 - 2 =1. q =q3 =1 93
  94. ID Tên Chức vụ Phòng Tuổi Giới tính Lương 01 Nam Nhân viên Maketing 24 F 3500 02 Lan Trưởng phong Kế hoạch 33 M 6200 03 Huệ VíNhân dụ viên SDBKế về hoạch công27 nhân:M 4000 04 Minh Giám sát viên Maketing 24 F 3600 05 Quỳnh Nhân viên Kế hoạch 24 F 2900  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. 94
  95. 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. q1 Sum (Sex F  Dept - Code Dept3 Birth - Year 1968, Salary) q2 Sum ((Sex F  Sex M)  Dept - Code Dept3 Birth - Year 1968, Salary)  Tương ứng ta có hệ sau:  Count1 = 7 x1 x3 x4 x6 x7 x8 x9 33  Count2 = 8 x1 x3 x4 x5 x6 x7 x8 x9 37  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 95
  96. 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) 96
  97. 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 97
  98. 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 98
  99. 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) m 0 1 2 m-1  Khi đó, tồn tại 2 = Cm + Cm +Cm + + Cm tập 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)  99  q(A1 = a1 A2= a2   Am =am)
  100. 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: m  Tốn công: phải kiểm tra 2 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
  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)  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
  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)  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) 2  Tập truy vấn ngầm định gồm: 2 =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
  103. 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
  104. 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
  105. 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
  106. Kỹ thuật gộp (microaggregation) Age Microaggregated Age 10 11.67 12 Average 11.67 13 11.67 57 56.67 54 Average 56.67 59 56.67 106
  107. Kỹ thuật gộp (microaggregation) User ry e s u lt u Q s e R Averaged Original Microaggregated Data Data 107
  108. 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
  109. 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
  110. 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
  111. 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 135 80 50 265 F 120 360 100 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
  112. 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 90%).  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). 112
  113. 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 135 80 _ 265 F 120 360 _ 580 Sum 255 440 150 845 113
  114. 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 135 _ _ 265 F _ _ 580 360 Sum 255 440 150 845 114
  115. 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
  116. 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
  117. Data Perturbation User 1 Noise Added ry e s u lt u Q s e R Original Perturbed Database Database R e su Q lts u e ry User 2 117
  118. 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
  119. 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
  120.  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. 2 E(ei) = 0, D(ei) =   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à: 2 2  P(|q’(C) – q(C)| )>= | |X(C)| | )<=  /(|X(C)| )  Như vậy |X(C)| càng lớn thì xác suất lỗi càng nhỏ 120
  121. 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
  122. 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 ’ X(C): x ij = f(xij). ’  Giá trị  = x ij – xij là ngẫu nhiên. 122
  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ê 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). n x ' ’  S’ = ij với xij = f(xij) = xij + z1 ( xij - xC ) + z2 i 1 j  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
  124. 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 n ’  m =  z3 j 3 2 Với E(z3) = 1 và Var(z3) = a 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). 2  E(m’) = m và Var(m’) = a 1 124
  125. 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
  126. Kỹ thuật gây nhiễu đầu ra User 1 ery Qu ts sul Re Noise Added to Results Original Database Re su lts Q ue ry User 2 126
  127. 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
  128. 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
  129. 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. Q nêu d 0  r(Q) = ' Q d nêu d b ' Q b d nêu d b 129
  130. 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. Q nêu d 0  r(Q) = Q d voi xácsuât1 p Q b d voi xác suât p  Xác suất p = d/b 130
  131. 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
  132. 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
  133. 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
  134. So sánh các kỹ thuật chống suy diễn  Các tiêu chuẩn so sánh:  Security: đánh giá mức độ bảo vệ của kỹ thuật (chống được những tấn công nào), chống được suy diễn, có lộ chính xác, lộ từng phần không.  Mức đầy đủ của thông tin: kết quả trả về có chính xác không, có nhất quán không và có bị mất mát thông tin hay không.  Cost: chi phí thực hiện, chi phí xử lý trên một câu truy vấn (thời gian CPU), chi phí đào tạo ngươì dùng. 134
  135. So sánh các kỹ thuật chống suy diễn Method Security Richness of Costs Information Query-set Restriction Low Low1 Low Microaggregation Moderate Moderate Moderate Data Perturbation High High-Moderate Low Output Perturbation Moderate Moderate-low Low Auditing Moderate-Low Moderate High Sampling Moderate Moderate-Low Moderate 135