# Learning-Based Automatic Synthesis of Software Code and Configuration

Shantanu Mandal
Texas A&M University
<EMAIL_ADDRESS>
###### Abstract

Increasing demands in software industry and scarcity of software engineers
motivates researchers and practitioners to automate the process of software
generation and configuration. Large scale automatic software generation and
configuration is a very complex and challenging task. In this proposal, we set
out to investigate this problem by breaking down automatic software generation
and configuration into two different tasks. In first task, we propose to
synthesize software automatically with input output specifications. This task
is further broken down into two sub-tasks. The first sub-task is about
synthesizing programs with a genetic algorithm which is driven by a neural
network based fitness function trained with program traces and specifications.
For the second sub-task, we formulate program synthesis as a continuous
optimization problem and synthesize programs with covariance matrix adaption
evolutionary strategy (a state-of-the-art continuous optimization method).
Finally, for the second task, we propose to synthesize configurations of large
scale software from different input files (e.g. software manuals,
configurations files, online blogs, etc.) using a sequence-to-sequence deep
learning mechanism.

##  1 Introduction

Automation of software generation and configuration is a well studied research
problem. However, due to the complexity of the problem, there is a wide gap to
fill to improve the process of automatic generation of software code and
configuration. Recently, there has been notable progress in machine learning
for different complex tasks. In search related problems, machine learning is
heavily used due to it’s incredible pattern recognition characteristics from
past trained data. The trained model then helps to prune the search space
significantly. Since automatic software generation is a search problem, we
integrate machine learning-based approach to tackle the issue as our first
task. For the second task, we formulate software configuration synthesis as a
sequence-to-sequence natural language-based synthesis problem to extract
configuration specifications.

We first formulate the problem of our first task. Let
$S^{t}=\\{(I_{j},O^{t}_{j})\\}^{m}_{j=1}$ be a set of $m$ input-output pairs,
such that the output $O_{j}^{t}$ is obtained by executing the program $P^{t}$
on the input $I_{j}$. Inherently, the set $S^{t}$ of input-output examples
describes the behavior of the program $P^{t}$. We would like to synthesize a
program $P^{t^{\prime}}$ that recovers the same functionality of $P^{t}$.
However, $P^{t}$ is usually unknown, and we are left with the set $S^{t}$,
which was obtained by running $P^{t}$. Based on this assumption, we define
equivalency between two programs as follows:

######  Definition 1.1 (Program Equivalency).

Programs $P^{a}$ and $P^{b}$ are equivalent under the set
$S=\\{(I_{j},O_{j})\\}^{m}_{j=1}$ of input-output examples if and only if
$P^{a}(I_{j})=P^{b}(I_{j})=O_{j}$, for $1\leq j\leq m$. We denote the
equivalency by $P^{a}\equiv_{S}P^{b}$.

Definition 1.1 suggests that to obtain a program equivalent to $P^{t}$, we
need to synthesize a program that is consistent with the set $S^{t}$.
Therefore, our goal is to find a program $P^{t^{\prime}}$ that is equivalent
to the target program $P^{t}$ (which was used to generate $S^{t}$), i.e.,
$P^{t^{\prime}}\equiv_{S^{t}}P^{t}$. This task is known as Inductive Program
Synthesis (IPS). As suggested by [1], a machine learning-based solution to the
IPS problem requires definition of two components. First, we need a
programming language that defines the domain of valid programs. Second, we
need a method to search over the program domain. The search method sweeps over
the program domain to find $P^{t^{\prime}}$ that satisfies the equivalency
property.

We divide the first research task into two sub-tasks. In the first sub-task,
we set out to use an off-the-self genetic algorithm for program synthesis. A
genetic algorithm requires a ranking function to rank all the solutions so
that the best ones can be chosen to analyze further. We propose to use a
trained neural network as a ranking function. Note that a _genetic algorithm_
(GA) is a machine learning technique that attempts to solve a problem from a
pool of candidate solutions. These generated candidates are iteratively
evolved and mutated and selected for survival based on ranking function, often
referred to as the _fitness function_. Fitness functions are usually hand-
crafted heuristics that grade the approximate correctness of candidate
solutions such that those that are closer to being correct are more likely to
appear in subsequent generations. Designing simple and effective fitness
functions is a unique challenge for GA. Despite many successful applications
of GA, it still remains an open challenge to automate the generation of such
fitness functions. An impediment to this goal is that fitness function
complexity tends to increase proportionally with the problem being solved.
With program synthesis being a particularly complex problem, generating a good
fitness function is a daunting challenge. To solve this, we propose to explore
an approach to automatically generate a fitness function by representing their
structure with a neural network.

For the second sub-task, we formulate the searching process of program
synthesis from discrete domain to continuous domain and propose to solve it as
a continuous optimization problem. Suppose a program $P$, consisting of $l$
tokens (instructions or functions), is denoted by
$P=\left<P_{1},...,P_{l}\right>$, where $P_{i}$ represents the $i$-th token
for $1\leq i\leq l$. $P_{i}$ can be any token from the set of all possible
tokens, $\Sigma_{\mathit{DSL}}$. Instead of a discrete search process, we set
out to investigate if an approach can be developed to map $P$ into continuous
parameters that does not require any learned encoding for the formulation.
Towards that end, we propose a novel formulation, where $P$ can be expressed
as $P=\left<f_{1}(\cdot),f_{2}(\cdot),\dots,f_{M}(\cdot)\right>$. Here, each
$f_{i}(\cdot)$, for $1\leq i\leq M$, is a function that takes a number of
continuous parameters as inputs and maps them into some tokens in $P$. With
this formulation, an error function that compares the output produced by $P$
(for a specified input) with the specified output, essentially becomes a
function of continuous parameters. Therefore, the problem of program synthesis
amounts to minimizing the error function. In other words, program synthesis
becomes a continuous optimization problem where the goal is to minimize the
error function. We propose to solve this continuous optimization problem using
Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Commonly used error
functions for comparing program outputs, such as edit or Manhattan distance
[2, 3, 4], are non-smooth and ill-conditioned, i.e., a small change in the
input can produce a large error. Therefore, CMA-ES is perfectly suited to
solve such cases. It is a stochastic derivative-free algorithm for difficult
(e.g., non-convex, ill-conditioned, multi-modal, rugged, noisy, etc.)
optimization problems and considered as one of the most advanced optimization
algorithms.

Finally, we formulate the problem of our second task - configuration
synthesis. Every large scale software takes some inputs to configure them.
These inputs are crucial and can vary across different software. Configuring
software with invalid inputs can lead to software failures. Sometimes these
inputs are not checked inside the software rather are specified in some
software manuals or other places (such as readme files, online blogs, etc.).
Based on the use cases, admins configure the software. However, invalid
configurations can lead to software failures. Thus, it is important to
automatically generate specification sets from configurations to prevent
software misconfiguration failure. Due to the unstructured format of the input
files, it is hard to extract configuration constraints automatically. To
tackle this problem, we propose a system that uses natural language-based
machine learning model to automatically extract configuration constraints from
different input files.

##  2 Task 1: Automatic Software Synthesis

In Task 1, we propose to synthesize programs automatically that satisfy some
specifications. We approach this problem in two different ways. We use
discrete search process and a continuous search process. They are described in
the following sections as sub-task 1 and 2. These sub-tasks are named as
NetSyn[2] and Genesys[5].

###  2.1 Sub-Task 1: NetSyn

Here, we describe our proposed solution to synthesize programs with a genetic
algorithm (GA) and a trained neural network used as a fitness function in GA.
We name our solution as NetSyn. In the following sections, we will first
describe the domain specific language that we use, the GA search process, how
we learn the fitness function, and finally, the auxiliary local neighborhood
search.

####  2.1.1 Domain Specific Language

As NetSyn’s programming language, we choose a domain specific language (DSL)
constructed specifically for it. This choice allows us to constrain the
program space by restricting the operations used by our solution. NetSyn’s DSL
follows the DeepCoder’s DSL [1], which was inspired by SQL and LINQ [6]. The
only data types in the language are _(i)_ integers and _(ii)_ lists of
integers. The DSL contains 41 functions, each taking one or two arguments and
returning one output. Many of these functions include operations for list
manipulation. Likewise, some operations also require lambda functions. There
is no explicit control flow (conditionals or looping) in the DSL. However,
several of the operations are high-level functions and are implemented using
such control flow structures. A full description of the DSL can be found in
the supplementary material. With these data types and operations, we define a
program $P$ as a sequence of functions. Table 1 presents an example of a
program of 4 instructions with an input and respective output.

Arguments to functions are not specified via named variables. Instead, each
function uses the output of the previously executed function that produces the
type of output that is used as the input to the next function. The first
function of each program uses the provided input $I$. If $I$ has a type
mismatch, default values are used (i.e., 0 for integers and an empty list for
a list of integers). The final output of a programs is the output of its last
function.

Table 1: An example program of length 4 with an input and corresponding
output.

[int] | Input:
---|---
Filter ($>$0) | $[-2,10,3,-4,5,2]$
Map (*2) |
Sort | Output:
Reverse | $[20,10,6,4]$

As a whole, NetSyn’s DSL is novel and amenable to genetic algorithms. The
language is defined such that all possible programs are _valid by
construction_. This makes the whole program space valid and is important to
facilitate the search of programs by any learning method. In particular, this
is very useful in evolutionary process in genetic algorithms. When genetic
crossover occurs between two programs or mutation occurs within a single
program, the resulting program will _always_ be valid. This eliminates the
need for pruning to identify valid programs.

Figure 1: Overview of NetSyn. Phase 1 automates the fitness function
generation by training a neural network on a corpus of example programs and
their inputs and outputs. Phase 2 finds the target program for a given input-
output example using the trained neural network as a fitness function in a
genetic algorithm.

####  2.1.2 Search Process

NetSyn synthesizes a program by searching the program space with a genetic
algorithm-based method [7]. It does this by creating a population of random
genes (i.e., candidate programs) of a given length $L$ and uses a learned
neural network-based fitness function (NN-FF) to estimate the fitness of each
gene. Higher graded genes are preferentially selected for crossover and
mutation to produce the next generation of genes. In general, NetSyn uses this
process to evolve the genes from one generation to the next until it discovers
a correct candidate program as verified by the input-output examples. From
time to time, NetSyn takes the top $N$ scoring genes from the population,
determines their neighborhoods, and looks for the target program using a local
proximity search. If a correctly generated program is not found within the
neighborhoods, the evolutionary process resumes. Figure 1 summarizes the
NetSyn’s search process.

We use a value encoding approach for each gene. A gene $\zeta$ is represented
as a sequence of values from $\Sigma_{\mathit{DSL}}$, the set of functions.
Formally, a gene $\zeta=\left(f_{1},\dots,f_{i},\dots,f_{L}\right)$, where
$f_{i}\in\Sigma_{\mathit{DSL}}{}$. Practically, each $f_{i}$ contains an
identifier (or index) corresponding to one of the DSL functions. The encoding
scheme satisfies a one-to-one match between programs and genes.

The search process begins with a set $\Phi^{0}$ of $|\Phi^{0}|=T$ randomly
generated programs. If a program equivalent to the target program $P^{t}$ is
found, the search process stops. Otherwise, the genes are ranked using a
learned NN-FF. A small percentage (e.g., 20%) of the top graded genes in
$\Phi^{j}$ are passed in an unmodified fashion to the next generation
$\Phi^{j+1}$ for the next evolutionary phase. This guarantees that some of the
top graded genes are identically preserved, aiding in forward progress
guarantees. The remaining genes of the new generation $\Phi^{j+1}$ are created
through crossover or mutation with some probability. For crossover, two genes
from $\Phi^{j}$ are selected using the Roulette Wheel algorithm with the
crossover point selected randomly [8]. For mutation, one gene is Roulette
Wheel selected and the mutation point $k$ in that gene is selected based on
the same learned NN-FF. The selected value $z_{k}$ is mutated to some other
random value $z^{\prime}$ such that $z^{\prime}\in\Sigma_{\mathit{DSL}}{}$ and
$z^{\prime}\neq z_{k}$.

Crossovers and mutations can occasionally lead to a new gene with dead code.
To address this issue, we eliminate dead code. Dead code elimination (DCE) is
a classic compiler technique to remove code from a program that has no effect
on the program’s output [9]. Dead code is possible in our list DSL if the
output of a statement is never used. We implemented DCE in NetSyn by tracking
the input/output dependencies between statements and eliminating those
statements whose outputs are never used. NetSyn uses DCE during candidate
program generation and during crossover/mutation to ensure that the effective
length of the program is not less than the target program length due to the
presence of dead code. If dead code is present, we repeat crossover and
mutation until a gene without dead code is produced.

Figure 2: Neural network fitness function for (a) single and (b) multiple IO
examples. In each figure, layers of LSTM encoders are used to combine multiple
inputs into hidden vectors for the next layer. Final fitness score is produced
by the fully connected layer.

####  2.1.3 Learning the Fitness Function

Evolving the population of genes in a genetic algorithm requires a fitness
function to rank the fitness (quality) of genes based on the problem being
solved. Ideally, a fitness function should measure how close a gene is to the
solution. Namely, it should measure how close a candidate program is to an
equivalent of $P^{t}$ under $S^{t}$. Finding a good fitness function is of
great importance to reduce the number of steps in reaching the solution and
directing the algorithm in the right direction so that genetic algorithm are
more likely to find $P^{t}$.

Intuition: A fitness function, often, is handcrafted to approximate some ideal
function that is impossible (due to incomplete knowledge about the solution)
or too computationally intensive to implement in practice. For example, if we
knew $P^{t}$ beforehand, we could have designed an ideal fitness function that
compares a candidate program with $P^{t}$ and calculates some metric of
closeness (e.g., edit distance, the number of common functions etc.) as the
fitness score. Since we do not know $P^{t}$, we cannot implement the ideal
fitness function. Instead, in this work, we propose to approximate the ideal
fitness function by learning it from training data (generated from a number of
known programs). For this purpose, we use a neural network model. We train it
with the goal of predicting the values of an ideal fitness function. We call
such an ideal fitness function (that would always give the correct answer with
respect to the actual solution) the _oracle_ fitness function as it is
impossible to achieve in practice merely by examining input-output examples.
In this case, our models will not be able to approach the 100% accuracy of the
_oracle_ but rather will still have sufficiently high enough accuracy to allow
the genetic algorithm to make forward progress. Also, we note that the trained
model needs to generalize to predict for any unavailable solution and not a
single specific target case.

Given the input-output samples
$S^{t}=\left\\{\left(I_{j},O_{j}^{t}\right)\right\\}_{j}$ of the target
program $P^{t}$ and an ideal fitness function $fit(\cdot)$, we would like a
model that predicts the fitness value $fit(\zeta,P^{t})$ for a gene $\zeta$.
In practice, our model predicts the values of $fit(\cdot)$ from input-output
samples in $S^{t}$ and from execution traces of the program $P^{\zeta}$
(corresponding to $\zeta$) by running with those inputs. Intuitively,
execution traces provide insights of whether the program $P^{\zeta}$ is on the
right track.

In NetSyn, we use a neural network to model the fitness function, referred to
as NN-FF. This task requires us to generate a training dataset of programs
with respective input-output samples. To train the NN-FF, we randomly generate
a set of example programs, $E=\left\\{P^{e_{j}}\right\\}$, along with a set of
random inputs $I^{j}=\\{I_{i}^{e_{j}}\\}$ per program $P^{e_{j}}$. We then
execute each program $P^{e_{j}}$ in $E$ with its corresponding input set
$I^{j}$ to calculate the output set $O^{j}$. Additionally, for each
$P^{e_{j}}$ in $E$, we randomly generate another program
$P^{r_{j}}=(f^{r_{j}}_{1},f^{r_{j}}_{2},...,f^{r_{j}}_{n})$, where
$f^{r_{j}}_{k}$ is a function from the DSL i.e.,
$f^{r_{j}}_{k}\in\leavevmode\nobreak\ \Sigma_{\mathit{DSL}}{}$. We apply the
previously generated input $I_{i}^{e_{j}}$ to $P^{r}_{j}$ to get an execution
trace, $T^{rj}_{i}=(t^{rj}_{i1},t^{rj}_{i2},...,t^{rj}_{in})$, where
$t^{rj}_{ik}=f^{rj}_{k}(t^{rj}_{i(k-1)})$ with
$t^{rj}_{i1}=f^{rj}_{1}(I_{i}^{e_{j}})$ and
$t^{rj}_{in}=f^{rj}_{n}(t^{rj}_{i(n-1)})=P^{r_{j}}(I_{i}^{e_{j}})$. Thus, the
input set $I^{j}=\\{I^{e_{j}}_{i}\\}$ of the program $P^{e_{j}}$ produces a
set of traces $T^{j}=\\{T^{r_{j}}_{i}\\}$ from the program $P^{r_{j}}$. We
then compare the programs $P^{r_{j}}$ and $P^{e_{j}}$ to calculate the fitness
value and use it as an example to train the neural network.

In NetSyn, the inputs of NN-FF consist of input-output examples, generated
programs, and their execution traces. Let us consider a single input-output
example, $(I^{e_{j}}_{i},O^{e_{j}}_{i})$. Let us assume that $P^{e_{j}}$ is
the target program that NetSyn attempts to generate and in the process, it
generates $P^{r_{j}}$ as a potential equivalent. NN-FF uses $(I^{e_{j}}_{i}$,
$O^{e_{j}}_{i})$, and $\\{(f^{r_{j}}_{k},t^{r_{j}}_{ik})\\}$ as inputs for
this example. Each of $(I^{e_{j}}_{i}$, $O^{e_{j}}_{i})$, and $t^{r_{j}}_{ik}$
are passed through an embedding layer followed by an LSTM encoder.
$f^{r_{j}}_{k}$ is passed as a one-hot-encoding vector. Figure 2(a) shows the
details of how a single input-output example is processed. Two layers of LSTM
encoders combines the vectors to produce a single vector, $H^{j}_{i}$. In
order to handle a set of input-output examples,
$\\{(I^{e_{j}}_{i},O^{e_{j}}_{i})\\}$, a set of execution traces,
$T^{j}=\\{T^{r_{j}}_{i}\\}$, is collected from a single generated program,
$P^{r_{j}}$. Each input-output example, $(I^{e_{j}}_{i},O^{e_{j}}_{i})$, along
with the corresponding execution trace produces a single vector, $H^{j}_{i}$.
An LSTM encoder combines such vectors to produce a single vector, which is
then processed by fully connected layers to predict the fitness value (Figure
2(b)).

Example: To illustrate, suppose the program in Table 1 is in $E$. Let us
assume that $P^{r_{j}}$ is another program {[int], Filter ($>$0), Map (*2),
Reverse, Drop (2)}. If we use the input in Table 1 (i.e., $[-2,10,3,-4,5,2]$)
with $P^{r_{j}}$, the execution trace is $\left\\{[10,3,5,2]\right.$,
$[20,6,10,4]$, $[4,10,6,20]$, $\left.[6,20]\right\\}$. So, the input of NN-FF
is {$[-2,10,3,-4,5,2],[20,10,6,4]$, $Filter_{v}$, $[10,3,5,2]$, $Map_{v}$,
$[20,6,10,4]$, $Reverse_{v}$, $[4,10,6,20]$, $Drop_{v}$, $[6,20]$}. $f_{v}$
indicates the value corresponding to the function $f$.

There are different ways to quantify how close two programs are to one
another. Each of these different methods then has an associated metric and
ideal fitness value. We investigated three such metrics – common functions,
longest common subsequence, and function probability – which we use as the
expected predicted output for the NN-FF.

Common Functions:  NetSyn can use the number of common functions (CF) between
$P^{\zeta}$ and $P^{t}$ as a fitness value for $\zeta$. In other words, the
fitness value of $\zeta$ is
$f^{CF}_{P^{t}}(\zeta)=|\mathbf{elems}(P^{\zeta})\cap\mathbf{elems}(P^{t})|$.
For the earlier example, $f^{CF}$ will be 3. Since the output of the neural
network will be an integer from 0 to $\mathbf{len}(P_{t})$, the neural network
can be designed as a multiclass classifier with a softmax layer as the final
layer.

Longest Common Subsequence:  As an alternative to CF, we can use longest
common subsequence (LCS) between $P^{\zeta}$ and $P^{t}$. The fitness score of
$\zeta$ is
$f^{LCS}_{P^{t}}(\zeta)=\mathbf{len}(\mathit{LCS}(P^{\zeta},P^{t}))$. Similar
to CF, training data can be constructed from $E$ which is then fed into a
neural network-based multiclass classifier. For the earlier example, $f^{LCS}$
will be 2.

Function Probability:  The work [1] proposed a probability map for the
functions in the DSL. Let us assume that the probability map $\mathbf{p}$ is
defined as the probability of each DSL operation to be in $P^{t}$ given the
input-output samples. Namely,
$\mathbf{p}=(p_{1},\dots,p_{k},\dots,p_{|\Sigma_{\mathit{DSL}}{}|})$ such that
$p_{k}=Prob(\mathrm{op}_{k}\in\mathbf{elems}(P^{t})|\\{(I_{j},O^{t}_{j})\\}^{m}_{j=1})$,
where $\mathrm{op}_{k}$ is the $k^{th}$ operation in the DSL. Then, a
multiclass, multilabel neural network classifier with sigmoid activation
functions used in the output of the last layer can be used to predict the
probability map. Training data can be constructed for the neural network using
$E$. We can use the probability map to calculate the fitness score of $\zeta$
as
$f^{FP}_{P^{t}}(\zeta)=\sum_{k:\mathrm{op}_{k}\in\mathbf{elems}(P^{\zeta})}p_{k}$.
NetSyn also uses the probability map to guide the mutation process. For
example, instead of mutating a function $z_{k}$ with $z^{\prime}$ that is
selected randomly, NetSyn can select $z^{\prime}$ using Roulette Wheel
algorithm using the probability map.

####  2.1.4 Local Neighborhood Search

Neighborhood search (NS) checks some candidate genes in the neighborhood of
the $N$ top scoring genes from the genetic algorithm. The intuition behind NS
is that if the target program $P^{t}$ is in that neighborhood, NetSyn may be
able to find it without relying on the genetic algorithm, which would likely
result in a faster synthesis time.

Let us assume that NetSyn has completed $l$ generations. Then, let
$\mu_{l-w+1,l}$ denote the average fitness score of genes for the last $w$
generations (i.e., from $l-w+1$ to $l$) and $\mu_{1,l-w}$ will denote the
average fitness score before the last $w$ generations (i.e., from $1$ to
$l-w$). Here, $w$ is the sliding window. NetSyn invokes NS if
$\mu_{l-w+1,l}\leq\mu_{1,l-w}$. The rationale is that under these conditions,
the search procedure has not produced improved genes for the last $w$
generations (i.e., saturating). Therefore, it should check if the neighborhood
contains any program equivalent to $P^{t}$.

Input: A set $G$ of top $N$ scoring genes

Output: $P^{t^{\prime}}$, if found, or _Not found_ otherwise

1 for  _Each $\zeta\in G$_ do

2 $NH\leftarrow\emptyset$

3 for  _$i\leftarrow 1\leavevmode\nobreak\ \mathbf{to\leavevmode\nobreak\
len}(\zeta)$_ do

4 for  _$j\leftarrow 1\leavevmode\nobreak\ \mathbf{to}|\Sigma_{DSL}|$_ do

5 $\zeta_{n}\leftarrow\zeta\leavevmode\nobreak\ with\leavevmode\nobreak\
\zeta_{i}\leavevmode\nobreak\ replaced\leavevmode\nobreak\
with\leavevmode\nobreak\ \mathrm{op}_{j}$ $\leavevmode\nobreak\
\leavevmode\nobreak\ such\leavevmode\nobreak\ that\leavevmode\nobreak\
\zeta_{i}\neq\mathrm{op}_{j}$

6 $NH\leftarrow NH\cup\\{\zeta_{n}\\}$

7

8 if  _there is $P^{t^{\prime}}\in NH$ such that
$P^{t^{\prime}}\equiv_{S^{t}}P^{t}$_ then

9 return _$P^{t^{\prime}}$_

10

return _Not found_

Algorithm 1 Defines and searches neighborhood based on BFS principle

Neighborhood Definition:  Algorithm 1 shows how to define and search a
neighborhood. The algorithm is inspired by the breadth first search (BFS)
method. For each top scoring gene $\zeta$, NetSyn considers one function at a
time starting from the first operation of the gene to the last one. Each
selected operation is replaced with all other operations from
$\Sigma_{\mathit{DSL}}{}$, and inserts the resultant genes into the
neighborhood set $NH$. If a program $P^{t^{\prime}}$ equivalent to $P^{t}$ is
found in $NH$, NetSyn stops there and returns the solution. Otherwise, it
continues the search and returns to the genetic algorithm. The complexity of
the search is
$\mathcal{O}(N\cdot\mathbf{len}(\zeta)\cdot|\Sigma_{\mathit{DSL}}{}|)$, which
is significantly smaller than the exponential search space used by a
traditional BFS algorithm. Similar to BFS, NetSyn can define and search the
neighborhood using an approach similar to depth first search (DFS). It is
similar to Algorithm 1 except $i$ keeps track of depth here. After the loop in
line 4 finishes, NetSyn picks the best scoring gene from $NH$ to replace
$\zeta$ before going to the next level of depth. The algorithmic complexity
remains the same.

###  2.2 Sub-Task 2: GeneSys

Here we propose our solution to synthesize programs with continuous
optimization technique. We call this solution as Genesys. In the following
sections we will describe how we formulate the program synthesis problem as a
continuous optimization problem. We use covariance matrix adaptive
evolutionary technique, in short CMA-ES. In part of that we will describe
different mapping schemes that we propose to incorporate the problem into CMA-
ES and different restart policies. We use the same DSL described in 2.1.1.

####  2.2.1 Program Synthesis as a Continuous Optimization Problem - A Novel
Formulation

We propose to model a program as an $l$-tuple, where each element of the tuple
is a function of continuous parameters. Intuitively, each function takes one
or more continuous parameters and maps them to $0$ or more DSL tokens in the
program. Let us consider a program $P$. It can be expressed as
$P=\left<f_{1}(x^{1}_{1},...,x^{1}_{M}),...,f_{N}(x^{N}_{1},...,x^{N}_{M})\right>$
where,
$f_{i}(x^{i}_{1},...,x^{i}_{M}):\mathbb{R}^{M}\rightarrow\Sigma_{\mathit{DSL}}^{C_{i}}$
for $1\leq i\leq N$, $0\leq C_{i}\leq l$, and $N,M>0$. Namely, each function
$f_{i}$ maps $M$ continuous random variables into $C_{i}$ DSL tokens in the
program. When $C_{i}=0$, it indicates the special case when $f_{i}$ does not
map its parameters to any DSL token. In other words, $f_{i}$ becomes a NULL
function. Figure 3(a) shows the mapping from the continuous variables to DSL
tokens. Since the length of the program $P$ is $l$, we can infer
$\Sigma_{i}C_{i}=l$.

Figure 3: Pictorial representation of how (a) each function maps the
continuous parameters to DSL tokens in the program and (b) the error function
maps the continuous parameters.w

We define an error over the given specification, $S=\\{(I_{j},O_{j})\\}$ as
$\mathbb{E}(P,S)=\left<E(P(I_{j}),O_{j})\right>^{s}_{j=1}$. Here,
$E(P(I_{j}),O_{j})$ could be any commonly used distance function in program
synthesis such as edit distance, Manhattan distance, etc. [10]. With the
formulation of $P$ as an $l$-tuple, $\mathbb{E}$ becomes a function mapping
$\mathbb{R}^{M\times N}$ to $\mathbb{R}^{s}$. Therefore, program synthesis
becomes a continuous optimization problem where the goal is to find values of
$M\times N$ continuous random variables that minimize $\mathbb{E}$ (i.e., the
minimum point in the $s$-dimensional space). Figure 3(b) depicts this
formulation.

####  2.2.2 Mapping Schemes

Based on the problem formulation in the prior Section, we propose a number of
novel mapping schemes for Genesys. Each scheme maps one or more continuous
random variables to $0$ or more DSL tokens of a program. Genesys uses these
mapping schemes to convert random variable samples to actual programs during
the CMA-ES algorithm. Figure 4 summarizes the pictorial illustration of
different mapping schemes and their characteristics.

Figure 4: Representation of different mapping schemes.

##### Single Group Mapping:

In this design, we choose $|\Sigma_{\mathit{DSL}}|$ functions to express an
$l$-length program, $P$. Each function represents a DSL token and takes one
continuous parameter. Each function will map its parameter to at most one DSL
token. Thus,
$P=\left<f_{1}(x^{1}_{1}),f_{2}(x^{2}_{1}),\dots,f_{|\Sigma_{\mathit{DSL}}|}(x^{|\Sigma_{\mathit{DSL}}|}_{1})\right>$
where $f_{i}(x^{i}_{1}):\mathbb{R}\rightarrow\Sigma_{\mathit{DSL}}^{0|1}$.
Genesys samples each continuous parameter and then constructs the program by
choosing the tokens corresponding to the $l$ largest sampled values. The token
for the largest sampled value occurs first in the program. The token
corresponding to the next largest value occurs second, and so on. This is
shown in Figure 2(a). A consequence of this approach is that each DSL token
could occur at most once in a program. Moreover, the mapping scheme is not
applicable if the length of the program, $l$ is larger than
$|\Sigma_{\mathit{DSL}}|$. The formal definition of $f_{i}$ and the
corresponding selection of program token is as follows:

$\displaystyle f_{i}(x^{i}_{1})$
$\displaystyle=\begin{cases}D_{i}&\mathrm{if}\,x^{i}_{1}=Top_{j}\left(\\{x^{i}_{1}\\}^{|\Sigma_{\mathit{DSL}}|}_{i=1}\right)\,\,\,\mathrm{for}\,\,1\leq
j\leq l\\\ None&otherwise\end{cases}$ $\displaystyle P_{j}$
$\displaystyle=D_{i}\quad\qquad when\leavevmode\nobreak\
f_{i}(x^{i}_{1})=D_{i},$

where $Top_{j}(ST)$ indicates the $j$-th top element of the set, $ST$. $None$
indicates that $f_{i}$ does not map its parameter to any DSL token. This
scheme is a very basic mapping scheme. Here a DSL token can not be used more
than once while constructing a program.

##### Multi-Group Mapping:

In this mapping, Genesys uses $l$ functions, each taking
$|\Sigma_{\mathit{DSL}}|$ continuous parameters to express the program $P$.
Each position in the program is thus represented by one function. Each
parameter of that function corresponds to a DSL token. Genesys samples the
continuous parameters of the first function and selects the largest sampled
parameter. The corresponding DSL token becomes the first token in $P$. Then,
Genesys samples the parameters of the second function and the token
corresponding to the largest sampled parameter becomes the second token in
$P$. This process repeats for each of the $l$ functions. This is shown in
Figure 2(b). The formal definition of $f_{i}$ and the corresponding selection
of program token is as follows:

$\displaystyle f_{i}(x^{i}_{1},\dots,x^{i}_{|\Sigma_{\mathit{DSL}}|})$
$\displaystyle=D_{j}\quad\mathrm{if}\,\,x^{i}_{j}=Top_{1}\left(\\{x^{i}_{j}\\}^{|\Sigma_{\mathit{DSL}}|}_{j=1}\right)$
$\displaystyle P_{i}$ $\displaystyle=D_{j}.$

This mapping scheme is flexible in the sense it allows a DSL token to be used
multiple times in a program. Thus, it is more robust than Single Group Mapping
scheme but it requires a larger number of variables to represent a program.

##### Dynamic Multi-Group Mapping:

In multi-group mapping, we have $l$ functions, each taking
$|\Sigma_{\mathit{DSL}}|$ continuous parameters and choosing one DSL token for
$P$, whereas in single group mapping, we have $|\Sigma_{\mathit{DSL}}|$
functions, each taking one continuous parameter and choosing at most one DSL
token for $P$. Dynamic multi-group mapping is a hybrid scheme between single
and multi-group mapping. Here, we have $k$ functions, each taking
$|\Sigma_{\mathit{DSL}}|$ continuous parameters and choosing
$\nicefrac{{l}}{{k}}$ DSL tokens for $P$. Genesys randomly chooses $k$ for
each program. Each function uses single group mapping scheme to choose
$\nicefrac{{l}}{{k}}$ DSL tokens. This is shown in Figure 2(c). This mapping
gives Genesys the flexibility to find out the best group setup by evolving.
The formal definition of $f_{i}(\cdot)$ and the corresponding selection of
program token is as follows:

$\displaystyle f_{i}(x^{i}_{1},\dots,x^{i}_{|\Sigma_{\mathit{DSL}}|})$
$\displaystyle=\left\\{D_{j}|\leavevmode\nobreak\
x^{i}_{j}=Top_{\frac{l}{k}}\left(\\{x^{i}_{j}\\}^{|\Sigma_{\mathit{DSL}}|}_{j=1}\right)\right\\}$
$\displaystyle P_{(i-1)\frac{l}{k}+t}$
$\displaystyle=D_{j}\quad\mathrm{if}\,\,x^{i}_{j}=Top_{t}\left(\\{x^{i}_{j}\\}^{|\Sigma_{\mathit{DSL}}|}_{j=1}\right)\quad\mathrm{for}\,\,1\leq
t\leq\frac{l}{k}.$

Here, Genesys can decide the number of groups to construct a program. Although
Genesys can decide the number of groups, it always requires same number of
variables as Multi-Group Mapping in addition to the group variable. Hence,
this schemes requires more variables than any other schemes.

##### Bin Mapping:

In bin mapping, we choose $l$ functions to construct an $l$-length program
$P$. Each function takes one continuous parameter. Thus,
$P=\left<f_{1}(x^{1}_{1}),f_{2}(x^{2}_{1}),\dots,f_{l}(x^{l}_{1})\right>$
where $f_{i}(x^{i}_{1}):\mathbb{R}\rightarrow\Sigma_{\mathit{DSL}}$. Each
function $f_{i}$ must be able to map the continuous parameter to one of the
DSL tokens. This is shown in Figure 2(d). We conceptually divide the range of
each variable into $|\Sigma_{\mathit{DSL}}|$ bins. The size of each bin can be
equal (except the bin at each end) or proportional to the probability of the
corresponding token being present in the program $P$. Prior work [2, 1] showed
how to infer such probability. When Genesys samples from the continuous
variables to create a candidate program, it takes each real sampled value and
determines into which of the bins the value falls. The token used in that
position in the candidate program is the one corresponding to the bin number
into which the sampled value fell. This sampling process occurs for each of
the $l$ continuous parameters. Thus, the definition of $f_{i}$ and the
corresponding selection of program token is as follows:

$\displaystyle f_{i}(x^{i}_{1})$
$\displaystyle=D_{j}\qquad\mathrm{if}\leavevmode\nobreak\ x^{i}_{1}\in
Bin_{D_{j}}\leavevmode\nobreak\ \mathrm{for}\leavevmode\nobreak\ 1\leq
j\leq|\Sigma_{\mathit{DSL}}|$ $\displaystyle P_{i}$ $\displaystyle=D_{j},$

where $Bin_{D_{j}}$ represents the range of values corresponding to token
$D_{j}$, and $P_{i}$ represents the $i$-th token of program $P$. This mapping
scheme is more robust and flexible compared to the other mapping schemes. It
requires the less number of variables to represent a program. This makes the
optimization problem easier and helps Genesys to find more programs within a
fixed time budget.

##### Dynamic Bin Mapping:

With prior mapping schemes, Genesys can synthesize programs of a particular
length. However, it is possible to find a program of a lower length (than the
length of the target program) that also satisfies the given specification. To
accommodate such programs, we propose dynamic bin mapping scheme which uses
one function to choose the length and other functions to choose the DSL
tokens. Thus, we have $l+1$ functions each taking one continuous parameter.
Function $f_{l+1}$ maps its parameter to a program length at which Genesys
will synthesize a program. To do this, we conceptually divide the range of
$x_{l+1}^{0}$ into $l$ equal sized bins. When Genesys samples this parameter,
it determines which bin the parameter’s value fall into. The length
corresponding to that bin is chosen as the program length. Earlier functions
(up to that length) map their continuous parameters into one DSL token each
based on the bin mapping idea. This is shown in Figure 2(e). The formal
definition is as follows:

$\displaystyle f_{i}(x^{i}_{1})$
$\displaystyle=D_{j}\qquad\mathrm{if}\leavevmode\nobreak\ x^{i}_{1}\in
Bin_{D_{j}}\leavevmode\nobreak\ \mathrm{and}\leavevmode\nobreak\
x^{l+1}_{1}\in Bin_{k}$
$\displaystyle\qquad\qquad\mathrm{for}\leavevmode\nobreak\ 1\leq
j\leq|\Sigma_{\mathit{DSL}}|\leavevmode\nobreak\
\mathrm{and}\leavevmode\nobreak\ 1\leq k\leq l\leavevmode\nobreak\
\mathrm{and}\leavevmode\nobreak\ i\leq k$ $\displaystyle P_{i}$
$\displaystyle=D_{j},$

This mapping scheme can represent variable length program instead of always
constructing the highest length program. However, synthesis rate can be lower
if length is not accurate.

####  2.2.3 Restart Policy

Genesys can stop its evolutionary process when the potential solutions are
converging due to some local minima. This is checked by determining if a
change in one or multiple axes does not affect the distribution mean, or if
the condition number of the covariance matrix is too high (i.e., ill-
conditioned), or the evolutionary path’s step size is too small to reach the
solution [11]. To escape from such situation, we investigate several restart
policies where Genesys restarts with fresh initial parameters. We explore all
policies resulting from the combinations of 3 core restart policies:
population-based (PB), mean-based (MB), and covariance matrix-based (CB). For
the PB restart, Genesys doubles the size of the population from its previous
size. For the MB restart policy, Genesys resets the mean vector to randomly
initialized values (using the uniform random distribution) after a restart
instead of keeping its current value. For the CB restart policy, Genesys re-
initializes the covariance matrix to the identity matrix after a restart
instead of keeping its current values. Additional restart policies can be
constructed by any combination of these core restart policies. Some of these
combinations have been proposed in earlier work such as IPOP [12] and BIPOP
[13] where they re-initialize mean vector, covariance matrix, and increase
population size simultaneously.

Figure 5: Overview of Genesys.

####  2.2.4 Putting It All Together

Genesys follows the high level workflow shown in Figure 5. Genesys starts by
initializing a multivariate normal distribution and the population size. The
continuous variables of the distribution are determined based on the choice of
a mapping scheme. Any of the mapping schemes in Section 2.2.2 can be used. In
each generation, Genesys samples $\lambda$ points from the multivariate
distribution and maps each sample to a program. Each of these candidate
programs could potentially be the solution. Therefore, Genesys applies the
error function $\mathbb{E}$. The error function essentially applies inputs
from the given specification to a candidate program and checks if the produced
output matches with the given output specification. If the outputs match, the
candidate program is returned as the solution. Otherwise, Genesys checks if
convergence has reached. If not, Genesys updates the mean, covariance matrix
and distribution path based on the error function and starts a new generation.
If, on the other hand, convergence is reached, Genesys applies a restart
policy and repeats the whole process with new parameters. The synthesis
process continues until a maximum time limit has passed or a solution is
found.

##  3 Task 2: Automatic Configuration Synthesis

In Task 2, we propose to extract configuration constraints for software
automatically from textual flies such as manuals, readme files, online blogs,
etc.

##### Background and motivation:

Large scale software synthesis is very challenging. One needs to tackle many
small problems to synthesis a large scale software. Configuration synthesis is
a big part of it. Configuration, also known as specification, defines how a
software will be set up and run in the system. Mis-configuration of a software
can lead to failures during runtime. It makes a system unreliable and often,
difficult to maintain. Thus configuring the software with correct parameters
is very important.

Now a days, almost all large scale software comes with many configuration
parameters. As a result, manually setting up those configurations can be
error-prone. An automatic system needs to be placed that prevents mis-
configuration. Usually these configuration constraints are written in large
scale software manuals. Sometime there can also be found in input files,
special configuration file, system environment file, online blogs, etc. Going
through all these files automatically and extracting specifications is very
challenging. In this work, we explore automatic configuration extraction from
different unstructured software manuals. We refer to this work as ConfigSyn.

Category | Specification | Example
---|---|---
Value | $p==v$ | Set this value greater than 2000
| $p<v|p>v$ |
| $p\in\\{v,v^{\prime}\\}$ |
Correlation | $with(p,p^{\prime})$ |  $p$ lower than $p^{\prime}$ not ideal
Usage | $use(p)$ | this option is useful for diagnostic purpose
Property | $format(p,f)$ | best to specify $p$ as an absolute path

Table 2: Category of specifications and their examples.

##### Example of specifications:

We categorize software configuration specification into 4 categories. Table 2
shows the category with specification and their examples. This specifications
can be written in software manuals or any online group. For example, let us
assume that specification $p$ needs to be within two value $on$ or $off$. If
someone configures $p$ with a value different from $on,off$, the software will
be mis-configured that can lead to a crash. The goal of our proposed ConfigSyn
is to collect the specification of $p$ by analyzing the software manuals or
other input sources. And this specification can be used as a rule checker
during the configuration of the software.

Software | Number of Configuration Parameter
---|---
Mysql | 1453
Httpd | 372
Hadoop | 132
CentOs | 407

Table 3: Number of configuration parameters of different software.

##### Data collection:

We choose to synthesize configurations for Mysql, Httpd, Hadoop, and CentOS.
To do this, we first collect the software manual for these four software. We
go through the manual and collect all the configuration parameters. Table 3
shows the number of configuration parameters for each of the software. Then,
we collect configuration-related raw data set mainly from two sources. First,
we go through each of the sentences of the manual and if any of the
configuration keyword has been found we collect that sentence assuming this
sentence may contain specifications related to this parameter. Then, we build
a crawler to go through different Stackoverflow[14] posts. Stackoverflow is a
developer website where people submit different questions related to software
and other people answer those questions. It has a lot of posts related to
configuration bugs and their solutions. The crawler collects those posts and
makes a database. This database contains raw texts that hold different
specifications of the configurations. As these texts are all written in a
natural language (e.g., English), we use a deep learning model to extract the
specifications automatically.

##### Model:

We formulate this problem as a sequence-to-sequence translation problem. For
specification modeling, we use a transformer-based [15] end-to-end encoder-
decoder model to synthesize configuration specifications. As the configuration
is described in a natural language, we first encode the natural texts with an
encoder into a latent representation. Then, on the decoder side if any
configuration is present in the texts, that is decoded automatically. For
example, sentence set the port_num to any value greater than 2000 has
configuration specification as port_num > 2000. Now, we can train a model
which encodes the sentence set the port_num to any value greater than 2000
into some latent representation and the decoder will take it and decode to
port_num > 2000.

##### Transformer model:

For the core modeling of our dataset, we use the Transformer-based [15]
sequence-to-sequence model. This model achieves the state-of-the-art
performance on various machine translation-based work. It significantly
outperforms other models (such as RNN, LSTM, etc.) that rely on recurrence-
based calculations. The transformer based model is an encoder-decoder based
model that harnesses the power of attention mechanism. There are two parts in
transformer-based model. One is encoder and another is decoder. First the
input goes through the embedding layer to make token embedding for each of the
input tokens. Positions of each token are represented by positional embedding.
Token embedding and positional embedding are merged together and go through
multi-head attention mechanism. Attention mechanism finds correlation between
each of the tokens that are passed to the encoder. The purpose of the encoder
is to convert the inputs into some latent representation. This latent
representation is passed to the decoder part of the transformer model. Decoder
takes the latent representation from the encoder and a start symbol. It
continuously pops out an output token until it sees the end token or maximum
length is reached. Basically, the decoder gives all tokens’ probabilities
through the softmax layer. The token with the highest probability is taken as
the output token.

##  4 Related work

Program synthesis has been widely studied with various applications. _Formal
program synthesis_ uses formal and rule based methods to generate programs[16,
17]. Formal program synthesis usually guarantees some program properties by
evaluating a generated program’s semantics against a corresponding
specification [18, 19]. In [20], authors use a SMT based solver to find
different constraints in the program and learn useful lemma that helps to
prune away large parts of the search space to synthesize programs faster.
However, these techniques can often be limited by exponentially increasing
computational overhead that grows with the program’s instruction size [21, 22,
23, 24, 25].

Another way to formal methods for program synthesis is to use machine learning
(ML). Machine learning differs from traditional formal program synthesis in
that it generally does not provide correctness guarantees. Instead, ML-driven
program synthesis approaches are usually only _probabilistically_ correct,
i.e., their results are derived from sample data relying on statistical
significance [26]. Such ML approaches tend to explore software program
generation using an objective function. Objective functions are used to guide
an ML system’s exploration of a problem space to find a solution. Other deep
learning based program synthesizer [27, 28, 29] also tried different
approaches such as reinforcement learning to solve the problem. Most of these
works focus on synthesizing programs in domain specific languages, such as
FlashFill [30, 31] for string transformation problem, simulated robot
navigation, such as Karel [32, 33] or LIST manipulation [2, 1, 34, 35, 36, 20]
work.

Among the ML-based program synthesis, in Deepcoder[1], the authors train a
neural network with input-output examples to predict the probabilities of the
functions that are most likely to be used in a program. Raychev et al. [37]
take a different approach and use an n-gram model to predict the functions
that are most likely to complete a partially constructed program. Robustfill
[30] encodes input-output examples using a series of recurrent neural networks
(RNN), and generates the the program using another RNN one token at a time.
Bunel et al. [38] explore a unique approach that combines reinforcement
learning (RL) with a supervised model to find semantically correct programs.
These are only a few of the works in the program synthesis space using neural
networks [2, 39, 40, 41, 42].

Significant research has been done in the field of genetic programming [4, 43,
44] too, where the goal is to find a solution in the form of a complete or
partial program for a given specification. Prior work in this field has tended
to focus on either the representation of programs or operators during the
evolution process. Real et al. [45] recently demonstrated that genetic
algorithms can generate accurate image classifiers. Their approach produced a
state-of-the-art classifier for CIFAR-10 [46] and ImageNet [47] datasets.
Moreover, genetic algorithms have been exploited to successfully automate the
neural architecture optimization process [48, 49, 50, 51, 52].

However, all these works formulate program synthesis as a search problem of
discrete parameters. On the other hand, NetSyn tries to formulate program
synthesis as a continuous optimization problem and uses a well established
derivative free method, CMA-ES, to solve it. Previously, CMA-ES was used in
machine learning [53], aerospace engineering [54], mechanical engineering
[55], health [56] and various other engineering fields [57] but not in the
field of synthesizing complex programs.

In addition, researchers engage in extensive analysis of configuration files
in order to mitigate the occurrence of software misconfigurations. The
prevention of such misconfigurations holds various significances for ensuring
software reliability. Therefore, researchers dedicate their efforts towards
identifying configurations valid rules and bounds (e.g., specifications), with
the aim of preventing software misconfigurations [58, 59, 60].

##  5 Conclusion

We propose automatic synthesis of software code and configuration constraints
as two major tasks for the automation of software generation process. We sub
divide the software synthesis task into two major sub-tasks that explore the
synthesis with discrete and continuous search techniques. On the other hand,
we propose to use a state-of-the-art natural language model for configuration
specification extraction. We believe our approaches in each of the tasks open
up potential other research directions to explore.

## References

  * [1] M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow.  DeepCoder: Learning to Write Programs.  In International Conference on Learning Representations, April 2017\.
  * [2] Shantanu Mandal, Todd Anderson, Javier Turek, Justin Gottschlich, Shengtian Zhou, and Abdullah Muzahid.  Learning fitness functions for machine programming.  In A. Smola, A. Dimakis, and I. Stoica, editors, Proceedings of Machine Learning and Systems, volume 3, pages 139–155, 2021.
  * [3] Kory Becker and Justin Gottschlich.  AI Programmer: Autonomously Creating Software Programs Using Genetic Algorithms.  CoRR, abs/1709.05703, 2017.
  * [4] T. Perkis.  Stack-based genetic programming.  In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, pages 148–153 vol.1, 1994.
  * [5] Shantanu Mandal, Todd A. Anderson, Javier Turek, Justin Gottschlich, and Abdullah Muzahid.  Synthesizing programs with continuous optimization, 2022.  arXiv 2211.00828.
  * [6] Kulkarni Dinesh, Bolognese Luca, Warren Matt, Hejlsberg Anders, and George Kit.  LINQ to SQL: .NET Language-Integrated Query for Relational Data, 2007\.
  * [7] Thomas.  Global Optimization Algorithms-Theory and Application.  2009\.  http://www.it-weise.de/projects/book.pdf.
  * [8] David E. Goldberg.  Genetic Algorithms in Search, Optimization and Machine Learning.  Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989.
  * [9] Saumya K. Debray, William Evans, Robert Muth, and Bjorn De Sutter.  Compiler Techniques for Code Compaction.  ACM Trans. Program. Lang. Syst., 22(2):378–415, March 2000.
  * [10] Dan Jurafsky and James H. Martin.  Speech and language processing : an introduction to natural language processing, computational linguistics, and speech recognition.  Pearson Prentice Hall, 2009.
  * [11] Nikolaus Hansen.  The CMA Evolution Strategy: A Tutorial.  ArXiv e-prints, arXiv:1604.00772, 2016, pp.1-39, 2005.
  * [12] A. Auger and N. Hansen.  A restart cma evolution strategy with increasing population size.  2005 IEEE Congress on Evolutionary Computation, 2:1769–1776 Vol. 2, 2005.
  * [13] Nikolaus Hansen.  Benchmarking a bi-population cma-es on the bbob-2009 function testbed.  In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, GECCO ’09, page 2389–2396, New York, NY, USA, 2009. Association for Computing Machinery.
  * [14] Stack overflow, 2008 Accesssed: 2020-9-08.
  * [15] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  CoRR, abs/1706.03762, 2017.
  * [16] Zohar Manna and Richard Waldinger.  Knowledge and Reasoning in Program Synthesis.  Artificial Intelligence, 6(2):175 – 208, 1975.
  * [17] Yuepeng Wang, Xinyu Wang, and Isil Dillig.  Relational program synthesis.  Proceedings of the ACM on Programming Languages, 2(OOPSLA):1–27, 2018.
  * [18] Sumit Gulwani, William R. Harris, and Rishabh Singh.  Spreadsheet Data Manipulation Using Examples.  Commun. ACM, 55(8):97–105, August 2012.
  * [19] Rajeev Alur, Rastislav Bodík, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa.  Syntax-Guided Synthesis.  In Maximilian Irlbeck, Doron A. Peled, and Alexander Pretschner, editors, Dependable Software Systems Engineering, volume 40 of NATO Science for Peace and Security Series, D: Information and Communication Security, pages 1–25. IOS Press, 2015.
  * [20] Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig.  Program Synthesis Using Conflict-driven Learning.  In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, pages 420–435, New York, NY, USA, 2018. ACM.
  * [21] Stefan Heule, Eric Schkufza, Rahul Sharma, and Alex Aiken.  Stratified Synthesis: Automatically Learning the x86-64 Instruction Set.  SIGPLAN Not., 51(6):237–250, June 2016.
  * [22] Rastislav Bodík and Barbara Jobstmann.  Algorithmic Program Synthesis: Introduction.  International Journal on Software Tools for Technology Transfer, 15:397–411, 2013.
  * [23] Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat.  Combinatorial Sketching for Finite Programs.  SIGOPS Oper. Syst. Rev., 40(5):404–415, October 2006.
  * [24] Calvin Loncaric, Michael D. Ernst, and Emina Torlak.  Generalized Data Structure Synthesis.  In Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, pages 958–968, New York, NY, USA, 2018. ACM.
  * [25] Alvin Cheung, Armando Solar-Lezama, and Samuel Madden.  Using Program Synthesis for Social Recommendations.  ArXiv, abs/1208.2925, 2012.
  * [26] Kevin P. Murphy.  Machine Learning: A Probabilistic Perspective.  The MIT Press, 2012.
  * [27] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli.  Leveraging grammar and reinforcement learning for neural program synthesis.  arXiv preprint arXiv:1805.04276, 2018.
  * [28] Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli.  Neuro-symbolic program synthesis.  arXiv preprint arXiv:1611.01855, 2016.
  * [29] Yanju Chen, Chenglong Wang, Osbert Bastani, Isil Dillig, and Yu Feng.  Program synthesis using deduction-guided reinforcement learning.  In International Conference on Computer Aided Verification, pages 587–610. Springer, 2020.
  * [30] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli.  RobustFill: Neural Program Learning under Noisy I/O.  In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 990–998, 2017.
  * [31] Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani.  Neural-guided deductive search for real-time program synthesis from examples.  arXiv preprint arXiv:1804.01186, 2018.
  * [32] Eui Chul Shin, Illia Polosukhin, and Dawn Song.  Improving neural program synthesis with inferred execution traces.  Advances in Neural Information Processing Systems, 31:8917–8926, 2018.
  * [33] Xinyun Chen, Chang Liu, and Dawn Song.  Execution-guided neural program synthesis.  In International Conference on Learning Representations, 2018.
  * [34] Illia Polosukhin and Alexander Skidanov.  Neural program search: Solving data processing tasks from description and examples.  2018\.
  * [35] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama.  Learning to infer program sketches.  In International Conference on Machine Learning, pages 4861–4870. PMLR, 2019.
  * [36] Amit Zohar and Lior Wolf.  Automatic Program Synthesis of Long Programs with a Learned Garbage Collector.  CoRR, abs/1809.04682, 2018.
  * [37] Veselin Raychev, Martin Vechev, and Eran Yahav.  Code Completion with Statistical Language Models.  In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, pages 419–428, New York, NY, USA, 2014. ACM.
  * [38] Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli.  Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [39] Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett.  Optimal neural program synthesis from multimodal specifications.  CoRR, abs/2010.01678, 2020.
  * [40] Scott E. Reed and Nando de Freitas.  Neural Programmer-Interpreters.  In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
  * [41] Jonathon Cai, Richard Shin, and Dawn Song.  Making Neural Programming Architectures Generalize via Recursion.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [42] Xinyun Chen, Chang Liu, and Dawn Song.  Towards synthesizing complex programs from input-output examples.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [43] Markus Brameier.  On Linear Genetic Programming.  PhD thesis, Dortmund, Germany, 2007.
  * [44] William B. Langdon and Riccardo Poli.  Foundations of Genetic Programming.  Springer Publishing Company, Incorporated, 1st edition, 2010.
  * [45] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le.  Regularized Evolution for Image Classifier Architecture Search.  In Thirty-Third AAAI Conference on Artificial Intelligence, February 2019.
  * [46] Alex Krizhevsky.  Learning Multiple Layers of Features from Tiny Images.  Technical report, 2009.
  * [47] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In CVPR09, 2009.
  * [48] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever.  Evolution Strategies as a Scalable Alternative to Reinforcement Learning.  CoRR, abs/1703.03864, 2017.
  * [49] Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, and Jeff Clune.  Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning.  CoRR, abs/1712.06567, 2017.
  * [50] Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu.  Hierarchical Representations for Efficient Architecture Search.  CoRR, abs/1711.00436, 2017.
  * [51] Santient Labs.  Evolv Delivers Autonomous Optimization Across Web & Mobile.  https://www.evolv.ai/.
  * [52] Esteban Real, Chen Liang, David R. So, and Quoc V. Le.  Automl-zero: Evolving machine learning algorithms from scratch, 2020.
  * [53] S. D. Mueller, M. Milano, and P. Koumoutsakos.  Application of machine learning algorithms to flow modeling and optimization.  In CTR Annual Research Briefs, page 169–178. Center for Turbulence Research, Center for Turbulence Research, 1999.
  * [54] Th. Lutz, S. Wagner, Th. Lutz, and S. Wagner.  Drag reduction and shape optimization of airship bodies.  In 12th Lighter-Than-Air Systems Technology Conference. American Institute of Aeronautics and Astronautics, June 1997.
  * [55] Toyotaka Sonoda, Yoshihiro Yamaguchi, Toshiyuki Arima, Markus Olhofer, Bernhard Sendhoff, and Heinz-Adolf Schreiber.  Advanced high turning compressor airfoils for low reynolds number condition—part i: Design and optimization.  Journal of Turbomachinery, 126(3):350–359, July 2004.
  * [56] S. Winter, B. Brendel, A. Rick, M. Stockheim, K. Schmieder, and H. Ermert.  Registration of bone surfaces, extracted from CT-datasets, with 3d ultrasound.  Biomedizinische Technik/Biomedical Engineering, 47(s1a):57–60, 2002\.
  * [57] Nikolaus Hansen.  CMA-ES Applications.  http://www.cmap.polytechnique.fr/~nikolaus.hansen/cmaapplications.pdf, 2009\.
  * [58] Shantanu Mandal, Adhrik Chethan, Vahid Janfaza, S M Farabi Mahmud, Todd A Anderson, Javier Turek, Jesmin Jahan Tithi, and Abdullah Muzahid.  Large language models based automatic synthesis of software specifications, 2023.  arXiv 2304.09181.
  * [59] Mark Santolucito, Ennan Zhai, Rahul Dhodapkar, Aaron Shim, and Ruzica Piskac.  Synthesizing configuration file specifications with association rule learning.  Proc. ACM Program. Lang., 1(OOPSLA), oct 2017.
  * [60] Sarah Nadi, Thorsten Berger, Christian Kästner, and Krzysztof Czarnecki.  Mining configuration constraints: Static analyses and empirical results.  In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, page 140–151, New York, NY, USA, 2014. Association for Computing Machinery.