1. Access control is a key component of a secure computing system. Capabilities or access control lists (ACLs) can be used to determine whether a request should be granted or denied. What are the pros and cons of using capabilities or ACLs. In many systems, ACLs allow both positive and negative access rights to be associated with subjects. Capabilities can have access rights (Hydra capabilities had a variety of such rights) but negative rights have not been found to be useful in the context of capabilities. Explain why negative rights are useful with ACLs but not with capabilities. Finally, give an example of a system where both ACLs and capabilities are used to govern access to resources.

2. In this question, you are asked to explore the future of text based passwords for authenticating users. In particular, you need to explore the strength of such passwords in the face of dictionary or exhaustive attacks. If the space of passwords has N elements, assume that in the worst case N crypt operations are required to find a particular user's password. Also, assume that with current 1GHz processors, one can perform one million crypt operations per second. One way to characterize the exhaustive search is to associate an entropy measure with possible passwords. For example, if the passwords are English phrases, each character offers approximately 1.2 bits of entropy (e.g., all five letter passwords can be represented using 6 bits). If English phrases that can be remembered by people easily cannot be longer than 20 letters and processor speeds will double every 18 months (Moore's law), in year 2005, how much CPU time will be needed to find someone's password by doing an exhaustive search? Based on such projections, what can say about the viability of text based passwords in the future. What other kinds of passwords can be used if text based passwords will not be strong enough to withstand dictionary attacks in the future?

3. Much of the intrusion detection work is done at the network level based on information contained in various fields of network packets. Application level intrusion detection must identify suspicious access patterns at the level of services that are accessed by the application. In particular, consider file systems. There is a good bit known about file usage based on widely available traces. How would you characterize the data in such traces and how would one use such characterizations to determine if a sequence of requests to the file system is from a potential attacker? Do you think intrusion detection closer to the application level is a good idea? Explain your answer.

4. Assume you are in charge of specifying a cryptographic protocol to enable a user to control his/her home remotely (lights, appliances, alarm system, etc..) through Internet.

(a) Describe the infrastructure you are going to use. Be specific about the pros and cons of your choices.

(b) Specify the protocol. Include the cryptographic algorithm(s) you have chosen, steps, what you are targeting on each step (authentication, authorization, confidentiality, ...), any other detail that you think make your protocol cool.

(c) Give examples of threats that your protocol is robust against and that it is not. Clearly state the reason your protocol is vulnerable to some attacks if this is the case.

In this question I am only concerned with the security of your protocol. Although other factors may (and should) affect your decisions, like cost, you should concentrate in detailing the security related features of your protocol. Please include anything that is not listed above which makes your protocol interesting.

5. Provide two examples of application-level functionality placed into the kernel that can substantially improve performance. Then define the constraints that must be imposed by future operating systems that attempt to make such placements routinely possible, even for end users who are not experts in how to build or protect OS kernels and other users on the same machine. You must be complete for this part of the question and mention related work.

6. (Read the entire question before starting to answer.) Program specialization is similar to partial evaluation. A generic program can be specialized when there are _invariants_ that make some sequence of instructions superfluous, since they always produce the same results at the end. The idea of program specialization is to replace the sequence of instructions with the result, thus improving program performance. The main difficulty in OS specialization is that there are _quasi-invariants_ that remain true almost all of the time, but that could be invalidated in rare situations.

(a) In their SOSP'95 paper, Pu et al describe the specialization of the HP-UX file system. They specialize the read system call using the exclusive sequential access quasi-invariant, which is considered the most common case in Unix file systems. Give an example of quasi-invariant in another OS module that may improve system performance through specialization. Hint: I/O subsystems are easier candidates.

(b) To guard against the rare cases when quasi-invariants may be invalidated, we need to insert _guards_ into the system when applying program specialization. For example, in the specialization of HP-UX read system call, they inserted guards into the open system call, which may invalidate the exclusive access quasi-invariant when a second process opens the same file. A less obvious guard is inserted into the dup system call, which may produce the same result. For the example of quasi-invariant you gave in sub-question (a), give two examples of places you need to guard against quasi-invariant invalidation. If you believe there is only one guard necessary, present an argument that you don't need any other guards.

7. Polling and interrupts can both be used to deliver events, e.g. notification of the arrival of a network message in a multiprocessor. This problem explores the issues arising from using both mechanisms. (a) under what circumstances does each mechanism provide better performance than the other? (b) what does an OS have to do to make polling of an I/O device available as a user-level mechanism? (c) What does an OS have to do to make device interrupts available as a user-level mechanism? Give examples that are as concrete as possible.

8. In distributed systems, failures make it difficult and/or impossible to solve many problems. For example, the consensus problem allows a set of nodes to decide on a common outcome of a protocol's execution (e.g., a commit protocol decides if the results of a computation should be made permanent or undone). In a purely asynchronous system, it is impossible to reach consensus. Consider a system in which message delivery time is bounded. Furthermore, processes can execute atomic steps in which they can receive a set of messages and send messages to one or more other processors (broadcast including a message to all participants in a protocol). Can one design a consensus protocol for such a system? If your answer is yes, give the protocol and argue why it is correct. Otherwise, discuss why no such protocol exists.