Binary Fission: Crowdsourcing the Logic of Code via Gamified Classification

TL;DR

Finding program invariants is a notorious bottleneck in software verification. Binary Fission turns this "math problem" into a "game problem." By tasking non-expert players to separate "good" and "bad" program states in a graphical interface, the researchers successfully crowdsourced valid, human-readable program preconditions for a critical aircraft collision system (TCAS)—achieving results that fully automated machine learning tools (like DTinv) missed due to overfitting.

The "Infinite Search" Problem

In formal verification, we need a precondition: a logical statement that, if true at the start of a function, guarantees the code won't crash later.

The problem? The space of possible logical formulas is effectively infinite. Automated tools often take a "brute force" or "greedy" approach, resulting in "likely invariants" that are brittle. They might work for the specific data points provided but fail the second they encounter a new scenario. This is the classic Overfitting trap.

Methodology: Logic as a Game of "Quarks"

Binary Fission strips away the code and replaces it with a physics-inspired metaphor:

• Program States are Quarks: Blue for "good" states (normal execution) and Gold for "bad" states (assertion violations).
• Predicates are Filters: Logical conditions (e.g., Altitude > 1000) act as filters that split the nucleus of quarks.
• The Goal: Build a decision tree that isolates pure nodes of blue quarks.

The Secret Sauce: Scoring for Generality

The game isn't just a UI wrapper; it's a constrained search engine. The scoring function: $Score=Nimes\sum (purit{y}_i^{A}imessiz{e}_i^B)$ By rewarding purity (how well a node separates gold from blue) and penalizing depth, the game encourages players to find the simplest and strongest logical statements—which are exactly the kind of general preconditions verification experts look for.

Figure 1: The Binary Fission interface where players apply filters to separate quarks.

Experiments: Humans vs. Machines

The researchers tested Binary Fission on TCAS (Traffic Alert and Collision Avoidance System), a standard benchmark in the verification community.

Key Comparison: Binary Fission vs. DTinv

• Automated SOTA (DTinv): Produced massive decision trees (depth 15) with 65+ predicates. When plugged into the CBMC model checker, zero of its outputs were valid preconditions. It had "overfit" the training samples with complex numeric thresholds.
• The Crowd (Binary Fission): Players, unaware of the underlying physics of aircraft collision, found valid preconditions for 6 out of 7 tasks. These expressions were concise, typically involving only 2-3 variables.

Figure 2: Statistical progress showing how 20% of the crowd's solutions cover 80% of the possible "truth" in the program state space.

Depth Insight: Why the Crowd Wins

The "Wisdom of the Crowd" here isn't just about volume; it's about Inductive Bias.

1. Non-Greedy Search: Unlike algorithms that make the best local split (greedy), humans explore "idiosyncratic" paths, finding global patterns that automated scorers might ignore.
2. Breadth over Depth: The game's 5-level depth limit essentially acts as a Regularization technique, preventing the hyper-specific, multi-clause logical messes that machines tend to generate.
3. Human Readability: Because the primitives come from Daikon (structured relations), and the trees are shallow, the resulting logic (e.g., Other_Tracked_Alt > Own_Tracked_Alt) is intuitive and useful for human developers.

Conclusion & Future Outlook

Binary Fission proves that you don't need a PhD in Formal Methods to verify safety-critical software. By abstracting logic into visual classification, the researchers opened the door to Crowdsourced Formal Verification (CSFV).

While this study focused on relatively simple arithmetic code (TCAS), the implication is profound: for the millions of programs needing verification, the bottleneck isn't just CPU cycles—it's the lack of human-like "gut feeling" for what makes a general rule. Games like Binary Fission might just bridge that gap.

Limitations

• Predicate Discovery: The game still relies on Daikon to provide the "candidate" predicates. If the necessary logic isn't in the provided pool, the crowd cannot find it.
• Complexity: Can this scale to programs with complex pointers or recursive data structures? That remains the frontier for the next generation of "Software Verification Games."