Access Control Lists (ACLs) in Operating Systems - Time & Space Complexity

Time Complexity: Access Control Lists (ACLs)

O(n)

Understanding Time Complexity

When working with Access Control Lists (ACLs), it is important to understand how the time to check permissions grows as the list gets longer.

We want to know how the system's work changes when more entries are added to the ACL.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function checkPermission(user, resource, acl) {
  for (const entry of acl) {
    if (entry.user == user && entry.resource == resource) {
      return entry.permission;
    }
  }
  return 'no access';
}
    

This code checks if a user has permission to access a resource by scanning through the ACL entries one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each ACL entry to find a matching user and resource.
• How many times: Up to once for each entry in the ACL list, until a match is found or the list ends.

How Execution Grows With Input

As the number of ACL entries grows, the time to check permissions grows roughly in direct proportion.

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

Pattern observation: The number of checks grows linearly as the ACL list grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check permissions increases directly with the number of ACL entries.

Common Mistake

[X] Wrong: "Checking permissions is always fast and constant time regardless of ACL size."

[OK] Correct: Because the code must look through each ACL entry until it finds a match, the time depends on how many entries there are.

Interview Connect

Understanding how permission checks scale with ACL size helps you design systems that remain efficient as they grow.

Self-Check

"What if the ACL was stored in a hash table instead of a list? How would the time complexity change?"

Practice

1. What is the main purpose of an Access Control List (ACL) in operating systems?

easy

A. To monitor network traffic

B. To store the content of a file securely

C. To manage system hardware devices

D. To specify which users or groups have permissions on a file or resource

Solution

1. Step 1: Understand what ACLs control

   ACLs list permissions for users or groups on files or resources.

2. Step 2: Identify the main function

   The main function is to specify who can do what on a resource.

3. Final Answer:

   To specify which users or groups have permissions on a file or resource -> Option D

4. Quick Check:

   ACL = user/group permissions [OK]

Hint: ACLs control user permissions on files/resources [OK]

Common Mistakes:

• Confusing ACL with file content storage
• Thinking ACL manages hardware
• Assuming ACL monitors network

2. Which of the following is the correct way to represent an ACL entry for a user named 'alice' with read and write permissions?

easy

A. user:alice:rwx

B. user:alice:rw

C. group:alice:rw

D. user:alice:r

Solution

1. Step 1: Identify the correct ACL entry format

   ACL entries usually specify type (user/group), name, and permissions.

2. Step 2: Match permissions to read and write only

   Read and write permissions are 'rw', execute is 'x'. So 'rw' matches read and write.

3. Final Answer:

   user:alice:rw -> Option B

4. Quick Check:

   user + alice + rw = correct ACL entry [OK]

Hint: User entries start with 'user:' and list exact permissions [OK]

Common Mistakes:

• Using 'group' instead of 'user' for a user entry
• Adding execute permission when not needed
• Listing only read permission when write is required

3. Given the following ACL entries on a file:
user:alice:rwx
group:staff:r-x
other::r--
What permissions does a user named 'bob' who belongs to the 'staff' group have?

medium

A. Read and execute only

B. Read, write, and execute

C. Read only

D. No permissions

Solution

1. Step 1: Identify bob's group membership

   Bob belongs to the 'staff' group, so group permissions apply.

2. Step 2: Check group permissions in ACL

   Group 'staff' has 'r-x' which means read and execute, no write.

3. Final Answer:

   Read and execute only -> Option A

4. Quick Check:

   Group 'staff' = r-x = read + execute [OK]

Hint: User's group permissions apply if user not listed explicitly [OK]

Common Mistakes:

• Assuming user permissions apply to bob
• Including write permission incorrectly
• Using 'other' permissions instead of group

4. A system administrator sets an ACL entry as user:bob:r but Bob reports he cannot write to the file. What is the most likely cause?

medium

A. The file is owned by another user

B. Bob is not listed in the ACL

C. The ACL entry only grants read permission, not write

D. The ACL entry syntax is incorrect

Solution

1. Step 1: Analyze the ACL entry permissions

   The entry 'user:bob:r' grants only read permission, no write.

2. Step 2: Understand why Bob cannot write

   Without write permission, Bob cannot modify the file.

3. Final Answer:

   The ACL entry only grants read permission, not write -> Option C

4. Quick Check:

   Read-only permission blocks writing [OK]

Hint: Check if write permission 'w' is included in ACL entry [OK]

Common Mistakes:

• Assuming ownership affects ACL permissions directly
• Thinking syntax error causes permission denial
• Ignoring the actual permissions granted

5. You want to allow a group named 'developers' to have read and write access to a file, but no execute permission. Which ACL entry correctly achieves this without affecting other permissions?

hard

A. group:developers:rw-

B. group:developers:rwx

C. user:developers:rw-

D. group:developers:r--

Solution

1. Step 1: Identify the correct ACL entry type

   Since 'developers' is a group, the entry must start with 'group:developers'.

2. Step 2: Set permissions to read and write only

   Read and write permissions are 'rw-', where '-' means no execute.

3. Step 3: Confirm no execute permission is given

   group:developers:rw- uses 'rw-' which excludes execute permission.

4. Final Answer:

   group:developers:rw- -> Option A

5. Quick Check:

   Group + rw- = read/write, no execute [OK]

Hint: Use 'group:name:rw-' for read/write without execute [OK]

Common Mistakes:

• Using 'user' instead of 'group' for group permissions
• Including execute permission by mistake
• Setting only read permission when write is needed