IP lookup in CIDR blocks

(image taken from the cidranger site)

 

Lately we've had a new requirement in our system: whitelist IPs.

This means that whenever a new client request arrives to our service, our system should first look fo the client IP in a predefined list of IPs, and in case the IP exists, the system should allow it to pass without any validations.

This sounded quite simple, until I've realized that the whitelist IPs is not a list of IPs, but a list of CIDRs, for example: 

1.2.3.0/24

While I could create a new code to scan the whitelist, and check inclusion within any subnet, it would had been very inefficient, especially considering the whitelist is ~1K long.

The solution for this is to represent the entire whitelist as a Trie, and then simply look for the IP in the trie.

Building the Trie is O(N) where N is the length of the whitelist, while searching the IP in the entire whitelist Trie, is O(number of bits in a IP) ~= O(1).

Luckily, I am not the first one who needed this, and I've found the cidranger GO library.

The following is an example of building the Trie:

cidrs := []string{"1.2.3.0/24", "1.1.1.1", "1.1.1.2/32"}

ranger := cidranger.NewPCTrieRanger()
for _, cidr := range cidrs {
   if !strings.Contains(cidr, "/") {
      if strings.Contains(cidr, ":") {
         cidr += "/128"
      } else {
         cidr += "/32"
      }
   }

   _, parsedCidr, err := net.ParseCIDR(cidr)
   if err != nil {
      panic(err)
   }

   err = ranger.Insert(cidranger.NewBasicRangerEntry(*parsedCidr))
   if err != nil {
      panic(err)
   }
}

To lookup in IP, use the following code:

parsedIp := net.ParseIP("1.2.3.7")
included, err := ranger.Contains(parsedIp)
if err != nil {
   panic(err)
}

fmt.Printf("IP included: %v",included)

It worth mentioning the library supports both IPv4 and IPv6.