15-410 HW2 solutions (Fall, 2004)

Question 1 - Public Key Practicum

If you did this problem correctly, in a couple of hours your hw2 directory should contain a $USER.message.decrypted file. If not, check to see if there is a $USER.ERROR file. If not, a popular problem is that you used file names other than the ones specified in the assignment, the grading script wasn't able to guess what you meant, and the grader hasn't yet had the time to manually intervene.

By the way, your encrypted messages to us were read and, generally, appreciated.

Question 2 - Copy-on-write

As some students pointed out, implementing copy-on-write is a good way for an operating system to overcommit memory--to promise applications more memory than the system can actually provide.

Part A

Briefly explain how this overcommittment happens. If you wish you may use a short, clear program to help explain.

Consider the following program

main()
{
	unsigned char *base = 0x80000000, *p;
	int len = 120*1024*1024; /* nearly 1/2 of phys. mem */

	(void) new_pages(base, size); /* wow, that was fast! */
	(void) fork(); /* that was fast too! */
	(void) fork(); /* fun fun fun! */

	for (p = base; p < base + len; p += PAGE_SIZE)
		*p = '!';

	exit(0); /* what could possibly go wrong? */
}

Part B

Explain how a VM system which implements copy-on-write can avoid overcommitting system memory.

Have the VM system keep a counter of the number of free physical frames; before a region is "copied" with COW, remove the appropriate number of frames from the free-frame tally (though they remain in the free-frame pool) or fail if unable to do so. When a region is freed, of course, return the logical size of the region to the tally and any actually-used frames to the pool. In the case of the example program above, the first fork() call might well succeed, but the second and third (yes, third) fork() calls would fail, immediately, because the system would not have enough frames to fulfill its promises. Systems paging to disk would tally the sum of free frames and free frame-sized disk blocks.

Part C

Some kernel implementors and some users believe that memory overcommittment (as long as it is temporary and resolves itself non-painfully) is motivation for copy-on-write. Explain how copy-on-write could be beneficial even for systems which don't overcommit memory.

Consider the comments in the program above. A COW fork() of 120 megabytes is dramatically faster than a real fork()...easily hundreds of times faster. Even your manager would notice the difference.

Question 3 - Process Model

[...]

Explain why Bennet felt that storing the user's password in a pipe represented an increase in security over a more straightforward implementation which would hold the password somewhere in kauthd's address space. Specify a threat and how the pipe reduces the exposure to that threat. While there is more than one possibility, please describe only the one you find most threatening.

Several people approached me about this problem. Don't worry too much: the value is more in thinking (writing) about threats and how to address them than in finding "the" right answer.

The primary difference between storing the password in user memory and kernel memory is that in many systems kernel memory is not paged to disk. Some systems, such as VMS, have paged out page tables, but pipes (or their moral equivalent in other systems) are less likely to be sent to disk. One reason is that it doesn't make much sense to send a communication buffer several milliseconds away to disk when it's used to communicate with other network nodes which are themselves only milliseconds away (if you decide to retransmit a packet it's pretty expensive to first fetch it from disk...).

So storing the plain-text password in a pipe means that it will be paged to disk only if the virtual memory system is heavily loaded during the few milliseconds every 24 hours when kauthd needs to use it to acquire a new TGT. Leaving it in plain old virtual memory for 24 hours, on the other hand, almost ensures that the extremely-idle page will be evicted sometime during the course of a day.

How much of a threat is this? If I am considering breaking into your office at night to steal your disk, and in one case there is only a faint possibility it contains a plaintext password, but in the other case there's a virtual certainty...

There are less-cryptic ways to prevent memory from being paged out. For example, many versions of Unix offer a system call, mlock() which can be used to "lock" a region of memory in RAM. However, it is also popular for systems with mlock() to make it almost entirely useless by restricting its use to the superuser based on the vague argument that if you let random user riff-raff lock memory, they'd all rush to lock all of their programs into RAM and the system would degenerate to one without paging. Solaris (through at least 2.9) and Linux (through at least 2.4.24) cripple mlock() in exactly this way.

On the other hand, fringe operating systems such as BSD (NetBSD 1.2, 1998, or earlier) and Plan 9 (date unknown to this author, but probably at least since the publication of the factotum paper) make memory-locking much more available. BSD kernels consider locked memory to be a metered resource just like file size, coredump size, CPU time, stack size, etc., meaning that each process has a limited quota of memory it can lock. Plan 9 is typically willing to lock a program into memory via a simple file-system operation:
echo noswap > /proc/$pid/ctl
on the theory that in a distributed-system environment if you lock up all the RAM on the terminal you booted by being silly then only you will suffer the consequences...

For further reading...

Here is last semester's homework page.

[Last modified Friday December 10, 2004]