This paper presents a novel analysis framework and algorithm for statically identifying dataraces in multithreaded object-oriented programs. The framework shows how datarace analysis can be formulated as a conjuction of interthread control flow analysis and points-to analysis of thread objects, synchronization objects and access objects. This formulation can be used to identify a spectrum of dataraces depending on the precision of points-to and control flow information received as input. The framework can be used for datarace analysis of programs written in any multithreaded object-oriented language that supports creation of thread objects, monitor-like synchronization of threads via object-based locking, and global memory accesses via static and instrance fields. Our datarace analysis algorithm operates interprocedurally over the interthread call graph (ICG) and extracts ordering information by examining the thread creation sites and the object references used for monitor synchronization. The algroithm computes two classes of data races -- potential (no false negatives) and definite (no false positives). We present experimental results obtained from a preliminary implementatoin of the datarace analysis algorithm in the Jalapeno JVM. The results show that our preliminary implementation can be effective in narrowing down the set of statement pairs that may participate in a datarace. This information could be used in a static analysis tool, or as a filter for reducing the overhead of dynamic datarace detection.
By: Jong-Deok Choi, Alexey Loginov, Vivek Sarkar
Published in: RC22146 in 2001
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .