Reducing the barriers to writing verified specifications

Download: PDF, slides (PDF), study materials.

“Reducing the barriers to writing verified specifications” by Todd W. Schiller and Michael D. Ernst. In OOPSLA 2012, Object-Oriented Programming Systems, Languages, and Applications, (Tucson, AZ, USA), Oct. 2012, pp. 95-112.

Abstract

Formally verifying a program requires significant skill not only because of complex interactions between program subcomponents, but also because of deficiencies in current verification interfaces. These skill barriers make verification economically unattractive by preventing the use of less-skilled (less-expensive) workers and distributed workflows (i.e., crowdsourcing).

This paper presents VeriWeb, a web-based IDE for verification that decomposes the task of writing verifiable specifications into manageable subproblems. To overcome the information loss caused by task decomposition, and to reduce the skill required to verify a program, VeriWeb incorporates several innovative user interface features: drag and drop condition construction, concrete counterexamples, and specification inlining.

To evaluate VeriWeb, we performed three experiments. First, we show that VeriWeb lowers the time and monetary cost of verification by performing a comparative study of VeriWeb and a traditional tool using 14 paid subjects contracted hourly from Exhedra Solution's vWorker online marketplace. Second, we demonstrate the dearth and insufficiency of current ad-hoc labor marketplaces for verification by recruiting workers from Amazon's Mechanical Turk to perform verification with VeriWeb. Finally, we characterize the minimal communication overhead incurred when VeriWeb is used collaboratively by observing two pairs of developers each use the tool simultaneously to verify a single program.

Download: PDF, slides (PDF), study materials.

BibTeX entry:

@inproceedings{SchillerE2012,
   author = {Todd W. Schiller and Michael D. Ernst},
   title = {Reducing the barriers to writing verified specifications},
   booktitle = {OOPSLA 2012, Object-Oriented Programming Systems,
	Languages, and Applications},
   pages = {95--112},
   address = {Tucson, AZ, USA},
   month = oct,
   year = {2012}
}

Back to Publications whose methodology uses invariant detection.