logo标签列表

如何检查IP是否在这些子网中之一

javascriptsqlsqliteperformancesubnet
22

我有大约12600个子网：

例如：123.123.208.0/20

还有一个IP地址。

我可以使用SQLite数据库或数组或其他任何东西。

一个月前有类似的问题，但我不是要检查一个IP地址是否在一个子网中，而是要检查一堆子网（显然是最有效的方式，希望不是O（总子网数））:)

如何检查IP地址是否在这些子网中之一，我需要true或false，而不是子网，如果这有助于优化。

当前列表中有类似的子网，例如： （实际提取）

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

它们的范围从4.x.y.z到222.x.y.z。

6个回答
29

在我看来，最好的方法是利用位运算符。例如，123.123.48.0/22表示为32位数的IP地址，计算公式为(123<<24)+(123<<16)+(48<<8)+0（=2071670784；这可能是一个负数），掩码为-1<<(32-22) = -1024。有了这个以及同样将您的测试IP地址转换为数字，您可以进行以下操作：

(inputIP & testMask) == testIP
例如，123.123.49.123在这个范围内，因为2071671163和-1024的按位与结果是2071670784。
所以，以下是一些工具函数：
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)
}

测试：

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

返回 true。

如果您的掩码格式为“255.255.252.0”，则您也可以对掩码使用IPnumber函数。

我喜欢你使用位运算符的方式，但JavaScript是否保证了你的印地安编码？我将IP范围分为低和高，以便在列被索引时实现O(logN)的行为，而不是使用这种方法的O(N)。但这可能取决于SQLite的实现。不确定。 - Allain Lalonde
“保证字节序编码”？我不明白为什么需要这样做。这只是数字而已。无论如何，您确实可以使用IP＆mask和IP |〜mask（〜-1024 == 1023）找到范围的上限和下限，因此您可以使用BETWEEN搜索范围内的匹配项。 - bart
@bart 我只输入了IP和掩码，我想检查输入的IP是否在掩码范围内（掩码格式为255.255.252.0）。如何检查呢？ - Sagar
3
一个 Bug：如果你的子网掩码没有正确定义，尾数是 0 的位数不够，则会导致失败。为了使错误的定义能够工作，请使用 (IPnumber('123.123.49.123') & IPmask('22')) == (IPnumber('123.123.48.1') & IPmask('22'))。 - Turbo
11

试试这个：

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;
};

用法：

inSubNet('192.30.252.63', '192.30.252.0/22') => true
inSubNet('192.31.252.63', '192.30.252.0/22') => false
3
但是你的代码没有包括第一个和最后一个 IP。 我增加了一个检查，现在它包括了。 return (long_ip > base_ip || long_ip === base_ip) && ((long_ip < base_ip + freedom - 1) || (long_ip === base_ip + freedom - 1)); - through.a.haze
6

我使用 node netmask 模块解决了这个问题。您可以通过类似以下代码来检查一个IP是否属于一个子网：

import { Netmask } from 'netmask'

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

这里将打印true。

您可以使用以下方式进行安装:

npm i --save netmask
3
将范围内的较小IP和较大IP转换为整数，并存储范围到数据库中，确保两列都被索引。以下是伪代码：
``` 将较小IP和较大IP转换为整数 将范围存储到数据库中 为两列创建索引 ```
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];
}

这应该可以了。
要查找特定IP是否属于任何一个范围，请将其转换为整数并执行以下操作：
SELECT COUNT(*) FROM ipranges WHERE lowrange <= 1234567 AND 1234567 <= highrange

查询优化器应该能够大幅提高此操作的速度。
谢谢您的回复，我该如何使用JavaScript将子网转换为范围？还有： 123.123.48.0/22 123.123.48.0/24它们重叠了。 - Steve
范围的起始和结束IP将不同，因此重叠不应该是一个问题。 - Allain Lalonde
不是：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 - Steve
两端不同，那有什么问题呢？ - Allain Lalonde
难道不该有更好的解决方案来移除多余的/24吗？我猜我总可以选择最低的/x并删除所有高于它的子网。 - Steve
当然可以，但这并不是你的问题的一部分。它们重叠的事实是无关紧要的，只会使速度变慢。 - Allain Lalonde
2

虽然IPnumber和IPmask函数很好，但我更喜欢像这样进行测试:

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

因为对于每个地址，您只需要考虑地址的网络部分。因此，执行IPmask('22')将清除地址的计算机部分，您应该对网络地址执行相同的操作。

1

关键词: 二分搜索，预处理，排序

我有一个类似的问题，如果你能预处理子网列表并对其进行排序，则二分搜索非常有效。然后，您可以实现O(log n)的渐近时间复杂度。

这是我的代码（MIT许可证，原始位置: 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;
}

并且一个使用示例：

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)

你可以获取一个PAC脚本*并查看其性能（它从其他地方加载中国IP列表，对其进行排序并适当格式化），以针对5000个子网进行测试。实际上，它的速度令人惊讶地令人满意。
可以使用上述页面上的F12 Dev工具检查预处理代码。简而言之，您需要将1.2.3.4/16转换为[0x01020304, 0xFFFF0000]，即IP地址和网络掩码的32位无符号整数。 *链接指向我的个人网站。
你的二分查找漏掉了列表大小为1的边缘情况。只需更新循环以使用“do { } while”语法即可解决此问题。 - this-sam
@this-sam 我不这么认为。当列表大小为1时，它会跳过x=0的循环，并在检查相等性之前继续应用子网掩码。二分搜索旨在找到元素x，其中list[x] <= ip < list[x+1]，因此唯一的边缘情况是当ip < list[0]时，这已经在之前处理过了。 - iBug
你是正确的。我错过了初步检查。在我的实现中，我还添加了一个检查空输入列表的检查。 - this-sam
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接