Efficient synthesis for concurrency by semantics-preserving transformations

Cerny, Pavol; Henzinger, Thomas A; Radhakrishna, Arjun; Ryzhyk, Leonid; Tarrach, Thorsten

Efficient synthesis for concurrency by semantics-preserving transformations

Cerny P, Henzinger TA, Radhakrishna A, Ryzhyk L, Tarrach T. 2013. Efficient synthesis for concurrency by semantics-preserving transformations. CAV: Computer Aided Verification, LNCS, vol. 8044, 951–967.

Download

IST-2014-199-v1+1_cav2013-final.pdf 365.55 KB [Submitted Version]

DOI

10.1007/978-3-642-39799-8_68

Conference Paper | Published | English

Scopus indexed

Author

Cerny, Pavol^ISTA; Henzinger, Thomas A^ISTA ; Radhakrishna, Arjun^ISTA; Ryzhyk, Leonid; Tarrach, Thorsten^ISTA

Department

Henzinger_Thomas Group

Grant

Quantitative Reactive Modeling
Rigorous Systems Engineering

Series Title

LNCS

Abstract

We develop program synthesis techniques that can help programmers fix concurrency-related bugs. We make two new contributions to synthesis for concurrency, the first improving the efficiency of the synthesized code, and the second improving the efficiency of the synthesis procedure itself. The first contribution is to have the synthesis procedure explore a variety of (sequential) semantics-preserving program transformations. Classically, only one such transformation has been considered, namely, the insertion of synchronization primitives (such as locks). Based on common manual bug-fixing techniques used by Linux device-driver developers, we explore additional, more efficient transformations, such as the reordering of independent instructions. The second contribution is to speed up the counterexample-guided removal of concurrency bugs within the synthesis procedure by considering partial-order traces (instead of linear traces) as counterexamples. A partial-order error trace represents a set of linear (interleaved) traces of a concurrent program all of which lead to the same error. By eliminating a partial-order error trace, we eliminate in a single iteration of the synthesis procedure all linearizations of the partial-order trace. We evaluated our techniques on several simplified examples of real concurrency bugs that occurred in Linux device drivers.

Publishing Year

2013

Date Published

2013-07-01

Publisher

Springer

Volume

8044

Page

951 - 967

Conference

CAV: Computer Aided Verification

Conference Location

St. Petersburg, Russia

Conference Date

2013-07-13 – 2013-07-19

IST-REx-ID

2445

Cite this

Cerny P, Henzinger TA, Radhakrishna A, Ryzhyk L, Tarrach T. Efficient synthesis for concurrency by semantics-preserving transformations. In: Vol 8044. Springer; 2013:951-967. doi:10.1007/978-3-642-39799-8_68

Cerny, P., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., & Tarrach, T. (2013). Efficient synthesis for concurrency by semantics-preserving transformations (Vol. 8044, pp. 951–967). Presented at the CAV: Computer Aided Verification, St. Petersburg, Russia: Springer. https://doi.org/10.1007/978-3-642-39799-8_68

Cerny, Pavol, Thomas A Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, and Thorsten Tarrach. “Efficient Synthesis for Concurrency by Semantics-Preserving Transformations,” 8044:951–67. Springer, 2013. https://doi.org/10.1007/978-3-642-39799-8_68.

P. Cerny, T. A. Henzinger, A. Radhakrishna, L. Ryzhyk, and T. Tarrach, “Efficient synthesis for concurrency by semantics-preserving transformations,” presented at the CAV: Computer Aided Verification, St. Petersburg, Russia, 2013, vol. 8044, pp. 951–967.

Cerny, Pavol, et al. Efficient Synthesis for Concurrency by Semantics-Preserving Transformations. Vol. 8044, Springer, 2013, pp. 951–67, doi:10.1007/978-3-642-39799-8_68.

All files available under the following license(s):

Copyright Statement: