An Analysis of Complexity of Insider Attacks to Databases

Insider attacks are one of the most dangerous threats to an organization. Unfortunately, they are very difficult to foresee, detect, and defend against due to the trust and responsibilities placed on the employees. In this article, we first define the notion of user intent and construct a model for a common scenario that poses a very high risk for sensitive data stored in the organization's database. We show that the complexity of identifying pseudo-intents of a user in this scenario is coNP-Complete, and launching a harvester insider attack within the boundaries of the defined threat model takes linear time while a targeted threat model is an NP-Complete problem. We also discuss the general defense mechanisms against the modeled threats and show that countering the harvester insider attack takes quadratic time while countering the targeted insider attack can take linear to quadratic time, depending on the strategy chosen. We analyze the adversarial behavior and show that launching an attack with minimum risk is also an NP-Complete problem. Finally, we perform timing experiments with the defense mechanisms on SQL query workloads collected from a national bank to test the feasibility of using these systems in real time.