Policy evaluation logic in AWS - Time & Space Complexity

Time Complexity: Policy evaluation logic

O(n)

Understanding Time Complexity

When AWS checks if a user can do something, it looks at policies. Understanding how long this check takes helps us know how fast permissions work.

We want to see how the time to decide permission changes as we add more policies or rules.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Simplified policy evaluation logic
for each policy attached to user or resource {
  for each statement in policy {
    if statement matches action and resource {
      evaluate allow or deny
    }
  }
}
return final decision
    

This sequence checks all policies and their statements to decide if an action is allowed or denied.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Checking each statement in every policy attached to the user or resource.
• How many times: Once for each statement in each policy.

How Execution Grows With Input

As you add more policies or statements, the number of checks grows. More policies mean more statements to look through.

Input Size (n)	Approx. Api Calls/Operations
10 (statements)	10 checks
100 (statements)	100 checks
1000 (statements)	1000 checks

Pattern observation: The time grows directly with the number of statements checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide permissions grows in a straight line as you add more policy statements.

Common Mistake

[X] Wrong: "Adding more policies won't slow down permission checks much because AWS is super fast."

[OK] Correct: Each policy statement must be checked, so more statements mean more work and more time.

Interview Connect

Understanding how permission checks grow helps you design better systems and explain your thinking clearly in interviews.

Self-Check

"What if policies had nested conditions that require extra checks? How would the time complexity change?"

Practice

1. What happens if an AWS IAM policy has both an explicit Allow and an explicit Deny for the same action?

easy

A. The explicit Deny always overrides the Allow.

B. The Allow always overrides the Deny.

C. The action is allowed only if the user is an administrator.

D. The action is denied only if there is a condition attached.

Solution

1. Step 1: Understand explicit Deny effect

   In AWS IAM, an explicit Deny always takes priority over any Allow for the same action.

2. Step 2: Apply policy evaluation logic

   Even if a policy allows an action, if another policy explicitly denies it, the Deny wins and the action is blocked.

3. Final Answer:

   The explicit Deny always overrides the Allow. -> Option A

4. Quick Check:

   Explicit Deny > Allow [OK]

Hint: Remember: Deny always beats Allow in AWS policies [OK]

Common Mistakes:

• Thinking Allow can override Deny
• Ignoring explicit Deny effect
• Assuming conditions affect Deny priority

2. Which of the following is the correct JSON syntax to allow the s3:ListBucket action on a bucket named my-bucket?

easy

A. {\"Effect\": \"Deny\", \"Action\": \"s3:ListBucket\", \"Resource\": \"arn:aws:s3:::my-bucket\"}

B. {\"Effect\": \"Allow\", \"Action\": [\"s3:ListBucket\"], \"Resource\": \"arn:aws:s3:::my-bucket\"}

C. {\"Effect\": \"Allow\", \"Action\": \"s3:ListBucket\", \"Resource\": \"my-bucket\"}

D. {\"Effect\": \"Allow\", \"Action\": \"ListBucket\", \"Resource\": \"arn:aws:s3:::my-bucket\"}

Solution

1. Step 1: Check Action format

   The Action field must be a string or an array of strings. Using an array is valid and recommended for multiple actions.

2. Step 2: Verify Resource ARN format

   The Resource must be the full ARN: arn:aws:s3:::my-bucket for the bucket itself.

3. Final Answer:

   Action as array and correct ARN Resource -> Option B

4. Quick Check:

   Action array + correct ARN = D [OK]

Hint: Use full ARN and array for actions to avoid syntax errors [OK]

Common Mistakes:

• Using bucket name instead of ARN in Resource
• Omitting array brackets for multiple actions
• Using action name without service prefix

3. Given this policy snippet:

{
  "Effect": "Allow",
  "Action": "ec2:StartInstances",
  "Resource": "*",
  "Condition": {
    "IpAddress": {"aws:SourceIp": "203.0.113.0/24"}
  }
}

What happens if a user tries to start an EC2 instance from IP 198.51.100.10?

medium

A. The action is denied because the IP does not match the condition.

B. The action is allowed because the Effect is Allow.

C. The action is allowed only if the user has another policy allowing it.

D. The action is denied only if there is an explicit Deny policy.

Solution

1. Step 1: Understand Condition effect

   The policy allows the action only if the request comes from IPs in 203.0.113.0/24 range.

2. Step 2: Check IP address

   The user's IP 198.51.100.10 is outside the allowed range, so the condition fails.

3. Final Answer:

   The action is denied because the IP does not match the condition. -> Option A

4. Quick Check:

   Condition IP mismatch = Deny [OK]

Hint: Conditions restrict Allow; mismatch means Deny [OK]

Common Mistakes:

• Ignoring condition and assuming Allow always works
• Confusing explicit Deny with condition-based Deny
• Assuming multiple policies needed to allow

4. You have two policies attached to a user:
Policy 1: Allows s3:GetObject on bucket my-bucket.
Policy 2: Denies s3:GetObject on bucket my-bucket if the request is from outside office IP range.

The user tries to get an object from home IP. What is the result?

medium

A. The request is allowed because Policy 1 allows it.

B. The request is allowed only if the user is in the admin group.

C. The request is denied only if there is a service outage.

D. The request is denied because Policy 2 explicitly denies it from outside IPs.

Solution

1. Step 1: Identify explicit Deny with condition

   Policy 2 denies the action if the IP is outside the office range, which applies here.

2. Step 2: Apply evaluation logic

   Explicit Deny overrides any Allow, so the request is denied.

3. Final Answer:

   The request is denied because Policy 2 explicitly denies it from outside IPs. -> Option D

4. Quick Check:

   Explicit Deny with condition blocks request [OK]

Hint: Explicit Deny with condition beats Allow always [OK]

Common Mistakes:

• Ignoring condition in Deny policy
• Assuming Allow always wins
• Thinking user group affects Deny priority

5. You want to create a policy that allows ec2:StopInstances only during business hours (9 AM to 5 PM UTC) and denies it otherwise. Which policy logic correctly enforces this?

hard

A. Only use Deny with condition outside 9-17 UTC, no Allow needed.

B. Allow ec2:StopInstances with condition "DateGreaterThan": {"aws:CurrentTime": "09:00:00Z"}, no Deny needed.

C. Allow ec2:StopInstances unconditionally, and add a Deny with condition outside 9-17 UTC.

D. Allow ec2:StopInstances with condition for 9-17 UTC, and Deny unconditionally.

Solution

1. Step 1: Understand Deny override with time condition

   Unconditional Allow permits ec2:StopInstances, but explicit Deny applies outside 9-17 UTC overriding the Allow.

2. Step 2: Verify business hours enforcement

   During 9 AM-5 PM UTC: Deny condition false -> action allowed. Outside: Deny true -> denied.

3. Final Answer:

   Allow unconditionally, and add a Deny with condition outside 9-17 UTC. -> Option C

4. Quick Check:

   Allow + Deny conditions enforce time limits [OK]

Hint: Unconditional Allow + conditional Deny outside business hours [OK]

Common Mistakes:

• Relying only on Allow conditions without Deny
• Using unconditional Deny that blocks all
• Missing time range in conditions