Program Boosting or Crowd-Sourcing for Correctness

  • Robert Cochran ,
  • Ben Livshits

MSR-TR-2013-94 |

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 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 problem from developers and then blending these programs together in a way that improves correctness.

%While correctness of the resulting (blended) program is a goal, so is its succinctness. While it is possible to crowd-source programs in general-purpose languages such as Java or C, limiting program expressiveness leads to more elegant blending techniques. In this paper we explore blending of regular expressions represented as DFAs.

We show how interesting and highly non-trivial tasks such as writing regexes for URLs 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.