Verfahren und System zum Anonymisieren von Datenbeständen Die vorliegende Erfindung betrifft ein Verfahren ein System zum Anonymisieren von Datenbeständen.

Die Druckschrift US 7,269,578 betrifft Systeme und Verfahren zum De-Identifizieren oder Anonymisieren von Einträgen in ei- ner Eingabedatenquelle. Ziel des Verfahrens ist es, Attribut ^¬ werte, die auch in Kombination einen indirekten Personenbezug beinhalten, wie beispielsweise ein Geburtsdatum, in einer Datenmenge so zu verallgemeinern, dass ein Rückschluss auf kon ^¬ krete Personen aus der Datenmenge auch dann nicht mehr mög- lieh ist, wenn Hintergrundinformation hinzugezogen werden, wie beispielsweise ein Melderegister mit Geburtsdaten. Attribute mit einem indirekten Personenbezug werden als Quasi- Identifikator (Quasi Identifier) bezeichnet. Ein Datensatz ist „k-anonym", wenn jede mögliche Abfrage über Kombinationen von Quasi-Identifikatoren stets entweder kein Ergebnis oder mindestens eine Anzahl von k Ergebnissen lie ^¬ fert. Dies wird dadurch erreicht, dass jede Kombination von generalisierten Quasi-Identifikatoren eine Gruppe von mindes- tens k Elementen beschreibt.

Zusätzlich gibt es über die k-Anonymität hinausgehende, stär ^¬ kere Bedingungen an das Ergebnis der Anonymisierung. Diese stellen neben der Mindestanzahl von k Elementen je entstehen- de Gruppe auch Bedingungen an spezielle Attribute, die nicht generalisiert worden sind. Diese speziellen Attribute werden als sensitive Attribute bezeichnet. Gängige Kriterien hierfür sind „1-Diversität" ( 1-Diversity) und „t-Nähe" (t-Closeness) . Ein Beispiel für ein sensitives Attribut wäre beispielsweise das Attribut "Krankheit" in einem Patientendatensatz.

„1-Diversität" bedeutet, dass jede entstehende Gruppe mindes ^¬ tens k Elemente enthält und dass in jeder Gruppe mindestens 1 verschiedene Werte für das sensitive Attribut anzutreffen sind (vgl. Ashwin Machanavaj j hala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramaniam, 2007, „1-Diversity : Privacy beyond k-Anonymity" , ACM Trans, Knowl . Discov. Data 1, 1, Article 3 (March 2007),

DOI=http: //dx. doi.org/ 10.1145/1217299.1217302) .

„t-Nähe" bedeutet, dass sich die statistische Verteilung der sensitiven Attribute in jeder Gruppe nur um ein als Parameter gegebenes Maß von der statistischen Verteilung des sensitiven Attributes in der Gesamtmenge unterscheiden (vgl. N. Li, T. Li and S. Venkatasubramanian, "t-Closeness : Privacy Beyond k- Anonymity and 1-Diversity", 2007 IEEE 23rd International Con ^¬ ference on Data Engineering, Istanbul, 2007, pp . 106-115. doi: 10.1109/ICDE .2007.367856) .

Um dies zu erzielen, werden für die Quasi-Identifikatoren sogenannte Generalisierungsstufen festgelegt. Durch Anwendung einer Generalisierung auf einen Quasi-Identifikator wird der Informationsgehalt der Attributwerte verringert, so dass ur ^¬ sprüngliche verschiedene Attributwerte gleich werden können. So können zum Beispiel die Postleitzahlen 53754 und 53757 beide zu 5375* generalisiert werden und würden somit in der ersten Generalisierungsstufe angeglichen werden.

Eine Generalisierung führt dazu, dass die Abfragen über Quasi-Identifikatoren weniger differenziert sind und die Ergeb ^¬ nismengen größer werden. Wenn ein Datensatz hinreichend generalisiert ist, dann erfüllt dieser das Kriterium der k- Anonymität.

Jedoch führt jede höhere Stufe der Generalisierung zu einem weiteren Informationsverlust in den Daten. Ein Verfahren, um den Informationsverlust zu verringern, ist es, die benötigten Generalisierungsstufen möglichst gering zu halten. Um dies zu erzielen, können auch geeignete Datensätze aus dem Datenbe ^¬ stand vollständig entfernt werden ( Suppression) . Die Kombination von Generalisierungsstufen und Suppression zu finden, die auf einer Datenmenge mit möglichst wenig Informa ^¬ tionsverlust k-Anonymität erzielt, ist ein algorithmisch kom ^¬ plexes Optimierungsproblem (NP-hart) .

Verschiedene Algorithmen und Implementierung aus der Literatur und im Open-Source-Bereich stellen Heuristiken bereit, um auf einem Datenbestand eine Kombination von Generalisierung und Suppression zu finden, die k-Anonymität erreicht und nicht allzu viele Informationen aus dem Datenbestand ent ^¬ fernt .

Die bisherigen Lösungen sind jedoch nicht in der Lage, auf großen Datenmengen zu operieren, da diese voraussetzen, dass alle Daten der Datenmenge in den Hauptspeicher oder virtuellen Speicher eines einzelnen Rechners geladen werden und dort der Algorithmus ausgeführt wird. Damit sind diese Lösungen nicht für große Datenmengen (Big-Data) geeignet, deren Umfang größer als der Speicher eines Rechners ist.

Die Druckschrift Kohlmauer et. al, „Flash: Efficient, Stable and Optimal k-Anonymity" , 2012) beschreibt eine Suchheuris ^¬ tik, die k-Anonymität auf der Basis von Generalisierung und Suppression erzielt. Dieser Algorithmus ist jedoch nicht ver- teilt, sondern als Einzelrechner-Lösung konzipiert. Der Algorithmus basiert, wie andere Heuristiken für die k-Anonymität, auf der Basis einer Generalisierung und Suppression auf einem sogenannten Generalisationsgraphen (Generalization-Lattice) . Dieser Generalisationsgraph wird durch die Anzahl der Quasi- Identifikatoren und die Anzahl der pro Quasi-Identifikator angegebenen Generalisierungsstufen bestimmt.

Ein Knoten in dem Graphen umfasst einen Vektor, der genauso viele Elemente hat, wie Quasi-Identifikatoren existieren. In jeder Komponente des Vektors wird für jeden Quasi- Identifikator eingetragen, welche Generalisierungsstufe für diesen Quasi-Identifikator angewendet werden soll. Die Gesamtmenge aller Knoten gibt alle Kombinationsmöglichkeiten für die Generalisierung auf den Quasi-Identifikatoren an. Eine Kante wird zwischen zwei Knoten genau dann gezogen, wenn diese sich in genau einer Komponente um den Wert 1 unter ^¬ scheiden .

Für jeden Knoten kann untersucht werden, ob, wenn die in diesem beschriebenen Generalisierungsstufen angewendet werden, der modifizierte Datenbestand die Bedingung der k-Anonymität , der 1-Diversität oder der t-Nähe erfüllt, möglicherweise un- ter Hinzunahme einer Suppression der Datensätze, die nicht die Gruppenstärke k erreichen. Ebenso kann für den Knoten ausgerechnet werden, welcher Informationsverlust bei der An ^¬ wendung des Knotens entstanden ist. Dieser wird über eine Unterscheidbarkeits-Metrik

(Discernability Metrik) ausgerechnet, in der die Anzahl der entstandenen Gruppen, die Größe sowie die Anzahl der unterdrückten („suppressed" ) Datensätze eingehen. Darüber hinaus bietet der Algorithmus eine Suchheuristik an, die angibt, ob und welcher Knoten als nächstes zu prüfen ist.

Der Knoten mit dem geringsten Informationsverlust aller geprüften Knoten bestimmt das Ergebnis der Anonymisierung. Der Flash-Algorithmus führt alle diese Berechnungen und Prüfungen auf dem Datenbestand im Hauptspeicher aus. Damit ist er nicht auf große Datenmengen anwendbar, die in einem verteilten Big-Data-System gehalten und verarbeitet werden.

Die Druckschrift Ghinita, P. Karras, P. Kalnis und N.

Mamoulis, „Fast Data Anonymization with Low Information

Loss", in: Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB '07, VLDB Endowment, 2007, S. 758-769, beschreibt einen Hilb-Algorithmus , mit dem überprüft werden kann, ob eine Generalisierung für sich allein genommen k-Anonymität erreicht.

In der Druckschrift X. Zhang et. al . , „A Scalable Two-Phase Top-Down Specialization Approach for Data Anonymization Using MapReduce on Cloud", IEEE Transactions On Parallel And Dis- tributed Systems, Vol. 25, NO. 2, February 2014, wird eine map-reduce-basierte Ausführung von TDS (Top-Down- Specialization) für eine k-Anonymität beschrieben. Dieses Verfahren bietet jedoch nicht die Flexibilität, mit einer be ^¬ liebigen Suchheuristik auf dem kompletten Generalisierungs- graphen zu suchen.

Es ist die technische Aufgabe der vorliegenden Erfindung, ei- ne Anonymisierung großer Datenbestände zu ermöglichen.

Diese Aufgabe wird durch technische Gegenstände nach den un ^¬ abhängigen Ansprüchen gelöst. Vorteilhafte Ausführungsformen sind Gegenstand der abhängigen Ansprüche, der Beschreibung und der Figuren.

Gemäß einem ersten Aspekt wird diese Aufgabe durch ein Ver ^¬ fahren zum Anonymisieren von Datenbeständen gelöst, mit den Schritten eines Bestimmens einer Kombination an Generalisie- rungsstufen für Quasi-Identifikatoren eines Datenbestandes an einem zentralen Knoten; eines Übermitteins der Kombination an Generalisierungsstufen an eine Mehrzahl von Unterknoten; und eines parallelen Durchführens einer Anonymisierung des Datenbestandes auf Basis der Kombination an Generalisierungsstufen durch die Unterknoten. Durch die Verwendung einer Mehrzahl von Unterknoten wird der technische Vorteil erreicht, dass auch große Datenbestände in einer geringen Zeit anonymisiert werden können. In einer technisch vorteilhaften Ausführungsform des Verfahrens wird überprüft, ob der anonymisierte Datenbestand die Bedingung einer k-Anonymität erfüllt. Dadurch wird beispiels ^¬ weise der technische Vorteil erreicht, dass sichergestellt werden kann, dass der Datenbestand die gewünschte Anonymität aufweist.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird eine Kombination an niedrigeren Generalisie- rungsstufen bestimmt, wenn der anonymisierte Datenbestand die Bedingung der k-Anonymität erfüllt. Dadurch wird beispiels ^¬ weise der technische Vorteil erreicht, dass die Generalisie ^¬ rung des Datenbestandes sukzessive vermindert werden kann.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird eine Kombination an höheren Generalisierungs- stufen bestimmt, wenn der anonymisierte Datenbestand die Be ^¬ dingung der k-Anonymität nicht erfüllt. Dadurch wird bei- spielsweise der technische Vorteil erreicht, dass die Genera ^¬ lisierung des Datenbestandes sukzessive erhöht werden kann, bis k-Anonymität erreicht ist.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird eine Kombination an niedrigeren oder höheren Generalisierungsstufen an die Mehrzahl von Unterknoten übermittelt und eine Anonymisierung des Datenbestandes auf Basis der niedrigeren oder höheren Kombination an Generalisierungsstufen durch die Unterknoten parallel durchgeführt. Dadurch wird beispielsweise der technische Vorteil erreicht, dass die Generalisierung des Datenbestandes optimiert werden kann.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird das Bestimmen einer Kombination an Generali- sierungsstufen auf Basis eines Generalisierungsgraphen durchgeführt. Dadurch wird beispielsweise der technische Vorteil erreicht, dass eine Hierarchie an Generalisierungsstufen er ^¬ zeugt wird, die eine schnelle Auswahl höherer oder niedrige ^¬ rer Generalisierungsstufen ermöglicht.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens ist der Generalisierungsgraph in den Speicher des zentralen Knoten geladen. Dadurch wird beispielsweise der technische Vorteil erreicht, dass die Generalisierungsstufen auf schnelle Weise durch den zentralen Knoten ausgewählt wer ^¬ den können. Alternativ kann der Generalisierungsgraph als verteilte Datenstruktur über mehrere Knoten hinweg gespei ^¬ chert werden. In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird der Generalisierungsgraph mittels einer vorgegeben Suchheuristik traversiert. Dadurch wird beispielswei- se der technische Vorteil erreicht, dass Kombinationen unter ^¬ schiedlicher Generalisierungsstufen mit wenigen Rechenschritten ausgewählt werden können.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird überprüft, ob der anonymisierte Datenbestand die Bedingung einer 1-Diversität erfüllt. Dadurch wird bei ^¬ spielsweise der technische Vorteil erreicht, dass jede ent ^¬ stehende Gruppe mindestens k Elemente enthält und dass in je ^¬ der Gruppe mindestens 1 verschiedene Werte für das sensitive Attribut anzutreffen sind

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird überprüft, ob der anonymisierte Datenbestand die Bedingung einer t-Nähe erfüllt. Dadurch wird beispiels- weise der technische Vorteil erreicht, dass sich die statis ^¬ tische Verteilung der sensitiven Attribute in jeder Gruppe nur um ein als Parameter gegebenes Maß von der statistischen Verteilung des sensitiven Attributes in der Gesamtmenge unterscheiden .

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird aus jedem Datensatz des Datenbestandes eine Zeichenkette als Gruppenschlüssel für die Anonymisierung er ^¬ zeugt. Dadurch wird beispielsweise der technische Vorteil er- reicht, dass die Größe der jeweiligen Gruppen für die Überprüfung der K-Anonymität mit geringen Aufwand festgestellt werden kann.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens wird der ursprüngliche Datenbestand gelöscht, wenn der anonymisierte Datenbestand die Bedingung der k-Anonymität erfüllt. Dadurch wird beispielsweise der technische Vorteil er-reicht, dass sich der Speicherbedarf verringert und ein Missbrauch des ursprünglichen Datenbestandes verhindert wird.

In einer weiteren technisch vorteilhaften Ausführungsform des Verfahrens ist der Datenbestand in einer parallelen Datenbank gespeichert. Dadurch wird beispielsweise der technische Vor ^¬ teil erreicht, dass auf jeden Datensatz des Datenbestandes schnell und in paralleler Weise zugegriffen werden kann. Gemäß einem zweiten Aspekt wird diese Aufgabe durch ein Sys ^¬ tem zum Anonymisieren von Datenbeständen gelöst, mit einem zentralen Knoten zum Bestimmen einer Kombination an Generali- sierungsstufen für Quasi-Identifikatoren eines Datenbestandes; einer Übermittlungseinrichtung zum Übermitteln der Kom- bination an Generalisierungsstufen an eine Mehrzahl von Unterknoten; und einer Mehrzahl an Unterknoten zum parallelen Durchführen einer Anonymisierung des Datenbestandes auf Basis der Kombination an Generalisierungsstufen . Dadurch werden die gleichen technischen Vorteile wie durch das Verfahren nach dem ersten Aspekt erreicht.

Gemäß einem dritten Aspekt wird diese Aufgabe durch ein Com ^¬ puterprogramm gelöst, das in den Speicher eines digitalen Computers geladen werden kann und das Softwarecodeabschnitte umfasst, mit denen das Verfahren nach dem ersten Aspekt ausgeführt werden kann, wenn das Computerprogramm auf Dem Computer läuft. Dadurch werden die gleichen technischen Vorteile wie durch das Verfahren nach dem ersten Aspekt erreicht. Ausführungsbeispiele der Erfindung sind in den Zeichnungen dargestellt und werden im Folgenden näher beschrieben.

Es zeigen: Fig. 1 ein Blockdiagramm eines Verfahrens; und

Fig. 2 eine schematische Ansicht eines Systems zum Anony ^¬ misieren von Datenbeständen. Fig. 1 zeigt ein Blockdiagramm eines Verfahrens zum Anonymisieren von Datenbeständen. Der Datenbestand umfasst eine Vielzahl einzelner Datensätze mit unterschiedlichen Attribu- ten .

Das Verfahren umfasst den Schritt S101 eines Bestimmens einer Kombination an Generalisierungsstufen für Quasi- Identifikatoren eines Datenbestandes an einem zentralen Kno- ten. Die Quasi-Identifikatoren sind dabei Attribute mit einem indirekten Personenbezug, über die eine Identifizierung der Person möglich sein könnte, wie beispielsweise ein Geburtsda ^¬ tum oder eine Postleitzahl einer Person. Die Generalisierungsstufe gibt das Maß an Generalisierung an, der der Quasi-Identifikator unterzogen werden soll. Für den Quasi-Identifikator des Geburtsdatums kann die Generalisie- rungsstufe beispielsweise Tag (keine Generalisierung) , Woche (1. Generalisierungsstufe) , Monat (2. Generalisierungsstufe) oder Jahr (3. Generalisierungsstufe) betragen. Für den Quasi- Identifikator der Postleitzahl kann die Generalisierungsstufe darin bestehen, eine oder mehrere Ziffern der Postleitzahl zu entfernen, beispielsweise 80336 (keine Generalisierung) , 8033X (1. Generalisierungsstufe) , 803XX (2. Generalisierungs- stufe), 80XXX (3. Generalisierungsstufe) oder 8XXXX (4. Gene- ralisierungsstufe) . Für jeden Quasi-Identifikator des Datenbestandes wird eine jeweilige Generalisierungsstufe bestimmt.

Anschließend umfasst das Verfahren den Schritt S102 eines Übermitteins der bestimmten Kombination an Generalisierungs- stufen an eine Mehrzahl von Unterknoten. In Schritt S103 führen die Unterknoten eine Anonymisierung des Datenbestandes und der jeweiligen Datensätze auf Basis der Kombination an Generalisierungsstufen parallel durch. Bei dem zentralen Kno- ten und den Unterknoten handelt es sich beispielsweise um ei ^¬ genständige Rechner, die jeweils einen Prozessor und eine Speicher aufweisen, auf den der Prozessor über einen Adress- und Datenbus zugreifen kann. Durch das Verfahren wird ein Algorithmus zum Anonymisieren von Datenbeständen in verschiedene Bestandteile zerteilt, von denen einige zur verteilten Ausführung auf Unterknoten parallelisiert werden, so dass der Algorithmus in einem Big- Data-System parallel auf verteilt gespeicherten Datenbeständen angewendet werden kann. Als Ausführungsumgebung kann ein verteiltes Big-Data-System verwendet werden, wie beispiels ^¬ weise Spark/Hadoop oder eine massiv parallele Datenbank.

Fig. 2 zeigt eine schematische Ansicht eines Systems 100 zum Anonymisieren von Datenbeständen 105. Das System 100 umfasst einen zentralen Knoten 101, wie beispielsweise einen Compu ^¬ ter, zum Bestimmen einer Kombination an Generalisierungsstu- fen für die Quasi-Identifikatoren des Datenbestandes 105.

Mittels einer Übermittlungseinrichtung 103, wie beispielsweise einer Netzwerkschnittstelle, wird die Kombination an Gene ^¬ ralisierungsstufen an eine Mehrzahl von Unterknoten 109 übermittelt. Die Mehrzahl an Unterknoten 109, wie beispielsweise mit dem zentralen Knoten 101 über ein Netzwerk verbundene Computer, führen die Anonymisierung des Datenbestandes 105 auf Basis der Kombination an Generalisierungsstufen parallel und gleichzeitig durch. Das Ergebnis dieser Anonymisierung wird zwischengespeichert.

Die einzelnen Bestandteile a) bis e) des parallelen Algorithmus sind: a) Eine Steuerung auf dem zentralen Knoten 101 konstruiert einen Generalisierungsgraphen GG auf der Basis der spezifizierten Quasi-Identifikatoren und deren Generalisie- rungsstufen, die zuvor eingegeben worden sind. Typischerweise werden jeweils höchstens 10 Quasi- Identifikatoren und Generalisierungsstufen angegeben.

Damit ist der Generalisierungsgraph GG als Datenstruktur prinzipiell klein genug, um in dem Speicher des zentra ^¬ len Knotens 101 gehalten zu werden. Standardmäßige Komp- rimierungstechniken können ebenfalls auf den Generali- sierungsgraph GG angewendet werden. Die Größe des Gene ^¬ ralisierungsgraphen GG ist unabhängig von der Größe des zu bearbeitenden Datenbestandes 105 und stellt daher keinen Flaschenhals für die Verarbeitung großer Datenmengen dar. Falls der Generalisierungsgraph zu groß für die Darstellung auf einem Rechner ist, kann er auch in einer auf mehreren Unterknoten verteilt gespeicherten Datenstruktur abgelegt werden. In diesem Fall ist wei- terhin die Ausführung der Suchheuristik zentralisiert, nur die Ausführung elementarer Graphoperationen erfolgt über Kommunikation mit den entsprechenden Unterknoten.

Des Weiteren wendet der zentrale Knoten 101 eine Such- heuristik H auf dem Generalisierungsgraphen GG an, um den als nächstes zu prüfenden Knoten des Generalisie ^¬ rungsgraphen GG zu bestimmen. Dies können auch durch die Parallelisierung mehrere Knoten des Generalisierungsgra ^¬ phen GG sein. Eine weitere Eingabe für die Suchheuristik H sind neben dem Generalisierungsgraphen GG die Ergebnisse der bislang bewerteten Knoten des Generalisierungsgraphen GG.

Die konkrete Ausprägung der Suchheuristik ist nicht we- sentlich. Es können bestehende Suchheuristiken verwendet werden, die als Ergebnis der Bewertung eines Knoten im Generalisierungsgraphen GG lediglich die Information verwenden, ob ein Knoten den gewünschten Grad an Anonymisierung erreicht, d.h. Gruppen mindestens der Größe k, wenn höchstens S-viele vertrauliche Datensätze

(Confidential Records) unterdrückt oder weggelassen wer ^¬ den. Andere Suchheuristiken können auch weitere Informationen als Ergebnis der Bewertung eines Knotens verwenden, die sich zum Beispiel aus einer

Unterscheidbarkeitsmetrik (Discernability Metrik) oder dem Informationsverlust ergeben (siehe d) ) . Eine Kombination von Generalisierungen des Datenbestandes 105 wird auf den Quasi-Identifikatoren in verteilter und hypothetischer Weise durch die Unterknoten 109 durchgeführt. Jeder Knoten des Generalisierungsgraphen GG bestimmt dabei eine mögliche Kombination von Genera ^¬ lisierungsstufen .

Diese können in einem verteilten Big-Data-System parallel auf allen verteilt liegenden Datensätzen des Datenbestandes 105 durchgeführt werden. Als Ergebnis einer Generalisierung auf einem Datensatz werden die Ergebnisse der Generalisierung auf den einzelnen Quasi- Identifikatoren zu einer einzigen Zeichenkette

konkatenieren, die als Gruppenschlüssel bezeichnet wird.

Die Menge aller Gruppenschlüssel ist das Ergebnis einer verteilten hypothetischen Generalisierung auf dem Datenbestand 105. Im Falle von 1-Diversität oder t-Nähe wird für jeden einzelnen Datensatz die Menge aus Gruppenschlüssel und Werten der sensitiven Attribute als Ergeb ^¬ nis betrachtet.

Es wird eine verteilte Überprüfung durch die Unterknoten 109 durchgeführt, ob die hypothetische Generalisierung auf Basis der vorausgewählten Kombination von Generali- sierungsstufen das Kriterium der k-Anonymität , der

1-Diversität oder t-Nähe erfüllt. Dies wird auf Basis einer verteilten Berechnung einer Aggregation basierend auf dem Gruppierungsergebnis aus Schritt b) nach dem Gruppenschlüssel durchgeführt.

Zur Überprüfung des Kriteriums der k-Anonymität wird auf dem Ergebnis aus b) durch eine verteilte Aggregation die jeweilige Gruppengröße der jeweiligen Gruppenschlüssel berechnet. Jeder gleiche Gruppenschlüssel wird mit dem Wert „1" gezählt und die Summe für jeweils gleiche Grup ^¬ penschlüssel gebildet, beispielsweise in einem Combi- ne/Reduce-Schritt in Hadoop oder einem ReduceByKey in Spark .

Das Ergebnis ist ein verteilter Datensatz, der pro Gruppe ein Element enthält, das ein Paar aus Gruppenschlüs ^¬ sel und Gruppengröße umfasst. Gruppen mit einer Gruppen ^¬ größe größer oder gleich k werden beibehalten, die anderen werden als "suppressed" markiert (siehe Schritte d) und e) ) . c2) Ist 1-Diversität erfordert, so erfolgt zusätzlich zu

Schritt cl) eine weitere Überprüfung. Für jede nicht markierte Gruppe wird eine verteile Aggregation durchge ^¬ führt, die die Anzahl der verschiedenen Werte für jedes sensitive Attribut innerhalb jeder Gruppe bestimmt. Dies kann in Hadoop wieder durch einen Combine/Reduce-Schritt auf Basis der Gruppenschlüssel oder in Spark durch einen combineByKey-Aggregator durchgeführt werden, der Datenstrukturen für die Werte aufbaut und verteilt zusammen ^¬ führt. Nun wird parallel für jede Gruppe überprüft, ob jedes sensitive Attribut mindestens 1 Elemente enthält. Falls dies nicht der Fall ist, so wird die Gruppe als "suppressed" markiert. c3) Ist t-Nähe gefordert, so erfolgt zusätzlich zu Schritt cl) eine weitere Überprüfung. Für jede Gruppe, die nicht als vertraulich („Confidential" ) markiert ist, werden verteilte Aggregationen durchgeführt, die die Häufigkeit des Auftretens der Werte jedes sensitiven Attributes in ^¬ nerhalb jeder Gruppe bestimmen.

Dies kann beispielsweise in Hadoop durch einen Combi ^¬ ne/Reduce-Schritt auf Basis der Gruppenschlüssel oder in Spark durch einen combineByKey-Aggregator durchgeführt werden, der Datenstrukturen für die Häufigkeitsverteilungen aufbaut und verteilt zusammenführt. Nun wird pa ^¬ rallel für jedes sensitive Attribut der Gruppe über ^¬ prüft, ob die entstandene Häufigkeitsverteilung inner- halb der erlaubten Häufigkeitsverteilung des sensitiven Attributes auf der Gesamtmenge liegt.

Diese ist vorab vor Schritt a) einmal nach dem gleichen Verfahren parallel berechnet worden und an alle betei ^¬ ligten Unterknoten 109 zur Verfügung gestellt worden. Der Unterschied in der Häufigkeitsverteilung jedes sensitiven Attributes innerhalb einer Gruppe im Vergleich zu der globalen Häufigkeitsverteilung des sensitiven At tributes kann mit dem Pearson-Korrelationskoeffizienten berechnet werden. Ist der Unterschied eines sensitiven Attributes größer als die vorgegebene maximale Abwei ^¬ chung, wird die Gruppe als "suppressed" markiert.

Es wird eine verteilte Berechnung des Informationsverlusts aus der Anwendung der Schritte b) und c) durchge ^¬ führt. Die Eingabe in diesem Schritt ist eine verteilte Datenstruktur, in der die Paare aus Gruppenschlüssel, Gruppengröße und Suppressed-Attribut (True/False) ge ^¬ speichert sind. Hieraus kann die

Unterscheidbarkeitsmetrik in einer verteilten Aggregati on berechnet werden. Andere entropie-basierte Maße wie ein Informationszuwachs (Information Gain) sind ebenfalls anwendbar, indem aus dem Gruppenschlüssel wieder die Werte der anonymisierten Quasi-Identifikatoren bestimmt und mit den Originalwerten verglichen werden.

Es wird eine verteilte Ausführung der Generalisierung oder Suppression durchgeführt. Die zentrale Steuerung mittels des zentralen Knotens 101 aus Schritt a) führt auf dem Generalisierungsgraphen die Suchheuristik H durch, nach der Knoten für die Ausführung der Schritte b) , c) , und d) bestimmt werden.

Die Auswahl der Knoten erfolgt durch die Suchheuristik H. Hierzu können mehrere Knoten des Generalisierungsgra phen parallel geprüft werden, da der Schritt b) immer z einer hypothetischen Generalisierung zur Erzeugung des jeweiligen Gruppenschlüssels führt. Dies bedeutet für die Suchheuristik H, dass alle Knoten, die in der inneren Schleife als zu evaluierende Knoten bestimmt werden und auf dem Heap gespeichert werden, parallel evaluiert werden können.

Die Suchheuristik H beendet die Suche, wenn ein zumeist lokales Optimum gefunden worden ist und bestimmt den Knoten, nach dem die Generalisierung oder Suppression am geeignetsten zu erfolgen hat. Der Algorithmus führt nun wie in b) die entsprechende Generalisierung verteilt auf dem tatsächlichen Datenbestand durch und entfernt, wie in c) beschrieben, die Datensätze, die weggelassen werden müssen.

Der Ablauf des gesamten Algorithmus im Pseudo-Code ist wie folgt :

Zur Eingabe werden verwendet:

D: Datenbestand, beispielsweise verteilt gespei ^¬ chert m einem Cluster oder einer massiv rallelen Datenbank;

QI: Liste der Quasi-Identifikatoren;

GS : Generalisierungsstufen pro Qua- si-Identifikator;

SA: sensitive Attribute im Falle von 1-Diversität oder t-Nähe; k: gewünschte Mindest-Gruppengröße s, beispiels ^¬ weise Prozentsatz an erlaubter Supression;

1: eine Ganzzahl, falls eine 1-Diversität gefor ^¬ dert ist: sigma : erlaubte Abweichung der Verteilung des sensitiven Attributes in den Gruppen, falls t-Nähe gefordert ist;

H: Suchheuristik im Generalisierungsgraph; und

M: Evaluierungsmetrik .

Aus der Eingabe folgt als Ausgabe ein generalisierter Datenbestand D-anon.

1) Aus QI und GS wird ein Generalisierungsgraph GG in der zentralen Steuerung berechnet. Dabei sind in jedem Knoten des Generalisierungsgraphs GG zu Beginn alle Attri ^¬ bute mit dem Wert „False" oder „nicht" gesetzt und das Attribut „Qualität" nicht gesetzt.

Die Generalisierungsstufe für jeden Quasi-Identifikator wird definiert. Das Attribut „Evaluated" wird auf „True" oder "False" gesetzt. Das Attribut "k-Anonymity" wird auf „True" oder "False" gesetzt. Gegebenenfalls werden die Attribute „1-Diversität" und „t-Nähe" auf „True" oder „False" gesetzt. Das Attribut „Quality" wird ge ^¬ setzt .

2) Schleife: Traversiere den Generalisierungsgraph GG gemäß Suchheuristik H; a. Schreibe in Kandidatenliste CL eine Liste der Kan ^¬ didaten gemäß Suchheuristik H(GG); b. Falls Kandidatenliste CL nicht leer ist, führe pa ^¬ rallel für alle Kandidaten C in der Kandidatenliste CL die folgenden Schritte aus: i. Schreibe in S_C eine Tabelle der Gruppen ^¬ schlüssel (evtl. mit sensitivem Attribut, falls gesetzt) , die wie in b) beschrieben pa ^¬ rallel berechnet sind; ii. C . k-Anonymity <- parallel evaluiert auf Basis von S_C, wie in cl) beschrieben; iii. C .1-Diversity <- parallel evaluiert auf Basis von S_C, wie in c2) beschrieben; iv. C . t-Closeness <- parallel evaluiert auf Basis von S_C, wie in c3) beschrieben; v. C.Quality <- parallel evaluiert auf Basis von S_C, wie in d) beschrieben vi. C.evaluated <- True vii. GG.C <- C

Sonst: Beende Schleife

3) GG-anon <- Knoten aus dem Generalisierungsgraph GG mit C . k-anonymity = „True" und zusätzlich C .1-Diversity = "True", C. t-Closeness = „True";

4) C_best <- Knoten aus GG-anon mit dem der besten

C.Quality; und

5) D-anon <- parallele Anwendung von C_best auf D, wie in e) beschrieben.

Die Anonymisierung spielt sowohl beim Verarbeiten und Speichern von Datenbeständen 105 als auch beim Teilen von Daten und Informationen eine große Rolle. Big-Data-Systeme verar ^¬ beiten die anfallenden Datenbestände 105, um diese auszuwerten und einen Nutzen aus diesen Datenbeständen 105 ziehen zu können. Die Anonymisierung von Datenbeständen 105 ist eine Teilkomponente dieser Lösungen. Durch das beschriebene Ver- fahren wird eine Lauffähigkeit auf Big-Data-Systemen ermög ^¬ licht .

Eine Generalisierung und Suppression ist ein wichtiges Ver- fahren für die k-Anonymität , das wiederum ein wichtiges Kri ^¬ terium für die Anonymität des Datenbestandes 105 ist. Die bisherigen Verfahren zur k-Anonymität, 1-Diversität und t- Nähe auf der Basis von Generalisierung und Suppression arbeiten nur innerhalb eines einzigen Speichers (In-Memory) und können folglich nur auf einem Datenbestand 105 ausgeführt werden, der vollständig in den Speicher eines einzigen Knotens 101 geladen werden kann.

Damit sind diese Verfahren nicht für einen Datenbestand 105 verwendbar, der im Volumen derart umfangreich ist (Big Data) , dass dieser nicht mehr auf einem Rechner alleine gespeichert werden kann. Dadurch ist durch die Hardware eine Obergrenze für eine Verarbeitbarkeit des Datenbestandes 105 gegeben. Durch das Verfahren wird ein Algorithmus bereitgestellt, der zentrale und parallelisierte Ausführungsteile umfasst. Die zentralen Ausführungsteile sind im Speicherbedarf von dem Datenvolumen des Datenbestandes 105 unabhängig, so dass durch die parallelisierte Ausführung größere Datenvolumen verarbei- tet werden können, als dies bisher möglich war.

Das Verfahren erlaubt es, k-Anonymität, 1-Diversität und t- Nähe auf der Basis von Generalisierung und Suppression verteilt auf großen Datenbeständen 105 anzuwenden. Das Verfahren ist auf verteilten Big-Data-Systemen einsetzbar, wie beispielsweise Hadoop, Spark oder massiven parallelen Datenbanken .

Alle in Verbindung mit einzelnen Ausführungsformen der Erfin- dung erläuterten und gezeigten Merkmale können in unterschiedlicher Kombination in dem erfindungsgemäßen Gegenstand vorgesehen sein, um gleichzeitig deren vorteilhafte Wirkungen zu realisieren. Alle Verfahrensschritte können durch Vorrichtungen implementiert werden, die zum Ausführen des jeweiligen Verfahrensschrittes geeignet sind. Alle Funktionen, die von gegenständ- liehen Merkmalen ausgeführt werden, können ein Verfahrensschritt eines Verfahrens sein.

Der Schutzbereich der vorliegenden Erfindung ist durch die Ansprüche gegeben und wird durch die in der Beschreibung er- läuterten oder den Figuren gezeigten Merkmale nicht beschränkt .