Learning Program Behavioral Models from Synthesized Input-Output Pairs

Tural Mammadov, Dietrich Klakow, Alexander Koller, Andreas Zeller

TL;DR

This paper introduces MODELIZER, a framework that learns lightweight, reversible models of black-box programs using neural machine translation. By synthesizing inputs from grammars and training on input-output pairs, MODELIZER creates models that can accurately mimic program behavior and even predict inputs that produce specific outputs, offering a novel approach to program understanding and testing.

What Problem Does This Paper Address?

Understanding and predicting the behavior of complex software is a fundamental challenge in computer science. Many programs, especially those we use daily, operate as "black boxes," where their internal workings are hidden. Interacting with these programs involves providing inputs and observing outputs, but fully grasping their behavior, especially for testing, debugging, or reverse engineering, can be difficult. Existing approaches often require access to source code or rely on large, general-purpose language models (LLMs) that may not be perfectly suited for specific program behaviors. This paper addresses the need for accurate, efficient, and program-specific behavioral models that can be learned from observable input-output behavior alone.

Methods

MODELIZER leverages a neural machine translation (NMT) approach, treating program execution as a sequence-to-sequence task. The core methodology involves:

  • Grammar-based Input Synthesis: Instead of relying solely on existing datasets, MODELIZER uses formal grammars (Context-Free Grammars or CFGs) to automatically generate a diverse set of syntactically valid inputs. This allows for the creation of a virtually unbounded number of training examples.
  • Placeholder Tokens: To manage complexity and generalize better, MODELIZER employs placeholders within synthesized inputs, representing abstract concepts like text or URLs. These placeholders are later mapped to actual values during reconstruction.
  • Program Execution and Data Collection: The synthesized inputs are fed to the "Program Under Test" (PUT), and the resulting input-output pairs are collected.
  • NMT Model Training: These pairs are then used to train a sequence-to-sequence NMT model. This model learns to predict the output given an input.
  • Reversible Models: A key innovation is that the learned NMT models are also reversible. This means they can predict the input that would have produced a given output, enabling inverse behavior modeling.
  • Hyperparameter Optimization: The framework includes an automated hyperparameter tuning process using the Optuna framework to find optimal configurations for the NMT models.
  • Domain-Specific Tokenization: To handle various program formats, MODELIZER supports custom tokenizers that can parse and reconstruct program data, often leveraging grammar definitions.

Datasets

The paper uses several real-world programs and their associated data for evaluation. For training, MODELIZER primarily relies on synthesized input-output pairs generated using grammars. For evaluation, it uses both synthesized data and real-world test cases.

  • Evaluation Subjects:
    • Pandoc: For Markdown to HTML conversion.
  • MSTICpy: For SQL to KQL conversion.
  • latexify-py: For Python math expressions to LaTeX conversion.
  • py-asciimath: For AsciiMath to MathML and LaTeX conversion.
  • Real-world Data: For Pandoc, 100 Markdown files were used. For msticpy, a subset of the "sql-create-context" dataset was employed. For latexify-py and py-asciimath, synthesized samples were generated and then used for evaluation.

Key Insights and Ideas

  • Program-Specific Models Outperform General LLMs: The research suggests that lightweight, program-specific models trained from scratch can achieve higher accuracy and efficiency for mocking program behavior compared to large, general-purpose LLMs, even after fine-tuning.
  • Reversibility is Powerful: The ability of the learned models to predict inputs from outputs opens up new avenues for test generation and program analysis, going beyond simple behavior mocking.
  • Grammars are Key to Data Generation: Using grammars to synthesize inputs is crucial for creating diverse and sufficient training data, especially when real-world data is scarce or biased.
  • Synthesized Data Needs Careful Alignment: While synthesized data is essential, its distribution can differ from real-world data, potentially impacting model performance. Few-shot fine-tuning on real-world examples can effectively bridge this gap.
  • Lightweight Models are Feasible: MODELIZER demonstrates that accurate behavioral models can be learned with significantly fewer parameters (e.g., < 6.3 million for Markdown/HTML) than typical LLMs, making them deployable on commodity hardware.

Key Results

  • High Accuracy: MODELIZER models achieved up to 95.4% accuracy in mocking program behavior and a BLEU score of 0.98 with a standard error of 0.04 on real-world applications.
  • Efficient Models: The learned models are small, requiring fewer than 6.3 million parameters for languages like Markdown or HTML.
  • Accurate Inverse Prediction: Inverse models (predicting input from output) showed comparable accuracy to forward models.
  • Pandoc Performance: For Markdown to HTML conversion, models trained on medium-sized synthetic datasets (100k-250k samples) achieved high prediction accuracy, with Exact Match scores above 90%.
  • LLM Comparison: Fine-tuned LLMs (CodeLlama, CodeGemma) showed significantly lower performance compared to custom-trained MODELIZER models, especially in terms of Exact Match and Close Match scores, indicating they struggle to replicate program behavior without extensive adaptation.

Limitations and Future Work

  • Computational Complexity: Transformer models have quadratic complexity with respect to input length, making modeling extremely long sequences challenging.
  • Context Window Sensitivity: MODELIZER, like other Transformer models, is sensitive to the length of processed sequences. While techniques like sliding window expansion are used, ensuring correlation for input/output feature distributions between synthesized and real-world samples remains an area for improvement.
  • Program-Specific Parsers: For certain output formats (e.g., KQL), custom parsers were needed due to the unavailability of third-party options, which can be time-consuming to develop.
  • Stateful Programs: The current framework primarily models stateless programs. Modeling stateful systems would require extensions to encode and track program states.
  • Grammar Refinement: The quality of learned models heavily depends on the completeness of the input grammar. If the grammar misses features present in real-world data, model performance suffers. Future work includes automatically mining grammars and refining them based on feedback.
  • Leveraging Program Feedback: The authors plan to explore using feedback from the PUT to continuously re-train and fine-tune models, enabling automatic detection of behavior deviations and adaptation to system changes.

Summary updated

Abstract

We introduce Modelizer—a novel framework that, given a black-box program, learns a model from its input/output behavior using neural machine translation algorithms. The resulting model mocks the original program: Given an input, the model predicts the output that the program would have produced. However, the model is also reversible — that is, it can predict the input that would have produced a given output. Finally, the model is differentiable and can be efficiently restricted to predict only a particular aspect of the program behavior. Modelizer uses grammars to synthesize and inputs and unsupervised tokenizers to decompose the resulting outputs, allowing it to learn sequence-to-sequence associations between token streams. In addition to input grammars, Modelizer only requires the ability to execute the program. The resulting models are small, requiring fewer than 6.3 million parameters for languages such as Markdown or HTML; and they are accurate, achieving up to 95.4% accuracy and a BLEU score of 0.98 with standard error 0.04 in mocking real-world applications. As it learns from and predicts executions rather than code, Modelizer departs from the LLM-centric research trend, opening new opportunities for program-specific models that are fully tuned towards individual programs. Indeed, we foresee several applications of these models, especially as the output of the program can be any aspect of program behavior. Beyond mocking and predicting program behavior, the models can also synthesize inputs that are likely to produce a particular behavior, such as failures or coverage, thus assisting in program understanding and maintenance. This abstract refers to the TOSEM 2025 article with the same title[Ma25]
BibTeX
@article{mammadov2025learning,
  author = {Tural Mammadov and Dietrich Klakow and Alexander Koller and Andreas Zeller},
  title = {{Learning Program Behavioral Models from Synthesized Input-Output Pairs}},
  journal = {ACM Transactions on Software Engineering and Methodology},
  year = {2025},
  doi = {10.1145/3748720},
}
Figure