Attacken und Gegenmaßnahmen

ABSTRACT

In this paper I describe several attacks and remedies on collaborative recommendation systems and information retrieval systems in particular the websearch-engine Google. The paper also includes and compares different types of attacks and whose remedies. Furthermore I consider and compare the costs and benefits of several attacks on Recommendation Systems.

Schlusselworter

Attacke, Abhilfe, Empfehlungssystem, Websuche, Informationsabfrage, online.

EINLEITUNG

Im Zeitalter der Informationstechnologie wird ein GroBteil von Informationen zu Produkten, aber auch zu allen anderen Bereichen, mittels elektronischer, meist online verfugbarer, Hilfsmittel und -systeme zur Verfugung gestellt und vom User bzw. Kunden auch in Anspruch genommen. Daraus ergibt sich fur Unternehmen die Moglichkeit Kunden und Usern Informationen zukommen zu lassen, welche fur sie sonst oft verborgen bleiben wurden. Dadurch konnen Kaufentscheidungen oft beeinflusst werden. Verfalschte und unkorrekte Informationen (Bewertungen, Meinungen, Testergebnisse, allgemeine Informationen etc.) konnen den User implizit zu falschen Kaufentscheidungen drangen.

Aber nicht nur im Bereich der Online-Shopping-Malls werden diese Systeme angewandt und sind aufgrund diverser Schwachen beeinflussbar, auch die alltagliche Informationssuche im Internet, mittels uns allen bekannter Suchmaschinen wie z. B. Google, kann und wird durch Websitebetreiber und Hacker beeinflusst. Die Grunde dafur sind nicht immer kommerzieller Natur. Jeder Websitebetreiber versucht im PageRanking von Google ein moglichst zufriedenstellendes Ergebnis zu erzielen und bedient sich dabei bekannter Mittel und Methoden, um eine moglichst Google-konforme Website zu publizieren. Google wurde aber auch schon fur Attacken auf Personen (meist Politiker etc.) in Form von „Google-Bomben“ ge- und benutzt.

In der vorliegenden Arbeit werden zunachst Recommender Systeme allgemein diskutiert und vorgestellt. Ein weiterer Punkt dieser Bakkalaureats-Arbeit ist die kurze Vorstellung der Arbeitsweise von Informationsabfragesystemen, im Speziellen Online Suchmaschinen wie z. B. Google. Darauf basierend wird im nachsten Teil auf verschiede Typen von Attacken und GegenmaBnahmen im Falle dieser Attacken eingegangen. Dabei werden Effektivitat, Aufwand, Effizienz und Erfolgsaussichten verglichen. Daraus resultierende Abwehrmechanismen und Mechanismen zum Aufspuren werden im darauf folgenden Kapitel beleuchtet und diskutiert. AbschlieBend wird ein Kosten- / Nutzenvergleich, basierend auf den Untersuchungen von Neil J. Hurley, Michael P. O’Mahony, und Guenole C.M. Silvestre vom University College Dublin, durchgefuhrt.

Recommender Systeme

Ein Recommender System bezeichnet eine Software, deren Aufgabe darin besteht, dem Benutzer auf Grundlage seiner Praferenzen eine Empfehlung, z.B fur einen Artikel, ein Produkt oder eine Website, zu geben. Dazu benotigt es zum einen die ungefilterten Hintergrunddaten und als weiteren Input, Informationen uber den User. Das Recommender System ist nun ein Algorithmus, der diese Daten kombiniert und als Ergebnis personalisierte Empfehlungen generiert. [2]

Recommender Systeme machen sich die Meinung einer Community zu Nutze um Einzelpersonen (Individuen) in dieser Community dabei behilflich zu sein, den gesuchten Inhalt in der unermesslichen Auswahl heraus zu filtern. [27]

Im Allgemeinen lassen sich Recommender Systeme in zwei Klassen aufteilen. Zum einen kennen wir nicht- personalisierte, zum anderen personalisierte Systeme. Bei nichtpersonalisierten Systemen werden allen Usern, meist auf einer Durchschnittsberechnung dieser User basierend, die selben Empfehlungen ausgesprochen. [20]

In dieser Arbeit geht es aber vor allem um personalisierte Recommender Systeme, bei denen fur jeden User ein Profil erstellt wird und aufgrund seiner Praferenzen Empfehlungen generiert werden. Abbildung 1 zeigt die grundsatzliche Einteilung von Recommender Systemen. Fur uns interessant sind primar das Collaborative Filtering sowie am Rande auch das content-based Filtering. Beim content-based Filtering werden Empfehlungen nicht auf der Grundlage von Regeln ausgesprochen, sondern es werden Objekte gesucht, die denen fur die sich der User in der Vergangenheit interessiert hat, ahnlich sind. Man spricht in diesem Zusammenhang auch von item-to-item correlation. [20]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Klassifizierung von Recommender Systemen [20]

Die, wie schon gesagt, am haufigsten verwendeten und am haufigsten auftretenden Algorithmen von Recommender Systemen sind entweder userbasiert oder itembasiert: [7]

1. Der userbasierte Algorithmus bildet fur jeden User eine „benachbarte“ Usergruppe, mit Usern die ahnliche Meinungen (Bewertungen etc.) vertreten. Bewertungen dieser User wirken sich dann fur den primaren User in Form von Empfehlungen aus.
2. Der zweite Recommender System Algorithmus basiert auf den Items, d. h. angebotenen Produkten im System. Dabei werden ahnliche Produkte berucksichtigt und zur Berechnung herangezogen um danach anhand der Ahnlichkeiten sowie Bewertungen dem User empfohlen zu werden.

Die erfolgreichste Form der Recommender Systeme, das Collaborative Filtering, wurde in den letzten 15 Jahren entwickelt und immer wieder verbessert. Mittlerweile besteht eine Unzahl verschiedener Algorithmen und Systeme die diese Idee der Empfehlung, in Form elektronischer Empfehlungen, verkorpert. Bei der Frage, welche Methode nun tatsachlich die beste ist, gehen die Meinungen der Forscher weit auseinander, da nicht klar definiert werden kann, nach welchen Mabeinheiten Empfehlungen berechnet und bewertet werden sollen. [12]

Collaborative-Filtering Recommender Systeme (CFRS) sind eine elektronische Erweiterung der taglich stattfindenden Empfehlungen in diversen Verkaufs- und Informationsapparaten. Menschen sammeln Informationen und Daten zu diversen Produkten in allen Bereichen und entscheiden sich, fruher oder spater, fur eines dieser Produkte. CFRS sollen dem User die benotigten Informationen sowie Entscheidungshilfen, d. h. Empfehlungen, liefern, anhand welcher er danach seine Produkte kauft. [25]

Typische Recommmender Systeme erhalten und akzeptieren Anfragen von einem User, werten die Bedurfnisse, das Verhalten, Suchprofile sowie inhaltliche Informationen des Users aus, um personalisierte Empfehlungen abzugeben. [1]

Recommender Systeme werden grundsatzlich von drei Benuztergruppen genutzt. Diese teilen wir in: [13]

- End User sind die primaren User eines Recommendation Systems. Die Zufriedenheit der Endverbraucher hangt von der Qualitat und Genauigkeit der Empfehlungen ab, sowie davon ob die Geschmacker und Vorlieben der Endverbraucher getroffen werden.
- System Inhaber sind hauptsachlich mit dem System an sich betraut. Im Interesse der Inhaber des Systems liegt primar das Aufrechterhalten und die Attraktivitat des Systems, weniger aber die Genauigkeit bzw. Korrektheit der Empfehlungen.
- Interessierte Dritte haben hingegen konkretes Interesse an der Arbeitsweise und Funktionalitat von Transaktionen bzw. Empfehlungen. Beispielsweise ist der Autor oder der Verlag eines Buches, welches in einem System angeboten und daher auch empfohlen wird, daran interessiert, wie man haufiger und gezielter unter den Empfehlungen aufscheint.

Online Informationsabfragesysteme - Suchmaschinen

Die Zahl der Websites im Internet steigt. Vertraut man den Untersuchungen des Internet Systems Consortiums, Inc., hat sich die Zahl der betriebenen Internetseiten von Janner 2004 mit ca. 233 Millionen bis Juli 2007 auf ca. 489 Millionen mehr als verdoppelt. [16] Aufgrund dieser Zahlen und Berichte ist es nahe liegend, dass das Suchen und Finden relevanter Daten und Websites im Internet stetig komplexer wird. Laut Studien im Jahr 2004 suchen 56,3% aller Internetuser taglich zumindest einmal im Internet nach relevanten Informationen und Daten. [1, 16] Hingegen schauen nur noch 33%, d. h. weitaus weniger, auf die zweite Seite einer Internetsuchmaschine. [1]

Eine mogliche Antwort auf die steigende Komplexitat im Bereich des Information-Retrieval ist der Einsatz von Recommender System basierten Methoden und Algorithmen. Basierend auf Userdaten und Profilen, sprich personalisierter Suche, konnen Suchmaschinen immer bessere Suchergebnisse liefern. [1]

Ein typisches Recommender System ubernimmt Anfragen eines Users und wertet seine Bedurfnisse, Verhaltensmuster, Suchprofile und inhaltliche Informationen aus um personalisierte Empfehlungen abzugeben. Im Bereich der Websuche gibt es dabei hauptsachlich zwei angewandte Methoden: Systeme die mit den Inhalten von Websites handeln und Systeme die kollaborative Methoden anwenden. [6, 7, 17, 29]

Google

Die Suchmaschine Google, welche heute und schon seit langerem die Marktfuhrerschaft im Bereich der Websuche inne hat, wird von der Firma Google Inc., die 1998 von Larry Page und Sergey Brin gegrundet wurde, betrieben. Auf Grand qualitativ hochwertiger Suchergebnisse und, im Vergleich zu anderen Suchmaschinen, schnelleren Antwortzeiten der Suchanfrage entwickelte sich Google in nur wenigen Jahren zum Marktfuhrer unter den Suchmaschinen. [32] Im Jahr 2000 verfugte Google laut Hennesy und Patterson uber 6000 Prozessoren und 12000 Festplatten mit einer Gesamtkapazitat von ca. 1 Petabyte. Somit war Google das System mit der groBten Speicherkapazitat im zivilen Sektor. Im Gegensatz zu anderen Systemen verwendet Google keine groBen RAID Systeme. Vielmehr betreibt Google in den verschiedensten Landern eigenstandige Rechenzentren, in denen relativ gunstige PCs mit Standardkomponenten zu einem Cluster zusammengeschlossen sind. Jedes Rechenzentrum ist eigenstandig und kann Suchanfragen anderer Rechenzentren ubernehmen. In den Rechenzentren selbst sind die Daten vielfach redundant auf verschiedenen PCs gespeichert. Sollte ein PC ausfallen, so wird ein Ersatzgerat in den laufenden Betrieb eingehangt und die fehlenden Daten werden automatisch kopiert. Das so entstehende System ist sehr gut skalierbar, da bei Bedarf einfach neue PCs in den Cluster gehangt werden konnen. Als Betriebssystem wird bei Google eine modifizierte Version von Linux Red Hat verwendet. Programmiert wurde die Software vorwiegend in C, C++ und Python. [11]

Im April 2004 bestehen die Rechenzentren von Google bereits aus uber 63000 Rechner mit 127000 Prozessoren. Zusammengerechnet haben die Systeme ca. 127 Terabyte RAM und 5 Petabyte Festplattenkapazitat. Mittlerweile durften sich die Kapazitaten wiederum vervielfacht haben. [32]

FUNKTIONSWEISE VON RECOMMENDERSYSTEMEN UND WEBSEARCHENGINES

In diesem Kapitel wird auf Funktionsweisen, Algorithmen (soweit sie bekannt und nachvollziehbar sind) und Methoden in Recommender Systemen und Suchmaschinen eingegangen.

Recommender Systeme

Das Collaborative Filtering passiert im Wesentlichen in drei Schritten. Im ersten wird die Ahnlichkeit zu den anderen Usern definiert, entweder direkt uber ein AhnlichkeitsmaB, oder indirekt uber die Distanz. AnschlieBend werden aus allen Usern die Mentoren bzw. Nachbarn, also die besonders ahnlichen User, ausgewahlt. Diese mussen neben moglichst vielen Uberlappungen mit dem Profil des aktiven Users noch mindestens ein weiteres Objekt bewertet haben. Mithilfe der Mentoren wird im dritten Schritt die Empfehlung fur den aktiven User berechnet. [20]

Die Art der Berechnung von Ahnlichkeiten und Empfehlung hangt von den eingesetzten Techniken ab, welche sich in speicher- und modellbasierte Verfahren unterteilen. Bei den speicherbasierten Verfahren werden alle Berechnungen auf der kompletten Datenmatrix durchgefuhrt, wahrend die modellbasierten Techniken die Datenmatrix verwenden um offline ein Modell zu schatzen bzw. zu erlernen. Online, also zur Laufzeit, muss dann nur noch auf das Modell und nicht mehr auf den kompletten Datenbestand zugegriffen werden. [20]

In beiden Fallen wird eine Datenmatix V benotigt. Diese speichert die Userprofile und hat die Dimension M x N, wobei M die Anzahl der User und N die Anzahl der Objekte bzw. Produkte definiert. Ein Eintrag vj stellt damit die Bewertung des Nutzers i fur das Produkt j auf einer Skala 0...t dar, o steht fur ein noch nicht bewertetes Produkt. Jede Zeile vi in der Datenmatrix entspricht somit einem Nutzerprofil, in dem fur den Benutzer i die individuellen Bewertungen fur die Produkte 1...N gespeichert sind. [20]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Beispiel der Datenmatrix V [20]

Speicherbasierte Verfahren

Beim Anwenden speicherbasierter Verfahren werden zunachst alle Eintrage der Datenmatrix fur Berechnungen benotigt. Die daraus resultierenden Ahnlichkeiten werden bestimmt und in einer eigenen Tabelle gespeichert. Das Beispiel einer Datenmatrix wird in Abbildung 3 gezeigt. Abbildung 4 zeigt die dazugehorige Tabelle mit den Ahnlichkeiten der User. [20]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Datenmatrix [20]

Mithilfe eines Schwellenwertes werden daraus die Mentoren berechnet bzw. ausgewahlt. Diese bieten nun die Grundlage fur Empfehlungen im System. [20]

Algorithmen die bei speicherbasierten Verfahren zum Einsatz kommen, sind verhaltnismaBig einfach und ermoglichen ein relativ einfaches Hinzufugen neuer Daten. Durch neue User und Produkte, welche immer in neuen Zeilen bzw. Spalten angelegt werden, erreicht die Datenmatrix jedoch relativ schnell eine GroBe bei der Berechnungen sehr speicher- und zeitintensiv werden. Aus Grunden der Effizienzsteigerung wird daher oft, und vor allem in letzter Zeit, das modellbasierte Verfahren untersucht und angewandt. [20]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Tabelle mit Ähnlichkeiten zwischen den Usern [20]

Modellbasierte Verfahren

Die Idee hinter modellbasierten Algorithmen ist die, dass auf Basis der Bewertungen in der Datenmatrix ein Modell offline berechnet wird, so dass die online stattfindende Berechnung nur noch auf das bereits bestehende Modell zugreifen muss. Dieser Schritt erfolgt zur Laufzeit und ist im Normalfall wesentlich schneller, als die Onlineberechnung. Das Aussehen eines solchen Modells hangt stark vom eingesetzten Verfahren ab. [20]

Das am meisten verbreitete, modellbasierte Verfahren ist die Clusteranalyse, also eine Reduzierung der Datenmatrix auf wenige Interpretations einheiten, die sog. Cluster [30]. Die Idee dabei ist, dass unter den Usern bestimmte Gruppen (Cluster) entstehen, in welchen meist sehr ahnliche Bewertungen abgeben werden und somit zusammengefasst werden konnen. Ein Collaborative Filtering System wurde nun zunachst als offline stattfindende Berechnung die Clusteranalyse durchfuhren, also eine Einteilung der User in Klassen vornehmen. Das Ziel dabei ist es eine Userauswahl zu treffen, bei der User desselben Clusters besonders ahnlich, zu Usern aus anderen Clustern aber moglichst unahnlich sind. [20]

Nachdem diese Klassen bzw. Cluster in der Vorbereitungsphase, d. h. offline, erstellt wurden, muss das System zur Laufzeit den aktuellen User nicht mehr mit allen anderen Usern vergleichen, sondern nur noch mit einem Reprasentanten aus den anderen Clustern. Reprasentanten konnen entweder aufierst representative User oder virtuelle User, gebildet aus dem Schwerpunkt des Clusters, sein. Es wird also nicht mehr der ahnlichste Nutzer gesucht, sondern das ahnlichste Cluster. Als Mentoren konnten nun alle User des ahnlichsten Clusters gewahlt werden, bei grofieren Clustern empfiehlt sich aber eine zusatzliche Suche nach den darin ahnlichsten Usern. [20]

Vorteil aller modellbasierten Verfahren sind die deutlich schnelleren Berechnungen zur Laufzeit. Nachteil dabei ist jedoch, der Informationsverlust durch die Reduzierung der Datenmatrix auf ein Modell, das sich in schlechteren Empfehlungen aufiert. Aufierdem muss bei diesem Modell beim Hinzufugen neuer Daten immer uberpruft werden, ob sich Auswirkungen auf das Modell ergeben und eventuell eine Neuberechnung gestartet werden muss. [20]

Suchmaschinen

Suchmaschinen sind Online-Dienste die mittels sog. Indizierprogramme wie z. B. Such-Algorithmen, Crawler, Robots, Spider etc., automatisch und in regelmafiigen Abstanden Websites aufspuren, indizieren und erschliefien. Die Indizierung sieht vor, dass eine Suchmaschine, z. B. Google, gefundene Seiten mit Schlusselwortern in Form von Meta-Tags, Titles, Domains sowie Volltext der gefundenen Seite in Datenbanken ablegt. In weiterer Folge werden auch alle Links weiterverfolgt, was zu einer Katalogisierung grofier Bereiche des Internets fuhrt. [23]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Schematischer Aufbau einer Suchmaschine [32]

Wie Abbildung 5 zeigt bestehen die gangigen Suchmaschinen heute aus folgenden Komponenten: [32]

- Spider
- Indexer
- Inverser Index
- Datenbank
- Interface zu Usern
- Algorithmus.

[...]