Help beautify ugly heuristic code

**Mitja** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

On Wed, 08 Dec 2004 16:09:43 -0500, Stuart D. Gathman <stuart@bmsi.co m>
wrote:
[color=blue]
> I have a function that recognizes PTR records for dynamic IPs....
> Here is the very ugly code so far.
> ...
> # examples we don't yet recognize:
> ...[/color]

This doesn't help much; post example of all the possible patterns you have
to match (kind of like the docstring at the beginning, only more
elaborate), otherwise it's hard to know what kind of code you're trying to
implement.
--
Mitja

**Stuart D. Gathman** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

On Wed, 08 Dec 2004 18:00:06 -0500, Mitja wrote:
[color=blue]
> On Wed, 08 Dec 2004 16:09:43 -0500, Stuart D. Gathman <stuart@bmsi.co m>
> wrote:
>[color=green]
>> I have a function that recognizes PTR records for dynamic IPs.... Here
>> is the very ugly code so far.
>> ...
>> # examples we don't yet recognize:
>> ...[/color]
>
> This doesn't help much; post example of all the possible patterns you
> have to match (kind of like the docstring at the beginning, only more
> elaborate), otherwise it's hard to know what kind of code you're trying
> to implement.[/color]

This is a heuristic, so there is no exhaustive list or hard rule.
However, I have posted 23K+ examples at http://bmsi.com/python/dynip.samp
with DYN appended for examples which the current algorithm classifies
as dynamic.

Here are the last 20 (which my subjective judgement says are correct):

65.112.76.15 usfshlxmx01.myr eg.net
201.128.108.41 dsl-201-128-108-41.prod-infinitum.com.m x DYN
206.221.177.128 mail128.tanthil lyingyang.com
68.234.254.147 68-234-254-147.stmnca.adel phia.net DYN
63.110.30.30 mx81.goingwitht he-flow.info
62.178.226.189 chello062178226 189.14.15.vie.s urfer.at DYN
80.179.107.85 80.179.107.85.i speednet.net DYN
200.204.68.52 200-204-68-52.dsl.telesp.n et.br DYN
12.203.156.234 12-203-156-234.client.insi ghtBB.com DYN
200.83.68.217 CM-lconC1-68-217.cm.vtr.net DYN
81.57.115.43 pauguste-3-81-57-115-43.fbx.proxad.n et DYN
64.151.91.225 sv2a.entertainm entnewsclips.co m
64.62.197.31 teenfreeway.spa rklist.com
201.9.136.235 201009136235.us er.veloxzone.co m.br DYN
66.63.187.91 91.asandox.com
83.69.188.198 st11h07.ptambre .com
66.192.199.217 66-192-199-217.pyramidcoll ection.org DYN
69.40.166.49 h49.166.40.69.i p.alltel.net DYN
203.89.206.62 smtp.immigratio nexpert.ca
80.143.79.97 p508F4F61.dip0. t-ipconnect.de DYN

**Lonnie Princehouse** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

Regular expressions.

It takes a while to craft the expressions, but this will be more
elegant, more extensible, and considerably faster to compute (matching
compiled re's is fast).

Example using the top five from your function's comments:

.. host_patterns = [
.. '^1Cust\d+\.tnt \d+\..*\.da\.uu \.net$',
.. '^user\d+\.net\ d+\.mo\.sprint-hsd\.net$',
.. '^.*\.roadrunne r\.nf\.net$',
.. ]
..
.. host_expr = re.compile('|'. join(host_patte rns))
..
.. # only implementing host string matching, but you get the idea.
.. def is_dynip(host):
.. # host names are case insensitive
.. host = host.lower()
.. return host_expr.match (host) is not None
[color=blue][color=green]
>> is_dynip("1Cust 200.tnt8.bne1.d a.uu.ne")[/color][/color]
True[color=blue][color=green]
>> is_dynip("googl e.com")[/color][/color]
False

(the dots preceding code are to fool indentation stripping... please
ignore them)

**Stuart D. Gathman** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

On Wed, 08 Dec 2004 18:39:15 -0500, Lonnie Princehouse wrote:
[color=blue]
> Regular expressions.
>
> It takes a while to craft the expressions, but this will be more
> elegant, more extensible, and considerably faster to compute (matching
> compiled re's is fast).[/color]

I'm already doing that with the rehmac regex. I like your idea for making
it more readable, though. Looking for permutations of the IP address
gives much more bang for the line of code than most host only regexes
since it is ISP independent. At least one ISP uses roman numerals to code
the IP for their dynamic addresses! I tried matching a custom regex
computed from the IP, but compiling the regex for each test was too slow.

I could keep adding more patterns, but I was hoping for a tool that
"learns" from a database of preclassified examples how to recognize the
pattern. And the resulting data would be reasonably compact. I don't ask
for much, do I? A Bayesian classifier would have too big of a database, I
think. I've seen neural nets do amazing things with only 100 or so
neurons - a small weight database. But they are slow in software.

I have posted 10K preclassified (by current algorithm) examples here:

http://bmsi.com/python/dynip.samp

**Carlos Ribeiro** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

On 8 Dec 2004 15:39:15 -0800, Lonnie Princehouse
<finite.automat on@gmail.com> wrote:[color=blue]
> Regular expressions.
>
> It takes a while to craft the expressions, but this will be more
> elegant, more extensible, and considerably faster to compute (matching
> compiled re's is fast).[/color]

I think that this problem is probably a little bit harder. As the OP
noted, each ISP uses a different notation. I think that a better
solution is to use a statistical approach, possibly using a custom
Bayesian filter that could "learn" a little bit about some patters.

The basic idea is as follows:

-- break the URL in pieces, using not only the dots, but also hyphens
and underscores in the name.

-- classify each part, using REs to identify common patterns: frequent
strings (com, gov, net, org); normal words (sequences of letters);
normal numbers; combinations of numbers & letters; common substrings
can also be identified (such as isp, in the middle of one of the
strings).

-- check these pieces against the Bayesian filter, pretty much as it's
done for spam.

I think that this approach is promising. It relies on the fact that
real servers usually do not have numbers in their names; however,
exact identification either by a match or a regular expression is very
difficult. I'm willing to try it, but first, more data is needed.

--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: carribeiro@gmai l.com
mail: carribeiro@yaho o.com

**Lonnie Princehouse** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

I don't think a Bayesian classifier is going to be very helpful here,
unless you have tens of thousands of examples to feed it, or unless it
was specially coded to first break addresses into better tokens for
classification (such as alphanumeric strings and numbers).

The series of if host.find(...) lines in is_dynip() is equivalent to a
regular expression, but much more expensive to execute because of all
the list slicing, and it won't benefit from the re module's speedy
native implementation of regular expressions.

Try building a host_expr (as per my previous post) in the following
way:

# suppose dynamic_host_li st is a list of all the host strings already
known to be
# dynamic.

.. host_patterns = {} # use a dict to guarantee uniqueness. sets would
also work.
.. number_expr = re.compile("\d+ ")
.. for dynamic_host in dynamic_host_li st:
.. pattern = '^' + number_expr.sub ("\d+", dynamic_host) + '$'
.. host_patterns[pattern] = True
..
.. host_expr = re.compile('|'. join(host_patte rns.keys()))

This will catch any hostname that differs only in numbers from any
other host you've
already classified.

For IP addresses, you really just need a mechanism to filter blocks of
IP addresses. It might be easiest to first convert them into hex and
then make liberal use of [0-f] in regular expressions.

**Stuart D. Gathman** · Jul 18 '05, 06:29 PM

Re: Help beautify ugly heuristic code

On Wed, 08 Dec 2004 19:52:53 -0500, Lonnie Princehouse wrote:
[color=blue]
> I don't think a Bayesian classifier is going to be very helpful here,
> unless you have tens of thousands of examples to feed it, or unless it[/color]

We do have tens of thousands of examples to feed it.
[color=blue]
> The series of if host.find(...) lines in is_dynip() is equivalent to a
> regular expression, but much more expensive to execute because of all[/color]

It is not equivalent, because the patterns are based on the IP address.
As I mentioned before, I tried building a custom regex from the IP for
each test - but compiling the regex is way too slow to be done for each
test.
[color=blue]
> For IP addresses, you really just need a mechanism to filter blocks of
> IP addresses. It might be easiest to first convert them into hex and
> then make liberal use of [0-f] in regular expressions.[/color]

The point of the ip address is *not* to recognize ip addresses. The
point is to look for transformations of the ip address in the hostname.
This gives a *huge* bang for the buck. I have been working on this
problem for a while. If the hostname has a transformation of the ip
address - it is (almost certainly) a dynamic address. The ISPs are very
creative in their transformations , using the parts of the ip in various
orders and encoding in hex, base64, decimal with or without zerofill, and
even roman numerals.

The regex engine is just not powerful enough to handle parameterized
regexe (that I know of).

**Lonnie Princehouse** · Jul 18 '05, 06:30 PM

Re: Help beautify ugly heuristic code

Doh! I misread "a" as host instead of ip in your first post. I'm
sorry about that; I really must slow down. Anyhow,

I believe you can still do this with only compiling a regex once and
then performing a few substitutions on the hostname.

Substitutions:

1st byte of IP => (0)
2nd byte of IP => (1)
3rd byte of IP => (2)
4th byte of IP => (3)
and likewise for hex => (x0) (x1) (x2) (x3)

Each host string will possibly map into multiple expansions, esp. if a
number repeats itself in the IP, or if an IP byte is less than 10 (such
that the decimal and hex representations are the same). Zero-padded
and unpadded will both have to be substituted, and it's probably best
to not to alter the last two fields in the host name since ISPs can't
change those.

With this scheme, here are a few expansions of (ip,host) tuples:

172.182.240.186 ACB6F0BA.ipt.ao l.com
becomes
(x0)(x1)(x2)(x3 ).ipt.aol.com

67.119.55.77 adsl-67-119-55-77.dsl.lsan03.p acbell.net
becomes
adsl-(0)-(1)-(2)-(3).dsl.lsan03. pacbell.net
adsl-(0)-(1)-(2)-(x1).dsl.lsan03 .pacbell.net

81.220.220.143 ip-143.net-81-220-220.henin.rev.n umericable.fr
becomes
ip-(3).net-(0)-(1)-(1).henin.rev.n umericable.fr
ip-(3).net-(0)-(1)-(2).henin.rev.n umericable.fr
ip-(3).net-(0)-(2)-(1).henin.rev.n umericable.fr
ip-(3).net-(0)-(2)-(2).henin.rev.n umericable.fr

etcetera.

Now you can run a precompiled regular expression against these hostname
permutations, i.e. ".*$0$.*$1$ .*$2$.*$3$. *" would match any
host in which the IP address numbers appeared in the correct order.

There are only a handful dynamic addresses in your sample data that
don't match a decimal or hexadecimal IP-based pattern, e.g.

68.53.109.99 pcp03902856pcs. nash01.tn.comca st.net
68.147.136.167 s01060050bf91c1 e4.cg.shawcable .net

**Mitja** · Jul 18 '05, 06:30 PM

Re: Help beautify ugly heuristic code

On Wed, 08 Dec 2004 16:09:43 -0500, Stuart D. Gathman <stuart@bmsi.co m>
wrote:
[color=blue]
> I have a function that recognizes PTR records for dynamic IPs. There is
> no hard and fast rule for this - every ISP does it differently, and may
> change their policy at any time, and use different conventions in
> different places. Nevertheless, it is useful to apply stricter
> authentication standards to incoming email when the PTR for the IP
> indicates a dynamic IP (namely, the PTR record is ignored since it
> doesn't
> mean anything except to the ISP). This is because Windoze Zombies are
> the
> favorite platform of spammers.[/color]

This is roughly it.... you'll have to experiment and find the right
numbers for different pattern matches, maybe even add some extra criteria
etc. I don't have the time for it right now, but I'd be interested to know
how much my code and yours differ in the detection process (i.e. where are
the return values different).

Hope the indentation makes it through alright.

#!/usr/bin/python

import re
reNum = re.compile(r'\d +')
reWord = re.compile(r'(? <=[^a-z])[a-z]+(?=[^a-z])|^[a-z]+(?=[^a-z])')
#words that imply a dynamic ip
dynWords = ('dial','dialup ','dialin','ads l','dsl','dyn', 'dynamic')
#words that imply a static ip
staticWords = ('cable','stati c')

def isDynamic(host, ip):
"""
Heuristically checks whether hostname is likely to represent
a dynamic ip.
Returns True or False.
"""

#for easier matching
ip=[int(p) for p in ip.split('.')]
host=host.lower ()

#since it's heuristic, we'll give the hostname
#(de)merits for every pattern it matches further on.
#based on the value of these points, we'll decide whether
#it's dynamic or not
points=0;

#the ip numbers; finding those in the hostname speaks
#for itself; also include hex and oct representations
#lowest ip byte is even more suggestive, give extra points
#for matching that
for p in ip[:3]:
#bytes 0, 1, 2
if (host.find(`p`) != -1) or (host.find(oct( p)[1:]) != -1): points+=20
#byte 3
if (host.find(`ip[3]`) != -1) or (host.find(oct( ip[3])[1:]) != -1):
points+=60
#it's hard to distinguish hex numbers from "normal"
#chars, so we simplify it a bit and only search for
#last two bytes of ip concatenated
if host.find(hex(i p[3])[2:]+hex(ip[3])[2:]) != -1: points+=60

#long, seemingly random serial numbers in the hostname are also a hint
#search for all numbers and "award" points for longer ones
for num in reNum.findall(h ost):
points += min(len(num)**2 ,60);

#substrings that are more than just a hint of a dynamic ip
for word in reWord.findall( host):
if word in dynWords: points+=30
if word in staticWords: points-=30

print '[[',points,']]'
return points>80

if __name__=='__ma in__':
for line in open('dynip.sam p').readlines()[:50]:
(ip,host) = line.rstrip('DY N').split()[:2]
if host.find('.') != -1:
print host, ip, ['','DYNAMIC'][isDynamic(host, ip)]

--
Mitja

**Jeremy Sanders** · Jul 18 '05, 06:31 PM

Re: Help beautify ugly heuristic code

On Wed, 08 Dec 2004 18:38:14 -0500, Stuart D. Gathman wrote:
[color=blue][color=green]
>> Here are the last 20 (which my subjective judgement says are correct):[/color]
>
> 65.112.76.15 usfshlxmx01.myr eg.net 201.128.108.41[/color]
[snip][color=blue]
> 80.143.79.97 p508F4F61.dip0. t-ipconnect.de DYN[/color]

Looks like you could do something like look for a part of the dns name
which is over a certain length with a high fraction of numbers and
punctuation characters.

Of course, you could build up a probability tree of the chance of a
character being followed by another character in a dynamic name and a
static name.

This might work well, as many are sequences of numbers (high chance of
number followed by number), and mixed characters and numbers, which are
unusual in normal dns names.

Jeremy

**Stuart D. Gathman** · Jul 18 '05, 06:33 PM

Re: Help beautify ugly heuristic code

On Thu, 09 Dec 2004 00:01:36 -0800, Lonnie Princehouse wrote:
[color=blue]
> I believe you can still do this with only compiling a regex once and
> then performing a few substitutions on the hostname.[/color]

Cool idea. Convert ip matches to fixed patterns before matching a fixed
regex. The leftovers like shaw cable (which has the MAC address of the
cable modem instead of the IP) can still be handled with regex patterns.

I had an idea last night to compile 254 regexes, one for each possible
last IP byte - but I think your idea is better.

Mitja suggested a socring system reminiscent of SpamAssassin.

That gives me a few things to try.

--
Stuart D. Gathman <stuart@bmsi.co m>
Business Management Systems Inc. Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flamis acribus addictis" - background song for
a Microsoft sponsored "Where do you want to go from here?" commercial.

**JanC** · Jul 18 '05, 06:35 PM

Re: Help beautify ugly heuristic code

Stuart D. Gathman schreef:
[color=blue]
> I have a function that recognizes PTR records for dynamic IPs. There
> is no hard and fast rule for this - every ISP does it differently, and
> may change their policy at any time, and use different conventions in
> different places. Nevertheless, it is useful to apply stricter
> authentication standards to incoming email when the PTR for the IP
> indicates a dynamic IP (namely, the PTR record is ignored since it
> doesn't mean anything except to the ISP). This is because Windoze
> Zombies are the favorite platform of spammers.[/color]

Did you also think about ISPs that use such a PTR record for both dynamic
and fixed IPs?

--
JanC

"Be strict when sending and tolerant when receiving."
RFC 1958 - Architectural Principles of the Internet - section 3.9

**Stuart D. Gathman** · Jul 18 '05, 06:36 PM

Re: Help beautify ugly heuristic code

On Fri, 10 Dec 2004 22:03:20 +0000, JanC wrote:
[color=blue]
> Stuart D. Gathman schreef:
>[color=green]
>> I have a function that recognizes PTR records for dynamic IPs. There[/color][/color]
[color=blue]
> Did you also think about ISPs that use such a PTR record for both dynamic
> and fixed IPs?[/color]

There seems to be a lot of misunderstandin g about this. I am not blocking
anyones mail because they have a dynamic looking PTR. I simply don't
accept such a PTR as MTA authentication. You see, MTAs *SHOULD* provide a
fully qualified domain as their HELO name which resolves to the IP of the
MTA. Sadly, however, many internet facing MTAs don't do this, but I
accept a meaningful PTR as a substitute. I also waive the requirement for
MTA authentication if the MAIL FROM has an SPF record
(http://spf.pobox.com).

So, if your MTA complies with RFC HELO recommendations , you'll have no
trouble sending me mail. You can even use a dynamic IP with a dynamic DNS
service.

I 'do* block PTR names of "." or "localhost" . I would like to block all
single word HELO names - but there are too many clueless mail admins out
there. People seem to be unsure of what to send for HELO.

--
Stuart D. Gathman <stuart@bmsi.co m>
Business Management Systems Inc. Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flamis acribus addictis" - background song for
a Microsoft sponsored "Where do you want to go from here?" commercial.

**Stuart D. Gathman** · Jul 25 '06, 03:45 AM

Re: Help beautify ugly heuristic code

On Thu, 09 Dec 2004 00:01:36 -0800, Lonnie Princehouse wrote:

I believe you can still do this with only compiling a regex once and
then performing a few substitutions on the hostname.

That is a interesting idea. Convert ip matches to fixed patterns, and
*then* match the regex. I think I would convert hex matches to the same
pattern as decimal (and roman numeral). How would you handle zero fill?

1.2.3.4 001002003004foo .isp.com

An idea I had last night is to precompile 254 regexes - one for each of
the possible last ip bytes. However, your idea is cleaner - except, how
would it handle ip bytes that are the same: 1.2.2.2

Mitja has proposed a scoring system reminiscent of SpamAssassin.

This gives me a few things to try.

--
Stuart D. Gathman <stuart@bmsi.co m>
Business Management Systems Inc. Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flamis acribus addictis" - background song for
a Microsoft sponsored "Where do you want to go from here?" commercial.

Help beautify ugly heuristic code

Help beautify ugly heuristic code

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment