First Matching Security Group Rule
Problem Statement
Evaluate an ordered list of firewall rules against a connection and return the decision of the first matching rule (default deny).
Background
Each rule is {"action": "allow"|"deny", "proto", "port_lo", "port_hi", "cidr"}. A connection {"proto", "port", "ip"} matches a rule if the protocol equals the rule's (or the rule proto is "*"), the port is within [port_lo, port_hi], and the ip is inside the rule's CIDR. Rules are checked in order; the first match decides. If none match, the decision is "deny".
Your Task
def evaluate(rules, conn):
Return "allow" or "deny".
Input Format
- rules (ordered list of dicts), conn (dict).
Output Format
- A string "allow" or "deny".
Sample
rules = [{"action":"allow","proto":"tcp","port_lo":443,"port_hi":443,"cidr":"0.0.0.0/0"}]
print(evaluate(rules, {"proto":"tcp","port":443,"ip":"1.2.3.4"}))
Output:
allow
Example:
rules = [{"action":"allow","proto":"tcp","port_lo":443,"port_hi":443,"cidr":"0.0.0.0/0"}]
print(evaluate(rules, {"proto":"tcp","port":443,"ip":"1.2.3.4"}))allow
- Protocol Check: The connection protocol is
tcpand the rule's protocol istcp. Since they match (and the rule is not a wildcard*), the protocol condition is satisfied. - Port Range Check: The connection port is 443. The rule specifies a range from
port_lo= 443 toport_hi= 443. We verify if 443≤443≤443, which is true, so the port condition is satisfied. - CIDR Check: The connection IP is
1.2.3.4and the rule's CIDR is0.0.0.0/0. A prefix length of 0 means the subnet mask is 0.0.0.0 (all zeros). Any IP address matches a/0CIDR because the network portion is empty. Thus, the IP condition is satisfied. - Rule Decision: Since all three conditions (protocol, port, and IP) match the first rule in the list, the evaluation stops immediately. The action associated with this rule is
"allow". - The final output is
allow
Constraints:
- Proto matches if equal or the rule proto is
"*". - Port must be within
[port_lo, port_hi]; ip within the rule CIDR. - First matching rule wins; default
"deny".
1. Background Knowledge
Firewalls operate on a stateful packet inspection model where traffic is evaluated against an ordered list of rules. The critical concept here is first-match semantics: the engine scans rules sequentially and stops at the first rule whose conditions are satisfied by the packet. If no rule matches, a default policy (typically default deny) applies. This ordering is fundamental to network security; a broad "allow all" rule placed before a specific "deny" rule would render the latter unreachable.
The second key concept is CIDR (Classless Inter-Domain Routing) notation, which defines an IP range as address/prefix_length. An IP address matches a CIDR block if the first prefix_length bits of the IP match the first prefix_length bits of the block's base address. For example, 192.168.1.0/24 matches any IP from 192.168.1.0 to 192.168.1.255. In Python, the ipaddress module provides built-in functions to parse CIDR strings and test membership, which is far more reliable than manual bit manipulation.
Finally, firewall rules often support wildcards. A protocol value of "*" means the rule applies to any protocol. Similarly, a CIDR of 0.0.0.0/0 matches all IPv4 addresses. These wildcards simplify rule definitions but require careful conditional logic during evaluation.
2. Algorithm Approach
This problem follows a linear scan with early termination pattern. You iterate through the rules list in order. For each rule, you perform a conjunction of three independent checks:
- Protocol Match: Does the connection's protocol equal the rule's protocol, or is the rule's protocol "*"?
- Port Range Check: Is the connection's port within the inclusive range [port_lo, port_hi]?
- CIDR Membership: Is the connection's IP address contained within the rule's CIDR block?
If all three conditions are true, the rule matches. You immediately return the rule's action ("allow" or "deny"). If the loop completes without a match, you return the default decision, "deny".
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.