Report Number: CSL-TR-89-395
Institution: Stanford University, Computer Systems Laboratory
Title: Design of Run Time Monitors for Concurrent Programs
Author: Helmbold, David
Author: Bryan, Doug
Date: October 1989
Abstract: We address the problem of correctly monitoring the run time behavior of a concurrent program. We view a program as having three (potentially different) sets of behavior: computations of the original program when monitoring is not performed, computations after the monitor is added to the program, and "observations'' produced by the monitor. Using these sets of behaviors, we define four properties of monitor systems: non-interference, safety, accuracy and correctness. We define both a minimal level and a total level for each of these properties. The non-interference and safety properties address the degree to which the presence of the monitor alters a computation (the differences between the first two sets of computations). Accuracy is a relationship between a monitored computation and the observation of the computation produced by the monitor. Correctness is a relationship between observations and the unmonitored computations. A run time monitor for TSL-1 and Ada has been implemented. This monitor system uses two techniques for constructing the observation. We show that any monitoring system using these two techniques is at least minimally correct, from which the (minimal) correctness of the TSL-1 monitor follows.