Decidability of the Security against Inference Attacks Using a Functional Dependency on XML Databases


IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.5   pp.1365-1374
Publication Date: 2012/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.1365
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Database Security
XML database,  inference attack,  security,  verification,  functional dependency,  

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

This paper discusses verification of the security against inference attacks on XML databases in the presence of a functional dependency. So far, we have provided the verification method for k-secrecy, which is a metric for the security against inference attacks on databases. Intuitively, k-secrecy means that the number of candidates of sensitive data (i.e., the result of unauthorized query) of a given database instance cannot be narrowed down to k-1 by using available information such as authorized queries and their results. In this paper, we consider a functional dependency on database instances as one of the available information. Functional dependencies help attackers to reduce the number of the candidates for the sensitive information. The verification method we have provided cannot be naively extended to the k-secrecy problem with a functional dependency. The method requires that the candidate set can be captured by a tree automaton, but the candidate set when a functional dependency is considered cannot be always captured by any tree automaton. We show that the ∞-secrecy problem in the presence of a functional dependency is decidable when a given unauthorized query is represented by a deterministic topdown tree transducer, without explicitly computing the candidate set.