Seminar on Spam Filtering - SS 05

Lehrveranstaltung 20.410.4 im TUD Vorlesungsvorzeichnis

Die Seminar-Noten hängen - soweit ich die Ausarbeitungen bereits erhalten habe - vor E304 aus.

Inhalt

In diesem Seminar werden verschiedene Aspekte im Zusammenhang mit Spam Mail Filtering besprochen. Das Spektrum wird dabei Bereiche wie Spamming-Techniken, adaptiven Spam-Filter, bekannte Spam-Filter Pakete, Evaluierung von Spam-Filtern, rechtliche Aspekte usw. abdecken.

Die einzelnen Themenbereiche werden von den Teilnehmern aufbereitet, in einem ca. 45-minütigen Kurz-Vortrag (30 min Vortrag, 15 min Diskussion) präsentiert und schriftlich ausgearbeitet.

Es wird erwartet, daß Sie die Vorträge mit Slides begleiten. Falls Sie keinen Laptop haben, bitte mir die Slides rechtzeitig zu senden, damit ich sie auf meinem Laptop einspielen bzw. testen kann. Die Vorträge und/oder Slides können wahlweise auf Deutsch oder Englisch gehalten werden.

Benotung

In die Gesamtnote fließen die Ausarbeitung des Vortrags (Folien und schriftliche Ausarbeitung), die Präsentation, die Beantwortung von Fragen zum Vortrag, sowie die aktive Teilnahme an der Diskussion bei den Vorträgen anderer ein.

Vorbereitungsgespräche:

Falls Sie das wünschen, können wir uns in der Woche vor Ihrem Vortrag (Montag vor Ihrem Vortrag ist zu spät) über Ihre Präsentation unterhalten. Dazu sollten Sie mit einem mehr oder weniger fertig ausgearbeiteten Vortrag kommen, den wir dann kurz durchbesprechen, bzw. versuchen eventuelle Fragen zu klären.

Termine können wir frei vereinbaren, düblicherweise freitags.

Hardware:

Falls Sie die Folien von meinem Laptop aus präsentieren wollen, ist das kein Problem, aber Sie sollten mir die Folien rechtzeitig schicken (ansonsten gehe ich davon aus, daß sie Ihr eigenes Gerät mitbringen). Open Office, Powerpoint, und PDF sind kein Problem, alles andere nach Rücksprache.

Termine

jeweils Dienstag, 16:15 - 17:55, Raum S2/02|A102.

19.4. Vorbesprechung
3.5. Einführung
Einführung in das Problem
Spamming Techniques (Sebastian Blume)
10.5 Machine Learning Ansätze 1: Bayesian Filtering
Graham's filter, bogofilter (Charles Wijaya)
Spam Bayes (Arne Pottharst)
17.5. Machine Learning Ansätze 2
CRM 114 (Maryam Zadmajid)
Memory-Based and Other Machine Learning Techniques (Christian Stöhr)
24.5. Kollaborative Ansätze 1
Peer-to-Peer Spam filtering (Gregor Mitsch)
Social Networks (Christian Zimmer)
31.5. Kollaborative Ansätze 2
Detecting Near-Duplicate Messages (Simon Kulessa)
DCC, Razor, Pyzor (Andreas Göb)
7.6. Integrative Ansätze
Multi-faceted Systems (Jens Liebau)
Spam Assassin (Christian Hett)
14.6. Juristische und wirtschaftliche Aspekte
Legal Aspects (Daniel Szallies)
Economic Approaches (Jacqueline Vogel)
21.6. Ökonomische Ansätze

28.6.Erkennen beim Sender
Stopping Outgoing Spam (Darius Gasiorek)
Sender Identification (Oliver Staudt)
5.7. Evaluierung von Spam Mail Filtern
Spam Mail and E-mail Corpora (Sebastian Frischbier)
Evaluating Spam Filters (Thomas Widjaja)

Materialien

Die unten angegebenen Artikel und Web-links dienen als erste Anhaltspunkte, jedoch wird erwartet, daß sich die Vortragenden auch weiterführende Referenzen und Informationsquellen ansehen.

Überblick

Grundlegende Materialen, die sich alle ansehen sollten.

Geoff Hulten and J. Goodman: ICML-04 Tutorial on Junk E-mail Filtering
José María Gómez Hidalgo's Spam Bibliography and Spam Detection Resources

Understanding the Problem

Erste Einführung in das Problem, mit Schwerpunkt auf die Herausforderung für KDD.

Lorrie Faith Cranor and Brian A. LaMacchia.Spam! Communications of the ACM. Vol. 41, No. 8 (Aug. 1998), Pages 74-83.
Tom Fawcett: "In vivo" spam filtering: a challenge problem for KDD. SIGKDD Explorations 5(2): 140-148 (2003)
B. Reinhard Spam-Schutz - mangelhafte Filter und eingeschränkte Benutzerfreundlichkeit

Spamming Techniques

Welche Tricks verwenden Spammer eigentlich?

The Spammer's Compendium
Gregory L. Wittel and S. Felix Wu: On Attacking Statistical Spam Filters, CEAS 2004.
Christine E. Drake, Jonathan J. Oliver, and Eugene J. Koontz Anatomy of a Phishing Email, CEAS 2004
Geoff Hulten, Anthony Penta, Gopalakrishnan Seshadrinathan, Manav Mishra: Trends in Spam Products and Methods, CEAS, 2004.

Paul Graham's Filter

Ein einfacher adaptiver Spam-Filter, der auf Ideen aus Bayes'schen Filtern basiert, und bei vielen Open Source Projekten (insbesondere Mozilla und Thunderbird) als Basis verwendet wird.

Spam Bayes

Spam Bayes ist eine Bayesian Spam Filtering System, das auf Graham's Algorithmus basiert, aber etliche Verbesserungen von Gary Robinson und anderen enthält.

http://www.spambayes.org
T.A Meyer and B Whateley: SpamBayes: Effective open-source, Bayesian based, email classification system., CEAS 2004.
Gary Robinson: Spam Detection
Gary Robinson: A Statistical Approach to the Spam Problem Linux Journal.

CRM 114

CRM114 basiert auf einer Technik namens Sparse Binary Polynomial Matching und nimmt für sich ausgesprochen hohe Genauigkeiten in Anspruch.

http://crm114.sourceforge.net/
William S. Yerazunis, The Spam-Filtering Accuracy Plateau at 99.9% Accuracy and How to Get Past It. 2004 MIT Spam Conference.
William S. Yerazunis, Sparse Binary Polynomial Hashing and the CRM114 Discriminator, 2003 MIT Spam Conference

Machine Learning Techniques

Verschiedenste Maschinelle Lern-Techniken wurden bereits für diese Aufgabe untersucht. Die folgenden beiden Arbeiten sind nur eine kleine Auswahl.

Georgios Sakkis, Ion Androutsopoulos, Georgios Paliouras, Vangelis Karkaletsis, Constantine D. Spyropoulos, Panagiotis Stamatopoulos: A Memory-Based Approach to Anti-Spam Filtering for Mailing Lists. Information Retrieval 6(1): 49-73 (2003).
Gómez Hidalgo, J.M. Evaluating Cost-Sensitive Unsolicited Bulk Email Categorization. ACM Symposium on Applied Computing, 2002.

Peer-to-Peer Spam Filtering

Ansätze zum verteilten E-mail Filtering.

Alan Gray, Mads Haahr, Personalised, Collaborative Spam Filtering
Feng Zhou, Li Zhuang, Ben Zhao, Ling Huang, Anthony D. Joseph, and John Kubiatowicz, Approximate Object Location and Spam Filtering on Peer-to-Peer Systems, In the Proceedings of ACM/IFIP/USENIX International Middleware Conference (Middleware 2003), Rio de Janeiro, Brazil, June, 2003

Social Networks

Die folgenden Arbeiten konzentrieren sich auf soziale Netzwerke, die durch das Senden und Empfangen von E-mails entstehen.

P. Oscar Boykin and Vwani Roychowdhury: Personal Email Networks: An Effective Anti-Spam Tool
Jennifer Golbeck, James Hendler: Reputation Network Analysis for Email Filtering

Detecting Near-Duplicate Messages

Kollaborative Ansätze müssen sich darauf verlassen, daß man Duplikate (also identische oder in wesentlichen Punkten identische) Nachrichten erkennen kann. Das ist ein nicht triviales Problem.

A. Chowdhury, O. Frieder, D. A. Grossman, and M. C. McCabe. Collection statistics for fast duplicate document detection. ACM Transactions on Information Systems, 20(2):171-191, 2002.
Aleksander Kolez, Abdur Chowdhury, and Joshua Alspector: The Impact of Feature Selection on Signature-Driven Spam Detection

Collaborative Spam Filtering Systems

Ein Kurzüberblick über die wichtigsten Systeme, die auf einen kollaborativen Ansatz setzen.

Multifaceted Systems

Viele Systeme setzen auf eine offene Architektur, und die Integration vieler verschiedener Komponenten.

Richard Segal, Jason Crawford, Jeffrey Kephart, Barry Leiba SpamGuru: An Enterprise Anti-Spam Filtering System, CEAS 2004.
Barry Leiba, Nathaniel Borenstein A Multifaceted Approach to Spam Reduction, CEAS 2004.
Joshua Goodman, Robert Rounthwaite SmartProof

Spam Assassin

Spam Assassin ist eine offenes Spam-Bekämpfungs-System, das verschiedene Techniken miteinander zu integrieren versucht. Geben Sie einen Überblick über dieses System in allen seinen Komponenten.

http://spamassassin.apache.org/
Alexander K. Seewald Combining Bayesian and Rule Score Learning: Automated Tuning for SpamAssassin

Legal Aspects of Spam Filtering

Erarbeiten Sie eine kurze Präsentation über die Anti-Spam Gesetze verschiedener Länder, insbesondere natürlich EU und USA.

http://www.spamlaws.com
Nicola Lugaresi European Union vs. Spam: A Legal Response, CEAS 2004.

Economic Solutions

Eine Grundvoraussetzung für Spamming ist, daß das Senden vom Spam Mails billig ist. Könnte man die Kosten dafür erhöhen, wäre Spamming nicht mehr rentabel.

Sam Vaknin: The Economics of Spam
S. E. Fahlman. Selling interrupt rights: A way to control unwanted email and telephone calls. IBM Systems Journal, 41(4):759--766, 2002.
Kang Li, Calton Pu, Mustaque Ahamad Resisting SPAM Delivery by TCP Damping, CEAC 2004.

Pricing via Processing

Hier wird dem Sender Rechenzeit zur Lösung einfacher kombinatorischer Aufgaben abverlangt, mit der Idee, daß das für einzelne Sender ein vertretbarer Aufwand ist, für Spammers aber nicht.

Dwork and Naor: Pricing via Processing or Combatting Junk Mail. Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. pp. 139 - 147, 1992.
Cynthia Dwork, Andrew Goldberg and Moni Naor, On Memory-Bound Functions for Fighting Spam, Proc. Crypto 2003.
Moni Naor, Verification of a human in the loop or Identification via the Turing Test

The Penny Black Project

Ein Microsoft Projekt, das der Idee Pricing via Processing gewidmet ist.

Project Home-Page
M. Abadi, A. Birrell, M. Burrows, F. Dabek, and T. Wobber. Bankable Postage for Network Services Proceedings of the 8th Asian Computing Science Conference, Mumbai, India, December 2003
M. Abadi, M. Burrows, M. Manasse, and T. Wobber. Moderately Hard, Memory-bound Functions, Proceedings of the 10th Annual Network and Distributed System Security Symposium, February 2003.

Stopping Outgoing Spam

Während die meisten Ansätze darauf abzielen, Spam Mails beim Empfänger zu erkennen, gibt es einige Ansätze, die versuchen, das Problem auf der Seite des ISPs zu lösen.

Richard Clayton, Stopping Spam by Extrusion Detection, CEAS 2004.
Joshua Goodman, Robert Rounthwaite. Stopping Outgoing Spam ACM Conference on E-Commerce, May 2004.

Sender Identification

Es gibt verschiedene Vorschläge, die eine verläßliche Identifizierung des Absenders von E-mails zum Ziel haben.

Spam Mail and Other E-mail Corpora

Beschreiben Sie existierende Spam-Mail Corpora, wie sie erstellt wurden, ihre Charakteristika, Vergleiche anstellen, etc.

J. Goodman, G. Hulten, R. Rouhthwaite: Filtering Spam E-mail on a Global Scale Proceedings WWW 2004.
B. Klimt, Y. Yang: Introducing the Enron Corpus, Proc. CSEAS, 2004
http://www.spamarchive.org
links zu weiteren Corpora finden Sie hier

Evaluating Spam Filters

Wie sollen Spam Filter evaluiert werden?

Gordon Cormack and Thomas Lynam A Study of Supervised Spam Detection Applied to Eight Months of Personal Email
Ion Androutsopoulos, John Koutsias, Konstantinos Chandrinos, Constantine D. Spyropoulos: An experimental comparison of naive bayesian and keyword-based anti-spam filtering with personal e-mail messages. SIGIR 2000: 160-167
F. D. Garcia, J.-H. Hoepman, and J. van Nieuwenhuizen, Spam Filter Analysis, Proceedings of 19th IFIP International Information Security Conference, WCC2004-SEC, 2004.

Johannes Fuernkranz

Last modified: Thu Apr 28 21:44:17 CEST 2005