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 truy cập không đều mà tránh được các hạn chế trên, được gọi là clustering node acceses into uniform chains. Hai giao thức extreme protocols Giải pháp của Lin và Candan trong [2] chỉ phù hợp cho mô hình UC-UP. Đồng thời, vẫn còn tồn tại một số giới hạn [3, 22]: - Chưa chỉ ra rõ ràng cách thức cập nhật danh sách các empty nodes, đồng thời cũng chưa chỉ ra được việc tận dụng lại các empty node. - Giải thuật này không hỗ trợ các thao tác insert, delete một cách trực tiếp. Đặc biệt là khi xảy ra trường hợp over-full và under-full đối với các node. - Redundancy set chỉ có một empty node nên không hỗ trợ được khi xảy ra over- full và under-full. [1] đề ra hai extreme protocol để giải quyết cho hai mô hình DC-UP và DC-UP-DP. Mô hình DC-UP DC + UP = Encryption + PIR protocol Trong trường hợp cần cập nhật CSDL, PIR protocol được thay bằng PIS protocol. Và để đảm bảo tính thực thi, PIR/PIS protocol được thay bằng RIR/RIS protocol. Mô hình DC-UP-DP Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 17/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh [1] đề xuất sử dụng K như là một tổ chức đáng tin cậy thứ 3 (trusted third-party) làm cầu nối giữa khách hàng và nhà cung cấp dịch vụ. Khi đó mô hình DC-UP-DP quay trở lại mô hình DC-UP đã đuợc giải quyết trước đó. Tuy nhiên, do thông tin là một vấn đề hết sức nhạy cảm, nên tìm được một tổ chức như thế này trong thực tế là một điều hết sức khó khăn. Oblivious operations on dynamic outsourced search trees N hư đã trình bày, giải thuật của Lin và Candan trong [2] không hỗ trợ các thao tác insert/delete và một số giới hạn của giải thuật. [3, 22] [3, 22] đã đề cách giải quyết các giới hạn của giải thuật của Lin và Candan. Đồng thời, cũng đề ra giải thuật hỗ trợ thao tác insert/delete. Tuy nhiên, giải thuật oblivious insert chỉ hỗ trợ B+-tree, mà chưa hỗ trợ các cấu trúc cây đặc biệt khác như: SH-trees, UB-trees, R+-trees, rd-trees [3, 22].Giải thuật oblivious delete có thể được mở rộng để hỗ trợ các cây đặc biệt này, tuy nhiên trong trường hợp cấu trúc cây chấp nhận node under-full thì giải thuật không thể áp dụng. Một điều chỉnh của giải thuật này có thể giải quyết tốt vấn đề under-full node tuy nhiên chỉ được áp dụng cho B+-tree. 1.3 Query Assurance Query Assurance đảm bảo kết quả truy vấn trả về từ server là đúng (correctness) và đầy đủ (completeness) và mới nhất (freshness). - Tính đúng là các kết quả trả về là chính xác được lấy từ CSDL hay được dẫn xuất từ đó (trung bình, tổng,…) mà không bị thay đổi. - Tính đủ đảm bảo kết quả truy vấn trả về là đầy đủ, không bị bỏ sót vì một nguyên nhân nào đó (do server thực hiện không hết câu truy vấn, hoặc không trả về đầy đủ tập kết quả, hay do thất lạc trên đường truyền). - Tính mới đảm bảo kết quả trả về từ server là dữ liệu mới nhất được cập nhật từ các DO. Tính mới thường được quan tâm trong trường hợp dữ liệu outsource có thể được thay đổi. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 18/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Einar Mykletun [7] đề ra một giải pháp để đảm bảo tính đúng cho các câu truy vấn dạng chỉ đọc (read-only) và không có tính toán gộp (như SUM, AVERAGE,…). Mỗi dòng dữ liệu (record) được lưu kèm theo chữ ký điện tử của dòng đó. Kết quả trả về kèm theo với chữ ký điện tử. Client kiểm tra nội dung dữ liệu với chữ ký kèm theo để xác nhận được tính đúng của dữ liệu. Tuy nhiên, do số lượng record trả về có thể lớn, vì vậy việc kiểm tra một số lượng lớn chữ ký điện tử cho từng dòng dẫn đến lãng phí thời gian và là một chi phí nặng nề cho client. Để giải quyết vấn đề này, [7] đề nghị mô hình Condensed-RSA. Theo đó, thay vì kiểm tra riêng lẻ từng chữ ký của từng record, client chỉ cần kiểm tra tất cả các record cùng lúc dựa trên chữ ký tổng hợp (condensed signature) do server trả về là có thể xác định được tính đúng của dữ liệu. [7, 14] cũng nêu ra một giải pháp khác nhằm đạt được tính đúng là sử dụng Merkle Hash Tree (MHT). MHT là cây mà các lá của nó là kết quả băm của dữ liệu của từng dòng tương ứng trong CSDL. Và đánh dấu node gốc bằng một chữ ký điện tử chuNn. N ếu kèm theo hai record ở hai biên kết quả, ta có thể chứng minh được kết quả trả về đầy đủ. Cấu trúc MHT đòi hỏi phải lưu trữ kèm theo một cấu trúc dữ liệu chuyên dùng để phục vụ cho query assurance. Mỗi cấu trúc này thường chỉ áp dụng cho một thuộc tính, như vậy, trong trường hợp CSDL có nhiều thuộc tính dùng để tìm (searchable attribute) đòi hỏi nhiều cấu trúc tương ứng, điều này có thể làm tăng phí tổn để lưu trữ tại server. Maithili N arasimha [10, 21] đã đề nghị một hướng tiếp cận mới dựa trên chuỗi chữ ký điện tử. Khi đó, trong chữ ký của một record có bao gồm nội dung của record liền trước nó (được sắp xếp theo một thuộc tính cho trước). N hư vậy, tạo thành một chuỗi liên tiếp nhau. Trong kết quả trả về, server trả kèm thêm hai record ở biên để có thể đảm bảo được tính đúng và đầy đủ. Hướng tiếp cận của [10, 21] không đòi hỏi phải tốn thêm nhiều không gian lưu trữ trên server. Mỗi dòng dữ liệu chỉ cần lưu thêm một chữ ký. Độ lớn của một chữ ký thông thường là 128 byte, đối với RSA (64 byte cho BGLS). Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 19/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Tuy nhiên, chi phí xây dựng, tạo các chữ ký và kiểm tra các chữ ký đôi khi cũng đáng kể, thường chậm hơn._. từ 100 – 1,000 lần so với việc băm (hashing). [15] đề xuất giải pháp dựa trên Embedded Merkle B-tree (EMB) cho phép đảm bảo tính đúng, đầy đủ và mới. Việc đảm bảo truy vấn chủ yếu dựa vào các phép băm. Từ đó, có thể giảm bớt thời gian để thực hiện tính toán chữ ký khi CSDL có thay đổi cũng như thời gian kiểm tra kết quả trả về. [15] đồng thời cũng là giải pháp đầu tiên giải quyết được đầy đủ các vấn đề của query assurance. Radu Sion [8] đưa ra một hướng tiếp cận mới cho phép đảm bảo tính đầy đủ đối với kết quả trả về từ một tập các câu truy vấn cần được thực hiện (batch of queries). Hướng tiếp cận này xây dựng một giao thức dựa trên việc mở rộng giao thức ringer. Dựa trên các challenge-token, gởi kèm theo, một cách ngẫu nhiên, xen kẽ với các câu truy vấn cần thực hiện, client đã biết trước kết quả của những câu truy vấn này và so sánh nó với kết quả trả về từ server. N ếu trùng khớp thì đảm bảo kết quả trả về từ server đầy đủ. 1.4 Nhận xét Phần trên của tài liệu đã trình bày một cách tổng quan những nghiên cứu và những kết quả hiện tại trong ODBS. Các kết quả này được tóm tắt theo dạng cây ở phần phụ lục. Qua đó, ta có thể rút ra một số nhận xét như sau: - Việc đảm bảo data confidentiality có thể dễ dàng đạt được bằng cách mã hóa dữ liệu trước khi thực hiện outsourced. - Việc đảm bảo user privacy/data privacy trên dữ liệu mã hóa đã có rất nhiều nghiên cứu trên các dạng dữ liệu khác nhau (XML, RDB) và đã đạt được những kết quả rất khả quan có thể ứng dụng được vào thực tế. - Việc đảm bảo query assurance trên ODB. Dù hiện nay có nhiều nghiên cứu nhằm đảm bảo query assurance tuy nhiên kết quả đạt được vẫn còn ở mức hạn chế so với các kết quả đạt được ở các lĩnh vực khác. Các nghiên cứu hiện nay đã có thể đáp ứng được tính đúng, tính đầy đủ và tính mới trong việc thực hiện các câu truy vấn. Tuy nhiên, hầu như các cách tiếp cận hiện tại vẫn chưa đề cập Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 20/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh trực tiếp đến vấn đề query assurance trên CSDL XML. Do tính chất đặc thù của mình, CSDL XML đòi hỏi cần phải có một số điều chỉnh để có thể đảm bảo query assurance. Qua những nội dung đã tìm hiểu trên, chúng tôi có đề ra một số hướng nghiên cứu tiếp theo như sau: 1. Các nỗ lực nghiên cứu nhằm xây dựng các giao thức cho phép che dấu người dùng trong việc khai thác thông tin (định danh, truy vấn cái gì, đuợc trả cái gì) đi ngược lại với nguyên tắc không thể phủ định trong các hệ thống. Đặc biệt là đối với các hệ thống thông tin mật, có tính nhạy cảm cao, có thể tạo cơ sở cho các tội phạm tin học có những hành động xấu. N ên chăng xây dựng một giao thức vừa đảm bảo tính riêng tư mà vẫn có thể, khi cần thiết, chứng thực được ai đã lấy thông tin gì? [1] 2. Hầu hết các nghiên cứu hiện nay chỉ tập trung giải quyết cho mô hình DC-UP. Mặc dù [1] đã trình bày một giao thức toàn diện (extreme protocol) hỗ trợ mô hình DC-UP-DP, nhưng giao thức này đòi hỏi phải có một người trung gian tin cậy (trusted third-party server) K để có thể chuyển đổi mô hình DC-UP-DP sang trở lại DP-UP. Việc nghiên cứu để loại bỏ K cũng là một vấn đế đáng được quan tâm. [1] 3. Các giải thuật hỗ trợ oblivious operation (insert/delete) vẫn còn một số điểm chưa hoàn thiện. Giải thuật insert chưa hỗ trợ cây đặc biệt như: SH-tree, UB- tree, R+-tree, kd-tree. Giải thuật delete ban đầu có thể hỗ trợ các cây này, tuy nhiên nếu cấu trúc cây cho phép các under-full node, thì phiên bản hiệu chỉnh của nó chỉ hỗ trợ B+-tree [3, 22]. Một vấn đề khác cần quan tâm là các giải thuật này được chứng minh là đảm báo tính privacy trong trường hợp tần suất truy cập các node là phân bố đều. Trong khi, ở thế giới thực, tần suất này là không đều và có sự chênh lệch khá lớn về tần suất giữa các node [4]. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 21/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 4. Chiến lược thực thi câu SQL trên dữ liệu mã hóa của Hacigümüş vẫn còn nhiều lỗ hổng bảo mật [6]. Việc nghiên cứu và khắc phục vấn đề này vẫn là một điều đáng được quan tâm. 5. Đảm bảo tính query assurance đối với kết quả trả về từ server mới chỉ dừng ở mức xử lý các câu truy vấn đơn giản [7, 8] và chỉ hỗ trợ mô hình DC-UP. Để có thể thực thi các câu truy vấn cập nhật dữ liệu và các câu truy vấn phức tạp hơn đòi hỏi phải công sức hơn nữa [8]. Trong các hướng nghiên cứu vừa nêu: (1) đã được nghiên cứu và phát triển rất nhiều, đã áp dụng tốt vào thực tế. (2) là một vấn đề rất khó khăn, hiện tại hầu hết các giao thức đều tránh mô hình này do tính phức tạp của nó. Xét thấy trong thời gian giới hạn, cũng như vẫn còn thiếu các kiến thức cần thiết về bảo mật và ODB; mặt khác vấn đề này hầu như không liên quan đến CSDL XML như đã nêu trong đề tài nên tài liệu này sẽ không đề cập đến. (3) (4) chỉ là những khía cạnh rất nhỏ và hầu như đã được giải quyết. (5), như đã trình bày, tuy đã có nhiều nghiên cứu nhưng kết quả đạt được vẫn còn nhiều hạn chế, mặt khác chưa có nghiên cứu nào về query assurance liên quan đến CSDL XML. N hư vậy, trong phạm vi của mình, tài liệu này trình bày một hướng tiếp cận nhằm giải quyết vấn đề query assurance trong CSDL XML. Phần tiếp theo của tài liệu sẽ trình bày chi tiết hơn về các kết quả liên quan trong lĩnh vực query assurance. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 22/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chương 2 CÁC NGHIÊN CỨU LIÊN QUAN 2.1 Khái niệm N hư đã trình bày, query assurance là một yêu cầu bảo mật cần được quan tâm trong hầu hết tất cả các mô hình của ODBS. Query assurance có thể được định nghĩa thông qua ba tính chất cần được thỏa mãn, bao gồm: tính đúng, tính đầy đủ và tính mới. Việc giải quyết triệt để các vấn đề của query assurance vẫn còn là một bài toán khó, đòi hỏi nhiều công sức hơn nữa. Hiện nay, hình thành các hướng tiếp cận khác nhau để giải quyết vấn đề này, bao gồm: - Sử dụng chữ ký điện tử (digital signature) để chứng thực từng dòng dữ liệu trả về từ server là đúng đắn, không bị thay đổi bởi server hay thay đổi trên đường truyền [7]. Phương pháp này chỉ có thể đảm bảo tính đúng mà không thể đảm bảo hai yêu cầu còn lại. Một số nghiên cứu gần đây đã mở rộng việc sử dụng chữ ký điện tử để thể giải quyết được tính đầy đủ [10, 21]. Tuy nhiên, nó vẫn chưa thể giải quyết được yêu cầu thứ ba (tính mới) của query assurance. - Sử dụng các cấu trúc dữ liệu chuyên biệt để giải quyết được bài toán về tính đúng và tính đầy đủ. Merkle Hash Tree (MHT) là một cấu trúc khá điển hình của khuynh hướng này [11, 14]. - Áp dụng một số kết quả trong bài toán tính toán phân bố [13] để giải quyết các yêu cầu đặt ra. Một kết quả của hướng này là sử dụng mô hình challenge- response để đảm bảo tính đầy đủ trong việc xử lý tập các câu truy vấn (batch of queries). Ưu điểm của hướng tiếp cận này là có thể xử lý được cho dạng câu truy vấn bất kỳ [8]. Tuy nhiên, hướng tiếp cận này, như đã trình bày, chỉ có thể Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 23/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh áp dụng cho việc xử lý tập các câu truy vấn do đó không phù hợp trong việc xử lý các câu truy vấn đơn lẻ. - Dựa vào tính đặc thù của dữ liệu, cũng như tính chuyên biệt của các câu truy vấn để phát triển một giao thức riêng giải quyết các yêu cầu của query assurance. Truy vấn dữ liệu đã mã hóa dựa vào các từ khóa (keyword) là một ví dụ [12]. Phần tiếp theo của tài liệu sẽ trình bày chi tiết hơn về các hướng tiếp cận này. 2.2 Hướng tiếp cận dùng chữ ký điện tử Việc sử dụng chữ ký điện tử để chứng minh tính đúng của dữ liệu là một giải pháp đang được sử dụng hiện nay [7]. Trong mô hình unified client model, do chỉ có duy nhất một Client đồng thời là DO, nên việc sử dụng chữ ký điện tử có thể được thay thế bằng hàm băm một chiều không thể đảo trong thời gian tuyến tính [8]. Việc chứng thực dữ liệu có thể được thực hiện ở nhiều cấp độ khác nhau, granularity. Có thể thực hiện chứng thực trên một bảng (toàn bộ quan hệ), một cột (thuộc tính của quan hệ) hay một dòng dữ liệu (record). Việc chứng thực ở cấp độ bảng đòi hỏi toàn bộ dữ liệu của bảng phải được trả về mới có thể thực hiện chứng thực được. Điều này là không thể khả thi, vì hầu hết các câu truy vấn dữ liệu chỉ trả về một phần (một số dòng) của bảng mà thôi. Điều này cũng xảy ra tương tự nếu thực hiện việc chứng thực ở cấp độ cột. Vì vậy, việc chứng thực ở cấp độ dòng có thể được xem là một chọn lựa tốt nhất1. N hư vậy, mỗi dòng, ngoài các dữ liệu của quan hệ, còn cần được lưu trữ thêm thông tin về chữ ký của dòng này. Việc thiết kế một giao thức chứng thực cần phải chú ý đến các yếu tố sau [7]: - Tính toán tại client: chi phí tính toán tại client để xác định tính đúng của dòng dữ liệu. - Băng thông đường truyền đến client. 1 Một giải pháp khác là sử dụng việc chứng thực ở cấp độ trường (field). Tuy nhiên, điều này sẽ dẫn đến sự quá tải về mặt lưu trữ cũng quá tải về tính toán trong việc chứng thực (do thời gian kiểm tra chữ kí điện tử cũng khá lớn). Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 24/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh - Tính toán tại server: bao gồm việc truy suất, trả về các thông tin dùng để kiểm tra trả về cho câu truy vấn. - Tính toán đối với Data Owner: chi phí tính toán các thông tin dùng để kiểm tra trước khi để lưu trữ vào CSDL. - Yêu cầu không gian lưu trữ trên server. Trong đó, ba yếu tố đầu là cần được chú ý nhiều hơn cả [7]. Tuy nhiên, đối với CSDL động (dynamic outsourced database) thì cũng cần thiết phải xem xét đến yếu tố thứ tư khi thực hiện cập nhật dữ liệu. Yếu tố thứ 5 hầu như không quá quan trọng do các thiết bị dung lượng lớn ngày càng rẻ. Mô hình chữ ký điện tử được chọn phổ biến hiện nay là RSA với chiều dài của chữ ký là 1024 bit (theo đánh giá thì RSA 1024 có thể an toàn trong vài thập kỷ tới). Tuy nhiên trong trường hợp số lượng dòng dữ liệu trả về lớn thì dẫn đến việc lãng phí về mặt bandwidth cũng như thời gian tính toán tại server để chứng thực dữ liệu. Một giải pháp được áp dụng là sử dụng mô hình Condensed-RSA. Condensed-RSA là một mô hình chữ ký điện tử bao gộp. Giả sử có tập t message {m1,…,mt} với tập chữ ký tương ứng {σ1,…,σ t), chữ ký Condensed-RSA được tính bởi: σ1,t = ∏i σi (mod n) , i = 1..t Khi đó việc kiểm chứng chữ ký σ1,t tương đương với việc kiểm chứng t chữa ký σi riêng lẻ. Một lợi điểm khác là kích thước của Condensed-RSA bằng với kích thước của một RSA chuNn. N hư vậy, thay vì trả về toàn bộ các chữ ký của từng dòng riêng lẻ, server chỉ cần tính toán chữ ký Condensed-RSA và trả về cho client để có thể thực hiện việc chứng thực dữ liệu. Maithili và G.Tsudik [10, 21] đưa ra một hướng tiếp cận mới đảm bảo tính an toàn và hiệu quả cho các câu truy vấn cơ sở mà không đòi hỏi thêm bất kỳ một cấu trúc dữ liệu phức tạp nào. Hướng tiếp cận này gọi là Digital Signature Aggregation and Chaining (DSAC). Để đạt được tính đúng, [10, 21] sử dụng lại cách tiếp cận đã đề cập Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 25/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh trong [7]. Do đó, phần tiếp theo của tài liệu chỉ trình bày biện pháp để đạt được tính đầy đủ. Tính đầy đủ Tính đầy đủ đạt được bằng cách xây dựng một mối liên kết bảo mật giữa các chữ ký của từng record, gọi là signature-chain. Chuỗi liên kết này đạt được bằng cách thay đổi cách tính chữ ký của từng record như sau: Sign(r) = h(h(r)||h(IPR1(r))|| … h(IPRl(r)))SK Trong đó, h() là hàm băm mã hóa (như SHA), IPRi là record liền kề trước đó dọc theo chiều i, l là số chiều có thể thực hiện truy vấn, SK là khóa riêng của data owner. Các record liền kề trước của mỗi record được xác định bằng cách sắp xếp quan hệ R theo các chiều có thể truy vấn, như hình sau: Hình 2.3. Sắp xếp quan hệ R theo các chiều truy vấn. Các record liền kề trước của R5 lần lược là R6, R2, R7. Khi đó, chữ ký của R5 được tính như sau: Sign(R5) = h(h(R5)||h(R6)||h(R2)||h(R7))SK. Cách thức chứng minh tính đầy đủ, về mặt nguyên tắc, là tương tự như phương pháp dùng trong AuthDS. N ghĩa là, để chứng minh một kết quả trả về của một câu truy vấn, server trả về chuỗi chữ ký hai record biên của kết quả cùng với các chuỗi chữ ký của hai record cận biên kết quả. Từ đó có thể chứng minh được kết quả trả về là đầy đủ. 2.3 Hướng tiếp cận sử dụng cấu trúc dữ liệu đặc biệt Một hướng tiếp cận khác nhằm thỏa mãn các yêu cầu của Query Assurance là sử dụng các cấu trúc dữ liệu đặc biệt lưu trữ các thông tin giúp cho việc đảm bảo tính đúng cũng như tính đầy đủ. Ý tưởng của hướng tiếp cận này được thể hiện như sau [14]: Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 26/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Hình 2.4. Mô hình chứng minh truy vấn. Chữ ký tổng hợp (Summary-signature) được tính toán đệ quy từ dưới lên theo phương pháp băm trên toàn bộ cây chỉ mục (B-tree) đối với toàn bộ các record trong một relation. Giá trị này được ký bằng sk0. Các truy vấn của user được publisher thực thi trả về kết quả cùng với một cấu trúc dữ liệu khác gọi là verification-object, được dùng để chứng minh là kết quả trả về là đúng và đầy đủ. Hướng tiếp cận này có một số đặc tính như sau [14]: - User chỉ cần tin cậy vào khóa pk0 của owner. Owner chỉ tính toán lại chữ ký tổng hợp khi thực hiện các cập nhật, thay đổi trên CSDL. Vì vậy khóa riêng sk0 hoàn toàn có thể được bảo vệ offline, điều này tránh được sự tấn công từ mạng. N goài ra, còn có thể sử dụng phần cứng để hiện thực khóa này. - User không cần thiết phải tin cậy các DO. Vì vậy, khi có sự cố với một publisher nào đó, thì hậu quả chỉ là mất đi dịch vụ cung cấp bởi publisher này. - Kích thước của verification-object là tuyến tính với kết quả trả về của câu truy vấn và tương quan logarit với kích thước của CSDL. - Verification-object đảm bảo rằng kết quả trả lời là chính xác và đầy đủ. - Chi phí tính toán chữ ký tổng hợp, verification-object (VO) và kiểm tra VO là chấp nhận được. Một cấu trúc điển hình của hướng tiếp cận này là Merkle Hash Tree (MHT) [11]. Cây MHT được xây dựng dựa trên tập giá trị x1, x2,…, xn được sắp thứ tự của một thuộc tính trong một quan hệ. Mỗi lá của cây có mối liên kết với một giá trị xi sẽ chứa giá trị Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 27/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh h(xi), trong đó, h() là hàm băm một chiều, chẳng hạn như MD5, SHA-1. Các node trong của cây sẽ chứa giá trị băm của hợp tất cả các giá trị của các node con của nó. Giá sử v có hai node con là v1 và v2, thì giá trị của v là h(v1||v2). Cuối cùng, giá trị tại node root sẽ được xác thực bởi chữ ký điện tử. Tính đúng (correctness) Để chứng minh tính đúng của kết quả truy vấn, server trả về VO chứa co-path của node trả về. co-path của một node là tập các node khác để từ đó có thể tính toán được giá trị của node root. Do nội dung của root đã được ký, nên so sánh với kết quả tính được, server có thể chứng minh được câu trả lời của mình là đúng. Ở cây MHT dưới đây, khi kết quả truy vấn node 5, server sẽ trả về thêm node h1 và h34. Từ hai node này ta có thể dễ dàng tính được root như hình vẽ sau. h1 h2 h3 h4 3 5 6 9 h34 = h(h3||h4)h12 = h(h1||h2) root = h(h12||h34) Hình 2.5. Binary Merkle Hash Tree. Trong kết quả trả về {5}, server trả kèm thêm {h1, h34, sign(root)}. Như vậy, client có thể tính được h12’ = h(h1||h{5}); root’ = h(h12’||h34). So sánh root’ với chữ ký của root, client có để đảm bảo kết quả trả về là đúng. Tính đầy đủ Trước tiên ta xét trường hợp server trả lời câu truy vấn là không có một reocrd nào trong CSDL thỏa điều kiện truy vấn. Khi đó, server phải chứng minh được điều này, gọi là các empty proofs. Điều này có thể thực hiện bằng cách trả về co-path của hai node kề nhau sao cho khoảng trị cần truy vấn nằm trong khoảng giá trị của các node này. Tính đầy đủ của câu trả lời đạt được bằng cách gởi kèm theo các empty proofs cho các node lá lân cận hai node biên nằm trong kết quả trả về của câu truy vấn. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 28/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Một giới hạn lớn của AuthDS là đòi hỏi phải bảo trì một cấu trúc dữ liệu phức tạp bên cạnh dữ liệu thực sự. Cấu trúc này cần phải được tính toán đầy đủ trước khi đưa lên server. Mỗi thay đổi cập nhật dữ liệu đòi hỏi phải tốn chi phí không nhỏ để cập nhật lại các số liệu trong cấu trúc [8, 10, 21]. Bên cạnh đó, để có thể đảm bảo tính đúng cũng như đầy đủ của cây truy vấn theo khoảng (range-query) đòi hỏi phải xây dựng một cấu trúc cho từng thuộc tính, theo từng trật tự sắp xếp (sort-order) [10, 21]. 2.4 Hướng tiếp cận Challenge – Response. Radu Sion [8] đã đưa ra một giao thức để đảm bảo tính đúng và tính đầy đủ của các câu truy vấn dạng bất kỳ dựa trên việc mở rộng giao thức ringer trong tính toán phân bố (distributed computation). Giao thức ringer trong tính toán phân bố được đưa ra để tránh gian lận trong việc tính toán các bài toán con. Giao thức ringer có nhiều biến thể như basic ringer, bogus ringer và hybrid ringer (magic ringer). Xét bài toán sau: tìm ra chuỗi text ban đầu từ chuỗi text mã hóa bằng giải thuật DES. Các trạm làm việc (working station) sẽ phát sinh ra các chuỗi bằng phương pháp tổ hợp, sau đó áp dụng giải thuật DES trên chuỗi này, nếu kết quả trùng khớp với chuỗi mã hóa thì chuỗi phát sinh chính là chuỗi text ban đầu cần tìm. Ý tưởng của basic ringer trong [13] có thể được tóm tắt như sau: - supervisor chọn ra một giá trị ngẫu nhiên xi trong miền trị Di mà trạm làm việc i tính toán trên nó, sau đó tính yi = DES(xi). Sau đó, supervisor gởi cho trạm i giá trị yi và y. Trong đó, y là chuỗi mã hóa cần giải mã. - Trạm i nhận được miền trị Di và thực hiện tính toán, nếu việc tính toán là hoàn chỉnh (complete) thì chắc chắn trạm i sẽ tìm ra được giá trị của xi hay x (y = DES(x)) . Khi trả kết quả về cho supervisor, là xi (có thể có cả x). Khi đó supervisor có thể biết được thực sự trạm i đã thực hiện đầy đủ công việc. Để hiện thực, [8] đưa ra một cách tổ chức dữ liệu như sau. Giả sử S là dữ liệu outsource. S được phân thành nhiều đoạn Si, mỗi Si sẽ được xác định bởi một hàm băm dùng để đảm bảo dữ liệu là chính xác, không bị thay đổi. Giá trị này gọi là Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 29/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh “identity-hash”, được sử dụng để chứng thực các câu truy vấn “identity query”, là những câu truy vấn trả về toàn bộ dữ liệu trong Si. Quá trình thực thi các câu truy vấn như sau: - Trong tập các query Q {Q1, Q2, Q3, .. Qa} cần thực thi, querier sẽ chèn vào câu query Qx tại một vị trí bất kỳ, querier đã biết trước kết quả trả về của Qx. Đồng thời, querier tính toán một challenge token bằng {H(ε||ρ(Qx)), ε}. Trong đó, H() là hàm mã hóa một chiều bất khả đảo (non-invertible one-way hashing function); ε : là một giá trị duy nhất theo thời gian (timestamp) để đảm bảo challenge token là duy nhất; ρ(Qx) : là kết quả trả về đã được biết trước bởi querier. - N hiệm vụ của server là thực thi các câu query và xác định được giá trị x bằng cách áp dụng hàm H() cho các kết quả. Và gởi kèm x về cùng với kết quả của các truy vấn. N ếu chỉ sử dụng một challenge token thì có thể dẫn đến trường hợp server sau khi đã tìm được challenge token rồi thì ngưng thực hiện các câu truy vấn khác (hoặc thực hiện không đầy đủ). [8] cũng đã trình bày một số phương pháp để khắc phục vấn đề. Đầu tiên là có thể sử dụng nhiều challenge token thay vì một. Tuy nhiên về mặt hình thức thì cách thức này thực ra vẫn không thể giải quyết được vấn đề căn bản. N ghĩa là, vẫn có trường hợp server sau khi nhận diện được đầy đủ các challenge token thì ngưng thực hiện các query còn lại. Đồng thời việc phát sinh nhiều challenge token thật sự là một gánh nặng tính toán cho các thin-client (querier) như các thiết bị di động (mobile client). Một giải pháp khác được đề ra là sử dụng các fake token. Fake token là một challenge token giả, nghĩa là querier phát sinh ra ngẫu nhiên ra một challenge token mà không cần quan tâm đến kết quả trả về từ server. Trong tập các challenge token được gởi đến server sẽ bao gồm r challenge token thực sự và f token giả. Hai tham số r, f là có thể thay đổi theo từng tập truy vấn. Vì vậy, server không thể nào có thể xác định được toàn bộ số challenge token được gởi đến. Do đó, bắt buộc Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 30/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh server phải thực hiện đầy đủ các câu query để có thể tìm ra được các challenge token thật sự. N hững phương pháp trên chỉ tập trung cho giải quyết các câu truy vấn đọc dữ liệu (select query) chứ chưa giải quyết vấn đề cho các câu truy vấn cập nhật/thêm mới dữ liệu (update/insert query). Việc cập nhật dữ liệu thực hiện bằng cách đọc toàn bộ đoạn dữ liệu có chứa dòng cần update (hay sẽ chứa hàng insert). Sau đó thực hiện cập nhật dữ liệu, tính toán lại “identity hash” rồi cập nhật trở lại server. Tuy nhiên, việc xử lý tình huống cập nhật dữ liệu vẫn chỉ là bước khởi đầu [8]. 2.5 Hướng tiếp cận dựa vào đặc thù của bài toán Dễ dàng nhận ra rằng, để có thể xây dựng được một giao thức đảm bảo các yêu cầu của Query Assurance trong trường hợp tổng quát là một công việc cực kỳ khó khăn. Do vậy, một hướng tiếp cận mới để giải quyết bài toán này một cách tương đối hoàn chỉnh là đi vào giải quyết nó trong từng trường hợp dữ liệu, truy vấn cụ thể.. Radu Sion, Bogdan Carbunar [12] trình bày một giao thức dùng để truy vấn các dữ liệu mã hóa dựa trên từ khóa có thể đảm bảo các yêu cầu privacy cũng như query assurance. Các tài liệu được lưu thành những vùng riêng lẻ (file), mỗi tài liệu sẽ có một số lượng từ khóa (keyword) nhất định. Số các từ khóa cho mỗi tài liệu đã được liệt kê trước khi được đưa lên server. Bài toán đặt ra là có thể thực hiện truy vấn tài liệu dựa và một hay nhiều từ khóa cho trước. Mỗi tài liệu được gán với một con số định danh di ngẫu nhiên, duy nhất, không liên quan đến nội dung của tài liệu đó. Do số lượng từ khóa đã được xác định trước, ứng với mỗi từ khóa này, xây dựng một tập các định danh của tài liệu có chứa từ khóa, gọi là KDS (keyword document sets). Các KDS có thể được đặt tại chính các querier. Hay có thể được đặt ở server. Lúc này, các KDS cần được mã hóa và được chứng thực. Mỗi KDS có thể được mã hóa bởi một khóa khác nhau. Khóa này có thể được tính như sau: Keyi = H(key || ki), trong đó: H() là hàm băm một chiều; key : là khóa dùng chung; ki là từ khóa tương ứng với KDSi. Để tránh trường hợp server có thể loại bỏ Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 31/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh một entry trong KDS, mỗi KDS cần được bổ sung thêm một giá trị dùng để kiểm tra, giá trị này được tính toán như sau: Hcheck = H(d4||H(d3||H(d2||H(d1||0)))), với giả thiết KDS = {d4, d3, d2, d1}. Một phương thức để lưu trữ các KDS là dưới dạng ma trận, cột là các định danh của tất cả tài liệu, dòng là tất cả các từ khóa, mỗi cell trong ma trận sẽ nhận giá trị 0 hay 1 tùy vào tài liệu có chứa từ khóa đó hay không. Ma trận này, gọi là ma trận C, sẽ qua một phép biến đổi để trở thành C’ như sau: C’i,j = last_bit(F(ki , Rj , Cij)) trong đó: F là hàm bitwise pseudo-random function, Rj là một số ngẫu nhiên phát sinh bởi hàm sinh số ngẫu nhiên G với một random seed R cố định. Câu truy vấn query = {k1, k2,…, kq} được thực hiện bằng cách gởi yêu cầu đến server để lấy về các hàng tương ứng với các từ khóa. Querier lần lượt phát sinh lại các giá trị Rj , và thực hiện tính lại ma trận Cij như sau: nếu last_bit(F(ki , Rj ,0)) = Cij thì Cij = 0, ngược lại Cij = 1. Sau khi tính lại được ma trận C, querier hoàn toàn có thể xác định chính xác có danh sách các định danh tài liệu cần tìm. Từ các định danh, querier có thể yêu cầu server trả về đúng các tài liệu yêu cầu. Do querier biết được chính xác danh sách các định danh tài liệu cần lấy, nên, một cách hoàn toàn tự nhiên, có thể kiểm tra được tính đầy đủ của kết quả trả về. Để đảm bảo tính privacy, có thể sử dụng các PIR-like protocol. 2.6 Bảo đảm truy vấn cho dữ liệu dạng cây Một hướng tiếp cận tiếp theo dựa trên kỹ thuật của Lin và Candan [2] trong việc đảm bảo tính riêng tư . [16] mở rộng phương pháp này cho phép đảm bảo ba yêu cầu của query assurance, với nội dung cơ bản như sau. - Để đảm bảo tính đúng, mỗi record đều có chữ ký cho riêng nó (RSA). Trong trường hợp cần so sánh tính đúng của nhiều record, có thể sử dụng mô hình Condensed RSA. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 32/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh - Tính đủ được đảm bảo một cách tự nhiên, do querier yêu cầu một số lượng nhất định node. Khi đó, căn cứ vào số lượng node yêu cầu và số lượng node do server trả về, hoàn toàn có thể thỏa mãn được yêu cầu này. N goài ra, để đảm bảo đây chính là những node yêu cầu, trong dữ liệu của mã hóa của mỗi node, ta lưu trữ định danh (nodeID) của chính node đó. Do tập các định danh node yêu cầu là biết được, so sánh với các định danh của các node do server trả về để có thể chứng minh được đây thực sự là các node mong muốn. - Tính mới được thỏa mãn bằng cách bằng cách bổ sung vào một số thông tin như sau: o Mỗi node chứa thêm một giá trị thời gian (timestamp) để cho biết thời gian cập nhật của node này. o Node cha lưu toàn bộ giá trị thời gian (timestamp) của các node con. o Giá trị timestamp của node gốc là phổ biến cho tất cả các querier. N hư vậy, khi quá trình duyệt đi từ node gốc xuống các node con, với giá trị timestamp đã biết trước, querier hoàn toàn có thể chứng thực nội dung của node gốc là mới. Căn cứ giá trị timestamp của các node con được lưu trữ tại node gốc, querier cũng xác định được tính mới của các node con này. Và cứ như vậy, lan truyền tới node lá để có thể chứng minh tính mới của node này. Nhận xét Phương pháp tiếp cận của [16] vừa đảm bảo được tính riêng tư (user privacy và data privacy) do tận dụng phương thức redundancy data access và node swapping của Lin và Candan [2, 4], và có thể đảm bảo được query assurance. Tuy nhiên hướng tiếp cận này chỉ phù hợp cho các cấu trúc dữ liệu dạng cây tìm kiếm (search tree) như B-Tree, B+Tree, R-Tree,…, các cấu trúc này được dùng phổ biến để sử dụng làm chỉ mục (index) cho các dữ liệu khác. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 33/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 2.7 Nhận xét N goại trừ trường hợp ứng dụng cho bài toán cụ thể được trình bày ở mục 2.5, các phương pháp khác, về mặt bản chất, đều áp dụng chữ ký điện tử hay ứng dụng tính chất không thể đảo trong khoảng thời gian tuyến tính của các hàm băm (secure hash) để chứng minh tính đúng cũng như tính đầy đủ của kết quả truy vấn. Hướng tiếp cận của Maithili, G.Tsudik [10, 21] và Prem Devanbu [14] cho phép chứng minh được chính xác kết quả trả về là đúng và đầy đủ. Tuy nhiên, hiện tại, các giao thức này vẫn chỉ có thể giải quyết cho các câu truy vấn chỉ đọc đơn giản không có các hàm bao gộp (như SUM, AVERAGE,…). Một khuyết điểm của phương pháp này là phụ thuộc vào dạng thức của câu truy vấn. Đòi hỏi phải phân tích câu truy vấn thành từng phần riêng lẻ để có nhưng tác vụ thích hợp. Hướng tiếp cận của Radu [8] có thể áp dụng cho tất cả các loại truy vấn, kể cả việc sử dụng các hàm gộp mà [10, 14, 21] chưa giải quyết được. Ưu điểm chính của phương pháp này không cần phân tích cú pháp của các câu truy vấn. Từ đó, có thể triển khai dễ dàng hơn. Tuy nhiên, hướng tiếp cận này vẫn còn một số điều cần xem xét như sau. - Chỉ áp dụng cho tập các câu truy vấn, chưa giải quyết cho trường hợp thực thi từng câu truy vấn riêng lẻ, vốn được sử dụng khá nhiều trong thực tế. Để giải quyết vấn đề này có thể sử dụng các hướng như sau: (1) sử dụng các fake- query kèm theo để biến câu truy vấn đơn thành tập các câu truy vấn. Tuy nhiên, cách này có thể làm quá tải server, giảm hiệu năng của toàn hệ thống do phải thực hiện các fake-query quá nhiều so với các truy vấn thực sự. (2) các câu query riêng lẻ được tập trung lại tại một trust-server và gửi đến server dưới dạng tập các câu truy vấn theo đúng tinh thần của giải pháp. Phương thức này hầu như không khả thi do thời gian trễ của câu query trong thời gian chờ đợi là không thể chấp nhận được. (3) là kết hợp của (1) và (2). - Chưa chứng minh triệt để kết quả trả về là đầy đủ. Xác suất để server không thực thi hoặc thực thi không hoàn chỉnh đối với câu query cuối cùng là 33% Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 34/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh [8]. Đây là một xác suất khá cao. Điều này phần nào làm giảm bớt tính tin cậy của giải pháp. Các hướng tiếp cận trên đều được thực hiện cho các dữ liệu dạng quan hệ (relational database). Do đó, để có thể áp dụng được trong CSDL XML cần phải có một số thay đổi nhất định. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 35/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chương 3 DỮ LIỆU XML XML là một dạng dữ liệu bán cấu trúc (semistructured data), dạng cây (tree- structured). Đơn vị lưu trữ thông tin của XML là các node và attribute. Các node và attribute phân biệt thông qua tên và tầm vực của chúng (chiều sâu của cây, node cha). Dữ liệu XML là dạng văn bản đọc._.s of outsourced XML databases, we could create an algorithm to transform an XML database to a traditional relational database in which security problems are quite well-solved. Alternatively, we need a special method dealing with security issues in outsourced XML databases. Hence we should first answer the question “how do we store XML data?”. The answer strongly influences to the way we deal with this problem. Table based. Each XML document has a schema, we call it schema tree that defines the relation between nodes and their attributes (parent-child relationship). A schema tree consists of two node types: element node and attribute node. Hereafter, we name element node as t- node and attribute node as a-node. With the schema tree, we could easily change an XML document into relational tables as follows. - Label all t-nodes with integers incrementally so that their labels are unique in the whole XML document. - For each t-node, create a table named by suffixing t-node’s name with its label. The table should have one more column, called ID, that is its primary key. - If a t-node has a parent, we append a column named PNodeID to point to its parent’s corresponding table. - Finally, for each child node a-node, append to the table a column named as the a-node’s name. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 87/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Figure 4. Tranform an XML document into tables. Figure 4 illustrates a sample. From a given XML document (A), we extract its schema tree (B). After labeling, we transform it into relational tables (C). Once an XML document is transformed into traditional tables, we could apply prior work to achieve query authenticating. However, an XML database schema is changed easily. That causes the table schema to change also, and sometime forces the data to be re-outsourced. Node based. XML document is structured as a tree with t-nodes and a-nodes. We could save t-nodes and a-nodes as tuples in a single table. Each node has enough information to reconstruct the XML text. We propose the following schemas for t-node and a-node. t-node(nodeid, xtype, datatype, nameid, pnodeid, lmaid, value) a-node(nodeid, xtype, datatype, nameid, pnodeid, sibid, value) Where: - Xtype is used to distinguish t-node and a-node among the records. - Datatype determines type of the value (text, numeric, date time, etc.). - NameID is the node’s unique identity (using the labeling in the same manner of table based). - PnodeID refers to parent node’s tuple. - lmaID refers to the left-most attribute of the node. - sibID refers to the right sibling of the attribute. - Value is the value of the node/attribute. For security reasons, this information is serialized into an encrypted binary string before outsourcing. Storing XML documents under such a node-based format conforms to tree-structured data. Changing an XML document schema does not dramatically affect the outsourced data because it just appends the modified node to the database. However, each element is stored by a lot of records for the tag name and attributes. Thus outsourced database storage cost may become overhead. Furthermore, it’s difficult to utilize the existing indices. This problem extremely affects the overall performance. 5. Query Assurance An important factor for a feasible solution to query assurance of outsourced XML databases depends on index structures, which are employed to manage the storage and retrieval of the data. By embedding extra information into this structure, we could achieve query assurance. Most related work about XML indexing could be found in [17, 18]. However, these structures are not suitable for query authenticity purpose because we expect an ordered list of all XML elements (both xml-tags and xml-attributes) for giving completeness proof (cf. section 2.2). Additionally, because of the nature of XML query languages (e.g, XPath, XQuery), most of the queries require join-operations that take an expensive cost for proving the query completeness. A simple way of minimizing these costs is to sort XML elements by their parent. As mentioned in section 2.2, in order to obtain an effective proof for the completeness, we want to sort all XML elements by two criteria: (path, value) and (path, parent, value), where path is the path from the tree’s root to a given node. However, existing data structure could not help this. In the next sections, we will introduce a novel index structure, called N ested Merkle B+-Tree, to facilitate the storage and retrieval as well as to ensure the query correctness, completeness and freshness for outsourced XML databases. 5.1. Nested B+-Tree As mentioned above, we desire an index structure that can sort all elements by their corresponding combinations (path, value) and (path, parent, value); where path is the path from the root to a given node. Here, we list out all possible paths in the XML document, then we associate each path with an unique integer. We call this number nameid. To construct our desired structure, we first employ a B+-Tree structure with the search key is nameid (equivalent to path). We name it as NameTree. At each leaves’ entry of NameTree, instead of record’s links, we store two references to two new B+-Trees having value and (parent, value) as their search keys, respectively. We call these trees ValueTree and ParentTree (see figure 4). At all leaves of ValueTree and ParentTree, we store links to a-node or t-node records (hereafter, refered to as data records). N ote, if many data records have the same key then they are in a same entry. The B+-Tree can solve this situation by employing an additional structure called bucket. A bucket stores references to all same data records. Finally, an entry of the leaf points to this bucket. Combining these trees, we have our desired structure named N ested B+-Tree (N BT). Let us see how this structure fulfills our needs. With NameTree, we have data records sorted by nameid (or path). ValueTree sorts data records by value. Because ValueTree is at leaf of NameTree, we have data records sorted by (nameid, value). In the same manner, data Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 88/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh records are sorted by (nameid, parent, value) with ParentTree. Figure 5. Nested B+-Tree. 5.2. Nested Merkle B+-Tree Basing on the idea of the Mekle Hash Tree, we attach some information to N BT for giving proof of query assurance. Each node of N BT has some extra hashes of its children. The hash values are calculated as follows. a-node record : Ha-node = h(nodeid||xtype||…||value) (4) t-node record : Ht-node = h(h(nodeid||xtype||…||value)||∪i Hattr) (5) Leaf of ValueTree and ParentTree: HL = h(∪i Hdata-record) (6) Internal node: HI = h(∪i Hchild-node) (7) Leaf node of NameTree: HL-N = h(Hvtree || Hptree) (8) Root node of NameTree: HR = h(ε || ∪i Hchild-node) (9) Where, Hattr is hash value of an a-node of a given t-node. Hdata-record is either Ha-node or Ht-node that associated to the link. Hchild-node is one of HL, HI or HL-N . Hptree and Hvtree are hash values of the roots of corresponding ParentTree and ValueTree. ε denotes a timestamp value and h() is a one- way non-invertible hash function (e.g, SHA-1, MD5). Additionally, we sign the root of NameTree by private- key of a digital signature scheme (such as RSA, DSA). The corresponding public key and timestamp ε are broadcasted to all clients. 5.3. Providing query assurance The method of achieving query assurance is the same as that described in section 2.2. Data records are sorted in leaves of ValueTree and ParentTree. Let us see how a query is authenticated with this structure. Correctness and Completeness. Assume that the result set consists of leaf entries in ValueTree that contain links to records fallen into a given range (range query). As mentioned in section 2.2, two additional boundary records are also included in the result set. These entries occupy some adjacent leaves, say {Li, Li+1,…, Lj}. The server returns data records and hash values of not-in-result entries in Li and Lj so that clients could recompute hash values of these leaves. Similarly, the series {Li, Li+1,…, Lj} occupies entries in some internal nodes, say {Ix, Ix+1,…, Iz}. In addition, hash values of the remained entries in internal nodes are returned. Recursively, the server returns the root with its signature and timestamp. These not-in-result entries (in both leaves and internal nodes) are called co-path. Actual results and co-path are packaged in a structure called VO (verification object) and sent to clients. The clients will recalculate hash value of the root, then verify it with the signature to assure both correctness and completeness of the result set. More detail of co-path and VO could be found in [11, 14]. Freshness. Along with the result set, the server returns timestamp value of the root. After verifying the root’s signature. clients compare returned timestamp to the well-known timestamp broadcasted by the data owner before. If two values are equal, clients are guaranteed about freshness of the result. 5.4. Select operation We have seen how to use N MB+-Tree to achieve query authenticity for the simplest situation that returns a single and contiguous record set. It is just a single step among many ones that have to be done. To answer a query, the server has to perform some other tasks in a specific order called execution plan. N ext, let’s see some examples of XPath to find out a general method for query processing. Figure 6. An example of labeled XML schema tree. As illustrated in figure 6, the round rectangular nodes stand for elements and the sharp corner ones are attributes. The numbers next to node are their nameid we mentioned above. Example 1. The first question is “Find out all sold items named ‘TV’?”. The corresponding query in XPath should be expressed like /Customer/Order/Item[@name= Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 89/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh ”TV”]. The server scans NameTree with nameid = 13 to get the ValueTree. Then, the server scans on the found ValueTree with value = ‘TV’ to list out all satisfied attributes name_13 and builds a VO for authenticity. With the pnodeid field in each found name_13, the server reads and appends these Item_8 into the VO. Because there is only one Item_8 for each name_13, the server needs not to provide any information to prove query assurance. For each Item_8, the server returns two remain attributes. These steps could be rewritten in a semi-structured language as follows. STEP#1 IndexMethod : Vtree, nameID=13 Condition : equal to [TV] Result level : not included Retrieval : node only StepValue : PNODEID [For each matched item, perform] STEP#2 IndexMethod :DirectIDAccess, id=ParentStepValue Result level : 1 Retrieval : node and all its attributes Example 2. The second example deals with a question “List out all items bought by Marry?” and its query is /Customer[@name=”Marry”]/Order/Item. The server does some similar jobs to obtain satisfied Customer_1 records. For each Customer_1, the server scans on ParentTree3 with pnodeID equals id of Customer_1. The ParentTree3 is the ParentTree located in the leaf entry that nameid = 3 of the NameTree. A VO is built to give proof of query assurance for these records. In the same manner, the server returns expected Item_8 records and their VOs. The execution plan is described as follows. STEP#1 IndexMethod : Vtree, nameID=4 Condition : equal to [Marry] Result level : not included Retrieval : node only StepValue : PNODEID [For each matched item, perform] STEP#2 IndexMethod :DirectIDAccess, value=ParentStepValue Result level : not included Retrieval : node only StepValue : ID [For each matched item, perform] STEP#3 IndexMethod :Ptree,nameID=3, pid=ParentStepValue Result level : not included Retrieval : node only StepValue : ID [For each matched items, perform] STEP#4 IndexMethod :Ptree,nameID=8, pid=ParentStepValue Result level : 1 Retrieval : node and all its attributes Unifying VOs. For each matched Customer_1 record, the server returns an Order_3 record set that have pnodeid point to the Customer_1 record and, similarly, an Item_8 record set for each found Order_3. Therefore, the server returns a lot of record sets and each of them requires a VO. Thus, the number of VOs is linear with the product of matched records in Customer_1 and Order_3. This could dominate communication and computation cost at clients. Hence, instead of building multiple VOs, the server only builds a single VO for all returned record sets by making a slight modification on the co-path generating algorithm. Thus, the clients only have to carry out one verification for all returned record sets. The above shows the way we deal with simple XPath queries. However, by applying this idea, we could answer more complex questions, but we do not detail it here due to space limitation. 5.5. Update operations Since the database could be changed even if it has been outsourced, feasible solutions should have an acceptable cost for update operations. Update operations refer to insertion, update, and deletion. Data owners could make changes to a local copy of the database then outsource it again. Here, we refer to another scheme that data owners do not have any local copy and/or re-outsourcing is impossible. The most important issue of an update operation is to recalculate embeded security information. In this scheme, we should recalculate the data nodes relevant and their associated index nodes. The basic idea for this protocol is shown in figure 7. In general, an update could be treated as a series of delete and insert operations. We summarize them as follows. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 90/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Figure 7. Protocol to perform update operation. Insertion. To insert a new element into database, the owner first serializes it into t-node and a-node. Thesenodes are sent to server to insert into the database and update the index structure. This will change the hash value of a leaf, then the change is propagated to its ancestors (up to the root). The server recalculates these hash values and returns the new hash of the root to the data owner. The data owner generates a new timestamp value ε , combines it with the hash value then signs on it with the private key. The signature and ε are sent to the server to update the root. Finally, the owner announces the new timestamp to all clients. If many nodes are inserted at the same time, batch operation could be considered to minimize the root resigning round. Deletion. Performing a delete is quite similar to an insert operation. The only difference is the first round of the protocol. Instead of inserting, server has to locate deleted node in the index tree then removes it from the index and database. The remains are the same as that of the insertion process. 6. Analysis and Experiments Until now, no research work about query assurance of outsourced XML databases has been carried out. Hence, we will theoretically analyze our proposed solution with respect to storage cost and VO size. The table 1 summarizes the notions used in this section. n Total number of data item (element and attribute) s N umber item of result set. f fanout parameter N MB+-Tree. hTmin|max Min/max height of a tree T. LTmin|max Min/max number of leaves in a tree T. N Tmin|max Min/max of total nodes in a tree T. |sign| Size of a hash value. (20 bytes for SHA-1) Table 1. Formula notions. The experiments are conducted on a P4-2.8GHz Windows XP SP-2 with 512MB of memory. Benchmarking program is written in VB.N ET 2005, .N ET Framework 2.0. We employ the managed Rijndael and RSA-1024 for data encryption and digital signature. We use Microsoft SQL Server 2005 Express Edition for storing the encrypted database. Moreover, we use a sample 69,846 items dataset [19], representing about world geographic database integrated from the CIA World Factbook, for all the tests. Storage cost. Storage cost here is refered to as the cost for additional security information. In our scheme, this is the cost of storing the N MB+-Tree. The N MB+-Tree consists of one NameTree, several ValueTrees and ParentTrees. Because the number of nameid is small compared to that of elements, the storage cost for ValueTrees and ParentTrees dominates the overall storage cost. We, however, could not formulate the number of ValueTrees and ParentTrees in a database because it depends on the XML document structure. Therefore, we suppose that only one type of node in the XML document, hence there is only one nameid in the whole database. This means we have a one-element NameTree, one ValueTree and one ParentTree. Thus the storage cost is cost of storing n-elements ValueTree and ParentTree. In addition, we assume that these nodes are distinguished by their values. We could easily find that the minimal and maximal number of leaves is calculated as formula (10). Here we can get the minimum when all leaves are full (f entries) and the maximum when all leaves are half-full (f/2 entries). ⎥⎥ ⎤⎢⎢ ⎡=⎥⎥ ⎤⎢⎢ ⎡= f nL f nL VTreeVTree 2, maxmin (10) Then we have: ⎡ ⎤ 1log minmin += VTreefVTree Lh (11) 1log max 2 max +⎥⎥ ⎤⎢⎢ ⎡= VTreefVTree Lh (12) 1 11 11 1 minmin min + ⎥⎥ ⎥⎥ ⎥ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎡ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎝ ⎛ − − = − f fLN h VTree (13) Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 91/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 121 21 1 maxmax max + ⎥⎥ ⎥⎥ ⎥ ⎥ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎢ ⎡ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛− = − f f LN h VTree (14) Hence, the overall storage cost is calculated as follows (note that, proofs of formulas (11) to (14) are shown in appendix). ⎪⎩ ⎪⎨ ⎧ ++= ++= PTreeVTreeNTreestorage PTreeVTreeNTreestorage NNNC NNNC maxmaxmax minminmin (15) In fact, there are many elements that may have the same (nameid, value) or (nameid, parentID, value). These elements will occupy only one entry in the index tree. So , before applying these formulas, we should determine a value n’ that is the number of distinct elements by mentioned conditions. Then, we replace any occurance of n in formular (10) by n’. The actual storage cost is achieved by counting number of index nodes in the database. Figure 8 and table 2 show detailed information about the storage cost for our sample dataset. Figure 8. Number of actual nodes compared to min-, max-one. VO size. Similarly, we only concern about extra information returned to clients to give query authenticity. The formular (16) is used to calculated the size of a single VO. CVO =|sign|∑ CVOi , i = 1,hNMBTree (16) Number of nodes at a depth Additional elements in co-path h ⎥⎥ ⎤⎢⎢ ⎡ += f sLh 2 CVOh = f.Lh - s + 2 h-1 Lh-1 = ⎡Lh/f⎤ CVOh-1 = f.Lh-1 – Lh … … … h-i Lh-i = ⎡Lh-i+1/f⎤ C VO h-i = f.Lh-i – Lh- i+1 Overall cost. The overall cost includes I/O cost, communication cost, CPU cost at both server and client. Our experiments are performed in a local environment therefore, communication cost is omitted. But this is directly proportional with the VO size. We simulate the overall cost by measuring query processing time since a query is submitted to server until a completed XML result text is reconstructed from the returned data. To know the I/O cost, for each query, we measure number of nodes that have been loaded from the database into memory during the query processing process. Figure 9 describes six phases of the query processing process. The two gray phases, Parse and Plan, are ignored in our benchmarking program. To make a comparision, we import a same XML document into SQL Server and execute the same query on it. Experimental results are shown in the next paragraphes. Experimental results. Table 2 presents the storage cost in our tests. The first line, Distinct items, is the number of value-distinguished items, and the fourth one is that of items distinguished by combinations (parentID, value). The Min Nodes and Max Nodes are theoretic nodes calculated by formula (13) and (14). In table 3, we show the execution time and I/O cost over the result size and database size. In which, result size is number of items in the result set. Executing time is the overall time, including time for fetching data from the database into memory (fetch data); time for building VO (build VO); time for verifying the VO at client (verify VO); and time for reconstructing XML text (generate XML). SQL Time is the executing time SQL Server used to execute the query. IO Cost is number of nodes being loaded into memory during the process. Moreover, table 4 and figure 10 show the increase percentage of the four mentioned criteria Result Size, Executing Time, SQL Time and IO cost. 7. Conclusions and Future Work This work explored the problem of query assurance of query replies in outsourced database. In particular, we developed a novel index structure called N ested Merkle B+-Tree by which we could completely achieve query assurance for dynamic outsourced XML data, ensuring the query correctness, completeness and freshness. Our proposed solution is among the first efforts in this area. We also implemented a benchmarking program for experiments and carried out evaluations with real datasets to show the efficiency of the proposed solution. In the future, we will futher investigate other complex forms of XPath/XQuery, especially aggregated function ones. Moreover, another approach could be taken in mind is to employ multi-dimensional access methods (MAMs) [24] for the storage and retrieval management of outsourced XML data. Although MAMs bring in many advantages for the indexed data, they introduce Storage cost 1.821 3.518 5.264 6.894 7.920 8.703 9.885 0K 2K 4K 6K 8K 10K 12K 10K 20K 30K 40K 50K 60K 70K size node Min nodes Actual nodes Max nodes Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 92/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh challenging issues related to security, especially for outsourced databases. Thus, further research in this direction will be interesting. Database Size 10K 20K 30K 40K 50K 60K 70K Value Tree Distinct items 5,415 10,743 16,128 20,907 22,279 22,499 24,913 Min Nodes 603 1,196 1,794 2,325 2,477 2,501 2,770 Max Nodes 679 1,345 2,018 2,615 2,786 2,814 3,116 Parent Tree Distinct items 9,126 18,108 27,181 36,376 43,612 50,379 57,497 Min Nodes 1,015 2,014 3,022 4,043 4,848 5,599 6,390 Max Nodes 1,143 2,265 3,400 4,549 5,454 6,299 7,189 Actual nodes 1,821 3,518 5,264 6,894 7,920 8,703 9,885 Table 2. Storage cost from sample dataset. DataSize 10K 20K 30K 40K 50K 60K 70K Result size 77 340 570 743 743 743 743 Executing time (s) 0.220952 0.5181948 0.776308 0.932495 0.946947 0.965588 0.971315 Fetch data 0.063093 0.3028116 0.553021 0.765792 0.783896 0.784914 0.788293 Build VO 0.000781 0.0021049 0.003099 0.004648 0.00549 0.005479 0.010001 Verify VO 0.154281 0.2063051 0.213926 0.153889 0.150011 0.167531 0.163361 Generate XML 0.001558 0.0031142 0.004486 0.005616 0.005662 0.005688 0.006184 SQL Time (s) 0.038746 0.0878642 0.13144 0.177424 0.188258 0.194569 0.20183 IOCost (nodes) 108 402 685 871 873 873 885 Table 3. Execution time, I/O cost over result size and database size. DataSize 10K 20K 30K 40K 50K 60K 70K Result(%) 0 341.6% 640.3% 864.9% 864.9% 864.9% 864.9% Time (%) 0 134.5% 251.3% 322.0% 328.6% 337.0% 339.6% SQL Time(%) 0 126.8% 239.2% 357.9% 385.9% 402.2% 420.9% IOCost(%) 0 272.2% 534.3% 706.5% 708.3% 708.3% 719.4% Table 4. The increase of overall cost over result size and database size. Figure 9. Six phases of query processing progress. Figure 10. The increase of overall cost over result size and database size. 0% 865%865%865%865% 640% 342% 135% 251% 322% 329% 337% 340% 421%402%386% 358% 239% 127% 0% 100% 200% 300% 400% 500% 600% 700% 800% 900% 1000% 10K 20K 30K 40K 50K 60K 70K Result(%) Time (%) IOCost(%) SQL Time(%) Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 93/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 8. References [1]. T.K.Dang, “Security Protocols for Outsourcing Database Services”, Information and Security: An International Journal, ProCon Ltd., Sofia, Bulgaria, 18, 85-108, 2006. [2]. P. Lin and K.S. Candan, “Hiding Tree-Structured Data and Queries from Untrusted Data Stores”, In Proc. 2nd Intl. Workshop on Security In Information Systems, Porto, Portugal, April 2004. [3]. T.K.Dang, “A Practical Solution to Supporting Oblivious Basic Operations on Dynamic Outsourced Search Trees”, In Proc. Intl. Workshop on Privacy Data Management, in conjunction with ICDE05, IEEE Computer Society, Tokyo, Japan, April 2005. [4]. P.Lin and K.S. Candan, “Secure and Privacy Preserving Outsourcing of Tree Structured Data”, Secure Data Management, VLDB 2004 Workshop, Toronto, Canada, August, 2004. [5]. H. Hacigümüş, B. Iyer, C. Li and S. Mehrotra, “Executing SQL over Encrypted Data in the Database-Service- Provider Model”, In Proc. ACM SIGMOD Intl. Conf. on Management of data, February 2002. [6]. K.C.K.Fong, “Potential Security Holes in Hacigümüş’ Scheme of Executing SQL over Encrypted Data”, 2003, [7]. E.Mykletun, M.N arasimha and G.Tsudik, “Authentication and Integrity in Outsourced Databases”, In Proc. ISOC Symp. on N etwork and Distributed System Security, 2004. [8]. R.Sion, “Query Executing Assurance for Outsourced Databases”, In Proc. 31st VLDB Conf., Trondheim, N orway, 2005. [9]. R. Brinkman, L. Feng, J. Doumen, P.H. Hartel, and W. Jonker, “Efficient Tree Search in Encrypted Data”, Information System Security Journal, 13, 14-21, 2004. [10]. M.N arasimha and G.Tsudik, “DSAC: An Approach to Ensure Integrity of Outsourced Databases using Signature Aggregation and Chaining”, ACM Conf. on Information and Knowledge Management, N ovember, 2005. [11]. E.Mykletun, M.N arasimha and G.Tsudik, “Providing Authentication and Integrity in Outsourced Databased using Merkle Hash Tree’s”, UCI-SCON CE Technical Report, 2003, MerkleODB.pdf. [12]. R.Sion and B.Carbunar, “Conjunctive Keyword Search on Encrypted Data with Completeness and Computational Privacy”, Cryptology ePrint Archive, Report, 2005. [13]. P.Golle and I.Mironov, “Uncheatable distributed computations”, In Proc. Conf. on Topics in Cryptology, section 2.2, 2001. [14]. P.Devanbu, M.Gertz, C.Martel and S.G.Stubblebine, “Authentic Thrid-party Data Publication”, In Proc. IFIP Workshop on Database Security, 101–112, 2000. [15]. F.Li, M.Hadjieleftheriou, G.Kollios and L.Reyzin, “Dynamic Authenticated Index Structures for Outsourced Databases”, SIGMOD 2006, Chicago, USA, June, 2006. [16]. T.K.Dang and N .T.Son, “Providing Query Assurance for Outsourced Tree-Indexed Data”, In Proc. Intl. Conf. on High Performance Scientific Computing, Hanoi, Vietnam, March, 2006. [17]. H.Wang, S.Park, W.Fan and P.S.Yu, “ViST: A Dynamic Index Method for Querying XML Data by Tree Structures”, SIGMOD 2003, San Diego, CA, June, 2003. [18]. T.Shimizu and M.Yoshikawa, “An XML Index on B+ - Tree for Content and Structural Search”, 2005, shimizu_dews2005.pdf. [19]. Sample dataset World geographic database, mondial/mondial-3.0.xml. [20]. Sample dataset Index of articles from SIGMOD Record, igmod-record/SigmodRecord.xml. [21]. M. N arasimha and G. Tsudik, “Authentication of Outsourced Databases using Signature Aggregation and Chaining”, In Proc. Intl. Conf. on Database Systems for Advanced Applications, April 2006. [22]. T.K.Dang, “A Practical Solution to Supporting Oblivious Basic Operations on Dynamic Outsourced Search Trees”, Special Issue of International Journal of Computer Systems Science and Engineering (CSSE), CRL Publishing Ltd, UK, 21(1), 53-64, Jan, 2006. [23]. T.K.Dang, “Oblivious Search and Updates for Outsourced Tree-Structured Data on Untrusted Servers”, International Journal of Computer Science and Applications (IJCSA), 2(2), 67-84, June 2005. [24]. T.K. Dang, “Semantic Based Similarity Searches in Database Systems (Multidimensional Access Methods, Similarity Search Algorithms)”, PhD thesis, FAW- Institute, University of Linz, Austria, May 2003. Appendix Formulas (11) to (14) are proven as follows. Minimal nodes at a depth Maximal nodes at a depth h Lmin Lmax h-1 ⎡Lmin/f⎤ ⎡2Lmax/f⎤ h-2 ⎡Lmin/f2⎤ ⎡22Lmax/f2⎤ … … … h-(h-1) ⎡Lmin/fh-1⎤ = 1 ⎡2h-1Lmax/fh-1⎤ = 1 ⇒ ⎡ ⎤ 1log minmin += VTreefVTree Lh , ⎡ ⎤ 1log max2/max += VTreefVTree Lh ⎡ ⎤ ⎡ ⎤ 1/11)/1(11...)/1/11( 1min2minmin min +⎥⎥ ⎤⎢⎢ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ −−=++++=⇒ − f fLffLN h ⎡ ⎤ ⎡ ⎤ ( ) 1/21/211...)/2/21( 1 max 22 maxmax max +⎥⎥ ⎤⎢⎢ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ −−=++++=⇒ − f fLffLN h ._.