tailieunhanh - Efficient Data Structures for Tamper-Evident Logging

The preceding section discussed the basic concepts of an investigation and it never used the word forensic. To determine where, if at all, the term forensic can be applied we will first consult its definition. The American Heritage Dictionary defines forensic as an adjective and “relating to the use of science or technology in the investigation and establishment of facts or evidence in a court of law [Hou00].” Therefore, to be considered forensic, a process must use science and technology and the results must be able to be used in a court of law | Efficient Data Structures for Tamper-Evident Logging Scott A. Crosby Dan S. Wallach scrosby@ dwallach@ Department of Computer Science Rice University Abstract Many real-world applications wish to collect tamper-evident logs for forensic purposes. This paper considers the case of an untrusted logger serving a number of clients who wish to store their events in the log and kept honest by a number of auditors who will challenge the logger to prove its correct behavior. We propose semantics of tamper-evident logs in terms of this auditing process. The logger must be able to prove that individual logged events are still present and that the log as seen now is consistent with how it was seen in the past. To accomplish this efficiently we describe a tree-based data structure that can generate such proofs with logarithmic size and space improving over previous linear constructions. Where a classic hash chain might require an 800 MB trace to prove that a randomly chosen event is in a log with 80 million events our prototype returns a 3 KB proof with the same semantics. We also present a flexible mechanism for the log server to present authenticated and tamper-evident search results for all events matching a predicate. This can allow large-scale log servers to selectively delete old events in an agreed-upon fashion while generating efficient proofs that no inappropriate events were deleted. We describe a prototype implementation and measure its performance on an 80 million event syslog trace at 1 750 events per second using a single CPU core. Performance improves to 10 500 events per second if cryptographic signatures are offloaded corresponding to TB of logging throughput per week. 1 Introduction There are over 10 000 . regulations that govern the storage and management of data 22 58 . Many countries have legal financial medical educational and privacy regulations that require businesses to retain a variety of records. Logging systems are .