Database audit workload prioritization via game theory

Chao Yan, Bo Li, Yevgeniy Vorobeychik, Aron Laszka, Daniel Fabbri, Bradley Malin

Research output: Contribution to journalArticle

Abstract

The quantity of personal data that is collected, stored, and subsequently processed continues to grow rapidly. Given its sensitivity, ensuring privacy protections has become a necessary component of database management. To enhance protection, a number of mechanisms have been developed, such as audit logging and alert triggers, which notify administrators about suspicious activities. However, this approach is limited. First, the volume of alerts is often substantially greater than the auditing capabilities of organizations. Second, strategic attackers can attempt to disguise their actions or carefully choose targets, thus hide illicit activities. In this article, we introduce an auditing approach that 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. Specifically, we model the interaction between a database auditor and attackers as a Stackelberg game. We show that even a highly constrained version of such problem is NP-Hard. Then, we introduce a method that combines linear programming, column generation, and heuristic searching to derive an auditing policy. On the synthetic data, we perform an extensive evaluation on the approximation degree of our solution with the optimal one. The two real datasets, (1) 1.5 months of audit logs from Vanderbilt University Medical Center and (2) a publicly available credit card application dataset, are used to test the policy-searching performance. The findings demonstrate the effectiveness of the proposed methods for searching the audit strategies, and our general approach significantly outperforms non-game-theoretic baselines.

Original languageEnglish (US)
Article number17
JournalACM Transactions on Privacy and Security
Volume22
Issue number3
DOIs
StatePublished - Jun 10 2019

Fingerprint

Game theory
Data privacy
Linear programming
Computational complexity

Keywords

  • Anomaly detection
  • Data privacy
  • Database auditing
  • Game theory

ASJC Scopus subject areas

  • Computer Science(all)
  • Safety, Risk, Reliability and Quality

Cite this

Database audit workload prioritization via game theory. / Yan, Chao; Li, Bo; Vorobeychik, Yevgeniy; Laszka, Aron; Fabbri, Daniel; Malin, Bradley.

In: ACM Transactions on Privacy and Security, Vol. 22, No. 3, 17, 10.06.2019.

Research output: Contribution to journalArticle

Yan, C, Li, B, Vorobeychik, Y, Laszka, A, Fabbri, D & Malin, B 2019, 'Database audit workload prioritization via game theory', ACM Transactions on Privacy and Security, vol. 22, no. 3, 17. https://doi.org/10.1145/3323924
Yan, Chao ; Li, Bo ; Vorobeychik, Yevgeniy ; Laszka, Aron ; Fabbri, Daniel ; Malin, Bradley. / Database audit workload prioritization via game theory. In: ACM Transactions on Privacy and Security. 2019 ; Vol. 22, No. 3.
@article{9246dbfc8e974fc7a99961574bf0bc93,
title = "Database audit workload prioritization via game theory",
abstract = "The quantity of personal data that is collected, stored, and subsequently processed continues to grow rapidly. Given its sensitivity, ensuring privacy protections has become a necessary component of database management. To enhance protection, a number of mechanisms have been developed, such as audit logging and alert triggers, which notify administrators about suspicious activities. However, this approach is limited. First, the volume of alerts is often substantially greater than the auditing capabilities of organizations. Second, strategic attackers can attempt to disguise their actions or carefully choose targets, thus hide illicit activities. In this article, we introduce an auditing approach that 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. Specifically, we model the interaction between a database auditor and attackers as a Stackelberg game. We show that even a highly constrained version of such problem is NP-Hard. Then, we introduce a method that combines linear programming, column generation, and heuristic searching to derive an auditing policy. On the synthetic data, we perform an extensive evaluation on the approximation degree of our solution with the optimal one. The two real datasets, (1) 1.5 months of audit logs from Vanderbilt University Medical Center and (2) a publicly available credit card application dataset, are used to test the policy-searching performance. The findings demonstrate the effectiveness of the proposed methods for searching the audit strategies, and our general approach significantly outperforms non-game-theoretic baselines.",
keywords = "Anomaly detection, Data privacy, Database auditing, Game theory",
author = "Chao Yan and Bo Li and Yevgeniy Vorobeychik and Aron Laszka and Daniel Fabbri and Bradley Malin",
year = "2019",
month = "6",
day = "10",
doi = "10.1145/3323924",
language = "English (US)",
volume = "22",
journal = "ACM Transactions on Privacy and Security",
issn = "2471-2566",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

TY - JOUR

T1 - Database audit workload prioritization via game theory

AU - Yan, Chao

AU - Li, Bo

AU - Vorobeychik, Yevgeniy

AU - Laszka, Aron

AU - Fabbri, Daniel

AU - Malin, Bradley

PY - 2019/6/10

Y1 - 2019/6/10

N2 - The quantity of personal data that is collected, stored, and subsequently processed continues to grow rapidly. Given its sensitivity, ensuring privacy protections has become a necessary component of database management. To enhance protection, a number of mechanisms have been developed, such as audit logging and alert triggers, which notify administrators about suspicious activities. However, this approach is limited. First, the volume of alerts is often substantially greater than the auditing capabilities of organizations. Second, strategic attackers can attempt to disguise their actions or carefully choose targets, thus hide illicit activities. In this article, we introduce an auditing approach that 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. Specifically, we model the interaction between a database auditor and attackers as a Stackelberg game. We show that even a highly constrained version of such problem is NP-Hard. Then, we introduce a method that combines linear programming, column generation, and heuristic searching to derive an auditing policy. On the synthetic data, we perform an extensive evaluation on the approximation degree of our solution with the optimal one. The two real datasets, (1) 1.5 months of audit logs from Vanderbilt University Medical Center and (2) a publicly available credit card application dataset, are used to test the policy-searching performance. The findings demonstrate the effectiveness of the proposed methods for searching the audit strategies, and our general approach significantly outperforms non-game-theoretic baselines.

AB - The quantity of personal data that is collected, stored, and subsequently processed continues to grow rapidly. Given its sensitivity, ensuring privacy protections has become a necessary component of database management. To enhance protection, a number of mechanisms have been developed, such as audit logging and alert triggers, which notify administrators about suspicious activities. However, this approach is limited. First, the volume of alerts is often substantially greater than the auditing capabilities of organizations. Second, strategic attackers can attempt to disguise their actions or carefully choose targets, thus hide illicit activities. In this article, we introduce an auditing approach that 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. Specifically, we model the interaction between a database auditor and attackers as a Stackelberg game. We show that even a highly constrained version of such problem is NP-Hard. Then, we introduce a method that combines linear programming, column generation, and heuristic searching to derive an auditing policy. On the synthetic data, we perform an extensive evaluation on the approximation degree of our solution with the optimal one. The two real datasets, (1) 1.5 months of audit logs from Vanderbilt University Medical Center and (2) a publicly available credit card application dataset, are used to test the policy-searching performance. The findings demonstrate the effectiveness of the proposed methods for searching the audit strategies, and our general approach significantly outperforms non-game-theoretic baselines.

KW - Anomaly detection

KW - Data privacy

KW - Database auditing

KW - Game theory

UR - http://www.scopus.com/inward/record.url?scp=85069779135&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069779135&partnerID=8YFLogxK

U2 - 10.1145/3323924

DO - 10.1145/3323924

M3 - Article

AN - SCOPUS:85069779135

VL - 22

JO - ACM Transactions on Privacy and Security

JF - ACM Transactions on Privacy and Security

SN - 2471-2566

IS - 3

M1 - 17

ER -