Luận văn Những vấn đề bảo mật khi truy vấn cơ sở dữ liệu xml động được “outsourced”

– TP. Hồ Chí Minh 02/2007 – ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA WX NGUYỄN VIỆT HÙNG NHỮNG VẤN ĐỀ BẢO MẬT KHI TRUY VẤN CƠ SỞ DỮ LIỆU XML ĐỘNG ĐƯỢC “OUTSOURCED” CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ NGÀNH: 60.48.01 LUẬN VĂN THẠC SĨ Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 2/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH Cán bộ hướng dẫn khoa học: Tiến sĩ ĐẶNG TRẦN KHÁNH Cán bộ chấm nhận xét 1: Tiến sĩ NGUYỄN ĐỨC CƯỜNG Cán bộ chấm nhận xét 2: Tiến sĩ TRẦN VĂN HOÀI Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 03 tháng 02 năm 2007 TRƯỜNG ĐẠI HỌC BÁCH KHOA CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG ĐÀO TẠO SĐH ĐỘC LẬP – TỰ DO – HẠNH PHÚC Tp. HCM, ngày . . . . tháng . . . . năm 200. . NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Nguyễn Việt Hùng Phái: Nam Ngày, tháng, năm sinh: 14 tháng 01 năm 1981 Nơi sinh: Kiên Giang Chuyên ngành: Công nghệ thông tin MSHV: 00703170 I- TÊN ĐỀ TÀI: Các vấn đề bảo mật trong việc truy vấn CSDL XML động được outsourced. II- NHIỆM VỤ VÀ NỘI DUNG: - Tìm hiểu tổng quan các vấn đề liên quan bảo mật CSDL được outsourced. - Tìm hiểu các nghiên cứu liên quan khía cạnh Query Assurance. - Đề xuất giải pháp kiểm tra query assurance cho CSDL XML được outsourced. - Xây dựng chương trình hiện thực giải pháp, đo đạc và đánh giá giải pháp đề ra. III- NGÀY GIAO NHIỆM VỤ : ..................................................................................... IV- NGÀY HOÀN THÀNH NHIỆM VỤ: ...................................................................... V- CÁN BỘ HƯỚNG DẪN: Tiến sĩ Đặng Trần Khánh. CÁN BỘ HƯỚNG DẪN CN BỘ MÔN (Học hàm, học vị, họ tên và chữ ký) QL CHUYÊN NGÀNH Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua. Ngày tháng năm 2006 TRƯỞNG PHÒNG ĐT – SĐH TRƯỞNG KHOA QL NGÀNH Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 4/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh ACKNOWLEDGEMENT I would like to express my gratefulness To my mom and dad who has brought me up and done everything for my life; To my advisor, Dr. DangTran Khanh, who has advised me with all his heart; To my friends who are always in my side, and especially, to my colleagues who are willing to help me complete some parts of the work. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 5/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh ABSTRACT With the impressive improvement of the network technologies, database outsourcing is emerging as an important trend beside the “application-as-a-service”. In this model, data owners ship their data to external service providers. Service providers do data management tasks and offer their clients a mechanism to manipulate outsourced database. Since a service provider is not always fully trusted, security and privacy of outsourced data are important issues. These problems are referred as data confidentiality, user privacy, data privacy and query assurance. Among them, query assurance takes a crucial role to the success of the database outsourcing model. To the best of our knowledge, however, query assurance, especially for outsourced XML database, has not been concerned reasonably in any previous work. In this paper, we propose a novel index structure, Nested Merkle B+ Tree, combining the advantages of B+ tree and Merkle Hash Tree to completely deal with three issues of query assurance known as correctness, completeness and freshness in outsourced XML database. Experimental results with real dataset prove the effeciency of our proposed solution. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 6/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh TÓM TẮT Với sự phát triển vượt bậc trong lĩnh vực công nghệ mạng đã cho ra đời nhiều dịch vụ từ xa, đặc biệt là sự ra đời của dịch vụ “application as a service”. Dịch vụ này giúp cho mọi người có thể tiếp cận một cách hợp pháp với các phần mềm mới nhất với một chi phí thấp nhất. Thời gian gần đây, xuất hiện xu thế mới cho phép làm giảm chi phí về quản lý dữ liệu qua một dịch vụ gọi là “database outsourcing”. Với dịch vụ này, các đơn vị, tổ chức lưu trữ thông tin, dữ liệu của mình tại máy chủ của các nhà cung cấp dịch vụ. Các nhà cung cấp dịch vụ sẽ đảm nhận các công tác bảo trì máy chủ, bảo trì phần mềm DBMS cũng như bảo trì CSDL của khách hàng. Bên cạnh đó, họ cung cấp các cơ chế cho phép các đơn vị, tổ chức có thể thao tác trên CSDL của mình. Tuy nhiên, thông tin vốn là một tài sản hết sức quý báu, nên các đơn vị hoàn toàn không thể tin cậy được các nhà cung cấp dịch vụ trong việc đảm bảo an toàn cho CSDL. Do đó đã phát sinh các yêu cầu bảo mật về CSDL outsourced. Các vấn đề đó có thể tóm gọn trong bốn yêu cầu bảo mật, bao gồm: data confidentiality, data privacy, user privacy và query assurance. Ngoài phần giới thiệu tổng quan về các kết quả đạt được trong lĩnh vực data outsourcing, tài liệu đưa ra một cấu trúc chỉ mục mới cho dữ liệu XML. Dựa trên cấu trúc này, tài liệu trình bày phương pháp đảm bảo truy vấn cho CSDL XML outsourced cũng như một số kết quả thực nghiệm hiện thực cho phương pháp này. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 7/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh MỤC LỤC ACKNOWLEDGEMENT ................................................................................................................ 4  ABSTRACT ................................................................................................................................. 5  Chương 1 GIỚI THIỆU ..................................................................................................... 8  1.1  Data Confidentiality ............................................................................................ 12  1.2  User Privacy và Data Privacy ............................................................................. 13  1.3  Query Assurance ................................................................................................. 17  1.4  Nhận xét .............................................................................................................. 19  Chương 2 CÁC NGHIÊN CỨU LIÊN QUAN ............................................................... 22  2.1  Khái niệm ............................................................................................................ 22  2.2  Hướng tiếp cận dùng chữ ký điện tử ................................................................... 23  2.3  Hướng tiếp cận sử dụng cấu trúc dữ liệu đặc biệt ............................................... 25  2.4  Hướng tiếp cận Challenge – Response. .............................................................. 28  2.5  Hướng tiếp cận dựa vào đặc thù của bài toán ..................................................... 30  2.6  Bảo đảm truy vấn cho dữ liệu dạng cây .............................................................. 31  2.7  Nhận xét .............................................................................................................. 33  Chương 3 DỮ LIỆU XML ............................................................................................... 35  3.1  Mô hình lưu trữ ................................................................................................... 35  3.2  Chỉ mục cho tài liệu XML .................................................................................. 40  Chương 4 ĐẢM BẢO TRUY VẤN ................................................................................. 42  4.1  Phương pháp ....................................................................................................... 42  4.2  Nested B+ Tree ................................................................................................... 43  4.3  Tác vụ chọn ......................................................................................................... 45  4.4  Các tác vụ cập nhật dữ liệu ................................................................................. 49  Chương 5 PHÂN TÍCH .................................................................................................... 51  Chương 6 THỰC NGHIỆM ............................................................................................. 58  Chương 7 KẾT LUẬN ...................................................................................................... 63  Chương 8 PHỤ LỤC ......................................................................................................... 67  8.1  Cấu trúc lưu trữ XML ......................................................................................... 67  8.2  Giải thuật gán nhãn (labeling) ............................................................................. 67  8.3  Chương trình thử nghiệm .................................................................................... 68  8.4  Lược đồ tài liệu mondial.xml .............................................................................. 71  8.5  Kế hoạch thực thi truy vấn .................................................................................. 72  8.6  Tóm lược các nghiên cứu liên quan .................................................................... 73  8.7  Bài báo liên quan ................................................................................................ 83  Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 8/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chương 1 GIỚI THIỆU Thông tin là một nguồn tài nguyên rất quan trọng trong mọi tổ chức. Quản lý và xử lý thông tin hiệu quả đã và đang tập trung sự quan tâm của mọi người. Với sự ra đời của máy tính điện tử (eclectronic computer) và các máy tính cá nhân (personal computer – PC), ngành khoa học máy tính đã mang đến kỷ nguyên mới, kỷ nguyên của thông tin, tác động mạnh mẽ đến mọi lĩnh vực trong đời sống. Dữ liệu được lưu trữ thành các các cơ sở dữ liệu (CSDL), thông thường, được đặt trong nội bộ tổ chức (in-house database). Điều này đòi hỏi mỗi tổ chức phải đầu tư một khoản chi phí cho việc quản lý hệ thống CSDL, bao gồm: thiết bị phần cứng (máy móc, hệ thống mạng), phần mềm (hệ quản trị CSDL – DBMS, các chương trình ứng dụng cụ thể,…), nhân sự (nhân viên quản trị mạng, nhân viên quản trị CSDL,…). Cùng với sự phát triển của xã hội nói chung và tổ chức nói riêng, nhu cầu lưu trữ và xử lý ngày càng gia tăng và phức tạp hơn. Những yêu cầu này làm tăng tổng chi phí trong quản lý. Mặc dù, giá thành phần cứng đã giảm rất nhiều, nhưng chi phí bản quyền phần mềm, chi phí cho đội ngũ nhân viên quản trị có trình độ cao để quản lý các hệ thống thông tin ngày một phức tạp thật sự là một vấn đề đáng quan tâm trong tổng chi phí sở hữu (total cost of ownership) của tổ chức. Điều này đặc biệt quan trọng đối với các tổ chức vừa và nhỏ, tổ chức phi lợi nhuận,… Trong những năm gần đây, sự tiến bộ vượt bậc trong công nghệ mạng và truyền thông đã cho ra đời hệ thống mạng tốc độ cao, băng thông rộng, khai sinh ra khái niệm “application as a service”. Người dùng chỉ cần phải trả một khoản phí nhỏ cho nhà cung cấp dịch vụ là có thể sử dụng được các phần mềm mới mà không cần phải quan tâm đến chi phí bản quyền, chi phí cài đặt và bảo trì hệ thống. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 9/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Bên cạnh đó, một dịch vụ khác cũng dần được hình thành, đó là “database as a service”, cung cấp cho người dùng nơi lưu trữ và truy xuất dữ liệu chỉ với một chi phí thấp, mà không cần phải mua sắm thiết bị, cũng như đòi hỏi phải có đội ngũ chuyên trách. Điều này sẽ giúp giảm đáng kể chi phí quản lý thông tin cho các tổ chức. Hình 1.1. Mô hình “Database as a Service”. Trong mô hình “database as a service”, người sở hữu dữ liệu (data owner – DO) đặt CSDL của mình tại nhà cung cấp dịch vụ (service provider – SP) cho các khách hàng (clients, queriers – C, Q) thực hiện các tác vụ trên CSDL như select, insert update. Mô hình còn được gọi là “outsourced database services” (ODBS). Thông tin là tài sản quan trọng của tổ chức. Việc đặt CSDL lưu trữ các thông tin ở một nơi không tin cậy bên ngoài tổ chức (nhà cung cấp dịch vụ) đã làm nảy sinh các vấn đề bảo mật. Chính những vấn đề này sẽ quyết định tính khả thi của Dịch vụ CSDL outsource (outsourced database services – ODBS). Các CSDL outsourced phải được đảm bảo an toàn, ngăn cấm sự truy cập của các tổ chức/cá nhân không có thNm quyền, kể cả nhà cung cấp dịch vụ. Khi đó, chính nhà cung cấp dịch vụ trở thành đối tượng nguy hiểm nhất trong việc đảm bảo bảo mật của dữ liệu. Do các xâm nhập từ bên ngoài, cao nhất, cũng chỉ đạt được khả năng truy cập hệ thống như các nhà cung cấp dịch vụ. Vì vậy các nghiên cứu chủ yếu tập trung vào việc ngăn chặn hành vi xâm nhập của chính các nhà cung cấp dịch vụ (service provider – SP). Về mặt cơ bản, vấn đề bảo mật CSDL tại các SP có thể chia thành bốn lĩnh vực như sau [1]: Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 10/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Data confidentiality tính nội bộ của dữ liệu. Chủ sở hữu dữ liệu (data owner – DO) không muốn những người khác không có thNm quyền có khả năng truy cập CSDL của mình, kể cả các SP. User privacy tính riêng tư của người dùng. Thông tin là hàng hóa. Do đó nó có thể sẽ được bán cho các công ty khác. Các công ty khách hàng không muốn để lộ những thông tin mà họ khai thác, kể cả đối với DO và SP. Data privacy tính bảo mật dữ liệu. DO không muốn khách hàng của mình có thể khai thác được nhiều hơn nhưng thông tin mà họ được phép khai thác. Query Assurance tính bảo đảm truy vấn. Khách hàng (Client) phải được đảm bảo ra dữ liệu mà mình nhận được là chính xác, đầy đủ và mới nhất từ CSDL nguyên thủy do DO cung cấp, mà không bị những thay đổi ngoài ý muốn. Bảng 1.1. Các vấn đề bảo mật trong ODBS. Song song với việc đảm bảo các yêu cầu bảo mật, ta cần phải quan tâm đến hiệu năng thực hiện truy vấn (performance) cũng nhưng khả năng mở rộng của CSDL (scalability, usability). Để đảm bảo data confidentiality, dữ liệu được mã hóa trước khi được “outsourced”. Tuy nhiên điều này làm tăng tính phức tạp của việc xử lý các truy vấn trên dữ liệu mã hóa mà vẫn phải đảm bảo các yêu cầu bảo mật khác. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 11/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Hình 1.2. Mô hình ODBS Trong mô hình ODBS, data owner đặt CSDL của mình tại các server bên ngoài (SP) và thực hiện truy vấn lưu trữ thông qua đường truyền mạng bảo mật. Clients trả chi phí cho data owner để có quyền truy cập dữ liệu, và thực hiện truy cập dữ liệu trực tiếp từ SP cũng thông qua đường truyền bảo mật. Trong thực tế, không phải lúc nào cũng cần thiết phải đảm bảo tất cả các yêu cầu bảo mật trên. Tùy thuộc vào tình huống mà một số yêu cầu có thể được bỏ qua nhằm giảm thiểu mức độ phức tạp để tăng hiệu năng xử lý của hệ thống. Quay trở lại mô hình của ODBS, ta có bốn mô hình bảo mật như sau [1]. - Mô hình UP-DP (User privacy – Data privacy): trong mô hình này DO đồng thời là người cung cấp dịch vụ SP. DO bán thông tin từ CSDL của mình cho các khách hàng khác. Đây chính là mô hình CSDL “in-house” truyền thống. Do đó, mô hình này chỉ quan tâm đến user privacy và data privacy. - Mô hình UP-nDP (User privacy – non Data privacy): mô hình này tương tự mô hình trên, chỉ khác là dữ liệu được bán là phổ biến, không cần phải bảo mật dữ liệu. Chỉ cần che dấu những gì mà người dùng lấy từ CSDL. - Mô hình DC-UP (Data confidentiality – User privacy): trong mô hình này DO đồng thời là khách hàng duy nhất của hệ thống. Đây là mô hình khá phổ biến. Công ty thuê nhà cung cấp dịch vụ lưu trữ dữ liệu nội bộ của mình và thực hiện truy cập trên CSDL này. Do đó, chỉ xem xét confidentiality và user privacy. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 12/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh - Mô hình DC-UP-DP: đây là mô hình đầy đủ và phức tạp nhất. DO thuê nhà cung cấp dịch vụ lưu trữ CSDL của mình. Đồng thời, thực hiện bán thông tin cho các khách hàng khác. DO cần được đảm bảo data confidentiality và data privacy trong khi người dùng cần được đảm bảo user privacy. Trong tất cả các mô hình trên, query assurance luôn là một vấn đề cần được quan tâm và xem xét. Phần tiếp theo điểm qua các nghiên cứu cũng như các kết quả liên quan đến các vấn đề bảo mật trong bảng 1. 1.1 Data Confidentiality Data Confidentiality là yêu cầu đảm bảo CSDL không bị truy cập bất hợp pháp, kể cả các SP. Để đạt được yêu cầu này, CSDL thường được mã hóa trước khi outsourced. Tuy nhiên, chính việc mã hóa này làm gia tăng sự phức tạp trong truy vấn dữ liệu, ảnh hưởng rất nhiều đến hiệu năng của CSDL. Việc lựa chọn cơ chế mã hóa có thể dung hòa giữa nhu cầu bảo mật và yêu cầu về hiệu năng là rất cần thiết. Hiện nay, cơ chế mã hóa khóa bí mật đối xứng (symmetric private key encryption) thường được sử dụng, chẳng hạn như giải thuật Rijndael, DES, TripleDES,.... Thực thi truy vấn trên dữ liệu mã hóa Hacigümüş [5] đề xuất một giải pháp để thực thi cây truy vấn trên dữ liệu mã hóa. Ý tưởng chính của giải pháp này là tách câu truy vấn thành hai phần: một phần sẽ được thực thi tại server, phần còn lại sẽ được thực thi tại client. Kenny C.K.Fong [6] đã chỉ ra năm lỗ hổng bảo mật nghiêm trọng của phương pháp này: 1. Không thỏa mãn tính bảo mật về mặt ngữ nghĩa (semantically secure). Tính chất này không thỏa mãn nếu ta có thể tìm được hai thông điệp m0 và m1 mà có thể đoán được kết quả mã hóa là của m0 hay m1 với xác suất > ½ . 2. N ếu miền giá trị của các trường dữ liệu nhỏ và rời rạc, thì hàm băm của giải thuật không đảm bảo an toàn. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 13/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 3. Giải thuật chưa đảm bảo tính xác thực của kết quả truy vấn trả về. 4. Chưa che dấu câu truy vấn một cách hoàn hảo. Server có thể đoán biết được loại truy vấn mà người dùng thực hiện. 5. Thực hiện mã hóa theo record, do đó, phải giải mã theo record. Vì vậy, người dùng có thể biết nhiều thông tin hơn là họ được phép (không thỏa mãn data privacy). Tìm kiếm dữ liệu mã hóa trên dữ liệu XML R. Brinkman [9] giới thiệu một cách thức cho phép tìm kiếm so trùng các tag của một tài liệu XML đã được mã hóa dựa trên giải thuật Linear Search Strategy for Full Text Documents (1), gọi là Tree Search Strategy for XML Documents (2). Giải thuật (1) chia làm 3 giai đoạn: lưu trữ (storage), tìm kiếm (search), nhận dữ liệu (retrieval). Ở giai đoạn lưu trữ, toàn bộ dữ liệu được chia thành nhiều khối nhỏ cố định, sau đó thực hiện mã hóa các khối này trước khi lưu trữ trên server. DO cần phải ghi nhận một số thông tin về mã hóa để có thể giải mã sau này. Do đó, giải thuật này chỉ phù hợp với mô hình DP-UP. Ở giai đoạn tìm kiếm, chuỗi dữ liệu cần tìm sẽ được mã hóa và chuyển đến cho server so trùng trên các khối dữ liệu để xác định ra vị trí của đoạn dữ liệu mã hóa kết quả. Giai đoạn nhận dữ liệu, kết quả mã hóa sẽ được giải mã dựa theo các thông tin mã hóa được ghi nhận tại giai đoạn lưu trữ. Giải thuật (2) được xây dựng dựa trên giải thuật (1). Tuy nhiên, dữ liệu là một tài liệu XML thay vì file text phi cấu trúc. Kích thước của các khối chia ra cũng không đều nhau mà phục thuộc vào kích thức của từng node (hay mỗi node là một khối). (2) chỉ đáp ứng các câu truy vấn dạng tìm kiếm so trùng các tag name trong tài liệu XML mà không xử lý đến nội dung dữ liệu bên trong node. 1.2 User Privacy và Data Privacy N gười sử dụng CSDL yêu cầu hệ thống phải đảm bảo user privacy/data privacy về yêu cầu truy vấn cũng như kết quả trả về. SP, và kể cả DO, không được phép biết các thông tin này. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 14/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Mặt khác, người dùng chỉ được phép truy vấn những gì mà họ được phép. Kết quả trả về chỉ giới hạn trong phạm vi thông tin mà họ yêu cầu. N gười dùng không được phép “thấy” các dữ liệu không thuộc thNm quyền của mình. PIR-like protocols Để đạt được user-privacy, Chor giới thiệu giao thức PIR (private information retrieval). Về mặt lý thuyết, PIR cho phép người dùng có thể che dấu câu truy vấn và kết quả trả về. Tuy nhiên, CSDL cần phải được nhân bản (replicate) sang nhiều nơi. N ếu không, chi phí phải trả là rất lớn (có thể cần lấy về toàn bộ CSDL tại client). Mặc dù vậy, ngay cả khi đã được nhân bản, chi phí phải trả cũng đủ lớn để PIR không thể áp dụng vào thực tế. PIR chỉ dùng để truy xuất dữ liệu chỉ đọc (read-only). N otably và Ostrovsky phát triển giải thuật PIR cho phép hỗ trợ các thao tác cập nhật dữ liệu đảm bảo user privacy, giao thức PIS (private information storage). Để ứng dụng PIR/PIS vào thực tế, Asonov cải tiến PIR thành giao thức RIR (repudiative information retrieval). RIR giảm bớt một số ràng buộc bảo mật để giảm bớt chi phí I/O mà vẫn đảm bảo user privacy. Tương tự, giao thức RIS cải tiến từ PIS với chi phí thấp và khả thi hơn. Tất cả các giao thức trên đều được xây dựng dựa trên nền tảng của PIR, do đó, chúng còn được gọi là các giao thức họ PIR (PIR-like protocols). Tuy nhiên, các giao thức này chỉ hỗ trợ user privacy mà không đảm bảo data privacy. Gertner đã phát triển một giao thức xây dựng trên một giao thức họ PIR bất kỳ cho phép thỏa mãn cả hai yêu cầu data privacy và user privacy, gọi là SPIR (symmetrically private information retrieval). Dữ liệu dạng cây (tree-structured data) Lin và Candan [2] đề ra một giải thuật cho phép người dùng có thể che dấu dữ liệu và các truy vấn trên dữ liệu dạng cây. Lin và Candan đưa ra hai kỹ thuật: redundancy access và node swapping. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 15/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh - Redundancy access: khi người dùng truy cập một node dữ liệu, hệ thống trả về m node, trong đó m-1 node là ngẫu nhiên để hạn chế không cho server có thể biết được người dùng thực sự truy cập vào node nào. Tuy nhiên, nếu một node được truy cập thường xuyên, node root, server có thể giao các redandancy set để phát hiện ra node này. - Node swapping: một node sau khi được truy xuất sẽ được hoán chuyển sang một node khác. Để làm được điều này, trong m-1 node ngẫu nhiên có một node trống (empty node), node cần đọc sẽ được hoán chuyển với node trống này và cập nhật xuống CSDL. Kỹ thuật này đã giải quyết được vấn đề mà redundancy access gặp phải. [2] cũng chỉ ra năm vấn đề cần giải quyết và giải pháp cho chúng: 1. Quản lý danh sách các empty nodes. Bằng cách sử dụng một node đặc biệt snode để quản lý các eheads, etails để biết được danh sách empty nodes. 2. Phương pháp chọn ngẫu nhiên các node cho redundancy set. 3. Đảm bảo tính toàn vẹn của mối quan hệ cha-con của node bị hoán chuyển. Lin và Candan đề ra hai giải pháp: (1) xác định empty node sẽ hoán chuyển ở node cha và cập nhật liên kết vào node cha trước khi đọc node con lên. (2) ghi nhớ đường dẫn các node từ root đến node cần truy cập, sau đó mới thực hiện hoán chuyển từ dưới lên. [2] cũng chỉ ra rằng: giải pháp (1) là khả thi trong khi (2) là không khả thi. 4. Các vấn đề khi có sự truy cập dữ liệu đồng thời. Trong [2], tác giả đề ra giải pháp khóa các node khi truy cập. Từ đó, đưa ra những điều chỉnh đảm bảo giải thuật không bị deadlock. 5. Việc chọn giá trị các thông số bảo mật như thế nào là hợp lý (m – kích thước của các tập dư thừa, redundancy set, s – kích thước của node). Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 16/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Lin và Candan đã xây dựng giải thuật oblivious traversal algorithm, và đã chứng minh trong [2], nếu tần suất truy cập của các node được phân bố đều (uniform distribution) thì giải thuật này đạt được user privac. Trong trường hợp tần suất các node không đều nhau (điều này thường gặp trong thực tế), Lin và Candan cũng nêu ra một số giải pháp trong [4]: dummy node access, replicate frequently accessed nodes, clique approach. Tuy nhiên, [4] cũng nêu ra các yếu điểm của từng giải pháp như sau: số lượng dummy node access, số lượng replicated nodes, kích thước redundancy set phải khá lớn. Từ đó, [4] xây dựng một giải pháp đạt được tính privacy trong trường hợp tần suất