Fast and accurate static data-race detection for concurrent programs

Vineet Kahlon, Yang Yu, Sriram Sankaranarayanan, Aarti Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

46 Scopus citations

Abstract

We present new techniques for fast, accurate and scalable static data race detection in concurrent programs. Focusing our analysis on Linux device drivers allowed us to identify the unique challenges posed by debugging largescale real-life code and also pinpointed drawbacks in existing race warning generation 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 first and most crucial step is the automatic discovery of shared variables. Towards that end, we present a new, efficient dataflow algorithm for shared variable detection which is more effective than existing correlation-based techniques that failed to detect the shared variables responsible for data races in majority of the drivers in our benchmark suite. Secondly, accuracy of race warning generation strongly hinges on the precision of the pointer analysis used to compute aliases for lock pointers. We formulate a new scalable context sensitive alias analysis that effectively combines a divide and conquer strategy with function summarization and is demonstrably more efficient 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.

Original languageEnglish (US)
Title of host publicationComputer Aided Verification - 19th International Conference, CAV 2007, Proceedings
Pages226-239
Number of pages14
StatePublished - Dec 1 2007
Externally publishedYes
Event19th International Conference on Computer Aided Verification, CAV 2007 - Berlin, Germany
Duration: Jul 3 2007Jul 7 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4590 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other19th International Conference on Computer Aided Verification, CAV 2007
CountryGermany
CityBerlin
Period7/3/077/7/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fast and accurate static data-race detection for concurrent programs'. Together they form a unique fingerprint.

  • Cite this

    Kahlon, V., Yu, Y., Sankaranarayanan, S., & Gupta, A. (2007). Fast and accurate static data-race detection for concurrent programs. In Computer Aided Verification - 19th International Conference, CAV 2007, Proceedings (pp. 226-239). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4590 LNCS).