Practice/Databricks/Firewall CIDR Rules

Firewall CIDR Rules

CodingMust

Problem Statement

Design a firewall rules engine that evaluates IP addresses against CIDR block rules to determine whether traffic should be allowed or denied. The system must handle rule evaluation order, IP range matching, and extend to support entire CIDR block queries where every IP in a range must be verified.

This problem tests your understanding of bit manipulation, IP addressing, interval overlap algorithms, and how to extend a simple point-query system to handle range queries efficiently. Interviewers will probe your approach to range splitting, coverage verification, and optimization strategies.

Key Requirements

Functional

• CIDR rule matching -- evaluate firewall rules specified in CIDR notation (e.g., 192.168.1.0/24)
• First-match wins -- process rules in order and return the action of the first matching rule
• Default deny -- if no rule matches, return DENY by default
• Single IP check -- determine if a specific IP address is allowed or denied
• CIDR block check -- verify if an entire CIDR range is allowed (all IPs in the range must be allowed)
• Rule actions -- support ALLOW and DENY actions

Non-Functional

• Low latency -- single IP lookups should complete in microseconds
• Efficient range queries -- CIDR block verification should avoid checking every IP individually
• Scalability -- handle firewall configurations with hundreds or thousands of rules
• Correctness -- accurately handle overlapping rules, rule ordering, and edge cases
• Bit manipulation efficiency -- leverage binary operations for IP and CIDR calculations

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. IP Address and CIDR Representation (Foundation)

Interviewers want to see you understand IP addresses at the binary level and how CIDR notation works.

Hints to consider:

• IP address to 32-bit integer conversion: (a << 24) | (b << 16) | (c << 8) | d
• CIDR notation /24 means first 24 bits are network prefix, last 8 bits are host portion
• Network mask calculation: mask = (0xFFFFFFFF << (32 - prefix_length)) & 0xFFFFFFFF
• Range start (network address): base_ip & mask
• Range end (broadcast address): network_address | (~mask & 0xFFFFFFFF)
• Example: 192.168.1.0/24 represents 256 IPs from 192.168.1.0 to 192.168.1.255

2. Single IP Matching Algorithm

How to efficiently check if an IP matches any rule in the firewall configuration.

Hints to consider:

• Iterate through rules in order (first match wins, so order is critical)
• For each rule, convert CIDR to [start, end] integer range
• Check if start <= ip_int <= end
• Return the action of the first matching rule
• If no rule matches, return default DENY
• Time complexity: O(n) where n is number of rules -- acceptable for hundreds of rules

3. CIDR Block Query: Coverage Verification

The key challenge is verifying that every IP in a query CIDR range is allowed without checking each IP individually.

Hints to consider:

• Convert query CIDR to [query_start, query_end] range
• Split the query range into segments based on rule boundaries
• For each segment, find the first matching rule
• If any segment is DENIED or uncovered, return DENY
• Only return ALLOW if all segments are covered by ALLOW rules
• Use interval sweep algorithm with event boundaries for efficiency

4. Range Segmentation and Sweep Algorithm

How to decompose the query range into segments where each segment has a consistent rule match.

Hints to consider:

• Collect all boundary points: query start, query end, and overlapping rule boundaries
• Sort boundaries to get segment breakpoints
• For each segment between consecutive boundaries, determine the first matching rule
• If first match is DENY or no match exists, entire query is DENIED
• Example: query 192.168.1.0/24 with rules covering .0-.127 (DENY) and .128-.255 (ALLOW) → split into two segments, first is DENIED, so overall DENY

5. Optimization Strategies for Large Rule Sets

When rule count grows to thousands, linear scan becomes too slow.

Hints to consider:

• Interval tree data structure: build once, query in O(log n + k) where k is overlapping rules
• Prefix trie for CIDR matching: leverage hierarchical structure of IP addresses
• Pre-compute rule ranges and sort by start address for binary search
• Cache query results for frequently checked IPs or ranges
• Trade-off between pre-processing time and query time

Suggested Approach

Step 1: Clarify Requirements and Scope

Ask whether the focus is on single IP checks or CIDR block queries, how many rules the system needs to support, whether rules are static or dynamically updated, and if optimization beyond O(n) is expected. Confirm the default action when no rule matches.