First-Match CIDR Firewall: Status of an IP Address or a Whole CIDR Block

A firewall is configured with an ordered list of rules. Each rule pairs an IPv4 pattern with an action, for example:

rules = [("192.168.1.0/24", "ALLOW"), ("8.8.8.8", "DENY")]

A pattern is either a CIDR block a.b.c.d/p, which covers every address whose first p bits equal the first p bits of a.b.c.d, or a bare address, which is treated as /32. The list is ordered, so the status of an address is the action of the first rule that covers it.

Write get_status(rules, target). In the base question the target is a single address: get_status(rules, "192.168.1.5") returns "ALLOW", because its first 24 bits (192.168.1) match the first rule. The follow-up asks what happens, once the rules are in place, when the target is itself a CIDR block. A block stands for many addresses, and it counts as allowed only if every address in it is allowed. Your function must handle both kinds of target.

Function Signature

def get_status(rules: list[tuple[str, str]], target: str) -> str:

Rules

• Read each address as a 32-bit number with the first octet most significant. An address matches the pattern n/p when its first p bits equal the first p bits of n. /0 matches every address. Bits of n after the first p are ignored.
• The status of a single address is the action of the lowest-index rule it matches.
• Assumption (not stated in the report): an address that matches no rule has status "DENY".
• target is either a bare address (a block of exactly one address) or a CIDR block a.b.c.d/q covering every address whose first q bits equal those of a.b.c.d.
• Return "ALLOW" if every address in the target block has status "ALLOW"; otherwise return "DENY". For a bare address this is simply that address's status.

Constraints

• 1 <= len(rules) <= 10^5
• Every prefix length, in a rule or in target, is an integer from 0 to 32; a pattern without / means /32.
• Every address is four decimal octets from 0 to 255, separated by dots, with no leading zeros or whitespace.
• Every action is exactly "ALLOW" or "DENY".
• A target block can contain up to 2^32 (4,294,967,296) addresses, which exceeds 2^31 - 1.
• The output is exactly "ALLOW" or "DENY".

Examples

Example 1

rules = [("192.168.1.0/24", "ALLOW"), ("8.8.8.8", "DENY")]
target = "192.168.1.5"
Output: "ALLOW"

The first 24 bits of 192.168.1.5 match rule 0. With the same rules, "8.8.8.8" would return "DENY" (rule 1), and "10.0.0.1" would return "DENY" because no rule matches it.

Example 2

rules = [("10.0.0.7", "DENY"), ("10.0.0.0/24", "ALLOW")]
target = "10.0.0.0/28"
Output: "DENY"

The block covers 10.0.0.0 through 10.0.0.15. Address 10.0.0.7 matches the DENY rule first, so the block is not entirely allowed. The target "10.0.0.16/28" would return "ALLOW".

Example 3

rules = [("10.0.0.0/25", "ALLOW"), ("10.0.0.128/25", "ALLOW")]
target = "10.0.0.0/24"
Output: "ALLOW"

No single rule covers the whole block, but each of its halves, 10.0.0.0 through 10.0.0.127 and 10.0.0.128 through 10.0.0.255, is covered by an ALLOW rule.