Báo cáo Đánh giá các phương pháp bảo vệ tính riêng tư trong mạng xã hội (Phần 1)

Nội dung text: Báo cáo Đánh giá các phương pháp bảo vệ tính riêng tư trong mạng xã hội (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG ĐÁNH GIÁ CÁC PHƯƠNG PHÁP BẢO VỆ TÍNH RIÊNG TƯ TRONG MẠNG XÃ HỘI S K C 0 0 3 9 5 9 MÃ SỐ: T2014-43 SKC0 0 5 5 2 7 Tp. Hồ Chí Minh, 03/2015
2. TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƢỜNG ĐÁNH GIÁ CÁC PHƢƠNG PHÁP BẢO VỆ TÍNH RIÊNG TƢ TRONG MẠNG XÃ HỘI Mã số: T2014 – 43 Chủ nhiệm đề tài: Lê Thị Minh Châu Thành viên đề tài: Lê Thị Minh Châu TP. HCM, 03/2015
3. DANH SÁCH THÀNH VIÊN THAM GIA NGHIÊN CỨU ĐỀ TÀI 1. Lê Thị Minh Châu ĐƠN VỊ PHỐI HỢP CHÍNH 2. Khoa Công Nghệ Thông Tin – Đại học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 2
4. MỤC LỤC MỤC LỤC 3 DANH MỤC BẢNG 5 DANH MỤC H NH 6 THÔNG TIN KẾT QUẢ NGHIÊN CỨU 7 INFORMATION ON RESEARCH RESULTS 8 CHƢƠNG 1: MỞ ĐẦU 9 1.1 Tính cấp thiết của đề tài 9 1.2 Tổng quan tình hình nghiên cứu thuộc lĩnh vực đề tài ở trong và ngoài nước 9 1.2.1 Ngoài nước 9 1.2.2 Trong nước 10 1.3 Mục tiêu đề tài 10 1.4 Cách tiếp cận, phương pháp nghiên cứu 10 1.4.1 Cách tiếp cận 10 1.4.2 Phương pháp nghiên cứu 11 1.5 Đối tượng và phạm vi nghiên cứu 11 1.5.1 Đối tượng nghiên cứu 11 1.5.2 Phạm vi nghiên cứu 11 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT 12 2.1 Giới thiệu 12 2.2 Cấu trúc đồ thị 13 2.2.1 Các định nghĩa cơ bản 13 2.3 Bảo vệ tính riêng tư cho dữ liệu bằng phương pháp nặc danh dựa trên nhóm 14 2.4 Bảo vệ tính riêng tư trong mạng xã hội, liên kết 21 2.4.1 Các vi phạm tính riêng tư trong mạng xã hội, liên kết [1, 38] 21 CHƢƠNG 3: CÁC CÔNG TR NH LIÊN QUAN 25 3.1 Bảo vệ tính riêng tư trong các mạng xã hội (Social Network) 25 3.1.1 Nặc danh hóa cấu trúc mạng 25 3.1.2 Nặc danh hóa thuộc tính của người sử dụng và cấu trúc mạng 26 3.2 Bảo vệ tính riêng tư trong mạng liên kết (Affiliation Network) 26 CHƢƠNG 4: TỔNG KẾT 28 3
5. 4.1 Những công việc đã làm 28 4.2 Đóng góp của đề tài 28 4.3 Hướng phát triển 28 TÀI LIỆU THAM KHẢO 31 4
6. DANH MỤC BẢNG Bảng 2.1: Ví dụ đơn giản về bảng riêng tư [2] 16 Bảng 2.2: Tổng quát hóa bảng 2.1 dựa trên thuộc tính Sex 17 Bảng 2.3: Tổng quát hóa bảng 2.2 dựa trên thuộc tính Marital status 17 Bảng 2.4: Tổng quát hóa bảng 2.3 dựa trên thuộc tính Marital status 17 Bảng 2.5: Tổng quát hóa bảng 2.4 dựa trên thuộc tính Hour 18 Bảng 2.6: Tổng quát hóa bảng 2.5 dựa trên thuộc tính Hour 18 Bảng 2.7: Thông tin bệnh nhân [2] 18 Bảng 2.8: Bảng 2.7 đã được nặc danh (4-anonymity) 19 Bảng 2.9: Thông tin tiền lương – bệnh 20 Bảng 2.10: Thông tin tiền lương – bệnh đã được đa dạng (3-diversity) 20 Bảng 4.1: thông tin bệnh nhân 29 Bảng 4.2: thông tin bệnh nhân đã được nặc danh (4 – anonymity) 29 5
7. DANH MỤC H NH Hình 2.1: Thuộc tính Marital_status 16 Hình 2.2: Thuộc tính Sex 16 Hình 2.3: Thuộc tính Hour 17 Hình 3.1: Ví dụ về mạng liên kết [3, 6.3.2, trang 167] 26 6
8. TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM THÀNH PHỐ HỒ CHÍ MINH Độc lập - Tự do - Hạnh phúc KHOA CNTT Tp. HCM, ngày 04 tháng 03 năm 2015 THÔNG TIN KẾT QUẢ NGHIÊN CỨU 1. Thông tin chung: - Tên đề tài: Đánh giá các phương pháp bảo vệ tính riêng tư trong mạng xã hội - Mã số: T2014 – 43 - Chủ nhiệm: Lê Thị Minh Châu - Cơ quan chủ trì: Đại học Sư phạm Kỹ thuật Thành Phố Hồ Chí Minh - Thời gian thực hiện: Từ tháng 01 năm 2014 đến tháng 12 năm 2014 2. Mục tiêu: - Tìm hiểu khái niệm, cấu trúc mạng xã hội, mạng liên kết. - Tìm hiểu các vấn đề về tính riêng tư và các phương pháp bảo vệ tính riêng tư trong mạng xã hội. 3. Tính mới và sáng tạo: - Phân tích, đánh giá các phương pháp bảo vệ tính riêng tư trong mạng xã hội. 4. Kết quả nghiên cứu: - Phân tích, đánh giá các phương pháp bảo vệ tính riêng tư trong mạng xã hội. 5. Sản phẩm: - 01 quyển báo cáo các kết quả nghiên cứu được. - 01 bài báo đăng trên Web Khoa. 6. Hiệu quả, phƣơng thức chuyển giao kết quả nghiên cứu và khả năng áp dụng: - Hiệu quả: kết quả nghiên cứu đề tài góp phần giải quyết các bài toán về bảo vệ tính riêng tư trong mạng xã hội và hỗ trợ nhu cầu nghiên cứu của Sinh Viên. - Phương thức chuyển giao: quyển báo cáo (hard – copy). - Địa chỉ ứng dụng: kết quả nghiên cứu được sử dụng để giảng dạy hoặc phục vụ nhu cầu nghiên cứu khoa học cho Sinh Viên Khoa Công Nghệ Thông Tin. Trƣởng Đơn vị Chủ nhiệm đề tài 7
9. INFORMATION ON RESEARCH RESULTS 1. General information: - Project title: Social Network Privacy Methods Evaluation - Code number: T2014 – 43 - Coordinator: Lê Thị Minh Châu - Implementing institution: University of Technical Eduaction Ho Chi Minh City - Duration: from 01/2014 to 12/2014 2. Objective(s): - Study concepts, social network and affiliate network structure. - Study privacy problems and social networks privacy methods. 3. Creativeness and innovativeness: - Analyze, evaluate social network privacy methods. 4. Research results: - Analyze, evaluate social network privacy methods. 5. Products: - 01 study results report. - 01 paper published in the Website of the Faculty. 6. Effects, transfer alternatives of reserach results and applicability: - Efficiency: The research results contribute to solve problems of social network privacy and support research needs of students. - Transfer alternatives: software (CD) and book of report (hard – copy). - Applicability: research result is used to teach or serve the needs of scientific research for students of Information Technology Faculty. 8
10. CHƢƠNG 1: MỞ ĐẦU 1.1 Tính cấp thiết của đề tài Hiện nay, mạng xã hội phát triển ngày càng mạnh mẽ, phổ biến và là thành phần không thể thiếu trong cuộc sống hàng ngày của chúng ta. Mạng xã hội Facebook có trên 500 triệu người dùng, ZingMe trên 12 triệu người dùng, MySpace trên 266 triệu người dùng, LinkedIn có trên 80 triệu người dùng. Người tham gia mạng xã hội ngoài việc tìm kiếm, thực hiện liên kết bạn bè, trao đổi thông tin còn có thể thực hiện các giao dịch mua bán trực tuyến, chơi điện tử, Điều này làm phát sinh các bài toán suy diễn về các đặc tính và môi trường xã hội của người dùng. Các thông tin suy diễn được sử dụng với nhiều mục đích, từ việc tạo ra các chiến dịch tiếp thị hiệu quả hơn đến thiết kế các dịch vụ cá nhân tốt hơn. Các mô hình thống kê tiên đoán cho phép tìm ra các thông tin ẩn một cách tự động trong các mạng xã hội nhưng cũng đem đến nhiều vấn đề về tính riêng tư của người dùng. Do đó vấn đề bảo vệ tính riêng tư trên mạng xã hội rất quan trọng, cấp thiết, thu hút nhiều sự quan tâm hiện nay. 1.2 Tổng quan tình hình nghiên cứu thuộc lĩnh vực đề tài ở trong và ngoài nƣớc 1.2.1 Ngoài nƣớc Phần lớn các nghiên cứu trước đây về việc tiên đoán, sự tiến hóa và tính riêng tư trong mạng xã hội trực tuyến đều tập trung trên các mạng đơn mode (single – mode network) được hình thành xung quanh các liên kết giữa người sử dụng chẳng hạn như kết nối bạn bè và liên lạc qua email. Tuy nhiên, các mạng đơn mode thường tồn tại với các mạng liên kết hai mode (two – mode network) trong đó người dùng có thể liên kết với các thực thể khác như các nhóm xã hội, nội dung và các sự kiện trực tuyến. Gần đây đã có nghiên cứu về sự tương tác giữa hai loại mạng và cho thấy phân tích các tương tác bậc cao có thể tiết lộ các ràng buộc, các thông tin ẩn mà khó có thể rút ra khi phân tích các tương tác từng cặp riêng lẻ. Việc tiết lộ các 9
11. thông tin ẩn có thể dẫn đến các vấn đề về tính riêng tư. Kẻ tấn công tìm cách lấy được thông tin cá nhân của người dùng từ dữ liệu mạng xã hội có sẵn công khai. Ngược lại, nhà cung cấp dữ liệu cần phải cung cấp các cơ chế bảo mật mạng xã hội để bảo vệ các thông tin cá nhân người dùng. Các nghiên cứu đã chỉ ra các lỗ hổng bảo mật trên mạng xã hội như tiết lộ danh tính (identity disclosure), tiết lộ thuộc tính (attribute disclosure), tiết lộ liên kết xã hội (social link disclosure) và tiết lộ liên kết trên mạng liên kết (affiliation link disclosure) cũng như các phương pháp bảo vệ tính riêng tư cho dữ liệu mạng xã hội như nặc danh hóa dữ liệu với các kỹ thuật: k – nặc danh (k – anonymity), ℓ - đa dạng (ℓ - diversity) và t – gần nhau (t – closeness), 1.2.2 Trong nƣớc Thời gian gần đây đã có một số nghiên cứu về mạng xã hội và các đối tượng như người dùng, sự kiện, thông tin, trên mạng xã hội nhưng chưa có nghiên cứu chính thức về bảo vệ tính riêng tư của người dùng trên mạng xã hội. 1.3 Mục tiêu đề tài - Tìm hiểu khái niệm mạng xã hội, mạng liên kết. - Tìm hiểu cấu trúc mạng xã hội, cấu trúc đồ thị tương tác, cấu trúc mạng liên kết và hành vi người dùng. - Tìm hiểu các vấn đề về tính riêng tư và các phương pháp bảo vệ tính riêng tư trong mạng xã hội, liên kết. - Phân tích, đánh giá các kết quả nghiên cứu được. 1.4 Cách tiếp cận, phƣơng pháp nghiên cứu 1.4.1 Cách tiếp cận - Tìm hiểu khái niệm mạng xã hội, mạng liên kết. - Tìm hiểu cấu trúc mạng xã hội, cấu trúc đồ thị tương tác, cấu trúc mạng liên kết và hành vi người dùng. - Tìm hiểu các vấn đề về tính riêng tư và các phương pháp bảo vệ tính riêng tư trong mạng xã hội, liên kết. 10
12. - Phân tích, đánh giá các kết quả nghiên cứu được. 1.4.2 Phƣơng pháp nghiên cứu - Tìm hiểu các phương pháp bảo vệ tính riêng tư trong mạng xã hội và đánh giá các phương pháp. 1.5 Đối tƣợng và phạm vi nghiên cứu 1.5.1 Đối tƣợng nghiên cứu - Cấu trúc mạng xã hội, hành vi người dùng, các vấn đề về tính riêng tư và các phương pháp bảo vệ tính riêng tư trong mạng xã hội. 1.5.2 Phạm vi nghiên cứu - Các nghiên cứu được tiến hành trên các tập dữ liệu mẫu từ Facebook, Flickr, Zingme, 11
13. CHƢƠNG 2: CƠ SỞ LÝ THUYẾT 2.1 Giới thiệu Không giống như các trang web điện tử thông thường được tổ chức xoay quanh nội dung, các mạng xã hội được tổ chức với trọng tâm là con người. Người dùng tham gia vào mạng, công bố thông tin về bản thân hoặc bất cứ thông tin nào đang sở hữu, tạo liên kết với những người dùng khác mà họ quen biết. Kết quả là mạng xã hội cung cấp nền tảng cơ bản để giữ gìn và phát triển các mối quan hệ xã hội, tìm kiếm người dùng có cùng điểm tương đồng, định vị nội dung và tìm hiểu những tri thức do người khác đóng góp hoặc sở hữu. Trong vài năm qua, với sự xuất hiện của nhiều trang web mạng xã hội và truyền thông, sự quan tâm và hiểu biết về các hiện tượng xã hội đã tăng lên từ các liên kết và tương tác của người dùng. Các website này có hàng ngàn, thậm chí hàng triệu người dùng. Các người dùng này tình nguyện gửi các thông tin cá nhân để được hưởng lợi từ các dịch vụ được cung cấp chẳng hạn như duy trì tình bạn, chia sẻ hình ảnh, âm nhạc, tài liệu, Các thông tin cá nhân này có thể được sử dụng để nghiên cứu các sở thích cá nhân của người sử dụng, mô hình truyền thông và luồng thông tin. Phân tích mạng xã hội (Social Network Analysis – SNA) là một lĩnh vực nghiên cứu xuất hiện từ cuối thế kỷ 19. Trong đó, các mạng kết nối của các cá nhân sẽ được phân tích để đánh giá và định lượng vai trò của một cá nhân trong một nhóm hay cộng đồng. Ngày nay, SNA bao gồm việc thu tập một số lượng lớn các dữ liệu từ nhiều nguồn khác nhau, phân tích dữ liệu để xác định các mối liên kết và khai phá các mối liên kết đó để tìm ra các thông tin mới. Trong lĩnh vực khai phá dữ liệu, học máy người ta thường sử dụng các phương pháp thống kê để mô hình hóa và nghiên cứu các mẫu thức trong dữ liệu nói chung và dữ liệu mạng nói riêng. Theo truyền thống, học máy nghiên cứu các dữ liệu độc lập và được phân bố tương tự nhau. Nhưng ngày nay, sự phát triển của 12
14. các mạng xã hội trực tuyến đã dẫn tới việc phát triển nhiều giải thuật có thể xử lý các dữ liệu phụ thuộc lẫn nhau. Khai phá liên kết là một phần của khai phá dữ liệu nghiên cứu các mô hình tiên đoán hoặc mô tả dựa trên các liên kết có sẵn của dữ liệu. Hầu hết các khai phá liên kết cho các mạng xã hội trực tuyến tập trung vào việc nghiên cứu các mạng liên kết xung quanh các actor (actor – actor link) chẳng hạn như quan hệ bạn bè. Tuy nhiên, dữ liệu truyền thông xã hội thường rất phong phú. Ngoài các liên kết giữa các người dùng còn có các liên kết giữa người dùng với các đối tượng khác chẳng hạn như các nhóm, sự kiện, các trang cộng đồng và nội dung ưa thích. Đây được gọi là các affiliation link. Nghiên cứu các đặc điểm của người sử dụng (tường minh/ẩn) sẽ giúp phát triển các thuật toán tiên đoán tốt hơn. 2.2 Cấu trúc đồ thị 2.2.1 Các định nghĩa cơ bản Một mạng có thể xem như là một đồ thị G = (V, E). Trong ngữ cảnh mạng xã hội, mỗi đỉnh đại diện cho một người dùng và cạnh biểu diễn mối quan hệ giữa các người dùng. Liên kết trong đồ thị có thể là cạnh có hướng, nghĩa là mỗi cạnh có một đỉnh là nguồn và kết thúc tại một đỉnh khác. Hoặc liên kết có thể là vô hướng, nghĩa là cạnh nối giữa hai đỉnh không phân biệt nguồn và đích. Đồ thị xã hội (Social Graph) có cạnh biểu diễn quan hệ bạn bè giữa hai người dùng khác nhau. Đồ thị tương tác (Interaction Graph) có cạnh biểu diễn hai người dùng có quan hệ bạn bè và có thực hiện tương tác với nhau. Hành vi tương tác ở đây được hiểu là người dùng thực hiện ghi lên tường (Wall) của người bạn. Nếu người dùng A ghi lên tường của người bạn B thì ghi nhận đó là tương tác và hình thành cạnh vô hướng nối giữa A và B. Bậc của một đỉnh (bậc người dùng) trong đồ thị là tổng số cạnh có liên kết với đỉnh đó, trong đồ thị xã hội là tổng số bạn bè của người dùng (social degree) hay trong đồ thị tương tác là tổng số bạn bè mà người dùng tương tác (interaction degree), ký hiệu di. 13
15. Đối với đồ thị có hướng, bậc của đỉnh i được phân biệt thành: - Indegree: tổng số cạnh kết thúc tại đỉnh i, ký hiệu din - Outdegree: tổng số cạnh bắt đầu từ đỉnh i, ký hiệu dout Mạng liên kết được biểu diễn là một đồ thị phân đôi với hai loại node V và H và các liên kết giữa chúng Eh. 2.3 Bảo vệ tính riêng tƣ cho dữ liệu bằng phƣơng pháp nặc danh dựa trên nhóm Các thuộc tính được chia thành các loại: - Key identifier: là những thuộc tính xác định cụ thể cá thể như tên, số bảo hiểm xã hội. - Quasi-identifier (QI): các thuộc tính khi kết hợp với nhau sẽ xác định cụ thể cá thể như tuổi tác, zip-code, giới tính. - Sensitive: là những thuộc tính nhạy cảm như: bệnh, tiền lương, tiểu sử phạm tội. Trong nhiều ứng dụng, để bảo mật dữ liệu các thuộc tính xác định cụ thể cá thể (identifier) như tên, số bảo hiểm xã hội thường được loại bỏ. Tuy nhiên, các thuộc tính thuộc loại quasi-identifier (pseudo-identifier) có thể được dùng để xác định chính xác các cá thể. Ví dụ các thuộc tính như tuổi, mã vùng (zip-code), sex có sẵn trong một tập dữ liệu có thể được kết hợp để xác định các cá thể tương ứng hoặc thu hẹp phạm vi tìm kiếm các cá thể. Do đó việc loại bỏ trên không đủ để bảo vệ dữ liệu trước nguy cơ phơi bày thông tin. Các phơi bày được chia làm hai loại [10]: - Phơi bày định danh (identity disclosure): là trường hợp khi một cá thể nào đó bị liên kết đến một dòng dữ liệu nào đó trong bảng dữ liệu được đưa đi khai thác. - Phơi bày thuộc tính (attribute disclosure): là những thông tin mới của một cá thể nào đó bị bộc lộ. 14
16. a. K-anonymity (k-nặc danh) Là kỹ thuật biến đổi dữ liệu gốc sao cho dữ liệu được đưa đi khai thác phải thỏa mãn điều kiện: bất kỳ sự kết hợp nào của các thuộc tính riêng tư của một cá thể đều có ít nhất k cá thể khác có cùng giá trị cho sự kết hợp các thuộc tính riêng tư tương ứng trong dữ liệu đưa ra [6, chương 2, trang 21]. Nhóm ít nhất k dòng này còn được gọi là lớp tương đương (equivalence class). Có 2 kỹ thuật được dùng để biến đổi một bảng đạt được k-anonymity: Tổng quát hóa (Generalization): thay thế các giá trị của một thuộc tính bằng một giá trị tổng quát hơn. Việc tổng quát hóa dựa trên một phân cấp tổng quát hóa miền trị và một phân cấp tổng quát hóa giá trị tương ứng. Phân cấp tổng quát hóa miền trị có thứ tự toàn phần và phân cấp tổng quát hóa giá trị tương ứng là một cây, trong đó mối quan hệ cha/con diễn tả mối quan hệ tổng quát hóa/chuyên biệt hóa. Kỹ thuật này được chia làm 2 loại: . Mức cell: thay thế giá trị một vài cell nào đó bằng một giá trị tổng quát hơn. Mức cell có thuận lợi là tránh được sự thay thế tất cả các giá trị của một thuộc tính nhưng có một bất lợi là tạo ra sự không đồng nhất các giá trị cho một thuộc tính nào đó. . Mức thuộc tính: thay thế giá trị của cột thuộc tính bằng giá trị tổng quát hơn. Mức thuộc tính thì có được sự đồng nhất tuy nhiên lại làm thay đổi nhiều trên dữ liệu gốc, mất mát nhiều thông tin. Kỹ thuật loại bỏ (Suppression): loại bỏ các thông tin nhạy cảm. Cách thức loại bỏ có thể được áp dụng ở các mức cell đơn (cell này sẽ nhận giá trị null hoặc unknown), toàn bộ một dòng hoặc toàn bộ một cột, cho phép giảm mức độ tổng quát hóa mà được dùng để đạt được k-anonymity. Rõ ràng các phương pháp như vậy giảm nguy cơ xác định cá thể nhưng cũng làm giảm độ chính xác của các ứng dụng khai phá trên tập dữ liệu đã bị biến đổi. 15
17. Một ví dụ về biến đổi dữ liệu để đạt k-anonymity Marital status Sex Hours #tuples (Hyp. values) divorced M 35 2 (0Y,2N) divorced M 40 17 (16Y,1N) divorced F 35 2 (0Y,2N) married M 35 10 (8Y, 2N) married F 50 9 (2Y,7N) single M 40 26 (6Y, 20N) Bảng 2.1: Ví dụ đơn giản về bảng riêng tư [2] Giả sử Marital Status, Sex và Hour là các thuộc tính quasi-identifier. Bảng 2.2 gộp chung các hàng có giá trị giống nhau ở tất cả các thuộc tính này. Cột #tuples cho biết số các hàng giống nhau. Cột Hyp.values cho biết số người bị chứng cao huyết áp và số người không bị. Cụ thể, hàng thứ nhất cho biết: có 2 người đã ly hôn, giới tính là nam, số giờ làm việc trong tuần là 35 thì không có người nào bị bệnh cao huyết áp. Mức độ nặc danh của bảng là k = 2. Ta có phân cấp tổng quát hóa cho các thuộc tính như sau [6, chương 5, trang 108]: Hình 2.1: Thuộc tính Marital_status Hình 2.2: Thuộc tính Sex 16
18. Hình 2.3: Thuộc tính Hour Từ sơ đồ phân cấp này, giả sử ta tổng quát hóa mức thuộc tính cho thuộc tính Sex (từ S0 S1) ta được bảng có mức nặc danh k = 4. Marital status Sex Hours #tuples (Hyp. values) divorced Any_sex 35 4 (0Y,4N) divorced Any_sex 40 17 (16Y,1N) married Any_sex 35 10 (8Y, 2N) married Any_sex 50 9 (2Y,7N) Single Any_sex 40 26 (6Y, 20N) Bảng 2.2: Tổng quát hóa bảng 2.1 dựa trên thuộc tính Sex Tiếp tục áp dụng tổng quát hóa mức thuộc tính lên thuộc tính Marital status (Từ M0 M1), ta được bảng với k = 9 như sau: Marital status Sex Hours #tuples (Hyp. values) Been_married Any_sex 35 14 (8Y,6N) Been_married Any_sex 40 17 (16Y,1N) Been_married Any_sex 50 9 (2Y,7N) Never_married Any_sex 40 26 (6Y, 20N) Bảng 2.3: Tổng quát hóa bảng 2.2 dựa trên thuộc tính Marital status Tiếp tục áp dụng tổng quát hóa mức thuộc tính lên thuộc tính Marital status (Từ M1 M2), ta được bảng với k = 9, mức độ nặc danh không tăng lên. Marital status Sex Hours #tuples (Hyp. values) Any_marital_status Any_sex 35 14 (8Y,6N) Any_marital_status Any_sex 40 43 (22Y,21N) Any_marital_status Any_sex 50 9 (2Y,7N) Bảng 2.4: Tổng quát hóa bảng 2.3 dựa trên thuộc tính Marital status 17
19. Tiếp tục áp dụng tổng quát hóa mức thuộc tính lên thuộc tính Hours (Từ H0 H1), ta được bảng với k = 14 Marital status Sex Hours #tuples (Hyp. values) Any_marital_status Any_sex [1-40) 14 (8Y,6N) Any_marital_status Any_sex [40-100) 52 (24Y,28N) Bảng 2.5: Tổng quát hóa bảng 2.4 dựa trên thuộc tính Hour Tiếp tục áp dụng tổng quát hóa mức thuộc tính lên thuộc tính Hours (Từ H1 H2), ta được bảng với k = 66. Marital status Sex Hours #tuples (Hyp. values) Any_marital_status Any_sex [1-100) 66 (32Y,34N) Bảng 2.6: Tổng quát hóa bảng 2.5 dựa trên thuộc tính Hour b. ℓ – diversity (ℓ-đa dạng) K-anonymity chỉ giúp chống tái xác định các cá thể chứ không đảm bảo che giấu các giá trị nhạy cảm. Dựa vào đó, kẻ tấn công có thể suy luận chính xác hoặc gần đúng các giá trị nhạy cảm của các cá thể. Bảng 2.7: Thông tin bệnh nhân [2] 18
20. Bảng 2.8: Bảng 2.7 đã được nặc danh (4-anonymity) c. T – closeness (t-gần nhau) [10] Mô hình t-closeness là một bước nâng cao của mô hình ℓ-diversity. Một đặc điểm của mô hình ℓ-diversity là nó xử lý tất cả các giá trị của một thuộc tính cho trước theo cách tương tự nhau không phân biệt sự phân phối của các giá trị thuộc tính trong tập dữ liệu. Tuy nhiên trong thực tế, tập dữ liệu thường có sự chênh lệch rất lớn về sự xuất hiện của các giá trị trong thuộc tính. Điều này làm cho việc tạo ra các biểu diễn ℓ-diversity khả thi trở nên khó hơn. Ví dụ: Giả sử dữ liệu nguồn chỉ có một thuộc tính nhạy cảm là kết quả kiểm tra các cá thể có bị nhiễm một virus nào đó hay không. Thuộc tính này có 2 giá trị là positive và negative. Dữ liệu có 100000 dòng, trong đó 99% là negative và 1% là positive. Rõ ràng giá trị negative sẽ chiếm ưu thế so với positive. Do đó, để tạo ra một bảng mà thỏa mãn ℓ-diversity với ℓ = 2 cho thuộc tính nhạy cảm này là không cần thiết. Hơn nữa, không phải tất cả các giá trị của thuộc tính đều nhạy cảm như nhau. Ví dụ một thuộc tính mô tả một chứng bệnh khi giá trị là dương (positive) có thể nhạy cảm hơn là khi giá trị là âm (negative). Một hạn chế khác của ℓ-diversity là có thể không đủ mạnh để ngăn chặn phơi bày thuộc tính trong một số trường hợp: 19
21. Bảng 2.9: Thông tin tiền lương – bệnh Bảng 2.10: Thông tin tiền lương – bệnh đã được đa dạng (3-diversity) Giả sử kẻ tấn công muốn tìm thông tin của một bệnh nhân mà thuộc các dòng 1, 2, 3 của bảng thì họ có thể suy ra các thông tin nhạy cảm đó là: bệnh nhân đó có lương rất thấp và mắc bệnh liên quan đến dạ dày. Đây là kiểu tấn công tương tự (Similarity). Định nhĩa t-closeness [10] Một lớp tương đương được gọi là t-closeness nếu độ khác biệt giữa phân phối của một thuộc tính nhạy cảm trong lớp tương đương này với phân phối của cùng thuộc tính nhạy cảm trong toàn bộ bảng không vượt quá một ngưỡng t nào đó cho trước. Một bảng được gọi là thỏa mãn t-closeness nếu mọi lớp tương đương của nó thỏa mãn t-closeness. Độ khác biệt của 2 phân phối có thể được tính như sau: 20
22. S K L 0 0 2 1 5 4