Blocking Millions of Malicious IPs in O(32) Time with Bitwise Tries

#node #javascript #security #algorithms

If you're running an API gateway or FinTech service, blocking malicious traffic is a baseline requirement. Whether it's credential stuffing, scraping, or botnet attacks, your first line of defense is usually an IP blacklist.

Exact IP matching is easy. But attackers rarely use a single static IP. They rotate across entire subnets (CIDR blocks like 192.168.1.0/24).

If you try to match incoming requests against thousands of CIDR blocks, standard data structures break down. In this post, we’ll look at why linear arrays and Hash Maps fail at CIDR filtering, and how to build a Bitwise Trie that evaluates subnets in fixed sub-millisecond time.

The Problem: Why Hash Maps Fail at CIDR Matching

For exact IP lookup, a Hash Map gives you O(1) time complexity. You hash 192.168.1.5, look up the key, and get an immediate answer.

However, CIDR notation represents a range of IP addresses:

192.168.1.0/24 covers all 256 IPs from 192.168.1.0 to 192.168.1.255.

A Hash Map cannot perform prefix matching or range evaluation out of the box. To check if an incoming IP belongs to a blacklisted subnet using traditional methods, you either have to:

Iterate over an array of CIDR blocks (O(N) time complexity): If you have 50,000 blacklisted subnets, every single HTTP request performs up to 50,000 bitwise masking operations.
Expand subnets into individual IPs in a Hash Map (O(M) space complexity): Expanding a /16 subnet adds 65,536 entries to memory. Expanding multiple /8 subnets will crash your server process with out-of-memory errors.

The Algorithmic Fix: Bitwise Trie (Prefix Tree)

In competitive programming, Tries are commonly used for word dictionary lookups and prefix matching. Because an IPv4 address is simply a 32-bit unsigned integer, we can treat its binary representation as a string of 32 characters (0s and 1s).

A Bitwise Trie for IPv4 has two key properties:

Binary Nodes: Every node has at most two children: 0 (left) and 1 (right).
Fixed Depth: The maximum depth of the tree is strictly 32 levels (one for each bit of an IPv4 address).

How CIDR Insertion Works

Inserting a CIDR block like 192.168.1.0/24 means converting 192.168.1.0 into binary and walking down the Trie for only the first 24 bits (the network prefix). At the 24th bit node, we set isBlocked = true.

How IP Lookup Works

When an incoming request arrives with IP 192.168.1.42:

Convert the IP into a 32-bit integer.
Traverse the Trie bit-by-bit from left to right (MSB to LSB).
If at any step we hit a node marked isBlocked = true, the IP belongs to a blacklisted subnet. We stop immediately and block the request.

ext{Time Complexity: } O(W) \quad ext{where } W = 32 ext{ bits (Constant Time)}

Regardless of whether your database contains 10 subnets or 10,000,000 subnets, checking an IP takes at most 32 bit traversals.

Building the Bitwise Trie in Node.js

Here is a clean implementation of an IP Blacklist Trie:

class TrieNode {
  constructor() {
    this.children = [null, null]; // 0 for bit 0, 1 for bit 1
    this.isBlocked = false;
  }
}

class IPTrie {
  constructor() {
    this.root = new TrieNode();
  }

  // Helper: Convert IPv4 string ("192.168.1.1") to 32-bit Unsigned Integer
  ipToInt(ip) {
    return ip
      .split('.')
      .reduce((acc, octet) => ((acc << 8) + parseInt(octet, 10)) >>> 0, 0);
  }

  // Insert CIDR block (e.g., ipStr = "192.168.1.0", prefixLen = 24)
  addCIDR(ipStr, prefixLen = 32) {
    const ipNum = this.ipToInt(ipStr);
    let node = this.root;

    for (let i = 31; i >= 32 - prefixLen; i--) {
      const bit = (ipNum >>> i) & 1;

      if (!node.children[bit]) {
        node.children[bit] = new TrieNode();
      }
      node = node.children[bit];

      // Short-circuit: if a parent subnet is already blocked, stop
      if (node.isBlocked) return;
    }

    node.isBlocked = true;
  }

  // Search if an IP is blocked (Returns true/false in max 32 steps)
  isIPBlocked(ipStr) {
    const ipNum = this.ipToInt(ipStr);
    let node = this.root;

    for (let i = 31; i >= 0; i--) {
      const bit = (ipNum >>> i) & 1;

      if (!node.children[bit]) {
        return false; // Path doesn't exist -> IP is clean
      }

      node = node.children[bit];

      // Subnet match found!
      if (node.isBlocked) {
        return true;
      }
    }

    return false;
  }
}

// Example Express Middleware Usage
const ipFilter = new IPTrie();

// Blacklist a specific IP and a whole subnet
ipFilter.addCIDR("10.0.0.5", 32);       // Single IP
ipFilter.addCIDR("192.168.1.0", 24);    // 192.168.1.0 - 192.168.1.255

function ipFilterMiddleware(req, res, next) {
  const clientIP = req.ip || req.headers['x-forwarded-for'] || "127.0.0.1";

  if (ipFilter.isIPBlocked(clientIP)) {
    return res.status(403).json({
      error: "Access Denied",
      message: "Your IP or network subnet is blacklisted."
    });
  }

  next();
}

Performance Benchmark & Engineering Takeaways

Sub-Microsecond Traversal: Traversing 32 array pointers in memory executes in nanoseconds, safely outperforming database or external cache lookups.
Minimal Memory Overhead: Shared prefix nodes mean subnets inside the same range reuse existing tree nodes.
Algorithmic Elegance: Converting strings to 32-bit integers allows us to use fast bitwise shift (>>>) and bitwise AND (&) operators directly in the hot code path.

By applying competitive programming tree traversal concepts, we turn a costly linear security check into an ultra-fast constant-time guardrail for production backend services.

DEV Community