Deciding Schema <I>k</I>-Secrecy for XML Databases

Chittaphone PHONHARATH; Kenji HASHIMOTO; Hiroyuki SEKI

doi:10.1587/transinf.E96.D.1268

Deciding Schema k-Secrecy for XML Databases

Chittaphone PHONHARATH, Kenji HASHIMOTO, Hiroyuki SEKI

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.6 pp.1268-1277

Publication Date: 2013/06/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.1268

Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)

Category: Static Analysis

Authors

Chittaphone PHONHARATH
  Nara Institute of Science and Technology
Kenji HASHIMOTO
  Nara Institute of Science and Technology
Hiroyuki SEKI
  Nara Institute of Science and Technology

Keyword

inference attack, security, static analysis, XML database

Cite this

Copy

Chittaphone PHONHARATH, Kenji HASHIMOTO, Hiroyuki SEKI, "Deciding Schema k-Secrecy for XML Databases" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 6, pp. 1268-1277, June 2013, doi: 10.1587/transinf.E96.D.1268.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1268/_p

Copy

@ARTICLE{e96-d_6_1268,
author={Chittaphone PHONHARATH, Kenji HASHIMOTO, Hiroyuki SEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Deciding Schema k-Secrecy for XML Databases},
year={2013},
volume={E96-D},
number={6},
pages={1268-1277},
abstract={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.},
keywords={},
doi={10.1587/transinf.E96.D.1268},
ISSN={1745-1361},
month={June},}

Copy

TY - JOUR
TI - Deciding Schema k-Secrecy for XML Databases
T2 - IEICE TRANSACTIONS on Information
SP - 1268
EP - 1277
AU - Chittaphone PHONHARATH
AU - Kenji HASHIMOTO
AU - Hiroyuki SEKI
PY - 2013
DO - 10.1587/transinf.E96.D.1268
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2013
AB - 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.
ER -