Inference-proof materialized views

Abstract

Obwohl die Veröffentlichung von Daten heutzutage allgegenwärtig ist, ist diese häufig nur dann gestattet, wenn dabei Vertraulichkeitsanforderungen beachtet werden. Vor diesem Hintergrund wird in dieser Arbeit ein Ansatz entwickelt, um abgeschwächte Sichten auf gegebene Datenbankinstanzen zu erzeugen. Eine solche abgeschwächte Sicht ist dabei inferenzsicher im Sinne der sogenannten "Kontrollierten Interaktionsauswertung" und verhindert damit beweisbar, dass ein Angreifer vertrauliche Information erlangen kann – selbst dann, wenn dieser Angreifer versucht, diese Information unter Zuhilfenahme seiner Kenntnis über den Sicherheitsmechanismus und etwaigem Vorwissen über die Datenbankinstanz oder allgemeine Sachverhalte logisch zu erschließen.

Dieses Ziel wird innerhalb einer logik-orientierten Modellierung verwirklicht, in der alles sichere Wissen, das die Vertraulichkeitspolitik verletzt, (soweit möglich) durch schwächere, aber dennoch wahre Disjunktionen bestehend aus Elementen der Vertraulichkeitspolitik ersetzt wird. Auch wenn dieses disjunktive Wissen bewusst Unsicherheit über vertrauliche Information erzeugt, stellt es dennoch mehr Information als eine vollständige Geheimhaltung von vertraulicher Information bereit. Um dabei sicherzustellen, dass Disjunktionen im Hinblick auf ein betrachtetes Einsatzszenario sowohl glaubwürdig als auch aussagekräftig sind, kann ein Kriterium definiert werden, aus welchen Kombinationen von Elementen der Vertraulichkeitspolitik eine mögliche Disjunktion bestehen kann.

Dieser Ansatz wird erst in einer generischen Variante entwickelt, in der nicht-triviale Disjunktionen jeder Länge ≥ 2 zum Einsatz kommen können und das erreichte Maß an Vertraulichkeit mit der Länge der Disjunktionen variiert. Dabei wird jegliches Wissen in einem eingeschränkten, aber dennoch vielfältig einsetzbaren Fragment der Prädikatenlogik modelliert, in dem die Gültigkeit von Implikationsbeziehungen effizient ohne den Einsatz von Theorembeweisern entschieden werden kann. Anschließend wird eine Variante dieses generischen Ansatzes vorgestellt, die die Verfügbarkeit maximiert, indem Disjunktionen der Länge 2 effizient mit Hilfe von Clustering auf Graphen konstruiert werden. Diese Variante wird daraufhin derart erweitert, dass sie auch dann effizient inferenzsichere Sichten erzeugen kann, wenn ein Angreifer Vorwissen in Form einer eingeschränkten Unterklasse von sogenannten "Tuple Generating Dependencies" hat.

Um die Effizienz dieser (erweiterten) Verfügbarkeit maximierenden Variante zu demonstrieren, wird ein Prototyp unter verschiedenen Testszenarien erprobt. Dabei kommt ein Kriterium zur Konstruktion möglicher Disjunktionen zum Einsatz, das (lokal) die Verfügbarkeit innerhalb von Disjunktion maximiert, indem sich beide Disjunkte einer solchen Disjunktion nur in genau einer Konstante unterscheiden.

Nowadays, publishing of data is ubiquitous, but usually only permitted when complying with a confidentiality policy to respect privacy or other secrecy concerns. To this end, this thesis proposes an approach to weaken an original database instance to a weakened view on this instance. This view is inference-proof in the sense of "Controlled Interaction Execution" and does hence provably not enable an adversary to infer confidential knowledge – even if this adversary tries to deduce confidential knowledge on the basis of a released weakened view, his general awareness of the protection mechanism and some a priori knowledge he might possibly have about the original database instance or the world in general.

To achieve this goal within a logic-oriented modeling, all pieces of definite knowledge that compromise an element of a confidentiality policy are (whenever possible) replaced by weaker but true disjunctions of policy elements. Although this disjunctive knowledge deliberately introduces uncertainty about confidential knowledge, it still provides more information about the original database instance than complete refusals of confidential knowledge. To further guarantee that all of these weakening disjunctions are – with respect to a considered application scenario – both credible in terms of confidentiality and meaningful in terms of availability, a criterion specifying which policy elements might possibly be grouped together to an admissible weakening disjunction can be defined.

This approach is first developed in a generic way in the sense that non-trivial disjunctions of any length ≥ 2 might be employed and the achieved level of confidentiality varies with the length of disjunctions. Thereby, all knowledge is modeled within a restricted but expressive subclass of first-order logic, which allows for efficient decisions on the validity of implication relationships without general theorem proving. Afterwards, an availability-maximizing instantiation of this generic approach is presented, which aims at constructing disjunctions of length 2 efficiently on the basis of graph clustering, and is then also extended to handle an adversary's a priori knowledge in the form of a restricted subclass of well-known "Tuple Generating Dependencies" without losing its inference-proofness or efficiency.

To demonstrate the practical efficiency of this (extended) availability-maximizing approach, a prototype implementation is developed and evaluated under different experiment setups. Thereby, disjunctions are constructed on the basis of an admissibility criterion, which (locally) maximizes availability within a disjunction in the sense that both of its disjuncts differ in only one constant parameter and thereby generalizes this constant parameter to a wider set of possible values.