Data race detection on compressed traces

Dileep Kini, Umang Mathur, Mahesh Viswanathan

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

Abstract

We consider the problem of detecting data races in program traces that have been compressed using straight line programs (SLP), which are special context-free grammars that generate exactly one string, namely the trace that they represent. We consider two classical approaches to race detection D using the happens-before relation and the lockset discipline. We present algorithms for both these methods that run in time that is linear in the size of the compressed, SLP representation. Typical program executions almost always exhibit patterns that lead to significant compression. Thus, our algorithms are expected to result in large speedups when compared with analyzing the uncompressed trace. Our experimental evaluation of these new algorithms on standard benchmarks confirms this observation.

Original languageEnglish (US)
Title of host publicationESEC/FSE 2018 - Proceedings of the 2018 26th ACM Joint Meeting on European So ftware Engineering Conference and Symposium on the Foundations of So ftware Engineering
EditorsAlessandro Garci, Corina S. Pasareanu, Gary T. Leavens
PublisherAssociation for Computing Machinery, Inc
Pages26-37
Number of pages12
ISBN (Electronic)9781450355735
DOIs
StatePublished - Oct 26 2018
Event26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2018 - Lake Buena Vista, United States
Duration: Nov 4 2018Nov 9 2018

Publication series

NameESEC/FSE 2018 - Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Other

Other26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2018
CountryUnited States
CityLake Buena Vista
Period11/4/1811/9/18

Keywords

  • Compression
  • Dynamic Program Analysis
  • Race Detection

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Data race detection on compressed traces'. Together they form a unique fingerprint.

Cite this