Fine-grained access control in DynamoDB - Time & Space Complexity

Time Complexity: Fine-grained access control

O(n)

Understanding Time Complexity

When using fine-grained access control in DynamoDB, we want to know how the time to check permissions grows as data or rules increase.

We ask: How does the cost of enforcing detailed access rules change with more data or conditions?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB policy check snippet.

// Example: Checking user access to items with attribute filters
const params = {
  TableName: "Documents",
  KeyConditionExpression: "UserId = :uid",
  FilterExpression: "AccessLevel = :level",
  ExpressionAttributeValues: {
    ":uid": userId,
    ":level": userAccessLevel
  }
};
const result = await dynamodb.query(params).promise();
// Returns items user can access based on fine-grained rules

This code queries items for a user and filters them by access level to enforce fine-grained control.

Identify Repeating Operations

Look for repeated work in the query and filtering process.

• Primary operation: Querying items matching user ID, then filtering by access level.
• How many times: Each item for the user is checked once against the filter condition.

How Execution Grows With Input

As the number of items for a user grows, the system checks each item's access level.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of checks grows directly with the number of items to filter.

Final Time Complexity

Time Complexity: O(n)

This means the time to enforce fine-grained access grows linearly with the number of items checked.

Common Mistake

[X] Wrong: "Filtering by access level happens instantly regardless of item count."

[OK] Correct: Each item must be checked against the access rule, so more items mean more work.

Interview Connect

Understanding how access control scales helps you design systems that stay fast as data grows, a key skill in real projects.

Self-Check

"What if we added an index on AccessLevel to speed filtering? How would the time complexity change?"

Practice

1. What is the main purpose of fine-grained access control in DynamoDB?

easy

A. To automatically backup data

B. To speed up query performance

C. To restrict access to specific items based on keys

D. To encrypt data at rest

Solution

1. Step 1: Understand fine-grained access control concept

   Fine-grained access control limits access to individual items or attributes in a DynamoDB table.

2. Step 2: Identify the main purpose

   This control is used to restrict access based on keys, ensuring users see only their data.

3. Final Answer:

   To restrict access to specific items based on keys -> Option C

4. Quick Check:

   Fine-grained access control = restrict by keys [OK]

Hint: Focus on access control by keys, not performance or encryption [OK]

Common Mistakes:

• Confusing access control with encryption
• Thinking it improves query speed
• Assuming it manages backups

2. Which IAM policy condition key is used to enforce fine-grained access control in DynamoDB?

easy

A. dynamodb:LeadingKeys

B. dynamodb:TableName

C. dynamodb:Attributes

D. dynamodb:EncryptionEnabled

Solution

1. Step 1: Identify IAM condition keys for DynamoDB

   DynamoDB uses specific condition keys in IAM policies to control access.

2. Step 2: Match condition key for fine-grained access

   The key dynamodb:LeadingKeys restricts access based on partition key values.

3. Final Answer:

   dynamodb:LeadingKeys -> Option A

4. Quick Check:

   Fine-grained access uses dynamodb:LeadingKeys [OK]

Hint: Remember 'LeadingKeys' controls item-level access [OK]

Common Mistakes:

• Choosing TableName which controls table-level access
• Confusing Attributes with keys
• Selecting unrelated encryption keys

3. Given this IAM policy snippet, which items can the user access?

{
  "Effect": "Allow",
  "Action": "dynamodb:GetItem",
  "Resource": "arn:aws:dynamodb:us-east-1:123456789012:table/Orders",
  "Condition": {
    "ForAllValues:StringEquals": {
      "dynamodb:LeadingKeys": ["user123"]
    }
  }
}

medium

A. All items in the Orders table

B. Only items with partition key 'user123'

C. Items with any partition key except 'user123'

D. No items, because the policy is invalid

Solution

1. Step 1: Analyze the IAM policy condition

   The condition restricts access to items where the partition key matches 'user123'.

2. Step 2: Determine accessible items

   Only items with partition key 'user123' are accessible; others are denied.

3. Final Answer:

   Only items with partition key 'user123' -> Option B

4. Quick Check:

   Condition limits to 'user123' keys [OK]

Hint: Check the LeadingKeys value to find accessible items [OK]

Common Mistakes:

• Assuming access to all items
• Thinking policy denies all access
• Ignoring the condition block

4. You wrote this IAM policy to restrict access to items with partition key 'user456', but users still access other items:

{
  "Effect": "Allow",
  "Action": "dynamodb:GetItem",
  "Resource": "arn:aws:dynamodb:us-east-1:123456789012:table/Orders",
  "Condition": {
    "StringEquals": {
      "dynamodb:LeadingKeys": "user456"
    }
  }
}

What is the likely error?

medium

A. Action should be dynamodb:Query instead of GetItem

B. Resource ARN is incorrect

C. Effect should be Deny instead of Allow

D. Condition should use ForAllValues:StringEquals with an array

Solution

1. Step 1: Check condition syntax for dynamodb:LeadingKeys

   The condition expects an array with ForAllValues:StringEquals, not a single string with StringEquals.

2. Step 2: Understand impact of incorrect condition

   Using StringEquals with a string causes the condition to be ignored, allowing broader access.

3. Final Answer:

   Condition should use ForAllValues:StringEquals with an array -> Option D

4. Quick Check:

   Use ForAllValues:StringEquals and array for LeadingKeys [OK]

Hint: Use ForAllValues:StringEquals with array for LeadingKeys [OK]

Common Mistakes:

• Using StringEquals with a string instead of array
• Incorrect ARN format
• Confusing action types
• Changing Effect to Deny unnecessarily

5. You want to allow users to read only their own orders in a DynamoDB table where the partition key is 'UserId'. Which IAM policy condition correctly enforces this fine-grained access control for user 'alice'?

hard

A. { "ForAllValues:StringEquals": { "dynamodb:LeadingKeys": ["alice"] } }

B. { "StringEquals": { "dynamodb:Attributes": ["alice"] } }

C. { "ForAnyValue:StringEquals": { "dynamodb:LeadingKeys": ["alice"] } }

D. { "StringLike": { "dynamodb:LeadingKeys": "alice*" } }

Solution

1. Step 1: Identify correct condition operator for exact key match

   For fine-grained access, ForAllValues:StringEquals with an array ensures all keys match exactly.

2. Step 2: Evaluate options for correct syntax and semantics

   { "ForAllValues:StringEquals": { "dynamodb:LeadingKeys": ["alice"] } } uses correct operator and array format; others use wrong keys or operators.

3. Final Answer:

   { "ForAllValues:StringEquals": { "dynamodb:LeadingKeys": ["alice"] } } -> Option A

4. Quick Check:

   Exact key match needs ForAllValues:StringEquals with array [OK]

Hint: Use ForAllValues:StringEquals with array for exact user keys [OK]

Common Mistakes:

• Using dynamodb:Attributes instead of LeadingKeys
• Using StringEquals without array
• Using StringLike which allows wildcards