雲端儲存服務雖然在現今十分熱門，但若系統發生異常而造成使用者的資料毀損時，使用者卻沒有一套有效的方法能證明系統確實發生異常進而無法對損失成本進行索賠。因此企業使用者由於上述的因素對雲端儲存服務往往不信任甚至不採用，我們希望能設計出一套方法來解決及改善雲端儲存服務上的缺陷。本論文著重於違約證明 (Proof of Violation)技術的研究上，所有雲端儲存的更動行為都會透過數位簽章的方式由使用者與服務提供商(Service Provider)互相比對雜湊值(Hash Value)來證明是否有違約行為的出現，以確保雙方能彼此信任。 本論文提出適應性霍夫曼編碼雜湊樹建構(Adaptive Huffman Coding Hash Tree Construction; 簡稱AHCHTC)演算法，以強化雲端儲存服務之即時稽核與違約證明技術。所提之方法依據檔案的更動次數來動態新增與調整雜湊樹節點，能夠減少現今以雜湊樹為基礎違約證明技術的執行時間與所需要的記憶體空間。本論文進一步提出計數調整(Counter Adjustment)概念，設計適應性霍夫曼編碼雜湊樹建構/計數調整(Adaptive Huffman Coding Hash Tree Construction/Counter Adjustment; 簡稱AHCHTC/CA)演算法，在不破壞適應性霍夫曼編碼雜湊樹架構具兄弟特性(Sibling Property)的前提下變動雜湊樹所有節點的計數。不使用原先依據總更動計數的方式，改以檔案最近更動的計數為依據而建構雜湊樹。這更能貼近使用者的最近行為模式，而能進一步提昇演算法效能。 在實驗階段，我們以NCUCCWiki中網頁的更動模式以及SNIA (Storage Networking Industry Association) IOTTA (Input/output Traces, Tools, and Analysis) 中哈佛大學網路檔案系統檔案更動模式為對象，評估所提演算法的效能，並且與相關文獻提出的方法進行比較。實驗結果顯示，所提演算法不論在計算時間或是記憶空間方面都優於其他方法。本論文最後並提出針對實驗結果的觀察和所提演算法未來可能的應用場景。 ;Although cloud storage services are very popular nowadays, users have a problem that they do not have an effective way to prove the system is abnormal due to system errors. Users thus cannot claim a loss even when data or files are damaged by some kinds of internal errors. As a result, enterprise users often do not trust or even adopt cloud storage services due to the above-mentioned problem. We intend to design methods to solve the problem of cloud storage services. In this paper, we focus on the research of Proof of Violation (POV). All the updated files in cloud storage will be signed by users and service providers with digital signature, and their hash values are checked for detecting the occurrence of violations to ensure that both parties can trust each other. We propose Adaptive Huffman Coding Hash Tree Construction (AHCHTC) algorithm for the real-time POV of cloud storage services. The proposed algorithm dynamically adds and adjusts hash tree nodes according to the update counters of files. It consumes less execution time and memory space than an existing hash tree-based POV scheme. We further propose Adaptive Huffman Coding Hash Tree Construction/Counter Adjustment (AHCHTC/CA) algorithm to improve the AHCHTC algorithm by adjusting counters of all nodes associated with files while maintaining the hash tree structure to satisfy the sibling property. Thus, the AHCHTC/CA algorithm constructs the hash tree according to recent update counters, instead of total update counters. This can reflect recent file update patterns, and thus further improve the performance. Simulation experiments are conducted to evaluate the performance of the proposed algorithms is for the web page update patterns in NCUCCWiki and the file update patterns in the Harvard University network file system provided by SNIA (Storage Networking Industry Association) IOTTA (Input/output Traces, Tools, and Analysis) data set. The evaluated performance is compared with that of a related method. The comparisons show that the proposed algorithms are superior to the related method in terms of the computation time and the memory overhead. We also show some observations for the experimental results and possible application scenarios of the proposed algorithms.
