<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Publication:
Exploiting synchronization in the analysis of shared-memory asynchronous programs

Loading...
Thumbnail Image

Departments

School / College / Institute

Item type:Organizational Unit,
Item type:Organizational Unit,

Program

Organization Authors

Co-Authors

Emmi, Michael

Date

Language

Embargo Status

N/A

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

As asynchronous programming becomes more mainstream, program analyses capable of automatically uncovering programming errors are increasingly in demand. Since asynchronous program analysis is computationally costly, current approaches sacrifice completeness and focus on limited sets of asynchronous task schedules that are likely to expose programming errors. These approaches are based on parameterized task schedulers, each of which admits schedules which are variations of a default deterministic schedule. By increasing the parameter value, a larger variety of schedules is explored, at a higher cost. The efficacy of these approaches depends largely on the default deterministic scheduler on which varying schedules are fashioned. We find that the limited exploration of asynchronous program behaviors can be made more efficient by designing parameterized schedulers which better match the inherent ordering of program events, e.g., arising from waiting for an asynchronous task to complete. We follow a reduction-based sequentialization" approach to analyzing asynchronous programs, which leverages existing (sequential) program analysis tools by encoding asynchronous program executions, according to a particular scheduler, as the executions of a sequential program. Analysis based on our new scheduler comes at no greater computational cost, and provides strictly greater behavioral coverage than analysis based on existing parameterized schedulers; we validate these claims both conceptually, with complexity and behavioral-inclusion arguments, and empirically, by discovering actual reported bugs faster with smaller parameter values.

Source

Publisher

Association for Computing Machinery

Citation

item.page.haspartof

Source

2014 International SPIN Symposium on Model Checking of Software, SPIN 2014 - Proceedings

item.page.ispartofseries

item.page.edition

DOI

10.1145/2632362.263237

item.page.datauri

item.page.link

Rights

Other

Copyrights Note

Rights and licensing

Other

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators