You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@spamassassin.apache.org by bu...@bugzilla.spamassassin.org on 2005/03/04 06:33:04 UTC
[Bug 4170] New: Obfuscated text with (arbitrary) edit distances
http://bugzilla.spamassassin.org/show_bug.cgi?id=4170
Summary: Obfuscated text with (arbitrary) edit distances
Product: Spamassassin
Version: unspecified
Platform: Other
OS/Version: other
Status: NEW
Severity: normal
Priority: P5
Component: Rules (Eval Tests)
AssignedTo: dev@spamassassin.apache.org
ReportedBy: scrosby@cs.rice.edu
Obfuscated text is something thats fairly prevalent in email. Here's
an edit distance algorithm, and a set of distance metrics thats pretty
good at handling and dealing with many types of obfuscations.
By using arbitrary costs instead of the Levenshtein Distance (all
costs=1), it is much more sensitive to minor changes. The
algorithm is paramatarized by 3 tables that allow seperate costs to be
specified for inserting each type of character, deleting each type of
character, and all pairs of replacing one character with another. (so,
eg, deleting vowels is cheap, inserting [._,] is cheap, and replacing
a 'i' with '1' is cheap.)
Here is a sample output:
lolita lol....ita : 0.04;
lolita l*l*t* : 0.09;
viagra v....ia...gra : 0.07;
viagra v*agra : 0.03;
viagra v*ag.r a : 0.06;
lolita l()l!t.a : 0.07;
lolita l(ss)l!t.a : 1.87;
lolita l()l!t12.a : 0.67;
mortgage mort(age : 0.91;
>From this it is clear it is robust with both the replacement of
characters with '.' and with the insertion of extra *'s. It also handles
inserted spaces.
A sample selftest looking for FP's:
viagra Agra : 1.5;
lolita iota : 1.55;
lolita lilt : 1.3;
lolita Lola : 1.5;
lolita Lolita's : 0.91;
lolita loll : 1.55;
lolita Lila : 1.6;
Experience and experimentation is sure to find better distance tables.
One flaw with the algorithm is that the performance on an AMD XP-2500+
is only about 10k matches per second. Some filter to remove tokens is
necessary. I have a few ideas. One idea might be to only apply this to
tokens that aren't in the bayes database. Another option would be to
apply this to 'suspicious tokens' only.
------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
[Bug 4170] Obfuscated text with (arbitrary) edit distances
Posted by bu...@bugzilla.spamassassin.org.
http://bugzilla.spamassassin.org/show_bug.cgi?id=4170
------- Additional Comments From scrosby@cs.rice.edu 2005-03-03 21:34 -------
Created an attachment (id=2679)
--> (http://bugzilla.spamassassin.org/attachment.cgi?id=2679&action=view)
Edit distance prototype
------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
[Bug 4170] Obfuscated text with (arbitrary) edit distances
Posted by bu...@bugzilla.spamassassin.org.
http://issues.apache.org/SpamAssassin/show_bug.cgi?id=4170
felicity@apache.org changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|3.2.0 |Future
------- Additional Comments From felicity@apache.org 2006-09-10 06:06 -------
No movement -> future
------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
[Bug 4170] Obfuscated text with (arbitrary) edit distances
Posted by bu...@bugzilla.spamassassin.org.
http://bugzilla.spamassassin.org/show_bug.cgi?id=4170
Bob@Menschel.net changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|Undefined |3.2.0
------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.