Program Boosting: Program Synthesis via Crowd-Sourcing - Cochran, Robert A; D’Antoni, Loris; Livshits, Ben; Molnar, David; Veanes, Margus (Symposium on the Principles of Programming Languages (POPL), 2015)
A great deal of effort has been spent on both trying to specify software requirements and on ensuring that software actually matches these requirements. A wide range of techniques that includes theorem proving, model checking, type-based analysis, static analysis, runtime monitoring, and the like have been proposed. However, in many areas adoption of these techniques remains spotty. In fact, obtaining a specification or a precise notion of correctness is in many cases quite elusive. For many programming tasks, even expert developers are unable to get them right because of numerous tricky corner cases. In this paper we investigate an approach we call program boosting, which involves crowd-sourcing partially correct solutions to a tricky programming problem from developers and then blending these programs together in a way that improves correctness. We show how interesting and highly non-trivial programming tasks such as writing regular expressions to match URLs and email addresses can be effectively crowd-sourced. We demonstrate that carefully blending the crowd-sourced results together frequently yields results that are better than any of the individual responses. Our experiments on 465 of programs show consistent boosts in accuracy and demonstrate that program boosting can be performed at a relatively modest monetary cost.