Firewalls and packet filtering in Computer Networks - Time & Space Complexity

Time Complexity: Firewalls and packet filtering

O(n)

Understanding Time Complexity

When using firewalls to filter network packets, it's important to understand how the time to check each packet grows as more rules are added.

We want to know how the filtering process scales with the number of rules.

Scenario Under Consideration

Analyze the time complexity of the following packet filtering process.

for each incoming_packet in network_stream:
    for each rule in firewall_rules:
        if rule matches incoming_packet:
            apply rule action
            break
    if no rule matched:
        apply default action
    

This code checks each incoming packet against firewall rules one by one until a match is found or all rules are checked.

Identify Repeating Operations

• Primary operation: Checking each packet against firewall rules in a loop.
• How many times: For each packet, the rules are checked one by one until a match is found or all rules are checked.

How Execution Grows With Input

As the number of firewall rules increases, the time to check each packet grows roughly in proportion to the number of rules.

Input Size (number of rules)	Approx. Operations per packet
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows linearly with the number of rules.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter each packet grows directly with the number of firewall rules.

Common Mistake

[X] Wrong: "Filtering time stays the same no matter how many rules there are."

[OK] Correct: Each packet must be checked against rules until a match is found, so more rules usually mean more checks and longer filtering time.

Interview Connect

Understanding how firewall filtering scales helps you explain real-world network security performance and design efficient rule sets.

Self-Check

"What if the firewall used a data structure like a hash table to find matching rules instead of checking them one by one? How would the time complexity change?"

Practice

1. What is the primary function of a firewall in a computer network?

easy

A. To allow or block data packets based on security rules

B. To increase the speed of data transmission

C. To store data packets temporarily

D. To convert data packets into different formats

Solution

1. Step 1: Understand the role of a firewall

   A firewall controls network access by filtering data packets according to security rules.

2. Step 2: Identify the correct function

   It does not speed up transmission, store packets, or convert formats; it only allows or blocks packets.

3. Final Answer:

   To allow or block data packets based on security rules -> Option A

4. Quick Check:

   Firewall function = Allow/block packets [OK]

Hint: Firewalls control access by blocking or allowing packets [OK]

Common Mistakes:

• Thinking firewalls speed up network traffic
• Confusing firewalls with data storage devices
• Believing firewalls change packet formats

2. Which of the following is a correct example of a packet filtering rule?

easy

A. Store packets for later analysis

B. Block packets based on their payload content

C. Convert packets from TCP to UDP

D. Allow packets from IP 192.168.1.10 to port 80

Solution

1. Step 1: Understand packet filtering rules

   Packet filtering rules specify conditions like source IP and destination port to allow or block packets.

2. Step 2: Identify the valid rule

   Allowing packets from a specific IP to a specific port is a valid rule; converting or storing packets is not filtering.

3. Final Answer:

   Allow packets from IP 192.168.1.10 to port 80 -> Option D

4. Quick Check:

   Packet filtering = Allow/block by IP and port [OK]

Hint: Packet filtering rules specify IP and port conditions [OK]

Common Mistakes:

• Confusing filtering with packet conversion
• Thinking filtering stores packets
• Believing all packets are always blocked

3. Consider a firewall rule: Block packets from IP 10.0.0.5 to port 22. What will happen if a packet from IP 10.0.0.5 tries to connect to port 22?

medium

A. The packet will be redirected to another port

B. The packet will be allowed through the firewall

C. The packet will be blocked by the firewall

D. The packet will be logged but allowed

Solution

1. Step 1: Analyze the firewall rule

   The rule explicitly blocks packets from IP 10.0.0.5 to port 22.

2. Step 2: Determine the packet's fate

   Since the packet matches the block rule, it will be stopped and not allowed through.

3. Final Answer:

   The packet will be blocked by the firewall -> Option C

4. Quick Check:

   Block rule matched = Packet blocked [OK]

Hint: Block rules stop matching packets from passing [OK]

Common Mistakes:

• Assuming packets are redirected instead of blocked
• Thinking packets are logged but allowed by default
• Confusing allow and block rules

4. A firewall rule is written as: Allow packets to port 443 from any IP. However, packets from IP 192.168.1.20 to port 443 are still blocked. What is the most likely error?

medium

A. There is a conflicting block rule with higher priority

B. The firewall does not filter packets by port

C. Port 443 is not used for secure connections

D. The rule is missing a source IP specification

Solution

1. Step 1: Review the allow rule

   The rule allows packets to port 443 from any IP, so it should permit packets from 192.168.1.20.

2. Step 2: Identify possible conflicts

   If packets are blocked despite the allow rule, a block rule with higher priority likely overrides it.

3. Final Answer:

   There is a conflicting block rule with higher priority -> Option A

4. Quick Check:

   Conflicting rules = Block overrides allow [OK]

Hint: Check for higher priority block rules when allow fails [OK]

Common Mistakes:

• Believing port 443 is not for secure connections
• Ignoring rule priority order
• Assuming firewall ignores ports

5. You want to create a firewall rule that allows HTTP traffic (port 80) only from the IP range 192.168.1.0 to 192.168.1.255 and blocks all other HTTP traffic. Which approach correctly applies packet filtering to achieve this?

hard

A. Block packets from 192.168.1.0/24 to port 80; then allow all packets to port 80

B. Allow packets from 192.168.1.0/24 to port 80; then block all packets to port 80

C. Allow all packets to port 80 without IP restrictions

D. Block all packets to port 80 without exceptions

Solution

1. Step 1: Define the allow rule for the IP range

   Allow packets from IP range 192.168.1.0/24 (which covers 192.168.1.0 to 192.168.1.255) to port 80.

2. Step 2: Define the block rule for all other HTTP traffic

   Block all other packets to port 80 that do not match the allow rule.

3. Final Answer:

   Allow packets from 192.168.1.0/24 to port 80; then block all packets to port 80 -> Option B

4. Quick Check:

   Allow specific IP range, then block others = Correct filtering [OK]

Hint: Allow specific IP range first, then block others [OK]

Common Mistakes:

• Blocking allowed IP range by mistake
• Allowing all traffic without restrictions
• Reversing allow and block order