Security against Inference Attacks on Negative Information in Object-Oriented Databases

Yasunori ISHIHARA  Shuichiro AKO  Toru FUJIWARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.12   pp.2767-2776
Publication Date: 2005/12/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.12.2767
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Database
object-oriented database,  authorization,  inference attack,  negative information,  

Full Text: PDF(411.9KB)>>
Buy this Article

Inference attacks mean that a user derives information on the execution results of unauthorized queries from the execution results of authorized queries. Most of the studies on inference attacks so far have focused on only inference of positive information (i.e., what value is the execution result of a given unauthorized query). However, negative information (i.e., what value is never the execution result of a given unauthorized query) is also sensitive in many cases. This paper presents the following results on the security against inference attacks on negative information in object-oriented databases. First, inference of negative information is formalized under a model of object-oriented databases called method schemas. Then, the following two types of security problems are defined: (1) Is a given database instance secure against inference attacks on given negative information? (2) Are all of the database instances of a given database schema secure against inference attacks on given negative information? It is shown that the first problem is decidable in polynomial time in the description size of the database instance while the second one is undecidable. A decidable sufficient condition for any database instance of a given database schema to be secure is also proposed. Finally, it is shown that for a monadic schema (i.e., every method has exactly one parameter), this sufficient condition is also a necessary one.