Toward Neural-Network-Guided Program Synthesis and Verification

Naoki Kobayashi, Taro Sekiyama, Issei Sato, Hiroshi Unno

TL;DR

This paper introduces a "gray-box" approach to program synthesis, where neural networks are trained to classify data and then "interrogated" to reveal the underlying logical formulas. By extracting integer-based inequalities directly from the weights of a trained network, the authors can synthesize complex program invariants and fill "holes" in code sketches more effectively than traditional black-box or purely symbolic methods.

What Problem Does This Paper Address?

In the world of formal methods, two of the biggest challenges are program synthesis (automatically writing code that meets a spec) and verification (proving that code is correct). A central bottleneck in both is finding the right "qualifiers"—the basic building blocks of logic, like x + y > 5.

If you are trying to find a loop invariant (a logical statement that stays true throughout a loop), the search space is infinite. Traditional tools often rely on "templates" or simple brute-force enumeration, which fail when the required logic is complex or non-linear. Machine learning seems like a natural fit for finding patterns, but neural networks (NNs) are usually "black boxes"—they might learn the pattern, but they can't tell you the logical formula they used to get there.

Methods

The authors propose a hybrid framework called NeuGuS (Neural-Network-Guided Synthesis). It treats the neural network as a gray box:

  1. NN Training: They use a four-layer neural network. The network is trained on positive and negative examples (e.g., states where a program is safe vs. unsafe). Crucially, they use the sigmoid activation function. Because sigmoid outputs are very close to 0 or 1, it forces the hidden nodes to act like logical step functions.
  2. Qualifier Extraction: Instead of just using the NN to predict values, they look at the weights and biases of the first hidden layer. They use a mathematical technique (inspired by Diophantine approximation) to convert the floating-point weights into clean integer coefficients. For example, a weight of 0.333 might be extracted as the fraction 1/3.
  3. Formula Synthesis: Once they have a pool of candidate inequalities (qualifiers) from the NN, they use a classical logic algorithm (like Quine-McCluskey) to find the best Boolean combination (ANDs and ORs) that fits the data.
  4. Handling Implications: The method is extended to handle "implication constraints" ($A \Rightarrow B$), which are vital for finding inductive invariants in program verification.

Datasets

The authors evaluated their tool using several sets of problems:

  • Synthetic Arithmetic: Randomly generated linear and quadratic formulas (e.g., $(2x + y > 0 \land x - y > 9) \lor \dots$) to test the tool's ability to recover known logic.
  • CHC Benchmarks: 123 problems from the code2inv set and benchmarks from the SyGuS 2018 competition. These are standard "Constrained Horn Clause" problems used to test industrial-strength verification tools.
  • Oracle-based Programming: Higher-order program verification tasks, including a version of McCarthy’s famous "91 function."

Key Insights and Ideas

  • The "Gray Box" Philosophy: The authors realized that NNs are excellent at finding the "boundaries" of a problem, but poor at being precise. By using the NN only to find the qualifiers and letting a classical symbolic solver handle the Boolean logic, they get the best of both worlds: the search power of ML and the interpretability of formal logic.
  • Sigmoid is a Logic Gate: While ReLU is the standard in modern AI, the authors found that Sigmoid is superior for synthesis. Its "S-curve" naturally mimics the transition from false to true, making it easier to extract sharp logical boundaries from the weights.
  • Prioritization: Not all hidden nodes are useful. The authors developed a way to rank qualifiers based on how much influence they have on the final output, allowing them to discard "noise" qualifiers generated during training.

Key Results

  • High Accuracy: NeuGuS achieved a 100% success rate in synthesizing simple conjunctive formulas and over 90% for complex formulas involving both ANDs and ORs.
  • Solving the "Unsolvable": The tool successfully solved several CHC problems that HoIce (a state-of-the-art symbolic solver) could not solve on its own. For instance, it found invariants involving three variables that were previously a major bottleneck for symbolic engines.
  • Non-Linear Success: By adding auxiliary inputs (like $x^2$), the tool was able to synthesize quadratic inequalities (ovals, parabolas) with high reliability—a task that is notoriously difficult for traditional synthesis tools.

Limitations and Future Work

  • Computational Cost: Training a neural network is significantly slower than simple symbolic enumeration for very easy problems. The authors suggest using their tool as a "heavy hitter" backup when simpler methods fail.
  • Hyperparameter Sensitivity: The success of the extraction depends on choosing the right number of hidden nodes. Too few, and the NN can't learn the logic; too many, and the extraction becomes noisy.
  • Scaling to Data Structures: Currently, the tool focuses on integer arithmetic. The authors plan to extend this to recursive data structures (like lists and trees) and program loops using Recurrent Neural Networks (RNNs).

Summary updated

Abstract

We propose a novel framework of program and invariant synthesis called neural network-guided synthesis. We first show that, by suitably designing and training neural networks, we can extract logical formulas over integers from the weights and biases of the trained neural networks. Based on the idea, we have implemented a tool to synthesize formulas from positive/negative examples and implication constraints, and obtained promising experimental results. We also discuss an application of our method for improving the qualifier discovery in the framework of ICE-learning-based CHC solving, which can in turn be applied to program verification and inductive invariant synthesis. Another potential application is to a neural-network-guided variation of Solar-Lezama’s program synthesis by sketching.
BibTeX
@inproceedings{kobayashi2021toward,
  author = {Naoki Kobayashi and Taro Sekiyama and Issei Sato and Hiroshi Unno},
  title = {{Toward Neural-Network-Guided Program Synthesis and Verification}},
  booktitle = {SAS},
  year = {2021},
  url = {https://openreview.net/forum?id=05H7AXDBcOe},
}

Loading related content...

Figure