SplitRegex: Faster Regex Synthesis via Neural Example Splitting
Authors: Su-Hyeon Kim
Hyunjoon Cheon
Yo-Sub Han
Sang-Ki Ko
Venue: ICLR 2022 Submitted (2022)
Keywords: regular expression
program synthesis
programming by examples
deep learning
neural network

Abstract: Due to the practical importance of regular expressions (regexes, for short), there has been a lot of research to automatically generate regexes from positive and negative string examples. A basic idea of learning a regex is a search-and-repair; search for a correct regex and repair it if incorrect. The problem is known to be PSPACE-complete and the main issue is to obtain a regex quickly within a time limit. 
While classical regex learning methods do not perform well, recent approaches using deep neural networks show better performance
with respect to the accuracy of the resulting regexes. However, all these approaches including SOTA models are often extremely slow because of the slow searching mechanism, and do not produce desired regexes within a given time limit. 
We tackle the problem of learning regexes faster from positive and negative strings by relying on a novel approach called `neural example splitting'. Our approach essentially split up example strings into multiple parts using a neural network trained to group similar substrings from positive strings. This helps to learn a regex faster and, thus, more accurately since we now learn from several short-length strings.
We propose an effective regex synthesis framework called `SplitRegex' that synthesizes subregexes from `split' positive substrings and produces the final regex by concatenating the synthesized subregexes. For the negative sample, we exploit pre-generated subregexes during the subregex synthesis process and perform the matching against negative strings. Then the final regex becomes consistent with all negative strings. SplitRegex is a divided-and-conquer framework for learning target regexes; split (=divide) positive strings and infer partial regexes for multiple parts, which is much more accurate than the whole string inferring, and concatenate (=conquer) inferred regexes while satisfying negative strings. We empirically demonstrate that the proposed SplitRegex framework substantially improves the previous regex synthesis approaches over four benchmark datasets. 

Under review as a conference paper at ICLR 2022
SPLITREGEX: FASTER REGEX SYNTHESIS FRAME- WORK VIA NEURAL EXAMPLE SPLITTING
Anonymous authors Paper under double-blind review
ABSTRACT
Due to the practical importance regular expressions (regexes, for short), there has been lot of research to automatically generate regexes from positive and negative string examples. A basic idea of learning a regex is a search-and-repate search for correct regex and repair it if incorrect. The problem is known to be PSPACE- complete and the main issue is to obtain a regex quickly within a time limit. While classical regex learning methods do not perform well, recent approaches using deep neural networks show better performance with respect to the accuracy of the resulting regexes. However, all these approaches including SOTA models often extremely slow because of the slow searching mechanism, and do not produce desired regexes within given time limit.
We tackle the problem of learning regexes faster from positive and negative strings by relying on novel approach called 'neural example splitting'. Our approach essentially split up example strings into multiple parts using a neural network trained to group similar substrings from positive strings. This helps learn regex faster and, thus, more accurately since we now learn from several short-length strings. We propose an effective regex synthesis framework called 'SplitReeex' that synthesizes subregexes from 'split' positive substrings and produces the final regex by concatenating the synthesized subregexes. For the negative sample, we exploit pre-generated subregexes during the subregex synthesis process and perform the matching against negative strings. Then the final regex becomes consistent with all negative strings. SplitRegex a divided-and and-conquer framework for learning target regexes; split (=divide) positive strings and infer partial regexes for multiple parts, which is much more accurate than the whole string inferring, and concatenate (=conquer) inferred regexes while satisfying negative strings. We empirically demonstrate that the proposed SplitRegex framework substantially improves the previous regex synthesis approaches over four benchmark datasets.
INTRODUCTION
Regular expressions (regexes in short) are a powerful tool on processing sequence data in NLP or information retrieval. A regex-a finite sequence-is a formal representation of (infinite) symbol sequences. However, it is not easy write a good regex for set of sequences. Especially for those who have little experience on formal expressions, a single mistake in regex composition leads to an invalid regex or, even worse, regex with different semantics ones' intention. An automatic regex synthesis tries to moderate this human error.
Examples (Oneina & Gareía 1992 Bartoli et al. 2014) and natural language descriptions (Locascio et al., Zhong al.] (2088) are the two major sources of regex synthesis. Examples are specific in their meaning without any implicit semantics, but are hard to provide the complete user intent described by regex. On the other hand, natural language descriptions are ambiguous but describes the high-level concept of a regex. As these two different types of information are complementary to each other, there have been many studies (Chen et al. 2020 Li et al. 202 Zhong al. 2018a) that suggest to use both modalities as they can use examples to fix the ambiguous expressions generated from natural language descriptions.

---

Under review as a conference paper at ICLR 2022
The regex synthesis problem is to make a proper regex E from both positive and negative sets such that all the positive samples are generated by E and all the negative strings are not generated by E. This problem is also called the regex inference learning problem in the literature.
The traditional approaches for the regex synthesis problem are often inapplicable in practical set- tings. For example, AAngluin's (1987) L* is impractical because it requires the equivalence test between a target regex and a generated regex, which is known to be PSPACE-complete and thus intractable (Stockmeyer & Meyer 1973). Gold (1778) shows that the state characterization approach is NP-complete and thus intractable. Heuristic approaches based on state-merging DFA induction algorithms such as RPNI (Oncina & Gareía 1992) and blue-fringe (Lang et al. 1998) are not very promising on synthesizing complex regexes because it is almost impossible to obtain a concise regex even when they are able to produce a concise DFA from examples. As recent approaches, both AlphaRegex (Leee et al. (016) and RegexCienerator** (Bartoli et al. 2014, 2016) generate candidate regexes and match against the given examples until the target regex matches all examples successfully. While these approaches generate correct regexes when time limit is very long, they often fail when the example size is large. In addition, both approaches do not use any characteristies in the given examples, which can be useful feature to speed up the process. In other words, these methods are impractical for generating regexes within a reasonable time limit.
For practical usage, we notice that the divide-and andde--nd--ae aad---ndd---o- conquer approach is promising for synthesizing formal representation. For example, Alur et al.] (2017) synthesize a program with hierarchical partition of the given input-output pairs. A decision tree reflects the hierarchical partition forms the control flow of the synthesized program. This method noticeably improves program synthesis time due to the partitioned problem space. Farzan & Nicolet (2021a b) propose an effective method that converts program into an equivalent program by splitting g problem into several subproblems. This divide-and- conquer approach is efficient since individual tasks for solving subproblems can run simultaneouslyy Recently, Barrke et al. (2020); Shrivastava et al. (2021) propose program synthesis methods that first finds partial solutions satisfying subsets of input-output examples and combines the solutions to find the global solution.
In this paper, we propose a novel regex synthesis framework based on the divide-andd-onquee paradigm. Given a set of positive examples, we split examples into multiple parts by grouping similar substrings using a neural network and solve subproblems defined over the multiple parts in serial order. We train neural network called the NeuralSplitter that embeds set of positive examples into a fixed-size vector and produces the most probable split for each example in the set.
Our main contributions are follows:
We propose a regex synthesis framework SplitRegex based on the divide-and-conquee paradigm, which has been employed in many sequential algorithms. As far as we are aware, this is the first attempt to synthesize regexes in the divide-and-conquee manner.
2. We design neural network called the NeuralSplitee--a two-stage attention-based based recurrent neural network trained to predict the most probable split of input positive strings.
3. We conduct exhaustive experiments on various benchmark datasets including random dataset and practical regex datasets for demonstrating the effectiveness of the the proposed framework. We show that our framework can be easily combined with the off-the-shelf regex synthesis algorithms with minor modifications.
Namely, our framework solves regex synthesis problem, which is PSPACE-complete, much faster when applied to any existing regex synthesis models, and thus boosts the overall performance.
2 RELATED WORK
We provide a list of related works on regex synthesis problems based on various input types including positive and negative examples and natural language descriptions.
2.1 REGULAR EXPRESSION INFERENCE FROM EXAMPLES
One approach to regular expression inference is by Angluin s (987). Angluin suggests an algo-
rithm 1," that infers unknown DFA in teacher-student architecture. The teacher of I," offers
2

---

Under review as a conference paper at ICLR 2022
membership queries and equivalent queries the target expression for the student. Note that this type of algorithms generally requires an infinite amount of examples to synthesize an FA.
Gold (977)) proposes a heuristic inference algorithm that inductively distinguishes random prefixes according to the acceptance followed by the given examples. The prefixes with the same acceptance form single state in a DFA. The blue-fringe algorithm (Lang et al. 1998) and RPNI (Oncina &
Gareía 1992) are similar to the Goldd' algorithm.
AlphaRegex Lee al., 2016) exhaustively searches through all possible regular expressions until it identifies a solution regex that satisfies given positive and negative examples. A major limit of AlphaRegex is that its runtime is extremely due the exponential increase of search space.
RegexGeenraaoo+*+ (Bartoli et al.] 2014 2016) produces a regular expression using the genetic programming approach. The produced regular expression recognizes the surroundings (context) of the target sequence as well as the target itself. However, Regex ergexxenerator++4 entails a huge amount of computations due to the repetitive nature of genetic approach on each inference.
2.2 REGULAR EXPRESSION SYNTHESIS FROM NATURAL LANGUAGE DESCRIPTIONS
Ranta (198) studies based techniques for the conversion between multi- languails and regular expressions, Kushman & Barzilay (2013) build a parsing model that translates a natural language sentence a regular expression, and provides a dataset, which is the most popular benchmark dataset in recent research. Locascio et al. (2016) propose the Deep-Regex model based on Seq2Seq for generating regular expressions from NI. descriptions together with 10,000 NI-RXX pair data. However, due to the limitations of the standard Seq2Seq model, the Deep-Regex model can only generate regular expressions similar in shape to the training data. The SemRegex model (Zhong et al. (018b) improves the Repp-Regex model by reinforcement learning based on the DFA-equivalence oracle, which determines two regular expressions define the same language, as a reward function and their model can generate correct regular expressions even if they do not exactly look like answers. The SoftRegex model (Park et al. 2019) further improves SemRegex based on the fast regex equivalence test, which gives rise fast learning process.
2.3 MOLTI-MODAL REGULAR EXPRESSION SYNTHESIS
Most multi-modal synthesis method uses natural language descriptions and positive/negative exam- ples simultaneously to mitigate the ambiguity in natural languages. Chen et al. (2020) introduce hierarchical sketch for the semanties of natural description, Chen et al. implementation Regel first deduces the hierarchical structure representing the semantics of the natural language description. This semantic structure has some holes which the regular expression inference algorithm enhances a regular expression by predefined rules. Regel also prunes an infeasible expression using over- and under-approximation possible regular expressions, which replaces the holes with the most permissive and the most restrictive expression, respectively. Li et al. (202T) propose TransRegex framework that synthesizes a valid regular expression. TransRegex 's NLP-based synthesizer translates the given description to regular expression and fixes the expression by rules and RFixer (Pan et al. 2019) to increase matching score on the examples.
2.4
REPAIR-BASE REGULAR EXPRESSION SYNTHESTS
Pan et al. 2019) design a heuristic algorithm RFixer that repairs a regular expression with given examples. RFixer improves the given regular expression by introducing removing hole and approximate the target expression with over- and under-approximatt
method until finds a regular expression with no holes that satisfies the given examples. Li et al. (2020) propose FlashRegex that generates a deterministic regular expression, which is a subclass lass of regular expressions. A SAT solver designs the basic FA structure after the given examples and FlashRegex iteratively shuffles the transitions in FA model at random to find the most suitable FA that satisfies the given examples.
3 OUR APPROACH
Our approach involves the following procedure:
3

---

Under review as a conference paper at ICLR 2022
Positives
Divide positive examples
Negutives
Neurai Splitter
b
b
Symthesize subregexes
B
b
b
RegexSyntbesizer
RegexSynthesizer
Regex Syuthesizer
3. Combine into single regex
Figure Overview of the proposed approach.
1. Split the input positive strings in the set P into multiple partitions P2........ Ps. where S is the number of splits, using the NeuralSplitter model.
2. Run the regex synthesis engine for each P. for 1 < S with corresponding set N; negative strings. We will explain in more detail about how to use the set of negative strings for final regex synthesis.
3. Concatenate the obtained subregexes R1, R2 ... Rs such that P. S L(R:) to produce the final regex R. Note that L(R,) is the language represented by Rg
In order to train the NeuralSplitter, we generate target labels for positive examples as fol- lows. For instance, when are given P (aabbccabca, abcbbc, bbbcabb, aabbbc) and R = ""." we obtain ground truth labels for the four positive examples in P follows: (1122330000, 223000,,223000, that the corresponding symbols are generated from the first, second, and third subregex of R. Note that the output label for symbols generated from the wildcard pattern regex (capturing zero or more any characters) is always 0 regardless of the position of the corresponding subregex. We explain the reason later this section.
2223000, 112223). The digits 1, 2, and the ground truth labels imply
Note that cannot split negative examples just we do for positive examples using the Neu- ralSplitter model as there may be another split (not produced by the NeuralSplitter) that results in negative strings recognized by the synthesized regex. For instance, consider simple when given P= (abbaaa, abaaa, aaa) and N {aaaa]. ). The NeuralSplitter may simply predict that substrings with the same repeated symbols should be grouped to form subregex. Then, the first part has positive examples P1 = {a} and Ni {A}, the second part has Ps (bb, b, A} and N₂ = {A}, and finally the last part has P's {aa, aaa} } and N2 {aaaa). is possible that the regex synthesis algorithm generates ab aaa" which accepts the negative example.
We resolve this problem by introducing the concept prefix-conditionel subregex synthesis. The basic idea of our approach is to first synthesize n subregexes once the NeuralSplitter produces n splits (P1, P2..... P,)) from P. Then, we concatenate the resulting and use this regex to obtain the final regex from the last split sample P,, that satisfies all prefix subregexes as well as the negative samples. Namely, for each regex synthesis RG we only consider the corresponding split examples P, from P. We use the negative samples prevent for regex synthesis algorithm to return trivial regex such as the wildcard pattern regex (capturing zero or more any characters). One may consider to the NeuralSplitter approach for the negative samples. Our empirical observation confirms that causes substantially larger amount of additional computations, and the performance becomes worsened.
regexes to be RG R2 ... Rn
4

---

Under review as a conference paper at ICLR 2022
When there common strings between the split positive examples P. and the negative examples N, we remove the common strings from N. If P, has only one example (singleton set), then we simply returns the example Rz. The proposed method generates a regex R from a set P of positive examples and a set N of negative examples that satisfies the following conditions:
-LR))) S P. and (( P.) = 9 for 1 i n (independent subregex synthesis). -[(R ... R..) N = 0 (prefix
subregex synthesis).
. L(R.) = if = for v i S n (singleton subregex synthesis).
While the proposed method can generate a regex quickly by dividing a complex synthesis problem into several easier problems, one limit is that it cannot generate the wildcard pattern regex, -', as a subregex R; due to the negative examples. Because the wildcard pattern is common and handy in practice represent complicated sequences, we treat the symbols generated from the wildcard pattern differently compared with the rest of the symbols-we assign a special label 0 for the symbols in the data preprocessing step. For instance, if string abbccdd is generated from a"b' cdd" d", then the label is 1223344. However, if abbccdd is generated from a".", then the label is 1000000. When reading these special symbol O's, our framework immediately generates wildeard patterns without going through the prefi--condition subregex synthesis.
3.1
DATA PREPROCESSING
From the practical regex dataset, we exclude regexes with features listed below:
Backreference: we do consider backreference for regex synthesis as some baseline approaches such as AlphaRegex and Blue-Fringe algorithm do not support regex features that capture non-regular languages.
Lookaheed//ookbehind: while regexes with these features still only capture regular languages. we do not consider these features as they require the regex engine to perform backtracking that causes catastrophic runtime in some extreme cases.
Quantifier with exact count '[n}' or range '(n, m}:: we replace numerical quantifiers with **' to 1) reduce the search space and 2) control the length of randomly generated strings.
For each regex, we randomly generate 20 positive and negative examples up to certain length (10 for random dataset and 15 for the other datasets). In order to generate positive examples, we utilize a Python library called the Xeger]] For generating negative examples, we first generate positive examples and randomly substitute symbols with other symbols to make the examples outside the language represented by the regex. Then, we use Python library pyre2, which a Python wrapper for Google's RE2 regex library, to perform matchings of perturbed examples against the regex. We find this is effective compared to the complete random generation of negative examples.
In order to guarantee that every regular expression has 20 positive and negative examples, we exclude regular expressions that do not generate more than 20 positive strings (e.g.. regexes without quantifiers 10 positive/negative strings for
such as * and +). From 20 positive and negative strings, generating regexes and use the remaining strings for measuring the semantic accuracy of synthesized regexes by membership queries.
We utilize the fullmatch method of pyre2 to find subregexes from the whole regex that match corresponding substrings from given positive strings.
3.2 NEURAL NETWORK ARCHITECTURE
We introduce neural network called the NeuralSplitter that is trained to split positive examples generated from each regex. For set P = (P1. ......, Pr of positive examples, where p: Σ for 1 < < n, we embed each string p; with RNN encoder into dimensional space as follows: h4 = R.N encl (p:), where h; E Rd, Then, we embed the set P of positive examples with the second RNN encoder RNN Nenc as follows: hp RNNenc2(hu l2,..., hn), where hi RRdd
httpss//pppp..rr//gn//ee/tt///
5

---

Under review as a conference paper at ICLR 2022
From the hidden vectors h2 for 1 S i S and hp, the RNN decoder is trained to produce the ground truth label for each positive string p. as follows:
01, 02, 0.,-.... , oi; = RNNNec (W dec [b:: hpl),
where 4; pil. Oj E IRd for 1 j S 1,, Wdec E IR=2dxd
Finally, we retrieve the predicted label for each positive example p: as follows:y, = softmax (eitmaxx(Worrr output" 04), where yy IRI W ooupuut _ and is the output vocab. Note that yy is the predicted probability distribution for the label of jth symbol of the positive example p:-
During the decoding process, the RNN decoder exploits the attention mechanism better point out the relevant parts from the entire set of positive strings. Since the split label for positive string relies on the information from all positive strings, we implement two-step attention mechanism that enables our model to attend both in set level and example level. For instance, when we have two strings aabbbc and aabbcc, the most probable labels for these two strings are 112223 and 112233. However, if the second string is caabbec, where only the first symbol is appended in front of aabbcc, then the most probable labels for two strings become 223334 and 1223344. In this reason we need to use the information of all given positive strings correctly predict the output labels.
We use bi-directional GRU network for RNN encoder and decoder of NeuralSplitter. Cross entropy loss is used for training neural network.
4 EXPERIMENTAL SETUP
We describe the experimental setup for evaluation.
Datasets. We use the following benchmarks to measure the performance of the proposed approach compared to the previous approaches.
Random dataset: consists of 1,000,000 randomly generated regexes (784,682 unique regexes) over various alphabet sizes 2, 4, 6, 8 and 10.
RegExLit consists of regexes collected from an online regex library where 4, 4,149 regexes are indexed from 2,818 contributors help regex users write their own regexes more easily.
Snor an open source intrusion detection/preeentiion system, contains more than 1,200 regexes in its rule set for compactly describing malicious network traffic.
Polyglot Regex Corpus (Davis al., 2019): consists of 537,806 regexes extracted from 193,574 software projects written in eight popular programming languages. Introduced for the research on regex portability problem.
For training the NeuralSplitter and evaluating our framework on practical regex benchmarks including RegExLib, Snort and Polyglot Regex Corpus, we first generate 20 random positive and negative examples for each regex and split the data into training, validation and test set with the ratio of 8:1:1. Then, we collect the training and validation splits for three benchmarks for training the NeuralSplitter model, and use each test set for evaluating the regex synthesis performance each benchmark.
We use two-layer bidirectional GRU with 256 hidden units unless explicitly mentioned otherwise. The dimension of input token embedding is four. The Adam optimizer is used with batch size 512 and learning rate of 0.001 and weight decay of le-6.
Hyperparameters.
Baselines. We take the following baseline methods for regex synthesis from examples.
AlphaRegex (Lee et al. 2016 Kim et al. 2021): :): best-first search based regex enumeration algorithm. We use our own Python implementation of AlphaRegex algorithm, which is originally written in OCam together with the recent search space reduction techniques by Kim et al. (202T).
https://github.co httm://kpp//pppaaaeerruulll ic

---

Under review as a conference paper at ICLR 2022
(Bartoli et al. 2014 2016): regex inference algorithm based on genetic programming. Due to the nature of genetic inference procedure, this is the slowest among the baselines.
RegexGenerator++
Fringe algorithm (Lang et al. 1998): : a classical state-merging DFA induction algorithm. We choose this algorithm show the generality of our framework on classical synthesizers such as L Annglun 1987) or RPNI (Oncina & Garcia
1992).
Note that we also use these baselines as off-the-shelf regex synthesizers for our SplitRegex framework to evaluate the performance boost gained by our framework.
Metrics. We evaluate the performance of the proposed approach in two main aspects: 1) the time efficiency of synthesis algorithm and 2) the accuracy of synthesized regexes. For evaluating the time efficiency, we set a time budget, specified by timeous value. We set the timeout value to (seconds) for AlphaRegex and Blue-Fringe algorithm and 10 (seconds) for RegexGenerattr++ in our experiments. A regex synthesis is counted as a success if an algorithm finds a regex satisfying given positive and negative examples within the specified timeout. We measure the success rate of regex synthesis by counting the number of successes in n regex synthesis trials where n is the number of target regexes in test set.
Meanwhile, we also need to measure the accuracy of synthesized regexes as any algorithm may generate trivial solution that only recognizes positive examples. However, we cannot simply count the number of cases where the synthesized regex is 'literally' equivalent to the target regex as two different regexes can capture the same set of strings there are infinitely many semantically equivalent regexes. Hence. we need to introduce criterion that considers how two regexes are semantically similar. While it is well-known that it possible to algorithmically decide whether two regexes represent the same language, it is also well-known that the decision process is PSPACE- complete (Stockmeyer Meyer 1973) and therefore probably intractable.
Therefore, we define a metric called the semantic regex accuracy that utilizes randomly generated positive and negative examples that are not used for regex synthesis. Remark that the semantic regex accuracy has been already employed in previous work for evaluating the generated regexes (Li ct al. 2021). Given pair (P.N) ) of positive and negative sets reserved for evaluation, we define the semantic regex accuracy as follows:
sem awcuracccyycc...... (Raraacy,RRRRR P,N) = [Pll + N
FPl
|Fx]
x 100,
PP
N
where Tp = ((R w E P). = (w & L(R) w E N), =p=(w $ L(R) w E P) and Fx = fw L(R) NE.
Intuitively, the semantic regex accuracy is higher if the synthesized regex recogmizes more strings recognizable by the target regex and rejects more strings not recognizable by the target regex.
Finally, we define synthesized regex to be fully accurate if the regex satisfies all the unseen examples. In other words, regex is fully accurate if the semantic regex accuracy is
EXPERIMENTAL RESULTS AND ANALYSIS
We demonstrate the experimental results to show the effectiveness of the proposed approach compared to baselines and analyze the results.
5.1 MAIN RESULTS
Table Tsooss shows the main result of our paper. We evaluate approach with the basclines in terms of success rate, semantic accuracy, and the ratio of fully accurate regexes using reserved examples.
In order examine the upper bound on the performance of SplitRegex, we also consider variant of SplitRegex called 'GT Split' where we use ground-truth splits of regexes instead of predicted splits by NeuralSplitter.
is readily seen that the proposed framework substantially improves all of the success rate, semantic accuracy, ratio of fully accurate regexes in most benchmarks except some cases.
7

---

Under review as a conference paper at ICLR 2022
Table 1: Regex synthesis performance (success rate, semantic regex accuracy, and the ratio of fully accurate regexes) of our model and baselines over three benchmark regex datasets. 'AR', 'BF', and "RG' are abbreviations for AlphaRegex, Blue-Friing,, and RegexGenerator+4 respectively.
Method
RegExLib
Snort
Polyglot Corpus
Suec.
Acc.
Full.
Succ.
Acc.
Full.
Succ.
Acc.
Full.
AlphaRegex
14.0
13.56
12.1
16.2
15.74
13.8
49.9
49.04
46.2
SplitRegex (+AR)
23.4
21.78
17.6
72.1
67.42
54.4
64.0
62.28
56.4
GT Split (+AR)
43.8
40.90
32.3
87.7
83.20
69.6
70.4
67.68
59.6
RegexGennrator++
0.0
0.00
0.0
0.0
0.00
0.0
0.2
0.20
0.2
SplitRegex (+RG)
2.4
2.34
2.1
6,4
5.68
3.4
17.0
16.82
16.0
GT Split (+RG)
2.9
2.80
2.2
9.3
8.56
5.8
17.6
17.26
16.0
Blue-Fringe
100.0
0.80
0.1
100.0
0,46
0.0
100.0
4.40
0.3
SplitRegex (+BF)
86.9
15.26
1.3
97.3
17.22
2.6
97.4
13.32
1.7
GT Split (+BF)
90.8
18.00
2.1
100.0
19.42
3.0
99.4
13.72
1.7
Table 2: Comparisons of different regex synthesis method using split positive examples.
Synthesis Strategy
On Random Regexes
On Practical Regexes
Success Rate
Accuracy
Success Rate
Accuracy
Baseline (AlphaRegex)
47.57
44.83
12.90
13.08
Prefix-conditiones synthesis
63.90
60.50
37.60
36.94
Independent parallel synthesis
42.00
40.40
54.50
54.34
Independent sequential synthesis
64.60
61.68
55.84
55.20
First, the success rate the Blue-Fringe algorithm is the highest among all the considered algorithms due the nature of the Blue-Fringe algorithm. Note that the Blue-Fringe algorithm merges the suffixes of given positive examples while assuming that any string the expression represents is positive unless there is counterexample- negative example. While the Blue-Fringe algorithm can simply generate a regex satisfying the examples very quickly, the generated regex represents slightly larger of strings than the by Blue-Fringe rarely accepts positive examples that are not used in the regex synthesis process. However, when the SplitRegex framework combined with Blue- BluneFringe, the semantic accuracy is improved even though it fails to return solutions for some cases due to additional overhead caused by neural network computations. The main reason is that the process of splitting examples already makes the resulting regexes more fine-grained compared to those generated by the vanilla Blue-Fringe.
positive examples general. This means that the regex generated
The performance on RegexGenerator+++ very low across all experiments mostly due to the repetitive nature of genetic approach. Actually, RegexGenerator++ fails to generate regexes in most cases with larger time limit (10 seconds). Nevertheless, we can see that the proposed framework helps RegexCienerator+ succeed in few more cases compared to the vanilla RegexGenerator++
5.2 DETAILED ANALYSIS
Alphabet size. Figure shows how the SplitRegex framework affects the regex synthesis per- formance of AlphaRegex and Blue-Fringe algorithms on random dataset with different alphabet sizes. While the success rate decreases the alphabet size increases for AlphaRegex, SplitRegex effectively improves the success rate as the alphabet size increases. Moreover, the semantic accuracy of synthesized regexes is also improved when the SplitRegex is applied to both baselines. This is because it is easier to group the similar substrings using common symbols as there are more symbols in string. For example, two regexes abc d? f) and 000 1?(0 + 1) are similar in terms of length and structure but is easier to find correct split from the examples generated from the former infer where each symbol in the examples comes from more easily.
8

---

Under review as a conference paper at ICLR 2022
100
70
90
Semantie Accurary
Success Rato
AlphaRagex
40
BlawFFinng
70
SpitRagox (+AR)
30
SpitRRgex (+BF)
Method
AlphaRagex
60
Blue-Fringe
10
SpliRugax (+AR)
80
SpitRegex (18F)
10
10
AlphabeiSize
AlphabesSize
Figure Results random regular expression dataset with different alphabet sizes.
Table 3: Examples of neural example splitting.
Dataset
Input String
Split Result
uname=&pword-9E8
uname=
&pword=
9E8
uname=18pword=
uname=
&pword=
RegExLib
unamm==tiyo//&@pwordAAA
uname= Hj%}v
&pword=
'Af7=
uname=)/&&porrd=@K
uname= )#
&pword=
@k
immageslphp7t=66553/
/images
php?t=
6153
U
immaes-phpp?t-295.
/images
php?t=
296
U
Snort
images4phhp?t=52131U imagesQphp?!:1655U
/images 4
php?t=
5213
/U
/images Q
php?t= 165
U
Subregex synthesis strategies. We conduct additional experiments to verify whether the 'prefix- conditioned synthesis' strategy can be utilized for every subsequent subregexes while utilize only for synthesizing the last subregex. Moreover, we also test whether the first n subregexes (when the split size is n)) can be synthesized in parallel if the rreix-coodiiiooed synthesis is not used. Table 2 demonstrates the experimental results on random regexes and practical regexes from RexExLii, Snort and Polyglot corpus datasets. The results imply that the simplest approach (independent sequential synthesis except the final subregex) achieves the best performance compared to the parallel approach and preix-conditionee synthesis approach.
Examples of neural splitting. Table 3 demonstrates several examples of neural example split- ting- For instance, positive examples in the 'Snort' dataset generated from a regex '/im- ages. "php?t=."/U" We can that NeuralSplitter model successfully splits positive examples into five parts where similar strings are grouped together. As a result, SplitRegex produces the follow- ing regex for the examples which is quite similar the target regex: '/images. "php?t=[0-9]//U
CONCLUSIONS AND FUTURE WORK
In this paper, we have proposed a regex synthesis framework called the SplitRegex that synthesizes regex from given positive and negative examples based on the divide-and-cooquee paradigm. Given a predict the most probable splits for strings such that substrings in the
set of positive examples, same partition exhibit similar patterns using a neural network called the NeuralSplitter. Then, we synthesize subregexes for all partitions and derive the final regex satisfying the input examples. Our experimental results show that the proposed scheme is very effective in reducing the time complexity of regex synthesis and actually yields more accurate regexes than the previous approaches.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. Scaling enumerative program synthesis via divide and conquer. In Axel Legay and Tiziana Margaria (eds.), Tools and Algorithms for the Construction and Analysis of Systems 23rd International Conference, TACAS 2017, volume 10205 of Lecture Notes in Computer Science, pp. 319-336, 2017.
Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computa- tion, 75(2):87-106, 1987.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. 3rd International Conference on Learning Representation, ICLR 2015, 2015.
Shraddha Barke, Hila Peleg, and Nadia Polikarpova, Just-in-time learning for bottom-up enumerative synthesis. Proc. ACM Program. Lang., 4(0OPSLA), 2020.
A. Bartoli, G. Davanzo, A. De Lorenzo, Medvet, and Sorio. Automatic synthesis of regular expressions from examples. Computer, 47(12):72 -0, dec 2014. ISSN 1558-0814. doi: 10. 1109/ MC.2014.344.
Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. Inference of regular expres- sions for text extraction from examples. IEEE Trans. on Knowl. and Data Eng.. 28(5):1217 -130 May 2016.
Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. Multi-modal synthesis of regular expressions. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 487-502, 2020.
James C. Davis, Louis G. Michael IV, Christy A. Coghlan, Francisco Servant, and Dongyoon Lee. Why aren't regular expressions a lingua franca? an empirical study on the re-use and portability of regular expressions. In Marlon Dumas, Dietmar Pfahl, Sven Apel, and Alessandra Russo (eds.), Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering, ESEC/SIGSOFT FSE 2019, pp. 443-454. ACM, 2019.
Azadeh Farzan and Victor Nicolet. Counterexample-guidee partial bounding for recursive function synthesis. In Alexandra Silva and K. Rustan M. Leino (eds.), Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part I, volume 12759 of Lecture Notes in Computer Science, pp. 832 855. Springer, 2021a
Azadeh Farzan and Victor Nicolet. Phased synthesis of divide and conquer programs. In Stephen N. Freund and Eran Yahav (eds.), PLDI '21: 42nd ACM SIGPLAN International Conference on Programminng Language Design and Implementation, Virtual Event, Canada, June 20-25, 20211, pp. 984 ACM, 2021b.
E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37 (3):302-320, 1978.
Su-Hyeon Kim, Hyeonseung Im, and Sang-Ki Ki Ko. Efficient enumeration of regular expressions for faster regular expression synthesis. Sebastian Maneth (ed.), Implementation and Application of Automata, pp. 65-76. Springer International Publishing, 2021.
Nate Kushman and Regina Barzilay. Using semantic unification to generate regular expressions from natural language. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 826-836, 2013.
Kevin J. Lang, Barak A. Pearlmutter, and Rodney A. Price. Results of the abbadingo one DFA learning competition and a new evidence- state merging algorithm. In Vasant G. Honavar and Giora Slutzki (eds.), Granmatical Inferecee, 4th International Colloquium, ICGI-98, Ames, Iowa, USA. July 12-14, 1998, Proceedings, volume 1433 of Lecture Notes in Computer Science, pp. 1-12. Springer, 1998.
10

---

Under review as a conference paper at ICLR 2022
Mina Lee. Sunbeom So, and Hakjoo Oh. Synthesizing regular expressions from examples for introductory automata assignments. In Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, GPCE 2016, pp. 70- 2016.
Yeting Li, Zhiwu Xu, Jialun Cao, Haiming Chen, Tingjian Ge. Shing-Chi Cheung, and Haoren Zhao. Flashregex: Deducing anti-redos regexes from examples. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, ASE '20, pp. 659 671, 2020.
Yeting Li, Shuaimin Li, Zhiwu Xu, Jialun Cao, Zixuan Chen, Yun Hu, Haiming Chen, and Shing- Cheung. TransRegex: multi-modal regular expression synthesis by generate-and-repair, In 43rd IEEE/ACM International Conference Software Engineering. ICSE 2021, Madrid, Spain, 22-30 May 2021, pp. 1210-1222. IEEE, 2021.
Nicholas Locascio, Karthik Narasimhan, Eduardo DeLeon, Nate Kushman, and Regina Barzilay. Neural generation of regular expressions from natural language with minimal domain knowledge. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1918-1923, 2016.
Oncina and P. García. Inferring Regular Languages In Polynomial Updated Time, pp. 49-61. 1992.
Rong Pan, Qinheping Hu, Gaowei Xu, and Loris D' A'Antoni. Automatic repair of regular expressions. Proc. ACM Program. Lang., 3(0OPSLA), 2019.
Jun-U Park, Kang-Ki Ko, Marco Cognetta, and Yo-Sub Han. SoftRegex: Generating regex from natural language descriptions using softened regex equivalence. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 6425-644 022--431, 2019.
Aarne Ranta. A multilingual natural-language interface to regular expressions. In Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, pp. 79-90, 1998.
Disha Shrivastava, Hugo Larochelle, and Daniel Tarlow. Learning combine per-example solutions for neural program synthesis. CoRR, abs/2106.07175. 2021. URL httttt:///aaiv...oot
abs/2106.077 07175
Larry Stockmeyer and Albert R Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the fifth annual ACM symposium on Theory of computing, pp. 1-9, 1973.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104-31 3112, 2014.
Zexuan Zhong, Jiaqi Guo, Wei Yand, Tao Xie, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. Gen- erating regular expressions from natural language specifications: Are we there yet? In Workshops at the 32nd AAAI Conference on Artificial Intelligence, pp. 791-794, 2018a
Zexuan Zhong, Jiaqi Guo, Wei Yang, Jian Peng, Tao Xie, Mlan-Guang Lou, Ting Liu, and Dongmei Zhang. Semregex: A semantics- based approach for generating regular expressions from natural language specifications. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 1608-1618, 2018b.

---

Under review as a conference paper at ICLR 2022
APPENDIX
A BACKGROUND
Here we provide some background knowledge on the task of regular expression synthesis/ifference and basic neural network architectures used in our model.
Regular expression inferenceesynthesis. Let Σ be a finite alphabet and E" be the set of all strings over the alphabet Σ. A regular expression (regex) over following rules finitely many times. For regexes Rí and R2, the union R1 + R2, the concatenation R1 R2, the star Rý. and the question Ri are also regexes. Note that T.( R2) is defined as L ((R1) U (c).
a E Σ, or is obtained by applying the
Given set of positive and negative strings, consider the problem of synthesizing concise regex that consistent with the given strings. The examples are given by a pair (P, N) of two sets of strings, where P C Σ* is set of positive strings and N C Σ* is a set of negative strings.
Then, our goal is to find a regex R that accepts all positive strings in while rejecting all negative strings in N. Formally, R satisfies the following condition: P L(R) and L(R) n N 0.
Recurrent neural networks. An RNN is described by a function that takes an input æt and hidden state fT-1 at time step t - 1 and returns a hidden state ht at time step as follows: h4 RNN h4-1).
Given input sentence x (æ1, (21.22 In), encoder RNNeec plays its role as follows: hr RNN h1-1) where h, E R is a hidden state at time t. After processing the whole input sentence, the encoder generates fixed-size context vector that represents the sequence as follows:
c
Usually, q simply returns the last hidden state hn in one of the original sequence sequence paper by "Sutskever et al. (2014). Since the initial hidden state ho is usually randomly initialized, we simply define RNN as function that takes sequence and produces vector c follows: c RNN(xx.
Now suppose that y = (y), ...... ym ) is an output sentence that corresponds to the input sentence x in training set. Then, the decoder RNN is trained to predict the next word conditioned on all the previously predicted words and the context vector from the encoder RNN. In other words, the decoder computes probability of the translation y by decomposing the joint probability into the ordered conditional probabilities as follows:
1
ply) II plsl ....... .b.11,.))...
Now our decoder RNN dec computes each conditional probability follows:
plulyı, 12, c) softmax(W" (W -81),
where s, E Rd is the hidden state of decoder RNN at time and W E Rdx is a linear transformation
that outputs a vocabulary-sizer vector. Note that the hidden state s; is computed by
Si RNN dec MiNNdecyyi-11 c)
where Vi-1 is the previously predicted word, s;-1 is the last hidden state of decoder RNN, and c is the context vector computed from encoder RNN.
Attention mechanism. In order to resolve the long-range range dependency problem in the sequence-to- sequence model, [Bahdanau et al. (2015) defined each conditional probability time depending on dynamically computed context vector e, follows:
p(y: M/, y2. Ii-1, x) = softmax(g(s:))
where 8; is the hidden state of the decoder RNN at time i computed by 8; = RNN (Vi-1, 81-1
The context vector c is computed as a weighted sum of the hidden states from encoder: C: = Ej OijSj, where
exp(score(s,,h;))
1= exp(score($* hz))
12

---

Under review as a conference paper at ICLR 2022
Encoder: encode positive examples
Example
Example Vector
Set Vector
Duplicates
Example 2
RNN 1
Encoder
Example Vector
Encoder RNN 2
Set Vector
Example N
Example N Vector
Set Vector
Predicetd Label
Attention Layer
Example Vector
Set Vector
Decoder
Predicetd Label
RNN
Example Vector
Set Vector
Predicetd Label N
Example N Vector
Set Vector
Decoder: predict split labels for input positive examples
Figure 3: Neural network architecture of the 'NeuralSplitter" model.
Table 4: Statistics of four benchmark datasets. Numbers in parentheses are the numbers of regexes in original datasets and in front parentheses are the numbers of regexes used in our experiments.
Dataset
of Regexes
Alphabet Size
Max Length
Random
784,682
{2, 4, 6, 8, 10}
81
RegExLib
1,422 (3,072)
128
767
Snort
375 (1,254)
128
203
Polyglot Corpus
199,350 (537,800)
128
1,903
Here the function 'score' called an alignment function that computes how well the two hidden states from the encoder and the decoder, respectively, match. For example, score(s;, h2), where s; is the hidden state of the encoder time and h2 is the hidden state the decoder at time j implies the probability of aligning the part of the input sentence around position and the part of the output sentence around position j.
B NEURAL NETWORK ARCHITECTURE
Figure 3 depicts the neural network architecture of the 'NeuralSplitter' model. Note that both RNN encoders used in our neural network are bi-directional.
C EXPERIMENTAL DETAILS
C.I STATISTICS OF DATASETS
We refer the readers to Table 4 for the statistics of benchmark datasets. For random dataset, we randomly generate in total 1,000,000 regexes independently where there are 200,000 regexes for each alphabet size in {2, 4, 6, 8, 10). The number unique regexes is 784,682 as we allow duplicates in random generation.
13

---

Under review as a conference paper at ICLR 2022
Table 5: Split performance (%) of the NeuralSplitter under different settings of hyperparameters.
Dataset
RNN Cell
Dimension
# of Layers
String Accuracy
Set Accuracy
54.10
35.04
64
55.34
37.04
GRU
Random
57.41
38.03
128
57.41
38.03
256
2
57.41
38.24
384
57.21
38.25
LSTM
256
57.93
38.34
Practical
GRU
256
2
76.78
68.20
Environment. We conduct experiments on a server equipped with Intel Core i7-8700K processor with 6 cores, 48GB DDR4 memroy, and NVIDIA GTX 1080 Ti GPU. We use the neural network framework Py Torch for experiments.
D ADDITIONAL RESULTS
D.1 PERFORMANCE 'NEURAL EXAMPLE SPLITTING'
The performance of the NeuralSplitter model under different settings of hyperparameters and RNN cell types is provided in Table 5 We define two metrics, "string accuracy' and 'set accuracy', for evaluating the performance of neural example splitting. String accuracy is the ratio of correctly labeled examples from ten positive examples for each test sample. Set accuracy means the ratio of correctly labeled sets whole. If the NeuralSplitter correctly splits ten positive examples for test sample, then it is regarded as 'correctly labeled'. It is notable that the NeuralSplitter performs better on practical dataset which is apparently more complex than random dataset.
While we find that LSTM cell performs slightly better than GRU cell when the other hyperparameters are equivalent, we decide use GRU instead LSTM as GRU is known execute faster than LSTM. We also find that the performance of the NeuralSplitter is higher as we increase the number of hidden units and the number of layers until 256 and 2, respectively. We decide not to increase the number of parameters further as the computation efficiency is also very important metric in the task of regex synthesis.
D.2 PERFORMANCE COMPARISON WITH DIFFERENT TIMEOUT VALUES
Table 6 shows how the regex synthesis performance changes the timeout value changes. We perform regex synthesis with various timeout values 1, 2, 3, 5, and 10 seconds and measure the success ratio and semantic accuracy of the proposed baselines including our approach. We do include RegexGeneratore
for comparison as fails to synthesize regexes in most cases even with timeout value of 10 seconds. The result shows that Blue-Fringe algorithm succeeds in regex synthesis within I second in most cases as the success rate and semantic accuracy does not increase with higher timeout values.
On the other hand, AlphaRegex with and without our SplitRegex framework exhibits better regex synthesis success rate and semantic accuracy as timeout value increases.
D.3 SPLIT NON-SPLIT
We evaluate the performance of our SplitRegex framework by comparing the results of regex synthesis model with and without the SplitRegex framework for each test case. First, we present the number of test cases that are exclusively solved by each method. 'Win Ratio' means the ratio of test cases where each method performs better (synthesizes regex faster). We do not count the cases where both methods fail synthesize regexes when caleulating *Win Ratio (%).
14

---

Under review as a conference paper at ICLR 2022
Table 6: Regex synthesis performance (success and semantic regex accuracy) of our model and baselines over four benchmark regex datasets under different timeout values. 'AR' is abbreviations for Alpx. 'Random' dataset consists of regular expressions over alphabet of size ten.
Method
Time.
Random
RegExLib
Snort
Polyglot
Succ.
Acc.
Succ.
Acc.
Succ.
Acc.
Succ.
Acc.
AlphaRegex
34.67
32.03
9.67
9.63
8.33
8.01
42.67
42.29
SplitRegex (+AR)
58.33
55.21
20.00
19.24
71.67
67.47
64.00
62.34
AlphaRegex
41.00
38.20
12.33
12.11
9.00
8.46
46.33
45.91
SplitRegex (+AR)
66.00
62.20
20.67
19.63
72.67
68.27
64.67
62.97
AlphaRegex
45.67
42.47
13.00
12.76
13.67
12.79
51.00
50.16
SplitRegex (+AR)
67.67
63.79
21.33
19.83
73.00
68.56
65.67
63.57
AlphaRegex
51.00
47.14
14.00
13.76
14.33
13.43
53.67
52.69
SplitRegex (+AR)
72.67
68.47
21.67
20.09
73.67
69.07
66.33
63.91
AlphaRegex
55.00
50.94
19.00
18.56
16.00
14.84
57.33
56.13
10
SplitRegex (+AR)
74.00
69.54
22.00
21.22
74.33
69.51
66.33
63.91
Table 7: Comparisons of regex synthesis performance of AlphaRegex algorithm with and without SplitRegex framework on practical regex datasets.
Method
Success Ratio
Win Ratio
Runtime
Runtime for Success Cases
AlphaRegex
25.77
20.82 79.18
2.4344
0250 0.0088
SplitRegex (+AR)
46.10
1.6622
We also estimate the average amount of time taken for regex synthesis in two different cases. First, 'Runtime (seconds)' is the average amount of time taken for synthesizing regexes all test cases. the method fails to synthesize regex, then consider it as '3 seconds' which is the timeout value used for this experiment. Second, 'Runtime for Success Cases (seconds)' is the average amount of time taken for synthesizing regexes in cases where both methods succeeds in synthesizing regexes.
Experimental results on practical regex datasets (RegExLib, Snort and Polyglot Corpus dataset) are provided Table 7 Results show that SplitRegex sufficiently improves the success ratio and reduces runtime complexity taken for regex synthesis in almost 80% of test cases.
D.4 USING NEGATIVE EXAMPLES GENERATED FROM RANDOMLY PERTURBED REGEXES
As we mentioned in the second paragraph of Section 3.1 we generate negative examples by randomly substituting symbols from positive examples. We call this method 'Symbol Perturb' here.
In order generate 'harder' negative examples, we introduce noise the level of regex and call the method 'Regex Perturb'. We perform the 'Regex Perturb' by randomly choosing one of the following three manners: 1) Randomly substitute a symbol in the target regex, 2) Randomly insert subregex from the target regex, and 3) Randomly delete subregex from the target regex.
Table shows the results. We observe that our method shows better performance than the baseline RegphaRegex) for both cases. It is also seen that the 'Regex Perturb' generates harder negative examples than 'Symbol Perturb' as the performance is lower for negative examples generated by 'Regex Perturb' in general.
D.5 PERFORMANCE ON DATASETS FROM TRANSREGEX (LI ET AL. 2021
We conduct additional experiments on datasets KB13 and NL-RX- NL-RX-Turk used in Trans Li al. 2021), previous work on the multi-modal regex synthesis from both natural language
15

---

Under review as a conference paper at ICLR 2022
Table 8: Comparisons of regex synthesis performance evaluated for negative examples generated from randomly perturbed regexes.
Method
Symbol Perturb
Regex Perturb
Suce.
Acc.
Full.
Succ.
Acc.
Full.
AlphaRegex
46.20
42.60
28.40
24.00
22.70
17.50
SplitRegex (+AR)
63.20
59.72
45.30
38.75
36.25
29.00
GT Split (+AR)
76.40
73.78
61.90
57.75
54.53
44.75
Table 9: Regex synthesis performance of our model in datasets used in TransRegex (Li et al. 2021
Method
KB13
NL-RX-Turk
Succ.
Acc.
Full.
Suec.
Acc.
Full.
AlphaRegex
77.33
77.33
77.33
51.33
50.53
48.33
SplitRegex (+AR)
67.00
66.94
66.66
55.66
55.54
55.00
GT Split (+AR)
80.00
80.00
80.00
72.00
71.80
71.00
Table 10: Additional examples of neural example splitting.
Dataset
Input String
Split Result
Invatidlv%allaas@Z
Invalid Invalid Invalid
!valliasZ accountD#f
InvalidaccountD##
Polyglot
(wvaiid(pvaaddree)
{pv_address
InvalidvSemail5 C aaaliddH22mmllbboxvxx
Invalid
vSemail5
Invalid
aH2' mailbooobo
descriptions and examples. We found that regexes used in experiments use a larger set of symbols. The only difference is that some regexes from KB13 3 and NL-RX-Turk have 'and' and 'not' operators that are not supported by the standard regex library (pyre2) used in our experiments. For this reason, we conduct experiments without 'and' and 'not' operators. Table shows the experimental results. We can see that the performance of the proposed method is higher for NL-RX-Tur dataset but lower for KB13 dataset. We speculate that the main reason of the poor performance on KB13 is the size KB dataset. Note that there are only 814 regexes in KB13 and we use only 440 regexes among the 814 regexes as the rest of regexes have 'and' or 'not" that are not compatible with standard regex library.
complex and
regexes from KB 13 and NL-RX-Ture
D.6 ADDITIONAL EXAMPLES OF NEURAL EXAMPLE SPLITTING
In Table 10 present additional examples of neural example splitting to exhibit the upper limit on the hardness of regexes the proposed method cannot generate.
Note that here the target regex is 'Invalid." (account amdrressemaillmallloo on at most 10 positive examples to perform neural example splitting. it is difficult to find a split corresponding to the 'union' operator with many subregexes.
Since rely
16


Reviews:
[{"review_id": "runU1AR1tL", "reviewer": "Reviewer_fKY9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think that the proposed idea is itself simple, which means it should be easy to use, and at the same time it could potentially be useful for the task. However, I have several comments/questions, which limit my understanding and make the potential impact less clear. Resolving these would greatly strengthen the paper.\n\n1. It is not clear if the proposed approach has an upper limit on the hardness regexes it can generate. Without this understanding, the usefulness of the approach is not clear.\n\n2. Related to the previous question, how does the complexity of the regexes in this submission compare to the regexes used in the multi-modal settings such as Ye et al. (2020) and TransRegex (Li et al., 2021)? It is possible to evaluate the proposed method on their datasets while ignoring the textual inputs? \n\nBenchmarking Multimodal Regex Synthesis with Complex Structures.\nXi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Proceedings of ACL 2020.\n\n3. In the proposed approach, the results NeuralSplitter are final in the sense that after computing the output of the network (splits of the input examples) it cannot be changed and there is no search over these splits. It looks like an error of this stage can be fatal for the overall method. Evaluating how bad this effect is would strengthen the paper. \n\n4. I don't understand why the results of the Blue-Fringe baseline are evaluated so differently w.r.t. the two metrics. Such difference should be easy to see qualitatively on several examples.\n\n5. The overall performance of the SplitRegex (from table 1) is around 60%, which is higher than the baselines, but it still means that there are lots of errors. Showing and analyzing the error cases (on top of Successful examples in Table 3) would greatly strengthen the paper.\n\n6. I also feel like another metric is missing: the percentage of the regexes that are generated correctly in the sense that all the unseen by the generation process positive and negative examples (the ones used in semantic regex accuracy) are recognized correctly within the time limit. This metric is stricter and will indicate how many regexes are actually correctly generated.\n\n7. It looks like none of the baselines uses a neural network. Is it actually true that no published work put positive/negative regex examples into a neural network?\n\n8. [Clarity] I did not find a description of how numerical targets of NeuralSplitter (like 1223344) were defined. I have my guesses but am not sure.", "summary_of_the_paper": "This paper studies the problem of synthesizing regular expressions given positive/negative examples (no textual description). The core of the proposed method is a neural network that takes the examples and splits all of them into several parts. Then, an external search-based system is used to generate regex for each part. Finally, the regexes for the parts are concatenated into one overall regex.\nThe proposed system is evaluated against several baselines (the same external systems applied not to parts but to complete regexes) and is shown to bring benefits.", "summary_of_the_review": "Overall, I think that the proposed idea is itself simple, which means it should be easy to use, and at the same time it could potentially be useful for the task. However, I have several comments/questions, which limit my understanding and make the potential impact less clear. Resolving these would greatly strengthen the paper. The issues lie at the intersection of clarity, positioning, and evaluation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rmSFxaoiBFb", "reviewer": "Reviewer_qHid", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- this is a novel application for recurrent neural networks, and I am excited to see such innovative uses of neural heuristic solutions for otherwise unsolvable, hard problems\n- the experiments section is solid, and presents a few different baselines and benchmark datasets, both including real, practical examples, and synthetically generated ones.\n- the authors demonstrate and motivate the benefit that SplitRegex adds when applied in combination with existing regular expression generators\n- the paper is well-written and is easy to read and follow\n\nWeaknesses:\n- My main concern is about the approach for generating negative strings. For example, the authors do not specify whether they make sure that their negative examples are *not* matched by their regular expression. I also have doubts whether substituting a random symbol in a string really produces a very challenging counter-example; I think this is further illustrated in the Figure 3, where the performance of the model goes up as the size of the alphabet increases - because the task gets easier. The authors have presented a \"hard\" negative example \"aabbccc\", which can be incorrectly parsed by a regular expression that is too generic, but generating this \"hard\" negative from positive example \"aabbcc\" is less likely if the size of the alphabet is larger. One thing I would probably suggest to do instead could be introducing the noise at the level of regular expression itself, and then sampling strings from the \"negative or incorrect\" regular expression, but this might not be a catch-all solution either, besides the fact that deciding whether two regexes are the same or not is not trivial. I definitely think that further experimentation in this area would improve the value of the paper. \n\n- I also have a reservation about the 3 seconds time limit, as it seems to be chosen arbitrarily. I understand that it might not be practical to experiment with a larger time limit for a really large, randomly generated dataset, but at least attempting evaluating some of the smaller datasets would be great. and I am also not convinced that it is chosen wisely from the empirical perspective, because one of the baselines does not find *any* regular expressions in that amount of time, which makes including it less valuable and less informative for the reader.\n\n- the paper could be improved via further editing and proof-reading, some of the smaller typos I noticed: \n> \"do not produce desired regexes within a give time limit.\" -> \"a given\"\n> \"For each regex, we randomly generate 20 positive and negative examples of length up to certain length\" \n> \"Recurrent network networks\"", "summary_of_the_paper": "This paper proposes a novel method for employing neural networks to aid in solving an NP-hard problem. The authors use the divide-and-conquer approach to regular expression generation, by generating the regex one piece at a time. They use Recurrent Neural Network to predict which substrings should be tackled by the same sub-regular expression, and then combine multiple subregular expressions into a single regular expression.\nThe authors demonstrate how their proposed approach is helpful in combination with different regular expression generation tools, and demonstrate improved overall performance in all cases. In the experiments where SplitRegex algorithm is applied in combination with a fast regex generator (BF), their experiments indicate that some of the speed is getting traded off for semantic accuracy. In the experiments with the slowest regex generator (RegexGenerator++), they manage to speed up its computation time to go from timing out before producing any regexes to successfully producing regexes in 20% of the time. Finally, in the experiments with AlphaRegex they demonstrate that both success rate and the accuracy go up on all benchmark datasets.", "summary_of_the_review": "This is a novel approach to a problem that does not have feasible exact solutions, and I think it is an interesting use of neural networks. The proposed approach is relatively light-weight and demonstrates improvement in both run-time and performance quality in most cases. It has been evaluated quite rigorously, further evaluation can improve the quality of the paper, but even as it is, the proposed approach demonstrates non-trivial improvement for real-world scenario datasets, which I believe warrants acceptance of this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Lzb-6qCU_9e", "reviewer": "Reviewer_Nx3i", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Strengths*\n- The motivation of the work is well laid out.\n\n*Weaknesses*\n - Lack of clarity: I found many important details from the paper missing. Some of them include:\n (i) What is L ? It is stated directly in Section 3 without defining what it is and then used consistently there after without any clarification.\n (ii) Why is there a disparity between the performance of SplitRegex in terms of the two metrics (success rate and semantic regex accuracy)? From Table 1 we can see that across all datasets, SplitRegex is better only in terms of semantic regex similarity but not the success rate. Moreover, I would have expected the combination of SplitRegex with Blue-Fringe to be better in terms of semantic similarity keeping in view that without SplitRegex, Blue-Fringe is the best framework. This disparity is worrying for me and understanding why this occurs is required to put more faith in the SplitRegex system.\n(iii) There are some questionable design choices made by the authors elucidating in Section 3.1 as well as the treatment of the wildcard pattern. It seems to me that these decisions were made to fit the SplitRegex framework in particular without proper motivations justifying why these choices make sense on a system design level.\n(iv) It is not clear to me why SplitRegex works better with an increase in alphabet size while other approaches have the opposite behaviour.\n(v) Though the paper claims in the conclusions that their framework is \" ...very effective in reducing the time complexity of regex synthesis\", this has not been shown experimentally.  \n\n-  Weak experimental results: To me, the poor performance of SplitRegex in terms of success rate is concerning ( see point (ii) above)\n-  Missing related works: There are very closely related works based on the idea of divide and conquer in program synthesis that are missing from the paper. Some include:\n\n   [1] Shrivastava, Disha, H. Larochelle and Daniel Tarlow. “Learning to Combine Per-Example Solutions for Neural Program Synthesis.” NeurIPS, 2021. They find solutions that satisfy a single example (split) and then learn to combine the solutions (combine) using a neural network.\n\n   [2] Shraddha Barke, Hila Peleg, and Nadia Polikarpova. 2020. Just-in-time learning for bottom-up enumerative synthesis. Proc. ACM Program. Lang. 4, OOPSLA, Article 227 (November 2020), 29 pages. DOI:https://doi.org/10.1145/3428295\n\n- Less novel: In lieu of the other works mentioned above that have already explored the idea of example splitting and then combining the solutions for neural program synthesis, the contributions of the paper seem incremental.\n\n-  Narrow scope: It is not exactly clear to me how the approach will be used for other domains say string manipulations programs or straight-line code or programs containing data and control-flow structures. It seems the approach is catered specifically to regular expressions that make the approach extremely narrow in scope and hence less significant.\n\n*Suggestions/Comments*\n- Figure 1 and Figure 2 can be combined into a single Figure. Both have a lot of redundant information.\n- Results on other values of timeout and other domains ( apart from Regex) will be useful.", "summary_of_the_paper": "The paper proposes a method to synthesize regular expressions by first splitting positive examples and synthesizing regexes for those and then combining these while using negative examples as an additional constraint. They perform experiments on few regex baselines and show better results in one of the two metrices.", "summary_of_the_review": "The paper has less technical novelty, weak experimental results, lack of clarity, missing related works and narrow scope in terms of applicability to other programs that are not regex. I will suggest improvement in writing in terms of clarity and a thorough evaluation across other DSLs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AzrtGh04nj", "reviewer": "Reviewer_Nyta", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the idea is neat and simple, and the consistent improvement from the existing toolkits is appealing. I have several comments below: \n\n1. The modeling part seems a bit arbitrary. While I understand that this paper is a kind of proof-of-concept, the segmentation model can potentially be improved in the following ways: \n- The RNN mentioned in appendix A is unidirectional. However one may want to at least use bidirectional ones in Sec 3.2, for RNN_enc1 (or Transformers)\nIdeally the component of RNN_enc2 should be order invariant (i.e., encode a set of strings, rather than a list of strings with particular order), something like DeepSet should be considered\n- Ideally the predicted segmental label should be permutation invariant as well. \n- Regarding the evaluation of the segmentation model itself, one can use the optimal transport metrics, following the practice in the literature. \nI would suggest the authors investigate a bit more carefully into the literature of segmentation models, either supervised or unsupervised. \n\n2. Is it possible to evaluate the performance based on the ground-truth split, rather than the model predicted splits? In this way we can get to know what is the upper bound of the performance, and see how far away we are from this upper bound. \n\n3. The model relies on the existing synthesis tools for the sub-RegExpr synthesis, so the bottleneck would be the synthesis of the most difficult sub-expression. Imagine if the sequence is formed from a single segment and in this case the proposed model would not help in any way. I’m wondering how often this happens, or if there’s a dominant segment that takes the most amount of time, how much speed up can we get with the neural split model? \n", "summary_of_the_paper": "This paper proposed a way of synthesizing RegEx from positive and negative sample specifications. The main idea is to split the positive samples into segments, such that one can leverage any existing RegEx synthesis tool to synthesize the sub-regex out of the segments of specifications. Finally the entire RegEx is obtained via the concatenation of these sub-RegExes. The paper proposes to split the specifications using RNN, which is trained via synthetically generated data. Experiments on synthetic and some benchmark datasets show that the proposed method is able to outperform the existing counterparts in most cases.", "summary_of_the_review": "The paper presents a practical and neat idea for RegEx synthesis that can leverage existing synthesis tools as subroutines, based on the proposed neural-split model. However the neural splitter is not technically solid, and there can be more experimental studies for the sake of completeness and the understanding of current limitations. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There were genuine differences of opinion here. I saw reviews of 8,6,5,5.
In these cases, I do try to check if the 8 has a really compelling argument and err on the side of accepting, but here I think both the positive and negative reviews have fair points, so I am inclined to recommend rejection here.

I think the good news is that a lot of the negative stuff was around scoping/writing/related-work, and so it should be (relatively) easy to shore up this submission into something that will get better reviews in the next conference cycle.
Decision: Reject