Auditing Inference Based Disclosures in Dynamic Databases

A privacy violation in an information system could take place either through explicit access or inference over already revealed facts using domain knowledge. In a post violation scenario, an auditing framework should consider both these aspects to determine exact set of minimal suspicious queries set. Update operations in database systems add more complexity in case of auditing, as inference rule applications on different data versions may generate erroneous information in addition to the valid information. In this paper, we formalize the problem of auditing inference based disclosures in dynamic databases, and present a sound and complete algorithm to determine a suspicious query set for a given domain knowledge, a database, an audit query, updates in the database. Each element of the output set is a minimal set of past user queries made to the database system such that data revealed to these queries combined with domain knowledge can infer the valid data specified by the audit query.