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 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 được. Vì vậy, trước khi tiến hành outsource, ta cần phải xác định được cấu trúc lưu trữ phù hợp với cấu trúc dữ liệu của XML. Điều này đặc biệt quan trọng, nó ảnh hưởng rất lớn đến các phương pháp sẽ được áp dụng trong xử lý truy vấn và đảm bảo truy vấn. 3.1 Mô hình lưu trữ Tương tự như RDB truyền thống, mỗi tài liệu XML đều được đặc trưng bởi một lược đồ (schema) định nghĩa mối quan hệ cha con giữa các node, số lượng thuộc tính của của mỗi node. Và dĩ nhiên, lược đồ này có dạng cây, gọi là schema tree. Mỗi node trong tài liệu XML (xml element) tương ứng với một t-node trong cây luận lý, mỗi thuộc tính của xml element sẽ tương ứng với a-node trong cây luận lý. Hình 6 ví dụ về cây dữ liệu luận lý và cây cấu trúc rút ra từ một tài liệu XML. Từ cây cấu trúc, có thể dễ dàng chuyển đổi tài liệu XML sang các dạng lưu trữ khác. Tài liệu này trình bày hai phương pháp thường dùng để lưu trữ tài liệu XML: dạng bảng (table-based) và dạng node (node-based). Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 36/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Root Customer Customer Order Order Code, “01” Amount, “5000” Code, “02” Amount, “10000” Name, “Bob” Name, “Alice” t-node t-node t-node t-nodet-node a-node a-node a-nodea-nodea-nodea-node (A) (B) Root Customer Order Cây cấu trúc của tài liệu XML Cây dữ liệu luận lý Name Code Amount a-node t-node Hình 3.6. Cấu trúc cây luận lý của một tài liệu XML. Trong cây dữ liệu luận lý và cây cấu trúc, mỗi node hình chữ nhật góc tròn đại diện cho một node (element) trong tài liệu XML. Các node hình chữ vuông góc đại diện cho một thuộc tính (attribute) trong một element của tài liệu XML. 3.1.1 Dạng bảng: Table-based Từ cây cấu trúc của tài liệu, có thể chuyển đổi sang dạng lược đồ quan hệ theo các bước sau. - Gán nhãn (labeling) các t-node cấu trúc sao cho mỗi node có một giá trị nhãn duy nhất. - Mỗi t-node cấu trúc được chuyển thành một bảng tương ứng có tên là tên của t- node kết hợp với giá trị nhãn. Các a-node con của t-node này được chuyển thành các cột của bảng. Mỗi bảng bổ sung thêm cột nodeid là định danh của node trong bảng dữ liệu. N ếu t-node có cha, thì bổ sung thêm cột pnodeid tham chiếu đến bảng phát sinh từ t-node cha. Từ cây cấu trúc hình 3.6.b, ta thực hiện gán nhãn cho các node: Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 37/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Hình 3.7. Cây cấu trúc sau khi được gán nhãn. Sau đó, chuyển sang lược đồ quan hệ như sau. Root_01(nodeid) Customer_02(nodeid, name, pnodeid) Order_03(nodeid, code, amount, pnodeid) N goài ra, mỗi table còn được bổ sung thêm một số cột như timestamp, sign,… các giá trị này được dùng để giúp việc chứng minh kết quả truy vấn trả về sau này. • Ưu điểm Tài liệu XML sau khi đã được chuyển đổi sang dạng lược đồ quan hệ từ đó có thể áp dụng các kết quả trước đó dùng trong lược đồ quan hệ. Ta có thể áp dụng biện pháp DSAC [10, 21] hay EMB Tree [15] để có thể đảm bảo querry assurance trong việc truy vấn. • Khuyết điểm Về phía người dùng, CSDL được outsourced là tài liệu XML, vì vậy câu truy vấn được thực hiện thông thường là một dạng query trên tài liệu XML (XPath, XQuery,…). Do đó, cần phải có một bước chuyển đổi từ ngôn ngữ truy vấn này sang ngôn ngữ SQL bình thường. Một vấn đề cần được quan tâm là: bản chất schema của CSDL có thể được thay đổi động bất cứ lúc nào. Mặc khác, việc thay đổi schema của tài liệu XML là Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 38/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh khá linh động. Tuy nhiên điều này dẫn việc thay đổi cấu trúc bảng RDB tương ứng. Điều này có tác động không tốt đến dữ liệu đã được lưu trữ (việc thêm cột dữ liệu và một bảng có thể dẫn đến việc tính toán lại toàn bộ các chữ ký điện tử, nếu sử dụng phương pháp DSAC). Mã hóa lại toàn bộ dữ liệu. Điều này là không thể trong trường hợp dữ liệu đã được outsourced. Tuy còn tồn tại một số khuyết điểm, nhưng trong trường CSDL XML không thay đổi về schema thì vẫn có thể áp dụng phương pháp này để có thể tận dụng được các kết quả đã được nghiên cứu tốt trên CSDL quan hệ. Trong tài liệu này, chúng tôi đề cập đến một hướng tiếp cận khác dựa trên phương pháp lưu trữ dữ liệu thứ hai: node- based. 3.1.2 Dạng node: Node-based Một hướng tiếp cận khác trong việc lưu trữ CSDL XML là lưu các t-node và a-node của cây dữ liệu luận lý. Tương tự như phương pháp trên, đầu tiên, các node cấu trúc (bao gồm cả t-node và a- node) đều phải được gán nhãn. Phương pháp gán nhãn tương tự như trên (chỉ khác là việc gán nhãn bao gồm cả a-node). Khi đó, việc lưu xuống CSDL quan hệ sẽ tồn tại hai bảng dữ liệu để lưu t-node và a-node có nội dung như sau: t-node(nodeid, xtype, datatype, nameid, pnodeid, lmaid, value) a-node(nodeid, xtype, datatype, nameid, pnodeid, sibid, value) Trong đó 2: - NodeID : là định danh của node. - XType : dùng để phân biệt các loại đối tượng. - Datatype : dùng để xác loại dữ liệu 2 N goài các thành phần như trên, tùy theo các giải thuật chứng thực khác nhau mà cần bổ sung thêm một số các thông tin khác vào t-node và a-node. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 39/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh - NameID : định danh của tên của node (t-node và a-node) . Tên của một node được phân biệt dựa vào ngữ cảnh mà tên đó xuất hiện. Mỗi tên sẽ được định danh bởi một chỉ số duy nhất trong toàn CSDL. - PNodeID: định danh của t-node cha của t-node hiện tại. Chú ý: đối với a-node, pnodeid là định danh của t-node cha của t-node cha của a-node hiện tại. - LMAid: định danh của a-node trái nhất. - SibID: định danh của a-node anh em bên phải. Với dạng thức lưu trữ như vậy, việc thay đổi schema (bổ sung/bỏ bớt một thuộc tính) chỉ đơn thuần như một tác vụ insert/delete đơn giản, và chỉ ảnh hưởng đến node hiện tại. Do đó, không đòi hỏi thêm bất kỳ một chi phí nào khác mà vẫn đảm bảo được các yêu cầu bảo mật đặt ra. 1. Ưu điểm Phản ánh đúng bản chất dạng cây của tài liệu XML. Do đó, khắc phục được khuyết điểm của phương pháp table-based, việc thay đổi cấu trúc của tài liệu XML không ảnh hưởng nhiều đến nội dung lưu trữ hiện tại. Và chỉ ảnh hưởng đến node cần cập nhật. Sử dụng được một số kết quả nghiên cứu trước đó [2, 16] trong việc bảo đảm các vấn đề của query assurance. 2. Khuyết điểm Do tất cả các t-node, a-node được lưu thành những record riêng lẻ nên số lượng record có thể trở nên rất lớn so với table-based. Điều này làm tăng tính phức tạp của database. N goài ra, các biện pháp chỉ mục (indexing) trên RDB áp dụng không mấy hiệu quả đối với dữ liệu dạng cây như XML. Trong khi, các phương pháp chỉ mục chuyên cho XML vẫn còn trong giai đoạn phát triển. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 40/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 3.1.3 Nhận xét Trong hai phương pháp lưu trữ đã đề cập như trên, phương pháp table-based chuyển đổi tài liệu XML sang dạng table của RDB truyền thống. Từ đó có thể áp dụng lại được các biện pháp bảo đảm query assurance [10, 11, 14, 15, 21]. N hưng phương pháp này có một khuyết điểm khá lớn là: khi cấu trúc của tài liệu XML thay đổi bằng cách bổ sung mới một node mới hoàn toàn (hay một attribute mới) thì cấu trúc của các bảng dữ liệu sẽ bị thay đổi theo. Điều này đòi hỏi một khối lượng tính toán khá lớn để bảm bảo các cấu trúc được dùng trong đảm bảo truy vấn (bao gồm việc ký lại các record, mã hóa dữ liệu, xây dựng lại các chuỗi chữ ký hoặc các cấu trúc index phức tạp khác,…) Trong phạm vi của tài liệu này, chúng tôi sẽ áp dụng phương pháp lưu trữ node- based, đồng thời đề nghị một cấu trúc chỉ mục (indexing structure) chuyên dùng cho tài liệu XML. Từ đó, nhúng kèm một số thông tin để chứng minh tính đúng, tính đầy đủ và tính mới. 3.2 Chỉ mục cho tài liệu XML Chỉ mục là một khái niệm hết sức quan trọng trong CSDL. N ó giúp tăng tốc đáng kể hiệu suất truy vấn dữ liệu so với phương pháp tìm kiếm tuần tự cổ điển, trong trường hợp lý tưởng, tìm kiếm sử dụng chỉ mục nhanh hơn tìm kiếm tuần tự là N/log2N lần. Đối với CSDL quan hệ (relational databases), chỉ mục được áp dụng hết sức có hiệu quả và phổ biến trong hầu hết các RDBMS. Các cấu trúc chỉ mục thường dùng là : bảng băm (hash table), bitmap và các cấu trúc chỉ mục dạng cây. Đối với CSDL bán cấu trúc dạng cây như CSDL XML, hiện tại có nhiều nguyên cứu trong việc xây dựng chỉ mục phù hợp[17, 18]. Trong phạm vi của mình, tài liệu này không đi chi tiết vào các phương pháp chỉ mục cho tài liệu XML và cũng không có ý định so sánh chúng, mà chỉ đưa ra một cấu trúc chỉ mục cho tài liệu XML, mà qua đó có thể nhúng vào một số thông tin nhằm phục vụ cho mục tiêu đảm bảo query assurance. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 41/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Trong các phương pháp chỉ mục, phương pháp chỉ mục dạng cây được sử dụng khá phổ biến. Trong đó điển hình là B+Tree được áp dụng rất thành công trong việc tạo chỉ mục trên các RDBMS hiện tại. Với đặc tính của mình, B+Tree có thể tạo chỉ mục cho một số lượng lớn các record mà độ phức tạp không cao (nếu cây B+Tree có fanout là 100, chiều cao là 4 thì có thể quản lý được 100x100x100 = 1.000.000 record). Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 42/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chương 4 ĐẢM BẢO TRUY VẤN 4.1 Phương pháp Đảm bảo truy vấn (Query assurance) nhằm mục tiêu chứng minh với người dùng kết quả truy vấn trả từ server là: đúng, đủ, mới. Tính đúng có thể thực hiện khá dễ dàng thông qua chữ ký điện tử. Chứng minh tính đủ của kết quả truy vấn thường dựa vào tính chất của từng loại query. Xét hai loại truy vấn: truy vấn theo vùng (khoảng giá trị thỏa mãn) và truy vấn theo điểm (bằng một giá trị cụ thể). Truy vấn điểm thực chất là dạng suy biến của truy vấn vùng với hai cận tiến đến bằng nhau. N hư vậy chỉ cần xem xét đối với truy vấn vùng. Xét một truy vấn theo vùng đối với cận là LB và UB. Kết quả trả về là các record thỏa mãn. S = { R | R ≥ LB, R ≤ UB } N ếu các record R được đảm bảo là sắp xếp tăng dần (hoặc giảm dần), để chứng minh kết quả trả về là đầy đủ, server chỉ cần trả về hai record nằm ở hai biên : S’ = S ∪ {RL | RL = max(Ri), Ri UB, ∀j} N ếu server có thể chứng minh được giữa RL và RU chỉ có các record trả về là có thể chứng minh được kết quả là hoàn toàn đầy đủ. N hư vậy, các record cần được sắp xếp theo thứ tự và thứ tự này có thể chứng minh được. Một cách đơn giản để đạt được điều này là sau khi sắp xếp R theo thứ tự, ta tính giá trị băm như sau: S = h(h(R0) | h(R1) | h(R2) |….| h(RN))SK Trong đó : h là hàm băm bảo mật (security hash) như SHA1, MD5. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 43/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Sau đó thực hiện ký lên giá trị băm vừa tính được bằng giải thuật mã hóa bất đối xứng (như RSA). Trong kết quả trả về, server trả về kèm theo các h(Ri) còn lại và giá trị S. Client hoàn toàn có thể tính lại băm của các record theo quy tắc trên và thực hiện kiểm chứng với S bằng khóa công cộng của giải thuật ký. 4.2 Nested B+ Tree N hư đã trình bày ở phần trên, phương pháp áp dụng để chứng minh tính đầy đủ căn bản dựa trên dãy thứ tự các record và chữ ký lên dãy thứ tự này. Điều này có thể đạt được bằng một cấu trúc chỉ mục phù hợp với cách thức lưu trữ dữ liệu đã được trình bày ở mục 3.1 của tài liệu này. Xét một tài liệu XML, các node được định vị bởi path, tức đường đi từ node gốc đến node hiện tại. Các truy vấn trên XML thông thường được xác định path. N hư vậy, chỉ mục XML, ngoài giá trị của node, cần phải chứa thêm thông tin về path của node. Quay lại phương pháp lưu trữ đã được đề cập ở phần trên, giá trị nameid là duy nhất đối với mỗi node cấu trúc, do đó có thể được sử dụng tương đương với path. N hư vậy, mỗi node cần được chỉ mục trên bộ hai thuộc tính (nameid, value). Tuy nhiên, ngoài việc truy vấn theo giá trị, với bản chất cha/con của dữ liệu dạng cây XML thì yêu cầu truy vấn các node con khi đã biết được node cha là thường xuyên. Để chứng minh completeness cho các truy vấn này, cần bổ sung thêm chỉ mục của bộ ba giá trị (nameid, pnodeid, value) để các record được sắp xếp theo node cha. Ta có thể xây dựng hai cây chỉ mục riêng lẻ cho hai bộ giá trị trên. Tuy nhiên, điều này có thể dẫn đến một số vấn đề phức tạp trong việc cập nhật dữ liệu, chứng minh truy vấn và lãng phí nơi lưu trữ (do có trùng thuộc tính đầu là nameid). Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 44/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh ... ... NameTree ParentTree ValueTree (n am eid ) (p no de id, va lue ) (va lue ) Hình 4.8. Cấu trúc NB+Tree. Sự kết hợp của ba loại cây NameTree, ParentTree và ValueTree cho phép sắp thứ tự toàn bộ các attribute và các element của tài liệu XML theo hai thứ tự: (nameid, value) và (nameid, pnodeid, value), đảm bảo cho việc truy vấn nhanh chóng cũng như khả năng đảm bảo truy vấn trên tài liệu XML. Để đảm bảo được yêu cầu trên, có thể sử dụng kết hợp các cấu trúc cây như sau. Xây dựng một cây B+-Tree với khóa so sánh là nameid, gọi là NameTree. Tại node lá của NameTree chứa gốc của hai cây B+Tree theo khóa lần lượt là (pnodeid, value) và (value). Hai cây này có tên là: ParentTree và ValueTree. Tập hợp ba loại cây này tạo thành một cấu trúc dữ liệu, gọi là Nested B+Tree, cho phép lập chỉ mục cho tài liệu XML trên hai bộ giá trị (nameid, pnodeid, value) và (nameid, value). N goài ra, việc phân bố của dữ liệu cũng ảnh hưởng một phần khá lớn đến cấu trúc cây. N ếu dữ liệu bị tập trung vào một vùng nhất định có thể làm quá trình tách node diễn ra thường xuyên, làm cho hiệu suất sử dụng của cây B+ không cao. Để hạn chế điều này, cây B+ đưa vào thao tác tái phân bố (redistribute) dữ liệu ở các node gốc. Trong cây N B+, ngoài đặc tính trên, các khóa (key) cũng được thực hiện tái phân bố trước khi thực hiện việc tách node hay hợp nhất (merge) node. Một hướng tiếp cận khác, là sử dụng một cấu trúc chỉ mục đa chiều (multi-dimension index) để tạo chỉ mục cho tài liệu XML dựa trên bộ bốn thuộc tính (nameid, prefixid, pnodeid, value) như họ cây R (R-Tree, R+Tree, R* Tree, X-Tree,…). Tuy nhiên, các Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 45/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh cấu trúc chỉ mục này không đảm bảo được thứ tự tăng dần của các record (hoặc chỉ đảm bảo cho một thuộc tính) vì vậy không phù hợp cho việc chứng minh completeness trong truy vấn. Nested Merkle B+ Tree Để N M+Tree có thể chứng minh kết quả truy vấn, cần nhúng kèm một số thông tin tương tự như cây Merkle Hash Tree (MHT) vào cây N B+Tree như sau: gọi H(node) là băm của một node bất kỳ thuộc N B+Tree, khi đó h(node) được tính như sau: - Node là node lá của ValueTree, ParentTree: H(node) = h(A(node)) - Node là node lá của NameTree: H(node)=h(H(R(ParentTree))||H(R(PrefixTree))) - Node là node nội : H(node)= h(∪I H(Childi(node))) , i = 1..số con của node. - Node là gốc của NameTree: H(node)= h(ε||∪I H(Childi(node))) , i = 1..số con của node. Trong đó: h là hàm băm bảo mật thỏa tính không đụng độ và không thể đảo trong thời gian tuyến tính (collusion-free and non-invertable) như SHA1, MD5. A(node) là t- node hoặc a-node liên kết với node lá này. R(tree) là node gốc của tree. Childi (node) là node con thứ i của node. ε là một giá trị duy nhất theo thời gian (timestamp), giá trị nào được cung cấp tới tất cả các client khi có sự thay đổi. Sau đó, thực hiện ký lên nội dung của R(PrefixTree) bằng giải thuật chữ ký số. N hư vậy, với việc áp dụng ý tưởng của MHT lên N B+Tree, ta được N MB+Tree (Nested Merkle B+ Tree), vừa dùng làm chỉ mục trong truy vấn vừa được dùng để chứng minh truy vấn trên toàn dữ liệu XML. Phần tiếp theo của tài liệu trình bày cách thức vận dụng N MB+Tree trong việc thực hiện truy vấn cũng như chứng minh kết quả trả về. 4.3 Tác vụ chọn Phép chọn (Selection) là câu truy vấn được xử dụng thường xuyên nhất. Đối với RDB, đó là phát biểu SELECT trong SQL. Trong XML, có nhiều ngôn ngữ được dùng truy Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 46/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh vấn như XPath, XQuery. Tài liệu này minh họa cho một vài dạng câu truy vấn XPath thông dụng. Xét một tài liệu XML có cấu trúc như sau: Hình 4.9. Cây cấu trúc của một tài liệu XML Các chỉ số đánh kế bên các node là nameid của node đó. Tài liệu sẽ khảo sát qua một số dạng truy vấn thường gặp. 4.3.1 Dạng truy vấn liên quan một node, điều kiện đơn Là dạng truy vấn đơn giản nhất, ví dụ /Customer/Order/Item[@name=”TV”]: tìm tất cả các hạng mục có tên là “TV”. Theo quy tắc gán tên, ta có định danh tên của thuộc tính name của node Item là 12. N hư vậy, để trả lời câu truy vấn này, thực hiện tìm trên N MB+Tree với khóa tìm kiếm (nameid=13, value=”TV”). Kết quả trả về các a-node Name_13 của Item_8. Từ các a-node, có thể dễ dàng xác định được các t-node Item_8 tương ứng. Sau đó, ta có thể lấy được các a-node khác (như price_14, qty_15). Tính đúng và Tính đầy đủ N goài các a-node Name thỏa điều kiện, server trả về thêm hai a-node biên của tập kết quả, và các băm của các node lân cận đủ để tính băm của node cha, đồng thời trả thêm giá trị băm của các node anh em của node cha. Các kết quả này giúp cho client có thể tính ngược lại được giá trị băm của nút gốc. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 47/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Tại nút gốc, từ giá trị băm tính được kết hợp với temp thời gian lưu trữ, client có thể kiểm tra với chữ ký của nút gốc. Do đặc tính một chiều, bất-khả-đảo của các hàm băm được áp dụng nên có thể chứng minh tính đúng (correctness). Do các record được sắp xếp theo thứ tự tăng dần theo bộ thuộc tính (nameid, value), kết hợp với hai record biên kèm theo, có thể chứng minh được tính đầy đủ (completeness) của dữ liệu. Tính mới Do trong băm của node gốc có chứa đựng giá trị temp thời gian ε (timestamp). N ếu data owner phổ biến giá trị ε này cho tất cả các client. Từ đó client có thể xác định được tính mới của dữ liệu. N hư vậy, chỉ sau một thao tác kiểm tra, client có thể kiểm tra đầy đủ cả ba vấn đề đặt ra của query assurance chi thông qua các phép băm với chi phí thấp hơn rất nhiều với các phép toán số nguyên lớn của các chữ ký số. Chứng minh không có record thỏa mãn (empty proof) Một phương diện khác cần được quan tâm là chứng minh kết quả trả về là trống, nghĩa là không có record nào thỏa điều kiện tìm kiếm. Để chứng minh, server trả về hai record nằm kế nhau trong dãy thứ tự có giá trị lớn và nhỏ hơn giá trị cần truy vấn. 4.3.2 Dạng liên quan nhiều node, điều kiện đơn Là dạng truy vấn tương đối phức tạp hơn liên quan đến nhiều node. Điều này tương đương với phép join query của RDB. Xét câu truy vấn : /Customer[@name=”Marry”]/Order/Item : trả về tất cả các hạng mục do khách hàng có tên là “Mary” đã mua. Tương tự như trên, xây dựng một VO để chứng minh cho truy vấn (nameid=4, prefixid=1, value=”Marry”). Tuy nhiên, VO này chỉ cần chứa các a-node Name_4 và các t-node Customer_1 tương ứng. Các a- node Name_4 được dùng để chứng minh t_node Customer_1 đầy đủ. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 48/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Ứng với mỗi t-node Customer_1 xây dựng một VO để đảm bảo query assurance của truy vấn (nameid=3, prefixid=1, pnodeid=) để lấy ra kết quả cho t-node Order_3. Tương tự, ta có thể đảm bảo cho kết quả truy vấn cho các node Item trả về. Tương tự cho câu truy vấn /Customer[@name=”Marry”]/Order/Item[@name= ”TV”] : lấy các hạng mục có tên là “TV” do khách hàng tên “Marry” đã mua. Phương pháp xử lý kết hợp giữa câu truy vấn trên và xử lý của trường hợp đầu tiên. 4.3.3 Các dạng khác Hai ví dụ trên là cách thức vận dụng cây N MB+ trong việc thực hiện truy vấn và chứng minh kết quả truy vấn. Để xử lý các câu truy vấn khác phức tạp hơn, ta có thể phân tách chúng thành những câu truy vấn đơn và từ đó xây dựng một kế hoạch thực thi (execution plan) với các bước thực hiện đơn. Ví dụ, ta có execution plan cho các câu truy vấn trên như sau. /Customer/Order/Item[@name=”TV”] STEP#1 IndexMethod : Vtree, nameID=13 Condition : equal to [TV] Result level : not included Retrieval : node only StepValue : PNODEID [For each matched items, perform] STEP#2 IndexMethod : DirectIDAccess, id=ParentStepValue Result level : 1 Retrieval : node and all its attributes /Customer[@name=”Marry”]/Order/Item STEP#1 IndexMethod : Vtree, nameID=4 Condition : equal to [Marry] Result level : not included Retrieval : node only StepValue : PNODEID [For each matched items, perform] STEP#2 IndexMethod : DirectIDAccess, value=ParentStepValue Result level : not included Retrieval : node only StepValue : ID [For each matched items, 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 Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 49/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 4.3.4 Hợp nhất các VO Trong việc thực thi một câu truy vấn, hầu hết các trường hợp, server cần trả về cho client nhiều hơn một VO. Ví dụ, trong trường hợp câu truy vấn mục 4.2.2, số lượng VO server cần trả về phục thuộc vào số lượng record Customer thỏa điều kiện @name=”Marry”. Điều này có thể dẫn đến sự quá tải ở phía Client trong việc kiểm tra các VO. Để hạn chế trường hợp trên, server cần phải thực hiện hợp nhất các VO này trở thành một VO duy nhất và gửi trả VO này về cho client. N hư vậy, client chỉ cần thực hiện kiểm tra một lần duy nhất để có thể xác định query assurance cho toàn bộ dữ liệu nhận được. Việc hợp nhất các VO có thể thực hiện được dễ dàng. Mỗi VO ban đầu được xác định bởi một đoạn các record liên tục nhau cùng với (tối đa) hai record biên. Với nhiều VO, ta sẽ có nhiều đoạn. Vì vậy, thay vì phát sinh co-path cho từng đoạn, ta có thể thực hiện phát sinh co-path cho toàn bộ các đoạn. 4.4 Các tác vụ cập nhật dữ liệu Các tác vụ cập nhật khi dữ liệu đã được outsourced đòi hỏi thêm một số chi phí nhất định. Trong trường hợp một bản sao của CSDL được lưu trữ ở data owner, số lượng các lần cập nhật xảy ra không thường xuyên (thời gian giữa hai lần cập nhật là đủ lớn) và số lượng cập nhật là nhiều, data owner có thể thực hiện cập nhật dữ liệu cục bộ. Sau đó thực hiện outsourced lại dữ liệu. Ở đây, tài liệu trình bày một phương thức để cập nhật dữ liệu trực tiếp được dùng trong trường hợp data owner không lưu trữ lại bản sao của dữ liệu outsourced hoặc chi phí cho mỗi lần outsource là khá lớn. 4.4.1 Tác vụ thêm mới (insertion) Data owner gửi các dữ liệu cần thêm mới (các xml element, attrbiute) đến server. Server thực hiện thêm các record mới vào CSDL, cập nhật lại cấu trúc index. Tính toán và cập nhật các giá trị băm của các node lá có liên quan và lan truyền lên đến node gốc của cây N MB+. Server gởi trả về cho data owner giá trị băm mới của node Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 50/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh gốc. Data owner phát sinh một giá trị timestamp mới, kết hợp với giá trị băm nhận được. Sau đó thực hiện ký lên các giá trị này. Data owner gửi lại cho server giá trị timestamp mới cùng với chữ ký mới. Server cập nhật giá trị timestamp và chữ ký vừa nhận được vào CSDL. Giao thức cập nhật nhiều giai đoạn như trên được minh họa như hình sau. Hình 4.10. Các bước thực hiện insert 4.4.2 Tác vụ xóa và cập nhật (deletion/updation) Tác vụ xóa/cập nhật dữ liệu cũng được thực hiện thông qua các bước tương tự như tác vụ thêm mới. Data owner gửi yêu cầu đến server. Server thực hiện việc cập nhật xuống CSDL đồng thời tính toán lại các giá trị băm của các node trong cây N MB+. Giá trị băm mới của node gốc được trả về cho data owner để thực hiện ký. Chữ ký cùng giá trị timestamp mới được gửi trả về cho server để cập nhật vào CSDL. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 51/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chương 5 PHÂN TÍCH Chúng tôi đã trình bày giải pháp lưu trữ và sử dụng cây chỉ mục N MB+ để chứng minh truy vấn đối với dữ liệu XML được outsourced. Trong phần này, chúng tôi đề cập đến các khía cạnh bảo mật cũng như chi phí của giải pháp. Tất cả dữ liệu, kể cả các node của cây chỉ mục, trước khi lưu trữ đều được mã hóa bằng giải thuật mã hóa đối xứng (như Rijndael) nhằm đảm bảo tính bảo mật của dữ liệu cũng như hiệu suất khi thực hiện truy vấn. N hư vậy, phương pháp này thỏa mãn được yêu cầu data confidentiality. Giải pháp trên không đề cập đến tính riêng tư. Tuy nhiên, do đặc tính của dữ liệu dạng cây, nên hoàn toàn có thể áp dụng các kết quả của Lin và Candan [2] để có thể đạt được tính riêng tư. Đối với query assurance, tài liệu trình bày phương thức giải quyết đối với các câu truy vấn vùng và điểm của một điều kiện đơn. Đối với câu truy vấn vùng với nhiều điều kiện kết hợp, ta có thể giải quyết tương tự như cách thức xử lý các tác vụ tập hợp (set operations) bao gồm phép toán giao và hội như đã trình bày trong [10, 14, 21] - Phép Hội : được thực hiện đơn giản như hai câu truy vấn riêng biệt. Các VO phát sinh từ hai câu truy vấn sẽ được hợp nhất như đã trình bày. - Phép Giao : một giải pháp đơn giản, với các tập kết quả từ hai cây truy vấn con theo từng điều kiện, server chọn một tập kết quả nhỏ hơn, ứng với mỗi kết quả thuộc tập này không thỏa mãn tập kia, server trả về một empty proof. Tất cả các VO sau cùng sẽ được hợp nhất để thực hiện kiểm tra một lần ở phía client. Một điều cần quan tâm trong query assurance là chứng minh cho phép join. Trong dữ liệu dạng cây như XML, phép join được áp dụng chủ yếu cho quan hệ từ node cha Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 52/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh xuống node con. Đây là mối quan hệ phổ biến trong CSDL XML. Cây N MB+ sử dụng PTree để chứng minh truy vấn cho phép join này với chi phí thấp nhất trong việc xây dựng VO cũng như chi phí kiểm tra tại phía client. Giải pháp này không áp dụng trực tiếp cho các câu truy vấn có sử dụng các hàm tính toán bao gộp (aggregated function). Cho tới thời điểm hiện tại, theo hiểu biết của chúng tôi, chỉ có giải pháp của Radu Sion. [8] giải quyết cho trường hợp này, tuy nhiên giải pháp cũng tồn tại một số hạn chế như đã trình bày ở trên. Đối với các câu truy vấn này, ta có thể chứng minh các câu truy vấn này tương tự như câu truy vấn vùng, với điều kiện là điều kiện lọc của câu truy vấn ban đầu. Kết quả của hàm bao gộp có thể được tính toán tại server và được client kiểm tra lại ngẫu nhiên sau khi chứng thực được query assurance cho các record thỏa mãn điều kiện. Hoặc hoàn toàn được tính toán tại client. Tiếp theo, tài liệu tiến hành phân tích về mặt chi phí của giải pháp. Do hiện tại, chưa có một nghiên cứu trong lĩnh vực về query assurance cho CSDL XML, nên các phân tích chi phí được đánh giá dựa trên chi phí tối đa và tối thiểu theo tính toán lý thuyết. Đồng thời, ở đây, chúng tôi chỉ đề cập đến các chi phí phát sinh nhằm đảm bảo query assurance. Trước tiên, tài liệu trình bày một số ký hiệu quy ước được sử dụng bao gồm: n Tổng số phần tử (số element và số attribute). s Tổng số phần tử trả về của một truy vấn. f Tham số fanout của cây N MB+. h Chiều cao của cây. L Số node lá của cây. N Tổng số node của cây. |sign| Kích thước giá trị băm (20 byte cho SHA-1) Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 53/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chi phí lưu trữ tại server (storage cost): chi phí phát sinh cho việc lưu trữ tại server là chi phí dùng để lưu cây N MB+. Cây N MB+ là kết hợp bởi một cây NameTree và các cây ValueTree, ParentTree ở các lá của cây NameTree. Kích thước của cây NameTree phụ thuộc vào số lượng node trong cây cấu trúc (shema tree) của tài liệu XML. Số lượng node này thường là rất nhỏ so với số lượng node của cây dữ liệu (data tree) XML, đồng thời ít biến động trong thời gian sống của dữ liệu. Do đó, chi phí lưu trữ chủ yếu là chi phí để lưu các cây ParentTree và ValueTree. Do số lượng ValueTree và ParentTree biến đổi tùy theo số phần tử của schema tree, và chiều cao của các cây là biến đổi phụ thuộc và số phần tử dữ liệu tương ứng với mỗi phần tử cấu trúc. N hư vậy, để tiện cho việc đánh giá, ta giả sử schema tree của tài liệu XML chỉ có duy nhất một phần tử, và do đó chỉ có một cây ValueTree và một cây ParentTree. Dễ dàng nhận ra rằng, tổng số phần tử dữ liệu ở các lá của cây ValueTree và ParentTree là giống nhau. Giả sử rằng các phần tử dữ liệu là phân biệt nhau qua (nameid, value), nghĩa là, mỗi slot của một node lá bất kỳ chỉ chứa liên kết đến một phần tử dữ liệu duy nhất. Khi đó ta có: ⎥⎥ ⎤⎢⎢ ⎡=⎥⎥ ⎤⎢⎢ ⎡= f nL f nL VTreeVTree 2, maxmin (5.1) Ta có số node lá cần thiết tối thiểu trong trường hợp tất cả các node là đều đầy và số node là tối đa trong trường hợp tất các các node lá chỉ chứa ½ số phần tử. Từ số Lmin và Lmax, có thể xác định được số node tối thiểu và tối đa của cây như sau. ⎡ ⎤ 1log minmin += VTreefVTree Lh (5.2) 1log max 2 max +⎥⎥ ⎤⎢⎢ ⎡= VTreefVTree Lh (5.3) Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 54/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh 1 11 11 1 minmin min + ⎥⎥ ⎥⎥ ⎥ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎡ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎝ ⎛ − − = − f fLN h VTree (5.4) 1 21 21 1 maxmax max + ⎥⎥ ⎥⎥ ⎥ ⎥ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎢ ⎡ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛− = − f f LN h VTree (5.5) Các công thức (5.2),(5.3),(5.4),(5.5) có thể được chứng minh như sau. Giả sử, cây B+ có L node lá, khi đó ta có: Số node tối thiểu tại độ sâu Số node tối đa tại độ sâu 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 max 2 max +⎥⎥ ⎤⎢⎢ ⎡= VTreefVTree Lh ⇒ N min = Lmin + ⎡Lmin/f⎤ + ⎡Lmin/f2⎤ + … + 1 = ⎥⎥ ⎥⎥ ⎥ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎡ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎝ ⎛ − − − f fL h 11 11 1 min min + 1 N max = Lmax + ⎡2Lmax/f⎤ + ⎡22Lmax/f2⎤ + … + 1 = ⎥⎥ ⎥⎥ ⎥ ⎥ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎢ ⎡ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛− − f f L h 21 21 1 max max + 1 Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 55/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh N hư vậy, chi phí lưu trữ phát sinh có thể tính như sau: ⎪⎩ ⎪⎨ ⎧ +=++= +=++= VTreeNTreePTreeVTreeNTreestorage VTreeNTreePTreeVTreeNTreestorage NNNNNC NNNNNC maxmaxmaxmax minminminmin 2 2 (5.6) Thực tế, tồn tại khá nhiều phần tử có khóa so sánh trùng nhau, tức là có bộ giá trị (nameid, value) đối với ValueTree hoặc (nameid, pnodeid, value) đối với ParentTree giống nhau. N hững phần tử này chiếm cùng một slot trong node lá của cây chỉ mục. Do đó, tổng số slot sử dụng trong các node lá luôn nhỏ hơn tổng số phần tử cần chỉ mục. N ếu gọi n’, n” lần lượt là số các phần tử phân biệt qua (nameid, value) và (nameid, pnodeid, value), dễ dàng nhận ra rằng: n’ < n’’ < n. N hư vậy, để tính được chi phí lưu trữ, cần xác định giá trị n’ và n’’. Sau đó thay vào công thức (5.4), (5.5) để xác định chi phí cho ValueTree và ParentTree. Kích thước VO: trong phân tích này, chúng tôi chỉ quan tâm đến phần dữ liệu phải thêm vào VO để có thể chứng minh truy vấn, do đó, khái niệm kích thước VO là kích thước thông tin thêm vào. N goài kết quả truy vấn, server trả về hai giá trị khóa biên (value cho ValueTree và pnodeid, value cho ParentTree) cùng băm của record tương ứng của hai khóa trên. Cộng với kích thước của co-path dùng để tính toán băm của node gốc. N hư đã trình bày ở phần trên, một câu truy vấn XPath có thể được phân tích thành nhiều đoạn truy vấn vùng, vì vậy có nhiều VO cho các vùng này. Kích thước VO trả về là tổng kích thước của các VO con. Xét kích thước VO cho một truy vấn, ta có: Số node ở độ sâu Số phần tử bổ sung vào co-path h ⎥⎥ ⎤⎢⎢ ⎡ += f sLh 2 CVOh = f.Lh - s + 2 h-1 Lh-1 = ⎡Lh/f⎤ CVOh-1 = f.Lh-1 – Lh Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 56/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh … … … h-i Lh-i = ⎡Lh-i+1/f⎤ CVOh-i = f.Lh-i – Lh-i+1 ⇒ Kích thước VO: CVO =|sign|∑ CVOi , i = 1,hNMBTree (5.7) Chi phí CPU: chi phí CPU (CPU time) là tổng thời gian xử lý kể từ lúc server nhận được yêu cầu truy vấn cho đến khi kết quả truy vấn được giải mã hoàn tất phía client sau khi đã loại bỏ thời gian cho việc truyền nhận dữ liệu trên đường truyền. Có thể chia các giai đoạn xử lý một câu truy vấn thành các giai đoạn sau: se rv er s id e cl ie nt s id e Hình 5.11. Các bước thực thi query. - Parse : phân tích các thành phần của câu truy vấn, loại bỏ các ký tự đại diện nếu cần thiết. Có thể từ một câu truy vấn ban đầu sẽ được phân tích thành nhiều câu truy vấn con. - Plan : xây dựng chiến lược thực thi các câu truy vấn vừa phân tích. - Fetch data : thực hiện truy vấn trên cây chỉ mục, đọc các record thỏa mãn điều kiện từ CSDL. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 57/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh - Build VO : bổ sung các thông tin cần thiết để xây dựng các VO phục vụ cho việc chứng minh truy vấn, bao gồm cả thời gian tạo ra các co-path cho kết quả truy vấn. - Verify VO : kiểm tra kết quả truy vấn dựa vào thông tin VO nhận được. - Generate XML : phục hồi lại dữ liệu dạng XML. Do dữ liệu XML ban đầu lưu xuống CSDL đã chuyển thành các t-node và a-node, nên kết quả trả về phải được phục hồi sang dạng XML ban đầu. Hiện tại, do giới hạn về thời gian, chương trình đánh giá không thực hiện hai bước đầu là Parse và Plan. Các câu truy vấn được dùng để thực thi được cung cấp dưới dạng execution plan. Do đó, công việc còn lại chỉ bắt đầu từ bước fetch data. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 58/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Chương 6 THỰC NGHIỆM Để đánh giá thực nghiệm, chúng tôi hiện thực giải pháp trên nền tảng .N ET Framework 2.0, thư viện mã hóa sử dụng Rijndael và SHA1 cung cấp bởi .N ET 2.0. Sử dụng MS SQL Server 2005 Express Edition để lưu trữ CSDL. Chương trình thử nghiệm trên hệ thống PC P4 2.8GHz, 512MB. Tài liệu XML mẫu là Modial [19] với 69,846 hạng mục (gồm 22,423 element 47,423 attribute). Lược đồ của tài liệu này được trình bày ở phần phụ lục. Hệ số fanout của cây N MB+ là 10. Các tiêu chí được đo đạc bao gồm: - Chi phí lưu trữ (tổng số node của cây N MB+ theo thực tế, so sánh với số node tính trên lý thuyết trình bày ở mục 5). - Kích thước VO (số lượng các hạng mục trả kèm về để chứng minh truy vấn). - Thời gian thực thi truy vấn bao gồm các giai đoạn: fetch data, build VO, verify VO, generate XML và thời gian tổng cộng kể từ lúc câu truy vấn bắt đầu được thực thi cho đến khi dữ liệu XML kết quả được giải mã hoàn tất. Các thời gian này được so sánh trên tương quan số lượng record trả về trên tổng số record của CSDL để thấy được tính tương quan của thời gian thực thi với các thông số khác (yêu cầu là tương quan tuyến tính với kết quả trả về và tương quan logarit với kích thước CSDL). N goài ra, thời gian này còn được so sánh với thời gian thực thi câu truy vấn trong điều kiện không bảo mật để đo được chi phí phát sinh cho việc bảo mật của giải pháp. Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 59/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Các số liệu đo đạc dựa trên câu truy vấn /mondial/country/city[population > 500000]. Kế hoạch thực thi cho câu truy vấn này được trình bày ở phần phụ lục. Chi phí lưu trữ Ở đây, chúng tôi bỏ qua chi phí lưu trữ cho dữ liệu XML mà chỉ tập trung vào phần chi phí phát sinh cần thiết để lưu trữ cấu trúc cây chỉ mục. Chi phí này được đánh giá thông qua số lượng node cần thiết của cây để thực hiện chỉ mục cho số lượng các phần tử cần thiết. Đánh giá chi phí dựa trên chi phí tính toán từ công thức (5.4) và (5.5) cho kích thước tối thiểu và tối đa. Từ kích thước của CSDL (database size) (số lượng phần tử), xác định được số phần tử phân biệt nhau qua bộ thuộc tính (nameid, value) và (nameid, pnodeid, value) để xác định số lượng slot cần lưu trữ tại các node lá của cây chi mục theo (5.4), (5.5). Kết quả trình bày ở bảng dưới đây. Database Size 10K 20K 30K 40K 50K 60K 70K Va lu e Tr ee Distinct items 5,415 10,743 16,128 20,907 22,279 22,499 24,913 Min Leaves 542 1,075 1,613 2,091 2,228 2,250 2,492 Min Height 4 5 5 5 5 5 5 Min Nodes 603 1,196 1,794 2,325 2,477 2,501 2,770 Max Leaves 1,083 2,149 3,226 4,182 4,456 4,500 4,983 Max Height 5 6 6 6 6 6 6 Max Nodes 679 1,345 2,018 2,615 2,786 2,814 3,116 Pa re nt T re e Distinct items 9,126 18,108 27,181 36,376 43,612 50,379 57,497 Min Leaves 913 1,811 2,719 3,638 4,362 5,038 5,750 Min Height 4 5 5 5 5 5 5 Min Nodes 1,015 2,014 3,022 4,043 4,848 5,599 6,390 Max Leaves 1,826 3,622 5,437 7,276 8,723 10,076 11,500 Max Height 6 6 6 7 7 7 7 Max Nodes 1,143 2,265 3,400 4,549 5,454 6,299 7,189 Bảng 6.2. Kích thước cây ValueTree, ParentTree min, max Bảng 6.3. Chi phí lưu trữ Data size 10K 20K 30K 40K 50K 60K 70K Min nodes 1,618 3,210 4,816 6,368 7,325 8,100 9,160 Max nodes 1,822 3,610 5,418 7,164 8,240 9,113 10,305 Actual nodes 1,821 3,518 5,264 6,894 7,920 8,703 9,885 Đề tài: Security Issues in Querying Dynamic Outsourced XML Databases Trang 60/93 SV: Nguyễn Việt Hùng HD: TS Đặng Trần Khánh Hình 6.12. Kích thước cây index. Chi phí tổng cộng Chi phí tổng cộng bao gồm được đo dựa trên thời gian kể từ lúc bắt đầu thực hiện execution plan cho đến khi kết quả được trả về. Để đánh giá được mức độ hiệu quả của giải pháp, tiêu chí đánh giá là quan hệ về thời gian thực thi với kích thước CSDL cũng như kích thước của kết quả trả về. DataSize 10K 20K 30K 40K 50K 60K 70K Result size 77 340 570 743 743 743 743 Executing time 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 Generate co-path 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 0.038746 0.0878642 0.13144 0.177424 0.188258 0.194569 0.2