Program Boosting or Crowd-Sourcing for Correctness
Robert A. Cochran, Benjamin Livshits · 2013
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. In this paper we investigate an approach we call program boosting, which involves crowd-sourcing imperfect solutions to a difficult programming problem from developers and then blending these programs together in a way that improves their correctness. We show how interesting and highly non-trivial tasks such as writing regular exepressions for URLs or email addresses can be effectively crowd-sourced. We demonstrate that carefully blending the crowd-sourced results together consistently produces a boost, yielding results that are better than any of the starting programs. Our experiments on 465 programs show consistent boosts in accuracy and demonstrate that program boosting can be performed at a relatively modest monetary cost. 1.