Fast and Accurate Static Data-Race Detection for Concurrent Programs

Abstract. We present new techniques for fast, accurate and scalable static race detection in concurrent programs. Focusing our analysis on Linux device drivers allowed us to identify the unique challenges posed by debugging large-scale real-life code and also pinpointed drawbacks in existing race warning genera-tion methods. This motivated the development of new techniques that helped us in improving both the scalability as well as the accuracy of each of the three main steps in a race warning generation system. The rst and most crucial step in data race detection is automatic shared variable discovery. Towards that end, we present a new, efcient dataow algorithm for shared variable detection which is more effective than existing correlation-based techniques that failed to detect shared variables responsible for data races in majority of the drivers in our bench-mark suite. Secondly, accuracy of race warning generation strongly hinges on the accuracy of the pointer analysis used to compute aliases for lock pointers. We for-mulate a new scalable context sensitive alias analysis that effectively combines a divide and conquer strategy with function summarization and is demonstra-bly more efcient than existing BDD-based techniques. Finally, we provide a new warning reduction technique that leverages lock acquisition patterns to yield provably better warning reduction than existing lockset based methods.