PENELOPE: Weaving threads to expose atomicity violations

Francesco Sorrentino, Azadeh Farzan, P. Madhusudan

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

Abstract

Testing concurrent programs is challenged by the interleaving explosion problem - - the problem of exploring the large number of interleavings a program exhibits, even under a single test input. Rather than try all interleavings, we propose to test wisely: to exercise only those schedules that lead to interleavings that are typical error patterns. In particular, in this paper we select schedules that exercise patterns of interaction that correspond to atomicity violations. Given an execution of a program under a test harness, our technique is to algorithmically mine from the execution a small set of alternate schedules that cause atomicity violations. The program is then re-executed under these predicted atomicity-violating schedules, and verified by the test harness. The salient feature of our tool is the efficient algorithmic prediction and synthesis of alternate schedules that cover all possible atomicity violations at program locations. We implement the tool PENELOPE that realizes this testing framework and show that the monitoring, prediction, and rescheduling (with precise repro) are efficient and effective in finding bugs related to atomicity violations.

Original languageEnglish (US)
Title of host publicationProceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE-18
Pages37-46
Number of pages10
DOIs
StatePublished - Dec 1 2010
Event18th ACM SIGSOFT International Symposium on the Foundations of Software Engineering, FSE-18 - Santa Fe, NM, United States
Duration: Nov 7 2010Nov 11 2010

Publication series

NameProceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering

Other

Other18th ACM SIGSOFT International Symposium on the Foundations of Software Engineering, FSE-18
Country/TerritoryUnited States
CitySanta Fe, NM
Period11/7/1011/11/10

Keywords

  • atomicity violation
  • concurrency
  • dynamic analysis
  • predictive analysis
  • schedule selection
  • testing

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'PENELOPE: Weaving threads to expose atomicity violations'. Together they form a unique fingerprint.

Cite this