CS380L: Advanced Operating Systems

Emmett Witchel

Assignment #3 Proposal

Drivers

The goal of this assignment is to come up with a plan for Assignment 3.

Assignment 3 is a more open-ended assignment, where you have the flexibility to pursue an OS topic or subsystem that interests you. The goal of the first part of this assignment then, is to identify roughly what you will be doing for the rest of the assignment. Unless you have made other arrangements, you should focus on working within the field of Linux device drivers.

You must submit a proposal (~1 page long), which covers:

  • Whether you will create a new driver (based upon a skeleton), or modify an existing driver
  • The functionality you plan to include in the driver
  • Information about how the driver's functionality will be accessed, and
  • A brief plan on how you will be evaluating your driver's performance/functionality

    • There are many resources concerning device drivers (in addition to the actual code/documentation that came with the kernel source). For example, there is a book "Linux Device Drivers" by Rubini & Corbet. (A slightly older 2nd edition is available online at this site.

    I will review your proposal, and can request a revision.

    Ideas (related to TxOS)

    1) Implement speculation using the TxOS infrastructure.
    Transactions and speculations (see Nightingale's SOSP 05 and OSDI 06 papers) are similar in that they both provide a degree of isolation to a set of work, but the guarantees are different.  Moreover, a substantial portion of the implementation of this isolation in each system functionally overlaps.  It would be interesting to see the amount of additional effort required to leverage the transaction implementation to provide speculation.
    I would recommend first reproducing the results for hiding the latency of synchronous writes to a local file system, and perhaps next looking at NFS latency.  It would be interesting to see if speculation could be used to hide the latency of committing durable transactions.  For extra credit, find additional uses for speculation, with or without transactions.

    2) Parallelize apt with transactions (probably easier).
    TxOS currently provides transactional installation of single packages.  Aside from the internal bookkeeping, apt installs rarely touch the same files and could likely be executed concurrently in the common case.  In the uncommon case, two packages may touch the same configuration files or have a dependence that makes parallelization unsafe.  The problem is that this is difficult to reason about.  The safety guarantees of transactions could make this a more realistic option.
    The main focus of the project would be to modify apt to use system transactions in TxOS to parallelize a large software upgrade (like a distribution upgrade).  Ideally, one would understand apt well enough to leverage its internal knowledge of package dependences to make smart choices, such as scheduling dependent packages in the same process or transaction.
    A likely problem may be package database structure introducing false conflicts, and this may require some straightforward modification to the dpkg bookkeeping.
    For the particularly ambitious group, TxOS currently only supports flat nesting, but it might be interesting to experiment with closed nesting to commit the install as one unit but use nested transactions internally for safety.  Implementing closed nesting support could be a sub-project or may become available if a group shows significant progress.

    3) Producer/consumer transactions.
    Consider a user who is downloading music files that must be converted to a format supported by his or her player. When the producer does not easily fit into a UNIX-style pipeline (such as a GUI program), attempts to overlap the conversion with the download creates irritating partially converted files. If the producer and consumer ran in transactions designated as a producer and consumer pair, the system could coordinate the transactions so that the consumer serializes after the producer and waits for the producer, if necessary. Ramadan et al. (PPoPP '09) describe the safety conditions for this sort of transaction coordination, called dependence-awareness. Dependence-aware transactions improve usability by providing a simple way to coordinate data producers and consumers that do not communicate through pipes or sockets.
    A first step in this project would be to implement dependent transactions that allow "cascading aborts."  One might compare the overheads and benefits of using them for simple workloads, and then for pipelined tasks where there is a clear producer/consumer relationship.  A final step would be to implement an implicit pipeline such as the download/post-process pair.  A nice performance result would be the ability to overlap the execution of the post-processing with the download, leveraging multi-core hardware to improve performance.

    4) Large system transactions
    Currently, system transactions are constrained to the size of memory.  A trivial solution for large data writes would be to spill them to swap, but this will likely perform poorly.  A more appealing solution might allocate free disk blocks for data and later update the file system bookkeeping.  The downside to this solution is the risk of complicating the VFS interface.  The goal of the project might be to explore the design tradeoffs between performance of large transactions and introducing complexity into the API.
    One might begin by implementing the simple swap-based solution and then the most straightforward interface to acquiring free blocks.  After measuring this, find ways to refine the performance or reduce the complexity of the interface.  The project should also attempt to compare performance with database systems and BDB, which will likely do better.  An interesting nugget might be the crossover point in terms of data set size where a database outperforms OS transactions.

    5) IPC and transactions (perhaps simpler, but maybe more creative?)
    TxOS currently supports transactional semantics for signals and pipes, but there are other IPC abstractions in Linux.  Essentially, this project is to design transactional semantics for these resources  (mqueue, fifo, etc.) and extend support to them.
    An ideal project would also identify uses for said support or build non-trivial applications that use transactions.

    Ideas (related to Laminar)

    1) Extending Laminar
    Laminar currently supports only labels for each object. Resin (SOSP'09) has shown how a variety of attacks can be prevent by expressing usage restrictions as policies. The idea is simple, attach a policy with each object, and track the flow of the object and the policy. Access checks now depend on the policy that is attached with the object.
    Your task is to extend the Laminar implementation so that it supports policies for each object.

    2) Detecting rootkits
    A number of rootkit attacks are aimed at breaking data structure invariants. However, if you know the invariant then the violation of the invariant is itself a good mechanism to detect rootkits. You can look at a few examples of kernel rootkits in a paper by Baliga et. al (ACSAC'08). Pick any two of the rootkit attacks. Now create a mechanism to detect that attack. For example, you may create a thread that becomes active everytime the particular data structures are modified. The thread then checks if the invariants still hold.
    A harder task is to ensure that the thread performs the checks in isolation. Can you think of an efficient way to ensure this?
    Note: You can take a similar approach for detecting violations of application data structures. You will need to instrument the JVM.

    3) Linux security modules (LSM)
    Linux security modules (LSM) provide a flexible means to implement different security models in Linux. Use LSM to implement the mandatory access control model. You should be able to enforce the Biba
    and La-Padula policies. As a concrete example, your implementation should be able to run a process in a sandbox with access restricted to a few files. Look at Ubuntu AppArmor and Flume (SOSP'07).