  Cloud DBs offer strong properties, including serializability, sometimes
called the gold standard database correctness property. But cloud DBs are
complicated black boxes, running in a different administrative domain from
their clients; thus, clients might like to know whether the DBs are meeting
their contract. A core difficulty is that the underlying problem here, namely
verifying serializability, is NP-complete. Nevertheless, we hypothesize that on
real-world workloads, verifying serializability is tractable, and we treat the
question as a systems problem, for the first time. We build Cobra, which tames
the underlying search problem by blending a new encoding of the problem,
hardware acceleration, and a careful choice of a suitable SMT solver. cobra
also introduces a technique to address the challenge of garbage collection in
this context. cobra improves over natural baselines by at least 10x in the
problem size it can handle, while imposing modest overhead on clients.
