In smarten Umgebungen werden hau g gro e Datenmengen durch eine Vielzahl von Sensoren erzeugt. In vielen Fallen werden dabei mehr Informationen generiert und verarbeitet als in Wirklichkeit vom Assistenzsystem benotigt wird. Dadurch lasst sich mehr uber den Nutzer erfahren und sein Recht auf informationelle Selbstbestimmung ist verletzt. Bestehende Methoden zur Sicherstellung der Privatheitsanspruche von Nutzern basieren auf dem Konzept sogenannter Quasi-Identi katoren. Wie solche Quasi-Identi katoren erkannt werden konnen, wurde in der bisherigen Forschung weitestgehend vernachlassigt. In diesem Artikel stellen wir einen Algorithmus vor, der identi zierende Attributmengen schnell und vollstandig erkennt. Die Evaluierung des Algorithmus erfolgt am Beispiel einer Datenbank mit personenbezogenen Informationen.
Mittels einer datensparsamen Weitergabe der Sensor- und Kontext-Informationen an die Analysewerkzeuge des Assistenzsystems wird nicht nur die Datenschutzfreundlichkeit des Systems verbessert. Bei der Vorverdichtung der Daten durch Selektion, Aggregation und Komprimierung am Sensor selbst lasst sich die E zienz des Systems steigern. Die Privatheitsanspruche und der Informationsbedarf der Analysewerkzeuge konnen als Integritatsbedingungen im Datenbanksystem umgesetzt werden. Durch die Integritatsbedingungen lassen sich die notwendigen Algorithmen zur Anonymisierung und Vorverarbeitung direkt auf dem Datenbestand ausfuhren. Eine U bertragung in externe Programme bzw. Module, die sich evtl. auf anderen Recheneinheiten benden, entfallt somit.
Fur die Umsetzung von Datenschutzbestimmungen in smarten Umgebungen wird derzeit das PArADISE1Framework entwickelt, welches insbesondere die Aspekte der Datensparsamkeit und Datenvermeidung in heterogenen Systemumgebungen realisieren soll.
In [
Fur einen unerfahrenen Nutzer ist das Festlegen von
sinnvollen Einstellungen nur schwer moglich. Die Frage, die sich
ihm stellt, ist nicht die, ob er seine personlichen Daten
schutzen soll, sondern vielmehr, welche Daten es wert sind,
geschutzt zu werden. Zur Kennzeichnung schutzenswerter
Daten werden u.a. sogenannte Quasi-Identi katoren [
Der Rest des Artikels ist wie folgt strukturiert: Kapitel 2 gibt einen aktuellen U berblick uber den Stand der Forschung im Bereich der Erkennung von Quasi-Identi katoren. Im folgenden Kapitel gehen wir detailliert darauf ein, wie schutzenswerte Daten de niert sind und wie diese e zient erkannt werden konnen. Kapitel 4 evaluiert den Ansatz anhand eines Datensatzes. Das letzte Kapitel fasst den Beitrag zusammen und gibt einen Ausblick auf zukunftige Arbeiten.
In diesem Kapitel stellen wir bestehende Konzepte zur Ermittlung von Quasi-Identi katoren (QI) vor. Au erdem werden Techniken vorgestellt, die in unseren Algorithmus einge o en sind. 2.1
Zum Schutz personenbezogener Daten existieren
Konzepte wie k-anonymity [
Wahrend Schlussel im Laufe des Datenbankentwurfes
festgelegt werden, lassen sich Quasi-Identi katoren erst beim
Vorliegen der Daten feststellen, da sie von den konkreten
Attributwerten der Relation abhangen. Der Begri
QuasiIdenti kator wurde von Dalenius [
Fur "most tuples\ wird hau g ein Grenzwert p
festgelegt, der bestimmt, ob eine Attributkombination ein
QuasiIdenti kator ist oder nicht. Dieser Grenzwert lasst sich
beispielsweise in relationalen Datenbanken durch zwei
SQLAnfragen wie folgt bestimmen:
p = COUNT DISTINCT * FROM (SELECT <attr-list> FROM table)
COUNT FROM table
(1)
Wird fur p der Wert 1 gewahlt, so sind die gefundenen QI
mit diesem Grenzwert auch Schlussel der Relation. Um eine
Vergleichbarkeit unseres Algorithmus mit dem von Motwani
und Xu zu gewahrleisten, verwenden wir ebenfalls die in (1)
de nierte "distinct ratio\ (nach [
Da es fur den Ausdruck "die meisten\ keinen standardisierpten Quantor gibt, formulieren wir ihn mit dem Zeichen: 8 , wobei p den Prozentsatz der eindeutig identi zierbaren Tupel (ti) angibt. Ein Quasi-Identi kator QI := fA1; :::; Ang ist fur eine Relation R entsprechend de niert:
p Quasi-Identi kator. 8 t1, t2 2 R [t1 6= t2 ) 9 A 2 QI: t1(A) 6= t2(A)]
Wie beim Datenbankentwurf reicht es auch fur die Angabe von Quasi-Identi katoren aus, wenn die minimale Menge von Attributen angegeben wird, welche die Eigenschaft eines QI hat. Eine solche Menge wird als minimaler QuasiIdenti kator bezeichnet. minimaler Quasi-Identi kator. X ist ein minimaler Quasi-Identi kator (mQI), wenn X ein Quasi-Identi kator ist und jede nicht-leere Teilmenge Y von X kein QuasiIdenti kator ist.
X ist mQI: X ist QI ^ (@ Y X: (Y 6= ) ^ (Y ist QI)) Insbesondere ist X kein minimaler Quasi-Identi kator, wenn eine Teilmenge X-fAg von X mit A 2 X existiert, die ein Quasi-Identi kator ist. Das Finden von allen QuasiIdenti katoren stellt ein NP-vollstandiges Problem dar, weil die Menge der zu untersuchenden Teilmengen exponentiell zur Anzahl der Attribute einer Relation steigt. Besteht eine Relation aus n Attributen, so existieren insgesamt 2n Attributkombinationen, fur die ermittelt werden muss, ob sie ein QI sind.
In [
Der Algorithmus ist e zienter als alle 2n Teilmengen zu testen, allerdings stellt die von Big-Data-Anwendungen erzeugte Datenmenge eine neue Herausforderung dar. Insbesondere die hohe Dimensionalitat und die Vielfalt der Daten sind ernst zu nehmende Probleme. Aus diesem Grund schlagen wir im folgenden Kapitel einen neuen Algorithmus vor, der auf den Algorithmus von Motwani und Xu aufsetzt. 2.2
Der von uns entwickelte Algorithmus verwendet
Techniken, die bereits beim Sideways Information Passing (SIP,
[
Durch das fruhzeitige Erkennen solcher Tupel wird der
zu betrachtende Suchraum eingeschrankt und die
Ausfuhrungszeit von Anfragen reduziert. Besonders e ektiv ist
dieses Vorgehen, wenn das Wissen uber diese "magic sets\ [
In [
Ist eine Attributmenge hingegen keine IA fur R, so sind auch alle Teilmengen dieser Attributmenge keine IA. Wenn beispielsweise AC keine IA fur R ist, dann sind auch weder A noch C identi zierende Attributmengen fur R. Attributmengen, die keine identi zierende Attributmenge sind, werden als negierte Schlussel bezeichnet.
Der in [
In diesem Kapitel stellen wir einen neuen Algorithmus
zum Finden von minimalen Quasi-Identi katoren vor. Der
Algorithmus beschrankt sich dabei auf die Einschrankung
der zu untersuchenden Attributkombinationen. Der
entwickelte Ansatz fuhrt dabei den von [
Der von Motwani und Xu in [
Die Methodik ist in Algorithmus 1 kurz skizziert. Zunachst erfolgt eine Initialisierung der Datenbank. Dabei wird zudem die zu untersuchende Relation einmalig uberpruft, um festzustellen, wie viele Tupel vorhanden sind. Anschlieend werden alle einelementigen Attributmengen gebildet. Fur jede Attributmenge wird uberpruft, wie viele einzigartige Tupel in der Relation vorhanden sind und das Verhaltnis zur Gesamtzahl an Tupeln gebildet. Liegt der Anteil uber einen vorher bestimmten Grenzwert (threshold ), so ist diese Attributmenge ein Quasi-Identi kator und wird in die Menge aller minimalen QIs qiLowerSet aufgenommen.
Sind alle Attributkombinationen uberpruft, werden mittels Algorithmus 2 die nachstgro eren Attributkombinationen unter Rucksichtnahme der bekannten QI gebildet. Die U berprufung wird solange fortgesetzt, bis alle potentiellen Attributkombinationen uberpruft worden sind.
Der Algorithmus arbeitet sehr e zient, da durch das Bottom-Up-Vorgehen die Minimalitat der gefundenen QI sofort festgelegt ist. Besonders gut eignet sich der Algorithmus, wenn die Relation viele, aus wenigen Attributen zusammenend
Data: database table tbl, list of attributes elements Result: a set with all minimal QI qiLowerSet initialization(); for element in elements do
set := set [ felementg end while set is not empty do for Set testSet: set do double p := getPercentage(testSet, tbl); if p threshold then
qiLowerSet := qiLowerSet [ ftestSetg; end set := buildNewLowerSet(set, elements); end return qiLowerSet;
Data: current lower set lSet, list of attributes
elements Result: the new lower set lSetNew Set lSetNew := new Set(); for Set set: lSet do for Attribut A: elements do if @q 2 qiLowerSet : q set then
lSetNew := lSetNew [ fset [ fAgg; end end end return lSetNew; gesetzte QIs besitzt, da so der Suchraum gleich zu Beginn stark eingeschrankt wird.
Der Nachteil des Algorithmus zeigt sich, wenn die Relation QIs besitzt, die aus vielen Attributen zusammengesetzt sind. In diesem Fall wird der Suchraum erst zum Ende eingeschrankt, wodurch die Anzahl der zu betrachtenden Attributmengen nur unmerklich geringer ist. Falls die Relation sogar keine QIs besitzt, so erkennt der Algorithmus dies erst nach U berprufung aller Kombinationen. 3.2
Fur die Erklarung des Algorithmus 5 wird noch das
zum Bottom-Up-Vorgehen entgegengesetzte
Top-DownVorgehen benotigt. Dieses Verfahren setzt auf die in [
Die U berprufung der Attributkombinationen erfolgt wie beim Bottom-Up-Verfahren ebenenweise, jedoch in umgekehrter Reihenfolge. Fur eine Relation mit n Attributen wird zunachst die n-elementige Teilmenge gebildet und gepruft. Anschlie end werden alle (n-1)-elementigen Teilmengen gebildet. Dies wird solange fortgesetzt, bis alle einelementigen Teilmengen uberpruft wurden. Die gefundenen QuasiIdenti katoren werden in qiUpperSet gespeichert.
Durch das Top-Down-Vorgehen ist die Minimalitat der Quasi-Identi katoren nicht gewahrleistet. Dieser Nachteil
Data: current upper set uSet Result: the new upper set uSetNew Set uSetNew := new Set(); for Set set: uSet do for Attribut A: set do if @o 2 optOutSet: set - fAg o then
uSetNew := uSetNew [ fset - fAgg; end end end return uSetNew; lasst sich dadurch beheben, dass wenn auf Ebene k ein QI gefunden wird, die entsprechenden Obermengen in den Ebenen mit mehr als k Attributen gestrichen werden. In den Algorithmen 3 und 4 ist das Top-Down-Vorgehen skizziert.
Data: database table tbl, list of attributes elements Result: a set with all minimal quasi-identi er qiSet initialization(); set := elements; Set optOutSet := new Set(); Set qiUpperSet := new Set(); while set is not empty do for Set<String> testSet: set do double p := getPercentage(testSet, tbl); if p < threshold then
optOutSet := optOutSet [ fsubsetg; else qiUpperSet := qiUpperSet [ ftestSetg; for Set o: qiSet do if testSet o then
qiUpperSet := qiUpperSet - fog; end end end end set := buildNewUpper(set); end return qiUpperSet;
Der Top-Down-Ansatz hebt die Nachteile des Bottom-UpVorgehens auf: der Algorithmus arbeitet e zient, wenn QIs aus vielen Attributen zusammengesetzt sind und fur den Fall, dass die gesamte Relation kein QI ist, wird dies bei der ersten U berprufung erkannt und der Algorithmus terminiert dann umgehend.
Besteht die Relation hingegen aus vielen kleinen QIs, dann wird der Suchraum erst zum Ende des Algorithmus stark eingeschrankt. Ein weiterer Nachteil liegt in der erhohten Rechenzeit, auf die in der Evaluation naher eingegangen wird. 3.3
Der in diesem Artikel vorgeschlagene Algorithmus kombiniert die oben vorgestellten Verfahren. Dabei werden die Verfahren im Wechsel angewandt und das Wissen uber (negierte) Quasi-Identi katoren wie beim Sideways Information (a) Schritt 1: Top-Down
(b) Schritt 2: Bottom-Up (c) Schritt 3+4: Top-Down (d) Schritt 5+6: Bottom-Up
Passing [
Um zu entscheiden, welcher Algorithmus im nachsten Zyklus angewandt wird, wird eine Wichtungsfunktion eingefuhrt. Die U berprufung einer einzelnen Attributkombination auf Duplikate hat eine Laufzeit von O(n*log(n)), wobei n die Anzahl der Tupel in der Relation ist. Die U berprufung der Tupel hangt aber auch von der Gro e der Attributkombination ab. Besteht ein zu uberprufendes Tupel aus mehreren Attributen, so mussen im Datenbanksystem auch mehr Daten in den Arbeitsspeicher fur die Duplikaterkennung geladen werden. Durch gro e Datenmengen werden Seiten schnell aus dem Arbeitsspeicher verdrangt, obwohl sie spater wieder benotigt werden. Dadurch steigt die Rechenzeit weiter an.
Fur eine vereinfachte Wichtungsfunktion nehmen wir an, dass alle Attribute den gleichen Speicherplatz belegen. Die Anzahl der Attribute in einer Attributkombination bezeichnen wir mit m. Fur die Duplikaterkennung ergibt sich dann eine Laufzeit von O((n*m)*log(n*m)).
Da die Anzahl der Tupel fur jede Duplikaterkennung konstant bleibt, kann n aus der Kostenabschatzung entfernt werden. Die Kosten fur die U berprufung einer einzelnen
Data: database table tbl, list of attributes attrList Result: a set with all minimal quasi-identi er qiSet attrList.removeConstantAttributes(); Set upperSet := new Set(fattrListg); Set lowerSet := new Set(attrList); // Sets to check for each algorithm int bottom := 0; int top := attrList.size(); while (bottom<=top) or (lowerSet is empty) do calculateWeights(); if isLowerSetNext then bottomUp(); buildNewLowerSet(); bottom++; // Remove new QI from upper set modifyUpperSet(); else topDown(); buildNewUpperSet(); top--; // Remove new negated QI from lower set modifyLowerSet(); end end qiSet := qiLowerSet [ qiUpperSet; return qiSet; Attributkombination mit m Attributen betragt demnach O((m*log(m)).
Die Gesamtkosten fur das U berprufen der moglichen Quasi-Identi katoren werden mit WAV G bezeichnet. WAV G ergibt sich aus dem Produkt fur das U berprufen einer einzelnen Attributkombination und der Anzahl der Attributkombinationen (AttrKn) mit n Attributen.
WAV G := AttrKn log(m) m
Soll die Wichtungsfunktion praziser sein, so lasst sich der Aufwand abschatzen, indem fur jede Attributkombination X die Summe s uber die Attributgro en von X gebildet und anschlie end gewichtet wird. Die Einzelgewichte werden anschlie end zum Gesamtgewicht aufsummiert.
WAV G :=
P X2AttrKn log(s) s; s =
P size(A) A2X
Diese Wichtung eignet sich allerdings nur, wenn Zugang zu den Metadaten der Datenbankrelation besteht.
Fur die Evaluation des Algorithmus wurde die
Adult\"
Relation aus dem UCI Machine Learning Repository [
Die Evaluation erfolgte in einer Client-Server-Umgebung. Als Server dient eine virtuelle Maschine, die mit einer 64-BitCPU (vier Kerne @ 2 GHz und jeweils 4 MB Cache) und 4 GB Arbeitsspeicher ausgestattet ist. Auf dieser wurde eine MySQL-Datenbank mit InnoDB als Speichersystem verwendet. Der Client wurde mit einem i7-3630QM als CPU betrieben. Dieser bestand ebenfalls aus vier Kernen, die jeweils uber 2,3 GHz und 6 MB Cache verfugten. Als Arbeitsspeicher standen 8 GB zur Verfugung. Als Laufzeitumgebung wurde Java SE 8u5 eingesetzt.
Der Datensatz wurde mit jedem Algorithmus getestet. Um zu ermitteln, wie die Algorithmen sich bei verschiedenen Grenzwerten fur Quasi-Identi katoren verhalten, wurden die Tests mit 10 Grenzwerten zwischen 50% und 99% wiederholt.
Die Tests mit den Top-Down- und Bottom-UpAlgorithmen benotigten im Schnitt gleich viele Tablescans (siehe Abbildung 2). Die Top-Down-Methode lieferte bessere Ergebnisse bei hohen QI-Grenzwerten, Bottom-Up ist besser bei niedrigeren Grenzwerten. Bei der Laufzeit (siehe Abbildung 3) liegt die Bottom-Up-Methode deutlich vor dem Top-Down-Ansatz. Grund hierfur sind die gro en Attributkombinationen, die der Top-Down-Algorithmus zu Beginn uberprufen muss.
Der Bottom-Up+Top-Down-Ansatz liegt hinsichtlich Laufzeit als auch bei der Anzahl der Attributvergleiche deutlich vorne. Die Anzahl der Tablescans konnte im Vergleich zum Bottom-Up-Verfahren zwischen 67,4% (4076 statt 12501 Scans; Grenzwert: 0.5) und 96,8% (543 statt 16818 Scans; Grenzwert 0.9) reduziert werden. Gleiches gilt fur die Laufzeit (58,1% bis 97,5%; siehe Abbildung 3).
6000 s n a c s e 4000 l b a T l a 2000 h z n A 0
Wie in Abbildung 3 zu erkennen ist, nimmt die Laufzeit beim Bottom-Up+Top-Down-Verfahren im Grenzwertbereich von 70%-90% stark ab. Interessant ist dies aus zwei Grunden. Erstens nimmt die Anzahl der QuasiIdenti katoren bis 90% ebenfalls ab (179 bei 50%, 56 bei 90%). Dies legt nahe, dass die Skalierung des Verfahrens neben der Dimension der Relation (Anzahl von Tupel und Attributen) auch von der Anzahl der vorhandenen QIs abhangt. Um den Zusammenhang zu bestatigen, sind aber weitere Untersuchungen erforderlich.
Zweitens wird dieser Grenzwertbereich in der Literatur
[
8000 0 50 60 70
80 Grenzwert in %
In dieser Arbeit stellten wir einen e zienten Algorithmus zur Erkennung von QI in hochdimensionalen Daten vor. Anhand eines Beispiels mit Sensordaten zeigten wir die Eignung in Assistenzsystemen. Daruber hinaus ermitteln wir derzeit, inwiefern sich QIs in temporalen Datenbanken feststellen lassen. Das so gewonnene Wissen uber schutzenswerte Daten wird in unser Gesamtprojekt zur datenschutzfreundlichen Anfrageverarbeitung in Assistenzsystemen eingebunden.
In spateren Untersuchungen werden wir testen, welche
weiteren Quasi-Identi katoren sich aus der Kombination
von Daten verschiedener Relationen ableiten lassen. Der
dafur verwendete Datensatz besteht aus Sensordaten, die
im Smart Appliance Lab des Graduiertenkollegs
MuSAMA durch ein Tool [
Hannes Grunert wird durch die Deutsche Forschungsgemeinschaft (DFG) im Rahmen des Graduiertenkollegs 1424 (Multimodal Smart Appliance Ensembles for Mobile Applications - MuSAMA) gefordert. Wir danken den anonymen Gutachtern fur ihre Anregungen und Kommentare.
[1] Bundesrepublik Deutschland.
Bundesdatenschutzgesetz in der Fassung der