Finding schedule-sensitive branches

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

Abstract

This paper presents an automated, precise technique, TAME, for identifying schedule-sensitive branches (SSBs) in con- current programs, i.e., branches whose decision may vary depending on the actual scheduling of concurrent threads. The technique consists of 1) tracing events at fine-grained level; 2) deriving the constraints for each branch; and 3) invoking an SMT solver to find possible SSB, by trying to solve the negated branch condition. To handle the infeasibly huge number of computations that would be generated by the fine-grained tracing, TAME leverages concolic execution and implements several sound approximations to delimit the number of traces to analyse, yet without sacrificing precision. In addition, TAME implements a novel distributed trace partition approach distributing the analysis into smaller chunks. Evaluation on both popular bench- marks and real applications shows that TAME is effective in finding SSBs and has good scalability. TAME found a total of 34 SSBs, among which 17 are related to concurrency errors, and 9 are ad hoc synchronizations.

Original languageEnglish (US)
Title of host publication2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015 - Proceedings
PublisherAssociation for Computing Machinery, Inc
Pages439-449
Number of pages11
ISBN (Electronic)9781450336758
DOIs
StatePublished - Aug 30 2015
Externally publishedYes
Event10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015 - Bergamo, Italy
Duration: Aug 30 2015Sep 4 2015

Publication series

Name2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015 - Proceedings

Other

Other10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015
CountryItaly
CityBergamo
Period8/30/159/4/15

Keywords

  • Schedule-sensitive branches
  • Symbolic constraint analysis

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Finding schedule-sensitive branches'. Together they form a unique fingerprint.

  • Cite this

    Huang, J., & Rauchwerger, L. (2015). Finding schedule-sensitive branches. In 2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015 - Proceedings (pp. 439-449). (2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015 - Proceedings). Association for Computing Machinery, Inc. https://doi.org/10.1145/2786805.2786840