Kolloquiumsvortrag, Prof. Dr. Joachim Biskup, TU Dortmund, Fakultät für Informatik / 22.04.2016
22.04.2016 von 14:15 bis 15:45
Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K
Titel: Publishing Inference-Proof Relational Data: Design, Implementation, Optimization and Experiments
Abstract:
An agent might want to share information maintained by a relational database by means of data publishing, i.e., by generating a view customized for the further unrestricted usage by the anticipated clients. Often, however, the usability of the view has to be confined to ensure the confidentiality of particular pieces of information in need of being excluded from sharing. Within the framework of Controlled Interaction Execution, we have designed a sound and complete generation procedure for an inference-proof (i.e., consistent and confidentiality-preserving) view that has minimal distortion distance to the original database instance. Confidentiality is achieved regarding a policy declared in terms of first-order logic sentences to be kept hidden. Consistency ensures the compliance with postulated a priori knowledge of the clients, expressed as first-order logic sentences, too. Conceptually, the generation procedure performs a depth-first search for satisfying the constraints and follows a branch-and-bound strategy for minimizing distortions. We have further provided an actual implementation of the generation procedure together with several optimizations. In particular, we exploited sophisticated local lower bounds on the number of additional distortions in subtrees to be explored to prune them early, and we employed coordinated parallelization for searching in many subtrees concurrently. Moreover, we have performed an experimental evaluation in terms of runtime behavior. Finally, we have also explored to replace depth-first searching by priority searching, exhibited special cases that can be handled more efficiently, considered heuristics for only approximating distortion minimality, and explored options of refined mechanisms to employ and invent constants to resolve current violations of constraints.
The original design was joint work with Lena Wiese (J. Biskup/L. Wiese, Journal of Computer Security 16 (2008) 477–494; L. Wiese, Dissertation, TU Dortmund 2009; J. Biskup, L. Wiese, Theoretical Computer Science 412 (2011) 4044–4072).
The implementation, the optimizations and the evaluation are joint work with Christine Dahn, Katharina Diekmann, Ralf Menzel, Dirk Schalge und Lena Wiese (manuscript submitted for publication).