Overview
Transaction-time support in a database allows it to store all the information that was ever entered into the system. Changed and deleted information can be retrieved at a later stage to check for mistakes or malicious act. In this project we have provided transaction-time support to BerkeleyDB with minimum memory overhead while maintaining the high performance of the original system.
One significant subproject concerns detecting tampering of a transaction-time table in BerkeleyDB and forensic analysis of such tampering once it has been detected. A transaction-time table can be considered to be a particularly robust form of audit log. Audit logs are considered good practice for business systems, and are required by federal regulations for secure systems, drug approval data, medical information disclosure, financial records, and electronic voting. Given the central role of audit logs, it is critical that they are correct and inalterable. It is not sufficient to say, "our data is correct, because we store all interactions in a separate audit log." The integrity of the audit log itself must also be guaranteed.
We have developed mechanisms within BerkeleyDB, based on cryptographically strong one-way hash functions, that prevent an intruder, including an auditor or an employee or even an unknown bug within the DBMS itself, from silently corrupting the audit log. The DBMS stores additional information in the database to enable a separate audit log validator to examine the database along with this extra information and state conclusively whether the audit log has been compromised. We have shown with our implementation that the overhead for auditing is low and that the validator can efficiently and correctly determine if the audit log has been compromised.
We also provide a systematic means of performing forensic analysis after such tampering has been uncovered, to determine who, when, and what. We have developed a schematic representation termed a "corruption diagram" that aids in intrusion investigation. We have developed successively more sophisticated forensic analysis algorithms: the monochromatic, RGB, and polychromatic algorithms, which can efficiently extract a good deal of information concerning a corruption event.
Here is a simple graphic illustrating our approach, created by Cheryl Ryan.
Active members (left to right): Huilong Huang, Qing Ju, Rick Snodgrass, Kyriacos Pavlou, Ricardo Carlos (Soumyadeb Mitra and Marianne Winslett not shown)
tBerkeleyDB group, Spring 2007 (left to right): Kyriacos Pavlou, Huilong Huang, Rick Snodgrass, Natasha Gaitonde, Man Zhang, Melinda Malmgren 