	UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
CS 736 Fall 2005		Barton Miller

Project List

(Project Assigned: Thursday, October 10)
(Project Proposal Due: Monday, October 24, 3pm)
(Midway Interviews: Friday, November 18)
(Draft Report to Referees: Friday, December 9, in class)
(Referee Reports to Authors: Wednesday, December 14)
(Final Report Due: Tuesday, December 20)
(Project Presentation Session: Tuesday, December 20, time TBA)

General Comments

The projects are intended to give you an opportunity to study a particular area related to operating systems. Your project will require a test implementation, measurement study or analysis, literature search, and evaluation.

The project suggestions below are briefly stated. They are intended to guide you into particular areas and you are expected to expand these suggestions into a full project descriptions. This gives you more freedom in selecting an area and more burden in defining your own project. There may be more issues listed for a project than you can cover. If you have a topic of your own that is not listed below, you should come and talk with me so we can work out a reasonable project description.

You will write a paper that reports on your project. This paper will structured as if you were going to submit it to a conference. I will provide more details on the project report later in the semester.

You should work in teams of two people (and, in certain cases three people) on the project and report.

Projects

Here are a few project suggestions. I have mentioned other ideas in class and I encourage you to develop an idea of your own.

(1) Kernel Profiling Revisited:

In your first paper assignment, you profiled some basic kernel operations, including simple kernel calls and interprocess communication. For several of these operations, you had behaviors that could not be explained easily with the techniques at your disposal. The goal of this project is to explore, in depth, the cause of your performance results. One tool that can help you with this effort is Kerninst.

The preferred platform for this study is IA32/Linux, using the machines in the Crash and Burn Lab.

(2) Dynamic Instrumentation API:

The Paradyn project has developed a library for patching code into running programs. This interface, called the DynInst API, allows programmers to write tools that can patch code into unmodified programs in a machine-independent way. So, a tool that uses DynInst can work on SPARC, IA32, IA64, Power, AMD64, and Alpha. Many simple tools have been built using DynInst for tracing and debugging, and more complex tools for doing such things as checkpointing and process migration.

One idea for a project involves Security Avoidance. Software vendors often want to control access to a piece of software, with the goal of charging the user for each copy. To this end, many programs require a license key, either stored in a file or distributed from license servers. When you first start an application program, it will obtain the license to see if you have permission to run the program. Previous students have successfully used dyninst to bypass obtaining a license from a server. The goal of this project is to attempt this operation for programs that store their licenses locally. We will discuss a list of possible programs that might be appropriate.

(3) Random Testing of Programs:

Join a distinguished line of CS736 projects! In the past (1990, 1995, and 2000), we have used random input to test the reliability of application programs on UNIX and NT. These techniques have been quite effective in finding bugs, and have been widely cited; this work has become almost a cult in itself.

The goal of this project is to take the 1995 study of applications on various platforms and repeat the study on command-line and X-window applications. Especially interesting would be to compare the various free/open UNIX systems such as Linux, BSDi, and freeBSD). Testing MacOS X is another possibility. As a product of this project, we would like to provide: (1) an update of the tool set that can be used by other developers, (2) bug reports for the software vendors, and (3) bug fixes for these bugs.

(4) Visualizing File System Layout: (thanks to Andrea Arpaci-Dusseau)

A file system can be viewed as a large, complex data structure (i.e., consisting of a superblock, i-nodes, indirect blocks, and data blocks). In this project, you will investigate how the layout of a local file system can be visualized. This will involve understanding the file system data structures of a particular OS (e.g., Linux or Windows), traversing those structures by reading from the raw disk device, determining what information is interesting, and innovating in how to display this complex information simply.

You may want to show which blocks on disk are dedicated to i-nodes vs. data blocks vs. unallocated, the layout of individual files across the disk (i.e., the amount of fragmentation), and the age of each block. In addition, you will want to present quantitative information about such things as grouping and fragmentation.

(5) Windows vs. Unix File System Performance:

NTFS and the Unix FFS are both designed to provide good performance. However each file system has been optimized to be good at different things. The goal of this project is to do a side-by-side comparison of the basic on-disk structures, performance strategies (e.g., memory caching of data and meta-data, pre-fetching, replication), and generate workloads to tests these features.

Project Proposal

The project descriptions listed above a intentionally brief. You will need to expand and refine these to develop your own project. Different groups may choose the same topic, but have significantly different emphases.

Your project proposal will describe your goals, methods, implementation outline, evaluation criteria, and resources needed. First, you should describe the basic problem that you will be addressing. Next, you should provide a more detailed description of how you will approach the problem. This description should be contain much more detail than the brief paragraphs given above. You will provide an outline of features that you project will include, an implementation plan, and an evaluation plan.

Project proposals will typically be 3 to 4 double-spaced pages.

Referee Report

Each of you will referee the paper from another group. I am providing you with a sample referee report form, that is similar to one that I used for a recent conference. I am also providing you with two sample referee reports, to give you an idea of what might appear in a real report.

In general, a referee report starts with a summary of the main idea(s) in the paper, and then has an overall statement of the quality. You should then review the main technical ideas. In addition, either a marked-up copy of the paper, with typos and related errors, or a summary of typos and related errors should be given to the authors.