测试CIDR格式的网络是否与另一个网络重叠

10

我正在寻找一种高效的 PHP 算法,用于测试一个 CIDR 表示的网络是否与另一个网络重叠。

基本上,我的情况如下:

CIDR 地址数组:

$cidrNetworks = array(
    '192.168.10.0/24',
    '10.10.0.30/20',
    etc.
);

我有一个方法可以将网络添加到数组中,但是当添加的网络与已经存在于数组中的网络重叠时,该方法应该抛出异常。
例如,如果添加了192.168.10.0/25,就应该抛出异常。
有没有人知道或者能够想到一种有效的测试方法?
4个回答

18

这是之前在聊天中讨论的类的更新版本。它可以做你需要的事情,以及许多其他有用的功能。

<?php

    class IPv4Subnet implements ArrayAccess, Iterator {

        /*
         * Address format constants
         */
        const ADDRESS_BINARY = 0x01;
        const ADDRESS_INT = 0x02;
        const ADDRESS_DOTDEC = 0x04;
        const ADDRESS_SUBNET = 0x08;

        /*
         * Constants to control whether getHosts() returns the network/broadcast addresses
         */
        const HOSTS_WITH_NETWORK = 0x10;
        const HOSTS_WITH_BROADCAST = 0x20;
        const HOSTS_ALL = 0x30;

        /*
         * Properties to store base address and subnet mask as binary strings
         */
        protected $address;
        protected $mask;

        /*
         * Counter to track the current iteration offset
         */
        private $iteratorOffset = 0;

        /*
         * Array to hold values retrieved via ArrayAccess
         */
        private $arrayAccessObjects = array();

        /*
         * Helper methods
         */
        private function longToBinary ($long) {
            return pack('N', $long);
        }
        private function longToDottedDecimal ($long) {
            return ($long >> 24 & 0xFF).'.'.($long >> 16 & 0xFF).'.'.($long >> 8 & 0xFF).'.'.($long & 0xFF);
        }
        private function longToByteArray ($long) {
            return array(
                $long >> 24 & 0xFF,
                $long >> 16 & 0xFF,
                $long >> 8 & 0xFF,
                $long & 0xFF
            );
        }
        private function longToSubnet ($long) {
            if (!isset($this->arrayAccessObjects[$long])) {
                $this->arrayAccessObjects[$long] = new self($long);
            }
            return $this->arrayAccessObjects[$long];
        }
        private function binaryToLong ($binary) {
            return current(unpack('N', $binary));
        }
        private function binaryToDottedDecimal ($binary) {
            return implode('.', unpack('C*', $binary));
        }
        private function binaryToX ($binary, $mode) {
            if ($mode & self::ADDRESS_BINARY) {
                $result = $binary;
            } else if ($mode & self::ADDRESS_INT) {
                $result = $this->binaryToLong($binary);
            } else if ($mode & self::ADDRESS_DOTDEC) {
                $result = $this->binaryToDottedDecimal($binary);
            } else {
                $result = $this->longToSubnet($this->binaryToLong($binary));
            }
            return $result;
        }
        private function byteArrayToLong($bytes) {
            return ($bytes[0] << 24) | ($bytes[1] << 16) | ($bytes[2] << 8) | $bytes[3];
        }
        private function byteArrayToBinary($bytes) {
            return pack('C*', $bytes[0], $bytes[1], $bytes[2], $bytes[3]);
        }

        private function normaliseComparisonSubject (&$subject) {
            if (!is_object($subject)) {
                $subject = new self($subject);
            }
            if (!($subject instanceof self)) {
                throw new InvalidArgumentException('Subject must be an instance of IPv4Subnet');
            }
        }

        private function validateOctetArray (&$octets) {
            foreach ($octets as &$octet) {
                $octet = (int) $octet;
                if ($octet < 0 || $octet > 255) {
                    return FALSE;
                }
            }
            return TRUE;
        }

        /*
         * Constructor
         */
        public function __construct ($address = NULL, $mask = NULL) {
            if ($address === NULL || (is_string($address) && trim($address) === '')) {
                $address = array(0, 0, 0, 0);
            } else if (is_int($address)) {
                $address = $this->longToByteArray($address);
            } else if (is_string($address)) {
                $parts = preg_split('#\s*/\s*#', trim($address), -1, PREG_SPLIT_NO_EMPTY);
                if (count($parts) > 2) {
                    throw new InvalidArgumentException('No usable IP address supplied: Syntax error');
                } else if ($parts[0] === '') {
                    throw new InvalidArgumentException('No usable IP address supplied: IP address empty');
                }
                if (!empty($parts[1]) && !isset($mask)) {
                    $mask = $parts[1];
                }
                $address = preg_split('#\s*\.\s*#', $parts[0], -1, PREG_SPLIT_NO_EMPTY);
            } else if (is_array($address)) {
                $address = array_values($address);
            } else {
                throw new InvalidArgumentException('No usable IP address supplied: Value must be a string or an integer');
            }

            $suppliedAddressOctets = count($address);
            $address += array(0, 0, 0, 0);
            if ($suppliedAddressOctets > 4) {
                throw new InvalidArgumentException('No usable IP address supplied: IP address has more than 4 octets');
            } else if (!$this->validateOctetArray($address)) {
                throw new InvalidArgumentException('No usable IP address supplied: At least one octet value outside acceptable range 0 - 255');
            }

            if ($mask === NULL) {
                $mask = array_pad(array(), $suppliedAddressOctets, 255) + array(0, 0, 0, 0);
            } else if (is_int($mask)) {
                $mask = $this->longToByteArray($mask);
            } else if (is_string($mask)) {
                $mask = preg_split('#\s*\.\s*#', trim($mask), -1, PREG_SPLIT_NO_EMPTY);

                switch (count($mask)) {
                    case 1: // CIDR
                        $cidr = (int) $mask[0];
                        if ($cidr === 0) {
                            // Shifting 32 bits on a 32 bit system doesn't work, so treat this as a special case
                            $mask = array(0, 0, 0, 0);
                        } else if ($cidr <= 32) {
                            // This looks odd, but it's the nicest way I have found to get the 32 least significant bits set in a
                            // way that works on both 32 and 64 bit platforms
                            $base = ~((~0 << 16) << 16);
                            $mask = $this->longToByteArray($base << (32 - $cidr));
                        } else {
                            throw new InvalidArgumentException('Supplied mask invalid: CIDR outside acceptable range 0 - 32');
                        }
                        break;
                    case 4: break; // Dotted decimal
                    default: throw new InvalidArgumentException('Supplied mask invalid: Must be either a full dotted-decimal or a CIDR');
                }
            } else if (is_array($mask)) {
                $mask = array_values($mask);
            } else {
                throw new InvalidArgumentException('Supplied mask invalid: Type invalid');
            }

            if (!$this->validateOctetArray($mask)) {
                throw new InvalidArgumentException('Supplied mask invalid: At least one octet value outside acceptable range 0 - 255');
            }
            // Check bits are contiguous from left
            // TODO: Improve this mechanism
            $asciiBits = sprintf('%032b', $this->byteArrayToLong($mask));
            if (strpos(rtrim($asciiBits, '0'), '0') !== FALSE) {
                throw new InvalidArgumentException('Supplied mask invalid: Set bits are not contiguous from the most significant bit');
            }

            $this->mask = $this->byteArrayToBinary($mask);
            $this->address = $this->byteArrayToBinary($address) & $this->mask;
        }

        /*
         * ArrayAccess interface methods (read only)
         */
        public function offsetExists ($offset) {
            if ($offset === 'network' || $offset === 'broadcast') {
                return TRUE;
            }

            $offset = filter_var($offset, FILTER_VALIDATE_INT);
            if ($offset === FALSE || $offset < 0) {
                return FALSE;
            }

            return $offset < $this->getHostsCount();
        }
        public function offsetGet ($offset) {
            if (!$this->offsetExists($offset)) {
                return NULL;
            }

            if ($offset === 'network') {
                $address = $this->getNetworkAddress(self::ADDRESS_INT);
            } else if ($offset === 'broadcast') {
                $address = $this->getBroadcastAddress(self::ADDRESS_INT);
            } else {
                // How much the address needs to be adjusted by to account for network address
                $adjustment = (int) ($this->getHostsCount() > 2);
                $address = $this->binaryToLong($this->address) + $offset + $adjustment;
            }

            return $this->longToSubnet($address);
        }
        public function offsetSet ($offset, $value) {}
        public function offsetUnset ($offset) {}

        /*
         * Iterator interface methods
         */
        public function current () {
            return $this->offsetGet($this->iteratorOffset);
        }
        public function key () {
            return $this->iteratorOffset;
        }
        public function next () {
            $this->iteratorOffset++;
        }
        public function rewind () {
            $this->iteratorOffset = 0;
        }
        public function valid () {
            return $this->iteratorOffset < $this->getHostsCount();
        }

        /*
         * Data access methods
         */
        public function getHosts ($mode = self::ADDRESS_SUBNET) {
            // Parse flags and initialise vars
            $bin = (bool) ($mode & self::ADDRESS_BINARY);
            $int = (bool) ($mode & self::ADDRESS_INT);
            $dd = (bool) ($mode & self::ADDRESS_DOTDEC);
            $base = $this->binaryToLong($this->address);
            $mask = $this->binaryToLong($this->mask);
            $hasNwBc = !($mask & 0x03);
            $result = array();

            // Get network address if requested
            if (($mode & self::HOSTS_WITH_NETWORK) && $hasNwBc) {
                $result[] = $base;
            }

            // Get hosts
            for ($current = $hasNwBc ? $base + 1 : $base; ($current & $mask) === $base; $current++) {
                $result[] = $current;
            }

            // Remove broadcast address if present and not requested
            if ($hasNwBc && !($mode & self::HOSTS_WITH_BROADCAST)) {
                array_pop($result);
            }

            // Convert to the correct type
            if ($bin) {
                $result = array_map(array($this, 'longToBinary'), $result);
            } else if ($dd) {
                $result = array_map(array($this, 'longToDottedDecimal'), $result);
            } else if (!$int) {
                $result = array_map(array($this, 'longToSubnet'), $result);
            }

            return $result;
        }
        public function getHostsCount () {
            $count = $this->getBroadcastAddress(self::ADDRESS_INT) - $this->getNetworkAddress(self::ADDRESS_INT);
            return $count > 2 ? $count - 1 : $count + 1; // Adjust return value to exclude network/broadcast addresses
        }
        public function getNetworkAddress ($mode = self::ADDRESS_SUBNET) {
            return $this->binaryToX($this->address, $mode);
        }
        public function getBroadcastAddress ($mode = self::ADDRESS_SUBNET) {
            return $this->binaryToX($this->address | ~$this->mask, $mode);
        }
        public function getMask ($mode = self::ADDRESS_DOTDEC) {
            return $this->binaryToX($this->mask, $mode);
        }

        /*
         * Stringify methods
         */
        public function __toString () {
            if ($this->getHostsCount() === 1) {
                $result = $this->toDottedDecimal();
            } else {
                $result = $this->toCIDR();
            }
            return $result;
        }
        public function toDottedDecimal () {
            $result = $this->getNetworkAddress(self::ADDRESS_DOTDEC);
            if ($this->mask !== "\xFF\xFF\xFF\xFF") {
                $result .= '/'.$this->getMask(self::ADDRESS_DOTDEC);
            }
            return $result;
        }
        public function toCIDR () {
            $address = $this->getNetworkAddress(self::ADDRESS_DOTDEC);
            $cidr = strlen(trim(sprintf('%b', $this->getMask(self::ADDRESS_INT)), '0')); // TODO: Improve this mechanism
            return $address.'/'.$cidr;
        }

        /*
         * Comparison methods
         */
        public function contains ($subject) {
            $this->normaliseComparisonSubject($subject);

            $subjectAddress = $subject->getNetworkAddress(self::ADDRESS_BINARY);
            $subjectMask = $subject->getMask(self::ADDRESS_BINARY);

            return $this->mask !== $subjectMask && ($this->mask | ($this->mask ^ $subjectMask)) !== $this->mask && ($subjectAddress & $this->mask) === $this->address;
        }

        public function within ($subject) {
            $this->normaliseComparisonSubject($subject);

            $subjectAddress = $subject->getNetworkAddress(self::ADDRESS_BINARY);
            $subjectMask = $subject->getMask(self::ADDRESS_BINARY);

            return $this->mask !== $subjectMask && ($this->mask | ($this->mask ^ $subjectMask)) === $this->mask && ($this->address & $subjectMask) === $subjectAddress;
        }
        public function equalTo ($subject) {
            $this->normaliseComparisonSubject($subject);

            return $this->address === $subject->getNetworkAddress(self::ADDRESS_BINARY) && $this->mask === $subject->getMask(self::ADDRESS_BINARY);
        }
        public function intersect ($subject) {
            $this->normaliseComparisonSubject($subject);

            return $this->equalTo($subject) || $this->contains($subject) || $this->within($subject);
        }

    }

为了实现您的需求,该类提供了4种方法:
contains()
within()
equalTo()
intersect()

这些的示例用法:
// Also accepts dotted decimal mask. The mask may also be passed to the second
// argument. Any valid combination of dotted decimal, CIDR and integers will be
// accepted
$subnet = new IPv4Subnet('192.168.0.0/24');

// These methods will accept a string or another instance
var_dump($subnet->contains('192.168.0.1')); //TRUE
var_dump($subnet->contains('192.168.1.1')); //FALSE
var_dump($subnet->contains('192.168.0.0/16')); //FALSE
var_dump($subnet->within('192.168.0.0/16')); //TRUE
// ...hopefully you get the picture. intersect() returns TRUE if any of the
// other three match.

该类还实现了Iterator接口,使您能够迭代子网中的所有地址。迭代器排除网络和广播地址,这些地址可以单独检索。
示例:
$subnet = new IPv4Subnet('192.168.0.0/28');
echo "Network: ", $subnet->getNetworkAddress(),
     "; Broadcast: ", $subnet->getBroadcastAddress(),
     "\nHosts:\n";
foreach ($subnet as $host) {
    echo $host, "\n";
}

该类还实现了ArrayAccess接口,使您可以将其视为数组:
$subnet = new IPv4Subnet('192.168.0.0/28');
echo $subnet['network'], "\n"; // 192.168.0.0
echo $subnet[0], "\n"; // 192.168.0.1
// ...
echo $subnet[13], "\n"; // 192.168.0.14
echo $subnet['broadcast'], "\n"; // 192.168.0.15

注意: 迭代器/数组方法用于访问子网的主机地址将返回另一个 IPv4Subnet 对象。该类实现了 __toString() 方法,如果它表示单个地址,则返回 IP 地址作为点分十进制,否则返回 CIDR。可以通过调用相关的 get*() 方法并传递所需的标志 (请参阅类顶部定义的常量) 直接访问数据作为字符串或整数。
所有操作都是 32 位和 64 位安全的。兼容性应该是 5.2+(虽然没有彻底测试)。 查看它的工作原理

为了完整起见,我想你的使用情况将会实现类似以下方式:

public function addSubnet ($newSubnet) {
    $newSubnet = new IPv4Subnet($newSubnet);
    foreach ($this->subnets as &$existingSubnet) {
        if ($existingSubnet->contains($newSubnet)) {
            throw new Exception('Subnet already added');
        } else if ($existingSubnet->within($newSubnet)) {
            $existingSubnet = $newSubnet;
            return;
        }
    }
    $this->subnets[] = $newSubnet;
}

看它如何运作


+1 鼓励你超越职责范围 ;) 喝点咖啡后,我会尽力理解 contains 中所有位运算的奥秘。 - Leigh
只是一个小问题,您的类没有覆盖ArrayAccess的offsetUnset方法。不过很容易解决。 - Damien Overeem
@cryptic 尽快需要它 :-P 我曾经开始写过一次,但是我停下来了,因为我做出了一个决定,就是IPv6地址实际上是128位的整数,所以它们不能表示为int类型。我会找出来看一下,然后尝试完成它。 - DaveRandom
@DaveRandom,BCMath函数不是允许使用数字字符串并且据我所知没有大小限制吗? - cryptic ツ
@cryptic确实会这样,但如果可以避免耦合到不一定可用的扩展,我宁愿不这样做。虽然我不确定将IPv6地址作为int使用有多大用处,但我能想到的每种用例都可以通过位运算获取所需的信息或将其简单地存储为打包的二进制字符串(用于存储在数据库中等)。你有什么想法吗?(如果您有任何想法,可能更适合/rooms/11/php,以免让我们因在评论中进行了扩展讨论而被SO告知。) - DaveRandom
显示剩余6条评论

3

作为我们在 PHP 聊天中简要讨论的内容,以下是我将如何实现比较任意两个地址:

  1. 将 IP 地址转换为二进制形式
  2. 从 CIDR 格式中提取掩码
  3. 取两者的最小掩码(最不具体=包含更多地址)
  4. 将掩码应用于两个二进制表示。
  5. 比较这两个二进制表示。

如果有匹配,则一个地址包含在另一个地址内。

以下是一些示例代码,它并不太好看,您需要根据您的数组进行调整。

function bin_pad($num)
{
    return str_pad(decbin($num), 8, '0', STR_PAD_LEFT);
}

$ip1 = '192.168.0.0/23';
$ip2 = '192.168.1.0/24';

$regex = '~(\d+)\.(\d+)\.(\d+)\.(\d+)/(\d+)~';

preg_match($regex, $ip1, $ip1);
preg_match($regex, $ip2, $ip2);

$mask = min($ip1[5], $ip2[5]);

$ip1 = substr(
    bin_pad($ip1[1]) . bin_pad($ip1[2]) .
    bin_pad($ip1[3]) . bin_pad($ip1[4]),
    0, $mask
);

$ip2 = substr(
    bin_pad($ip2[1]) . bin_pad($ip2[2]) .
    bin_pad($ip2[3]) . bin_pad($ip2[4]),
    0, $mask
);

var_dump($ip1, $ip2, $ip1 === $ip2);

我在使其兼容32位时遇到了问题,因此最终选择将IP地址的每个八位单独转换为二进制,然后使用substr

起初我使用了pack('C4',$ip [1] .. $ip [4]),但当涉及使用完整的32位掩码时,我遇到了将其转换为二进制的问题(因为PHP整数是有符号的)。不过这是未来实现的想法!


谢谢你的回答,Leigh。Dave有点过火了,但是你的帮助一如既往地受到赞赏。+1 - Damien Overeem

0
<?php
    function checkOverlap ($net1, $net2) {

        $mask1 = explode("/", $net1)[1];
        $net1 = explode("/", $net1)[0];
        $netArr1 = explode(".",$net1);

        $mask2 = explode("/", $net2)[1];
        $net2 = explode("/", $net2)[0];
        $netArr2 = explode(".",$net2);

        $newnet1 = $newnet2 = "";

        foreach($netArr1 as $num) {
            $binnum = decbin($num);
            $length = strlen($binnum);
            for ($i = 0; $i < 8-$length; $i++) {
                $binnum = '0'.$binnum;
            }
            $newnet1 .= $binnum;
        }

        foreach($netArr2 as $num) {
            $binnum = decbin($num);
            $length = strlen($binnum);
            for ($i = 0; $i < 8-$length; $i++) {
                $binnum = '0'.$binnum;
            }
            $newnet2 .= $binnum;
        }

        $length = min($mask1, $mask2);

        $newnet1 = substr($newnet1,0,$length);
        $newnet2 = substr($newnet2,0,$length);

        $overlap = 0;
        if ($newnet1 == $newnet2) $overlap = 1;

        return $overlap;
    }

    function networksOverlap ($networks, $newnet) {

        $overlap = false;

        foreach ($networks as $network) {
            $overlap = checkOverlap($network, $newnet);
            if ($overlap) return 1;
        }

        return $overlap;        

    }

    $cidrNetworks = array(
        '192.168.10.0/24',
        '10.10.0.30/20'
    );

    $newnet = "192.168.10.0/25";

    $overlap = networksOverlap($cidrNetworks, $newnet);
?>

不确定这是否完全正确,但可以尝试一下看看是否有效。


1
有几件事情,你重复运行了几次相同的 explode 操作。你可以使用 list($mask1, $net1) 仅执行一次。看看 str_pad,那些填充循环是不必要的。三元比较返回最大值是不必要的,使用 max(虽然我确定你实际想要的是 min)。除此之外,它基本上和我的代码做的一样。 - Leigh

0

直觉上,我建议您做以下操作:

  1. 让新条目为X
  2. X转换为单个整数形式,令该整数为Y
  3. 让任何条目A的掩码长度为mask(A)
  4. 比较任何现有条目,其中mask(entry) = mask(Y)
  5. 屏蔽掉现有条目,其中mask(entry) > mask(Y)并与Y进行比较
  6. 对于每个现有条目,屏蔽掉mask(entry) < mask(X)Y,使得mask(Y) = mask(entry)并进行比较

如果没有遇到冲突,那么一切都很好。

当然,这并不检查所提出的子网是否有效。

我的正确性建议是,我想不出反例,但可能会有一个,因此我提供这个作为进一步思考的基础 - 希望这有所帮助。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接