[SOLVED] Fast way to check if a list of IP is in a list of IP-ranges (CIDR notation)

Fast way to check if a list of IP is in a list of IP-ranges (CIDR notation)

I am looking for a fast way to check if IP addresses are part of a list of CIDR notated IP ranges. I've seen examples before use netaddr like:

from netaddr import IPNetwork, IPAddress

    for CIDR in CIDRLIST:
        if IPAddress(row[0]) in IPNetwork(CIDR):
            print('success')

However this solution is way too slow for my problem (800 IP ranges in CIDR and 500.000 IP adresses).

What could be a way to do this faster? I've read about using pytries, but I am not certain this is the solution.

Solution

Patricia/Radix tree/tries seem to be the answer. I found them by searching for algorithms for looking up routing tables.

There is a python implementation here.

A little later: I now have this working fine in Ruby:

require 'rpatricia'
require 'uoainfoblox'

ib = UoAIinfoblox.new ({'user' => 'xxxxx', 'password' => 'yyyy', 'host' => 'ipam.auckland.ac.nz'})

pt = Patricia.new

ib.get_networks('*roaming_network=true').each do |net, info |
  pt.add(net)
end

puts "'130.216.66.65 #{ pt.include?('130.216.66.65')}"
puts "130.216.5.128 #{pt.include?('130.216.5.128') }"

Infoblox is an IP Management system and UoAInfoblox is a wrapper around their web api. So here I get a list of the roaming networks add them into a patricia tree and then check two IP addresses (that I know the status of).

Edit: I have just found out from a friend who uses python and who teaches networking in our CS department that he used the python radix module in his research scripts. I know he was processing very large amounts of data from a /8 darkenet for CAIDA.