Locking discipline inference and checking

Download: PDF, slides (PDF), slides (PowerPoint), checking implementation.

“Locking discipline inference and checking” by Michael D. Ernst, Alberto Lovato, Damiano Macedonio, Fausto Spoto, and Javier Thaine. In ICSE'16, Proceedings of the 38th International Conference on Software Engineering, (Austin, TX, USA), May 18-20, 2016.
A previous version appeared as University of Washington Department of Computer Science and Engineering technical report UW-CSE-15-09-02, (Seattle, WA, USA), Sep. 2015.

Abstract

Concurrency is a requirement for much modern software, but the implementation of multithreaded algorithms comes at the risk of errors such as data races. Programmers can prevent data races by documenting and obeying a locking discipline, which indicates which locks must be held in order to access which data.

This paper introduces a formal semantics for locking specifications that gives a guarantee of race freedom. A notable difference from most other semantics is that it is in terms of values (which is what the runtime system locks) rather than variables. The paper also shows how to express the formal semantics in two different styles of analysis: abstract interpretation and type theory. We have implemented both analyses, in tools that operate on Java. To the best of our knowledge, these are the first tools that can soundly infer and check a locking discipline for Java. Our experiments compare the implementations with one another and with annotations written by programmers, showing that the ambiguities and unsoundness of previous formulations are a problem in practice.

Download: PDF, slides (PDF), slides (PowerPoint), checking implementation.

BibTeX entry:

@inproceedings{ErnstLMST2016,
   author = {Michael D. Ernst and Alberto Lovato and Damiano Macedonio and
	Fausto Spoto and Javier Thaine},
   title = {Locking discipline inference and checking},
   booktitle = {ICSE'16, Proceedings of the 38th International Conference
	on Software Engineering},
   address = {Austin, TX, USA},
   month = {May~18--20,},
   year = {2016}
}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.