  For enhancing the privacy protections of databases, where the increasing
amount of detailed personal data is stored and processed, multiple mechanisms
have been developed, such as audit logging and alert triggers, which notify
administrators about suspicious activities; however, the two main limitations
in common are: 1) the volume of such alerts is often substantially greater than
the capabilities of resource-constrained organizations, and 2) strategic
attackers may disguise their actions or carefully choosing which records they
touch, making incompetent the statistical detection models. For solving them,
we introduce a novel approach to database auditing that explicitly accounts for
adversarial behavior by 1) prioritizing the order in which types of alerts are
investigated and 2) providing an upper bound on how much resource to allocate
for each type. We model the interaction between a database auditor and
potential attackers as a Stackelberg game in which the auditor chooses an
auditing policy and attackers choose which records to target. A corresponding
approach combining linear programming, column generation, and heuristic search
is proposed to derive an auditing policy. For testing the policy-searching
performance, a publicly available credit card application dataset are adopted,
on which it shows that our methods produce high-quality mixed strategies as
database audit policies, and our general approach significantly outperforms
non-game-theoretic baselines.
