Deciding Schema k-Secrecy for XML Databases
スポンサーリンク
概要
- 論文の詳細を見る
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.
著者
-
Seki Hiroyuki
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Hashimoto Kenji
Graduate School Of Creative Science And Engineering Waseda University
-
Phonharath Chittaphone
Graduate School Of Information Science Nara Institute Of Science And Technology
関連論文
- Verification of the Security against Inference Attacks on XML Databases
- A Formal Approach to Detecting Security Flaws in Object-Oriented Databases (Special Issue on New Generation Database Technologies)
- An Authorization Model for Object-Oriented Databases and Its Efficient Access Control
- Assignment of Data Types to Words in a Natural Language Specification
- Implementation of Natural Language Specifications of Communication Protocols by Executable Specifications
- RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
- RIGHT-LINEAR FINITE PATH OVERLAPPING REWRITE SYSTEMS EFFECTIVELY PRESERVE RECOGNIZABILITY
- A Polynomial Time Learning Algorithm for Recognizable Series
- A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars
- A Note on Inadequacy of the Model for Learning from Queries
- A Labeled Transition Model A-LTS for History-Based Aspect Weaving and Its Expressive Power
- New certificate chain discovery methods for trust establishment in ad hoc networks and their evaluation (特集:次世代社会基盤をもたらす高度交通システムとモバイル通信システム)
- Policy Controlled System and Its Model Checking
- Decidability of the Security Verification Problem for Programs with Stack Inspection
- Disturbance Compensation Control for a Biped Vehicle
- Tree Automaton with Tree Memory
- Static Analysis for k-secrecy against Inference Attacks
- An Efficient Method for Optimal Probe Deployment of Distributed IDS(Dependable Computing)
- RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
- Deciding Schema k-Secrecy for XML Databases
- A Static Analysis using Tree Automata for XML Access Control
- New Certificate Chain Discovery Methods for Trust Establishment in Ad Hoc Networks and Their Evaluation
- New Certificate Chain Discovery Methods for Trust Establishment in Ad Hoc Networks and Their Evaluation
- Runtime Control of a Program based on Quantitative Information Flow