Digital repositories, either digital preservation systems or archival systems, periodically check the integrity of stored objects to assure users of their correctness. To do so, prior solutions calculate integrity metadata and require the repository to store it alongside the actual data objects. This integrity metadata is essential for regularly verifying the correctness of the stored data objects. To safeguard and detect damage to this metadata, prior solutions rely on widely visible media, that is unaffiliated third parties, to store and provide back digests of the metadata to verify it is intact. However, they do not address recovery of the integrity metadata in case of damage or attack by an adversary. In essence, they do not preserve this metadata. We introduce IntegrityCatalog, a system that collects all integrity related metadata in a single component, and treats them as first class objects, managing both their integrity and their preservation. We introduce a treap-based persistent authenticated dictionary managing arbitrary length key value pairs, which we use to store all integrity metadata, accessible simply by object name. Additionally, IntegrityCatalog is a distributed system that includes a network protocol that manages both corruption detection and preservation of this metadata, using administrator-selected network peers with two possible roles. Verifiers store and offer attestations on digests and have minimal storage requirements, while preservers efficiently synchronize a complete copy of the catalog to assist in recovery in case of a detected catalog compromise on the local system. We describe our prototype implementation of IntegrityCatalog, measure its performance empirically, and demonstrate its effectiveness in real-world situations, with worst measured throughput of approximately 1K insertions per second, and 2K verified search operations per second.
Persistence was studied thoroughly by in @cite_22 . used the node copying technique to introduce a persistent authenticated search tree in @cite_44 , using a multi-key tree (B- Tree), which can be converted to a dictionary with some additional work. However, space requirements quickly become prohibitive as any change in a snapshot requires complete B- Tree page copies. introduced the Persistent Authenticated Dictionary (PAD) concept in @cite_26 , using a persistent Red-Black tree and node copying. More recently, in @cite_24 @cite_17 Crosby and Wallach studied the subject of PADs and suggested different techniques to implement them, including the treap @cite_14 with its set-unique property, as well a discussion about authenticator caching, which influenced our design decisions. However, this line of work never studied the impact of secondary memory on these data structures as all experiments were done in main memory.
@cite_26 @cite_14 @cite_22 @cite_44 @cite_24 @cite_17
2403712541 2096252661 1512285202 1579315492
Many proposals for managing replicated data use sites running the Snapshot Isolation (SI) concurrency control mechanism, and provide 1-copy SI or something similar, as the global isolation level. This allows good scalability, since only ww-conflicts need to be managed globally. However, 1-copy SI can lead to data corruption and violation of integrity constraints [5]. 1-copy serializability is the global correctness condition that prevents data corruption. We propose a new algorithm Replicated Serializable Snapshot Isolation (RSSI) that uses SI at each site, and combines this with a certification algorithm to guarantee 1-copy serializable global execution. Management of ww-conflicts is similar to what is done in 1-copy SI. But unlike previous designs for 1-copy serializable systems, we do not need to prevent all rw-conflicts among concurrent transactions. We formalize this in a theorem that shows that many rw-conflicts are indeed false positives that do not risk non-serializable behavior. Our proposed RSSI algorithm will only abort a transaction when it detects a well-defined pattern of two consecutive rw-edges in the serialization graph. We have built a prototype that integrates our RSSI with the existing open-source PostgresR(SI) system. Our performance evaluation shows that there is a worst-case overhead of about 15 for getting full 1copy serializability as compared to 1-copy SI in a cluster of 8 nodes, with our proposed RSSI clearly outperforming the previous work [6] for update-intensive workloads. Restoration of writing order from a single-stroked handwriting image can be seen as the problem of finding the smoothest path in its graph representation. In this paper, a 3-phase approach to restore a writing order is proposed within the framework of the edge continuity relation (ECR). In the initial, local phase, in order to obtain possible ECRs at an even-degree node, a neural network is used for the node of degree 4 and a theoretical approach is presented for the node of degree higher than 4 by introducing certain reasonable assumptions. In the second phase, we identify double-traced lines by employing maximum weighted matching. This makes it possible to transform the problem of obtaining possible ECRs at odd-degree node to that at even-degree node. In the final, global phase, we find all the candidates of single-stroked paths by depth first search and select the best one by evaluating SLALOM smoothness. Experiments on static images converted from online data in the Unipen database show that our method achieves a restoration rate of 96.0 percent A prototype implementation of a mechanism that uses fingerprints to identify exact repetitions of text in large program source trees has been built and successfully applied to a legacy source of over 300 megabytes. This prototype system has provided useful information as well as establishing the scalability of the technology. The approach will form the basis of a suite of tools for the visualization and understanding of programs and will complement other approaches currently under investigation. Many real-world applications run on untrusted servers or are run on servers that are subject to strong insider attacks. Although we cannot prevent an untrusted server from modifying or deleting data, with tamper-evident data structures, we can discover when this has occurred. If an untrusted server knows that a particular reply will not be checked for correctness, it is free to lie. Auditing for correctness is thus a frequent but overlooked operation. In my thesis, I present and evaluate new efficient data structures for tamper-evident logging and tamper-evident storage of changing data on untrusted servers, focussing on the costs of the entire system. The first data structure is a new tamper-evident log design. I propose new semantics of tamper-evident logs in terms of the auditing process, required to detect misbehavior. To accomplish efficient auditing, I describe and benchmark a new tree-based data structure that can generate such proofs with logarithmic size and space, significantly improving over previous linear constructions while also offering a flexible query mechanism with authenticated results. The remaining data structures are designs for a persistent authenticated dictionary (PAD) that allows users to send lookup requests to an untrusted server and get authenticated answers, signed by a trusted author, for both the current and historical versions of the dataset. Improving on prior constructions that require logarithmic storage and time, I present new classes of efficient PAD algorithms offering constant-sized authenticated answers or constant storage per update. I implement 21 different versions of PAD algorithms and perform a comprehensive evaluation using contemporary cloud-computing prices for computing and bandwidth to determine the most monetarily cost-effective designs.