Classifying IP addresses with a decision tree

Question

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.

Answer 1

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 :(

Answer 2

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.

Answer 3

Admittedly two years since you asked this question..., but this article is just too perfect to not share here. Here is your answer and algorithm. Well, at least when they made it, although if you check out the authors they have personal webpages with more work in the same area.

This is how Microsoft did it or began to do it a few years back: UDMAP.

Yinglian Xie, Fang Yu, Kannan Achan, Eliot Gillum+, Moises Goldszmidt, Ted Wobber. "How Dynamic are IP Addresses?" Microsoft Research, Silicon Valley Microsoft Corporation. research.microsoft.com/pubs/63680/sigcomm07-onefile.pdf

Don't be fooled by the title of the article too much, although they do focus on that a bit - the reason behind them trying to identify dynamic IP addresses is for spammers - and they have followed up in more recent works (and built on this quite a bit, although they had some clever ideas in here) - all of this is posted on the leader authors' page.

Answer 4

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