Upload
marny-cain
View
28
Download
0
Embed Size (px)
DESCRIPTION
Algorithmen des Internets Sommersemester 2005 04.07.2005 12. und letzte Vorlesung. Christian Schindelhauer [email protected]. Überblick. Das Internet: Einführung und Überblick Mathematische Grundlagen IP: Routing im Internet TCP: Das Transport-Protokoll des Internets - PowerPoint PPT Presentation
Citation preview
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und Komplexität
Algorithmen desInternets
Sommersemester 200504.07.2005
12. und letzte Vorlesung
Christian [email protected]
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
2
Heute
Überblick
•Das Internet: Einführung und Überblick
•Mathematische Grundlagen
•IP: Routing im Internet
•TCP: Das Transport-Protokoll des Internets
•Die Struktur des World Wide Web und des Internets
•Suche im Web
•Web-Caching im Internet
•Peer-to-peer-Netzwerke
•Angriffe auf das Internet
– Spam-Mails und Spam-Filter
– Denial of Service Angriffe und ihre Abwehr
– Viren, Würmer, Trojaner, Hoaxes
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
3
Was ist SPAM?
•Spam:
– ist der Gebrauch eines elektronischen Mediums in unverhältnismäßig großen Ausmaße
•Ausprägung:
– Spam-E-Mail
– Instant Messages
– Usenet Newsgroups
– Spam-Webseiten für Web-Suchmaschinen
• Spamdexing
– Weblogs
– Handy-SMS
– Internet-Telefon-SPAM
•Unterschied zu herkömmlicher Werbung:
– Die Kosten werden dem “Konsumenten” des Spams aufgebürdet
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
4
Spam-E-Mail
•E-Mail-Spam
– Tausend bis Millionen versandte Kopien einer fast identischen E-Mail
•Offizielle Begriffe
– UCE (Unsolicited Commercial E-Mail)
• unerbetene kommerzielle E-Mail
– UBE (Unsolicited Bulk E-Mail)
• unerbetene Massen-E-Mail
•Fakten: (sophos.com, Apr. 2004)
– Wo kommt sie her?
– 50% von “Zombie”-PCs
• deren Besitzer nichts davon ahnen
– Prozentualer Anteil an allen E-Mails
• geschätzt: 68%-83%
1. United States (35.7 %) 2. South Korea (24.9 %) 3. China and Hong Kong (9.7 %) 4. France (3.1 %) 5. Spain (2.7 %) 6. Canada (2.6 %) 7. Japan (2.1 %) 8. Brazil (1.9 %) 9. United Kingdom (1.5 %) 10. Germany (1.2 %) 11. Australia (1.2 %) 12. Poland (1.2 %)
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
5
Wie funktionieren ein SPAM-Filter?Beispiel SPAM-Assassin Version 3.0
•Problem:
– Fehler erster Ordung (false positive) versus
– Fehler zweiter Ordnung (false negative)
•628 Basis-Regeln mit 227 Unter-Regeln.z.B.
– DRUGS_* (bezeichnet of Arzneimittel adressiert werden)
– LONGWORDS (viele Wörter mit mehr als 5 Buchstaben)
•Anwedung Bayessche Regeln auf Schlüsselwörter (Token)
•Genetische Algorithmen
– seit Version 3.0 nicht mehr Bestandteil
•Ergebnisse werden mittels eines Perzeptrons kombiniert, d.h.
– lineare Kombination der gewichteten Regeln
– mit Anwendung einer Schwellwert Funktion mit Werte
– Gewichte werden in Testreihen mit Test-Mails bestimmt
[Van Dinter 2004, ApacheCon 2004]
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
6
Beispiele für besonders erfolgreiche Regeln
•Message-ID in Großbuchstaben
– 11,3 % SPAM
– False Positives: 0%
•X-Message-Info existiert
– 18.0 % der SPAM, keine FP
•Sender-IP weicht von angegebener IP ab
– 25,7 % der SPAM, FP: 0,03 %, z.B.– Received: from 65.214.43.12 (unknown [211.222.252.28]) by bblisa.bblisa.org
(Postfix)
– with SMTP id DD6DE1768DB for <[email protected]>; Sat, 11 Sep 2004 00:38:56 -0400 (EDT)
•MIME-Boundary beginnt mit “--” und endet mit Ziffernfolge
– 36,5% der SPAM, FP: 0%
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
7
Bayessche Filter
•Idee:
– Es gibt typische Worte in SPAM-Mails, z.B.
• Viagra, “NIGERIAN MINISTER”, VI@gra
– Das Auffinden dieser Wörter erhöht die “Wahrscheinlichkeit”, dass ein Wort SPAM ist
– Es gibt typische Worte, die nicht in SPAM-Mails auftuachen, z.B.
• Frühschicht, Butterbrot,
– Solche Worte erhöhen die “Wahrscheinlichkeit”, dass ein Wort keine SPAM ist
•Problem:
– Es gibt im eigentlichen Sinne keine “Wahrscheinlichkeit”, da die E-Mail entweder SPAM ist oder nicht
– Wie kann man diesen Begriff formalisieren?
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
8
Der Satz von Bayes und ein Beispiel
•Die bedingte Wahrscheinlichkeit P(A | B) ist definiert durch
– Wahrscheinlichkeit dass Ereignis A unter der Bedingung B erscheint
•Umgekehrt gilt:
•Daraus folgt der Satz von Bayes:
•Beispiel:
– A = “Mail ist SPAM”
– B = “E-Mail beinhaltet Viagra”
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
9
Einsatz von Bayes-Anti-SPAM-Filter
•Bei mehreren Schlüsselwörtern B1, B2, ..., Bn erhält man dann
•Sind nun Bi, Bj unabhängige Ereignisse,
– als auch Bi∩A, Bj∩A voneinander unabhängig, erhält man
•Um die Wahrscheinlichkeit einer SPAM-Mail zu bestimmen,
– genügt es dann die Häufigkeit des Schlüsselworts in SPAM-Mails mit der Gesamthäufigkeit des Schlüsselworts in Relation zu setzen
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
10
Anti-Anti-Spam-Filter-Tricks
•Kodierung der Schlüsselwörter
– durch gezielte Falschschreibung:
• V|agra (mit senkrechten Strich), V I A G R A, V-I-A-G-R-A, etc.
– durch Bilder
•Verwirren des Filters
– Einstreuen von Zitaten aus Standardtexten/Weltliteratur
– oft nicht sehr erfolgreich
•Diese Tricks können oft mit neuen bedingten Wahrscheinlichkeiten gelöst
•Dagegen unlösbares Problem (?):
– “normale” E-Mails die auf eine neue E-Mail hinweisen
• “Hallo Tom, ich wollte Dir nur mal meine neue Web-page zeigen, klick doch mal drauf: wwww.unscheinbarer-link.de. Grüße, Tina”
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
11
Denial of Service-Angriffe(Dienstverweigerungsangriffe)
•Denial of Service (DoS)-Angriffe verbrauchen die Ressourcen eines Rechners oder Netzwerks, um deren Verfügbarkeit zu verringern oder auszuschalten
•Angriffsziele
– Netzwerk
• Internet
• Peer-to-Peer-Netzwerke
• Proxy-Caching-Netzwerke
– Rechner
• Web-Server
• Mail-Server
• Router
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
12
DoS auf Rechner
•Angriffsziel Rechner, z.B. SYN-Angriffe:
•Angriffsziel Rechner im Internet
•Eine Reihe von „half-open“ TCP-Verbindungen wird aktiviert
•Ununterscheidbar von regulären Anfragen
•Der TCP-Server muss SYN/ACK-Pakete senden und auf Reaktion warten
•Rechnerangriffe können relativ gut lokal abgewehrt werden
•Durch Abschalten des Rechners
•Analyse der Attacke
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
13
DoS-Angriff auf ein Netzwerk
•Z.B. SMurf-Angriff oder distributed DoS (DDoS)
– Angriff gegen Internet-Service Provider (ISP)
– Großer Datenstrom wird auf Netzwerk gerichtet
– Mit gleicher Häufigkeit werden gültige wie DoS-Pakete wegen Überlastung durch IP gelöscht
•Netzwerkangriffe sind schwierig zu bekämpfen
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
14
IP ist anfällig für DoS-Angriffe
•DoS-Angriffe auf IP-Ebene können meist nicht zurückverfolgt werden
– Der Angreifer erzeugt Datagramme mit falscher Quell-IP-Adresse
– Dem Empfänger der Datagramme steht die Routeninformation nicht zur Verfügung
• Es sei denn alle Router kooperieren bei der Suche, während einer Attacke
•DoS-Datagramme können nicht von legitimen Datatgrammen unterschieden werden
– Nur implizit und aus dem Kontext.
– Beispiele:
• Universitätsrechner werden oft benutzt, um DoS-Attacken mit korrekter Quellinformation zu führen.
• 11. September 2001 – Sämtliche Nachrichtensites brachen unter der legitimer Last zusammen
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
15
Aufgabenstellung
•Wie kann man die Quelle(n) einer eingehenden Datagrammflut mit gefälschten Quell-IP-Adressen bestimmen?
•ohne Kooperation der Router im Netzwerk
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
16
Quellbestimmung einer DoS-Attacke
•Motivation:
– Im einfachsten Fall: Quelle = Angreifer
– Abschalten (möglicherweise instrumentalisierter) Rechner beendet (vorerst) den Angriff
•Problem Reflektorangriff
– Angreifer schickt Datagramme mit Opfer-IP-Adresse als falscher Quellinformation an unbeteiligte Netzteilnehmer (Rechner oder Drucker
– Die unbeteiligten Netzteilnehmer beantwortet Request an mutmaßliche Quelle
– Das Opfer erhält die DoS-Attacke von diesen instrumentalisierten Netzteilnehmern
•Gegenmaßnahme
– Vom instrumentalisierten Netzteilnehmer aus, muss der Angreifer gefunden werden
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
17
Lösung: Ingress Filtering[Ferguson, Senie ’98]
•Verfahren:
– Router blockieren Pakete mit fehlerhafter Quellinformation
– Sinnvoll an Schnittstellen von ISP
•Diskussion
– Effektiv nur bei universellen Einsatz
– Wird aber nicht bei der Mehrheit der ISP eingesetzt
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
18
Lösung: Link testing by input debugging
•Verfahren
– Routenrückverfolgung stromaufwärts
– Opfer beschreibt allgemeines Merkmal der DoS-Datagramme (attack signature)
– Opfer kommuniziert diese Merkmal an Netzwerkbetreiber der eingehenden Datagramme
– Dieser wiederholt dies bis zur Quelle
•Einige ISPs haben dieses Verfahren automatisiert [Stone ’00]
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
19
Lösung: Link Testing durch Controlled Flooding [Burch, Cheswick ’99]
•Verfahren
– Opfer verfügt über eine aktuelle Routingkarte
– Während eines DoS-Angriffs konstruiert das Opfer die Angriffsrouten stromaufwärts
• indem es alle Möglichkeiten der letzten unbekannten Station selber durch einen DoS-Angriff belegt
– Läßt die Datenmenge kurzfristig nach, ist eine Station gefunden und der Vorgang wird per Tiefensuche fortgesetzt
•Nachteile
– Opfer wird selber zum Angreifer
– Kaum geeignet für verteilte DoS-Angriffe (DDoS)
– Kann leicht von einem Angreifer überlistet werden
– durch eingebaute Fluktuationen
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
20
Lösung: Logging
•Verfahren
– Jeder Router zeichnet alle IP-Header auf
– Durch Data-Mining-Techniken kann der Angreifer bestimmt werden
•Nachteil
– Enormer Aufwand
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
21
Lösung: ICMP Traceback
•Mit geringer Wahrscheinlichkeitkeit (z.B. 1/20.000) wird in einem Router ein ICMP-traceback-datagram an den Zielknoten geschickt
– Der Zielknoten kann dann den Weg rekonstruieren
•Nachteile:
– ICMP-Pakete könnten bei Pufferüberlauf vor IP-datagrammen gelöscht werden
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
22
•Theorem
– Wird mit Wahrscheinlichkeit p ein ICMP-Paket erzeugt, dann sind erwartet ((ln d) + O(1))/p DoS-Pakete ausreichend zur Bestimmung eines DoS Pfades aus d Routern.
– Um mit Wahrscheinlichkeit 1 ‒ ε den Pfad zu bestimmen genügen ln(d)/p ‒ ln(ε)/p DoS Pakete.
•Beweis
– wird hier nicht besprochen...
– Interessierte finden es im Skript von vor zwei Jahren
ICMP Traceback
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
23
Lösung: Marking [Savage et al. ’00]
•Verfahren
– In ungenutzte Felder des IP-Headers schreibt jeder Router seine Adresse mit gewisser W’keit
•Nachteil:
– Router müssen auf gewisse Weise mitarbeiten
– Distributed DoS-Pfade nur schwer rekonstruierbar
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Quellbestimmung einer DoS-Attacke
Verwaltungs-aufwand
Netzwerklast Router-aufwand Post mortem fähig
Präventiv/ reaktiv
Ingress filtering moderat niedrig moderat Nein präventiv
Link testing by input debugging
hoch niedrig hoch schlecht reaktiv
Link testing by flooding
niedrig hoch niedrig schlecht reaktiv
Logging hoch niedrig hoch ausgezeichnet reaktiv
ICMP Traceback niedrig niedrig niedrig ausgezeichnet reaktiv
Markieren niedrig niedrig niedrig ausgezeichnet reaktiv
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
25
MarkierungVoraussetzungen und Annahmen
•Ein Angreifer kann alle Pakettypen erzeugen
•Verschiedene Angreifer können konspirieren
•Angreifer wissen, dass die Pakete zurückverfolgt werden
•Pakete können verloren gehen oder ihre Reihenfolge kann vertauscht werden
•Angreifer senden zahlreiche Pakete
•Die Route zwischen Angreifer und Opfer ist relativ stabil
•Die Router habe beschränkte Rechen- und Speicherressourcen
•Die Router arbeiten im wesentlichen ordnungsgemäß
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Das Traceback-Modell
•V: Opfer
•Ri: Router
•Aj: mögliche Angreifer
•Ax =A2: tatsächlicher Angreifer
•P = (R2,R4,R5): Angriffspfad
•(R1,R3,R2,R4,R5): von Ax vorgetäuschter Pfad
A1
A3
R3
R1
V
A2
R5
R2
R4
P
R3
R1
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
27
Problemstellungen
•Exact traceback:
– Berechne exakten Angriffspfad P
•Approximate traceback:
– Finde Pfad P‘ mit Angriffspfad P als Suffix
– Angreifer kann längeren Pfad vortäuschen
•Zwei Algorithmen:
– Markierungsalgorithmus im Router
• Algorithmus schreibt Pfadinformation in den IP-Header durchlaufender Datagramme
– Pfadrekonstruktion durch Opfer
• Löst approximate traceback
•Qualtitätsmerkmale:
– Konvergenzzeit: Anzahl notwendiger Pakete zur Lösung
– Speicherbedarf in IP-Header
– Berechnungsaufwand
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
28
Node Append
•Markierung bei Router R
begin
for all packets w do
Füge R zu w hinzu
od
end
•Pfadrekonstruktion durch Opfer V
begin
for a packet w do
Extrahiere Pfad P aus w
od
return P
end
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
29
Node Append
•Pfadprotokoll (node append)
•In IP-Header wird gesamte Pfadinformation gespeichert
– Jeder Router hängt seine IP an.
– Konvergenzzeit: 1
•Probleme
– Pfadlänge im vorhinein nicht bekannt
– Datagrammlänge (praktisch) konstant
– Angreifer kann falsche Pfade fingieren
– Erheblicher Overhead
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
30
Node Sampling
•Mit Wahrscheinlichkeit p>1/2 schreibt der Router seine IP-Adresse in den IP-Header
– Nur eine Adresse
•Markierung bei Router R
begin
for all packets w do
x ← Zufallszahl aus [0..1]
if x<p then
w.router ← R (Ersetze alte Information)
fi
od
end
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
31
Pfadrekonstruktion by Node Sampling
•Pfadrekonstruktion durch Opfer V
begin
for all packets w do
N(R) ← Anzahl Pakete mit Router R aus Paket w
od
P ← sortierte Liste aller vorgekommenden Router R gemäß N(R)
return P
end
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Konvergenz Node Sampling
•Lemma
– Die Wahrscheinlichkeit bei der Pfadrekonstruktion von Node-sampling ein Paket mit Router-IP R, der Hopdistanz d zum Opfer hat zu finden ist
• mindestens p(1‒p)d-1 und
• höchstens p(1-p)d-1+(1-p)D,
– wobei D die Hopdistanz des Angreifers ist.
•Beweis:
•1. Fall: Der Angreifer sendet keine Pakete mit Routerinfo R
– W’keit, dass d-1 Router Routerinfo nicht überschreiben: (1-p)d-1
– W’keit, dass Router R Routerinfo überschreibt: p
•2. Fall: Der Angreifer sendet nur Pakete mit Routerinfo R
– W’keit, dass D Router Routerinfo nicht überschreiben: (1-p)D
– W’keit, dass Router R Routerinfo überschreibt: p(1-p)d-1
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
33
Edge Sampling
•Kantenproben (edge sampling)
– ähnlich wie node sampling
– zusätzlich wird die Entfernung der Kante eingetragen
– p kann nun kleiner als1/2 gewählt werden
– Kleine Wahl p verringert die Anzahl der Nachrichten, um die Route zu bestimmen.
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
34
Edge Sampling
•Markierung bei Router R
begin
for all packets w do
x ← Zufallszahl aus [0..1]
if x<p then
w.start ← R
w.distance ← 0
else
if w.distance=0 then w.end ← 0 fi
w.distance += 1
fi
od
end
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Edge Sampling Pfadrekonstruktion
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Konvergenz Edge Sampling
•Theorem
– Die erwartete Konvergenzzeit E[T] von Edge Sampling bei
– Wahrscheinlichkeit p ist
– wenn D die Distanz des Angreifers ist.
•Beweis:
– Xi,n: Anzahl der DoS-Pakete mit Kanteninformation der Kante in Entfernung i zum Opfer und n DoS-Paketen
– Für i<D kann so ein Paket nicht gefälscht werden
– Setzt man für n den obigen Wert ein erhält man die Wahrscheinlichkeit 1/D.
– Der Rest des Beweises ist dann leicht einzusehen.
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Anzahl Virusinfektionen pro 1000 Rechner im Monat
Quelle: ICSA Labs Annual Computer Virus Prevalence Survey 2004
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
38
Computerviren (I)
“Unique among all forms of artificial life, computer viruses have escaped their playpens and established themselves pervasively throughout the world’s computing environment”
Jeffrey Kephart, IBM Research Center, 1994•Computervirus ist ein Program, das sich auf andere Computer und in
Netzwerken verbreiten kann, indem es sich selbst ohne Wissen des Benutzers kopiert.
•Virustypen
•werden nach Übertragungsart charakterisiert
•Nicht Viren
•Hoax (falsche Viruswarnung), Kettenbrief, Gerüchte, Urban Legend, Meme
•keine Programme
•Joke-Virus
•keine Ausbreitung
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
39
Virustypen
•Wurm
– benötigt Wirtsprogramm (wie Textdokument, Betriebssystem, Mailprogramm) zur Fortpflanzung
•File-Infector
– Viren hängen sich an Programmdateien, die auf einen anderen Rechner dann den Virus weiterverbreiten
•Boot-Virus
– verändert Bootsektor von anderen Disketten oder Festplatten durch unabsichtliches Booten von infizierter Diskette
•Macro-Virus
– Benutzen Macro-Befehle in Text/Tabellen-Dokumente zur Weiterverbreitung
•Trojanisches Pferd
– ist ein legitimes Programm mit nicht spezifizierter (Viren-) Funktionalität
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Computerviren (II)
Quelle: ICSA Labs Annual Computer Virus Prevalence Survey 2004
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Computerviren (II)Quelle: ICSA Labs Annual Computer Virus Prevalence Survey 2000/2001
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
42
Erfolgreiche Viren 2004
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Virusauswirkungen
Quelle: ICSA Labs 7th Annual Computer Virus Prevalence Survey 2000/2001
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Virusauswirkungen
Quelle: ICSA Labs 7th Annual Computer Virus Prevalence Survey 2000/2001
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
45
Virusauswirkungen
•Nachrichten
– z.B.WM97/Jerk: “I think *** is a big stupid jerk”
•Pranks
– z.B. Yankee spielt “Yankee Doodle Dandy” um 17 Uhr
•Zugriffsverweigerung
– z.B.WM97/NightShade errichtet Passwortschutz für Dokument am Freitag, den 13.
•Datendiebstahl
– z.B. Troy/LoevLet emailt Maschinen und Benutzerinformation auf die Philipinen
•Datenbeschädigung
– z.B. XM/Compatable ändert Daten in Excel-Tabellen
•Datenlöschung
– z.B. Michelangelo überschreibt Teile der Festplatte am 6. März
•Hardwaresteuerung
– z.B. Chernobyl versucht BIOS am 26. April zu überschreiben
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
46
Ausbreitungsverhalten
•Beobachtungen:
– Die meisten Viren kommen in der freien Wildbahn nicht vor
– Andere erreichen einen hohen Ausbreitungsgrad
•Wie schnell breitet sich ein Virus in einem idealisierten Umfeld aus?
•Welchen Anteil der Population infiziert der Virus?
•Probleme:
– Kommunikationsverhalten
• bestimmt Ausbreitung des Virus
• ist i.A. unbekannt, wird bösartig beeinflußt
• verändert sich bei Ausbreitung eines Virus
– Übertragungswahrscheinlichkeit
• unterschiedlich, verändert sich, z.B. durch verändertes Verhalten, AntiVirus-Software
– Virustod
• durch Virusverhalten, z.B. Crash
• durch Benutzerverhalten
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
47
Mathematische Modelle
•SI-Modell (rumor spreading)
– susceptible → infected
•SIS-Modell (birthrate/deathrate)
– susceptible → infected → susceptible
•SIR-Modell
– susceptible → infected → recovered
•Kontinuierliche Modelle
– Deterministisch
– Stochastisch
– führt zu Differentialgleichungen
•Diskrete Modelle
– Graphbasierte Modelle
– Random Call-basiert
– Analyse von Markov-Prozesse
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
48
Infektionsmodelle
•SI-Modell (rumor spreading)
– susceptible → infected
– Am Anfang ist ein Individuum infiziert
– Bei jedem Kontakt wird ein Individuum unheilbar angesteckt
– In jeder Zeiteinheit finden (erwartet) ß Kontakte statt
•SIS-Modell (birthrate/deathrate)
– susceptible → infected → susceptible
– Wie SI-Modell, aber ein Anteil δ aller Infizierten wird geheilt, aber wieder empfänglich für Virus
– Alternativ: Mit Wahrscheinlichkeit δ wird Individuum wieder empfänglich
•SIR-Modell
– susceptible → infected → recovered
– Wie SIS-Modell, aber einmal geheilte Individuen, sind immun gegen Virus
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
49
Deterministische Modellierung
•Susceptible, Infected, Recovered
– S(t), s(t) := S(t)/n; absolute Anzahl/relativer Anteil Gesunder zum Zeitpunkt t
– I(t), i(t) := I(t)/n; absolute Anzahl/relativer Anteil Infizierter
– R(t), r(t) := R(t)/n; absolute Anzahl/relativer Anteil Geheilter
•In jeder Zeiteinheit kontaktiert jedes Individuum ß Partner
•Jeder der ß i(t) S(t) Kontakte mit einem Infizierten ist ansteckend
•SI-Modell: Kranke bleiben infektiös
– I(t+1) = I(t) + ß i(t) S(t)
– S(t+1) = S(t) – ß i(t) S(t)
•SIS-Modell: In jeder Runde wird ein Anteil δ geheilt
– I(t+1) = I(t) - δ I(t) + ß i(t) S(t)
– S(t+1) = S(t) + δ I(t) – ß i(t) S(t)
•SIR-Modell: Ein δ Anteil aller Infizierten wird immun
– S(t+1) = S(t) – ß i(t) S(t)
– I(t+1) = I(t) – δ I(t) + ß i(t) S(t)
– R(t+1) = R(t) + δ I(t)
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
50
Ergebnis SI-Modell
•SI-Modell: Kranke bleiben infektiös
– i(t+1) = i(t) + ß i(t) s(t)
– s(t+1) = s(t) – ß i(t) s(t)
•Kann geschlossen dargestellt werden.
•Anfangs steigt s(t) exponentiell
•Dann nimmt i(t) exponentiell ab
Zeit
i(t)
s(t)
1
0
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
51
Ergebnis SIS-Modell
•SIS-Modell: In jeder Runde wird ein Anteil δ geheilt
– i(t+1) = i(t) - δ i(t) + ß i(t) s(t)
– s(t+1) = s(t) + δ i(t) – ß i(t) s(t)
•Kann zu Gleichgewichtszustand für bestimmte Parameter ß,δ führen
•Dann bleibt das Verhältnis Infizierten zu Ansteckenden stabil
– Muss aber nicht
– Dann kommte es zu Wiederausbruch der Epidemie
Zeit
i(t)
s(t)
1
0
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
52
Ergebnis SIR-Modell
•SIR-Modell: Ein δ Anteil aller Infizierten wird immun
– s(t+1)= s(t) – ß i(t) s(t)
– i(t+1)= i(t) – δ i(t) + ß i(t) s(t)
– r(t+1)= r(t) + δ i(t)
•Je nach Parameter wird ein gewisser Anteil aller Infiziert
– jedoch nicht notwendigerweise alle
•Führt in jedem Fall zu einem Gleichgewichtszustand
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Randomisierte Modelle für SI-Infektionen
•In jeder Runde ruft jeder Teilnehmer einen zufälligen Teilnehmer an
•Push:
– Der Anrufer A erzählt dem Angerufenen B das neue Gerücht
•Pull:
– Der Angerufene B erzählt dem Anrufer A das neue Gerücht
•Push&Pull:
– Beide erzählen das Gerücht
PushPush
PullPullPush&PullPush&Pull
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Ausbreitung: Push
•Startphase: i(t)<1/2
Sättigung: s(t) < 1/2
Sicherung
Zeit
i(t)
s(t)
1
0
log2 n ln n O(ln n)
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Gerüchteausbreitung: Pull
Startphase i(t) < 1/2
Sättigung
s(t) < 1/2Sicherung
Zeiti(t)
s(t)
1
0
O(ln n) + log2n log log n O(log log n)
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Gerüchteausbreitung: Push & Pull
Startphase i(t)<1/2
Sättigung
s(t) < 1/2Sicherung
Zeit
i(t)
s(t)
1
0
log3n log log n O(log log n)
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Warum Pull schlecht startet und Push schlecht abschließt
•Die Wahrscheinlichkeit, dass jemand in einer Runde keinen Anruf bekommt, ist
•Pull: Mit Wahrscheinlichkeit 1/e verbreitet sich das Gerücht in der ersten Runde nicht weiter
•Push: Mit Wahrscheinlichkeit 1/e kann ein Knoten in der Sättigung nicht erreicht werden
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
58
Warum Pull so schnell endet
•Die Wahrscheinlichkeit, dass ein Nicht-Infizierter einen Nicht-Infizierten anruft, ist s(t)
•Pull: Damit ist der erwartete Anteil Nicht-Infizierter in der nächsten Runde: E[s(t+1)] = s(t)2
•Damit ist der Pull-Mechanismus der stärkste bekannte (anynome) Ansteckungsmechanismus
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
59
Rückblick
•Das Internet: Einführung und Überblick
•Mathematische Grundlagen
•IP: Routing im Internet
•TCP: Das Transport-Protokoll des Internets
•Die Struktur des World Wide Web und des Internets
•Suche im Web
•Web-Caching im Internet
•Peer-to-peer-Netzwerke
•Angriffe auf das Internet
Algorithmen des Internets 2005-12
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
60
Vorausblick
•Wintersemester 2005/2006
– Vorlesung:
• Algorithms for Radio Networks (in englisch)
– PG
• Integrating PAMANET into the Internet
•Sommersemester 2006
– Vorlesung:
• Peer-to-Peer-Netzwerke
– Seminar
• Thema noch offen
•Nicht vergessen Abschlussveranstaltung am
– Donnerstag 21.07.2005, 19 Uhr am Beach-Volleyballfled
– Grillsachen bitte selbst organisieren....
– Getränke werden gestellt
61
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und Komplexität
Vielen Dank: Ende der 12. und letzten Vorlesung
Nächste Woche: Projektgruppenvorstellung!!!Letzte Übung und Vorbesprechung der mündlichen Prüfung: Mo. 20.07.2005
Viel Erfolg bei der mündlichen Prüfung!Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn
Tel.: 0 52 51/60 66 92Fax: 0 52 51/62 64 82E-Mail: [email protected]://www.upb.de/cs/schindel.html