The inference problem: Maintaining maximal availability in the presence of database updates

In this paper, we present the Dynamic Disclosure Monitor (D2Mon) architecture to prevent illegal inferences via database constraints. D2Mon extends the functionality of Disclosure Monitor (DiMon) to address database updates while preserving the soundness and completeness properties of the inference algorithms. We study updates from the perspective of increasing data availability. That is, updates on tuples that were previously released may affect the correctness of the user inferences over these tuples. We develop a mechanism, called Update Consolidator (UpCon), that propagates updates to a history file to ensure that no query is rejected based on inferences derived from outdated data. The history file is used by the Disclosure Inference Engine (DiIE) to compute inferences. We show that UpCon and DiIE working together guarantee confidentiality (completeness property of the data-dependent disclosure inference algorithm) and maximal availability (soundness property of the data-dependent disclosure inference algorithm) even in the presence of updates. We also present our implementation of D2Mon and our empirical results.