Auditing Interval-Based Inference

The result shows that it is intractable to audit interval-based inference for bounded integer values; while for bounded real values, the auditing problem is polynomial yet involves complicated computation of mathematical programming.

Abstract

In this paper we study the feasibility of auditing interval-based inference. Sensitive information about individuals is said to be compromised if an accurate enough interval, called inference interval, is obtained into which the value of the sensitive information must fall. Compared with auditing exact inference that is traditionally studied, auditing interval-based inference is more complicated. Existing auditing methods such as audit expert do not apply to this case. Our result shows that it is intractable to audit interval-based inference for bounded integer values; while for bounded real values, the auditing problem is polynomial yet involves complicated computation of mathematical programming. To further examine the practicability of auditing interval-based inference, we classify various auditing methods into three categories: exact auditing, optimistic auditing, and pessimistic auditing. We analyze the trade-offs that can be achieved by these methods among various auditing objectives: inference security, database usability, and auditing complexity.