Erhalt der Privatsphäre beim Data Mining Ulrich Graf
Betreuer: Frank Eichinger
Seminar im SS 2007 Aktuelle Herausforderungen an Datenschutz und Datensicherheit in modernen Informationssystemen
Institut für Programmstrukturen und Datenorganisation (IPD) – Universität Karlsruhe (TH)
Ulrich Graf, Seminar DSDS SS 2007
2
Motivation Data Mining gewinnt immer mehr an
Bedeutung: Analysen auf Kundendaten (z.B.
Payback), Datensammlung im Internet, … Sorge um Gefährdung der
Privatsphäre beim Mining naturgemäß besonders hoch
Gründe auch für Entwicklerinteresse: Kundenbindung durch Vertrauen Schlechte Miningergebnisse durch falsche
Kundenangaben
Ulrich Graf, Seminar DSDS SS 2007
3
Agenda Übersicht Data Mining Privatsphäre –
Gefährdungsszenarien Klassifizierung von Algorithmen
anhand verschiedener Parameter Beispielalgorithmen Ausblick und Zusammenfassung
Ulrich Graf, Seminar DSDS SS 2007
4
Data Mining „We´re drowning in information and
starving for knowledge.“ Data Mining = „Knowledge“ Mining:
Finden von interessanten Mustern in großen Datenbeständen
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
5
Data Mining – Techniken Clusteranalyse: gruppiere
„ähnliche“ Datensätze, z.B.Kunden mit ähnlichemMusikgeschmack
Assoziationsregeln, z.B. Warenkorbanalyse: „Wenn Kunde Käse und Wurst kauft, kauft er mit hoher Wahrscheinlichkeit auch Brot.“
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
6
Data Mining – Techniken Klassifikation: benutze
Merkmale, um Datentupel in Klasse einzuteilen, z.B. RisikoanalyseEntscheidungsbaum,
Neuronale Netze
A < 0.5A >= 0.5
… …
……
hoch hochniedrig niedrig
Ulrich Graf, Seminar DSDS SS 2007
7
Data Mining - Entscheidungsbaum Aufbau des Baums mit Trainingsdaten Binärbaum wird von der Wurzel
ausgehend rekursiv aufgebaut: Falls Split notwendig: Ermittle Attribut A,
das die Daten optimal nach Klassen trennt
Bilde Partitionen P, P´, wiederhole Algorithmus für beide Partitionen
Vermeidung von Überanpassung des Modells an Trainingsdaten: Pruning Zusammenfassen von Blättern mit
wenigen Datensätzen
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
A < 0.5A >= 0.5
P P‘
Ulrich Graf, Seminar DSDS SS 2007
8
Was ist Privatsphäre? Unterschiedliche Definitionen:
„Individual's right to be let alone“ (1890) „Das aktive Recht, darüber zu bestimmen,
welche Daten über sich [...] von anderen gebraucht werden und welche Daten auf einen selbst einwirken dürfen." (Kuhlen)
„Personal data […]: any information relating to an identified or identifiable natural person […]“ (EG 1995)
Schutz vor Missbrauch und Identifi-zierbarkeit muss angestrebt werden
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
9
Szenario Zentralisiertes Mining Schutz individueller Daten
A < 0.5A >= 0.5
… …
……
Data
Mining
Mining-ErgebnisModifikation
Missbrauch
Identifizierbarkeit
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
hoch hochniedrig niedrig
Ulrich Graf, Seminar DSDS SS 2007
10
Szenario Verteiltes Mining Secure Multiparty Computation (SMC):
mehrere Parteien möchten Mining gemeinsam durchführen, aber jede Partei will ihre Daten geheim halten
A
B
C
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
A+B+C
MiningA < 0.5
A >= 0.5
… …
……
hoch hochniedrig niedrig
nicht sicher
Ulrich Graf, Seminar DSDS SS 2007
11
Szenario Verteiltes Mining Vertrauenswürdiger Server nicht
realistisch – sicheres Protokoll für direkte Kommunikation unter den Parteien notwendig
A B
C
SicheresProtokoll
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
12
Parameter für Algorithmen Vielzahl von Algorithmen
verfügbar Parameter:
Verteilung der Daten: zentralisiert, horizontal, vertikal vertikal
verteilthorizontal verteilt
DM DM
zentralisiert
DM
Attribute
Date
ntup
elMotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
13
Parameter für Algorithmen Parameter:
Data-Mining-Ziel: Clusteranalyse, Klassifikation, …
Modifikation der Eingangsdaten: Rauschfunktionen Blockieren von Werten Vertauschen von 0- und 1-Werten Swapping Sampling Aggregation
Grad verbleibender Funktionalität bzw. Privatsphäre
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
14
Algorithmen für SMC Jede polynomiell berechenbare
Funktion kann sicher berechnet werden (Goldreich et al.)
Beweis läuft über logische Gatter: Jede Partei besitzt eine Inputvariable Inputvariablen durch Zufallszahlen
modifiziert Jede Partei berechnet ihre
Outputvariable Zusammensetzen der
Outputvariablen eliminiert die Zufallszahlen
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
15
SMC – Beispiel Sichere Summe Summation wichtig für Data Mining Voraussetzung: Intervall [0,n) für die
Summe bekannt (Addition in Fn). Jede der m Parteien besitzt Summand
si , i = 1, …, m. Algorithmus:
1. Partei generiert Zufallszahl R aus [0,n) und leitet V = (R+s1) mod n weiter an Partei 2.
Partei i = 2,…, n-1 berechnet V = (si+V) mod n und leitet V weiter an Partei i+1.
Partei n berechnet den gleichen Schritt und leitet das Ergebnis an Partei 1 weiter.
Subtrahieren von R ergibt das Ergebnis.
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
16
SMC – Sichere Summe n = 20 Im F20:
12-13 = 19 V = 18
V = 2V = 10
s2 = 4
s1 = 5, R = 13
s3 = 8
s4 = 2
1
2
3
4
V = 12
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
17
SMC Ähnliche Algorithmen für:
Durchschnitt Vereinigung Skalarprodukt Berechnung der Inversen Matrix
Annahme: alle Parteien stellen korrekte Inputdaten bereit Bei falschen Inputdaten wird gesamtes
Ergebnis verfälscht, kein Vorteil für Datensaboteur
Problem: für viele Attribute sehr aufwändig
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
18
Auf Datenmodifikation beruhende Algorithmen
Herausforderungen: Modifikation muss Privatsphäre
sicherstellen Mining nicht möglich, ohne dass
Information zu großem Teil in den Daten erhalten bleibt
=> Gegensätzliche Ziele, Kompromisse erforderlich
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
A < 0.5A >= 0.5
… …
……
Data
Mining
Mining-Ergebnishoch hochniedrig niedrig
Modifikation
Ulrich Graf, Seminar DSDS SS 2007
19
Datenmodifikation Beobachtung: einzelne Werte
oftmals nicht entscheidend für das Mining, sondern Verteilung der Werte
Addition von Rauschfunktion zufällige Werte aus Gleichverteilung
bzw. Gauß´scher Verteilung Originaldaten geschützt, wenn
Rauschfunktion und Originaldaten nicht unkorreliert
Verteilung der Originaldaten iterativ annäherbar
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
20
Mining mit modifizierten Daten Klassifikation mit Entscheidungsbaum
Verschiedene Rekonstruktionsansätze: Global: Einmalige Rekonstruktion für jedes Attribut Nach Klassen:
Trenne Daten für jedes Attribut nach den Klassen Rekonstruiere Verteilung Baue Entscheidungsbaum auf
Lokal: Vorgehen wie nach Klassen getrennt Zusätzlich Rekonstruktion bei jedem Baumknoten
Sehr akkurate Ergebnisse möglich: Abweichung normalerweise < 10% vom Mining-Ergebnis mit nicht modifizierten Daten
Global zu ungenau, Lokal sehr aufwändig, Nach Klassen liefert fast so gute Ergebnisse wie Lokal
=> Nach Klassen guter Kompromiss
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
21
Bewertung von Algorithmen Generelle Maßstäbe:
Performanz Nutzbarkeit der Daten Grad der Privatsphäre Robustheit von Modifikationen gegenüber
anderen Algorithmen SMC:
Sicher, aber sehr hoher Aufwand – Ansätze weg von der beweisbaren Sicherheit zu mehr Performanz
Datenmodifikation: Wenn Originaldaten und Rauschfunktion
unkorreliert sind, kann Sicherheitslücke entstehen Bei erhältlichen Algorithmen guter Erhalt von
Privatsphäre und Performanz
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
22
Zusammenfassung / Ausblick Data Mining nicht mehr wegzudenken Ruf nach Mining, das die Privatsphäre
respektiert, wird lauter Forschungsgebiet noch sehr jung, aber
bereits mit guten Ergebnissen: viele Algorithmen verfügbar, die Privatsphäre und Funktionalität sichern
Größte Herausforderungen in Zukunft: weg von vielen Speziallösungen hin zu
performanten, generalisierbaren Lösungen Integration in Mining-Tools und DBMS Standardisierung steht noch ganz am Anfang
MotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Ulrich Graf, Seminar DSDS SS 2007
23
SchlussMotivationData MiningPrivatsphäreParameterAlgorithmenSchluss
Vielen Dank für die Aufmerksamkeit!