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

Project List

(Project Assigned: Wednesday, October 6)
(Project Proposal Due: Friday, October 22, noon)
(Midway Interviews: Thursday and Friday, November 11 and 12)
(Draft Report to Referees: Friday, December 10, start of class)
(Referee Reports to Authors: Wednesday, December 15 noon)
(Final Reports Due: Monday, December 20, noon)
(Project Poster Session: Friday, December 13)

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 more people) on the project and report. Special circumstances and explicitly prior permission is required to work by yourself on a project.

Projects

Here are a few project suggestions. Some that I have mentioned in class, plus a few other ideas. I also encourage you to develop an idea of your own (in consultation with me).

(1) Benchmarking a System of Your Own

For your first assignment, you did a series of simple micro-benchmarks. The goal of this assignment is to perform an thorough benchmarking study of some interesting system with which you are involved. As with any real benchmarking study, you will take this in two conceptual pieces:

Macro-benchmarking: In this step, you will try to understand what are the critical performance measures for your system. For example, a database system might use transactions/second, data transfer rates, and transaction latency. You will also look at overall performance measures like CPU utilization and I/O rates.

Micro-benchmarking: Once you have your macro numbers, you then need to explain why your behaves that way. That will require detailed performance measures of parts of your code and the system.

You will need to find tools to help you do this benchmarking. There are some obvious Linu utilities for helping (such as top, and you can also write you own custom tools. Plus there are tools like Intel's highly regarded Vtune product and research tools like HPCToolkit from Rice University.

For your proposal, you will need to select a system, come up with an initial set of benchmarks to collect, and investigate some tools.

(2) More Fuzz Testing of Programs:

Join a distinguished line of CS736 projects! In the past (1990, 1995, 2000, 2006, and most recently just last year), 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. Fuzz testing has become a fundamental technique in both the testing and security communities, and it all started with CS736 projects. Here are a couple of different fuzz projects that you might undertake (you are free to think of others):

A. Comparing the Reliability of GUI-based Programs

We testing X Windows programs back in 1995, Microsoft Windows program in 2000, and MacOS programs in 2006. In each case, the reliability of the programs was terrible. However, we never did a simultaneous test of all three of these platforms. The goal of this project would be to do that comprehensive testing. This is a more aggressive project, so could support 3-4 people (though staying organized with that many people can be a challenge).

As a product of this project, we would like to provide: (1) an update of the tool sets that can be used by other developers, (2) bug reports for the software vendors, and (3) bug fixes for these bugs.

B. Fuzz Testing of Threads

Multi-threaded programming is challenging and bugs in such programs can be the most difficult type to find. While there has been a lot of work in tools for detecting races in such programs, we are going to take a different approach: apply randomness.

The idea is to apply random testing to thread scheduling. The goal of this project is to test multi-threaded programs by randomizing and biasing the thread scheduler. Such randomization and bias has the potential to expose synchronization problems in multi-thread programs. As multi-core processors are increasing the prevalence of multi-threaded programs, such testing only becomes more interesting.

You will have to choose a threading environment, probably pthreads, understand what type of controls an application program has over the scheduling decisions, and how you will manipulate these controls under test. You will also have to choose a set of programs to test and (when you find bugs), identify the causes of the bugs. Note that this debugging step can be quite challenging.

(3) Multiple Condition Variables in Java :

As we discussed in class, Java has the awkward feature that a monitor (synchronized class) can have only one implicitly-declared condition variable. The goal of this assignment is to modify a Java compiler to allow the use of variables explicitly declared to be of type condition.

You will first figure out how to extend the language grammar to support explicit condition variables, including: (1) declaration of this new type of variable, (2) syntax checks to restrict their use to synchronized classes and methods, and (3) explicitly naming the variables to use them.

You will then select an open source Java compiler and figure out how to modify the compiler to allow these declarations and generate the proper byte code. Once you have done that, you will write some sample programs to demonstrate their use.

A working assumption, that you will have to verify, is that the Java Virtual Machine byte code can support these mechanisms without any modification.

(4) Dynamic Instrumentation API:

The Paradyn project has developed a library for the analysis and patching of binary (executable) programs and libraries, for both the executable files and running programs. This library, 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 x86, Power (32 and 63 bit), and ARMv6. 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.

With Dyninst, you can extract structural information such as control flow and call graphs, and identify functions, basic blocks, and instructions. You can instrument code and patch it to change its behavior, either statically (before execution) or dynamically (during execution).

The goal is to choose some analysis, instrumentation, or control task, and build a Dyninst-based tool. The task could be in the area of tracing, program analysis, modeling, cyber-security and forensics, performance profiling, or debugging.

An interesting example of such a project is to build a tool that can perform "hot patching" of a running server. You can check out the example of such a tool in the paper:

Andrew R. Bernat and Barton P. Miller, "Structured Binary Editing with a CFG Transformation Algebra", 19th Working Conference on Reverse Engineering (WCRE), Kingston, Ontario, October 2012.

(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. You will need to describe the basic problem that you will be addressing.

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. Specifically, you will need to describe:

An outline of features that you project will include;
An implementation plan with week-by-week schedule;
An evaluation plan.

Project proposals will typically be three to four pages, formatted the same as you did for the first paper.

It it crucial that you discuss your approach with me before you write your proposal. This will allow you make a quick start.

It is also crucial that you keep to your plan (or even ahead of it); if you try to do all of your project in the last week or two, you will crash and burn.

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.