Project 2: Capability System Implementation
Build a capability-based access control system with creation, delegation, and revocation.
Quick Reference
| Attribute | Value |
|---|---|
| Difficulty | Advanced |
| Time Estimate | 2 weeks |
| Language | C (Alternatives: Rust) |
| Prerequisites | IPC basics, access control concepts |
| Key Topics | Capabilities, delegation, revocation, least privilege |
1. Learning Objectives
By completing this project, you will:
- Implement unforgeable capability tokens with rights.
- Support delegation and derivation with reduced rights.
- Solve revocation with a practical strategy.
- Explain how capability systems prevent confused deputy attacks.
2. Theoretical Foundation
2.1 Core Concepts
- Capabilities: Unforgeable tokens that grant specific rights to a resource.
- Object-Capability Model: Access is possible only if you hold a capability.
- Delegation: Passing a restricted capability to another process.
- Revocation: Invalidate derived capabilities without global scans.
2.2 Why This Matters
Microkernels like seL4 and Zircon rely on capabilities to guarantee least privilege. This minimizes the blast radius of compromise and makes security reasoning tractable.
2.3 Historical Context / Background
UNIX permissions are identity-based (UID/GID). Capabilities emerged to avoid ambient authority. Modern microkernels prove security properties partly because capabilities are explicit and trackable.
2.4 Common Misconceptions
- “Capabilities are just ACLs.” Capabilities are possession-based, not identity-based.
- “Revocation is easy.” Revocation is the hardest part; plan for it early.
3. Project Specification
3.1 What You Will Build
A capability runtime that issues tokens for objects (memory, endpoints, devices), supports derive/delegate, and enforces rights at invocation time.
3.2 Functional Requirements
- Capability creation: Privileged API to create caps for resources.
- Derivation: Create a child cap with reduced rights.
- Invocation: Check rights on use and return errors on denial.
- Delegation: Transfer caps via IPC messages.
- Revocation: Invalidate capabilities using a chosen strategy.
3.3 Non-Functional Requirements
- Security: No forgeable IDs or predictable tokens.
- Performance: O(1) checks on invocation.
- Traceability: Track which caps were derived from which.
3.4 Example Usage / Output
cap_t mem = cap_create(OBJ_MEMORY, 4096, CAP_READ | CAP_WRITE);
cap_t ro = cap_derive(mem, CAP_READ);
cap_send(endpoint_to_b, ro);
cap_t b_cap = cap_recv(my_endpoint);
cap_write(b_cap, data); // returns EPERM
3.5 Real World Outcome
$ ./cap_demo
[cap] created mem object id=42 rights=RW
[cap] derived id=43 rights=R
[ipc] sent cap id=43 to pid=2001
[cap] invoke write on id=43 -> EPERM
[cap] revoke id=42 -> invalidates descendants
4. Solution Architecture
4.1 High-Level Design
┌──────────────┐ cap_create ┌──────────────┐
│ Privileged │ ─────────────▶ │ Cap Manager │
│ Server │ │ (tables) │
└──────────────┘ └──────┬───────┘
│
cap_invoke │
▼
┌───────────┐
│ Resource │
└───────────┘
4.2 Key Components
| Component | Responsibility | Key Decisions |
|---|---|---|
| Cap table | Per-process storage | Fixed vs dynamic size |
| Cap manager | Global registry | Centralized vs distributed |
| Revocation index | Track descendants | Tree vs indirection table |
| IPC transfer | Pass caps safely | Handle transfer list |
4.3 Data Structures
typedef struct {
uint64_t object_id;
uint32_t rights;
uint32_t gen;
} cap_t;
typedef struct {
cap_t slots[MAX_CAPS];
uint8_t used[MAX_CAPS];
} cap_table_t;
4.4 Algorithm Overview
Key Algorithm: Capability Invocation
- Look up cap slot.
- Validate generation and rights.
- Dispatch to object handler.
Complexity Analysis:
- Time: O(1) for lookup and rights check
- Space: O(N) for cap table
5. Implementation Guide
5.1 Development Environment Setup
cc -O2 -g -o cap_demo *.c
5.2 Project Structure
cap-system/
├── src/
│ ├── cap_table.c
│ ├── cap_mgr.c
│ ├── cap_ipc.c
│ └── main.c
├── include/
│ └── cap.h
└── tests/
└── test_caps.c
5.3 The Core Question You’re Answering
“How do you prevent a process from touching anything it doesn’t explicitly hold a right for?”
5.4 Concepts You Must Understand First
Stop and research these before coding:
- Confused Deputy Problem
- Least Privilege
- Unforgeable Tokens
- Revocation Patterns (generation numbers vs trees)
5.5 Questions to Guide Your Design
- Do you allow delegation without kernel mediation?
- How do you represent rights (bitmask vs enum)?
- How do you avoid capability leaks across IPC boundaries?
- What is your revocation strategy and its cost?
5.6 Thinking Exercise
Model a Delegation Tree
Draw a tree of capabilities for a file. If the root is revoked, which caps must become invalid? How will you find them efficiently?
5.7 The Interview Questions They’ll Ask
- “How do capabilities differ from ACLs?”
- “Why is revocation difficult in capability systems?”
- “How does seL4 prevent capability forgery?”
5.8 Hints in Layers
Hint 1: Start with a global table Use a single manager process at first.
Hint 2: Add generation numbers Increment generation on revoke to invalidate old copies.
Hint 3: Add a derivation tree Track parent/child relationships to revoke subtrees.
5.9 Books That Will Help
| Topic | Book | Chapter |
|---|---|---|
| Capability security | seL4 papers | Design sections |
| Access control | OSTEP | Security chapters |
5.10 Implementation Phases
Phase 1: Foundation (3 days)
Goals:
- Cap table and basic creation
Tasks:
- Implement cap table per process.
- Add
cap_createandcap_invoke.
Checkpoint: Simple object access works.
Phase 2: Core Functionality (5 days)
Goals:
- Delegation and derivation
Tasks:
- Implement
cap_derive. - Transfer caps via IPC messages.
Checkpoint: Child process uses delegated cap.
Phase 3: Polish & Edge Cases (4 days)
Goals:
- Revocation
- Error handling
Tasks:
- Add generation or tree-based revocation.
- Add unit tests for invalid caps.
Checkpoint: Revoked caps fail on use.
5.11 Key Implementation Decisions
| Decision | Options | Recommendation | Rationale |
|---|---|---|---|
| Revocation | Generation, tree | Generation + indirection | Simple and fast |
| Rights model | Bitmask, enum | Bitmask | Compact and easy checks |
| Cap storage | Array, hash | Array | O(1) and predictable |
6. Testing Strategy
6.1 Test Categories
| Category | Purpose | Examples |
|---|---|---|
| Unit Tests | Table ops | create, derive, revoke |
| Integration Tests | IPC transfer | pass cap and use |
| Security Tests | Forgery attempts | invalid ID use |
6.2 Critical Test Cases
- Derived cap denies write.
- Revoked cap fails even if copied.
- IPC transfer preserves rights.
6.3 Test Data
Rights: R, W, X
Objects: memory, endpoint
Operations: invoke, revoke
7. Common Pitfalls & Debugging
7.1 Frequent Mistakes
| Pitfall | Symptom | Solution |
|---|---|---|
| Predictable IDs | Easy forgery | Use random or kernel-assigned IDs |
| Revocation leaks | Old caps still work | Use generation checks |
| Rights mismatch | Over-privilege | Always intersect rights on derive |
7.2 Debugging Strategies
- Log every cap creation and revoke.
- Add a debug command to dump a process cap table.
7.3 Performance Traps
Revocation trees can be O(N) if you walk the whole tree. Avoid global scans unless debugging.
8. Extensions & Challenges
8.1 Beginner Extensions
- Add a capability inspector tool.
- Add auditing logs for cap usage.
8.2 Intermediate Extensions
- Support capability transfer with rights attenuation rules.
- Add per-cap metadata (owner, purpose).
8.3 Advanced Extensions
- Integrate with Project 1 IPC to enforce endpoint access.
- Implement capability sealing (as in CHERI).
9. Real-World Connections
9.1 Industry Applications
- seL4: Capabilities are the core security mechanism.
- Zircon: Handles are capabilities with rights bits.
9.2 Related Open Source Projects
- seL4: https://sel4.systems/
- Fuchsia/Zircon: https://fuchsia.dev/
9.3 Interview Relevance
Capability systems are a strong signal of OS security knowledge.
10. Resources
10.1 Essential Reading
- seL4 Reference Manual - Capability model chapters.
- Capability Myths Demolished - Classic paper.
10.2 Video Resources
- seL4 tutorial videos.
10.3 Tools & Documentation
- TLA+ (optional) for modeling access control.
10.4 Related Projects in This Series
- Project 1: IPC foundation.
- Project 4: Implements capabilities in a kernel.
11. Self-Assessment Checklist
11.1 Understanding
- I can explain why capabilities avoid confused deputy attacks.
- I can describe my revocation strategy and its cost.
11.2 Implementation
- Cap creation, derive, revoke are implemented.
- Rights checks block invalid operations.
11.3 Growth
- I can explain how seL4’s cap system differs from UNIX permissions.
12. Submission / Completion Criteria
Minimum Viable Completion:
- Capability creation and invocation works.
- Rights are enforced on use.
Full Completion:
- Delegation via IPC works.
- Revocation invalidates descendants.
Excellence (Going Above & Beyond):
- Capability sealing or typed caps.
- Formal model of rights and revocation.
This guide was generated from LEARN_MICROKERNELS.md. For the complete learning path, see the parent directory.