CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Cells (20 minutes)

A system has 500 users and 200,000 objects. How many cells does its access matrix have?

Done when: 100,000,000.

Hint

multiply users by objects.

Easy 2: Read the matrix (20 minutes)

In the program of section 3, which subjects may use the printer, and what rights does daemon have on the logfile?

Done when: alice, bob and daemon; write only.

Hint

read the printer column of the ACL listing.

Easy 3: Which goal (20 minutes)

Name the goal that fails in each case: a user reads another user's mail; a user changes a grade; a program fills the disk.

Done when: confidentiality, integrity, availability.

Hint

think of reading, changing and using up.

Medium

Medium 1: Sparse storage (45 minutes)

A matrix has 2,000 users and 500,000 objects, and 0.05% of the cells hold a right. Find the number of entries and the size at 8 bytes each, and the size of a full table of 1 bit per cell.

Done when: 500,000 entries, 4 MB, and 125 MB.

Hint

2,000 x 500,000 x 0.0005 = 500,000. Eight bytes each. One bit per cell: 10^9 / 8.

Medium 2: Revoke (45 minutes)

An object is shared with 40 subjects through ACLs, and the same right also exists as a capability copied to 40 processes. Count the places to change to revoke it in each design.

Done when: 1 list edit for the ACL design and up to 40 copies to find for capabilities, with a sentence on indirection as a fix.

Hint

an ACL has one list for the object. A capability can be anywhere.

Medium 3: Check a domain (45 minutes)

On your Linux machine, run id and grep -E "^(Uid|Gid|Groups|CapEff)" /proc/self/status. Then run the same in setpriv --reuid=65534 --regid=65534 --clear-groups (as root) or sudo -u nobody to compare.

Done when: two listings, and a sentence on what changed in the domain.

Hint

look at the CapEff line.

Hard

Hard 1: Extend the matrix (90 minutes)

Change the program so that it reads the matrix from a text file, and add a command that revokes one right of one subject on one object. Show both cuts before and after.

Done when: the output of a revoke of alice's write on report, with both lists updated.

Hint

use fscanf with the words and a rights string.

Hard 2: Open descriptor survives chmod (90 minutes)

Write a program that opens a file for reading, then calls chmod(path, 0) on it, and then reads from the open descriptor. Show that the read still works, and that a new open of the same file by a non-root user fails.

Done when: the read succeeds, and the second open fails with EACCES (run the second open as nobody with setpriv).

Hint

chmod(path, 0) as root does not stop root. Test the second open as nobody.

Hard 3: Design a least-privilege service (90 minutes)

A program must listen on port 80, read files from /srv/www, and write a log in /var/log/site. List the rights each part really needs, and say how you would split the program or limit it so that no part has more than that.

Done when: a table with at least three rights and the rule that gives each, and a note on dropping from root after the port is open.

Hint

port 80 needs a special right, CAP_NET_BIND_SERVICE, or root, only at the start.