## Verification of the Security against Inference Attacks on XML Databases

## Chittaphone PHONHARATH (1051135)

We examine the decidability of 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 study, we investigate the decidability of the schema *k*-secrecy problem defined as follows: For a given XML database schema, an authorized query and unauthorized query, decide whether every database instances 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. We next show that the schema *∞*-secrecy problem is decidable for queries represented by linear deterministic top-down tree transducers. We give an algorithm for deciding the schema *∞*-secrecy problem and analyze its time complexity. Moreover, we adjust/extend the decision algorithm to the case that queries are given by linear deterministic bottom-up tree transducers and linear deterministic top-down tree transducers with regular look-ahead.