Computer Science 161 (2016)

Final Exam

24 hours between 9:00 AM May 6, 2016 and 5:00 PM May 9, 2016 PM

240 minutes/240 points

Instructions

The points allocated to each problem correspond to how much time we think the problem should take. Although you have 24 hours in which to take the exam, we do not recommend that you pull an all-nighter and spend 24 hours completing the exam.

All questions should be directed to Professors Seltzer and Mickens via email. We will check mail periodically, but you should not expect an instant response. We strongly encourage you to read through the exam and fire off any questions that immediately come to mind. When in doubt, document assumptions.

Here is our advice on how to complete this exam:

Please place your answers in the final.txt file that you will find in the course code repository in the exams directory. In the policy2.txt file, place the exam policy statement (see below) which indicates that you have followed all the rules for the exam. Do not forget to:
  1. Commit your changes
  2. Push your changes
  3. Enter your personal repository URL on the grading server.
This exam is open text book, open source code, open course web site, and open notes. It is not open Internet -- you may use only the materials listed above. In particular: You must complete the exam on your own.

Exam Policy Statement

Please do not forget to do this!

After you have completed the exam, assuming that you have, in fact, followed all the rules stated above, please type the following statement into the policy2.txt file and place your name after it. "I have neither given nor received help on this exam and have followed the rules as stated." If this statement is absent, you will hear from us.

I. Scheduling (28 points)

The following statements about scheduling are true to some degree. Your task is to place the statements in order from least true to most true. For each statement, explain what is true about the statement and what is not true. Then justify its relative position in the ranking.
  1. Shortening the scheduling quantum will make a system more responsive to interactive jobs.
  2. Shortening the scheduling quantum increases system overhead.
  3. Shortening the scheduling quantum produces fairer scheduling.
  4. The length of the scheduling quantum dictates how long a compute-bound process runs before another process is scheduled.

II. Virtualization (45 points)

On an x86 chip without VT-x support, virtualization is often implemented using direct execution with binary translation, such that the VMM lives in Ring 0, the guest OS lives in Ring 1, and the guest applications live in Ring 3. However, processors such as MIPS only have two privilege levels (user-mode and kernel-mode), meaning that the guest OS must execute with the user-mode privilege level---from the perspective of the hardware, the guest OS is just a standard user-mode application.

The hypothetical Janus processor has two privilege levels. The Janus processor supports the MIPS instruction set and defines trap frames to be the same (in spirit, if not exact content) to the trap frames used in OS/161. However, the Janus processor uses x86-style memory management, meaning that: On the Janus processor, operating systems are relocatable, i.e., the kernel can be mapped into an arbitrary location in virtual memory. Further, the processor reserves the upper half of virtual memory for a privileged program like an OS; user-mode applications cannot access that part of memory. Also note that all sensitive Janus instructions are privileged. Thus, a VMM can do direct execution with trap-and-emulate, avoiding the need for binary translation.

A. Designing a VMM (30 points)

Describe the design for a VMM that runs on the Janus processor. The guest OS and guest applications should be memory-isolated from each other, but the guest applications must be able to execute system calls that are handled by the guest OS (after being vectored through the VMM). Your answer should focus on how system calls work; to make your discussion concrete, explain your design with respect to the getpid() system call (you only need to describe enough of your design to make getpid() work, and to provide memory isolation between the guest OS and guest applications).

In your answer, describe the control flow that is triggered by getpid(), starting with the guest application calling getpid(), and ending with the guest application reading the return value of getpid(). You should describe details like: State any additional assumptions that you make.

B. Supporting read() (15 points)

Now suppose that you must extend your VMM to support the read() system call. Describe why it is more difficult to implement a data-movement system call like read() than a system call like getpid(). Then, describe how you would update your design from Part A to handle read(). Be specific about how system call parameters and results would be transferred between the guest OS and the guest application.

III. Security (40 points)

A. Attested booting (10 points)

As discussed in class, the iPhone uses an attested software stack with a hardware root of trust. The attestation process allows Apple to guarantee that only Apple-blessed software runs on the phone. Suppose that Apple wants to remove the hardware root of trust, while still using an attested software stack. In pursuit of this goal, Apple redesigns the boot sequence as follows: The read-only firmware no longer has Apple's public key burned into hardware. Instead, the read-only firmware uses formal verification to prove that the LLB is trustworthy. In particular, the read-only firmware uses formal verification to check whether the LLB adheres to this constraint: "the LLB's executable code reads iBoot from the SSD into memory, and then uses Apple's public key PubKey_Apple to verify the signature on iBoot; the LLB will only jump to the first instruction in iBoot if the signature on iBoot's code and data is valid, i.e., if the signature was generated by the private key associated with PubKey_Apple." The read-only firmware determines PubKey_Apple by extracting it from a well-known location in the LLB binary.

Is the new attested boot scheme more secure, as secure, or less secure than a standard attestation scheme which uses a hardware root of trust? Why? You should define security as "the ability of the user or the attacker to run an OS or a user-level application that has not been blessed by Apple." If the new scheme is less secure, provide an example of an attack that succeeds under the new scheme, but fails under the old scheme. If the new scheme is more secure, provide an example of an attack that fails under the new scheme, but succeeds in the old scheme.

B. Reusing process resources (30 points)

Suppose that a new version of OS161 wants to make exec() faster by reusing process resources. To do so, the kernel tracks which path names are frequently used as the targets for exec() calls. Once the kernel has determined that some path_name is popular, the kernel looks for new exec() calls that involves path_name. Let P be a process that calls exec() on path_name. Inside exec(), the kernel sets a special bit in P's process structure that indicates that the address space should be reclaimed. Later, when P calls exit(), the kernel does not destroy P; instead the kernel halts P and places it in a special waiting area associated with path_name. Later, when another process P_new calls exec(path_name), the kernel sees whether it already has a P in the waiting area for path_name. If so, the kernel reuses the address space and other bookkeeping information associated with P (for example, P will already have the necessary executable code mapped into its address space, so the OS will not require that code to be read in from disk a second time).

To securely implement process reuse, the OS must guarantee that P_new cannot access any sensitive resources that belonged to P. For example, the OS must zero-out the memory pages in P that belonged to the heap, the stack, and data regions like the BSS.
  1. (20 points) Identify a different type of process resource or bookkeeping data that may contain (or provide access to) sensitive information that P_new should not be able to access. Describe what the sensitive information is, and how the attacker would access it if the OS did an insufficient job of scrubbing the data before starting P_new. Also describe how the OS would scrub resources to prevent the information leak.
  2. (10 points) Identify a type of process resource or bookkeeping data that belonged to P and is acceptable for P_new to access and reuse. Why is the access and reuse acceptable from the security perspective?

IV. File System Implementation (27 points)

For each of the next problems, we are going to suggest a change to the SFS implementation. Your job is to indicate what impact that change would have on each of the following:

  1. The space consumed by meta-data in the file system.
  2. Whole file sequential read performance
  3. Performance of random 1-byte reads
  4. The performance of directory operations (specifically, traversal and directory rename)
  1. Double the block size.
  2. Create a directory pathname cache that contains a mapping from a full pathname of a directory (e.g., /a/b/c) to an inode number.
  3. Convert SFS to a no-overwrite file system (that is, like LFS, instead of modifying blocks in place, you will allocate a new block to the file and free the old block; however, we are not proposing a segment-oriented scheme like LFS).

V. Virtual Memory (20 points)

Suppose that the hardware designers for MIPS decide to get rid of per-core TLBs--instead, there will be a single TLB that is shared by all cores. This is an OS-visible architectural change, specifically, not just an implementation modification such that the per-core TLBs are simply crammed together in a single piece of hardware.

Describe the additional hardware support (if any) that would be needed to simultaneously run different processes on different cores. Also sketch a design for how an OS would perform context switches and TLB invalidations on the new processor architecture; describe whether any cross-core IPIs would be needed to handle context switches and TLB invalidations.

VI. Failure Atomic Updates (80 points)

The purpose of this question is two fold: First, we believe that you will find it immensely satisfying to see how far you've come this semester, when you read a recent research paper and are able to understand it and think deeply about it. Second, between lecture and Assignment 4, you've spent a lot of time thinking about file systems and this is where you get to synthesize all that material. For this question, you'll need to read (at least) sections 1-3 of the paper Failure-Atomic Updates of Application Data in a Linux File System. After you've done that, answer the following questions.

In Assignment 4, we explicitly stated that you need not worry about journaling and recovering user data. It is now time to consider the challenges inherent in providing a range of guarantees to the user. Let's begin with something weaker than the consistent modifications of application durable data (CMADD) discussed in the paper.

A. Single-write Recovery

We're getting ready to roll out OS/161 for production use and it's no longer acceptable to lose user data. Propose a strategy for making application writes recoverable. This is not the same guarantee as CMADD from the paper, but rather a guarantee that whatever is written in an individual write system call is guaranteed to appear atomically in the file system. Include a precise description of 1) your log records, 2) what ordering constraints you will enforce, and 3) how you will undo and redo such operations during recovery.

B. Compare your new and improved SFS with CMADD

Next, we want you to compare and contrast your new and improved SFS with the CMADD described in the paper. When we ask you to describe a workload or application, be specific. The phrase "an application that writes a TB of data" is not specific enough. Instead, describe what the application is doing, "Imagine a key/value store where both keys and data are arbitrarily long and are not necessarily stored adjacent to each other."

Give an example of a workload/application where the improved SFS provides the same guarantees as CMADD. Explain why the workload behaves the same on both systems.

C. More comparisons

Give an example of a workload/application where the improved SFS provides weaker guarantees than CMADD. Explain how the workload behaves on each system and what problems might arise.

D. Extend SFS to support CMADD

You are asked to extend SFS to support CMADD. You may add the calls discussed in the paper, but your implementation must be purely journal-based. You reply that, while you can provide the requested functionality, there is a terrible mismatch between the interfaces as provided and a pure journaling approach. Explain this mismatch.

E. CMADD via COW versus CMADD via Journaling

Nonetheless, the powers that be have decided to move ahead with the journal-based CMADD implementation.

Discuss the space trade-offs between a journal-based design and the one proposed in the paper.

F. Recovery

Recovery will be simpler in which system? Why?