Rewriting histories: Recovering from malicious transactions

We consider recovery from malicious but committed transactions. Traditional recovery mechanisms do not address this problem, except for complete rollb acks, which undo the work of good transactions as well as malicious ones, a nd compensating transactions, whose utility depends on application semantic s. We develop an algorithm that rewrites execution histories for the purpos e of backing out malicious transactions. Good transactions that are affecte d, directly or indirectly, by malicious transactions complicate the process of backing out undesirable transactions. We show that the prefix of a rewr itten history produced by the algorithm serializes exactly the set of unaff ected good transactions. The suffix of the rewritten history includes speci al state information to describe affected good transactions as well as mali cious transactions. We describe techniques that can extract additional good transactions from this latter part of a rewritten history. The latter proc essing saves more good transactions than is possible with a dependency-grap h based approach to recovery.