Databases Reference
In-Depth Information
the theory can certainly be extended to handle blind writes. At the transac-
tion level, an application (e.g., the application types shown in Figure 2) is a
transaction execution
history
. Since recovery of uncommitted transactions is
addressed by standard mechanisms [3], we can safely ignore aborted transac-
tions and only consider the committed
projection C
(
H
) of every history
H
.
We define
<
H
to be the usual partial order on
C
(
H
), namely,
T
i
<
H
T
j
if
<
H
orders operations of
T
i
before conflicting operations of
T
j
(Note that in
H
the operations of different transactions are often interleaved). Two operations
conflict
if they are on the same data object and one is write.
In principle, the
correctness
of a DQR scheme (or solution) can be
“checked” either by the operations performed by the scheme or by the re-
sulted effects. Here, we use the resulted history of a DQR scheme to study
its correctness. In our model, the DQR histories resulted from a DQR scheme
may contain the following information:
•
A DQR history may contain two types of
malicious
transactions, four
types of
legitimate
transactions, and one type of
cleaning
transactions:
Type 1 malicious transactions are issued by attackers or malicious code;
more broadly, transactions executed by mistake can be viewed as a Type
2 malicious transaction A legitimate transaction may be either a
regular
transaction or a
reexecuted
transaction; and both regular and reexecuted
transactions may be
affected
or
damaged
if they read any corrupted data
object. Finally, cleaning transactions only contain backward or forward
overwrite operations, depending upon how the recovery is performed.
•
A classic history consists of only operations, while a DQR history is an
interleaved sequence of operations and data store states. The
data store
contains all the data objects that a transaction may access. The
state
of
the data store at time
t
is determined by the latest committed values of
every data object in the store.
•
A data store state (e.g., a database state) contains three types of
cor-
rupted
data objects and two types of
clean
data objects. Type 1 corrupted
data objects are originally generated by the writes of malicious transac-
tions. Type 2 are originally generated by affected transactions. Type 3 are
originally generated by non-transactional attacking actions outside of the
application's transaction scope. Note that a corrupted data object may be
read or updated several times before it is
repaired
(a.k.a.
cleaned
). Type
1 clean data objects are never corrupted. Type 2 clean data objects are
once corrupted, but they are repaired.
Damage Propagation
Based on the threat model, we know where malicious transactions come from.
To see how affected transactions are generated and how the damage spreads,
we should do dependency (or causality) analysis.
Definition 4.1 (dependency graph)
As stated in [68], transaction
T
j
is
dependent upon T
i
in a history if there exists a data object
o
such that
T
j
