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

, 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