In this article we present refinements on previously proposed approaches to forensic analysis of database tampering. We significantly generalize the basic structure of these algorithms to admit new characterizations of the “where” axis of the corruption diagram. Specifically, we introduce page-based partitioning as well as attribute-based partitioning along with their associated corruption diagrams. We compare the structure of all the forensic analysis algorithms and discuss the various design choices available with respect to forensic analysis. We characterize the forensic cost of the newly introduced algorithms, compare their forensic cost, and give our recommendations. We then introduce a comprehensive taxonomy of the types of possible corruption events, along with an associated forensic analysis protocol that consolidates all extant forensic algorithms and the corresponding type(s) of corruption events they detect. The result is a generalization of these algorithms and an overarching characterization of the process of database forensic analysis, thus providing a context within the overall operation of a DBMS for all existing forensic analysis algorithms.

Regulations and societal expectations have recently emphasized the need to mediate access to valuable databases, even access by insiders. Fraud occurs when a person, often an insider, tries to hide illegal activity. Companies would like to be assured that such tampering has not occurred, or if it does, that it will be quickly discovered and used to identify the perpetrator. At one end of the compliance spectrum lies the approach of restricting access to information and on the other that of information accountability. We focus on effecting information accountability of data stored in high-performance databases. The demonstrated work ensures appropriate use and thus end-to-end accountability of database information via a continuous assurance technology based on cryptographic hashing techniques. A prototype tamper detection and forensic analysis system named DRAGOON was designed and implemented to determine when tampering(s) occurred and what data were tampered with. DRAGOON is scalable, customizable, and intuitive. This work will show that information accountability is a viable alternative to information restriction for ensuring the correct storage, use, and maintenance of databases on extant DBMSes.

Information restriction controls access and renders records immutable, information accountability requires data transparency to easily and efficiently determine when a particular use is appropriate. Information accountability in the context of relational databases is associated with time in a surprising number of ways, as is summarized in this paper. Notarization and validation of a database exploit the temporal semantics of a transaction-time database. A corruption can be associated with multiple times. Forensic analysis determines the when: bounds on the corruption time, and the where: also specified in terms of time. These bounds are depicted in a two-dimensional corruption diagram, with both axes denoting time. The various kinds of corruption events are defined in terms of time. A parameter termed the regret interval has significant security and performance implications. This paper emphasizes the deep connections between time and the definition, detection, forensic analysis, and characterized extent of a database corruption within the context of information accountability.

Tampering of a database can be detected through the use of cryptographically strong hash functions. Subsequently, applied forensic analysis algorithms can help determine when, what, and perhaps ultimately who and why. This paper presents a novel forensic analysis algorithm, the tiled Bitmap algorithm, which is more efficient than prior forensic analysis algorithms. It introduces the notion of a candidate set (all possible locations of detected tampering(s)) and provides a complete characterization of the candidate set and its cardinality. An optimal algorithm for computing the candidate set is also presented. Finally, the implementation of the tiled Bitmap algorithm is discussed, along with a comparison to other forensic algorithms in terms of space/time complexity and cost. An example of candidate set generation and proofs of the theorems and lemmata and of algorithm correctness can be found in the appendix, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TKDE.2009.121.

Regulations and societal expectations have recently expressed the need to mediate access to valuable databases, even by insiders. One approach is tamper detection via cryptographic hashing. This article shows how to determine when the tampering occurred, what data was tampered with, and perhaps, ultimately, who did the tampering, via forensic analysis. We present four successively more sophisticated forensic analysis algorithms: the Monochromatic, RGBY, Tiled Bitmap, and a3D algorithms, and characterize their “forensic cost” under worst-case, best-case, and average-case assumptions on the distribution of corruption sites. A lower bound on forensic cost is derived, with RGBY and a3D being shown optimal for a large number of corruptions. We also provide validated cost formulæ for these algorithms and recommendations for the circumstances in which each algorithm is indicated.

Mechanisms now exist that detect tampering of a database, through the use of cryptographically-strong hash functions. This paper addresses the next problem, that of determining who, when, and what, by providing a systematic means of performing forensic analysis after such tampering has been uncovered. We introduce a schematic representation termed a "corruption diagram" that aids in intrusion investigation. We use these diagrams to fully analyze the original proposal, that of a linked sequence of hash values. We examine the various kinds of intrusions that are possible, including retroactive, introactive, backdating, and postdating intrusions. We then introduce successively more sophisticated forensic analysis algorithms: the monochromatic, RGB, and polychromatic algorithms, and characterize the "forensic strength" of these algorithms. We show how forensic analysis can efficiently extract a good deal of information concerning a corruption event.