language=XML, basicstyle=, keywordstyle=, stringstyle=, commentstyle=,
numbers=left, numberstyle=, stepnumber=1, numbersep=10pt, backgroundcolor=,
showspaces=false, showstringspaces=false, showtabs=false, frame=none,
rulecolor=, tabsize=4, captionpos=b, breaklines=true, breakatwhitespace=false,
escapeinside=%**), morekeywords=*,..., morestring=[s]<>, columns=fullflexible,

# Learning Program Behavioral Models from Synthesized Input-Output Pairs

Tural Mammadov<EMAIL_ADDRESS>0009-0007-8466-3694 CISPA Helmholtz
Center for Information SecuritySaarbrückenGermany ,  Dietrich Klakow
<EMAIL_ADDRESS>0000-0002-4147-9690 Saarland
UniversitySaarbrückenGermany ,  Alexander Koller<EMAIL_ADDRESS>0000-0002-5317-6689 Saarland UniversitySaarbrückenGermany and  Andreas Zeller
<EMAIL_ADDRESS>0000-0003-4719-8803 CISPA Helmholtz Center for Information
SecuritySaarbrückenGermany

(2024; 11 July 2024)

###### 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_. The resulting model _mocks_ the original program: Given an
input, the model predicts the output that would have been produced by the
program. However, the model is also _reversible_ —that is, the model 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
certain aspect of the program behavior. Modelizer uses _grammars_ to
synthesize inputs and to parse the resulting outputs, allowing it to learn
sequence-to-sequence associations between token streams. Other than input and
output 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. We foresee several _applications_ of these models,
especially as the output of the program can be any aspect of program behavior.
Besides mocking and predicting program behavior, the model can also synthesize
inputs that are likely to produce a particular behavior, such as failures or
coverage.

Software Testing, Mocking, Deep Learning

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††journal:
TOSEM††journalvolume: 1††journalnumber: 1††article: 1††publicationmonth:
1††ccs: Computing methodologies Learning from demonstrations††ccs: Software
and its engineering Model-driven software engineering††ccs: Security and
privacy Software reverse engineering††ccs: Software and its engineering
Software prototyping††ccs: Software and its engineering Software testing and
debugging

##  1\. Introduction

Figure 1. Example of Modelizer in action.

Example of Modelizer in action.

Understanding and predicting the behavior of a given program is a core
challenge of Computer Science. Many programs people use are black-box systems
that conceal their internal workings, while allowing users to interact with
them by providing inputs and observing outputs. In this work, we present
Modelizer—a novel approach to extract a _behavior model_ from a black-box
program under test (PUT)—by synthesizing inputs, observing outputs, and
learning the relationships between input and output features. The resulting
_neural machine translation model_ $M$ can be used for several purposes.
First, $M$ is able to _mock_ the behavior of the PUT: Given an input, $M$
predicts the output that the PUT would have produced, with high accuracy
(Figure 1). $M$ can then replace the PUT in case the PUT can no longer be
executed—for instance, because it requires a special environment, or is
expensive to run, or because it may be suspected to contain malware (which
will not be extracted into $M$). As the output can be any aspect of program
behavior (such as execution traces or coverage), the model $M$ can also
predict such aspects for any given input.

The most interesting point, however, is that the learned model $M$ is
_reversible:_ it can predict an input that likely produces a given output.
Assuming the PUT translates _Markdown_ inputs to HTML, then a reversed model
$M^{-1}$ would take HTML inputs and _translate them back_ to the original
Markdown code, again with high accuracy. And if the output is, say, a
particular execution trace, then the reversed model $M^{-1}$ will produce an
input that is likely to produce this very trace. The learned model $M$ is
_differentiable,_ and can thus be efficiently restricted to particular output
features.

Modelizer learns the model from the PUT by executing it again and again,
observing how its inputs translate to its outputs. However, like all machine
learning models, Modelizer depends on good training. This raises two central
problems, for each of which Modelizer has a solution:

Synthesizing inputs.:

The first central problem thus is the availability of _input data_ for
training. In Software Engineering, the field of _test generation_ discusses
how to obtain input data for a program. The test data must be _valid,_ such
that it gets accepted by the PUT, as well as _diverse,_ such that a wide
variety of input features is covered. In a black-box setting, obtaining valid
and diverse input data requires a dedicated _generator_ or _producer,_
leveraging knowledge about the input language of the program.

Tokenization.:

The second problem is obtaining _features_ from inputs and outputs. Modelizer
uses a _sequence-to-sequence_ translation model to translate token sequences
from inputs into outputs. Hence, we need a _decomposition_ of inputs and
outputs into individual tokens, so we can learn how token sequences map into
each other. While this is a mostly solved problem for natural languages,
tokenizing _formal inputs_ correctly is a challenge, notably as we want the
tokenizer to be general-purpose, and suitable for all sorts of input and
output languages.

Modelizer addresses both problems by leveraging _grammars_ for both input and
output language. The _input grammar_ is used to _produce_ syntactically valid
and diverse inputs; it can also _parse_ existing inputs into derivation trees.
In both cases, we know the structure of the input. The _output grammar_ is
used to _parse_ the output, again delivering a tree structure allowing
decomposition into tokens. Using the input grammar as a producer, we can
synthesize valid and diverse input data automatically and thus obtain as many
input-output pairs from the PUT as we want. In cases when output language
grammar is unavailable, the program output can be decomposed by unsupervised
tokenizers. Modelizer distinguishes structure from content in the decomposed
sequences and can abstract content by replacing them with placeholders to
improve the learning quality.

Developers who want to use Modelizer thus only need to provide the PUT in an
executable form, as well as grammars that describe its input and output
languages; such grammars can also be inferred from the PUT or input samples.
Modelizer synthesizes inputs for the PUT, eventually extracting its behavior
model $M$. The model can then be used for a variety of purposes, including:

  * •

as a _mock_ for the PUT, predicting its behavior—for instance, for testing or
development when the PUT is not available for execution;

  * •

as a _reverse engineering_ tool—for instance, allowing developers to simulate
and analyze the behavior of the PUT without requiring its code; or for plain
_model stealing,_ replicating the behavior of an existing model;

  * •

as an _anomaly detector_ monitoring the PUT and detecting behavior changes—for
instance, flagging situations where the PUT and model deviate;

  * •

as a _reverse predictor,_ producing likely inputs that result in given
outputs—for instance, to produce inputs that trigger behaviors of interest;
this is the core challenge of software test generation.

These scenarios only scratch the surface of possible usages. In this paper,
however, we focus on the _mock_ and _reverse predictor_ scenarios—that is,
predicting outputs from inputs and vice versa. We evaluate Modelizer across a
range of challenging PUTs and achieve excellent accuracy. Notably, the models
produced by Modelizer showed high accuracy on non-trivial programs despite
having a small number of neurons (and thus efficient to learn). On the
_Pandoc_ markup converter, for instance, Modelizer achieved over 90% accuracy
in converting Markdown to HTML and vice-versa with a BLEU score of 0.71. While
complex computations as performed by TeX or many commercial programs remain
out of reach for our current methods, our experiments indicate that increased
model and training sizes may make such learning possible in the future.

In summary, our contributions are as follows:

A novel, generic means to extract behavior models from programs.:

To the best of our knowledge, Modelizer is the first approach to automatically
learn sequence-to-sequence models from arbitrary programs.

Using grammars to produce inputs for training.:

Modelizer uses grammars to produce inputs (and parse given inputs), and can
thus learn from an unbounded number of training inputs and resulting outputs.

Abstract placeholders for tokenizers.:

Tokenizers that implement the suggested interface can automatically replace
the real content with abstract placeholders, thus focusing on translating
_text structure_ rather than text content.

Predictive behavior models with high accuracy.:

The models produced by the Modelizer framework show high accuracy when
predicting outputs for given inputs.

Reversible behavior models.:

The models produced by Modelizer can be reversed, producing inputs that are
likely to result in given outputs.

The remainder of this paper is organized as follows: Section 2 describes in
detail how Modelizer works, including input generation, dataset preprocessing,
model learning, and model deployment. Section 3 covers the implementation
aspects of Modelizer. In Section 4, we evaluate Modelizer on a variety of
text-to-text translators, such as Markdown to HTML, query languages, and more.
Section 5 discusses the limitations of Modelizer. After discussing related
work (Section 6), Section 7 closes with a conclusion and future work.
Modelizer and all experimental data are available as open source; see Section
7 for details.

##  2\. Approach

Figure 2. How Modelizer works. Modelizer tests program with synthesized inputs
and automatically learns reversible program behavior model from extracted
input-output pairs.

How Modelizer works. Modelizer tests program with synthesized inputs and
automatically learns reversible program behavior model from extracted input-
output pairs.

Modelizer is a generic framework for _learning program behavior._ It uses
_synthesized data_ to automatically learn _reversible generative models_ that
can replicate the behavior of real-world programs with high accuracy. Figure 2
shows a general overview of the framework. Given the input specification for
the selected PUT, Modelizer automatically generates the required number of
inputs and passes them to the PUT for processing. Once the PUT produces the
corresponding output, Modelizer extracts these input-output pairs and uses
them to train a reversible neural machine translation model. The trained model
can be further deployed on modern computer architectures. We have automated
_program behavior mocking_ using the following steps: Input Generation,
Dataset Preprocessing, Model Learning, and Model Deployment. The following
sections will cover each step in detail.

###  2.1. Input Generation

While developing our framework, we aimed to make it interoperable with
different types of programs. Even though all programs are written in different
programming languages, differ in implementation logic, and target different
hardware architectures and operating systems, most programs are made to
process input coming from users or other programs. Thus, we have decided to
learn program behavior by training our behavior mocking models from the
_program inputs and processed outputs._ Of course, such a strategy will
enforce certain limitations:

  * •

The program behavior should be _deterministic_. At every execution, the
program should produce the same output for the given input.

  * •

We will not be able to model the behavior of programs that process _extremely
long inputs_ or _outputs_ at once. The computational complexity, memory, and
time constraints scale quadratically with the input-output length.

  * •

Learning accurate inverse models that predict inputs for the given output is
challenging when PUT computes multiple inputs to the same output. An
intermediate representation for inputs could assist in such cases, which leads
to _context loss_.

To learn an accurate model, we need sufficiently many diverse input-output
pairs. Since public test datasets are typically biased towards commonly used
features, and we do not know in advance how many inputs are required for our
approach to learn the behavior of an unseen program, Modelizer assumes that
inputs are _automatically generated_.

####  2.1.1. Input Generation with Grammars

To cover the entire input space (and hence increase our chances to also cover
the behavior and output spaces), we use _grammar-based_ input producers
(Zeller et al., 2023). These encode input specifications as context-free
grammars (CFG) (Chomsky, 1956)—a finite set of recursive string generation
rules. For some input formats, such CFGs already exist and are publicly
available. For example, the Grammar Zoo (Zaytsev, 2015) repository contains
definitions of 1756 grammars of mainstream programming languages mined from
standard documentation or community-created resources.

Figure 3. Input generation pipeline. Modelizer automatically synthesizes and
validates unique inputs from given specification

Input generation pipeline. Modelizer automatically synthesizes and validates
unique inputs from given specification

The first major component of the Modelizer framework is the Input Generator
Module. This module functions as a data processing pipeline, which is sketched
in Figure 3. It contains four steps: (1)  _Synthesis_ , (2)  _Post-Processing_
, (3)  _Hashing_ , and (4)  _Validation_.

At the synthesis step, the input producer synthesizes new input samples
according to the rules encoded in grammar. Then, the synthesized samples get
refined to better align with real-world data. Such a refinement helps to map
synthesized input features to real-world data features without increasing the
size of grammars and, thus, simplifies the model learning process. The refined
samples are then checked for uniqueness by computing a hash of the synthesized
sample. If the hash value is not present in the Hashes Dataset, the sample is
passed to the PUT for further processing. Otherwise, all steps are repeated
till a unique sample is generated. The PUT produces the corresponding output,
which is saved in a persistent storage along with the input. The collected
input-output pairs are later used to train a program behavior model.

⬇

1<start> ::= <blocks>

2<blocks> ::= <element> | <element>\n\n<blocks>

3<element> ::= <heading> | <paragraph_block> | <blockquote> |

4 <horizontal_rules> | <ordered_list> | <unordered_list>

5<heading> ::= # <paragraph_text> | ## <paragraph_text> | ### <paragraph_text> |

6 #### <paragraph_text> | ##### <paragraph_text> | ###### <paragraph_text> |

7 <paragraph_text>\n<double_equal_sign> | <paragraph_text>\n<double_dash_sign>

8<paragraph_block> ::= <paragraph_text>\n | <paragraph_text>\n<paragraph_block>

9<paragraph_text> ::= <formatted_text> | [<formatted_text>](<url>) |

10 <code_block> | <paragraph_text> <paragraph_text>

11<formatted_text> ::= <text> | <bold_text> | <italic_text> | <bold_italic_text> | <quoted_text>

12<bold_text> ::= <double_asterisk><text><double_asterisk> | <double_underscore><text><double_underscore>

13<italic_text> ::= <asterisk><text><asterisk> | <underscore><text><underscore>

14<code_block> ::= ‘<text>‘ | ‘‘‘<text>‘‘‘ | "<empty_space><text>"

15<quoted_text> ::= ’<text>’ | "<text>"

16<text> ::= TEXT

17<url> ::= URL

Listing 1: Markdown grammar used for input generation (excerpt)

Let us reuse our handwritten Markdown grammar (LABEL:lst:markdown-grammar) to
demonstrate the synthetic input generation process. We will follow the steps
that Modelizer takes to produce inputs. You can find the high-level
implementation of the input generation pipeline written in Python in
LABEL:lst:generate. Once the input producer is configured, it is ready to
synthesize as many inputs as needed (Step 1). Below we give an example of
synthesized input that was generated by the producer:

`TEXT [TEXT](URL) TEXT **TEXT** TEXT ‘TEXT‘ TEXT\n`

⬇

1def generate_data(grammar, min_terminals, max_terminals, total_elements,
program_handler):

2 dataset = list()

3 seen_inputs = set()

4 processor = PlaceholderProcessor(grammar)

5 fuzzer = GrammarFuzzer(grammar, min_terminals, max_terminals)

6 while(len(dataset) < total_elements):

7 input_data = fuzzer.fuzz() # Step 1

8 input_data = processor.deduplicate(input_data) # Step 2

9 input_hash = sha384(input_data.encode("utf-8")).hexdigest() # Step 3.1

10 if input_hash not in seen_inputs:

11 seen_inputs.add(input_hash) # Step 3.2

12 output_data = exec(program_handler, input_data) # Step 4

13 dataset.append((input_data, output_data))

14 return dataset

Listing 2: Input generation in Modelizer (pseudocode)

The producer has synthesized one top-level Markdown element, which is a
paragraph block. The paragraph block was expanded to a single paragraph text
element which respectively contains a sequence of formatted text, hyperlink,
and codeblock elements. One of the formatted text elements was further
expanded to a bold text element. The synthesized input contains TEXT and URL
placeholders instead of real character sequences. We have decided to define
placeholder tokens for replacing the real-world data instead of encoding the
whole language vocabulary into our grammar and synthesizing natural language
sentences. We will elaborate more about placeholders in the follow-up section.

####  2.1.2. Placeholders

Synthesizing the data that is equivalent to real-world counterparts is a
challenging task. Different programs can process the same data in various
ways. This means that the grammar must be specified or refined according to
program expectations. Depending on the complexity of input specification, the
number of required input samples for efficient behavior learning can also
become extremely large. We have figured out that for certain data types and
programs, some fragments that are not affected or used by underlying
implementation logic can be abstracted. For example, many text format
converters only process the document structure, leaving the document content
untouched. To benefit from such effects, we suggested and implemented two
strategies in our input generation pipeline:

  * •

We suggest generalizing certain low-level non-terminal expansion rules by
replacing a fraction of non-terminal to terminal expansions with generic
placeholders.

  * •

We have added an optional post-processing step that augments placeholders with
unique identifiers.

Both strategies will help to capture large portions of possible input space
with few samples and correctly map real-world inputs to generic
representations and vice-versa during the inference phase. Instead of learning
the behavior from real-world examples, we learn how the PUT processes
placeholders.

Let us refer back to the Markdown synthesis example and follow the input
generation phases. The Placeholder Processor at Step 2 will replace these
placeholders with equivalents that additionally carry unique identifiers. The
output of the Placeholder Processor is shown below:

`TEXT_1 [TEXT_2](URL_1) TEXT_3 **TEXT_4** TEXT_5 ‘TEXT_6‘ TEXT_7\n`

We assume that a TEXT placeholder can represent any character sequence in a
real Markdown document. Similarly, a URL placeholder can substitute an
arbitrary definition. By introducing such an abstraction layer, we can cover
the whole space of structures of real-world documents with a relatively small
number of synthesized samples.

While the input producer’s output is already well-formed and will pass the
input parsing guards, it can be challenging to align real-world Markdown
documents with the synthesized structure because it is impossible to
distinguish the generated _placeholders_ from each other. Therefore, we have
included a post-processing phase in the input generation pipeline, for which
we have implemented a generic Placeholder Processor. It must be initialized
with the list of Placeholders that are encoded into selected grammar, like
`[TEXT, URL]`, and can automatically assign a unique identifier to every
placeholder that it finds in the given sequence. Of course, it is possible to
inject identifiers during the input generation. However, grammar-based input
generators do not synthesize integers incrementally. They cannot guarantee
that the generated identifier will be used in a synthesized sequence of
characters only once. It is much faster and easier to generate a simple
candidate sequence and then refine it using custom string-replacement or
constraint-solving rules. The presence of unique identifiers improves the
accuracy of both input-to-output and output-to-input translations,
specifically in the cases when elements must be reordered during translation.
During the tokenization process, which we will cover in the following
sections, the respective data portions are assigned with a matching
placeholder type that already includes a uniquely generated identifier.
Optionally, the assignment of unique identifiers can be disabled.

Since grammar-based producers do not maintain a list of generated samples, we
have implemented a sample validation procedure which first computes an HMAC-
SHA-384 (Hansen and 3rd, 2011) value (Step 3.1) for the synthesized sample and
then checks whether the computed hash value is stored in the Hashes Dataset
(Step 3.2). If a computed hash value is absent in the dataset, the dataset
gets updated with a new record (Step 4) and the synthesized input is passed to
the PUT to compute output. Otherwise, the synthesized sample is dropped, and
all input generation steps are repeated till the unique sample is synthesized.
Corresponding input-output pairs are saved in a persistent storage for later
processing. The collected input-output pairs are saved in a persistent storage
for later processing.

###  2.2. Dataset Pre-processing

Machine translation is the task of automatically translating a text from one
language to another. Neural machine translation models are the latest
iteration of machine translation approaches that rely on deep neural networks
to learn dependencies and patterns between sentences in the source and target
languages. The ability to learn these dependencies from matching input-output
pairs inspired us to reason about the program behavior modeling as a sequence-
to-sequence translation task. In principle, the current generation of neural
machine translation architectures that we use in our implementation can
operate with the whole input at once. The computational complexity of these
systems scales quadratically concerning the length of the input, and practical
implementations do not follow this principle. Instead, text-to-text
translations are performed by partitioning the whole input into sequences of
small elements called tokens. Then, neural text translation models learn how
to generate sequences of tokens in a target language by mapping the cross-
token dependencies from a source language to a target language. Similarly, the
synthesized input and computed output must be converted into batched tensors
for the Learner to be able to process them. While text partitioning is a well-
studied problem in the natural language processing domain (Manning et al.,
2008), and there are already tools that can perform this task (Honnibal and
Montani, 2017), we find the tokenization of program input and output to be a
challenging task.

####  2.2.1. Pre-trained and Unsupervised Tokenizers

Instead of implementing tokenizers from scratch, one can potentially rely on
existing _generic_ tokenizers. For example, the _HuggingFace_ repository (Wolf
et al., 2020) provides access to many community-developed natural language
tokenizers through the HuggingFace API. Such tokenizers cannot properly split
the program data for several reasons. First, they ignore the data-specific or
computation-specific features. Both factors impact the tokenization
granularity, which is covered in the following paragraphs. Also, some
tokenizers, like the pre-trained Llama3 tokenizer, modify the input by
prepending or appending additional characters to the produced tokens. This can
break the syntactical correctness when it comes to program data and can impact
the quality of learned models.

While any input and output can be encoded as a sequence of characters,
semantically it does not necessarily need to be textual data. Programs can
accept or produce structural data. Such a structure contains knowledge that is
relevant for behavior learning, but many existing tokenizers cannot
distinguish the data structure from the content. Since, for certain
computation tasks, like converting Markdown-to-HTML or SQL-to-KQL, the program
is going to process the structure of the input while leaving content
unchanged, a tokenizer needs to be able to map the fragments of the input to
an abstract representation while processing. It is possible to augment the
tokenization process of pre-trained tokenizers with additional pre and post-
processing steps, where inputs can be transformed into semantically similar
representations with placeholders replacing the fragments containing content.
To build such a pipeline, the parser for the given data type has to exist and
align with the input parsing rules of PUT.

Still, the program behavior learning approach is tokenizer-agnostic, and an
unsupervised tokenizer like Google SentencePiece (Kudo and Richardson, 2018)
is sufficient to quickly start the behavior learning process. However, the
implementation of a data-specific tokenizer will help to further improve the
quality of the learned model.

####  2.2.2. Masked Tokenization

While our approach works with generic tokenizers, we obtain better results
with _custom tokenizers_ adapted to the languages at hand. Our `HTMLTokenizer`
adapted to HTML, for instance, takes an HTML string such as

`<h1>Foobar</h1><p>Foobar is a <em>Python</em> library</p>`

The result of the tokenization looks like following:

`[ <h1>, TEXT_1, </h1>, <p>, TEXT_2, <em>, TEXT_3, </em>, TEXT_4, </p> ]` `{
TEXT_1: Foobar, TEXT_2: Foobar is a, TEXT_3: Python, TEXT_4: library }`

If we include the placeholder mapping as input to the reconstruction routine
for the selected example, it will output the original HTML string. Otherwise,
we will get the following output:

`<h1>TEXT_1</h1><p>TEXT_2<em>TEXT_3</em>TEXT_4</p>`

The reconstruction routine is inverse to tokenization, and for many data
formats, it can be performed as a simple string concatenation. However,
Modelizer provides several implementations for mapped string reconstruction.
We support both early and late token instantiations, meaning that abstract
tokens will be replaced with real-world values before or after the token
concatenation. Furthermore, we support different _mapping policies;_ see
Section 3.2 for details of our implementation, including the pseudocode for
HTML tokenization.

Full control over the tokenization process allows us to specify the
tokenization granularity, impacting the prediction accuracy and model learning
time. The vocabulary size grows corresponding to the number of unique tokens
in the training set, which impacts the overall number of model parameters. It
is useful to combine tokens that sequentially appear in the same context. With
this measure, we reduce

  1. (1)

the chances of breaking the syntactical correctness of the generated
sequences;

  2. (2)

the time required for learning the model; and

  3. (3)

the time required for sequence generation.

How does one implement a domain-specific tokenizer? The simplest way is by to
extend the parsing functionality, by deriving a parser from the grammar. In
this case, we can reuse the grammar that was used for synthesizing inputs.
Still, we cannot infer the output parser this way yet. Once we can
automatically and correctly extract output grammars from PUTs, we will be able
to infer domain-specific parsers and tokenizers for them.

###  2.3. Model Learning

Our Learner is based on a sequence-to-sequence neural machine translation
model called Transformer (Vaswani et al., 2017). It learns a program-specific
behavior mocking model from selected input-output pairs.

We present the high-level representation of the learning pipeline in
LABEL:lst:learn and cover the steps taken in detail in the following
paragraphs. Model Learner accepts the input-output data formats as input and
loads the corresponding synthesized training sample pairs from the dataset.
The loaded samples get automatically split into training, validation, and test
sets.

⬇

1def learn_model(dataset, input_type, output_type, train_fraction,
num_epochs):

2 dataloader = DataLoader(dataset, input_type, output_type)

3 train_split, validation_split, test_split =
dataloader.random_split(train_fraction)

4 src_vocab, trg_vocab = dataloader.get_vocabularies()

5 param_searcher = HyperparameterSearcher(src_vocab, trg_vocab,

6 model_trials=250, lr_trials=100)

7 model_params = param_searcher.search(test_split)

8 model = Learner(model_params, src_vocab, trg_vocab)

9 for _ in range(num_epochs):

10 model.train(train_split)

11 model.validate(validation_split)

12 return model

Listing 3: The model learning pipeline in Modelizer (pseudocode)

Modelizer _automates the hyperparameter tuning process._ We have implemented a
Hyperparameter Optimizer that tries to automatically find the best combination
of configurable parameter values using a small disjoint set of test samples.
Such a test set consists of synthesized 10,000 samples. The optimizer is built
upon the _Optuna_ (Akiba et al., 2019) framework, which is a hyperparameter
optimization framework that can be used for any machine learning model.
Parameter search is performed in two phases. The first phase is _Model
Parameter Search,_ which looks for the best configuration of the neural
network for the fixed number of iterations (Vaswani et al., 2017). Using a
fixed learning rate, the optimizer computes the value of the cross entropy
loss metric for the different combinations of the Linear Layer size, Embedding
size, the number of Attention Heads, and the number of Encoder and Decoder
layers. The combination that has the lowest value of cross-entropy criterion
is then used in the _Learning Rate Search phase_ , where the starting learning
rate (LR) value, as well as weight decay and learning rate adjustment policy,
are determined. For our experiments, we have configured the Hyperparameter
Optimizer to execute the _Model Parameter Search_ phase for 250 trials and the
_Learning Rate Search_ phase for 100 trials.

Then the `Learner` gets initialized using the discovered model configuration
and the model learning process gets executed for the specified number of
iterations, called epochs. We use the cross-entropy loss function (Shannon,
1948), which is a generalization of the Logarithmic Loss function for multi-
class classification problems, as our training evaluation criterion. It
measures the dissimilarity of probability distributions between the expected
and predicted labels. Also, we use the _Adaptive Moment Estimation with
Decoupled Weight Decay Regularization_ optimization algorithm (AdamW)
(Loshchilov and Hutter, 2019) to automatically adjust the model’s parameters
to minimize the training loss value. The validation split is used to evaluate
the model’s performance on unseen data to prevent overfitting.

With our “lightweight” models, which, for example, require less than 6.3
million parameters to learn the Markdown to HTML conversion behavior of the
Pandoc markup converter (MacFarlane, 2006), we achieve high accuracy in
mocking program-specific behavior in a short amount of time on a commodity
hardware. For the rest of the subjects that we used in the evaluation, the
forward models contained 3-to-7.7 million parameters and inverse models
required 2.8 to 10.3 million parameters to learn the hypothetical inverse
behavior. The training time varies from several minutes to a couple of hours,
depending on the subject.

###  2.4. Model Deployment

Figure 4. Model Deployment. An example scenario of the Learned Behavior Model
predicting Program Input given the Program Output. The model prediction gets
validated for correctness in the optional validation phase.

Model Deployment. An example scenario of the Learned Behavior Model predicting
Program Input given the Program Output. The model prediction gets validated
for correctness in the optional validation phase.

The model Deployment phase, which is summarized in Figure 4, includes the
Prediction and optional Validation phases. Depending on the source data type,
which can be either program input or output, the respective model, source
tokenizer, and target tokenizer get initialized. From this point, model
inference operates similarly to the model training phase. The source data gets
tokenized (1) and passed to the Program Model (2), which predicts a target
token sequence. Then, the predicted sequence gets lifted from token
representation to real-world format by the target reconstructor component (3).
The translation routine supports an optional max output sequence length
parameter. If the framework user does not specify this argument, our default
implementation dynamically estimates the maximum output sequence length by
applying a 1.25 multiplier to the length of the currently processed input
sequence.

Lastly, the predicted data can be passed to an optional Validation phase (4),
which requires access to the respective PUT. It operates according to the
model’s operation mode. For the behavior-mocking mode (predicting program
output from a given program input), predicted output gets compared with
computed output, which additionally gets tokenized and is marked as a
reference sequence. Using both token sequences, we compute the Levenshtein
distance (Levenshtein, 1965) and the BLEU (Papineni et al., 2002) score.
Levenshtein distance, also named the edit distance in literature, is a metric
for measuring the difference between two sequences, computed as a minimal
number of insertions, deletions, and substitutions required to change the
predicted sequence into a reference sequence. More on the BLEU score and other
sequence similarity metrics will be covered in the next section.

In the Inverse-mocking mode (finding the program input used to compute the
given program output), the computed output collected by passing the predicted
input to the PUT gets compared with the initial program output. Since the
actual program input (ground truth) is unknown, currently we can compute
sequence similarity score metrics in cases when the program accepts the
predicted input and does not fail while processing it. A failure of course
will indicate the incorrectness of the predicted input. It is also challenging
to validate the correctness of the prediction in the inverse-mocking mode if
the PUT computes multiple valid inputs to the same output.

⬇

1def deploy(model, grammar, test_case, program_handler=None):

2 # Test the Model

3 in_tokenizer = Tokenizer(grammar)

4 out_tokenizer = CustomTokenizer()

5 test_tokens, test_mapping = in_tokenizer.mapped_feed(test_case) # Step 1

6 prediction = model.translate(test_tokens) # Step 2

7 reconstructed = out_tokenizer.mapped_reconstruct(prediction, test_mapping) #
Step 3

8

9 # Evaluate the Translation

10 if program_handler is not None: # Step 4

11 reference = exec(program_handler, test_case)

12 if reconstructed == reference:

13 print("Model correctly predicted", reconstructed)

14 else:

15 reference_tokens, _ = out_tokenizer.mapped_feed(reference)

16 bleu_score = compute_bleu(reference_tokens, prediction)

17 edit_distance = compute_distance(reference, reconstructed)

18 print("Model failed to correctly predict the output")

19 print("Expected:", reference, "\nPrediction:", reconstructed)

20 print("BLEU Score:", bleu_score, "Edit Distance:", edit_distance")

21 else:

22 print("Model predicted", reconstructed")

Listing 4: Model deployment with the help of Modelizer (pseudocode)

Such programs have to be modeled by introducing an additional abstraction
layer that defines the set of semantically equivalent inputs using formal
rules.

We want to demonstrate the results of the model deployment process depicted in
LABEL:lst:deploy using the example from Table 1. We used the HTML to Markdown
conversion model learned from the Pandoc program, which was trained on
1,000,000 synthesized document pairs. The input HTML string is passed to the
model, which predicts the corresponding Markdown string. At first, the input
HTML string is tokenized and the content gets replaced with placeholders (Step
1). The model uses the produced input tokens to predict a sequence of Markdown
tokens (Step 2). During the reconstruction phase (Step 3) the placeholder
tokens in the predicted sequence get replaced with the real-world data. Since
the Pandoc program was locally installed on the same machine, which was used
to run the HTML to Markdown conversion model, we can validate the correctness
of the predicted output by comparing it with the computed output. We measured
the BLEU score at 1.0 and the Levenshtein distance at 0.0, which indicates
that the predicted output is identical to the computed output.

Table 1. A conversion example from HTML to Markdown.

Input HTML | Reconstructed Markdown
---|---

    <p>Note that <a href="/docs/
    transformers/v4.34.0/en/
    model_doc/tapas#transformers.
    TapasTokenizer">TapasTokenizer</a>
    expects the data of the table
    to be <strong>text-only</strong>.
    You can use <code>.astype(str)
    </code> on a dataframe to turn it
    into text-only data. Of course,
    this only shows how to encode a
    single training example. It is
    advised to create a dataloader
    to iterate over batches.</p>

|

    Note that [TapasTokenizer]
    (/docs/transformers/v4.34.0/en/
    model_doc/tapas#transformers.
    TapasTokenizer) expects the data
    of the table to be **text-only**.
    You can use ‘.astype(str)‘ on a
    dataframe to turn it into
    text-only data. Of course, this
    only shows how to encode a single
    training example. It is advised
    to create a dataloader to
    iterate over batches.

Input Tokens | Predicted Tokens

    <p> TEXT_1 <a  href="URL_1" >
    TEXT_2 </a> TEXT_3 <strong>
    TEXT_4 </strong> TEXT_5 <code>
    TEXT_6 </code> TEXT_7 </p>

|

    TEXT_1 [ TEXT_2 ]( URL_1 ) TEXT_3 **
    TEXT_4 ** TEXT_5 ‘ TEXT_6 ‘ TEXT_7 \n

The conversion was performed by a model of the Pandoc program trained on
1,000,000 synthesized sequence pairs. BLEU score = 1.0, Levenshtein distance =
0.0

##  3\. Implementation

Modelizer implements grammar-based input generators using the grammar fuzzers
from FuzzingBook(Zeller et al., 2023). While the Fuzzing Book _GrammarFuzzer_
randomly chooses the expansion rule from the set of available rules, its
_ProbabilisticGrammarFuzzer_ allows the developer to control the input
generation by assigning _probabilities_ to certain expansion rules. In this
case, the non-attributed expansion rules will be assigned by equally
distributed remaining probabilities.

Such a technique allows us the following:

  * •

_Automatically generating_ a dataset of syntactically _valid_ inputs.

  * •

Customizing the feature selection procedure in the sample generation process.

  * •

Ensuring the representation of specific and _corner samples_ in the data
corpus.

###  3.1. System Requirements

We implemented the model learning functionality of Modelizer in Python using
the _PyTorch_ 2.0 Machine Learning Framework (Paszke et al., 2019). Our
framework currently supports the following hardware backends:

  * •

NVIDIA GPU that supports CUDA 11.7 or higher (Fastest)

  * •

Apple ARM-based system-on-a-chip with at least 16GB of system memory

  * •

System with a x64 processor and 32 GB of system memory (Slowest)

While model learning is a highly parallelizable task, and it can benefit from
the availability of dedicated hardware accelerators, the rest of the tasks can
also be scaled according to the number of available CPU cores. For example, to
reduce the total runtime, our generators support the execution of multiple
grammar-based fuzzers with the same configuration in parallel. The amount of
Fuzzers that got initialized depends on the number of available CPU cores.
Modelizer is responsible for distributing the total workload among all fuzzers
by assigning every fuzzer with its own budget. Then each fuzzer produces
samples in batches until it runs out of the budget. Modelizer systematically
collects the generated samples and checks for their uniqueness. If there was
no previously unseen sample generated within a single batch or a configurable
parameter of failing attempts is reached, the value of the minimum and maximum
non-terminals gets automatically incremented. To simplify the usability and
applicability of our framework, we include a base class generator that can be
extended to support new subjects.

###  3.2. Tokenization with Placeholders

Even though our models are trained on synthesized data, they must still be
capable of operating with real-world data. However, there can be a difference
in the representation between real-world and synthesized data due to the
latter optionally including placeholders instead of real-world values, which
impacts the implementation of our tokenizers. As a part of our contribution,
we supplied the Modelizer with the base implementation and abstract interfaces
for the mapped tokenization and mapped reconstruction routines. For every new
data type, the framework user can wrap the functionality of unsupervised
tokenizers with our mapped tokenization algorithm or implement a format-
specific tokenizer in the subclass.

####  3.2.1. Abstract Tokenizers

By assuming that for both input and output formats, a suitable parser can be
obtained, we implemented `AbstractTokenizer`—a generic mapped tokenization-
reconstruction algorithm that can benefit from format structure knowledge and
replications of input content fragments in the output. While it is not a fully
functional tokenizer, it provides a high-level generic and extendible
implementation of mapped tokenization-reconstruction routines, which assist in
mapping real-world content to abstract placeholders and vice-versa.
LABEL:lst:tokenize-base contains the fragment of the mapped tokenization
routine.

⬇

1class AbstractTokenizer:

2 def mapped_tokenize(self, data: str):

3 self.clear_mappings()

4 self.mask_mapping = True

5 self.tokenize(data)

6 self.mask_mapping = False

7 return self.buffer, self.mappings

8

9 def mask_token(self, token: str, pldr: str) -> str:

10 tag = pldr + "_" + str(len(self.mappings[pldr]) + 1)

11 if self.mapping_policy == MappingPolicy.SIMPLIFIED:

12 self.mappings[pldr][tag] = token

13 tag = pldr

14 elif self.mapping_policy == MappingPolicy.OPTIMIZING:

15 if token in self.inverse_mapping:

16 tag = self.inverse_mapping[token]

17 else:

18 self.mappings[pldr][tag] = token

19 self.inverse_mapping[token] = tag

20 elif self.mapping_policy == MappingPolicy.EXHAUSTIVE:

21 self.mappings[pldr][tag] = token

22 self.inverse_mapping[token] = tag

23 return tag

24

25 def set_mapping_policy(self, policy: MappingPolicy):

26 self.mapping_policy = policy

27

28 def tokenize(self, data: str):

29 raise NotImplementedError

Listing 5: Tokenization in Modelizer (pseudocode)

To be able to correctly map real-world content to abstract placeholders (we
use the term mask tokens, which you can see in the pseudocode) whether a
parser-tokenizer processes content fragment of data the provided `mask_token`
method must be called. Thus, the framework user must provide the format-
specific implementation of the `tokenize` routine in a subclass. Then
algorithm can correctly replace the content with an abstract placeholder
during tokenization and successfully recover the original sequence of
characters during the reconstruction. During initialization, the tokenizer,
can learn the placeholders from the grammar definition automatically or
operate with the user-defined collection of placeholders. The proposed
algorithm allows reusing the same tokenizer for tokenizing both synthesized
and real-world data.

####  3.2.2. A HTML Tokenizer

Below we demonstrate a partial implementation of the `HTMLTokenizer` class,
which demonstrates the procedure of masking HTML content by extending the
functionality of the `AbstractTokenizer` class.00footnotetext:  The full
implementation of HTMLTokenizer, which decomposes data using Python built-in
HTMLParser, can be found in our GitHub repository (see Section 7 for details).
This repository also provides additional examples of tokenizer implementations
that rely on PUT’s functionality to parse inputs or implement a custom parser
using regular expressions.

⬇

1from html.parser import HTMLParser

2

3class HTMLTokenizer(AbstractTokenizer, HTMLParser):

4 def tokenize(self, data: str):

5 self.buffer.clear()

6 HTMLParser.feed(self, data)

7

8 def handle_data(self, data: str):

9 if self.mask_mapping == True: # True only if called via
mapped_tokenize(data)

10 token = self.mask_token(data, self.placeholders[1])

11 self.buffer.append(token)

12 else:

13 tokens = self.split_and_align(data)

14 self.buffer.extend(tokens)

Listing 6: Tokenization in Modelizer (pseudocode)

Once the `mapped_tokenize` method is called, the tokenizer clears all internal
buffers and starts processing the given string with the selected Parser. In
this implementation, the HTMLParser requires the end-user to implement handler
methods to process HTML tags together and document content. Here we present
the simplified implementation of the document content handler `handle_data`.
Depending on the operation mode of the tokenizer, which is determined by the
`mask_mapping` flag, the tokenizer either replaces the document content with a
matching placeholder or performs a sequence of format-specific string
splitting operations, which are abstracted in this example.

####  3.2.3. Token Masking Strategies

The token masking algorithm behaves differently according to one of the
selected token mapping policy strategies:

  * •

The `SIMPLIFIED` policy reduces the vocabulary size of the model by removing
identifiers from placeholder tokens.

  * •

The `OPTIMIZING` policy, which is the default policy in our implementation,
uses a minimal number of placeholder tokens to encode data content.

  * •

The `EXHAUSTIVE` policy assigns every content fragment with a unique
placeholder token.

We use the extended version of the HTML document from Figure 1 to illustrate
the effect of using different token masking strategies in tokenization:

`<h1>Foobar</h1><p>Foobar is a <em>Python</em> library. Find` `more on <a
href="127.0.0.1"><i>Foobar</i>.com</a></p>`

When the tokenizer is running in `SIMPLIFIED` token masking mode, then it
removes every unique identifier that had been assigned to a placeholder. It
significantly reduces the model’s vocabulary size, but increases the chances
of producing errors during the reconstruction phase. The tokenized sequence
looks like the following:

`[ <h1>, TEXT, </h1>, <p>, TEXT, <em>, TEXT, </em>, TEXT,`
`<a, href="URL">, <i>, TEXT, </i>, TEXT, </a>, </p> ]`

The tokenizer tries to use a minimal number of placeholders to encode the
real-world data when it is configured to use `OPTIMIZING` token masking
strategy. The repetitive content is encoded by the same placeholder. This is
the default operation mode and evaluation experiments were arranged only using
this policy. The tokenized sequence looks like the following:

`[ <h1>, TEXT_1, </h1>, <p>, TEXT_2, <em>, TEXT_3, </em>, TEXT_4,`
`<a, href="URL_1">, <i>, TEXT_1, </i>, TEXT_5, </a>, </p> ]`

The `EXHAUSTIVE` token masking strategy increases the model’s vocabulary size
and negatively affects the model learning time. The tokenizer maps every
content piece in the processed input to a unique identifier. However, this
policy is useful for programs that reorder elements during processing. The
tokenized sequence looks like the following:

`[ <h1>, TEXT_1, </h1>, <p>, TEXT_2, <em>, TEXT_3, </em>, TEXT_4,`
`<a, href="URL_1">, <i>, TEXT_5, </i>, TEXT_6, </a>, </p> ]`

##  4\. Evaluation

We evaluated Modelizer by learning the execution behavior of real-world
programs. For every PUT, we collected two datasets of input-output pairs by
executing the program with synthesized and real-world inputs respectively. For
every evaluation subject, Modelizer additionally learned an inverse model
$M^{-1}$ that corresponds to a hypothetical program $\textnormal{PUT}^{-1}$,
which is expected to implement an inverse of the behavior of the original
program PUT.

###  4.1. Research Questions

In the evaluation, we address the following research questions:

  1. RQ1.

How accurate are the _Modelizer models_ that mock the behavior of the PUT?
This question is at the heart of Modelizer: How well do the learned models
perform in predicting outputs from inputs?

  2. RQ2.

How accurate are the _Modelizer models_ that are trained on synthesized data
in processing real-world data? This question evaluates the quality of the
learned models when tested with real-world data.

  3. RQ3.

How accurate are the _inverse models_ that mock the behavior of
$\textnormal{PUT}^{-1}$? With RQ3, we evaluate an important application of
Modelizer, namely its ability to predict inputs from outputs.

  4. RQ4.

How fast Modelizer can synthesize a training dataset? This question evaluates
the efficiency of the input generation pipeline implemented in Modelizer.

  5. RQ5.

How fast Modelizer can learn program models? This question evaluates the
efficiency of Modelizer core functionality, which is model learning.

  6. RQ6.

How well do the _synthesized samples_ represent the real-world data? With RQ6,
we investigate the quality of the synthesized training set.

  7. RQ7.

How much _synthetic data_ is required for mocking behavior at which accuracy?
With RQ7, we investigate the impact of the size of the synthesized training
set on the accuracy of learned models.

  8. RQ8.

How should synthetic data _be generated_ to achieve the highest accuracy of
the learned models? With RQ8, we investigate the impact of the synthetic data
generation strategies on the accuracy of learned models.

  9. RQ9.

How does Modelizer learn the _hyperparameters_ for each data pair combination?
This question assesses the impact of _hyperparameters_ (Section 2.3) on the
performance of Modelizer.

  10. RQ10.

Should Modelizer _re-use_ learned hyperparameters for inverse modeling? With
RQ10, we check the _reusability_ of found _hyperparameters_ (Section 2.3) with
forward models for training inverse models.

  11. RQ11.

What is the effect of _placeholders_ on behavior learning? This question
assesses the impact of _placeholders_ (Section 2.1.2) on the performance of
Modelizer.

  12. RQ12.

What is the effect of _tokenizers_ on learning performance? With RQ12, we
investigate the impact of _tokenizers_ (Section 2.2) on the performance of
Modelizer.

###  4.2. Evaluation Subjects

We conducted the evaluation using the four programs listed in Table 2:

Table 2.  The list of evaluated programs and their respective input-output types. Program | Input Type | Output Type | Version
---|---|---|---
Pandoc | Markdown | HTML | 2.19.2
msticpy | SQL | KQL | 2.9.0
latexify-py | Python Math Expression | LaTeX | 0.2.0
py-asciimath | MathML | LaTeX | 0.3.0
py-asciimath | LaTeX | AsciiMath | 0.3.0
py-asciimath | AsciiMath | MathML | 0.3.0

Pandoc:

(MacFarlane, 2006) is an open-source library and command-line tool for
converting markups from one format to another. While the library natively
supports the translation in both directions(Markdown to HTML and HTML to
Markdown), we have tested it only with Markdown to HTML translation
functionality. We manually extracted a Markdown Grammar from the CommonMark
Spec Version 0.29 (MacFarlane, 2019) specification. We used Pandoc’s
functionality to convert Markdown to HTML for our case study, first, to
validate the feasibility of neural behavior modeling of black-box systems,
second, to check the applicability of the same technique for inverse behavior
modeling, when a model has to predict the program input given the output. The
promising results of our first experiments encouraged us to test the approach
with other subjects.

Microsoft Threat Intelligence Python Security Tools:

(msticpy) (Hellen, 2019) is a library for InfoSec investigations, data
analysis, and hunting in Jupyter Notebooks authoring for Azure Sentinel, which
is a cloud-native security information and event management solution offered
by Microsoft for intelligent security analytics and threat intelligence.
Modelizer was evaluated on the SQL to KQL Conversion feature of MSTIC, which
accepts SELECT SQL queries constructed using a subset of ANSI SQL-92 (ISO/IEC
9075:1992, 1992) as input and produces Kusto Query Language (KQL) queries. KQL
is a proprietary query language developed by Microsoft, which is used for
querying and analyzing data in Microsoft Azure services. The supported subset
of SQL-92 specification was encoded as a CFG grammar by us.

latexify-py:

(Oda, 2020) is a Python library that converts Python math expressions to LaTeX
code. The grammar for synthesizing Python math expressions encodes the math
module (Foundation, 2021) functionality from the Python 3.10 standard library.

py-asciimath:

(Belotti, 2020) is a Python library for converting mathematical expressions
from AsciiMath representation to Mathematical Markup Language (MathML) and
LaTeX representation. The grammar for synthesizing MathML was manually
extracted from the MathML 2.0 Specification (Ausbrooks et al., 2003). The
training pairs were collected by converting the synthesized MathML formulas
first into LaTeX format, and then the collected LaTeX formulas were translated
once more into AsciiMath format. This way, we managed to collect three
different sets of input-output pairs and test the framework’s capabilities in
performing the cross-protocol translations in directions that the given PUT
does not currently support.

###  4.3. Training Setup

For every subject, we generated training sets of different sizes (5k, 10k,
50k, 100k, 250k, 500k, 1M). The input generation starts with the minimal
number of non-terminal expansions (_MinNonTerminals_) set to 10 and maximal
(_MaxNonTerminals_) set to 20. Once configured, the generator has 100,000
attempts to generate unique samples using a fixed configuration. If the
generator runs out of attempts the values of _MinNonTerminals_ and
_MaxNonTerminals_ parameters are increased by 10 and the generator is
restarted. The generation process will be running till the generator produces
the required number of unique samples. Also, we configured the data generators
to produce a separate set of input samples that had been synthesized with a
continuously increasing complexity of the generated samples. It was achieved
by implementing the sliding window modification of _MinNonTerminals_ and
_MaxNonTerminals_ values. In this case, the generator uses at least four
different non-terminal expansion configurations to generate the required
number of samples.

Pandoc, msticpy, and py-asciimath subjects were evaluated using real-world
data. We evaluated the SQL to KQL translation models on 1,000 samples that
were collected from the “sql-create-context” open-access dataset (brianm,
2023). This dataset contains natural language to SQL SELECT query pairs.
During testing the msticpy subject, we ensured that it produced a non-empty
output for every extracted SQL query extracted from the dataset. For the py-
asciimath subject, we also extracted 1000 real-world MathML formulas from the
NTCIR-12 dataset (Zanibbi, 2016). For testing the models of the Pandoc program
we extracted 12,783 top-level elements (tree-like structures nesting other
markdown definitions) from 100 markdown files that were collected from the
open-access Markdown dataset (Schmid, 2023) containing readme documentation
files of projects hosted at the HuggingFace Hub (Face, 2024). We have not
managed to find a dataset containing mathematical expressions written in
Python using the _math_ module from the Python Standard Library. Instead, we
synthesized 1000 samples using our Python Expression grammar and replaced the
placeholders with random values of corresponding data types. Additionally, we
evaluated every model on 10,000 synthesized samples that were not included in
the training set. The synthesized dataset was generated by fixing the minimal
number of non-terminal expansions to 10 and the maximal number of non-terminal
expansions to 20.

While the decoder of Modelizer’s translation routines supports a configurable
beam size parameter, we collected all of our experiments with a fixed beam
size = 1. All models were trained for 10 iterations(epochs) with a context-
window size equal to 5000 tokens. In every training configuration, 80% of the
synthesized data had been used for model training. After every training
iteration, the training quality was validated using the remaining 20% of the
training set. Additionally, the learning quality across models was evaluated
with 10,000 previously unseen data pairs which were collected using
synthesized inputs, that were generated by setting the maximal number of non-
terminal expansion to 20. We trained all models using a single NVIDIA Geforce
RTX 4090 GPU with 24 GB of Memory. During the model learning phase Modelizer
was allocating from 650 MB to 22 GB of memory depending on the configuration
of hyperparameters and the sizes of collected vocabularies. Once trained,
models can be deployed on any modern computer architecture that is equipped
with at least 8 GB of system memory and can execute a Python interpreter
version 3.10 or newer. In contrast to real-world programs the learned models
do not require any external dependencies or permissions for system-wide
installation. The required Python interpreter and the set of Python modules
can be pre-configured and shipped with the model instance. A single
environment can be used to execute multiple instances of the model in
parallel. Because the size of trained models is relatively small, we monitored
a low memory footprint when they were running in the inference mode.

###  4.4. Evaluation Metrics

To evaluate the quality of the learned models, we have used the following
evaluation metrics:

BLEU score:

(bilingual evaluation understudy) (Papineni et al., 2002) is a commonly used
metric for the evaluation of machine translation systems, that calculates the
geometric average precision of single, double, triple, and quadruple token
overlap cases between reference and hypothesis token sequences multiplied by
brevity penalty. The score output is always a number between 0 and 1, with 1
indicating the perfect translation case. The BLEU score was computed on the
whole corpus of test cases using the implementation provided by the Python
NLTK package (Team, 2007).

BLEU Error:

stands for Standard Error computed using BLEU score.

NIST score:

(Doddington, 2002) is a metric developed by the US National Institute of
Standards and Technology for evaluating the quality of machine-translated
texts, which is also based on the BLEU score and additionally calculates the
frequency of n-grams and gives a higher score to n-grams that are considered
to less likely occur. We calculated the metric using the implementation
provided by the Python NLTK package (Team, 2007).

Word Error Rate:

(WER) (Morris et al., 2004) is a metric that calculates the accuracy of a
model prediction by computing a ratio between the sum of token insertions,
deletions, and substitutions required to transform the predicted token
sequence into the reference token sequence and the total number of tokens in
the reference token sequence. The lower the value the better the model
performs with a score of 0 indicating that the model has not made any mistakes
during the translation process.

World Information Lost:

(WIL) (Morris et al., 2004) is a metric that computes the percentage of total
tokens that were incorrectly predicted by the model between sets of reference
token sequences and sets of hypothesis token sequences. The lower the value
the better the model performs with a score of 0 indicating that the model has
not lost any information during the translation process.

Exact Match:

is a metric that reflects the percentage of evaluation samples that were
translated correctly by the model. The higher the value, the better the model
performs with a score of 100 indicating that the model has not made any
mistakes during the translation process. This metric relies on the Levenshtein
distance to compare the similarity between the predicted and reference
sequences.

Close Match:

is a metric that reflects the percentage of evaluation samples that were
translated by the model with a single error. We treat such cases as
potentially recoverable at a post-processing stage. This metric relies on the
Levenshtein distance to compare the similarity between the predicted and
reference sequences.

###  4.5. Results

Let us now turn to the evaluation results.

Table 3.  Evaluation results for models mocking Pandoc, msticpy, latexify-py,
and py-asciimath behaviors.

Program | Source | Target |  | Model
---
Type
Size | BLEU |  | BLEU
---
Error
NIST | WER | WIL |  | Exact
---
Match
| Close
---
Match
|  |  |  | 1M | 0.9986 | 0.0033 | 9.9102 | 0.04 | 0.05 | 98.69 | 99.39
|  |  |  | 100k | 0.2923 | 0.3025 | 4.2689 | 54.2 | 72.13 | 51.72 | 56.03
| Markdown | HTML | Forward | 500k | 0.7128 | 0.2337 | 7.5700 | 23.19 | 35.30 | 90.57 | 94.79
|  |  |  | 1M | 0.9988 | 0.0045 | 10.9328 | 0.08 | 0.11 | 99.27 | 99.55
|  |  |  | 250k | 0.2352 | 0.2319 | 4.0123 | 52.62 | 66.00 | 55.78 | 57.51
Pandoc | HTML | Markdown | Inverse | 1M | 0.7036 | 0.1554 | 7.5202 | 23.74 | 34.48 | 93.27 | 93.58
|  |  |  | 500k | 0.9997 | 0.0035 | 11.0359 | 0.03 | 0.03 | 99.58 | 99.69
|  |  |  | 100k | 0.5040 | 0.0497 | 5.0374 | 21.48 | 38.07 | 1.60 | 1.90
| SQL | KQL | Forward | 100k | 0.9791 | 0.0397 | 6.4760 | 1.51 | 2.09 | 95.40 | 96.90
|  |  |  | 250k | 0.9206 | 0.0374 | 11.0730 | 6.41 | 7.48 | 27.51 | 32.64
|  |  |  | 50k | 0.9566 | 0.0388 | 5.0318 | 2.92 | 4.51 | 89.00 | 93.90
msticpy | KQL | SQL | Inverse | 100k | 0.9725 | 0.0379 | 5.1913 | 1.94 | 2.82 | 94.60 | 95.80
|  |  |  | 1M | 0.9969 | 0.0543 | 12.9138 | 0.45 | 0.48 | 88.47 | 88.86
|  |  |  | 50k | 0.5380 | 0.1796 | 6.2148 | 23.30 | 23.60 | 0.00 | 0.00
| PyExpres. | LaTeX | Forward | 100k | 0.9219 | 0.2806 | 9.8394 | 8.48 | 9.59 | 48.50 | 53.50
|  |  |  | 250k | 0.9612 | 0.1039 | 15.9279 | 3.39 | 4.12 | 40.69 | 43.98
|  |  |  | 10k | 0.8595 | 0.0908 | 10.7279 | 9.43 | 12.48 | 31.60 | 52.40
latexify-py | LaTeX | PyExpres. | Inverse | 100k | 0.8747 | 0.1240 | 11.0931 | 10.20 | 12.21 | 44.60 | 56.00
|  |  |  | 1M | 0.9999 | 0.0008 | 11.6252 | 0.01 | 0.01 | 99.82 | 98.92
|  |  |  | 250k | 0.3764 | 0.3522 | 4.7470 | 48.28 | 58.93 | 0.00 | 1.40
| LaTeX | AsciiMath | Forward | 1M | 0.7553 | 0.2994 | 8.4978 | 19.24 | 24.15 | 35.70 | 35.00
|  |  |  | 1M | 0.9983 | 0.0030 | 12.1796 | 0.11 | 0.12 | 98.86 | 99.86
|  |  |  | 50k | 0.3025 | 0.4990 | 4.4004 | 55.25 | 67.26 | 0.10 | 0.40
| AsciiMath | LaTeX | Inverse | 1M | 0.6899 | 0.3470 | 8.1353 | 24.57 | 32.19 | 30.40 | 42.50
| Outliers
|  |  |  | 500k | 0.9846 | 0.0086 | 11.9758 | 0.93 | 1.36 | 93.33 | 93.81
|  |  |  | 100k | 0.0568 | 3.6482 | 1.6700 | 84.26 | 94.50 | 0.00 | 0.00
| MathML | LaTeX | Forward | 5k | 0.2674 | 1.8474 | 3.3514 | 58.75 | 71.58 | 3.00 | 1.40
|  |  |  | 500k | 0.9782 | 0.0107 | 9.2103 | 0.88 | 1.71 | 61.09 | 93.44
|  |  |  | 500k | 0.0000 | 0.5871 | 0.0171 | 97.16 | 99.69 | 0.00 | 0.20
| LaTeX | MathML | Inverse | 10k | 0.5336 | 0.5286 | 4.1001 | 39.32 | 50.64 | 1.00 | 7.40
|  |  |  | 1M | 0.9780 | 0.0101 | 9.2108 | 0.92 | 1.74 | 60.81 | 94.01
|  |  |  | 500k | 0.0000 | 3.6580 | 0.0134 | 97.40 | 99.72 | 0.00 | 0.00
| AsciiMath | MathML |  Hypothet. Forward | 250k | 0.3084 | 2.7773 | 1.1503 | 53.34 | 59.63 | 0.70 | 0.70
|  |  |  | 500k | 0.9844 | 0.0112 | 11.4014 | 0.94 | 1.37 | 93.31 | 93.41
|  |  |  | 5k | 0.1028 | 0.6621 | 1.9223 | 74.02 | 84.91 | 0.00 | 0.20
py-asciimath | MathML | AsciiMath |  Hypothet. Inverse | 5k | 0.2963 | 0.5779 | 3.6842 | 54.06 | 67.69 | 3.40 | 8.80

Yellow cells ◼ indicate an evaluation run with synthetic test data, blue cells
◼ indicate evaluation runs with the real-world data, and purple cells ◼
indicate the evaluation runs on the real-world data performed after fine-
tuning the baseline model on a few real-world data pairs.

###  RQ1: Mocking Accuracy

We start with addressing RQ1: How well do Modelizer models predict outputs
from inputs? To answer this question, we evaluated our models on sets of
10,000 synthesized test cases per subject that have no intersection with any
of the training sets. The results of the evaluation are summarized in Table 3.
The evaluation results show that the models trained on the synthetic data can
achieve a high prediction accuracy for most subjects from the evaluation set.
For most models and subjects, the BLEU score is above 0.98, the Word
Information Lost score is below 0.02 and the Exact Match is above 93%.

Table 4.  Evaluation results of Markdown to HTML conversions done with the
learned models of Pandoc converter.

Dataset | Trained on Synthetic Data | Fine-Tuned on Real Data
---|---|---
Size | Partition | BLEU | WIL |  | Exact
---
Match
| Close
---
Match
BLEU | WIL |  | Exact
---
Match
| Close
---
Match
| ✗ | 0.2576 | 76.16 | 51.40 | 55.93 | 0.6763 | 36.97 | 89.80 | 94.01
5k | ✓ | 0.2710 | 72.94 | 51.64 | 55.96 | 0.6813 | 42.80 | 89.35 | 93.61
| ✗ | 0.2746 | 74.28 | 51.40 | 55.93 | 0.6934 | 40.00 | 88.53 | 92.73
10k | ✓ | 0.2723 | 75.36 | 44.43 | 52.11 | 0.6747 | 42.95 | 89.07 | 93.24
| ✗ | 0.2851 | 75.21 | 51.71 | 56.01 | 0.6735 | 43.97 | 89.42 | 93.80
50k | ✓ | 0.2849 | 73.25 | 51.69 | 56.03 | 0.6874 | 40.49 | 89.72 | 93.84
| ✓ | 0.2923 | 72.13 | 51.72 | 56.03 | 0.6966 | 36.79 | 88.66 | 92.88
100k | ✓ | 0.2704 | 73.26 | 51.61 | 55.89 | 0.6592 | 42.85 | 88.99 | 93.27
| ✗ | 0.2898 | 75.39 | 51.72 | 56.03 | 0.6725 | 38.03 | 89.30 | 93.56
250k | ✓ | 0.2824 | 74.49 | 49.67 | 52.17 | 0.6753 | 37.61 | 89.03 | 93.23
| ✗ | 0.2900 | 70.90 | 40.49 | 55.78 | 0.7128 | 35.30 | 90.57 | 94.79
500k | ✓ | 0.2950 | 68.56 | 51.71 | 56.02 | 0.6867 | 35.64 | 89.31 | 93.76
| ✗ | 0.2535 | 72.90 | 24.38 | 28.68 | 0.6886 | 33.95 | 90.25 | 94.56
1000k | ✓ | 0.2940 | 70.49 | 51.61 | 55.91 | 0.7208 | 36.64 | 90.35 | 94.69

Models were trained on the various sizes of datasets containing synthesized
Markdown to HTML structures. Blue cells ◼ indicate models trained on synthetic
data generated with a fixed number of non-terminal expansions, and purple
cells ◼ indicate application of the synthetic data with an increasing number
of non-terminal expansions.

Table 5.  Evaluation results of HTML to Markdown conversions done with the
learned inverse models of Pandoc.

Dataset | Trained on Synthetic Data | Fine-Tuned on Real Data
---|---|---
Size | Partition | BLEU | WIL |  | Exact
---
Match
| Close
---
Match
BLEU | WIL |  | Exact
---
Match
| Close
---
Match
| ✗ | 0.1988 | 76.01 | 55.08 | 56.83 | 0.6441 | 43.73 | 81.51 | 90.85
5k | ✓ | 0.1886 | 76.63 | 28.36 | 57.40 | 0.6550 | 42.45 | 91.14 | 91.97
| ✗ | 0.2006 | 74.47 | 55.71 | 57.46 | 0.6441 | 44.38 | 90.39 | 91.26
10k | ✓ | 0.2316 | 72.49 | 28.39 | 57.47 | 0.6280 | 45.16 | 87.64 | 88.59
| ✗ | 0.2115 | 70.59 | 53.72 | 55.25 | 0.6282 | 43.94 | 92.15 | 92.93
50k | ✓ | 0.2503 | 65.47 | 55.75 | 56.84 | 0.6170 | 46.18 | 88.61 | 88.97
| ✓ | 0.2096 | 69.33 | 50.58 | 57.31 | 0.6119 | 45.50 | 88.60 | 88.95
100k | ✓ | 0.2112 | 70.16 | 28.62 | 56.03 | 0.6471 | 37.28 | 89.24 | 91.39
| ✗ | 0.2218 | 65.89 | 55.78 | 57.31 | 0.6499 | 40.72 | 90.57 | 90.97
250k | ✓ | 0.2352 | 66.00 | 55.78 | 57.51 | 0.6778 | 39.30 | 92.20 | 92.52
| ✗ | 0.2251 | 66.88 | 55.78 | 55.89 | 0.6793 | 36.75 | 91.51 | 92.72
500k | ✓ | 0.2145 | 68.21 | 19.78 | 47.65 | 0.6646 | 40.97 | 89.02 | 89.56
| ✗ | 0.2326 | 67.26 | 54.97 | 56.31 | 0.6749 | 39.36 | 91.08 | 91.36
1000k | ✓ | 0.2408 | 64.17 | 55.75 | 57.31 | 0.7036 | 34.48 | 93.27 | 93.58

Models were trained on the various sizes of datasets containing synthesized
Markdown to HTML structures. Blue cells ◼ indicate models trained on synthetic
data generated with a fixed number of non-terminal expansions, and purple
cells ◼ indicate application of the synthetic data with an increasing number
of non-terminal expansions.

According to the prediction accuracy scores depicted in Table 3 and
representative results from both Table 4 and Table 5, the medium size of
training sets can already achieve a high prediction accuracy for most subjects
from the evaluation set. Using the given grammar definitions, the data
generator can produce the vast majority of data feature combinations within
the 100,000–250,000 samples range. By further increasing the number of
generated samples, while eliminating duplicates, the generator starts to
produce a more unnatural combination of features, which tends to negatively
affect the model accuracy, makes the learning more costly, and hits the
prediction performance.

Modelizer models trained on synthetic data have a high accuracy in predicting
outputs from inputs.

###  RQ2: Mocking Performance with Real Data

To answer this question, we evaluated our models on sets of 1,000 real-world
test cases per subject, except Markdown and HTML, where, as already mentioned,
we took 100 real-world _readme_ documents and extracted 12,783 top-level
elements from them. These test sets have no intersection with any of the train
sets. While the models achieve great accuracy when tested with synthetic data,
it is noticeably lower when tested with real-world data.

For the input generation, we did not learn the feature distribution from the
particular set of test cases to avoid overfitting to the test data and check
Modelizer’s capabilities in learning the program behavior while having no
additional knowledge of the test subject and the data it processes.
Consecutively, the feature distribution between the real-world and synthesized
samples did not align well resulting in a significant performance hit. The
availability of additional data pairs for the few-shot fine-tuning of the
learned models can significantly boost the prediction accuracy and partially
compensate for the feature distribution inconsistency at a small cost. After
the fine-tuning, we recorded the edit distance value between expected and
predicted output to be greater than 1 mostly for a small fraction of test
samples. The inspection of these test cases has shown that they contain
features that were not part of the grammar that we used to synthesize
input/output pairs, thus samples with similar sets of features were not
present in the training data. The only way to fix this issue is to populate
the grammar definition with new expansion rules. In contrast to the majority
of test data, a few test cases contained an unusual number of placeholder
tokens of a particular type. More on this will be discussed in the next
research question.

Modelizer requires that the training data (and hence, the synthesizing
grammar) covers the features found in the testing data.

In this evaluation, all models that had been trained on MathML Formulas used
as input or output (MathML to LaTeX, LaTeX to MathML, MathML to AsciiMath,
AsciiMath to MathML) have shown the lowest prediction accuracy. We treated
them as outliers and investigated the cause of failure. The reason for this is
the complexity of the MathML language and the lack of the corresponding test-
case features in the grammar we used for input generation. The MathML language
supports several operators and operands, including the different encodings for
the semantically same element. The grammar we used for the input generation
covers only a fraction of these features. Due to this fact, the custom
tokenizer also fails to parse these special cases. The better mapping of
operators and operands during the tokenization will help to resolve this
issue. While the MathML grammar was used for synthetic input generation and
the py-asciimath library was utilized for sequential conversion of first
MathML to LaTeX and then LaTeX to AsciiMath during the training dataset
formation, the accuracy of AsciiMath to LaTeX and LaTeX to AsciiMath models
were less impacted by the inconsistency of the vocabularies. The accuracy drop
was only caused by the lack of the specific unseen features, while the
encoding variations of the same operators got mapped to the same command by
the py-asciimath library in the LaTeX and AsciiMath representations, thus the
model’s vocabulary had already contained them. However, as the Table 3 also
depicts, the MathML models manage to learn the conversion behavior for the
synthesized test cases. We believe that alterations to the grammar and the
tokenization process will help to improve the accuracy of the learned models
for MathML Formulas.

In the performance evaluation, MathML is an outlier, due to the restricted
grammar used for input generation.

###  RQ3: Inverse Accuracy

We turn to RQ3 and evaluate the accuracy of Modelizer when predicting inputs
from outputs. We again refer to the prediction accuracy scores depicted in
Table 3 and representative results from both Table 4 and Table 5. In
particular, we are interested in HTML to Markdown, KQL to SQL, LaTeX to
PyExpression, and AsciiMath to LaTeX models. The numbers show that the inverse
model achieves a similar Exact Match accuracy, as their counterpart forward
conversion models. The BLEU Score values that we recorded for both forward and
inverse models are high and have insignificant margins between them. While the
models of the Pandoc and msticpy library achieve more than 90% accuracy in
both directions, the latexify-py and py-asciimath can produce fully correct
results in half of the cases. Between 20% to 35% of predictions require up to
4 edit operations, including token insertions and deletions, to correct the
prediction. Currently, Modelizer can automatically detect these failures using
the prediction validation mechanism discussed in Section 2.4. We plan to
integrate the automatic prediction repair mechanism in our future work.

Learning inverse models is as performant as learning mock models.

###  RQ4: Dataset Generation Time

Figure 5. Speed of Modelizer training data generation. This graph represents
the data generation time distribution for different subjects and training set
sizes. The x-axis represents the input types, and the y-axis represents the
time in minutes. Every training set size is represented by a different color.
For every input type, the generator was producing samples with fixed and
increasing complexity (partitioned).

Speed of Modelizer training data generation. This graph represents the data
generation time distribution for different subjects and training set sizes.
The x-axis represents the input types, and the y-axis represents the time in
minutes. Every training set size is represented by a different color. For
every input type, the generator was producing samples with fixed and
increasing complexity (partitioned).

We measured the performance of our input generation pipeline in forming a
tokenized training set of generated positive samples of data pairs. Our
generators can be configured to ignore all PUT runs when PUT fails to process
the synthesized input. In this evaluation, our generators we configured to
ensure that the number of requested and produced data pairs was equal.
Generation of MathML inputs was a special case, where the input generator was
executing the PUT twice to first produce LaTeX from MathML, and then AsciiMath
from LaTeX. The dataset generation time plotted on Figure 5 includes input
generation with grammar fuzzer, check for the uniqueness of produced input,
input processing with PUT, tokenization of both synthesized input and produced
output, and flushing the formatted dataset to the persistent storage. As
Figure 5 highlights, for the majority of subject and input generation strategy
combination pairs, it required 2-to-4 minutes to synthesize 10,000 samples,
1.5 to 2 hours to produce 250k samples, and more than 6 to 8 hours to produce
a dataset with 1,000,000 samples using an Ubuntu Linux workstation equipped
with AMD Ryzen Threadripper 3960X 24-Core processor and 256 GB of RAM. The
dataset generation time increases almost linearly according to the number of
included records. We also see that input generation with an increasing number
of non-terminal expansions takes from 0.3 to 2.5 times longer, and is on
average 44% slower. Also, we want to mention that by increasing the complexity
of synthesized inputs for SQL and MathML we started to get fewer input samples
that PUT can successfully process. While this can be seen as a desired effect
for stress testing the application, it significantly slows down the dataset
generation process if the end goal is to form a dataset containing only
positive samples.

1.5 to 2 hours are required to produce a mid-size dataset containing 250,000
samples using a multicore processor.

###  RQ5: Model Learning Time

Figure 6. Speed of Modelizer learning models from samples with a fixed and
increasing complexity (Partitioned). All model learning was done using a
single NVIDIA Geforce RTX 4090 GPU.

Speed of Modelizer learning models from samples with a fixed and increasing
complexity (Partitioned). All model learning was done using a single NVIDIA
Geforce RTX 4090 GPU.

According to timing records from the model learning log, it takes Modelizer
less than half an hour to learn a model from 10,000 synthesized training pairs
using NVIDIA RTX 4090 GPU. The similar models will be trained within 7 to 12
hours using a mid-size dataset with 250,000 training samples. Lastly, it takes
Modelizer 22 to 49 hours to train a model using a dataset with 1,000,000
records. Figure 6 demonstrates the model learning time distribution across
subjects from the evaluation set, training set sizes, and input generation
strategies. While an early program mock can be produced already within 30
minutes using a GPU, a significantly more accurate model will be trained
within 10 hours.

We also measured from 1% to 59% slowdown, with an average of 11%, while
training models containing inputs generated with fixed or increasing
complexity. The training time grows almost linearly with the increase of the
training set size, given the automatically discovered hyperparameter
configurations per subject from the evaluation set.

Training a Modelizer model can be done on a common PC in a few hours.

###  RQ6: Real-World Data

Our next research question is RQ6: How well do the _synthesized samples_
represent the real-world data?

The quality of synthesized samples depends on the presence and correctness of
the corresponding expansion rules that encode data-relevant features in the
grammar. We evaluated the quality of the synthesized samples by checking for
the inclusion of tokens collected from real-world samples into the
vocabularies of learned models. We have collected the following statistics per
data type used in our evaluation:

Markdown.:

One top-level element out of 12,783 contained a high number of URL
placeholders. Unfortunately, our generators, given the selected non-terminal
expansion configuration, have not produced sequences containing more than 51
URL declarations within 1 generation cycle. Thus, the corresponding
placeholders were not included in the model’s vocabulary, resulting in
encoding these tokens as “UNKNOWN” and the model’s inability to fully
correctly predict the output.

HTML.:

Similar to Markdown, in one of the top-level HTML elements we have observed
the absence of the same set of URL placeholders in the model’s vocabulary.
Additionally, from 9 more top-level elements a few extra HTML tags, like
`<head> </head> <title> </title>`, and meta attributes, like data-cites class,
were not seen during the data generation. During the data generation, we
filter out attributes that do not affect the semantics of the output data.
But, we have not manipulated the test data. Thus the model prediction could be
semantically correct but insignificantly differ from the reference sequence.

SQL.:

The test data contained 3 test cases that had been accessing more than 3
tables in a single query. The synthesized queries did not contain such complex
samples, which resulted in the model’s inability to produce a fully matching
prediction for these test cases.

KQL.:

2 out of 1,000 queries have accessed more than 3 tables in a single request
and used 1 additional feature not seen during the data generation. The model
cannot predict the output for these queries.

MathML Formulas.:

In 115 cases out of 1,000 formulas, the token sequence contained the unseen
operands and operators. This problem originates from the ability of the custom
tokenizer to parse and process these elements due to encoding and lack of the
corresponding parser rules. The grammar we have defined for the synthesis of
MathML Formulas does not cover all possible encodings for operators and
contains only a fraction of the special operand space. Due to this fact, the
custom tokenizer also fails to parse these special cases. While our tokenizer
already abstracts the numeric values and string literals with the
corresponding placeholders, we have not implemented the same abstraction
mechanism for the special operands. The better encoding and mapping of
operators will also help to represent such uncommon inputs without the
necessity to store them in the model’s vocabulary. The last issue is the
utilization of more than 18 identifiers within a single formula. To synthesize
such patterns the data generation configuration has to be changed.

LaTeX and AsciiMath Formulas.:

Similar to the MathML case we have detected the both larger than synthesized
number of enumerated placeholders and the presence of the unseen operands and
operators in the test data in 70 and 73 token sequences respectively.

Python and LaTeX Expressions.:

No unseen tokens were detected.

MathML to AsciiMath behavior mocking and vice-versa, and MathML to LaTeX
behavior mocking and vice-versa are representative demonstrations of a
correlation between the quality of the grammar used for input generation and
the accuracy of learned models. The more features are covered by the grammar,
the more program behavior gets tested and leaked, and the better model is
capable of accurately mocking the program behavior. A fully trained model
continuously failing to predict the output acts as a marker of the missing
features in the training data, thus in the input grammar. The failure can be
detected using a mechanism described in Section 2.4.

At this point, two scenarios are possible:

  * •

First, the grammar that has been used in the data generation process was an
estimate of the actual protocol specification, and it has to be refined
according to newly discovered features.

  * •

Second, the grammar follows the protocol specification, but the program
implementation does not. Then the learned model can be used as an oracle to
detect the program’s behavior deviation from the protocol specification.

In the case of predicting conversions of MathML Formulas to LaTeX and
AsciiMath representations, we demonstrated the necessity of the population of
the grammar with new features and improvements in the tokenization process.
Our study of the Pandoc markup converter with Modelizer detected a deviation
from the CommonMark Spec Version 0.29 (MacFarlane, 2019). Once we extended our
grammar declaration with Extended Markup Syntax, the model accuracy
significantly improved. Thus, we think that our models can detect behavior
deviations and can assist in the protocol specification refinement.

Altogether, we can conclude that the synthesizing data is suitable to form a
representative model vocabulary for the significant part of the real-world
data. However, according to the evaluation results that we observed, the
absence of feature distribution information encoded as part of grammar or
mined from real-world data at the synthesized time cannot guarantee accurate
model training. Still, the training with synthesized data allows learning
basic patterns and relationships between the input and output tokens, which
can be further fine-tuned on the real-world data using just a few
representative examples (few-shot training) to achieve the desired accuracy.

The performance of Modelizer depends on the accuracy and completeness of the
producing grammar.

###  RQ7: Usage of Synthetic Data

Our next research question is RQ7: How much synthetic data is required for the
behavior mocking of black-box programs? To answer these questions, we need to
distribute the training set sizes into three clusters:

Small:

consisting of 5k, 10k, and 50k samples;

Medium:

containing 100k, and 250k samples; and

Large:

with 500k and 1M samples.

The results are summarized in Table 4 and Table 5. We see that the best
results for models trained only on synthetic data were achieved with Medium-
sized models. They scored the highest number of Exact Matches while also
maintaining higher values for Close Matches and BLEU scores. However, after a
few-shot fine-tuning with real data, the best-performing models were trained
with Large datasets. Such a pattern is representative of half of the subjects
we tested. More aggregated statistics for the remaining subjects can be found
in Table 3.

Small and medium data sets suffice to obtain good Modelizer models.

###  RQ8: Generating Synthetic Data

Let us now go to RQ8: How should synthetic data be generated to achieve the
highest accuracy of the learned models? To answer this question, we are going
to explore the impact of the non-terminal expansion strategy on the accuracy
of the learned models and refer to the representative results of Markdown to
HTML conversion shown in Table 4 and HTML to Markdown conversion shown in
Table 5. As we can see, increasing the complexity of synthesized tokens does
not improve the conversion accuracy when the model is trained only on
synthetic data. When we fine-tuned the model on a small set number of
additional real-world samples that were not part of the test set, we measured
an insignificant increase in prediction accuracy.

Without providing the feature distribution by assigning expansion
probabilities, we assume the fuzzing budget gets wasted on randomly chosen
expansions that do not align with the feature patterns observed in the real-
world data. We can conclude that the efficient learning strategy would be to
generate the mid-size synthetic dataset with a fixed number of non-terminal
expansions, which, according to our results, is sufficient to cover the
feature mappings between input and output, and then perform a few-shot fine-
tuning on the real-world data, if available. This will achieve the highest or
almost the highest possible accuracy of the learned models while maintaining
the lowest possible time and resource consumption.

The highest Modelizer performance is obtained by combining a medium-sized
synthetic data set with fine-tuning on real-world data.

###  RQ9: Hyperparameters

Our next research question concerns _hyperparameters:_ How does Modelizer
learn the hyperparameters for each data pair combination?

While Modelizer makes no assumptions on the availability of the real-world
data at the training time, it still can perform _hyperparameter optimization._
For that, it needs a fixed set of test cases that are used to evaluate the
model’s performance by computing the cross-entropy loss function after every
search trial. The optimizer tries to minimize the value of the loss criterion
and prunes non-promising trials to further speed up the search process. In our
experiments, we reused the same set of test cases for forward and inverse
models, which allowed us to study the reusability of discovered
hyperparameters for the inverse models. Given the behavior mocking accuracy we
have observed during the evaluation of real-world data, we think that running
a hyperparameter parameter search on synthesized data is a suitable approach
for cases when sufficient quality and quantity of real-world inputs are not
available at the training time. According to the results of the hyperparameter
search in Table 6, the optimizer managed to find an individual configuration
for every translation pair type and the resulting number of model parameters
is small, ranging between 2.7 and 10 million parameters for the given
subjects.

Hyperparameter optimization is automatic and efficient.

Table 6. Automatically configured hyperparameter values using the Hyperparameter Search. Model |  Source Vocab Size |  Target Vocab Size |  Encoder Layers |  Decoder Layers |  Embedding Size |  Feedforward Size |  Attention Heads |  Learning Policy |  Learning Rate |  Weight Decay |  Dropout |  Clip Gradients |  Parameter Count
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Markdown HTML | 292 | 309 | 1 | 3 | 256 | 2048 | 32 | cosine | 0.0005 | 0.0100 | 0.0 | False | 6285621
HTML to Markdown | 309 | 292 | 1 | 3 | 256 | 2048 | 32 | step | 0.0001 | 0.0100 | 0.0 | False | 6281252
SQL to KQL | 674 | 675 | 1 | 2 | 256 | 2048 | 64 | cosine | 0.0001 | 0.0005 | 0.1 | True | 4992419
KQL to SQL | 675 | 674 | 1 | 1 | 256 | 2048 | 64 | cosine | 0.0001 | 0.0001 | 0.0 | False | 3413410
Expression to LaTeX | 1501 | 656 | 1 | 3 | 256 | 2048 | 16 | cosine | 0.0005 | 0.0005 | 0.1 | True | 6773136
LaTeX to Expression | 656 | 1501 | 1 | 1 | 256 | 1024 | 16 | multipl. | 0.0005 | 0.0005 | 0.0 | True | 2782173
AsciiMath LaTeX | 122 | 131 | 1 | 1 | 256 | 2048 | 32 | step | 0.0001 | 0.0100 | 0.1 | False | 2993283
LaTeX to AsciiMath | 131 | 122 | 1 | 4 | 256 | 2048 | 64 | step | 0.0001 | 0.0100 | 0.1 | False | 7727226
MathML to LaTeX | 174 | 131 | 1 | 4 | 256 | 1024 | 64 | cosine | 0.0001 | 0.0005 | 0.0 | False | 5116291
LaTeX to MathML | 131 | 174 | 1 | 3 | 256 | 4096 | 64 | cosine | 0.0001 | 0.0100 | 0.1 | False | 10377646
MathML to AsciiMath | 174 | 122 | 1 | 3 | 256 | 2048 | 64 | step | 0.0001 | 0.0100 | 0.0 | False | 6159482
AsciiMath to MathML | 122 | 174 | 1 | 2 | 256 | 1024 | 64 | step | 0.0001 | 0.0100 | 0.0 | False | 3018158

###  RQ10: Reusability of Hyperparameters

In this research question, we want to check the reusability of the
hyperparameters found with forward models for training the inverse models. To
answer this question, we need to take a look at the results of Hyperparameter
Search presented in Table 6. While the optimal embedding size value equal to
256 and the number of encoder layers equal to 1 were common for all input-
output pairs, the rest of the hyperparameters were different. Additionally, we
can mention that the best models were mainly trained with the lowest Learning
Rate value; Linear Layer Size has to be at least four times larger than the
Embedding Size; and, for the same data type pairs, inverse models require
mostly two times more decoder layers than forward models. We can conclude that
the hyperparameters for the forward models can serve as a lower bound for the
hyperparameter search for the inverse models.

Hyperparameters from forward models can be reused for inverse models.

###  RQ11: Effect of Placeholders

Let us now turn to the effect of design decisions, and start with RQ11: How
does the inclusion of additional enumerated placeholders into the model’s
input/output vocabularies impact behavior learning?

The inclusion of the additional enumerated tokens into both model’s
input/output vocabularies will impact the model’s configuration setup and
increase the number of required neurons. Since the training data does not
contain these injected tokens, the model will not be able to predict them.
Modelizer will deactivate dead neurons, and they will not be used for the
prediction. In cases, when the real-world samples contain the injected
placeholders, the corresponding neurons still can be revived using the model
fine-tuning. Such a technique is a cheap workaround to the problem of the
incompatible feature distribution between the training and prediction inputs,
when the input/output feature distribution is unknown at data generation time,
or the protocol specifications that PUT implements get changed over time
affecting only the quantity, but not the variety of these features. It helps
to either completely avoid or delay the necessity to retrain the model, which
is a time and resource-consuming process.

For several subjects that we tested like bidirectional conversion of the
AsciiMath formulas to the LaTeX representation and vice versa, the MathML
formulas to the AsciiMath representation and vice versa, MathML formulas to
the LaTeX representation, the quantity of the synthesized placeholders given
the used configuration of non-terminal nodes expansion for data generation was
insufficient to represent all symbolic values that can be found in the test
set. The preliminary oversizing of the vocabularies with the additional
placeholders helps to avoid the model’s failure to predict test cases that
contain unseen placeholders. Thus, if the selected hardware used for model
learning can tolerate the additional memory allocation caused by the inclusion
of additional placeholder tokens into the model’s vocabulary, we recommend
using this technique to handle the processing of previously unseen input and
output data, which is encoded with additional features, in a combination with
fine-tuning.

Placeholders can significantly improve Modelizer performance.

###  RQ12: Effect of Tokenizers

Let us turn to _tokenizers._ How should the model input/output be tokenized to
achieve the best learning performance? Should the pre-trained tokenizers used
instead of domain-specific tokenizers, considering the higher development
effort and cost?

The performance of the model is highly dependent on the quality of the
generated tokens. The more tokens encode the same input/output data the more
complex the model becomes, the more time it requires to produce the output,
and the higher the chance it has to fail predicting a correct token sequence.
Complex models require more powerful resources for functioning. At the same
time, having a very small vocabulary also limits the model’s capability to
learn a mapping between input and output correctly. In our work, we suggested
using domain-specific tokenizers, which are developed by the domain experts
and are capable of tokenizing the input/output data with the matching
granularity. The custom tokenization pipeline gives full control over the
tokenization process and allows to encoding of the input/output data in the
most suitable way. The custom tokenizers are also capable of handling domain-
specific data types and formats, which are not currently supported by the pre-
trained tokenizers.

Table 7.  Comparison of the tokenization quality between implemented domain-
specific tokenizers and selection of pre-trained tokenizers.

Subject | Tokenizer | Average Length | Vocab Size | Length Ratio | Vocab Ratio
---|---|---|---|---|---
| Custom | 12 | 176 | - | -
| BERT | 22 | 115 | 1.75 | 0.65
Markdown | Llama3 | 22 | 136 | 1.84 | 0.77
| Custom | 16 | 245 | - | -
| BERT | 49 | 178 | 3.10 | 0.73
HTML | Llama3 | 39 | 191 | 2.43 | 0.78
| Custom | 11 | 42 | - | -
| BERT | 20 | 38 | 1.93 | 0.90
SQL | Llama3 | 20 | 42 | 1.93 | 1
| Custom | 14 | 42 | - | -
| BERT | 26 | 41 | 1.89 | 0.98
KQL | Llama3 | 27 | 50 | 1.97 | 1.19
| Custom | 25 | 81 | - | -
| BERT | 47 | 102 | 1.87 | 1.26
Expression | Llama3 | 42 | 103 | 1.69 | 1.27
| Custom | 57 | 87 | - | -
| BERT | 90 | 108 | 1.58 | 1.24
LaTeX Expression | Llama3 | 66 | 148 | 1.16 | 1.7
| Custom | 151 | 101 | - | -
| BERT | 342 | 77 | 2.30 | 0.76
MathML | Llama3 | 296 | 101 | 1.99 | 1
| Custom | 27 | 104 | - | -
| BERT | 56 | 145 | 2.20 | 1.39
LaTeX Formula | Llama3 | 42 | 219 | 1.69 | 2.11
| Custom | 26 | 86 | - | -
| BERT | 51 | 111 | 2.14 | 1.29
AsciiMath | Llama3 | 39 | 229 | 1.66 | 2.66

The pre-trained tokenizers are shipped with the state-of-the-art NLP models
BERT and Llama3. Yellow cells ◼ indicate an evaluation run with a custom
domain-specific tokenizer, blue cells ◼ indicate the evaluation runs of the
BERT tokenizer, and purple cells ◼ indicate the evaluation runs of the Llama3
Tokenizer.

We compared the tokenization quality of the pre-trained tokenizers that are
shipped with the state-of-the-art NLP models BERT (Devlin et al., 2019) and
Llama3 (AI@Meta, 2024) with the domain-specific tokenizers that were
implemented for each subject. We have computed the average length of the
tokenized sequences and the vocabulary size per subject. To simplify the
comparison we derived additional metrics, the length ratio and vocabulary
ratio, which are computed as the ratio of the average length and vocabulary
size of the pre-trained tokenizer to the domain-specific tokenizer. The
results of our experiments are presented in Table 7. The evaluation was
conducted on 1000 real-world samples for each subject, except for Markdown and
HTML, where the tokenization was performed on all top-level elements extracted
from 100 real-world documents. All inputs that were processed by each
tokenizer were augmented by the _PlaceholderProcessor_ module, which replaced
the numeric and string literals with the matching placeholders.

While the pre-trained tokenizers managed to formulate a smaller vocabulary for
half of the evaluated subjects, the average length of the tokenized sequences
was significantly higher than the one produced by the domain-specific
tokenizers. We demonstrate an example of the tokenization of the HTML element
by the domain-specific and pre-trained tokenizers in Table 8. In this case,
the domain-specific tokenizer produces a sequence consisting of 18 tokens,
BERT produces 58 tokens, and Llama3 produces 48 tokens. Both BERT and Llama3
split the HTML tags and placeholders into multiple sub-tokens, which increases
the length of the tokenized sequence. The domain-specific tokenizer, on the
other hand, produces a shorter sequence of tokens that are more meaningful and
easier to interpret.

The results of the evaluation in Table 7 show that the domain-specific
tokenizers outperform the pre-trained tokenizers in terms of the average
length of the tokenized sequences. The pre-trained tokenizers, on the other
hand, do not require additional development effort, can tokenize multiple
subjects, and are easily interchangeable. We still think that, currently, the
domain-specific tokenizers can achieve better tokenization granularity, thus
they are more suitable for better-quality mocking. At the same, we think that
once a new type of pre-trained tokenizer that focuses on the tokenization of
the program-specific data is released, program behavior modeling will become
more accessible and easier to implement. Still, we currently suggest using the
pre-trained tokenizers as a lower bound for the domain-specific tokenizers.

By repeatedly analyzing the token vocabulary for the test set and using the
knowledge of domain experts and feedback from the PUT, one can potentially
quicker come up with a domain-specific tokenizer implementation that will
outperform the generic pre-trained tokenizers. We are currently working on the
automation of this process and plan to reduce the development cost and effort
of such tokenizers while keeping the tokenization quality high.

Table 8.  Example of the tokenization of the HTML element by the domain-specific and pre-trained tokenizers. Input |

    <p>TEXT_1<a href="URL_1">TEXT_2</a>TEXT_3<strong>
       TEXT_4</strong>TEXT_5<code>TEXT_6</code>TEXT_7</p>

---|---
Tokenizer | Tokens
Custom |

      <p>   TEXT_1   <a    href="URL_1"   >   TEXT_2   </a>
      TEXT_3   <strong>   TEXT_4   </strong>   TEXT_5
      <code>   TEXT_6   </code>   TEXT_7   </p>   \n

BERT |

      <   p   >   text   _   1   <   a   hr   ##ef   =   "
      ur   ##l   _   1   "   >   text   _   2   <   /   a   >
      text   _   3   <   strong   >   text   _   4   <   /
      strong      >   text   _   5   <   code   >   text   _
      6   <   /   code      >   text   _   7   <   /   p   >

Llama3 |

      <p   >   TEXT   _   1   <a   Ġhref   ="   URL   _   1
      ">   TEXT   _   2   </   a   >   TEXT   _   3   <strong   >
      TEXT   _   4   </   strong   >   TEXT   _   5   <   code   >
      TEXT   _   6   </   code   >   TEXT   _   7   </   p   >Ċ

Domain-specific tokenizers (as provided by output grammars) are better than
generic tokenizers.

##  5\. Limitations

In this section, we want to discuss the limitations of the Modelizer framework
and the current generation of sequence-to-sequence translation models. In
particular, we want to address the following limitations:

Stateless and Stateful Programs.:

In the current study, we have explored programs that implement deterministic
and stateless algorithms, including data format converters with recursive
descent parsers. Such programs fit the nature and functionality of sequence-
to-sequence models. In contrast, the modeling of stateful systems will require
tracing and encoding additional program states as a part of the input data.
Such a task implies further research and implementation of extensions to the
framework to identify the meaningful fraction of the program’s state
representation that should be used to model its behavior and the development
of efficient state encoding and tokenization algorithms. We assume that the
ability of the Modelizer framework to automatically validate and refine the
learned models in combination with reinforcement learning algorithms (Sutton
and Barto, 2018) will help to solve this problem. We plan to address this
research topic in our future work.

Computational Complexity.:

Modelizer, will not be able to create models for all sorts of programs. The
complexity of the whole program logic or its individual capabilities can be
too high to be modeled by the sequence-to-sequence models. The transformer
models themselves have a quadratic computational complexity. For the input
sequence length $n$, hidden dimension size $h$, and number of layers in the
neural network $L$, we get the following computational complexity:

$\textit{Time Complexity}:O\bigl{(}L\times(n^{2}d+nd^{2})\bigr{)}$
$\textit{Space Complexity}:O\bigl{(}L\times(n^{2}+nd^{2})\bigr{)}$

This means that modeling of extremely long input-output will be challenging
and impractical. The models that are learned by Modelizer are not intended to
replace programs. We see Modelizer as a tool that can help to understand the
behavior of the program and assist in the program testing and debugging.

Context Window Size.:

Similar to many Transformer-based systems, Modelizer is sensitive to the
length of the processed sequences. One of the factors that impact translation
accuracy is the synthesis of training sequences. The grammar-based fuzzers
used in the implementation of our Generators, by default, tend to produce
short sequences. To overcome this problem we have introduced the sliding non-
terminal expansion window, which partially resolves this issue. While the
total token quantity per input and output sequences reached values similar to
real-world samples, it does not guarantee a correlation for the input/output
feature distributions between synthesized and real-world samples. At the same
time, such a distribution can be learned from existing input samples
(Soremekun et al., 2022). This approach introduces three requirements: such
inputs have to be (1) available before input generation, (2) parsable with
selected grammar, and (3) the correct values have to be set for the minimal
and maximal number of non-terminal expansions in the generator. In the current
study, we intentionally have not followed this approach to check Modelizer’s
capabilities in learning behavior models of arbitrary systems given only the
formal specification of such systems.

Program-Specific Input Output Formats.:

Certain subjects, specifically the output data types like KQL, required the
implementation of custom parsers due to the unavailability of third-party
parsers at the time this publication was prepared. The implementation of such
parsers is a time-consuming and error-prone task. The third-party pre-trained
tokenizers suboptimally partition the corresponding sequences, by
unnecessarily splitting atomic tokens into sub-tokens similar to the
constructions that are found in natural language sequences, misinterpreting
certain characters like punctuation symbols, which cover part of the format
syntax. Partially, such an issue can be mitigated by defining custom post-
processing routines that will refine the outcome of the tokenization phase,
but, such a list of regular expressions and string replacement rules can
quickly become very long, create dependencies and conflicts in the order or
application, what makes them hard to maintain. Such measures do not simplify
the tokenization process but rather move the complexity from the tokenization
phase to the post-processing phase. While the custom subject-specific parser-
tokenizers are robust and produce high-quality tokens, we do not think that
automated model learning problems can benefit from this approach in the long
run, specifically for cases when complex system behavior has to be modelized
by chaining the behavior models of sub-systems. We think that such a domain-
specific tokenizer can be automatically created by wrapping existing
tokenization strategies like byte-pair encoding, word-piece, or sentence-piece
tokenization with a reinforcement learning loop. Alternatively, we are looking
forward to solutions that would be able to mine the input-output grammars from
the PUTs and automatically infer the parser-tokenizers from them.

Semantic Validity of Synthesized Inputs.:

Given the correct grammar definition, our generators which rely on grammar-
based fuzzers, are very efficient in producing syntactically correct inputs.
However, the PUT still can reject these inputs because grammar-based fuzzers
cannot guarantee that the generated input will be _semantically_ valid and
pass all parsing guards in the PUT. Thus, an additional refinement of the
synthesized data might be required. Steinhöfel et al. (Dominic Steinhöfel and
Andreas Zeller, 2022) have proposed a technique and a formal language that
allows manual specification of the semantic constraints inferred from the
system specification, domain knowledge, and human expertise. Their approach,
which builds on a modern Z3 SMT solver, can automatically refine the
semantically invalid inputs using encoded constraints. However, fuzzing with
semantic constraints is a computationally expensive task, and it slows down
the training dataset formation on a large scale. One type of inputs that we
synthesized, and which required such a refinement, were SQL queries with a
JOIN condition. Using our SQL grammar, the GrammarFuzzer was able to produce
SQL queries similar to the one given below:

`SELECT COLUMN FROM TABLE JOIN TABLE ON TABLE.COLUMN = TABLE.COLUMN`

Once PlaceholderProcessor updates all placeholders with unique identifiers the
query starts to look like this:

`SELECT COLUMN_1 FROM TABLE_1 JOIN TABLE_2 ON TABLE_3.COLUMN_2 =
TABLE_4.COLUMN_3`

The refined query is semantically invalid. To overcome this issue, we
implemented an additional string refinement step, which parses the synthesized
input and corrects the identifiers. While such an additional refinement step
requires a bit of manual effort, for simple cases like this, it adds an
insignificant performance penalty to the input generation process. Thus, the
current implementation of the Modelizer framework does not support fuzzing
with constraint solving, but we plan to support this functionality in future
releases.

Some of the identified limitations can be resolved in the future releases of
Modelizer.

##  6\. Related Work

The evolution of language models and their integration into existing projects
and solutions have opened new horizons in automating routine tasks and
processes (Chen et al., 2021; Ziegler et al., 2022). The so-called general-
purpose large language models (LLMs) like Llama 2 (Touvron et al., 2023) or T5
(Raffel et al., 2020) have been adapted to process code-related tasks by fine-
tuning on a huge corpus of publicly available source codes and documentation
(Code Llama (Rozière et al., 2024) or CodeT5 (Wang et al., 2021)). Such
optimized code-specific models can be further fine-tuned on code generation
and understanding downstream tasks. Below we discuss the most relevant
applications of neural models in the context of program behavior modeling and
the challenges they face:

Behavior Mocking.:

There have already been previous attempts to perform behavior mocking by
training sequence-to-sequence neural networks. TransCoder (Roziere et al.,
2020) represents two sequence-to-sequence models for cross-language
translations of code written in C++, Java, and Python with additional support
for back translations. Armengol-Estape et al. (Armengol-Estapé and O’Boyle,
2022) train transformer models to replicate the behavior of the GCC compiler.
The training data is obtained by selecting C functions from the Anghabench
benchmark and compiling them to x86 assembly code. The learned models can
correctly compile the C code in less than half of the cases, making replacing
compilers with neural machine Translation models invisible in practice.
Zaremba et al., in their “Learning To Execute” publication (Zaremba and
Sutskever, 2015), try to predict the execution results of short Python
programs performing simple arithmetic operations and echo printing by training
an LSTM (Hochreiter and Schmidhuber, 1997) model of a Python interpreter on a
set of synthesized programs. These works have shown that the current
generation of neural network architectures cannot correctly learn the full
behavior of such complex programs as compilers or interpreters. While learned
models cannot fully replace complex programs, our approach has demonstrated
promising results in modeling linear or linearithmic programs. In contrast to
previous approaches that rely on sequence-to-sequence models to achieve
behavior mocking, Shen. et al and their Konure (Shen and Rinard, 2021) system
relies on the active learning approach to mine the behavior model of
applications that interact with relational databases. Konure synthesizes
inputs with database content simultaneously, monitors the traffic exchange
between the database and the application, and inspects the results of the
database queries to continuously refine the application behavior hypothesis.
Using the refined application model, Konure can generate the Python code for
database querying that is semantically equivalent to the original application
code, which might be written in a different programming language. Similar to
Konure, our approach learns the program models from the input-output pairs.
While Konure is designed to model the database interaction behavior of
applications, our approach does not have such a limitation and can be used to
either model the behavior of the whole system or its components and individual
functionality.

Reversing Computation.:

Neural machine translation techniques have also shown promising results in
low-level code decompilation tasks. Such neural decompilers are either
implemented as sequence-to-sequence (Katz et al., 2018; Liang et al., 2021)
sequence-to-tree (Fu et al., 2019; Cao et al., 2022) models. While existing
works focus on converting the program’s binary representation to high-level
program code, our framework allows users to reverse the direction of
computation (predict the program input that was used to produce a given
output) by training a behavioral model of the inverse program. This result is
achieved by simply swapping training data pairs, i.e., using program output as
model input and program input as model output. Even though such an inverse
program may not exist, our approach still allows framework users to estimate
the result of an inverse computation. Meanwhile, the approaches proposed by
Katz et al. in the TRAFIX framework (Katz et al., 2019) and Fu et al., in the
N-Bref framework (Fu et al., 2021), suggest training a neural decompiler from
generated data. We think that these works are the closest to ours. In
contrast, our framework supports behavior modeling of arbitrary programs,
learning both direct and inverse models of the selected PUT, and supports
further generalization of the learning process from mapping finite input-
output pairs to extracting common input properties and constraints.

Data and Model Poisoning.:

Language models trained from crowd-sourced data suffer from data poisoning
problems. In their research, Pearce et al. (Pearce et al., 2022) have studied
the impact of training dataset poisoning on the quality of language model
predictions. Code-generation models still tend to generate buggy or malicious
code snippets because they have been trained on very similar corpora of
publicly available documents. Schuster et al. (Schuster et al., 2021) have
demonstrated two types of attacks on generative models: data poisoning and
model poisoning. In the first scenario, only a few specially crafted samples,
which are added to the training corpus, are sufficient to enforce code
generation models to produce malicious code snippets. Alternatively, such
models can be attacked by manipulating the training parameters (weights) or
fine-tuning them on a few malicious samples. Both attack strategies will
result in a deviation of generated sequences, and existing defense measures
against dataset poisoning attacks cannot mitigate the problem completely (Wan
et al., 2022; He and Vechev, 2023). Due to the possibility of manipulating
model behavior, the model outcome cannot be trusted, and their application in
mission-critical systems is still questionable. In contrast to other
approaches that rely on crowd-sourced training data, our framework allows full
control over the data collection and model training processes through the
specification of input synthesis rules, testing of generated samples with the
PUT, and filtration or sanitization of faulty, undesired, and dangerous
samples.

Domain-specific Adaptations.:

Due to the reason that such domain-specific models were fine-tuned only on the
program source codes, they cannot capture the program behavior patterns
without further fine-tuning. Such fine-tuning could be an expensive process
due to the sizes of models and specific hardware requirements. Zheng et al.
and their LlamaFactory citezheng2024llamafactory framework provide estimated
memory requirements implied in fine-tuning open-source LLMs. For example, the
small versions of commonly used LLMs, like Llama2, Llama3, and Mixtral, with
7-to-8 billion parameters require more than 60GB of memory for full-precision
fine-tuning. Even though models are open-source, it is mostly impossible to
fine-tune them locally without access to data-center-grade hardware. Instead,
our framework can learn “lightweight” program behavior models consisting of
only several million parameters and can be trained on commodity hardware.

Neural Program Induction.:

We find that the neural program induction and neural program synthesis fields
are also closely related to our research. While neural program induction
models (Joulin and Mikolov, 2015; Devlin et al., 2017a; Neelakantan et al.,
2016; Graves et al., 2014; Zaremba et al., 2016; Kurach et al., 2016) try to
train a sequence-to-sequence generative model that learns data patterns from
input-output examples, neural program synthesis (Vijayakumar et al., 2018;
Devlin et al., 2017b; Shin et al., 2019) use neural networks for predicting
algorithms from corresponding input-output samples. Existing studies cannot
capture the behavior of complex algorithms and programs because they had been
relying on already outdated neural network architectures; they could not
generalize to arbitrary complex inputs because the corresponding models had
been trained on a limited number of training samples, which, for certain
studies are in human-generated; require the additional manual modeling and
encoding of the algorithm or program in a domain-specific language that has
limited functionality. Recent advances in sequence-to-sequence prediction
algorithms (Transformer architecture and its variations) make it possible to
automatically infer complex data patterns from input-output pairs. Moreover,
our approach can also automatically learn the inverse patterns, which allows
the revision of the computation results of certain programs at a small cost.

AI-driven Testing.:

AI-driven, or specifically LLM-driven software testing is becoming more and
more popular. We picked a few representative works from myriads of
publications in this field to highlight the s TOGA (Dinella et al., 2022)
project explores neural test oracle generation problem by fine-tuning the
CodeBERT (Feng et al., 2020) model on automated inference of exceptional and
assertion oracles from developer-written tests. Haluptzok et al. (Haluptzok et
al., 2023) synthesize and solve Python programming puzzles using language
models. The authors of DeepAnalyze (Shetty et al., 2022) learned a sequence
labeling model to automatically mark memory frames in a stack trace that
caused the crash of an application. The LIBRO (Kang et al., 2023) framework
uses the Codex Large Language Model to generate and rank bug-reproducing test
cases from bug reports. Tufano et al. (Tufano et al., 2019) train a neural
machine translation model to automatically replicate in 36% of cases the
changes between pull requests in code repositories like bug fixes or code
refactoring. The DeepFix (Gupta et al., 2017) approach randomly mutates
correct programs to introduce errors. It uses these data pairs to train the
neural machine translation model for automated program repair, which succeeds
in fixing buggy programs in 27% of cases. The Break-It-Fix-It (Yasunaga and
Liang, 2021) approach achieves high accuracy in code repair tasks by chaining
two generative neural machine translation models for synthesizing naturally
looking code errors and training a fixer model from synthesized pairs.
Godefroid et al., in their “Learn&Fuzz” publication (Godefroid et al., 2017),
learn a generative model for PDF structures by training a recurrent neural
network from a set of PDF objects. The input sequence is represented by a
sequence of characters in PDF objects, while the output sequence is obtained
by shifting the corresponding input sequence by one character. While every
mentioned work follows its unique approach, they all require a significant
amount of human effort for problem-solving. In contrast, Modelizer tries to
automate the process of data collection (which is one of the most time-
consuming parts of model preparation) and model training. The minimalistic set
of requirements, in particular the ability to run a Python interpreter
locally, simplifies the integration of the learned models into the existing
projects and testing tools.

AI-generated Synthetic Data:

The capabilities of LLMs revealed several approaches of their application for
synthetic data generation (Li et al., 2023). They can generate human-like text
or dialogues given the prompt query, augment existing datasets by producing
variations of the original data, and produce structured representations of
existing data like JSON or CSV. Such AI-generated synthetic data is mostly
used for training classifiers or question-answering systems. For example,
general-purpose LLMs like OpenAI ChatGPT or Google Bard have shown promising
results (İrfan AYGÜN, 2023) in generating synthetic data in a medical text
production task. However, in certain tasks, like hateful speech detection and
classification, the inclusion of syntactically generated samples to the
training set does not improve the performance of classifiers (Kruschwitz and
Schmidhuber, 2024). Still, it is an active and promising field of research,
and industry giants like Nvidia invest in the development of LLMs, like
Nemotron-4 (Nvidia et al., 2024), specifically designed for synthetic data
generation. While synthetic data generation with LLMs implies specific
hardware requirements to run models locally or lead to a privacy compromise
while processing the data with a third-party cloud provider at an additional
service cost, our approach that relies on synthesizing data with grammar
fuzzers only requires a system with an ability to run a Python interpreter
locally.

Data Generation by Mutating Inputs:

We also want to address the alternatives to grammar-based and AI-based input
generation strategies. Potentially, an input set for the given PUT can be
automatically constructed with the help of mutation-based fuzz-testing (Barton
P. Miller et al., 1990). A mutation fuzzer, like AFL++ (Andrea Fioraldi et
al., 2020), can accept one input for a PUT as an initial seed and produce
infinitely many new inputs by applying pre-defined mutation strategies, like
bit flips, addition, or subtraction of integers, on different parts of the
given seed. Such a technique produces two types of mutants. The first type of
mutants has a broken syntactical or semantic structure. These mutants will
either crash the PUT if it contains a bug in its implementation, or the input
parser guards will reject such input, and program execution will be
terminated. The collected input-output pairs will only cover the behavior of
the input parser rather than the whole program. In most cases, the second type
of mutants, which would have managed to bypass the parser guards, will contain
insignificant differences when compared to an initial input sample. Thus,
testing the program with this kind of input will unlikely produce a diverse
set of outputs. While fuzz testing is helpful for bug discovery in the
implementations of input parsers, we do not think the mutation-based input
generation technique is applicable to automate program behavior modeling.

Mining Input Grammars:

In certain cases, input grammars can also be automatically mined from a PUT.
The _Mimid_ approach by Gopinath et al. (Rahul Gopinath et al., 2020) relies
on the program instrumentation in combination with string wrappers to identify
the respective control flow nodes that access the relevant portions of a
program input. Kulkarni et al. presented the _Arvada_ algorithm (Kulkarni et
al., 2021) that can automatically learn a highly recursive CFG from a given
program using a set of positive examples and a Boolean-valued oracle.
Currently, if input specifications are not publicly available or are not
recoverable from the PUT, then the user of our framework has to encode it in
CFG format manually.

##  7\. Conclusion and Future Work

With Modelizer, we provide a principled approach to turning regular programs
into models. This opens up the manifold capabilities of machine learning
models for several Software Engineering tasks such as mocking, testing, and
debugging. The maybe most promising feature of the learned translation models
is their ability to predict inputs for given outputs, not only reversing
executions but also offering new opportunities for test input generation. We
see Modelizer as a pioneer in _project-specific learning_ —rather than trying
to generate expensive LLMs that may or may not evolve into a one-size-fits-
all, Modelizer demonstrates that it is possible to learn small models for
nontrivial programs that can successfully replicate their behavior—and their
reverse.

Besides testing Modelizer with more complex programs and larger model sizes,
our future work on Modelizer will focus on further applications, as well as
addressing some of its current limitations. Specifically:

Targeted input generation.:

One of the most promising applications of Modelizer is its use for test input
generation. By treating _traces_ or _coverage_ as _output_ of the PUT (and
supplying an output grammar that can parse trace logs), Modelizer can learn
which input features correlate with which traces or coverage features; and can
then again predict which input would be required to achieve a particular trace
or coverage. These inputs could then be tested automatically, and if the trace
or coverage deviates, such feedback could be used to fine-tune the model (see
below).

Monitoring.:

Once Modelizer has extracted a model, one can also use it for _monitoring_ the
PUT, continuously comparing the program behavior against the extracted model.
This could be used to detect and prevent behavior not seen during testing.

Debugging.:

By learning correlations between collected crash data (core dumps and stack
traces) and input features, Modelizer could predict inputs and input features
likely to have caused a given program state.

Smarter test generation.:

In our evaluation, we have found again and again that the performance of
Modelizer very much depends on the quality and diversity of the synthesized
training data, and thus on the quality of the test generator. In our future
work, we will experiment with smarter black-box test generators, covering
grammar features and combinations thereof (Havrikov and Zeller, 2020), but
also smarter _grey-box fuzzing,_ using code coverage in the PUT as guidance
(Pham et al., 2019; Aschermann et al., 2019).

Stateful programs.:

At this point, the models extracted by Modelizer do not consider the internal
state, as, say, a server could maintain. Let us assume the PUT starts in a
known initial state, and the input to the PUT is a sequence of commands. Then,
having Modelizer learn the effects of command sequences should also give it
the ability to detect that certain outputs depend on specific subsequences of
commands (implying a specific state). Such reasoning will likely require
larger models; we plan to evaluate Modelizer on more complex and stateful
programs.

Feature distribution.:

The _feature distribution_ in the synthesized samples does not always