Capability vs. Access Control List
(2 classes)
(1) A Real-Life Analogy: Bank Analogy
Carla wishes to keep all of her valuables in a safe deposit box in the bank. On occasion, she would like one or more trustworthy friends to make deposits or withdrawals.
There are two ways that the bank can control access to the box.
(1) The bank maintains a list of people authorized to access the box.
(2) The bank issues Carla one or more keys to the safe deposit box.
ACL Approach
-- Bank's involvement: The bank must (i) store the list, (ii) verify users.
-- Forging access right: The bank must safeguard the list.
The bank must authenticate.
-- Add a new person: The owner must visit the bank.
-- Delegation: A friend cannot extend his or her privilege to someone else.
-- If a friend becomes untrustworthy, the owner can remove his/her name.
Capability Approach
-- Bank's involvement: The bank need not be involved in any transactions
-- Forging access right: The key cannot be forged
-- Adding a new person: The owner can give the key to the new person
-- Delegation: A friend can extend his or her privilege to someone else.
-- Revoke: The owner can ask for the key back, but it may not be possible to know whether or not the fried has made a copy.
Advantages:
-- Ease of use: capability is better
-- Friends can become enemies: access control list is better
(2) Concept: What is a capability
· Introduced by Dennis and Van Horn, 1966.
"A capability is a token, ticket, or key that gives the possessor permission to access an entity or object in a computer system".
· A capability is implemented as a data structure that contains:
-- Identifier: addresses or names. e.g. a segment of memory, an array,
a file, a printer, or a message port.
-- Access right
· Example: PUT(file_capability, "this is a record");
(3) Case Study: Access Control on File Access
· How does the access control list work?
ü Where to store the access control list? (Must be in a safe place)
ü inode data structure of Minix
Boot block: Super block: I-node bit map: Zone bit map: I-nodes: Data
16 bits each row (total 64 bytes)
Mode
Number of links
Uid
Gid
Each of the following are 32 bits
File size
Access time
Modification time
Status change time
Zone 0 -- Zone 6: each block is 1K
Indirect zone
Double indirect zone
Unused
ü Question: how to implement a full access control list?
· How does the capability work?
ü Where to store the capability? (Must be in a safe place)
ü How to make it hard to forge?
(1) Check the capability list
Save the capability list in the kernel.
For each access, check the list.
(2) Present the capability
A process presents the capability.
Problem: user can modify it.
Solution: (a) Encryption (integrity checksum)
(b) Tagged architecture (read-only, use-only)
(3) Combination of both:
Save the capability list in the kernel.
A process presents the index of the capability in the capability list.
ü Minix example:
Process Table --> Filp table --> I-node table
struct fproc /* (in src/fs/fproc.h) */
{
......
struct filp *fp_filp[OPEN_MAX]; /* the file descriptor table */
}
struct filp {
mode_t file_mode; /*RW bits, telling how file is opened */
int filp_flags;
int filp_count; /* how many file descriptors share this slot? */
struct inode *filp_ino /* pointer to the inode table */
off_t filp_pos;
}
The table is the capability list.
Q: How to forge a capability, so we can access a file without the legitimate capability?
A: need to put the inode entry in the table.
Q: Can we directly use fp_filp[10]?
A: Users cannot modify filp table (it is in the kernel)
(4) Case Study: Access Control on Memory Access
· Conventional segment address translation scheme
· Capability register addressing
Explain the two schemes. Draw the figures.
An important difference: the ability of a program to affect system-wide or process-local objects.
· Conventional:
A program executes within a virtual address space defined by a process. Every procedure called by that program has access to the process address space, including segments and files. Every procedure executes within an identical protection environment.
· Capability:
A procedure can only affect objects for which capability registers have been loaded. It is possible, for different procedures called by the same program to have access to different segments. (Note: although they have the potential to load capability registers from the capability list, some procedures may choose to execute within a very small addressing sphere).
· The benefit of restricting execution environment
The least privilege principle
(5) Comparison
· Pros and cons of Capability and ACL
v Naming objects:
ü ACL: can attempt to name any object in the system as the target of an operation.
Pros: The set of the accessible objects is not bounded.
Cons: Worm, virus, backdoor, stack buffer overflow.
ü C-List: a user can only name those objects for which a capability is held.
Pros: the least privilege principle
Cons: the set of the accessible objects is bounded.
v Granularity:
ü ACL is based on users.
ü Capabilities can be based on process, procedure
Caller and callee have different capabilities
Most capability systems go a step further: allow each procedure to have a private capability list.
ü Finer granularity --> the principle of least privilege
--- Root is a bad.
--- ACL is a bad
v Overhead
ü ACL: significant overhead when processing large ACLs
v Memory address: Addressing primary memory: capability
· Discussion:
-- Q: How to use capability to solve the virus problem?
-- Q: How to build sandbox using capability?
-- Discussion of the idea of set-Nobody-UID
(6) Issues on Capability:
· How to prevent a called program does not retain or pass on a capability parameter.
ü An extra bit to specific whether a capability can be stored in a C-list with longer life than the procedure invocation.
ü An extra bit can also be used to prevent copying.
· How do you revoke a capability (it is difficult)
ü Have each capability point to an indirect object
ü Use a random number. The owner can change the number.
A user must also present the number in addition to the capability. (used in Amoeba)
ü Neither allows selective revocation.
ü Revocation is generally a difficult problem.