Transaction-Time Support, Auditing, Forensic Analysis, and
Compliant Databases: 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
a3D 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.
We are now broadening this research to complement the existing market
for compliance storage servers , which guarantee that data are not
overwritten before the end of their mandatory retention period. These
servers are intended for preserving unstructured and semi-structured data
at a file-level granularity---email, spreadsheets, reports, instant
messages.
With Radu Sion and
Marianne
Winslett, we are developing a DBMS architecture that supports a spectrum of
approaches to regulatory compliance, each appropriate for a particular
domain, and each with different tradeoffs between security and
efficiency. The key challenge of this work is to provide compliance
assurances for the DBMS, even against insiders with superuser powers,
while balancing the need for trustworthiness against the conflicting
requirements for high performance and low cost. To meet this need, our
architecture will provide tunable tradeoffs between security and
performance, through a spectrum of techniques ranging from tamper
detection to tamper prevention for data, indexes, logs, and metadata;
tunable vulnerability windows; tunable granularities of protection;
careful use of magnetic disk as a cache; judicious use of secure
coprocessors on the DBMS platform and compliance storage server platform;
a block-based compliance storage server; and judicious retargeting of an
on-disk encryption unit.
People
Faculty:
Radu Sion
Richard T.Snodgrass (Director)
Marianne Winslett
Graduate Students:
Ricardo Carlos
Qing Ju (Chief Programmer)
Kyriacos Pavlou
Undergraduate Students:
Michael Patterson
Previous Faculty:
Christian S. Collberg
Previous Graduate Students:
Natasha Gaitonde
Haifeng He
Huilong Huang
Yong Liang
Yuhong Liu
Kalyani Mandapaka
Supratik Maitra
Soumyadeb Mitra
Mingde Qiu
Manigantan Sethuraman
Shilong (Stanley) Yao
Seunghwan You
Man Zhang
Previous Undergraduate Students:
Melinda Malmgren
Active members (left to right): Huilong Huang, Qing Ju, Rick Snodgrass, Kyriacos Pavlou, Ricardo Carlos (Soumyadeb Mitra and Marianne Winslett not shown)
Photo by Rui Zhang
tBerkeleyDB group, Spring 2007 (left to right): Kyriacos Pavlou, Huilong Huang, Rick Snodgrass, Natasha Gaitonde, Man Zhang, Melinda Malmgren
Photo by Praveen Rao
Funding
Publications
Soumyadeb Mitra, Marianne Winslett, Richard T. Snodgrass, and Shashank
Yaduvanshi, "An Architecture for Regulatory Compliant Database
Management," to appear in Proceedings of the International Conference on
Data Engineering (ICDE), 12 pages, Shanghai, China, 2009.
Kyri Pavlou and Richard T. Snodgrass, "Forensic Analysis of Database
Tampering," to appear in the ACM Transactions on Database Systems, 45+26
pages, December 2008. (pdf)
Melinda Malmgren, "An Infrastructure for Database Tamper Detection and
Forensic Analysis," Honors Thesis, University of Arizona, May 2007
(pdf).
Kyri Pavlou and Richard. T. Snodgrass, "The Pre-images of Bitwise AND
Functions in Forensic Analysis,'' TimeCenter TR 87, October, 2006.
(pdf)
Kyri Pavlou and Richard T. Snodgrass, "Forensic Analysis of Database
Tampering," in Proceedings of the ACM SIGMOD International Conference on
Management of Data (SIGMOD), pages 109-120, Chicago, June, 2006. (pdf)
David Lomet, Richard T. Snodgrass, and Christian S. Jensen, "Exploiting the
Lock Manager for Timestamping," in Proceedings of the Ninth International
Database Engineering and Applications Symposium (IDEAS 2005), Montreal,
Canada, July 2005. (pdf)
Richard T. Snodgrass, Stanley Yao and Christian Collberg, "Tamper Detection in Audit Logs," In Proceedings of the International Conference on Very Large Databases,
Toronto, Canada, August–September 2004, pp. 504–515. (pdf)
Mani Sethuraman, "Implementation and Evaluation of a Partitioned Store for
Transaction-Time Databases," TimeCenter TR-76,
December 2003. (pdf)
Link to Internal resources
Implementation of Forensic Analysis Algorithms
The ForensicAnalysis.tar.gz
file contains a C implementation of four forensic analysis
algorithms we developed: Monochromatic, RGBY, Tiled Bitmap, and a3D.
News
"Keeping Your DBA Honest"
(webpage)
"UA Shares NSF Grant for Research on Securing Databases"
(webpage)
Webmaster: Qing Ju
