Deciding Schema k-Secrecy for XML Databases

Chittaphone PHONHARATH  Kenji HASHIMOTO  Hiroyuki SEKI  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.6   pp.1268-1277
Publication Date: 2013/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1268
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Static Analysis
inference attack,  security,  static analysis,  XML database,  

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

We study a static analysis problem on k-secrecy, which is a metric for the security against inference attacks on XML databases. Intuitively, k-secrecy means that the number of candidates of sensitive data of a given database instance or the result of unauthorized query cannot be narrowed down to k-1 by using available information such as authorized queries and their results. In this paper, we investigate the decidability of the schema k-secrecy problem defined as follows: for a given XML database schema, an authorized query and an unauthorized query, decide whether every database instance conforming to the given schema is k-secret. We first show that the schema k-secrecy problem is undecidable for any finite k>1 even when queries are represented by a simple subclass of linear deterministic top-down tree transducers (LDTT). We next show that the schema ∞-secrecy problem is decidable for queries represented by LDTT. We give an algorithm for deciding the schema ∞-secrecy problem and analyze its time complexity. We show the schema ∞-secrecy problem is EXPTIME-complete for LDTT. Moreover, we show similar results LDTT with regular look-ahead.