Tài liệu Ứng dụng đảm bảo tính riêng tư cho dữ liệu đồ thị trong cơ sở dữ liệu neo4j

ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA -------------------- TRẦN THẾ HUY ỨNG DỤNG ĐẢM BẢO TÍNH RIÊNG TƯ CHO DỮ LIỆU ĐỒ THỊ TRONG CƠ SỞ DỮ LIỆU NEO4J Chuyên ngành : Khoa Học Máy Tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 08 năm 2021 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI: TRƯỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG -HCM Cán bộ hướng dẫn khoa học : PGS. TS Đặng Trần Khánh........................ Cán bộ chấm nhận xét 1 : TS. Đặng Trần Trí ............................................ Cán bộ chấm nhận xét 2 : PGS.TS. Nguyễn Tuấn Đăng ........................... Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày . . 06. . . tháng . .08 . . năm . . 2021. .(trực tuyến). Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. TS. Lê Lam Sơn…………………….. - Chủ tịch 2. TS. Phan Trọng Nhân .......................... - Thư ký 3. TS. Đặng Trần Trí ................................ - Phản biện 1 4. PGS.TS. Nguyễn Tuấn Đăng ............... - Phản biện 2 5. PGS.TS Đặng Trần Khánh ................... - Uỷ viên Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH 1 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc ------------- ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ------------- NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: TRẦN THẾ HUY MSHV: 1770021 Ngày, tháng, năm sinh: 24-01-1994 Nơi sinh: AN GIANG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01.01 I. TÊN ĐỀ TÀI: ỨNG DỤNG ĐẢM BẢO TÍNH RIÊNG TƯ CHO DỮ LIỆU ĐỒ THỊ TRONG CƠ SỞ DỮ LIỆU NEO4J. II. NHIỆM VỤ VÀ NỘI DUNG: Đề xuất các giải pháp và thuật toán để xây dựng và hiện thực ứng dụng đảm bảo tính riêng tư cho dữ liệu đồ thị trong cơ sở dữ liệu Neo4j. III. NGÀY GIAO NHIỆM VỤ : 22/02/2021 IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 13/06/2021 V. CÁN BỘ HƯỚNG DẪN: PGS. TS ĐẶNG TRẦN KHÁNH ……………………………………. CÁN BỘ HƯỚNG DẪN (Họ tên và chữ ký) Tp. HCM, ngày . . . . tháng .. . . năm 2021 CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) TRƯỞNG KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH (Họ tên và chữ ký) i LỜI CÁM ƠN Để hoàn thành luận văn thạc sỹ này tôi trân trọng gửi lời cám ơn đến PGS. TS Đặng Trần Khánh – giảng viên hướng dẫn khoa học cũng như người thầy đáng kính đã hỗ trợ và giảng dạy tôi, cũng như phản biện cho tôi trong suốt thời gian làm đề cương cũng như hoàn tất luận văn này. Ngoài ra, tôi cũng muốn gửi lời cảm ơn đến các thầy cô khoa Khoa học và kỹ thuật máy tính – Đại học Bách Khoa thành phố Hồ Chí Minh đã tạo mọi điều kiện vật chất cũng như tri thức để bổ trợ cho tôi, để tôi có thể hoàn thành luận văn như ý muốn. Cuối cùng, tôi cũng gửi lời cảm ơn đến bạn bè, gia đình, cha mẹ cũng như vợ tôi đã cổ vũ, động viên tôi, để tôi có thể có môi trường học tập cũng như nghiên cứu trong thời kỳ làm luận văn. TRẦN THẾ HUY ii TÓM TẮT LUẬN VĂN THẠC SỸ Ngày nay, dữ liệu có cấu trúc đồ thị ngày càng phổ biến như là đồ thị mạng xã hội, đồ thị trang web hay đồ thị giao tiếp trực tiếp giữa người với người. Dữ liệu đồ thị mang đến nhiều thông tin hữu ích về con người cũng như những quan hệ giữa con người với con người. Thông qua những đồ thị này, các nhà nghiên cứu có thể dùng phân tích cho các nghiên cứu cụ thể dựa trên các thông tin cá nhân cũng như các mối quan hệ của những người có trong các mạng đồ thị. Tuy nhiên, việc thu thập, truyền tải và phân tích các thông tin này thường có thể dẫn đến tiết lộ thông tin cá nhân. Thậm chí, sau khi phân tích, các thông tin cá nhân vẫn có thể còn tồn tại trên tập dữ liệu cá nhân đã phân tích. Cùng với đó, các chính phủ trên thế giới đã có nhiều bộ luật để đảm bảo quyền riêng tư như HIPPA, GDPR hay bộ luật An ninh mạng của Việt Nam 2018. Việc phân tích dữ liệu trên mạng đồ thị là cần thiết, tuy nhiên vẫn phải đảm bảo quyền riêng tư cá nhân có trong đồ thị. Vì vậy cần thiết có những công cụ hỗ trợ các nhà nghiên cứu có thể đảm bảo quyền riêng tư trong quá trình phân tích cũng như sử dụng dữ liệu đồ thị có cấu trúc. Luận văn đề xuất xây dựng ứng dụng đảm bảo tính riêng tư cho dữ liệu đồ thị trong cơ sở dữ liệu Neo4j. Ứng dụng gồm hai hướng tiếp cận chính, một là áp dụng các thuật toán ấn danh k-anonymity và l-diversity để ẩn danh dữ liệu thông tin các cá nhân trong đồ thị và hai là áp dụng thuật toán k-Degree anonymity để đảm bảo tính riêng tư trên các quan hệ của các cá nhân trong mạng dữ liệu đồ thị. iii ABSTRACT Today, graph-structured data is increasingly common, such as social network graphs, web page graphs, or face-to-face communication graphs. Graph data provides a lot of useful information about people as well as human-to-human relationships. Through these graphs, researchers can use analysis for specific studies based on the personal information as well as the relationships of the people contained in the graph networks. However, the collection, transmission, and analysis of this information often exposes personal information. Even after analysis, personal information may still exist on the analyzed personal data set. Along with that, governments around the world have had many laws to ensure privacy such as HIPPA, GDPR or Vietnam's cybersecurity law in 2018. The analysis of data on the graph network is necessary, but it is still necessary to ensure the privacy of individuals in the graph. Therefore, it is necessary to have tools to support researchers that can ensure privacy during the analysis and use of structured graph data. The thesis proposes to build an application to ensure the privacy of graph data in the Neo4j database. The application consists of two main approaches, one is to apply the k-anonymity and l-diversity encryption algorithm to anonymize the individual information data in the graph and the other is to apply the k-Degree anonymity algorithm to ensure privacy on the relationships of individuals in the graph data network. iv LỜI CAM ĐOAN Tôi cam kết rằng luận văn được trình bày ở đây là bài làm gốc của riêng tôi và chưa được xuất bản hoặc nộp ở nơi khác cho bất kỳ chương trình cấp bằng, bằng tốt nghiệp hoặc bằng cấp nào khác. Mọi dữ liệu tài liệu hoặc công việc do người khác thực hiện và được trích dẫn trong luận án này đã được liệt kê đầy đủ trong phần tài liệu tham khảo. TRẦN THẾ HUY v MỤC LỤC NHIỆM VỤ LUẬN VĂN THẠC SĨ ................................................................ i LỜI CÁM ƠN .................................................................................................. ii TÓM TẮT LUẬN VĂN THẠC SỸ .............................................................. iii ABSTRACT .................................................................................................... iv LỜI CAM ĐOAN ............................................................................................ v MỤC LỤC ....................................................................................................... vi DANH SÁCH CÁC HÌNH ẢNH ................................................................... ix 1 2 GIỚI THIỆU ĐỀ TÀI ............................................................................... 1 1.1 Tổng quan về cơ sở dữ liệu đồ thị thuộc tính .................................... 1 1.2 Cơ sở dữ liệu đồ thị Neo4j .................................................................. 2 1.3 Đặt vấn đề đảm bảo tính riêng tư cho dữ liệu đồ thị thuộc tính....... 3 1.4 Các công trình liên quan .................................................................... 5 1.5 Cây khái quát hoá (Generalization hierarchy) .................................. 7 1.6 Thuật toán graph pertubation ............................................................ 8 1.7 Thuật toán ẩn danh k-Degree anonymity .......................................... 8 CÁC PHƯƠNG PHÁP ĐỀ XUẤT .......................................................... 9 2.1 Thuật toán Mondrian Multidimensional K-Anonymity .................... 9 2.2 Thuật toán k-Degree anonymity....................................................... 11 2.3 Các độ đo kết quả .............................................................................. 11 2.3.1 Discernability metric .................................................................. 11 2.3.2 Normalized average equivalence class size metric .................... 12 vi 2.3.3 Normalized Certainty Penalty metric ......................................... 12 2.3.4 Degree anonymization cost ........................................................ 12 2.4 3 Các câu truy vấn cơ bản của ngôn ngữ Cypher .............................. 13 2.4.1 Tạo nút trong mạng .................................................................... 13 2.4.2 Tạo quan hệ giữa các nút ............................................................ 13 2.4.3 Xoá nút trong mạng .................................................................... 13 2.4.4 Xoá quan hệ giữa các nút ........................................................... 14 2.4.5 Cập nhật giá trị nút ..................................................................... 14 2.4.6 Tìm kiếm nút hay quan hệ trong mạng ...................................... 14 TỔNG QUAN VỀ ỨNG DỤNG ............................................................. 14 3.1 Kiến trúc ứng dụng ........................................................................... 14 3.2 Các công nghệ để hiện thực ứng dụng ............................................ 15 3.2.1 Yêu cầu hệ thống ........................................................................ 15 3.2.2 Thư viện xây dựng giao diện người dùng ReactJS .................... 16 3.2.3 Phần mềm Node.js...................................................................... 16 3.2.4 Ngôn ngữ lập trình Python ......................................................... 16 3.3 Tổng quan về mã nguồn ứng dụng .................................................. 17 3.4 Chức năng ứng dụng ........................................................................ 17 3.4.1 Ẩn danh hoá dữ liệu bằng giải pháp trên cây khái quát ............. 17 3.4.2 Ẩn danh hoá dữ liệu bằng thuật toán Mondrian Multidimensional K-Anonymity .................................................................................................... 22 4 3.4.3 Áp dụng thuật toán ẩn danh hoá đồ thị k-Degree anonymity ..... 24 3.4.4 Đăng ký và đăng nhập ................................................................ 25 3.4.5 Quản lý kết nối đến các cơ sở dữ liệu đồ thị thuộc tính ............. 26 3.4.6 Xem dữ liệu cơ sở dữ liệu đồ thị (Database Overview) ............. 27 KẾT QUẢ KIỂM THỬ ỨNG DỤNG ................................................... 29 4.1 Cấu hình máy tính chạy kiểm thử.................................................... 29 vii 4.2 Kết quả kiểm thử với thuật toán Mondrian ..................................... 29 4.3 Kết quả kiểm thử với thuật toán ẩn danh đồ thị k-Degree anonymity và Graph pertubations ......................................................................................... 29 5 KẾT LUẬN .............................................................................................. 30 DANH MỤC CÁC TÀI LIỆU THAM KHẢO ........................................... 31 viii DANH SÁCH CÁC HÌNH ẢNH Hình 1-1 Ví dụ về mô hình đồ thị thuộc tính .................................................... 1 Hình 1-2 Mô tả về 2 tập dữ liệu ........................................................................ 5 Hình 1-3 Bảng dữ liệu đã biến đổi để thoả mô hình k-anonymity với k=2 ...... 6 Hình 1-4 Ví dụ minh hoạ kỹ thuật Suppression ................................................ 7 Hình 1-5 Ví dụ cây khái quát ............................................................................ 8 Hình 2-1 Ví dụ điểm dữ liệu và áp dụng Mondrian ........................................ 10 Hình 2-2 Bảng dữ liệu sau khi ẩn danh bằng Mondrian ................................. 11 Hình 3-1 Kiến trúc ứng dụng .......................................................................... 15 Hình 3-2 Các bước ẩn danh dữ liệu cây khái quát .......................................... 18 Hình 3-3 Ví dụ chọn Manual Config .............................................................. 18 Hình 3-4 Cấu hình cây khái quát..................................................................... 19 Hình 3-5 Chọn giải pháp ẩn danh thuộc cây khái quát ................................... 20 Hình 3-6 Kết quả ẩn danh bằng cây khái quát ................................................ 21 Hình 3-7 Tạo task ẩn danh hoá dữ liệu ........................................................... 21 Hình 3-8 Cấu hình thuật toán thuật toán Mondrian ........................................ 22 Hình 3-9 Ví dụ cấu hình thuật toán thuật toán Mondrian ............................... 23 Hình 3-10 Cấu hình l-Diversity....................................................................... 23 Hình 3-11 Kết quả l-Diversity......................................................................... 24 Hình 3-12 Cấu hình cho thuật toán k-Degree Anonymity .............................. 25 Hình 3-13 Trang đăng ký ................................................................................ 25 Hình 3-14 Trang đăng nhập ............................................................................ 26 Hình 3-15 Trang quản lý kết nối ..................................................................... 27 Hình 3-16 Trang xem cơ sở dữ liệu dạng đồ thị ............................................. 28 Hình 3-17 Trang xem cơ sở dữ liệu dạng bảng ............................................... 28 Hình 3-18 Trang thêm hay xuất dữ liệu .......................................................... 29 ix 1 GIỚI THIỆU ĐỀ TÀI 1.1 Tổng quan về cơ sở dữ liệu đồ thị thuộc tính Cơ sở dữ liệu đồ thị [1] là bất kỳ hệ thống lưu trữ nào sử dụng cấu trúc đồ thị với các nút và cạnh, để biểu diễn và lưu trữ dữ liệu. Mô hình đồ thị được sử dụng phổ biến nhất trong ngữ cảnh của cơ sở dữ liệu đồ thị được gọi là mô hình đồ thị thuộc tính - Attributed Graph Model (có nhãn). Mô hình đồ thị thuộc tính chứa các thực thể được kết nối (các nút) có thể chứa bất kỳ số lượng thuộc tính (thuộc tính) được biểu thị dưới dạng cặp khóa-giá trị. Các nút và cạnh có thể được gắn thẻ bằng các nhãn thể hiện các vai trò khác nhau của chúng trong miền ứng dụng. Một số cách tiếp cận gọi nhãn là loại. Nhãn cũng có thể dùng để đính kèm siêu dữ liệu — chỉ mục hoặc thông tin ràng buộc — vào một số nút nhất định. Các mối quan hệ cung cấp các kết nối có hướng, có liên quan về mặt ngữ nghĩa (các cạnh) giữa hai nút. Một mối quan hệ luôn có một hướng, một nút bắt đầu và một nút kết thúc. Giống như các nút, các mối quan hệ có thể có bất kỳ thuộc tính nào. Thông thường, các mối quan hệ có các thuộc tính định lượng, chẳng hạn như trọng lượng, chi phí, khoảng cách, xếp hạng hoặc khoảng thời gian. Thuộc tính làm cho các nút và các cạnh mang tính mô tả và thực tế hơn. Cả hai nút và cạnh đều được xác định bởi một mã định danh duy nhất. Ví dụ về mô hình đồ thị thuộc tính (Hình 1-1) với các thực thể là: Employee, Company và City. Các mối quan hệ là: Company HAS_STAFF Employee { Tên: “Johnny Chen” ; Năm sinh: 1994 } hay Company LOCATED_IN City. Hình 1-1 Ví dụ về mô hình đồ thị thuộc tính 1 Khi các mối quan hệ được lưu trữ hiệu quả, hai nút có thể chia sẻ bất kỳ số lượng hoặc mối quan hệ nào thuộc các loại khác nhau mà không làm giảm hiệu suất. Lưu ý rằng mặc dù chúng được định hướng nhưng các mối quan hệ luôn có thể được điều hướng bất kể hướng nào. Trên thực tế, mô hình đồ thị thuộc tính liên quan đến cấu trúc dữ liệu trong lý thuyết đồ thị được gọi là “labelled and directed attributed multigraphs”. Cơ sở dữ liệu đồ thị tập trung vào: • Xử lý dữ liệu được kết nối tốc độ cao. • Linh hoạt trong các mô hình dữ liệu sử dụng đằng sau các đồ thị được sử dụng. • Hiệu suất đặc biệt cao cho các lần đọc cục bộ, bằng cách duyệt qua cây. 1.2 Cơ sở dữ liệu đồ thị Neo4j Cơ sở dữ liệu đồ thị Neo4j [2] là một cơ sở dữ liệu đồ thị gốc, NoSQL, mã nguồn mở, cung cấp phần phụ trợ giao dịch tuân thủ ACID cho các ứng dụng. Sự phát triển ban đầu bắt đầu vào năm 2003, nhưng nó đã được công bố rộng rãi từ năm 2007. Mã nguồn, được viết bằng Java và Scala, có sẵn miễn phí trên GitHub hoặc dưới dạng tải xuống ứng dụng máy tính thân thiện với người dùng. Neo4j có cả phiên bản cộng đồng và phiên bản doanh nghiệp của cơ sở dữ liệu. Phiên bản doanh nghiệp bao gồm tất cả những gì cộng đồng phải cung cấp, cùng với các yêu cầu bổ sung dành cho doanh nghiệp như khả năng sao lưu, phân cụm và chuyển đổi dự phòng. Neo4j được gọi là cơ sở dữ liệu đồ thị gốc vì nó triển khai hiệu quả mô hình đồ thị thuộc tính xuống cấp lưu trữ. Điều này có nghĩa là dữ liệu được lưu trữ chính xác như khi bạn viết bảng trắng và cơ sở dữ liệu sử dụng con trỏ để điều hướng và duyệt qua đồ thị. Trái ngược với xử lý đồ thị hoặc thư viện trong bộ nhớ, Neo4j cũng cung cấp các đặc điểm cơ sở dữ liệu đầy đủ, bao gồm tuân thủ giao dịch ACID, hỗ trợ cụm và chuyển đổi dự phòng thời gian chạy - làm cho nó phù hợp để sử dụng đồ thị cho dữ liệu trong các kịch bản sản xuất. Một số tính năng cụ thể sau làm cho Neo4j rất phổ biến trong số các nhà phát triển, kiến trúc sư và nhà quản trị cơ sở dữ liệu: 2 • Cypher, một ngôn ngữ truy vấn khai báo tương tự như SQL, nhưng được tối ưu hóa cho đồ thị. Hiện được sử dụng bởi các cơ sở dữ liệu khác như SAP HANA Graph và Redis graph thông qua dự án OpenCypher. • Constant time traversals (Thời gian ngắn để duyệt) trong đồ thị lớn cho cả chiều sâu và chiều rộng do biểu diễn hiệu quả các nút và mối quan hệ. Cho phép mở rộng quy mô lên đến hàng tỷ nút trên phần cứng vừa phải. • Cơ sở dữ liệu đồ thị thuộc tính linh hoạt có thể thích ứng theo thời gian, có thể hiện thực hóa và thêm các mối quan hệ mới sau này để cập nhật và tăng tốc suy suất dữ liệu khi nhu cầu kinh doanh thay đổi. • Trình điều khiển cho các ngôn ngữ lập trình phổ biến, bao gồm Java, JavaScript, .NET, Python,… 1.3 Đặt vấn đề đảm bảo tính riêng tư cho dữ liệu đồ thị thuộc tính Dữ liệu đồ thị có thông tin và ngữ nghĩa phong phú được biểu thị bằng đồ thị nên được sử dụng trong nhiều ứng dụng, chẳng hạn như mạng xã hội, mạng sinh học, mạng giao thông, biểu đồ web, cơ sở tri thức và biểu đồ RDF. Nhiều ứng dụng mới nổi dựa vào đồ thị lớn để đáp ứng nhu cầu truy vấn của họ, chẳng hạn như đồ thị tri thức của Google và tìm kiếm đồ thị của Facebook. Các ứng dụng này đã trở nên phổ biến để chia sẻ thông tin. Do đó, lượng dữ liệu đồ thị mạng xã hội đã phát triển nhanh chóng và điều này mang lại nhiều cơ hội để khai thác và phân tích dữ liệu, chẳng hạn như để tìm cộng đồng các nhóm và sự tiến hóa của chúng [3] [4]. Tuy nhiên, dữ liệu đồ thị mạng xã hội thường chứa thông tin cá nhân của người dùng; điều quan trọng là phải bảo vệ những thông tin này trong bất kỳ hoạt động chia sẻ và khai thác. Đó là những ví dụ nổi tiếng về việc tiết lộ thông tin cá nhân ngoài ý muốn trong dữ liệu đã phát hành (còn gọi là đã công bố), khiến các tổ chức ngày càng thận trọng trong việc phát hành các tập dữ liệu này. Thậm chí, luật pháp Việt Nam cũng đã đề xuất đảm bảo quyền riêng tư của cá nhân trong bộ luật An ninh mạng năm 2018. Vì vậy, trước khi xuất bản tất cả dữ liệu này để phân tích, dữ liệu khai thác và các mục đích khác, cần đảm bảo rằng dữ liệu đã xuất bản sẽ không chứa bất kỳ thông tin riêng tư nào. 3 Để đảm bảo tính riêng tư cho dữ liệu thì sẽ có nhiều cách tiếp cận [5] như: • Kiểm soát truy cập: trở nên phức tạp trong triển khai và khó quản lý trong cấp phát quyền trong môi trường mở với nhiều bên cùng dụng kho dữ liệu. • Mã hóa dữ liệu: thường dẫn đến chi phí tính toán để mã hoá dữ liệu trong quá trình vận hành, và đánh đổi này sẽ còn nghiêm trọng hơn với dữ liệu đa dạng và lớn. • Ẩn danh dữ liệu: đây là một bước thường có khi công khai dữ liệu và hướng tiếp cận lâu đời được hỗ trợ nhiều bởi giải thuật vững chắc. Luận văn tập trung đề xuất xây dựng ứng dụng tích hợp các kỹ thuật ẩn danh dữ liệu để đảm bảo tính riêng tư cho dữ liệu đồ thị thuộc tính trong cơ sở dữ liệu Neo4j. Về ý nghĩa khoa học, ứng dụng đề xuất ra một mô hình ứng dụng có thể triển khai các dạng thuật toán ẩn danh trên bảng cho các nốt dữ liệu trong dữ liệu đồ thị thuộc tính. Cùng với đó, ứng dụng còn kết hợp nó với thuật toán ẩn danh trên đồ thị mà tiêu biểu là thuật toán k-Degree anonymity. Về ý nghía thực tiễn, ứng dụng đáp ứng cho nhu cầu ngày càng đa dạng về dữ liệu mở để khai phá của các nhà nghiên cứu. Ứng dụng là công cụ đảm bảo cho việc chia sẽ dữ liệu mở không vi phạm các quy định về quyền riêng tư gây ảnh hưởng đến các cá nhân có trong dữ liệu mở đó. Ví dụ trong điều tra nghiên cứu những đặc điểm người bị lây nhiễm bệnh do virus thì cần thiết quá trình điều trị thì đi kèm với đó là các thông tin bệnh lý và thông tin cá nhân của các bệnh nhân có thể bị lộ ra ngoài khi dữ liệu được xuất bản mở, chia sẻ với nhau giữa các nhà nghiên cứu. Ngay cả khi các nhà nghiên cứu không công khai mà chia sẻ với nhau họ vẫn có thể vi phạm các quy định của pháp luật về quyền riêng tư như đã đề cập. Vì vậy ứng dụng cần thiết để ẩn danh dữ liệu đồ thị và xuất bản dữ liệu cho các mục đích khai phá, để hỗ trợ các dự án khoa học đem lại nhiều lợi ích cho cộng đồng. 4 1.4 Các công trình liên quan Nói về ẩn danh hoá dữ liệu, đầu tiên rất nổi tiếng và đơn giản là mô hình kanonymity [6]. Mô hình đưa ra một ví dụ về tấn công quyền riêng tư như sau. Giả sử kẻ tấn công có 2 tập dữ liệu (Hình 1-2 Mô tả về 2 tập dữ liệu) [6]: • Tập thứ nhất là bảng dữ liệu danh sách bầu cử có tên, địa chỉ, giới tính, số vùng và ngày sinh. • Tập thứ hai là bảng bệnh án bệnh nhân gồm tên bệnh của nhiều bệnh nhân đã xoá đi cột tên, tuy nhiên vẫn còn các cột như giới tính, số vùng và ngày sinh. Dựa vào các cột dữ liệu trùng nhau, kẻ tấn công có thể liên kết dữ liệu của tập dữ liệu thứ nhất qua tập dữ liệu thứ hai để biết chính xác bệnh nhân nào bị bệnh gì, tên gì và địa chỉ ở đâu. Hình 1-2 Mô tả về 2 tập dữ liệu Từ đó, trong ví dụ này, tên bệnh thuộc tập các cột dữ liệu nhạy cảm. Thêm nữa, bài báo xem các cột: giới tính, số vùng và ngày sinh là tập các thuộc tính bán định danh hay còn gọi là tập quasi-identifier. Nghĩa là nếu ai đó có được dữ liệu gồm giới tính, số vùng và ngày sinh thì sẽ có thể xác định lại một người cách liên kết lại các dữ liệu từ bảng thứ hai về bảng thứ nhất. Để giải quyết cho vấn đề này, mô hình k-anonymity với ý tưởng chính như sau. Một tập dữ liệu được cho là thoả k-anonymity nếu thông tin của mỗi người không thể phân biệt được với ít nhất k - 1 cá nhân có thông tin cũng xuất hiện trong đó. Ví dụ, 5 dữ liệu sẽ được biến đổi thoả mô hình k-anonymity (Hình 1-3 Bảng dữ liệu đã biến đổi để thoả mô hình k-anonymity với k=2) [6] với k = 2 Hình 1-3 Bảng dữ liệu đã biến đổi để thoả mô hình k-anonymity với k=2 Tuy nhiên, mô hình k-anonymity vẫn có những điểm yếu nhất nhất định của nó như có thể bi tấn công dựa trên kiến thức đã biết hay bị tấn công đồng nhất. Điều này dẫn đến mô hình khắc phục dạng tấn công đồng nhất cho k-anonymity, là mô hình ldiversity [7]. Mô hình l-diversity với ý tưởng chính là: Một lớp dữ liệu thỏa mãn mô hình ldiversity khi có ít nhất L giá trị biểu diễn tốt phân biệt cho thuộc tính nhạy cảm. Mô hình l-diversity có ưu điểm là có thể cản trở kẻ tấn công tận dụng phân phối toàn cục của tập dữ liệu với các giá trị dữ liệu của thuộc tính để suy ra thông tin về các giá trị dữ liệu nhạy cảm. Tuy nhiên trong tập dữ liệu thực, các giá trị thuộc tính có thể bị lệch hoặc tương tự về mặt ngữ nghĩa vì vậy mô hình t-closeness được đề xuất để để khắc phục nhược điểm đó. Mô hình t-closeness: Một lớp tương đương được cho là thoả t-closeness nếu khoảng cách giữa phân phối của một thuộc tính nhạy cảm trong lớp này và phân phối của thuộc tính trong toàn bộ bảng không quá ngưỡng t. Một bảng được cho thỏa tcloseness nếu tất cả các lớp tương đương thoả t-closeness. [8] 6 Hỗ trợ xây dựng mô hình k-anonymity trên có thể hiện thực bằng các thuật như: Suppression hay Generalization [9]. Với kỹ thuật Generalization là kỹ thuật tổng quát hoá dữ liệu, ví dụ ta có 1 giá trị ngày sinh trong bảng dữ liệu là ‘24-01-1994’ chúng ta có thể tổng quát hoá lại thành ‘01-1994’ hay ‘1994’ hay ‘19**’. Với kỹ thuật Suppression ta sẽ loại bỏ những giá trị trong bảng dữ liệu. Ví dụ (Hình 1-4 Ví dụ minh hoạ kỹ thuật Suppression) [9]. Hình 1-4 Ví dụ minh hoạ kỹ thuật Suppression Tổng quát các vấn đề thì có công trình “Graph-Based Privacy-Preserving Data Publication” [10]. Bài báo đề xuất một framework bảo vệ quyền riêng tư dữ liệu mở bao gồm nhiều kiểu dữ liệu như mạng xã hội, định nghĩa mạng ẩn danh và các độ đo hỗ trợ. 1.5 Cây khái quát hoá (Generalization hierarchy) Việc ẩn danh hoá còn được kết hợp với việc mã hoá bằng cây khái quát [11]. Cách mã hoá này có thể áp dụng cho dữ liệu có tính liên tục như số hoặc rời rạc. Ý 7 tưởng của việc áp dụng cây khái quát nhầm mục tiêu loại bỏ các bảng ghi vi phạm quyền riêng tư và thay thế bằng dữ liệu khái quát hơn trong một cây. Ví dụ dữ liệu là màu sắc có khoảng từ 8 màu. Cấp 0: 4 nhóm gồm: “xanh”, “đỏ”, “tím”, “vàng”. Cấp 1: 2 nhóm gồm “xanh-đỏ” và “tím-vàng”. Cấp 2: Chia thành 1 nhóm “màu” (tất cả giá trị được khái quát hoá về 1 giá trị màu). Với giá trị đỏ và khái quát hoá cấp 1 thì giá trị sẽ được mã hoá thành nhãn “xanh-đỏ”. Như vậy việc biến đổi giá trị với cấp độ khái quát càng cao, thì mức độ đảm bảo quyền riêng tư càng tốt. Lúc này cây khái quát sẽ được biểu diễn (Hình 1-5 Ví dụ cây khái quát) như sau: Hình 1-5 Ví dụ cây khái quát 1.6 Thuật toán graph pertubation Thuật toán graph pertubations [12] thuộc nhóm thuật toán nhiễu loạn ngẫu nhiên. Đồ thị mới Gp = (Vp, Ep) được xây dựng từ Gna thông qua một chuỗi xóa m cạnh sau đó là chèn m cạnh. Các phép xóa được chọn ngẫu nhiên đồng nhất từ tập hợp tất cả các cạnh tồn tại trong Gna. Các phần chèn được chọn ngẫu nhiên đồng nhất từ tập hợp tất cả các cạnh không tồn tại của đồ thị tạm thời. 1.7 Thuật toán ẩn danh k-Degree anonymity Nổi bật gần đây nhất có công trình lớn về ẩn danh đồ thị là “Towards Plausible Graph Anonymization” [13]. Bài báo chỉ ra điểm yếu nổi bật nhất của các thuật toán ẩn danh đồ thị đó là: Khi tạo ra thêm các cạnh giả trong đồ thị, thuật toán không tính đến các đặc điểm chính của cấu trúc đồ thị, cụ thể như “Vấn đề dự đoán liên kết cho 8 mạng xã hội” [14]. Từ đó, bài báo đề xuất ra các giải thuật, nổi bật trong đó là giải thuật k-Degree anonymity [15]. Do k-Degree anonymity đáp ứng được khái niệm chính là mô hình k-anonymity trong cơ sở dữ liệu riêng tư mà vẫn hạn chế thay đổi dữ liệu ban đầu nên ứng dụng tập trung vào triển khai k-Degree anonymity. Giải thuật giả định rằng kẻ tấn công có kiến thức trước về số liên kết nút mục tiêu trong mạng xã hội, cụ thể như biết được số lượng liên kết bạn bè của mục tiêu để xác định được mục tiêu. Để gảm thiểu điểm yếu này k-Degree anonymity sửa đổi đồ thị ban đầu, sao cho tạo ra đồ thị ẩn danh, mỗi người chia sẻ cùng một mức độ (degree) với ít nhất k -1 người dùng khác. 2 CÁC PHƯƠNG PHÁP ĐỀ XUẤT Ứng dụng có 2 chế độ cho người dùng ẩn danh hoá dữ liệu cá nhân ở các nút của đồ thị với thuật toán k-anonymity và l-diversity, gồm: • Run with Optimal Method - Ứng dụng sẽ dùng thuật toán Mondrian Multidimensional [16] để ẩn danh hoá dữ liệu. • Run with Manually Configs - Ứng dụng sẽ dùng các thông số người dùng cung cấp để ẩn danh hoá dữ liệu. Ứng dụng còn dùng thêm thuật toán để ẩn danh đồ thị là thuật toán k-Degree Anonymity. Sau quá trình ẩn danh hoá, ứng dụng tiến hành áp dụng các độ đo phổ biến để đánh giá kết quả là Discernability metric (CDM) [16], Normalized average equivalence class size metric (CAVG) [16] và Information loss of Generalization [17]. Ứng dụng sử dụng ngôn ngữ Cypher để truy xuất và lưu trữ dữ liệu trong cơ sở dữ liệu đồ thị Neo4j trong quá trình ẩn danh hoá dữ liệu. 2.1 Thuật toán Mondrian Multidimensional K-Anonymity Thuật toán Mondrian [16] là 1 thuật toán greedy partitioning algorithm. Giống như xây dựng kd-tree, độ phức tạp thời gian là O (nlogn), trong đó n = | T |. Thuật toán kiểm tra nếu có thể phân chia 1 phân vùng thì sẽ tìm giá trị trung bình của phân vùng là điểm phân chia. Sau đó thuật toán tiếp tục đệ quy và lấy điểm chia đặt vào phân vùng con bên trái và phân vùng con bên phải để tiếp tục xử lý bằng đệ quy. 9