Detecting Suspicious Relational Database Queries

Whenever secret information has been shared among multiple partners and has been illegally leaked to a third party, it is important for the trust among the partners to identify the information leak. We present a forensic approach to privacy violation control that after information has been leaked identifies those partners that had access to the leaked information. Our approach represents secret information as a boolean formula and compares it with the queries and the relational database state to which the queries were applied. We use this technique to identify suspicious queries, i.e., queries that have got sufficient information to infer secret information that has been leaked. Furthermore, we prove that checking where a select-project query is suspicious with respect to a given secret information is NP-complete, but a polynomial time solution exists for interesting subclasses.