Gesellschaft für Informatik e.V.

Lecture Notes in Informatics


Datenbanksysteme in Business, Technologie und Web (BTW 2007) P-103, 262-276 (2007).


2007


Editors

Alfons Kemper (ed.), Harald Schöning (ed.), Thomas Rose (ed.), Matthias Jarke (ed.), Thomas Seidl (ed.), Christoph Quix (ed.), Christoph Brochhaus (ed.)


Contents

Anreizmechanismen für peer-to-peerweb crawling unter berücksichtigung bösartiger teilnehme

Holger Steinhaus , Klemens Böhm and Stephan Schosser

Abstract


Web Crawling ist grundlegend für eine Vielzahl von Anwendungen. Aufgrund der damit verbundenen hohen Ressourcenanforderungen sind jedoch nur wenige Organisationen in der Lage, eigene Crawler zu betreiben. Um neue Anwendungsbereiche zu erschließen und eine hohe Skalierbarkeit sowie eine faire Verteilung der Kosten zu erreichen, muss Web Crawling nicht nur verteilt, sondern auch koordinatorfrei sein. Peer-to-Peer-Techniken können diese Anforderungen erfüllen, benötigen jedoch An- reizmechanismen, um Teilnehmer nachhaltig zur Beteiligung zu motivieren. Solche Mechanismen müssen jedoch einige Besonderheiten der Anwendung 'Web Crawling' berücksichtigen: Die Erkennung von sich nicht beteiligenden Teilnehmern ist schwierig, da diese nicht direkt beobachtet werden kann. Weiterhin sollte es einem Teilnehmer erlaubt sein, vorübergehend nicht zu crawlen, ohne in den Augen anderer Peers als bösartig betrachtet zu werden. Weiterhin müssen die zu entwerfenden Mechanismen robust gegen gezielte bösartige Angriffe sein. Wir stellen im Folgenden Anreizmechanismen für ein Peer-to-Peer-System vor, die diese Anforderungen erfüllen. Neben einem Feedback-basierten Reputationssystem kommen dabei Mechanismen zum Einsatz; die eine Überprüfung von Leistungsbehauptungen einzelner Teilnehmern ermöglichen. Umfangreiche Simulationsexperimente evaluieren die Auswirkungen bösartiger Teilnehmer und zeigen die Effektivität und Robustheit des Ansatzes. 262 1.1 Problembeschreibung Eine Vielzahl von Webanwendungen, wie z.B. Preisvergleiche, Webarchive, Webservice- Lokalisierungsdienste oder spezialisierte Suchmaschinen bauen auf Webcawlern auf. Der Betrieb eines Webcrawlers ist jedoch äußerst aufwändig, wenn man einen signifikanten Teil des Webs vollständig und zeitnah abdecken will. Dazu kommen normalerweise große Rechnerfarmen zum Einsatz, die aus dem Crawling resultierenden Datenmengen stellen eine große Herausforderung für konventionelle verteilte Datenbanken dar1. Nur wenige große Unternehmen oder Organisationen sind in der Lage und bereit, solche Datenmengen zu bewältigen. Unser Ziel ist es, Web Crawling einem breiteren Publikum zugänglich zu machen, u.a. kleineren Unternehmen, die neue crawling-basierte Dienste anbieten wollen, jedoch nicht die Ressourcen zum Crawlen des gesamten Webs aufbringen können. Die Grundidee besteht darin, dass viele verschiedene Teilnehmer und Organisationen gemeinsam crawlen, wenn ihre Ressourcen ansonsten brach liegen würden. Dazu ist eine gewisse Koordination erforderlich. Diese sollte jedoch nicht zentral erfolgen, da ein solches Modell im Allgemeinen schlecht skaliert und empfindlich gegenüber Denial-of-Service-Angriffen ist. Diese Koordinationsmechanismen müssen weiterhin einen Anreiz zur Beteiligung bieten, um Free Riding [AH00] zu verhindern. Dabei sollte jeder Teilnehmer die Kontrolle über seine Ressourcen behalten und selbst entscheiden können, wann er seine Bandbreite und Rechenleistung einsetzt. Folglich ist eine einfache Unterscheidung zwischen 'guten' und 'bösen' Teilnehmern bzw. zwischen gerade crawlenden und gerade nicht crawlenden zu kurz gegriffen. Weiterhin sollte berücksichtigt werden, dass sich in der Realität nicht alle Teilnehmer zwangsläufig rational verhalten. Die Erfahrung zeigt, dass Angreifer in offenen Umgebungen oft bereit sind, bedeutende eigene Ressourcen aufzubringen, um dem angegriffenen Dienst Schaden zuzufügen. Dieses Verhalten soll im Folgenden als bösartig bezeichnet werden. Die hier präsentierten Mechanismen haben daher zum Ziel, gegen beliebige Kombinationen aus Free Riding und bösartigkeit wirksam zu sein. Im Folgenden stellen wir Anreizund Verteidigungsmechanismen für einen P2P-Webcrawler vor, die diese Fragestellungen abdecken. Wir stellen ein Protokoll vor, dass es einem Teilnehmer ermöglicht, die behauptete Crawlingleistung eines Anderen anhand eines stichprobenbasierten mehrstufigen Verfahrens zu überprüfen. Die Überprüfung ist jedoch nicht trivial, da verschiedene Teilnehmer unterschiedliche Bereiche des Webs crawlen. Anhand der Reputation des betreffenden Peers wird dabei die Frequenz solcher Überprüfungen gesteuert, was den gesamten durch Überprüfungen verursachten Overhead in Grenzen hält. Die Ergebnisse der Überprüfungen beeinflussen wiederum die Reputation des geprüften Teilnehmers. Das Überprüfungsprotokoll stellt den Kern der hier vorgestellten Arbeit dar, während die Realisierung der Reputationsverwaltung auf bewährte Ansätze 1Ein Vorabexperiment zur Analyse der Webstruktur wurde auf einer Breite von 12 Mio. gecrawlten Webseiten (ca. 0.1\% der geschätzten Größe [GS05] des Webs im Jahr 2005) durchgeführt. Das Speichern der Linkstruktur der besuchten Seiten (ohne deren Inhalt) führte zu einer Datenbank mit 1 Mrd. Tupeln, die etwa 80 GB an permanentem Speicherplatz benötigt. 263 im Sinne von [AD01] zurückgreift. Wir evaluieren unseren Ansatz anhand umfangreicher Experimente mit verschiedenen Formen von Fehlverhalten. Diese zeigen, dass beispielsweise ein Denial-of-Service-Angreifer 15-30\% aller Teilnehmer des Systems unter seine Kontrolle bringen muss, um einen signifikaten Schaden zu verursachen.


Full Text: PDF

ISBN 978-3-88579-197-3


Last changed 04.10.2013 18:13:31