Bài giảng An toàn thông tin trong cơ sở dữ liệu - Chương 4: An toàn CSDL thống kê

chế nhiều câu truy vấn) 4.4.2 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 4.4.2.2 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 4.4.2.2 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 = Cm0 + Cm1 +Cm2 +…+ Cmm-1 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) ... q(A1 = a1 A2= a2 ...   Am =am) 4.4.2.2 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. 4.4.2.2 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) 4.4.2.2 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 4.4.2.2 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) 4.4.2 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 4.4.2 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 4.4.2 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 4.4.2.5 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. 4.4.2.5 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á. Microaggregation Microaggregation 4.4.2.5 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 4.3.2.5 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). 4.3.2.5 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. 4.3.2.5 Kỹ thuật Giấu ô (Cell suppression) Ví dụ: Giả sử n = 2 và k = 90% Tổng lương của nam,nữ công nhân trong các phòng 4.3.2.5 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). 4.3.2.5 Kỹ thuật Giấu ô (Cell suppression) Kết quả: 4.3.2.5 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! 4.3.2.5 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. 4.4.2 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 4.4.2 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 4.4.3 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 Data Perturbation 4.4.3.1 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 4.4.3.1 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 4.4.3.1 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)| | ) tốn công, giảm hiệu năng hệ thống. Kết quả đưa ra không chính xác. 4.4.3.2 Kỹ thuật gây nhiễu đầu ra 4.4.3.2 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) 4.4.3.2 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) 4.4.3.2 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) = 4.4.3.2 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 4.4.3.2 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. 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 So sánh các kỹ thuật chống suy diễn 4.4.4 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. 4.4.4 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. 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 So sánh các kỹ thuật chống suy diễn 4.5 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. 4.5 So sánh các kỹ thuật chống suy diễn