Slicing in Assistenzsystemen
Wie trotz Anonymisierung von Daten wertvolle Analyseergebnisse gewonnen
werden können
Hannes Grunert Andreas Heuer
Lehrstuhl für Datenbank- und Lehrstuhl für Datenbank- und
Informationssysteme Informationssysteme
Universität Rostock Universität Rostock
18051 Rostock 18051 Rostock
hg(at)informatik.uni-rostock.de ah(at)informatik.uni-rostock.de
Kurzfassung mit weiteren Informationen, beispielsweise dem Nutzerprofil
Datenschutz stellt eine große Herausforderung für die eines sozialen Netzwerkes verknüpft. Aus den so gewonne-
Entwicklung von Informationssystemen dar. Obwohl nen Informationen lassen sich Verhaltensmuster, Präferen-
viele Konzepte zur Wahrung des Datenschutzes beste- zen und zukünftige Ereignisse ermitteln. Auf Basis dieser
hen, werden Datenschutztechniken in der Regel nicht in Daten reagiert das Assistenzsystem eigenständig auf die Be-
Datenbankmanagement- und Assistenzsysteme integriert. dürfnisse des Nutzers und regelt Raumtemperatur, Lüftung
In diesem Artikel stellen wir eine SQL-Implementierung und weitere vernetzte Geräte.
des Slicing-Konzeptes von Li et al. [10] vor. Es erfolgt eine Assistenzsysteme sammeln häufig wesentlich mehr Infor-
detaillierte Betrachtung hinsichtlich der Parametrisierung mationen als sie für die Ausführung ihrer Funktionen benö-
des Algorithmus und dessen Auswirkung auf Informations- tigen. Der Nutzer hat dabei meist keinen oder nur einen un-
verlust und Grad des Datenschutzes. wesentlichen Einfluss auf die Speicherung und Verarbeitung
seiner personenbezogenen Daten. Dadurch ist sein Recht auf
informationelle Selbstbestimmung verletzt.
ACM Klassifikation Die Einführung von Datenschutzmechanismen wird sei-
H.2.4 [Database Management]: Systems—Query Proces- tens der Entwickler von Assistenzsystemen skeptisch an-
sing; K.4.1 [Computer and Society]: Public Policy Issu- gesehen. Es wird befürchtet, dass durch die Anonymisie-
es—Privacy rung der Daten die Entwicklung des Systems zurückgewor-
fen wird. Durch die Anonymisierung bzw. Pseudonymisie-
Stichworte rung der Nutzerdaten gehen Detailinformationen verloren,
wodurch Analysefunktionen ungenauere Ergebnisse zurück-
Datenbanken, Datenschutz, Datensparsamkeit liefern und im Extremfall unbrauchbar werden.
Im Rahmen des Graduiertenkollegs MuSAMA1 werden
1. EINLEITUNG Datenschutzkonzepte für die Anfrageverarbeitung in Assis-
Zwei Kernaspekte des Datenschutzes sind Datensparsam- tenzsystemen entworfen. Diese werden allerdings nicht on-
keit und Datenvermeidung. §3a des Bundesdatenschutzge- top auf die bestehenden Analysefunktionen aufgesetzt, son-
setzes [1] definiert diese als Forderung, dass Informations- dern in enger Zusammenarbeit während der Entwicklung
systeme möglichst wenig personenbezogene Daten erheben, integriert. Ein Beispiel für dieses Zusammenwirken ist die
verarbeiten oder nutzen sollen. Dies betrifft neben der Kon- Umsetzung des Slicing-Konzeptes von Li et al. [10] zusam-
zeption von Informationssystemen auch den Prozess der Da- men mit der Regressionsanalyse [6] auf hochdimensionalen
tenverarbeitung. Sensordaten.
Assistenzsysteme sollen den Nutzer bei der Bewältigung
seines Alltags, sei es im Beruf oder zu Hause, unterstüt-
1.1 PArADISE
zen. Über verschiedene Sensoren, wie Bewegungssensoren Für die Umsetzung von Datenschutzrichtlinien in smar-
und Wärmemessgeräte, werden Informationen über die mo- ten Umgebungen wird derzeit das PArADISE2 -Framework
mentane Situation und die Aktivitäten des Anwenders ge- [7] entwickelt, welches insbesondere die Aspekte der Da-
sammelt. Diese Daten werden im System gespeichert und tensparsamkeit und Datenvermeidung in heterogenen P2P-
Systemen realisieren soll.
PArADISE ist Werkzeug, welches den Entwicklern und
Nutzern von Assistenzsystemen helfen soll effizient und da-
tenschutzkonform Anfragen auf Sensordaten zu formulieren.
Der Kern des Frameworks ist ein datenschutzfreundlicher
1
Multimodal Smart Appliance Ensembles for Mobile
Applications
2
27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- Privacy-Aware Assistive Distributed Information System
banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Environment
Copyright is held by the author/owner(s).
24
Anfrageprozessor (siehe Abbildung 1). Dieser Prozessor er- spiels. Das letzte Kapitel fasst den Beitrag zusammen und
hält als Eingabe zum einen die Datenschutzeinstellungen der gibt einen Ausblick auf zukünftige Arbeiten.
Nutzer, zum anderen den Informationsbedarf des Systems
anhand von Anfragen an das Datenbanksystem. Als Aus- 2. SLICING
gabe wird ein anonymisierter, annotierter Teil des Daten-
In [10] stellen Li et al. ein neues Anonymisierungskonzept
bestandes zurückgeliefert. In den Annotationen wird ange-
vor, welches auf der Permutation von Daten beruht. Im Ge-
geben, wie der Datenbestand anonymisiert wurde und ob
gensatz zu den bisher gängigen Anonymisierungsverfahren
bereits die erforderlichen Analysen der Daten auf dem aus-
wie k-Anonymität [11] verzichtet dieses Verfahren auf Ge-
führenden Knoten umgesetzt wurden. Falls keine Analyse
neralisierungstechniken.
durchgeführt wurde, muss der Knoten, welcher das Ergebnis
Eine Relation ist k-anonym, wenn, auf Basis der identifi-
erhalten hat, die weitere Verarbeitung der Daten überneh-
zierenden Attributmengen der Relation, ein Tupel von k-1
men.
anderen Tupeln nicht unterscheidbar ist. In der Regel wird
Der Anfrageprozessor arbeitet in zwei Stufen. Ziel der ers-
eine Person durch ein Tupel in der Relation dargestellt. In
ten Stufe, der Vorverarbeitungsphase, ist die Modifikation
Assistenzsystemen werden, je nach Anwendungsgebiet, nur
der eingehenden Anfragen, sodass möglichst wenige Daten
Informationen über eine Person gesammelt. Dies gilt z. B.
aus der Datenbank ausgelesen werden. Dazu wird die Anfra-
bei der Überwachung von Demenzpatienten. Dort lassen sich
ge analysiert. Durch die Analyse lässt sich erkennen, welche
mittels der aufgenommenen Daten einzelne Handlungen ei-
Attribute angefragt werden, wie diese hinsichtlich ihres Wer-
ner Person identifizieren. Diese gilt es ebenfalls zu anonymi-
tebereichs gefiltert und ggf. aggregiert und gruppiert wer-
sieren.
den.
Bei der Generalisierung von Daten kommen Detailinfor-
Die so erhaltenen Informationen über die Anfrage werden
mationen abhanden, die bei vielen Analysefunktionen benö-
mit den vorformulierten Privatheitsansprüchen [4] des Nut-
tigt werden. Das Slicing-Verfahren verspricht einen höheren
zers verglichen. Treten an dieser Stelle Widersprüche auf,
Datennutzen, indem es die Verbindung von stark korreli-
wie beispielsweise der Zugriff auf ein Attribut, welches der
erenden Attributen bewahrt. Auf dieser Grundlage ist es
Nutzer nicht von sich preisgeben möchte, wird die Anfrage
trotz Anonymisierung weiterhin möglich Data-Mining- und
angepasst. Dabei werden verschiedene Techniken, wie An-
Analyse-Techniken, wie Regressionsanalysen, anzuwenden.
frageumschreibungen und Abbildungen auf Sichten, ange-
Das Konzept permutiert nicht den kompletten Datenbe-
wandt.
stand, sondern partitioniert die Daten sowohl horizontal als
In der Nachverarbeitungsphase erfolgt, sofern erforder-
auch vertikal. Bei der horizontalen Partitionierung (Tuple
lich, die Anonymisierung der Daten. Dabei wird überprüft,
Partition) wird der Datenbestand nach festgelegten Filter-
ob spezielle Kriterien wie k-Anonymität [11] zutreffen. An-
kriterien (Selektion nach einem bestimmten Attribut, An-
schließend erfolgt die Anonymisierung der Daten unter Be-
zahl an Partitionen, ...) in mehrere Mengen von Tupeln zer-
rücksichtigung des Grades der benötigten Anonymität und
legt.
des Informationsverlustes [8] zur Wahrung von Funktionali-
Die vertikale Partitionierung (Attribute Partition) unter-
tät und Datenschutz.
teilt den Datenbestand spaltenweise, indem aus der vorhan-
Durch die Vorverarbeitung der Anfrage müssen weniger
denen Attributmenge mehrere kleine Attributmengen gebil-
Daten in der Nachverarbeitungsphase anonymisiert werden.
det werden. Eine mögliche vertikale Zerlegung besteht im
Dadurch erfolgt nur eine geringe Erhöhung der Antwortzeit
Aufteilen der Attribute eines Quasi-Identifikators [2] auf
auf die Anfrage.
mehrere Partitionen.
1.2 Laufendes Beispiel Aus einem Datenbestand der durch n horizontale und m
vertikale Partitionsvorgaben zerteilt wird, entsteht ein Ras-
Die Umsetzung des Slicing-Konzeptes wird in diesen Ar-
ter aus n*m kleineren Relationen. Jede dieser Teilrelationen
tikel anhand eines laufenden Beispiels erläutert. Für die Im-
wird anschließend permutiert, indem die Reihenfolge der Tu-
plementation und Evaluation des Algorithmus wurde die
pel vertauscht wird. Die permutierten Relationen werden
Adult-Relation aus dem UCI Machine Learning Reposito-
anschließend wieder zu einer einzelnen Relation verknüpft.
ry [9] verwendet. Die Relation besteht aus personenbezoge-
nen Daten, bei denen Schlüssel sowie Vor- und Nachname
der betroffenen Personen entfernt wurden. Die verbleiben- 3. UMSETZUNG IN DER RELATIONALEN
den 15 Attribute enthalten weitere personenbezogene Anga- ALGEBRA
ben, wie beispielsweise Alter, Ehestand, Staatsangehörigkeit Für das Slicing-Konzept wird von Li et al. eine grobe Me-
und Schulabschluss. thodik für die Implementierung vorgestellt. In diesem Ab-
Tabelle 1 zeigt einen Ausschnitt der gesamten Relation. In schnitt demonstrieren wir die Adaption des Verfahrens auf
diesem Artikel wird gezeigt, wie diese Relation schrittweise die relationale Algebra. Konkrete Implementierungsdetails
in eine anonymisierte Relation (siehe Tabelle 3) überführt werden im nachfolgenden Kapitel vorgestellt.
wird.
Der Rest des Artikels ist wie folgt strukturiert: Kapitel 2 3.1 Schritt 1: Horizontaler Split
gibt einen Überblick über das Anonymisierungskonzept von Im ersten Schritt wird die Relation R in n disjunkte Par-
Li et al. Im folgenden Kapitel gehen wir detailliert darauf titionen R1 , ..., Rn zerlegt. Für jede Partition Ri wird eine
ein, wie das Konzept durch Operationen aus der Relationen- Selektionsbedingung ci angegeben, welche die Tupel aus R
algebra realisiert werden kann. In Kapitel 4 wird beschrie- den Partitionen zuordnet:
ben wie die Implementation des Konzeptes in SQL erfolgt.
Kapitel 5 evaluiert den Ansatz anhand des laufenden Bei- R1 := σc1 (R), ..., Rn := σcn (R). (1)
25
Abbildung 1: Das Konzept des datenschutzfreundlichen Anfrageprozessors
Age Workclass Occupation Relationship Race Sex
39 State-gov Adm-clerical Not-in-family White Male
50 Self-emp Exec-managerial Husband White Male
38 Private Handlers-cleaners Not-in-family White Male
53 Private Handlers-cleaners Husband Black Male
28 Private Prof-speciality Wife Black Female
34 Private Sales Husband White Female
Tabelle 1: Die Beispielrelation vor der Anonymisierung
Die Auswahl der Selektionsbedingungen muss dabei ge- auf unterschiedliche Partitionen zu verteilen. Die Ermittlung
schickt gewählt werden. Eine Möglichkeit besteht aus der von identifizierenden Attributmengen, sogenannten Quasi-
Selektion nach einem bestimmten Attribut, wobei für jeden Identifikatoren [2], lässt sich mit geringem Aufwand [5] vor
einzelnen auftretenden Attributwert (oder eine Menge von der Anonymisierung realisieren.
Attributwerten) eine Selektionsbedingung der Form attri-
but = ’Wert’ aufgestellt wird. Eine weitere Variante besteht 3.3 Schritt 3: Permutation
darin, die Tupel in R zu nummerieren (neues Attribut rank) Nach der Bildung der Teilrelationen Rij erfolgt die ei-
und die Selektionen in der Form ’rank between vj and vk ’3 gentliche Anonymisierung. Die Permutation erfolgt durch
zu beschreiben. den Ordnungsoperator τ , welcher die Tupel jeder Teilrelati-
on sortiert. In Abschnitt 4.2 wird genauer erklärt wie eine
3.2 Schritt 2: Vertikaler Split zufällige Sortierung erfolgen kann. Das Resultat der Permu-
Nachdem die Relation R in mehrere kleinere Relationen tation wird in der Liste Lij hinterlegt:
Ri zerlegt wurde, wird jede Ri durch Projektionen weiter
unterteilt. Jede Projektion πattributmengej (Ri ) wählt dabei Lij := τ (Rij ). (3)
ein oder mehrere Attribute aus der Relation R aus. Für jede An dieser Stelle geschieht ein kleiner Bruch mit der rela-
Partitionen Ri werden dabei die gleichen m Projektionen tionalen Algebra. Der Ordnungsoperator τ darf zwar auf
angewandt um die m Teilrelationen Rij aus Ri zu bilden: Relationen angewandt werden, liefert allerdings keine Rela-
Ri1 := πattributmenge1 (Ri ), ..., Rim := πattributmengem (Ri ). tion, sondern eine Liste zurück. τ darf somit nur als letzter
Operator angewandt werden [3]. Dies stellt ein Problem dar,
(2)
weil für den Slicing-Algorithmus die permutierten Listen im
Die Attributmengen in den Projektionen müssen dabei nicht
zwangsweise disjunkt sein4 . Sie dürfen keine identifizierende letzten Schritt wieder zusammengefügt werden müssen.
Attributmenge enthalten, da ansonsten Rückschlüsse auf die Die Listen müssen entsprechend wieder zurück in Rela-
Identität einer Person gezogen oder Handlungen eindeutig tionen überführt werden. Um die Ordnung zu bewahren,
wird jedes Tupel mit einer Ordnungszahl Ord (siehe Tabelle
bestimmt werden können. Die Auswahl der Attributmengen
sollte dabei in Abstimmung mit den Analysefunktionen ge- 2) versehen, welche ihre Position in der Liste widerspiegelt.
troffen werden, um z. B. stark korrelierende Attribute nicht Die Ordnungszahl wird für die folgenden Verbundoperatio-
nen benötigt. Die permutierten Relationen werden mit Rij 0
3
vj , vk nummerische Werte bezeichnet.
4
Im grundlegenden Algorithmus von Li et al. [10] wird Dis-
junktheit vorausgesetzt. Erweiterungen setzen Disjunktheit 3.4 Schritt 4: Zusammenfügen
nicht voraus. Im letzten Schritt erfolgt das Zusammenfügen der permu-
26
Ord Age Workclass Ord Occupation Relationship Ord Race Ord Sex
1 39 State-gov 1 Adm-clerical Not-in-family 1 White 1 Male
2 50 Self-emp 2 Exec-managerial Husband 2 White 2 Male
3 38 Private 3 Handlers-cleaners Not-in-family 3 White 3 Male
Ord Age Workclass Ord Occupation Relationship Ord Race Ord Sex
1 53 Private 1 Handlers-cleaners Husband 1 Black 1 Male
2 28 Private 2 Prof-speciality Wife 2 Black 2 Female
3 34 Private 3 Sales Husband 3 White 3 Female
Tabelle 2: Beispielrelation nach horizontalem und vertikalem Split. Der horizontale Split erfolgte auf dem internen Attribut
ROW_ID. Für den vertikalen Split wurden die Attribute Age und Workclass sowie Occupation und Workclass zusammenge-
fasst. Race und Sex wurden in jeweils einzelne Partitionen zusammengefasst.
Age Workclass Occupation Relationship Race Sex
39 Private Exec-managerial Husband White Male
38 State-gov Adm-clerical Not-in-family White Male
50 Self-emp Handlers-cleaners Not-in-family White Male
28 Private Handlers-cleaners Husband Black Female
34 Private Sales Husband Black Female
53 Private Prof-speciality Wife White Male
Tabelle 3: Beispielrelation nach Anwendung des Slicing-Konzeptes
tierten Teilrelationen Rij
0
zur permutierten Gesamtrelation SELECT ∗
R . Das Zusammenfügen geschieht dabei in zwei Teilschrit-
0
FROM