Abstracts for Alexander Aiken

The EECS Research Summary for 2003


Distributed Program Sampling

Ben Liblit and Alice Zheng
(Professor Alexander Aiken)
(DOE) W-7405-ENG-48, (NASA) NAG2-1210, (NSF) EIA-9802069, (NSF) CCR-0085949, and (NSF) ACI-9619020

We propose a sampling infrastructure for gathering information about software from the set of runs experienced by its user community. We show how to gather random samples with very low overhead for users, and we also show how to make use of the information we gather. We present two example applications: sharing the overhead of assertions, and using statistical analysis of a large number of sampled runs to help isolate the location of a bug.

[1]
B. Liblit, A. Aiken, and A. X. Zheng, "Distributed Program Sampling" (in preparation).

More information (http://www.cs.berkeley.edu/~liblit/distributed-sampling/) or

Send mail to the author : (liblit@eecs.berkeley.edu)

Building a Better Backtrace: Techniques for Postmortem Program Analysis

Ben Liblit
(Professor Alexander Aiken)
(NASA) NAG2-1210, (NSF) EIA-9802069, and (NSF) CCR-0085949

After a program has crashed, it can be difficult to reconstruct why the failure occurred, or what actions led to the error. We propose a family of analysis techniques that use the evidence left behind by a failed program to build a time line of its possible actions from launch through termination. Our design can operate with zero run time instrumentation, or can flexibly incorporate a wide variety of artifacts such as stack traces and event logs for increased precision. Efficient demand-driven algorithms are provided, and the approach is well suited for incorporation into interactive debugging support tools.

[1]
B. Liblit and A. Aiken, Building a Better Backtrace: Techniques for Postmortem Program Analysis, UC Berkeley Computer Science Division, Report No. UCB/CSD 02/1203, October 2002.

More information (http://www.cs.berkeley.edu/~liblit/better-backtrace/) or

Send mail to the author : (liblit@eecs.berkeley.edu)

Implementing Type-Inference-based Deforestation

Kirsten Chevalier
(Professor Alexander Aiken)
NSF Graduate Research Fellowship

Many lazy functional programs are modular collections of small functions that communicate via tree-like data structures. The advantages of this style include expressiveness and readability [1], but its disadvantage is inefficiency: lazy functional programs often use more time and space than equivalent imperative programs, partly due to the overhead of creating and destroying intermediate data structures. Deforestation is a program transformation that eliminates intermediate trees [2].

A particular strategy is shortcut deforestation, which exploits a simple programming pattern [3]. Using this pattern forces programmers to clutter their code with hints to the deforestation engine. Type-inference-based deforestation [4] builds on shortcut deforestation and removes the need for these annotations, making deforestation applicable to programs written without deforestation in mind. I am currently completing my implementation of type-inference-based deforestation for Haskell programs. Once it is finished, I plan to analyze the performance of type-inference-based deforestation on various benchmarks and compare its performance with that of other deforestation techniques.

A better practical understanding of deforestation will further the goal of making lazy functional programming languages useful for real-world applications, thus narrowing the gulf that exists between languages that can be efficiently compiled and languages that allow programmers to concisely express ideas.

[1]
J. Hughes, "Why Functional Programming Matters," Computer Journal, Vol. 32, No. 2, 1989.
[2]
P. Wadler, "Deforestation: Transforming Programs to Eliminate Trees," Theoretical Computer Science, Vol. 73, 1990.
[3]
A. Gill, J. Launchbury, and S. Peyton Jones, "A Short Cut to Deforestation," Proc. Conf. Functional Programming Languages and Computer Architecture, 1993.
[4]
O. Chitil, "Type Inference Builds a Short Cut to Deforestation," Proc. ACM SIGPLAN Int. Conf. Functional Programming, 1999.

Send mail to the author : (krc@uclink.berkeley.edu)

Proving Safety of Array Accesses in C Programs

Simon Goldsmith
(Professor Alexander Aiken)

Writing outside the bounds of arrays causes security problems and memory corruption bugs in C programs. CCured is a system that addresses this class of bugs by guarding potentially unsafe memory accesses with run-time safety checks. In the presence of these checks, buffer overruns and insidious memory corruption bugs become simple crashes. The cost of these checks is decreased performance. Our research uses a flow sensitive type-inference system to prove statically that some of the array bound checks inserted by CCured will always succeed and thus can be eliminated. Future work may investigate using our type-inference system as a tool to find array access bugs statically.


Send mail to the author : (sfg@eecs.berkeley.edu)