# Classifying IP addresses with a decision tree

I am working on a classification problem using IP addresses as input and I am trying to find which IP addresses or subnets are likely to belong to a spammer. I have data consisting of the four octets in the IP address as well as a label: SPAM or OK.

This feels like a good problem for a decision tree, but I am finding that most decision tree algorithms consider the order of the variables interchangeable. For example, ctree from party might output a rule interpreted as

IF octet1 == 192 && octet4 == 190 THEN label => SPAM

but with IP addresses, the order of the variables matters. That is, octet 2 must be considered after octet 1, and octet 3 must be considered after octet 2 and so on to yield rules like

IF octet1 == 206 THEN label => OK

IF octet1 == 193 && octet2 == 64 && octet3 == 11 THEN label => SPAM

What type of decision tree model is this and what algorithm/tool could help here? Is there some sort of variation I can use? I prefer to stick with R.

-
You could string them together so you get if (octet1 == "206") {label <- "OK"} and if (octet123 == "193.64.11") {label <- "SPAM"} –  Henry Aug 30 '11 at 7:14

As a Postmaster I find this not only a really cool problem, but a daily problem in my work. So I have a few questions for you:

• Is your dataset comprised only of IPv4 addresses?

• Is your dataset comprised of "known" spam address blocks, or just addresses that may belong to a botnet?

• Besides using IP addresses as ordered tupples, you can use them as integers too. There have been people using PATRICIA this way

My R-Fu is very low, so I cannot help you with that :(

-
I think you can do this by just gsubing out the the decimals in the ip addresses, and converting to integers, the running rpart. –  Zach Aug 30 '11 at 13:53
Yes, only IPv4. I hand classified the IPs based on the HTTP referer associated with them (I am trying to fight referer spam). –  Ryan Rosario Aug 30 '11 at 17:34
I suppose that you want a decision tree because you can easily represent IPv4 space as such. You want something that when a lot (say > 80) of child nodes are characterized as spammers then the whole set is to be considered as a spam generator, right? Is your database static? Do you take in account that as time passes the spamability of an IP address may change due to measures taken by the network managers? Have you considered querying databases such as Spamhaus to help your decision tool? –  adamo Aug 31 '11 at 7:43

The general rule for trees is that you shouldn't expect them to do anything with an order of attributes because they cannot "see" it. Moreover the attributes should be somewhat "orthogonal" description of the objects.

Thus I think you should rather use some descriptors of IPs, like country, provider, commercial/home (plus possibly mix it with other info you have about the messages).
Or drop learning at all, do some prefix tree as adamo and Henry suggested and try to find nodes with significant spam to no-spam differences and infer something from that.

-

It sounds like you're whacking a mole with a nuclear bomb there, why not just:

1.) Sort all the IP addresses 2.) Do a sliding window over all of them where if one of them is marked spam, the ones before it get a probability associated with them, and the ones after it do as well 3.) Make the probability weights you're assigning decline with some function of distance, and maybe stop assigning when one of the octets run out.

This way, if xxx.xxx.xx.125 is between .124 and .126, and both of those are marked as spammers, but it is not, .125 should get some spam value assigned from both.

I suppose you could do a similar sliding thing at each octet level if you want spam "value" to propagate up the octet tree.

Anyway, this sounds like something that 3 or 4 sorts, and three or 4 traversals of those sorts, could probably handle.

• T
-