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

CHƯƠNG 5 1 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 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.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 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 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 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 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 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 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 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 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 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 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 Mô hình làm lộ SDB 15 Ví dụ về làm lộ một SDB Ví dụ 1 (lộ chính xác) 16 Ví dụ 2 (lộ xấp xỉ) 17 Ví dụ 2 18 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 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 4.2 Các khái niệm cơ bản và các giả định 21 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 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 Lê sỹ Hoàng 37 HD Đỏ Toyota 6.25 1 0 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 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 tính Địa chỉ Phụ cấp Nghiện ma túy Lớp 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 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 Tổng phụ cấp theo giới tính và theo lớp Toán1 Toán2 Tin1 Tin2 M 500 0 0 100 F 100 200 300 0 Tổng cộng 600 200 300 100 25 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 Các khái niệm cơ bản và các giả định  SDB vĩ mô về Công nhân (count) Năm sinh Giới tính 1941-1951 M 1952-1962 >1962 F M F F M Mã phòng Phong1 Phong2 Phong3 0 1 8 5 3 0 10 0 2 10 0 12 20 15 20 12 1 10 BSD Table 27  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). Các khái niệm cơ bản và các giả định 28 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 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 30 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 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  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). Giới thiệu CSDL suy diễn (Deductive Database) 33 4.1 Giới thiệu 34 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 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 36 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 37 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ấu trúc CSDL suy diễn 38 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 39 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 40 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 41 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 42 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 43 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 44 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 45 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 46 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 47 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 48 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 49 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 50 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. Các thành phần của CSDL suy diễn 51 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 52 Ư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 53 Ư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) Các thành phần của CSDL suy diễn 54 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 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 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 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 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