Detecting access anomalies in programs with critical sections

Abstract

This paper presents an efficient on-the-fly method for detecting access anomalies in programs that contain critical section coordination. For a large class of programs, a single execution instance is sufficient to determine the existence of an access anomaly for a given input when the proposed method is used. In contrast, for the same class of programs, previous on-the-fly methods for handling critical sections can fail to detect anomalies for a given input, and can require N! execution instances to find an anomaly, where N is the degree of parallelism. An algorithm for statically determining which programs are in this class is described.