How to check if IP is in one of these subnets

Question

I have ~12600 subnets:

eg. 123.123.208.0/20

and an IP.

I can use a SQLite Database or an array or whatever

There was a similar question asked about a month ago, however I am not looking for checking one IP against one subnet but a bunch of subnets (obviously the most efficient way, hopefully not O(total subnets)) :)

How can I check that the IP is one of in one of these subnets, I need true or false not the subnet if that helps optimisation.

There are similar subnets in the current list eg.: (actual extract)

123.123.48.0/22 <-- not a typo
123.123.48.0/24 <-- not a typo
123.123.90.0/24
123.123.91.0/24
123.123.217.0/24

In total they range from 4.x.y.z to 222.x.y.z

Decrial

Answer 1

The best approach is IMO making use of bitwise operators. For example, 123.123.48.0/22 represents (123<<24)+(123<<16)+(48<<8)+0 (=2071670784; this might be a negative number) as a 32 bit numeric IP address, and -1<<(32-22) = -1024 as a mask. With this, and likewise, your test IP address converted to a number, you can do:

(inputIP & testMask) == testIP

For example, 123.123.49.123 is in that range, as 2071671163 & -1024 is 2071670784

So, here are some tool functions:

function IPnumber(IPaddress) {
    var ip = IPaddress.match(/^(\d+)\.(\d+)\.(\d+)\.(\d+)$/);
    if(ip) {
        return (+ip[1]<<24) + (+ip[2]<<16) + (+ip[3]<<8) + (+ip[4]);
    }
    // else ... ?
    return null;
}

function IPmask(maskSize) {
    return -1<<(32-maskSize)
}

test:

(IPnumber('123.123.49.123') & IPmask('22')) == IPnumber('123.123.48.0')

yields true.

In case your mask is in the format '255.255.252.0', then you can use the IPnumber function for the mask, too.

Pander

I like your use of the bitwise operators, but does JavaScript guarantee your indian encoding? I broke out the ip range into low and high to allow for O(logN) behaviour when the columns are indexed as opposed to O(N) using this approach. But it may depend on sqlite's implementation. Not sure. – Gragg

"guarantee endian encoding"? I don't see why it has to. It's just numbers. Anyway, you can indeed find both lower and upper bound of the range with IP&mask and with IP|~mask (~-1024==1023) respectively, so you can use BETWEEN to search for matches for the range. – Pander

@Pander I have only input IP and mask, I want to check that input IP lies in the mask range or not ( mask in format 255.255.252.0 ) How to check that ? – Butterworth

One bug: if your subnet is not defined correctly with right side 0's, this will fail. To make bad definitions work, use (IPnumber('123.123.49.123') & IPmask('22')) == (IPnumber('123.123.48.1') & IPmask('22')) – Sardonyx

Answer 2

Try this:

var ip2long = function(ip){
    var components;

    if(components = ip.match(/^(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})$/))
    {
        var iplong = 0;
        var power  = 1;
        for(var i=4; i>=1; i-=1)
        {
            iplong += power * parseInt(components[i]);
            power  *= 256;
        }
        return iplong;
    }
    else return -1;
};

var inSubNet = function(ip, subnet)
{   
    var mask, base_ip, long_ip = ip2long(ip);
    if( (mask = subnet.match(/^(.*?)\/(\d{1,2})$/)) && ((base_ip=ip2long(mask[1])) >= 0) )
    {
        var freedom = Math.pow(2, 32 - parseInt(mask[2]));
        return (long_ip > base_ip) && (long_ip < base_ip + freedom - 1);
    }
    else return false;
};

Usage:

inSubNet('192.30.252.63', '192.30.252.0/22') => true
inSubNet('192.31.252.63', '192.30.252.0/22') => false

Barrus

But your code doesn't include the first and the last IP. I added one more checking and now it does return (long_ip > base_ip || long_ip === base_ip) && ((long_ip < base_ip + freedom - 1) || (long_ip === base_ip + freedom - 1)); – Hatpin

Answer 3

I managed to solve this by using the node netmask module. You can check if an IP belongs to a subnet by making something like this:

import { Netmask } from 'netmask'

const block = new Netmask('123.123.208.0/20')
const ip = '123.123.208.0'
console.log(block.contains(ip))

Will here print true.

You can install it by using:

npm i --save netmask

Quantic

Answer 4

Convert the lower ip and the upper ip in the range to integers and store the range in the db then make sure both columns are indexed.

Off the top of my head (pseudo code):

function ipmap(w,x,y,z) {
  return 16777216*w + 65536*x + 256*y + z;
}

var masks = array[ipmap(128,0,0,0), ipmap(196,0,0,0), ..., ipmap(255,255,255,255)]

function lowrange(w, x, y, z, rangelength) {
  return ipmap(w, x, y, z) & masks[rangelength]
}

function hirange(w, x, y, z, rangelength) {
  return lowrange(w, x, y, z, ,rangelength) + ipmap(255,255,255,255) - masks[rangelength];
}

That ought to do it.

To find whether a particular ip falls in any of the ranges, convert it to an integer and do:

SELECT COUNT(*) FROM ipranges WHERE lowrange <= 1234567 AND 1234567 <= highrange

The query optimizer should be able to speed this up greatly.

Gragg

Thanks for your reply, how can I convert a subnet into a range using JavaScript? Also what about: 123.123.48.0/22 123.123.48.0/24 They overlap. – Decrial

The start and end ips of the range will differ. so the overlap shouldn't be a problem. – Gragg

Isn't: 123.123.48.0/22: 123.123.48.1 - 123.123.51.254 & 123.123.48.0/24: 123.123.48.1 - 123.123.48.254 – Decrial

And the ends differ, so what's the problem? – Gragg

Wouldn't a better solution remove the redundant /24? I guess I could always just take the lowest /x and remove all the higher subnets. – Decrial

sure, but that's not part of your question. The fact that they overlap is irrelevant, it'll just be slower. – Gragg

Answer 5

Functions IPnumber and IPmask are nice, however I would rather test like:

(IPnumber('123.123.49.123') & IPmask('22')) == (IPnumber('123.123.48.0')  & IPmask('22'))

Because for each address, you only need to take into account the network part of the address. Hence doing IPmask('22') will zero-out the computer part of the address and you should do the same with the network address.

Fredkin

Answer 6

Keywords: Binary searching, preprocessing, sorting

I had a similar problem and binary search appears to be very efficient if you can pre-process your subnet list and sort it. Then you can achieve an asymptotic time complexity of O(log n).

Here's my code (MIT License, original location: https://github.com/iBug/pac/blob/854289a674578d096f60241804f5893a3fa17523/code.js):

function belongsToSubnet(host, list) {
  var ip = host.split(".").map(Number);
  ip = 0x1000000 * ip[0] + 0x10000 * ip[1] + 0x100 * ip[2] + ip[3];

  if (ip < list[0][0])
    return false;

  // Binary search
  var x = 0, y = list.length, middle;
  while (y - x > 1) {
    middle = Math.floor((x + y) / 2);
    if (list[middle][0] < ip)
      x = middle;
    else
      y = middle;
  }

  // Match
  var masked = ip & list[x][1];
  return (masked ^ list[x][0]) == 0;
}

And an example usage:

function isLan(host) {
  return belongsToSubnet(host, LAN);
}

var LAN = [
  [0x0A000000, 0xFF000000], // 10.0.0.0/8
  [0x64400000, 0xFFC00000], // 100.64.0.0/10
  [0x7F000000, 0xFF000000], // 127.0.0.0/8
  [0xA9FE0000, 0xFFFF0000], // 169.254.0.0/16
  [0xAC100000, 0xFFF00000], // 172.16.0.0/12
  [0xC0A80000, 0xFFFF0000]  // 192.168.0.0/16
];

isLan("127.12.34.56"); // => true
isLan("8.8.8.8"); // => false (Google's Public DNS)

You can get a PAC script* and see how it performs (it loads a China IP list from somewhere else, sorts them and formats them appropriately) against 5000s of subnets. In practice its speed is surprisingly satisfactory.

The preprocessing code can be inspected using F12 Dev Tools on the above page. In short, you need to convert 1.2.3.4/16 to [0x01020304, 0xFFFF0000], i.e. 32-bit unsigned integer for the IP address and network mask.

^{* Link goes to my personal website.}

Browning

Your binary search misses the edge case where the list size is 1. Simply updating the loop to use do { } while syntax fixes this. – Podium

@Podium I don't think so. When the list size is 1 it skips the loop with x=0 and continues to apply subnet mask before checking equality. The binary search is intended to find the element x where list[x] <= ip < list[x+1], so the only edge case is when ip < list[0] which has been handled earlier. – Browning

You are correct. I missed the preliminary check. In my implementation I also added a check for an empty input list. – Podium

Answer 7

Simple match without doing math or external libs:

import { BlockList, isIp, isIPv4 } from "net";

function isIpWhitelisted(clientIp: string, allowedCidrs: string[]): boolean {
  if (!isIP(clientIp)) {
    return false;
  }
  if (!allowedCidrs.length) {
    return true;
  }

  const whitelist = allowedCidrs.reduce(addToWhitelist, new BlockList());
  return whitelist.check(clientIp);
}

function addToWhitelist(whitelist: BlockList, cidr: string): BlockList {
  const subnets = cidr.split("/");
  if (subnets.length === 1) {
    whitelist.addAddress(subnets[0]);
  }
  if (subnets.length === 2) {
    whitelist.addSubnet(subnets[0], parseInt(subnets[1], 10), isIPv4(subnets[0]) ? "ipv4" : "ipv6");
  }
  return whitelist;
}

Usage:

isIpWhitelisted("192.168.0.1", ["192.168.0.0/24", "10.0.0.0/8"]) === true
isIpWhitelisted("192.168.0.1", ["10.0.0.0/8"]) === false

Sorcim