Stateless behavior of NACLs in AWS - Time & Space Complexity

Time Complexity: Stateless behavior of NACLs

O(n)

Understanding Time Complexity

We want to understand how the number of checks grows when network traffic passes through Network ACLs (NACLs).

Specifically, how many rule evaluations happen as more packets flow through.

Scenario Under Consideration

Analyze the time complexity of NACL rule evaluations for incoming and outgoing packets.

// Example NACL rules evaluation for each packet
for each packet in network_traffic:
  check inbound rules for packet
  if allowed:
    forward packet
  check outbound rules for response packet
  if allowed:
    forward response

This sequence shows how NACLs check rules for both incoming and outgoing packets separately because they are stateless.

Identify Repeating Operations

Each packet causes these repeated operations:

• Primary operation: Rule checks on inbound and outbound traffic.
• How many times: Twice per packet (once inbound, once outbound).

How Execution Grows With Input

As the number of packets increases, the number of rule checks grows proportionally.

Input Size (n packets)	Approx. Rule Checks
10	20
100	200
1000	2000

Pattern observation: The total checks double the number of packets because each packet is checked twice.

Final Time Complexity

Time Complexity: O(n)

This means the number of rule checks grows directly in proportion to the number of packets passing through.

Common Mistake

[X] Wrong: "NACLs only check rules once per connection, so rule checks stay constant regardless of traffic."

[OK] Correct: NACLs are stateless, so they check every packet separately, causing rule checks to grow with traffic volume.

Interview Connect

Understanding how stateless checks scale helps you explain network security behavior clearly and confidently in real-world cloud roles.

Self-Check

"What if NACLs were stateful and tracked connections? How would the time complexity of rule checks change?"

Practice

1. What does it mean that Network ACLs (NACLs) are stateless in AWS?

easy

A. NACLs remember the state of connections to allow return traffic automatically

B. Each packet is checked independently without remembering previous packets

C. NACLs only filter traffic based on IP addresses, not ports

D. NACLs automatically block all inbound traffic by default

Solution

1. Step 1: Understand the meaning of stateless

   Stateless means the system does not keep track of previous packets or connection states.

2. Step 2: Apply this to NACLs

   NACLs evaluate each packet on its own, without remembering if it is part of an existing connection.

3. Final Answer:

   Each packet is checked independently without remembering previous packets -> Option B

4. Quick Check:

   Stateless means no memory of past packets = A [OK]

Hint: Stateless means no memory of past packets, check each separately [OK]

Common Mistakes:

• Thinking NACLs remember connection states like security groups
• Assuming NACLs allow return traffic automatically
• Confusing stateless with blocking all traffic by default

2. Which of the following is the correct way to allow inbound HTTP traffic on port 80 using a NACL rule?

easy

A. Allow inbound traffic on port 80 with rule number 100, protocol TCP, action ALLOW

B. Allow inbound traffic on port 22 with rule number 100, protocol TCP, action ALLOW

C. Allow outbound traffic on port 80 with rule number 100, protocol TCP, action DENY

D. Allow inbound traffic on port 443 with rule number 100, protocol UDP, action ALLOW

Solution

1. Step 1: Identify the correct port and protocol for HTTP

   HTTP uses TCP protocol on port 80.

2. Step 2: Confirm the rule direction and action

   To allow inbound HTTP traffic, the rule must be inbound with action ALLOW.

3. Final Answer:

   Allow inbound traffic on port 80 with rule number 100, protocol TCP, action ALLOW -> Option A

4. Quick Check:

   Inbound TCP port 80 ALLOW = D [OK]

Hint: HTTP uses TCP port 80 inbound ALLOW rule [OK]

Common Mistakes:

• Using wrong port number or protocol
• Setting rule direction incorrectly
• Using DENY action instead of ALLOW

3. Consider a NACL with the following rules:
Inbound Rule 100: ALLOW TCP port 80
Outbound Rule 100: DENY all traffic
What will happen when an instance in the subnet tries to send a response to an HTTP request?

medium

A. The response will be allowed because inbound is allowed

B. The response will be allowed because NACLs are stateful

C. The response will be blocked because outbound is denied

D. The response will be blocked because inbound denies it

Solution

1. Step 1: Analyze inbound rule

   Inbound HTTP traffic on port 80 is allowed, so requests can reach the instance.

2. Step 2: Analyze outbound rule

   Outbound rule denies all traffic, so responses from the instance are blocked.

3. Final Answer:

   The response will be blocked because outbound is denied -> Option C

4. Quick Check:

   Outbound DENY blocks response despite inbound ALLOW = B [OK]

Hint: Both inbound and outbound must allow traffic for two-way flow [OK]

Common Mistakes:

• Assuming NACLs are stateful and allow return traffic automatically
• Ignoring outbound rules when troubleshooting
• Confusing inbound and outbound directions

4. You configured a NACL to allow inbound SSH (port 22) and outbound HTTP (port 80) traffic. However, SSH connections fail. What is the most likely cause?

medium

A. Outbound SSH traffic is not allowed in the NACL

B. Inbound HTTP traffic is not allowed in the NACL

C. NACLs are stateful and do not require outbound rules

D. Security groups block SSH traffic

Solution

1. Step 1: Review NACL rules for SSH

   Inbound SSH (port 22) is allowed, but outbound SSH must also be allowed for return traffic.

2. Step 2: Understand stateless nature of NACLs

   NACLs do not remember connection state, so both inbound and outbound rules must permit traffic.

3. Final Answer:

   Outbound SSH traffic is not allowed in the NACL -> Option A

4. Quick Check:

   Both directions must allow SSH for connection success = C [OK]

Hint: Allow both inbound and outbound for SSH due to stateless NACLs [OK]

Common Mistakes:

• Assuming NACLs are stateful and outbound rules are unnecessary
• Blaming security groups without checking NACLs
• Ignoring outbound rules for return traffic

5. You want to allow a subnet to communicate with the internet using HTTP and HTTPS. Which NACL configuration correctly supports this stateless behavior?

hard

A. Allow all inbound and outbound traffic to simplify rules

B. Allow inbound TCP ports 80 and 443, allow outbound ephemeral ports 1024-65535

C. Allow inbound and outbound TCP ports 80 and 443 only

D. Allow inbound ephemeral ports 1024-65535, allow outbound TCP ports 80 and 443

Solution

1. Step 1: Understand HTTP/HTTPS traffic flow

   Clients initiate outbound connections to ports 80 and 443; responses come back on ephemeral ports (1024-65535).

2. Step 2: Configure NACL rules for stateless behavior

   Outbound rules must allow TCP ports 80 and 443; inbound rules must allow ephemeral ports for return traffic.

3. Final Answer:

   Allow inbound ephemeral ports 1024-65535, allow outbound TCP ports 80 and 443 -> Option D

4. Quick Check:

   Outbound to 80/443, inbound ephemeral ports for response = A [OK]

Hint: Allow outbound ports 80/443 and inbound ephemeral ports for return [OK]

Common Mistakes:

• Allowing inbound ports 80/443 instead of ephemeral ports
• Not allowing ephemeral ports inbound blocks responses
• Allowing all traffic unnecessarily