Peter Ohmann

Program coverage customization selectively adds instrumentation to a compiled computer program so that a limited amount of directly observed data can be used to infer other program coverage information after a run. A good instrumentation plan can reduce run-time overheads while still giving software developers the information they need. Unfortunately, optimal coverage planning is NP-hard, limiting either the quality of heuristic plans or the sizes of programs that can be instrumented optimally. We exploit the monotonicity property of feasible instrumentations to formulate this problem as an intraprocedural set covering problem. Our formulation has an exponential number of constraints, and we design a polynomial-time separation algorithm to incrementally add the necessary subset of these inequalities. Our approach reduces expected run-time probing costs compared with existing methods, offers a guarantee of the optimality of the instrumentation, and has compilation-time overhead suitable for wide practical use.

Assessment of student knowledge is a crucial and challenging part of course design. Especially in computer science courses in the United States, written examinations are very common. While written exams offer a number of advantages in convenience and familiarity, they are also inflexible and prone to question misinterpretation. In contrast to written tests, oral exams offer the prospect of an interactive conversation where students can express their knowledge in a variety of ways while asking clarifying questions.

In this paper, we present and assess our implementation of oral exams in an introductory computer science course. We describe the motivation for and resulting features of our design, including a simplified rubric style for equitable, on-the-fly grading. We also perform an assessment relative to more traditional written exams. We find the time commitment for instructors to be manageable and comparable to traditional exams. Through post-semester surveys, students self-report spending slightly more time studying for oral exams, but rate the difficulty as similar to written exams. Both qualitative and quantitative student feedback indicates that oral exams can be effective and well-received.

Debugging is difficult. When software fails in production, debugging is even harder, as failure reports usually provide only an incomplete picture of the failing execution. We present a system that answers control-flow queries posed by developers as formal languages, indicating whether the query expresses control flow that is possible or impossible for a given failure report. We consider three separate approaches that trade off precision, expressiveness for failure constraints, and scalability. We also introduce a new subclass of regular languages, the unreliable trace languages, which are particularly suited to answering control-flow queries in polynomial time. Our system answers queries remarkably efficiently when we encode failure constraints and user queries entirely as unreliable trace languages.

See also our accompanying technical report.

This is an extended journal version of our ASE 2013 paper which was awarded an ACM SIGSOFT Distinguished Paper Award.

Debugging is difficult and costly. As a human programmer looks for a bug, it would be helpful to see a complete trace of events leading to the point of failure. Unfortunately, full tracing is simply too slow to use after deployment, and may even be impractical during testing.

We aid post-deployment debugging by giving programmers additional information about program activity shortly before failure. We use latent information in post-failure memory dumps, augmented by low-overhead, tunable run-time tracing. Our results with a realistically-tuned tracing scheme show low enough overhead (0–5%) to be used in production runs. We demonstrate several potential uses of this enhanced information, including a novel postmortem static slice restriction technique and a reduced view of potentially-executed code. Experimental evaluation shows our approach to be very effective. For example, our analyses shrink interprocedural static slices by 53–78% in larger applications.