Auditing and Inference Control in Statistical Databases.

A statistical database (SDB) may be defined as an ordinary database with the capability of providing statistical information to user queries. The security problem for the SDB is to limit the use of the SDB so that only statistical information is available and no sequence of queries is sufficient to infer protected information about any individual. When such information is obtained, the SDB is said to be compromised. Inference control mechanisms are internal protection mechanisms applied to SDB's. Many researchers have studied different protection mechanisms to prevent an SDB from being compromised. However, most of these mechanisms are either ineffective or inefficient or are only applicable to large SDB's. Auditing in SDB's is initially proposed in the form of investigating log trails manually. In this paper, we present a practical technique for managing the past history of user's queries, discuss how the sequence of all the answered queries of the SDB can be reduced and stored in finite storage, and describe how this storage scheme can provide an effective way of checking compromise. We believe that this will help us develop a more practical and efficient tool for protection in a small SDB than the previously known mechanisms. Further, we extend the idea to checking compromise of a set of queries in a more efficient way than one query at a time. We also show that the problem of maximizing the amount of information to the users without compromising the SDB is NP-complete. [ABSTRACT FROM AUTHOR]