CS380L: Advanced Operating
Assignment #3 Proposal
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
to pursue an OS topic or subsystem that interests you.
The goal of the first part of this assignment then, is to identify
what you will be doing for the rest of the assignment.
Unless you have made other arrangements, you should focus on working
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,
A brief plan on how you will
be evaluating your driver's
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 &
(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
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
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
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
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
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
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
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
be able to run a process in a sandbox with access restricted to a few
Look at Ubuntu AppArmor and Flume (SOSP'07).