# Real-World Compositional Generalization
with Disentangled Sequence-to-Sequence Learning

Hao Zheng and Mirella Lapata
Institute for Language, Cognition and Computation
School of Informatics, University of Edinburgh
10 Crichton Street, Edinburgh EH8 9AB
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Compositional generalization is a basic mechanism in human language learning,
which current neural networks struggle with. A recently proposed Disentangled
sequence-to-sequence model (Dangle) shows promising generalization capability
by learning specialized encodings for each decoding step. We introduce two key
modifications to this model which encourage more disentangled representations
and improve its compute and memory efficiency, allowing us to tackle
compositional generalization in a more realistic setting. Specifically,
instead of adaptively re-encoding source keys and values at each time step, we
disentangle their representations and only re-encode keys periodically, at
some interval. Our new architecture leads to better generalization performance
across _existing_ tasks and datasets, and a _new_ machine translation
benchmark which we create by detecting _naturally occurring_ compositional
patterns in relation to a training set. We show this methodology better
emulates real-world requirements than artificial challenges.111Our code and
dataset will be available at xxx.yyy.zzz.

##  1 Introduction

The Transformer architecture Vaswani et al. (2017) and variants thereof have
become ubiquitous in natural language processing. Despite widespread adoption,
there is mounting evidence that Transformers as sequence transduction models
struggle with _compositional generalization_ Kim and Linzen (2020); Keysers et
al. (2020); Li et al. (2021). It is basically the ability to produce and
understand a potentially infinite number of novel linguistic expressions by
systematically combining known atomic components Chomsky (2014); Montague
(1970). Attempts to overcome this limitation have explored various ways to
explicitly inject compositional bias through data augmentation Jia and Liang
(2016); Akyürek et al. (2021); Andreas (2020); Wang et al. (2021) or new
training objectives Conklin et al. (2021); Oren et al. (2020); Yin et al.
(2021). The majority of existing approaches have been designed with semantic
parsing in mind, and as a result adopt domain- and task-specific grammars or
rules which do not extend to other tasks (e.g., machine translation).

In this work we aim to improve generalization via general architectural
modifications which are applicable to a wide range of tasks. Our starting
point are Zheng and Lapata (2022) who unveil that one of the reasons hindering
compositional generalization in Transformers relates to their representations
being entangled. They introduce Dangle, a sequence-to-sequence model, which
learns more Disentangled representations by adaptively re-encoding (at each
time step) the source input. For each decoding step, Dangle learns specialized
source encodings by conditioning on the newly decoded target which leads to
better compositional generalization compared to vanilla Transformers where
source encodings are shared throughout decoding. Although promising, their
results are based on synthetic datasets, leaving open the question of whether
Dangle is effective in real-world settings involving both complex natural
language and compositional generalization.

We present two key modifications to Dangle which encourage learning _more
disentangled_ representations _more efficiently_. The need to perform re-
encoding at each time step substantially affects Dangle’s training time and
memory footprint. It becomes prohibitively expensive on datasets with long
target sequences, e.g., programs with 400+ tokens in datasets like SMCalFlow
Andreas et al. (2020). To alleviate this problem, instead of adaptively re-
encoding at each time step, we only re-encode periodically, at some interval.
Our decoder is no different from a vanilla Transformer decoder except that it
just re-encodes once in a while in order to update its history information.
Our second modification concerns disentangling the representations of source
keys and values, based on which the encoder in Dangle (and also in
Transformers) passes source information to the decoder. Instead of computing
keys and values using shared source encodings, we disassociate their
representations: we encode source _values once_ and re-encode _keys
periodically_.

We evaluate the proposed model on existing benchmarks Andreas et al. (2020);
Li et al. (2021) and a new dataset which we create to better emulate a real-
world setting. We develop a new methodology for _detecting_ examples
representative of compositional generalization in naturally occurring text.
Given a training and test set: (a) we discard examples from the test set that
contain out-of-vocabulary (OOV) or rare words (in relation to training) to
exclude novel atoms which are out of scope for compositional generalization;
(b) we then measure how compositional a certain test example is with respect
to the training corpus; we introduce a metric which allows us to identify a
candidate pool of highly compositional examples; (c) using uncertainty
estimation, we further select examples from the pool that are both
compositional in terms of surface form and challenging in terms of
generalization difficulty. Following these three steps, we create a _machine
translation_ benchmark using the IWSLT 2014 German-English dataset as our
training corpus and the WMT 2014 German-English shared task as our test
corpus.

Experimental results demonstrate that our new architecture achieves better
generalization performance across tasks and datasets and is adept at handling
real-world challenges. Machine translation experiments on a diverse corpus of
1.3M WMT examples show it is particularly effective for long-tail
compositional patterns.

##  2 Background: The Dangle Model

We first describe Dangle, the Disentangled Transformer model introduced in
Zheng and Lapata (2022) focusing on their encoder-decoder architecture which
they show delivers better performance on complex tasks like machine
translation.

Let $X=[x_{1},x_{2},...,x_{n}]$ denote a source sequence; let
$f_{\texttt{Encoder}}$ and $f_{\texttt{Decoder}}$ denote a Transformer encoder
and decoder, respectively. $X$ is first encoded into a sequence of
contextualized representations $N$:

$\displaystyle N$ $\displaystyle=$ $\displaystyle f_{\texttt{Encoder}}(X)$ (1)

which are then used to decode target tokens $[y_{1},y_{2},...,y_{m}]$ one by
one. At the $t$-th decoding step, the Transformer takes $y_{t}$ as input,
reusing the source encodings $N$ and target memory $M_{t-1}$ which contains
the history hidden states of all decoder layers corresponding to past tokens
$[y_{1},y_{2},...,y_{t-1}]$:

$\displaystyle y_{t+1},M_{t}=f_{\texttt{Decoder}}(y_{t},M_{t-1},N)$ (2)

This step not only generates a new token $y_{t+1}$, but also updates the
internal target memory $M_{t}$ by concatenating $M_{t-1}$ with the newly
calculated hidden states corresponding to $y_{t}$.

Dangle differs from vanilla Transformers in that it concatenates the source
input with the previously decoded target to construct target-dependent input
for _adaptive_ decoding:

$\displaystyle C_{t}$ $\displaystyle=$
$\displaystyle[x_{1},x_{2},...,x_{n},y_{1},...,y_{t}]$ (3) $\displaystyle
H_{t}$ $\displaystyle=$ $\displaystyle f_{\texttt{Adaptive\\_Encoder}}(C_{t})$
(4)

The adaptive encoder consists of two components. $C_{t}$ is first fed to
$k_{1}$ Transformer encoder layers to fuse the target information:

$\displaystyle\bar{H}_{t}=f_{\texttt{Adaptive\\_Encoder}_{1}}(C_{t})$ (5)

where $\bar{H}_{t}$ is a sequence of contextualized representations
$[\bar{h}_{t,1},\bar{h}_{t,2},...,\bar{h}_{t,n},\bar{h}_{t,n+1},...,\bar{h}_{t,n+t}]$.
Then, the first $n$ vectors corresponding to source tokens are extracted and
fed to another $k_{2}$ Transformer encoder layers for further processing:

$\displaystyle H_{t}$ $\displaystyle=$ $\displaystyle
f_{\texttt{Adaptive\\_Encoder}_{2}}(\bar{H}_{t}[:n])$ (6)

Finally, the adaptive source encodings $H_{t}$ together with the target
context $[y_{1},y_{2},...,y_{t}]$ are fed to a Transformer decoder to predict
$y_{t+1}$:

$\displaystyle y_{t+1},M_{t}=f_{\texttt{Decoder}}(y_{<t+1},\\{\\},H_{t})$ (7)

In a departure from vanilla Transformers, Dangle does not reuse the target
memory from previous steps, but instead re-computes _all_ target-side hidden
states based on new source encodings $H_{t}$.

Similarly to Transformers, Dangle accesses source information at each decoding
step via encoder-decoder attention layers where the same encodings $H_{t}$ are
used to compute both keys $K_{t}$ and values $V_{t}$:

$\displaystyle K_{t}$ $\displaystyle=$ $\displaystyle H_{t}W^{K}$ (8)
$\displaystyle V_{t}$ $\displaystyle=$ $\displaystyle H_{t}W^{V}$ (9)
$\displaystyle O_{t}$ $\displaystyle=$
$\displaystyle\mathrm{Attention}(Q_{t},K_{t},V_{t})$ (10)

where key and value projections $W^{K}$ and $W^{V}$ are parameter matrices;
and $Q_{t}$, $K_{t}$, $V_{t}$, and $O_{t}$ are respectively query, key, value,
and output matrices, at time step $t$.

##  3 The R-Dangle Model

In this section, we describe the proposed model, which we call R-Dangle as a
shorthand for Real-world Disentangled Transformer.

###  3.1 Re-encoding at Intervals

The need to perform re-encoding (and also re-decoding) at each time step
substantially increases Dangle’s training cost and memory footprint, so that
it becomes computationally infeasible for real-world language tasks with very
long target sequences (e.g., in the region of hundreds of tokens). Adaptively
re-encoding at every time step essentially means separating out relevant
source concepts for each prediction. However, the Transformer is largely
capable of encoding source phrases and decoding corresponding target phrases
(or logical form fragments in semantic parsing), as evidenced by its
remarkable success in many machine translation and semantic parsing benchmarks
Vaswani et al. (2017); Keysers et al. (2020); Zheng and Lapata (2021). This
entails that the entanglement problem (i.e., not being able to disassociate
the representations of different concepts for a sequence of predictions) does
not occur very frequently. We therefore relax the strict constraint of re-
encoding at every step in favor of the more flexible strategy of re-encoding
at intervals.

Given source sequence $X=[x_{1},x_{2},...,x_{n}]$, we specify
$P=[t_{1},t_{2},...,t_{l}](t_{i+1}-t_{i}=~{}o)$ in advance, i.e., a sequence
of re-encoding points with interval $o$. Then, during decoding, when reaching
a re-encoding point $t(t=t_{i})$, we update source encodings $H_{t}$ and
target memory $M_{t}$:

$\displaystyle H_{t}$ $\displaystyle=$ $\displaystyle
f_{\texttt{Adaptive\\_Encoder}}(C_{t})$ (11) $\displaystyle y_{t+1},M_{t}$
$\displaystyle=$ $\displaystyle
f_{\texttt{Decoder}}(y_{<t+1},\\{\\},H_{t})\quad$ (12)

where $f_{\texttt{Adaptive\\_Encoder}}$ denotes the adaptive encoder described
in Section 2. For the next time step $t(t_{i}<t<t_{i+1})$, we fall back to the
vanilla Transformer decoder using the source encodings $H_{t_{i}}$ computed at
time step $t_{i}$:

$\displaystyle y_{t+1},M_{t}=f_{\texttt{Decoder}}(y_{t},M_{t-1},H_{t_{i}})$
(13)

Note that we always set $t_{1}$ to 1 to perform adaptive encoding at the first
time step.

Selected | Examples | Compositional Degree | Uncertainty
---|---|---|---
✗ |  but what can we do about this ? | 2 / 8 = 0.25 | —
✗ |  please report all changes here . | 5 / 6 = 0.83 | 0.054
✔ |  you have disabled your javascript ! | 5 / 6 = 0.83 | 0.274
|  |  |
Table 1: Candidate examples from the WMT corpus. Different $n$-grams
previously seen in the IWSTL training corpus are highlighted in color. The
first example is composed of two $n$-grams (but and what can we do about
this?) with a compositional degree 0.25, and is discarded in the second stage.
The second example has a high compositional degree but receives a low
uncertainty score, and is thus filtered in the third stage. The third example
is high in terms of both compositional degree and uncertainty, and is included
in the compositional test set.

###  3.2 Disentangling Keys and Values

During decoding, Dangle accesses source information via cross-attention (also
known as encoder-decoder attention) layers where the same source encodings are
used to compute both keys _and_ values. The core design principle underlying
Dangle is that learning specialized representations for different purposes
will encourage the model to zero in on relevant concepts, thereby
disentangling their representations. Based on the same philosophy, we assume
that source keys and values encapsulate different aspects of source
information, and that learning more specialized representations for them would
further improve disentanglement, through the separation of the concepts
involved.

A straightforward way to implement this idea is using two separately
parameterized encoders to calculate two groups of source encodings (i.e.,
corresponding to keys and values, respectively) during re-encoding. However,
in our preliminary experiments, we observed this leads to serious overfitting
and performance degradation. Instead, we propose to encode values once and
only update keys during adaptive encoding. We compute source _values_ via the
standard Transformer encoder:

$\displaystyle H^{v}$ $\displaystyle=$ $\displaystyle f_{\texttt{Encoder}}(X)$
(14)

and adaptively re-encode source _keys_ at an interval:

$\displaystyle H_{t}^{k}\mkern-13.0mu$ $\displaystyle=$
$\displaystyle\mkern-13.0muf_{\texttt{Adaptive\\_Encoder}}(C_{t})$ (15)
$\displaystyle y_{t+1},M_{t}\mkern-13.0mu$ $\displaystyle=$
$\displaystyle\mkern-13.0muf_{\texttt{KV\\_Decoder}}(y_{<t+1},\\{\\},H^{v},H_{t}^{k})\quad\quad$
(16)

where $f_{\texttt{KV\\_Decoder}}$ denotes a slightly modified Transformer
decoder where source keys and values in each cross-attention layer are
calculated based on different source encodings:

$\displaystyle K_{t}$ $\displaystyle=$ $\displaystyle H_{t}^{k}W^{K}$ (17)
$\displaystyle V$ $\displaystyle=$ $\displaystyle H^{v}W^{V}$ (18)
$\displaystyle O_{t}$ $\displaystyle=$
$\displaystyle\mathrm{Attention}(Q_{t},K_{t},V)$ (19)

At time step $t$ (where $t_{i}<t<t_{i+1}$), we perform vanilla Transformer
decoding:

$\displaystyle
y_{t+1},M_{t}=f_{\texttt{KV\\_Decoder}}(y_{t},M_{t-1},H^{v},H_{t_{i}}^{k})$
(20)

Note that fully sharing values could potentially cause some entanglement,
however, we we did not observe this in practice. We also experimented with a
variant where keys are shared and values are repeatedly re-computed but
empirically observed it obtains significantly worse generalization performance
than the value-sharing architecture described above. This indicates that
entanglement is more likely to occur when sharing keys.

##  4 A Real-world Compositional Generalization Challenge

Models of compositional generalization are as good as the benchmarks they are
evaluated on. A few existing benchmarks are made of artificially synthesized
examples using a grammar or rules to systematically control for different
types of generalization Lake and Baroni (2018a); Kim and Linzen (2020);
Keysers et al. (2020); Li et al. (2021). Unfortunately, synthetic datasets
lack the complexity of real natural language and may lead to simplistic
modeling solutions that do not generalize to real world settings Dankers et
al. (2022). Other benchmarks focus on naturally occurring examples but have
artificial train-test splits Finegan-Dollak et al. (2018), based on heuristics
(e.g., query patterns). Again, the types of compositional generalization
attested therein may not reflect real-world occurrence.

It is fair to assume that a SOTA model deployed in the wild, e.g., a
Transformer-based translation system, will be constantly presented with new
test examples. Many of them could be similar to seen training instances or
compositionally different but in a way that does not pose serious
generalization challenges. An ideal benchmark for evaluating compositional
generalization should therefore consist of phenomena that are of practical
interest while challenging for SOTA models. To this end, we create ReaCT, a
new REAl-world dataset for Compositional generalization in machine
Translation. Our key idea is to obtain a generalization test set by
_detecting_ compositional patterns in relation to an existing training set
from a large and diverse pool of candidates. Specifically, we use the IWSLT
2014 German $\to$ English dataset as our training corpus and the WMT 2014
German $\to$ English shared task as our test corpus (see Section 5 for
details) and detect from the pool of WMT instances those that exemplify
compositional generalization with respect to IWSLT. This procedure identifies
naturally occurring compositional patterns which we hope better represent
practical generalization requirements than artificially constructed
challenges.

In the following, we describe how we identify examples that demand
compositional generalization. While we create our new benchmark with machine
translation in mind, our methodology is general and applicable to other
settings such as semantic parsing. For instance, we could take a relatively
small set of annotated user queries as our training set and create a
generalization challenge from a large pool of unlabeled user queries.

#### Filtering Out-of-Vocabulary Atoms

Compositional generalization involves generalizing to _new_ compositions of
_known_ atoms. The WMT corpus includes many new semantic and syntactic atoms
that are not attested in IWSLT. A large number of these are out-of-vocabulary
(OOV) words which are by definition unknown and out of scope for compositional
generalization. We thus discard WMT examples with words occurring less than 3
times in the IWSLT training set which gives us approximately a pool of 1.3M
examples. For simplicity, we do not consider any other types of new atoms such
as unseen word senses or syntactic patterns.

#### Measuring Compositionality

How to define the notion of compositional generalization is a central question
in creating a benchmark. Previous definitions have mostly centered around
linguistic notions such as constituent or context-free grammars Kim and Linzen
(2020); Keysers et al. (2020); Li et al. (2021). Since we do not wish to
synthesize artificial examples but rather detect them in real-world
utterances, relying on the notion of constituent might be problematic.
Sentences in the wild are often noisy and ungrammatical and it is far from
trivial to analyze their syntactic structure so as to reliably identify new
compositions of known constituents. We overcome this problem by devising a
metric based on n-gram matching which assesses how compositional a certain
example is with respect to a training corpus.

Specifically, we first create a lookup dictionary of atomic units by
extracting all $n$-grams that occur more than 3 times in the training corpus.
Given a candidate sentence, we search the dictionary for the minimum number of
$n$-grams that can be composed to form the sentence. For example, for sentence
“$x_{1}x_{2}x_{3}x_{4}x_{5}$” and dictionary
$(x_{1},x_{2},x_{3}x_{4},x_{5},x_{1}x_{2},x_{3}x_{4}x_{5},)$, the minimum set
of such $n$-grams is $(x_{1}x_{2},x_{3}x_{4}x_{5})$. A sentence’s
_compositional degree_ with respect to the training corpus is defined as the
ratio of the minimum number of $n$-grams to its length (e.g., 2/5 = 0.4 for
the above example). We select the top 60,000 non-overlapping examples with the
highest compositional degree as our _candidate pool_. As we discuss in Section
6, compositional degree further allows us to examine at a finer level of
granularity how model performance changes as test examples become increasingly
compositional.

#### Estimating Uncertainty

Examples with the same compositional degree could pose more or less difficulty
to neural sequence models (see last two utterances in Table 1). Ideally, we
would like to identify instances that are compositional in terms of surface
form _and_ hard in terms of the underlying generalization (see third example
in Table 1). We detect such examples using a metric based on _uncertainty
estimation_ and orthogonal to compositional degree. We quantify predictive
uncertainty based on model ensembles, a method which has been successfully
applied to detecting misclassifications and out-of-distribution examples
Lakshminarayanan et al. (2017); Malinin and Gales (2021).

We follow the uncertainty estimation framework introduced in Malinin and Gales
(2021) for sequence prediction tasks. Specifically, we train 10 Transformer
models with different random initializations on IWSLT (our training corpus),
and run inference over the candidate pool created in the previous stage; for
each example in this pool, we measure the disagreement between ensemble models
using _reverse mutual information_ , a novel measure Malinin (2019); Malinin
and Gales (2021) which quantifies _knowledge uncertainty_ , i.e., a model’s
uncertainty in its prediction due to lack of understanding of the data rather
than any intrinsic uncertainty associated with the task (e.g., a word could
have multiple correct translations). We use the token-level approximation of
knowledge uncertainty.

We empirically find that the most uncertain examples are extremely noisy and
barely legible (e.g., they include abbreviations, typos, and non-standard
spelling). We thus therefore throw away the top 2,000 uncertain examples and
randomly sample 3,000 instances from the next 18,000 most uncertain examples
in an attempt to create a generalization test set with diverse language
patterns and different levels of uncertainty.

|  | Comp | Word $n$-gram | POS $n$-gram
---|---|---|---|---
Dataset | # examples | Degree | 2 | 3 | 2 | 3
COGS | 21,000 | 0.392 | 6,097 | 24,275 | 12 | 27
CoGnition | 10,800 | 0.502 | 1,865 | 13,344 | 1 | 38
CFQ | 11,968 | 0.268 | 168 | 2,736 | 8 | 30
ReaCT |  3,000 | 0.811 | 19,315 | 33,652 | 76 | 638
|  |  |  |  |  |

Table 2: Dataset Statistics: unique novel $n$-grams computed over words and
parts of speech in ReaCT, and test partitions of COGS, CoGnition, and CFQ
benchmarks.

#### Analysis

We analyze the compositional nature of ReaCT by comparing it to several
popular benchmarks. Specifically, for all datasets, we count the number of
novel test set $n$-grams that have not been seen in the training. We extract
$n$-grams over words and parts of speech (POS); word-based $n$-grams represent
more superficial lexical composition while $n$-grams based on POS tags reflect
more of syntactic composition.

As shown in Table 2, despite being considerably smaller compared to other
benchmarks (see # examples column), ReaCT presents substantially more diverse
patterns in terms of lexical and syntactic composition. It displays a much
bigger number of novel word $n$-grams, which is perhaps not surprising. Being
a real-world dataset, it has a larger vocabulary and more linguistic
variation. While our dataset creation process does not explicitly target novel
syntactic patterns (approximated by POS $n$-grams), ReaCT still includes
substantially more compared to other benchmarks. This suggests that it
captures the complexity of real-world compositional generalization to a
greater extent than what is achieved when examples are synthesized
artificially. We show ReaCT examples with novel POS $n$-gram compositions in
Appendix A (Table 6).

##  5 Experimental Setup

#### Datasets

We evaluated R-Dangle on two machine translation datasets and one semantic
parsing benchmark which we selected to maximally reflect natural language
variations and real-world generalization challenges. These include: (a) ReaCT,
the machine translation benchmark developed in this paper; we used the IWSLT
2014 De$\to$En test set as the in-domain test set and create an out-of-
distribution test set from the WMT’14 De$\to$En training corpus; (b) CoGnition
Li et al. (2021) is a semi-natural machine translation benchmark focusing on
English-Chinese sentence pairs; source sentences were taken from the Story
Cloze Test and ROCStories Corpora Mostafazadeh et al. (2016, 2017) and target
sentences were constructed by post-editing the output of a machine translation
engine; (c) SMCalFlow-CS Andreas et al. (2020) is a semantic parsing dataset
for task-oriented dialogue, featuring real-world human-generated utterances
about calendar management; following previous work Yin et al. (2021); Qiu et
al. (2022), we report experiments on the compositional skills split,
considering a few-shot learning scenario (with 6, 16, and 32 training
examples). See Appendix B for more detail on datasets.

#### Models

On machine translation, our experiments evaluated two variants of R-Dangle
depending on whether keys and values are shared (R-Dangleshr) or separate
(R-Danglesep). We implemented all machine translation models with fairseq Ott
et al. (2019). We compared R-Dangle against a vanilla Transformer Vaswani et
al. (2017) and the original Dangle model Zheng and Lapata (2022) which use the
popular fairseq configuration transformer_iwslt_de_en. We also implemented
bigger variants of these models using 12 encoder layers and 12 decoder layers
which empirically led to better performance. R-Dangleshr and R-Danglesep also
use a 12-layer decoder. We tuned the number of layers of the adaptive
components ($k_{1}=2$ and $k_{2}=10$) on the development set. For R-Danglesep,
we adopted a 10-layer value encoder and a 10-layer key encoder ($k_{1}=2$ and
$k_{2}=8$), with the top 8 layers in the two encoders being shared. This
configuration produced 12 differently parametrized transformer encoder layers,
maintaining identical model size to comparison systems.

Previous work Qiu et al. (2022) has shown the advantage of pre-trained models
on the SMCalFlow-CS dataset. For our semantic parsing experiments, we
therefore built R-Dangle on top of BART-large Lewis et al. (2020). We only
report results with R-Dangleshr as the R-Danglesep architecture is not
compatible with BART. We again set $k_{1}=2$ and $k_{2}=10$. We provide more
detail on model configurations in Appendix C.

CoGnition | 1 | 2 | 4 | 8
---|---|---|---|---
R-Dangleshr | 62.5 | 62.3 | 62.3 | 61.9
R-Danglesep | 63.4 | 63.1 | 62.3 | 62.1
ReaCT | 1 | 2 | 4 | 8
R-Dangleshr | 11.8 | 11.9 | 11.8 | 11.6
R-Danglesep | 12.3 | 12.2 | 11.9 | 11.7
|  |  |  |

Table 3: BLEU score for R-Dangle variants (with different re-encoding
intervals) on CoGnition and ReaCT compositional generalization test sets. Note
that R-Dangleshr with interval 1 is Dangle.

Models | CoGnition | ReaCT
---|---|---
$\downarrow~{}$ErrRInst |  $\downarrow$ ErrRAggr |  $\uparrow$ ind-test |  $\uparrow$cg-test |  $\uparrow$IWSLT14 |  $\uparrow$cg-test |
Transformer Zheng and Lapata (2022) | 30.5 | 63.8 | 69.2 | 59.4 | 34.4 | 9.5 |
Dangle Zheng and Lapata (2022) | 22.8 | 50.6 | 69.1 | 60.6 | — | — |
Transformer (our implementation) | 23.4 | 53.7 | 70.8 | 61.9 | 36.0 | 11.4 |
Dangle (our implementation) | 19.7 | 47.0 | 70.6 | 62.5 | 36.1 | 11.8 |
R-Danglesep (interval = 1 ) | 16.0 | 42.1 | 70.7 | 63.4 | 36.0 | 12.3 |
|  |  |  |  |  |  |

Table 4: Machine Translation Results: we compare R-Dangle to baseline models
on CoGnition and ReaCT. For CoGnition, we report instance-wise and aggregate
compound translation error rates (ErrR) on the compositional generalization
test set (cg-test) and BLEU on both in-domain test set (ind-test) and cg-test.
For ReaCT, we report BLEU on the in-domain IWSLT 2014 De$\rightarrow$En test
set and the compositional generalization test set (cg-test) created in this
paper. Results are averaged over 5 random runs on CoGnition and 3 random runs
on ReaCT.

##  6 Results

#### Disentangling Keys and Values Improves Generalization

Table 3 reports the BLEU score Papineni et al. (2002) achieved by the two
R-Dangle variants on ReaCT and CoGnition, across different re-encoding
intervals. R-Danglesep is consistently better than R-Dangleshr which confirms
that representing keys and values separately is beneficial. We also observe
that smaller intervals lead to better performance (we discuss this further
later).

Table 4 compares R-Danglesep (with interval 1) against baseline models. In
addition to BLUE, we report novel compound translation error rate, a metric
introduced in Li et al. (2021) to quantify the extent to which novel compounds
are mistranslated. We compute error rate over instances and an aggregate score
over contexts. R-Danglesep delivers compositional generalization gains over
Dangle and vanilla Transformer models (both in terms of BLEU _and_ compound
translation error rate), even though their performance improves when adopting
a larger 12-layer network. R-Danglesep achieves a new state of the art on
CoGnition (a gain of 0.9 BLEU points over Dangle and 1.5 BLEU points over the
Transformer baseline). R-Danglesep fares similarly on ReaCT; it is
significantly superior to the Transformer model by 0.9 BLEU points, and Dangle
by 0.5 BLEU points. Moreover, improvements on compositional generalisation are
not at the expense of in-domain performance (R-Dangle obtains similar
performance to the Transformer and Dangle on the IWSLT2014 in-domain test
set).

System | 8-$\mathbb{C}$ | 16-$\mathbb{C}$ | 32-$\mathbb{C}$
---|---|---|---
BERT2SEQ | — | 33.6 | 53.5
BERT2SEQ+SS | — | 46.8 | 61.7
C2F | — | 40.6 | 54.6
C2F$+$SS | — | 47.4 | 61.9
T5 | 34.7 | 44.7 | 59.0
T5$+$CSL | 51.6 | 61.4 | 70.4
BART | 32.1 | 47.2 | 61.9
$+$R-Dangleshr (interval = 6) | 36.3 | 50.6 | 64.1
|  |  |

Table 5: Semantic Parsing Results: we compare R-Dangle to various systems on SMCalFlow-CS. *-$\mathbb{C}$ denote different settings with 8, 16, and 32 cross-domain examples added to the training set. Results for BERT and C2F models are from Yin et al. (2021). Results for T5 models are from Qiu et al. (2022). Results for BART and R-Dangle are averaged over 3 random runs. (a) | (b)
---|---
$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$0$$0.2$$0.4$$0.6$$0.8$Compositional DegreeDifference in BLEU | $0$$50$$100$$150$$5$$10$$15$IntervalTraining time (hours)$46$$47$$48$$49$$50$Accuracy (%)
Figure 1: (a) Difference in BLEU score between R-Danglesep (interval = 1) and
Transformer vs compositional degree. A positive score means R-Danglesep is
better than Transformer. Each data point is computed on 30K WMT examples.
R-Dangle shows increasing performance improvements as test examples become
more compositional. (b) Training cost (hours) and test accuracy vs interval
length. R-Dangleshr was trained on SMCalFlow-CS (16-$\mathbb{C}$) using 4 A100
GPUs.

#### R-Dangle Can Handle Long-tail Compositional Patterns Bettter

We next examine model performance on real-world examples with diverse language
and different levels of composition. Specifically, we train R-Danglesep
(interval=1) and a Transformer on the IWSTL14 corpus and test on the pool of
1.3M WMT examples obtained after filtering OOV words. Figure 1a plots the
difference in BLEU between the two models against compositional degree. This
fine-grained evaluation reveals that they perform similarly on the majority of
less compositional examples (BLUE difference is around zero), however, the
performance gap becomes larger with more compositional examples (higher
difference means higher BLEU for R-Danglesep). This indicates that R-Dangle is
particularly effective for handling long-tail compositional patterns.

####  R-Dangle Boosts the Performance of Pretrained Models

The “pre-train and fine-tune” paradigm Peters et al. (2018); Devlin et al.
(2019); Raffel et al. (2020); Lewis et al. (2020) has been widely adopted in
NLP, and semantic parsing is no exception Shin et al. (2021); Qiu et al.
(2022). We further investigate R-Dangle’s performance when combined with a
pre-trained model on the SMCalFlow-CS dataset (across the three cross-domain
settings). Table 5 shows that R-Dangleshr boosts the performance of BART-
large, which suggests that generalization improvements brought by R-Dangle are
complementary to generalization benefits afforded by large-scale pre-training
(see Zheng and Lapata 2022 for a similar conclusion). The proposed model
effectively marries pre-training with disentangled representation learning to
achieve better generalization.

In Table 5, we also compare R-Dangle with other top-performing models on
SMCalFlow-CS. These include: (a) a sequence-to-sequence model with a BERT
encoder and an LSTM decoder using a copy mechanism (BERT2SEQ; Yin et al.
2021); (b) the coarse-to-fine model of Dong and Lapata (2018) which uses a
BERT encoder and a structured decoder that factorizes the generation of a
program into sketch and value predictions; (c) and combinations of these two
models with span-supervised attention ($+$SS; Yin et al. 2021). We also
include a T5 model and variant thereof trained on additional data using a
model called Compositional Structure Learner (CSL) to generate examples for
data augmentation (T5+CSL; Qiu et al. 2022). R-Dangle with BART performs best
among models that do _not_ use data augmentation across compositional
settings. Note that our proposal is orthogonal to CSL and could also benefit
from data augmentation.

#### Larger Re-encoding Intervals Reduce Training Cost

The results in Table 3 indicate that re-encoding correlates with R-Dangle’s
generalization ability, at least for machine translation. Both model variants
experience a drop in BLEU points when increasing the re-encoding interval to
8. We hypothesize that this sensitivity to interval length is task-related;
target sequences in machine translation are relatively short and
representative of real language, whereas in SMCalFlow-CS, the average length
of target sequences (in formal language) is 99.5 and the maximum length is
411. It is computationally infeasible to train R-Dangle with small intervals
on this dataset, however, larger intervals still produce significant
performance gains.

Figure 1b shows how accuracy and training time vary with interval length on
SMCalFlow-CS with the 16-$\mathbb{C}$ setting. Larger intervals substantially
reduce training cost with an optimal speed-accuracy trade off in between 10
and 50. For instance, interval 40 yields a 4x speed-up compared to interval 10
while achieving 50.3% accuracy. Finding a trade-off between generalization and
efficiency is an open research problem which we leave to future work.

##  7 Related Work

The realization that neural sequence-to-sequence models struggle with
compositional generalization has led to numerous research efforts aiming to
precisely define this problem and explore possible solutions to it. A line of
research focuses on benchmarks which capture different aspects of
compositional generalization. Finegan-Dollak et al. (2018) repurpose existing
semantic parsing benchmarks for compositional generalization by creating more
challenging splits based on logical form patterns. In SCAN Lake and Baroni
(2018b) compositional generalization is represented by unseen combinations of
seen actions (e.g., JUMP LTURN). Keysers et al. (2020) define compositional
generalization as generalizing to examples with maximum compound divergence
(e.g., combinations of entities and relations) while guaranteeing similar atom
distribution to the training set. Kim and Linzen (2020) design five linguistic
types of compositional generalization such as generalizing phrase nesting to
unseen depths. In ReaCT, our definition of compositional generalization is
dependent on the data distribution of the candidate corpus, which determines
what compositional patterns are of practical interest and how frequently they
occur.

Another line of work focuses on modeling solutions, mostly ways to explicitly
instil compositional bias into neural models. This can be achieved by adopting
a more conventional grammar-based approach Herzig and Berant (2021) or
incorporating a lexicon or lexicon-style alignments into sequence models
Akyurek and Andreas (2021); Zheng and Lapata (2021). Other work employs
heuristics, grammars, and generative models to synthesize examples for data
augmentation Jia and Liang (2016); Akyürek et al. (2021); Andreas (2020); Wang
et al. (2021); Qiu et al. (2022) or augments standard training objectives with
new supervision signals like attention supervision or meta-learning Oren et
al. (2020); Conklin et al. (2021); Yin et al. (2021). Our work builds on
Dangle Zheng and Lapata (2022), a disentangled sequence-to-sequence model,
which tries to tackle compositional generalization with architectural
innovations. While Dangle is conceptually general, our proposal is tailored to
the Transformer and features two key modifications to encourage more
disentangled representations and better computational efficiency.

##  8 Conclusions

In this paper we focused on two issues related to compositional
generalization. Firstly, we improve upon Dangle, an existing sequence-to-
sequence architecture which generalizes to unseen compositions by learning
specialized encodings for each decoding step. We show that re-encoding keys
periodically, at some interval, improves both efficiency and accuracy.
Secondly, we propose a methodology for identifying compositional patterns in
real-world data and create a new dataset which better represents practical
generalization requirements. Experimental results show that our modifications
improve generalization across tasks, metrics, and datasets and our new
benchmark provides a challenging testbed for evaluating new modeling efforts.

## Limitations

On machine translation, the optimal generalization performance requires using
small interval values. However, R-dangle with small intervals still runs much
slower than an equivalent Transformer model. In this paper, we only explore a
simple periodic re-encoding strategy. However, more complex and flexible ways
of re-encoding could be used to further narrow the gap. For instance, we could
adopt a dynamic strategy which _learns_ when re-encoding is necessary.

## References

  * Akyürek et al. (2021) Ekin Akyürek, Afra Feyza Akyurek, and Jacob Andreas. 2021.  Learning to recombine and resample data for compositional generalization.  In _Proceedings of the 9th International Conference on Learning Representations_ , Online.
  * Akyurek and Andreas (2021) Ekin Akyurek and Jacob Andreas. 2021.  Lexicon learning for few shot sequence modeling.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4934–4946, Online. Association for Computational Linguistics.
  * Andreas (2020) Jacob Andreas. 2020.  Good-enough compositional data augmentation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7556–7566, Online. Association for Computational Linguistics.
  * Andreas et al. (2020) Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christopher H. Lin, Ilya Lintsbakh, Andy McGovern, Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, Andrei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020.  Task-Oriented Dialogue as Dataflow Synthesis.  _Transactions of the Association for Computational Linguistics_ , 8:556–571.
  * Chomsky (2014) Noam Chomsky. 2014.  _Aspects of the Theory of Syntax_ , volume 11.  MIT press.
  * Conklin et al. (2021) Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. 2021.  Meta-learning to compositionally generalize.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3322–3335, Online. Association for Computational Linguistics.
  * Dankers et al. (2022) Verna Dankers, Elia Bruni, and Dieuwke Hupkes. 2022.  The paradox of the compositionality of natural language: A neural machine translation case study.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4154–4175, Dublin, Ireland. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dong and Lapata (2018) Li Dong and Mirella Lapata. 2018.  Coarse-to-fine decoding for neural semantic parsing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 731–742, Melbourne, Australia. Association for Computational Linguistics.
  * Finegan-Dollak et al. (2018) Catherine Finegan-Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. 2018.  Improving text-to-SQL evaluation methodology.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 351–360, Melbourne, Australia. Association for Computational Linguistics.
  * Herzig and Berant (2021) Jonathan Herzig and Jonathan Berant. 2021.  Span-based semantic parsing for compositional generalization.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 908–921, Online. Association for Computational Linguistics.
  * Huang et al. (2020) Zhiheng Huang, Davis Liang, Peng Xu, and Bing Xiang. 2020.  Improve transformer models with better relative position embeddings.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3327–3335, Online. Association for Computational Linguistics.
  * Jia and Liang (2016) Robin Jia and Percy Liang. 2016.  Data recombination for neural semantic parsing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 12–22, Berlin, Germany. Association for Computational Linguistics.
  * Keysers et al. (2020) Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020.  Measuring compositional generalization: A comprehensive method on realistic data.  In _Proceedings of the 8th International Conference on Learning Representations_ , Addis Ababa, Ethiopia.
  * Kim and Linzen (2020) Najoung Kim and Tal Linzen. 2020.  COGS: A compositional generalization challenge based on semantic interpretation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9087–9105, Online. Association for Computational Linguistics.
  * Lake and Baroni (2018a) Brenden M. Lake and Marco Baroni. 2018a.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2879–2888. PMLR.
  * Lake and Baroni (2018b) Brenden M. Lake and Marco Baroni. 2018b.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2879–2888, Stockholm, Sweden. PMLR.
  * Lakshminarayanan et al. (2017) Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. 2017.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Li et al. (2021) Yafu Li, Yongjing Yin, Yulong Chen, and Yue Zhang. 2021.  On compositional generalization of neural machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4767–4780, Online. Association for Computational Linguistics.
  * Malinin (2019) Andrey Malinin. 2019.  _Uncertainty Estimation in Deep Learning with Application to Spoken Language Assessment_.  Ph.D. thesis, University of Cambridge.
  * Malinin and Gales (2021) Andrey Malinin and Mark Gales. 2021.  Uncertainty estimation in autoregressive structured prediction.  In _Proceedings of the 9th International Conference on Learning Representations_ , Online.
  * Montague (1970) Richard Montague. 1970.  Universal grammar.  _Theoria_ , 36(3):373–398.
  * Mostafazadeh et al. (2016) Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016.  A corpus and cloze evaluation for deeper understanding of commonsense stories.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 839–849, San Diego, California. Association for Computational Linguistics.
  * Mostafazadeh et al. (2017) Nasrin Mostafazadeh, Michael Roth, Annie Louis, Nathanael Chambers, and James Allen. 2017.  LSDSem 2017 shared task: The story cloze test.  In _Proceedings of the 2nd Workshop on Linking Models of Lexical, Sentential and Discourse-level Semantics_ , pages 46–51, Valencia, Spain. Association for Computational Linguistics.
  * Oren et al. (2020) Inbar Oren, Jonathan Herzig, Nitish Gupta, Matt Gardner, and Jonathan Berant. 2020\.  Improving compositional generalization in semantic parsing.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2482–2495, Online. Association for Computational Linguistics.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2227–2237, New Orleans, Louisiana. Association for Computational Linguistics.
  * Qiu et al. (2022) Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022.  Improving compositional generalization with latent structure and data augmentation.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4341–4362, Seattle, United States. Association for Computational Linguistics.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018.  Self-attention with relative position representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 464–468, New Orleans, Louisiana. Association for Computational Linguistics.
  * Shin et al. (2021) Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021.  Constrained language models yield few-shot semantic parsers.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 7699–7715, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Wang et al. (2021) Bailin Wang, Wenpeng Yin, Xi Victoria Lin, and Caiming Xiong. 2021.  Learning to synthesize data for semantic parsing.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2760–2766, Online. Association for Computational Linguistics.
  * Yin et al. (2021) Pengcheng Yin, Hao Fang, Graham Neubig, Adam Pauls, Emmanouil Antonios Platanios, Yu Su, Sam Thomson, and Jacob Andreas. 2021.  Compositional generalization for neural semantic parsing via span-level supervised attention.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2810–2823, Online. Association for Computational Linguistics.
  * Zheng and Lapata (2021) Hao Zheng and Mirella Lapata. 2021.  Compositional generalization via semantic tagging.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 1022–1032, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Zheng and Lapata (2022) Hao Zheng and Mirella Lapata. 2022.  Disentangled sequence to sequence learning for compositional generalization.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4256–4268, Dublin, Ireland. Association for Computational Linguistics.

Train | Test
---|---
• and i can ’t believe you ’re here and that i ’m meeting you here at ted . ( PRP RB IN NN . ) • you see , this is what india is today . the ground reality is based on ( DT NN NN VBZ VBN IN ) a cyclical world view . |  the account data is provided to you directly via e-mail .
• a couple of hours ( DT NN IN NNS ) later , the sun will shine on the next magnifying glass . • but this could also be used for good . ( MD RB VB VBN IN NN . ) |  both setting of tasks must successfully be mastered under supervision .
• the national science foundation , other countries ( JJ NN NN , JJ NN ) are very interested in doing this • no , they are full of misery . ( VBP JJ IN NN .) |  its warm water temperature , small depth are convenient for bathing .
|
Table 6: Novel syntactic compositions in ReaCT test set (syntactic atoms of
same type are color coded). POS-tag sequences for these atoms are shown in
parentheses (PRP:pronoun, RB:adverb, IN: preposition, NN/S:noun
singular/plural, DT: determiner, JJ: adjective, MD:modal, VBZ/P: non-/3rd
person singular present, VBN: verb past participle.)

##  Appendix A Examples from ReaCT Dataset

Table 6 showcases examples from the ReaCT test set. These are novel syntactic
patterns approximated by POS $n$-grams. As mentioned in Section 4, ReaCT is
created by detecting compositional patterns in relation to an existing
training set from a diverse pool of candidates.

##  Appendix B Dataset Details

We evaluated our model on two machine translation datasets, and one semantic
parsing benchmark which we selected to maximally reflect natural language
variations and real-world generalization challenges. We describe these in
detail below.

#### ReaCT

is the real-world machine translation benchmark developed in this paper for
compositional generalization. The IWSLT 2014 De$\to$En dataset consists of
approximately 170K sequence pairs. We used the fairseq script prepare-
iwslt14.sh to randomly sample approximately 4% of this dataset as validation
set and kept the rest as training set. Following standard practice, we created
an in-domain test set, the concatenation of files dev2010, dev2012, tst2010,
tst2011, and tst2012. We created an out-of-distribution test sets from the
WMT’14 De$\to$En training corpus following the uncertainty selection method
based on sequences.

#### CoGnition

is another machine translation benchmark targeting compositional
generalization Li et al. (2021). It also contains a synthetic test set to
quantify and analyze compositional generalization of neural MT models. This
test set was constructed by embedding synthesized novel compounds into
training sentence templates. Each compound was combined with 5 different
sentence templates, so that every compound can be evaluated under 5 different
contexts. A major difference between ReaCT and CoGnition is the fact that test
sentences for the latter are not naturally occurring. Despite being somewhat
artificial, CoGnition overall constitutes a realistic benchmark which can help
distinguish subtle model differences compared to purely synthetic benchmarks.
For example, Zheng and Lapata (2022) showed that their encoder-only Dangle
variant performed badly on this dataset in spite of impressive performance on
synthetic semantic parsing benchmarks Kim and Linzen (2020); Keysers et al.
(2020).

#### SMCalFlow-CS

Andreas et al. (2020) is a large-scale semantic parsing dataset for task-
oriented dialogue, featuring real-world human-generated utterances about
calendar management. Yin et al. (2021) proposed a compositional skills split
of SMCalFlow (SMCalFlow-CS) that contains single-turn sentences from one of
two domains related to creating calendar events (e.g., Set up a meeting with
Adam) or querying an org chart (e.g., Who are in Adam’s team?), paired with
LISP programs. The training set $\mathbb{S}$ consists of samples from single
domains while the test set $\mathbb{C}$ contains compositions thereof (e.g.,
create a meeting with Adam and his team). Since zero-shot compositional
generalization is highly non-trivial due to novel language patterns and
program structures, we follow previous work Yin et al. (2021); Qiu et al.
(2022) and consider a few-shot learning scenario, where a small number of
cross-domain examples are included in the training set. We report experiments
with 6, 16, and 32 examples.

##  Appendix C Implementation Details

#### Machine Translation Models

We implemented all translation models with fairseq Ott et al. (2019).
Following previous work Li et al. (2021); Zheng and Lapata (2022), we compared
with the baseline machine translation models Dangle and Transformer using the
popular fairseq configuration transformer_iwslt_de_en. We also implemented a
bigger variant of these models using a new configuration, which empirically
obtained better performance. We used 12 encoder layers and 12 decoder layers.
We set the dropout to 0.3 for attention weights and 0.4 after activations in
the feed-forward network. We also used pre-normalization (i.e., we added layer
normalization before each block) to ease optimization. Following Zheng and
Lapata (2022), we used relative position embeddings Shaw et al. (2018); Huang
et al. (2020) which have demonstrated better generalization performance.

Hyperparameters for R-Dangle were tuned on the respective validation sets of
CoGnition and ReaCT. Both R-Dangleshr and R-Danglesep used a 12-layer decoder.
For R-Dangleshr, we tuned the number of layers of the two adaptive components
$k_{1}$ and $k_{2}$, and set $k_{1}$ and $k_{2}$ to 2 and 10, respectively.
For R-Danglesep, we shared some layers of parameters between the value encoder
and the adaptive key decoder and experimented with different sharing
strategies. Finally, we adopted a 10-layer value encoder and a 10-layer key
encoder ($k_{1}=2$ and $k_{2}=8$). The top 8 layers in the two encoders were
shared. This configuration produced 12 differently parametrized transformer
encoder layers, thus maintaining identical model size to the baseline.

#### Semantic Parsing Models

Qiu et al. (2022) showed the advantage of pre-trained sequence-to-sequence
models on SMCalFlow-CS. We therefore built R-Dangle on top of BART-large Lewis
et al. (2020), which is well supported by fairseq. We used BART’s encoder and
decoder to instantiate the adaptive encoder and decoder in our model. For
compatibility, we only employ the R-Dangleshr architecture. We also set
$k_{1}$ and $k_{2}$ to 2 and 10, respectively.


* Quirola-Vásquez et al. (2023) —. 2023, arXiv e-prints, arXiv:2304.13795, doi: 10.48550/arXiv.2304.13795
  * Raj et al. (2013) Raj, A., Banerjee, D. P. K., & Ashok, N. M. 2013, MNRAS, 433, 2657, doi: 10.1093/mnras/stt946
  * Raj et al. (2015) Raj, A., Ashok, N. M., Rudy, R. J., et al. 2015, AJ, 149, 136, doi: 10.1088/0004-6256/149/4/136
  * Ramsden et al. (2022) Ramsden, P., Lanning, D., Nicholl, M., & McGee, S. L. 2022, MNRAS, 515, 1146, doi: 10.1093/mnras/stac1810
  * Ray et al. (2019) Ray, P. S., Arzoumanian, Z., Ballantyne, D., et al. 2019, arXiv e-prints, arXiv:1903.03035.  https://arxiv.org/abs/1903.03035
  * Rea et al. (2016) Rea, N., Borghese, A., Esposito, P., et al. 2016, ApJ, 828, L13, doi: 10.3847/2041-8205/828/1/L13
  * Rea et al. (2013) Rea, N., Esposito, P., Pons, J. A., et al. 2013, ApJ, 775, L34, doi: 10.1088/2041-8205/775/2/L34
  * Reig (2011) Reig, P. 2011, Ap&SS, 332, 1, doi: 10.1007/s10509-010-0575-8
  * Rivera Sandoval et al. (2018) Rivera Sandoval, L. E., Maccarone, T. J., Corsi, A., et al. 2018, MNRAS, 480, L146, doi: 10.1093/mnrasl/sly145
  * Rivera Sandoval et al. (2019) —. 2019, MNRAS, 484, L7, doi: 10.1093/mnrasl/sly235
  * Rohatgi (2019) Rohatgi, A. 2019, WebPlotDigitizer (4.2), https://automeris.io/WebPlotDigitizer
  * Roming et al. (2009) Roming, P. W. A., Pritchard, T. A., Brown, P. J., et al. 2009, ApJ, 704, L118, doi: 10.1088/0004-637X/704/2/L118
  * Ross & Dwarkadas (2017) Ross, M., & Dwarkadas, V. V. 2017, AJ, 153, 246, doi: 10.3847/1538-3881/aa6d50
  * Rouco Escorial et al. (2022) Rouco Escorial, A., Fong, W.-f., Berger, E., et al. 2022, arXiv e-prints, arXiv:2210.05695.  https://arxiv.org/abs/2210.05695
  * Russell & Immler (2010) Russell, B. R., & Immler, S. 2010, The Astronomer’s Telegram, 2389, 1
  * Russell et al. (2010) Russell, B. R., Immler, S., & Milne, P. 2010, The Astronomer’s Telegram, 2618, 1
  * Russell et al. (2016) Russell, T. D., Miller-Jones, J. C. A., Sivakoff, G. R., et al. 2016, MNRAS, 460, 3720, doi: 10.1093/mnras/stw1238
  * Sazonov et al. (2021) Sazonov, S., Gilfanov, M., Medvedev, P., et al. 2021, MNRAS, 508, 3820, doi: 10.1093/mnras/stab2843
  * Sazonov et al. (2004) Sazonov, S. Y., Lutovinov, A. A., & Sunyaev, R. A. 2004, Nature, 430, 646, doi: 10.1038/nature02748
  * Schaefer (2010) Schaefer, B. E. 2010, ApJS, 187, 275, doi: 10.1088/0067-0049/187/2/275
  * Schaefer (2018) —. 2018, MNRAS, 481, 3033, doi: 10.1093/mnras/sty2388
  * Schlegel (2001) Schlegel, E. M. 2001, ApJ, 556, L25, doi: 10.1086/322269
  * Schlegel & Ryder (2002) Schlegel, E. M., & Ryder, S. 2002, IAU Circ., 7913, 1
  * Schulze et al. (2022) Schulze, S., Ho, A. Y. Q., Perley, D. A., Yan, L., & Fremling, C. 2022, Transient Name Server AstroNote, 207, 1
  * Sidoli et al. (2008) Sidoli, L., Romano, P., Mangano, V., et al. 2008, ApJ, 687, 1230, doi: 10.1086/590077
  * Soderberg et al. (2009) Soderberg, A., Grindlay, J. E., Bloom, J. S., et al. 2009, in astro2010: The Astronomy and Astrophysics Decadal Survey, Vol. 2010, 278.  https://arxiv.org/abs/0902.3674
  * Soderberg et al. (2006) Soderberg, A. M., Chevalier, R. A., Kulkarni, S. R., & Frail, D. A. 2006, ApJ, 651, 1005, doi: 10.1086/507571
  * Soderberg et al. (2008) Soderberg, A. M., Berger, E., Page, K. L., et al. 2008, Nature, 453, 469, doi: 10.1038/nature06997
  * Soderberg et al. (2012) Soderberg, A. M., Margutti, R., Zauderer, B. A., et al. 2012, ApJ, 752, 78, doi: 10.1088/0004-637X/752/2/78
  * Soria et al. (2004) Soria, R., Pian, E., & Mazzali, P. A. 2004, A&A, 413, 107, doi: 10.1051/0004-6361:20031506
  * Staley et al. (2013) Staley, T. D., Titterington, D. J., Fender, R. P., et al. 2013, MNRAS, 428, 3114, doi: 10.1093/mnras/sts259
  * Stone & Metzger (2016) Stone, N. C., & Metzger, B. D. 2016, MNRAS, 455, 859, doi: 10.1093/mnras/stv2281
  * Sturm et al. (2010) Sturm, R., Haberl, F., Aschenbach, B., & Hasinger, G. 2010, A&A, 515, A5, doi: 10.1051/0004-6361/200913317
  * Sugawara et al. (2020) Sugawara, Y., Nakahira, S., Negoro, H., et al. 2020, GRB Coordinates Network, 27661, 1
  * Sugizaki (2010) Sugizaki, M. 2010, in The First Year of MAXI: Monitoring Variable X-ray Sources, 14
  * Svirski & Nakar (2014) Svirski, G., & Nakar, E. 2014, ApJ, 788, L14, doi: 10.1088/2041-8205/788/1/L14
  * Tanaka et al. (2016) Tanaka, M., Tominaga, N., Morokuma, T., et al. 2016, ApJ, 819, 5, doi: 10.3847/0004-637X/819/1/5
  * Tanaka et al. (1994) Tanaka, Y., Inoue, H., & Holt, S. S. 1994, PASJ, 46, L37
  * Tetarenko et al. (2016) Tetarenko, B. E., Sivakoff, G. R., Heinke, C. O., & Gladstone, J. C. 2016, ApJS, 222, 15, doi: 10.3847/0067-0049/222/2/15
  * The CHIME/FRB Collaboration et al. (2020) The CHIME/FRB Collaboration, Andersen, B. Â. C., Band ura, K. Â. M., Bhardwaj, M., et al. 2020, Nature, 587, 54, doi: 10.1038/s41586-020-2863-y
  * The Lynx Team (2019) The Lynx Team. 2019, Lynx X-ray Observatory Concept Study Report, Tech. rep., Lynx Observatory
  * Tozzi et al. (2006) Tozzi, P., Gilli, R., Mainieri, V., et al. 2006, A&A, 451, 457, doi: 10.1051/0004-6361:20042592
  * Trümper (1990) Trümper, J. 1990, International Astronomical Union Colloquium, 115, 291–294, doi: 10.1017/S0252921100012483
  * Tsuboi et al. (2016) Tsuboi, Y., Yamazaki, K., Sugawara, Y., et al. 2016, PASJ, 68, 90, doi: 10.1093/pasj/psw081
  * Tsunemi et al. (2010) Tsunemi, H., Tomida, H., Katayama, H., et al. 2010, Publications of the Astronomical Society of Japan, 62, 1371, doi: 10.1093/pasj/62.6.1371
  * Vasilopoulos et al. (2017a) Vasilopoulos, G., Haberl, F., & Maggi, P. 2017a, MNRAS, 470, 1971, doi: 10.1093/mnras/stx1359
  * Vasilopoulos et al. (2014) Vasilopoulos, G., Haberl, F., Sturm, R., Maggi, P., & Udalski, A. 2014, A&A, 567, A129, doi: 10.1051/0004-6361/201423934
  * Vasilopoulos et al. (2020a) Vasilopoulos, G., Lander, S. K., Koliopanos, F., & Bailyn, C. D. 2020a, MNRAS, 491, 4949, doi: 10.1093/mnras/stz3298
  * Vasilopoulos et al. (2018) Vasilopoulos, G., Maitra, C., Haberl, F., Hatzidimitriou, D., & Petropoulou, M. 2018, MNRAS, 475, 220, doi: 10.1093/mnras/stx3139
  * Vasilopoulos et al. (2017b) Vasilopoulos, G., Zezas, A., Antoniou, V., & Haberl, F. 2017b, MNRAS, 470, 4354, doi: 10.1093/mnras/stx1507
  * Vasilopoulos et al. (2020b) Vasilopoulos, G., Ray, P. S., Gendreau, K. C., et al. 2020b, MNRAS, 494, 5350, doi: 10.1093/mnras/staa991
  * Villar et al. (2017) Villar, V. A., Berger, E., Metzger, B. D., & Guillochon, J. 2017, ApJ, 849, 70, doi: 10.3847/1538-4357/aa8fcb
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261, doi: 10.1038/s41592-019-0686-2
  * Wang et al. (2022) Wang, C. W., Xiong, S. L., Zhang, Y. Q., et al. 2022, The Astronomer’s Telegram, 15682, 1
  * Watson et al. (2004) Watson, D., Hjorth, J., Levan, A., et al. 2004, ApJ, 605, L101, doi: 10.1086/420844
  * Watson et al. (2001) Watson, M. G., Auguères, J. L., Ballet, J., et al. 2001, A&A, 365, L51, doi: 10.1051/0004-6361:20000067
  * Wei et al. (2016) Wei, J., Cordier, B., Antier, S., et al. 2016, arXiv e-prints, arXiv:1610.06892.  https://arxiv.org/abs/1610.06892
  * Weisskopf et al. (2000) Weisskopf, M. C., Tananbaum, H. D., Van Speybroeck, L. P., & O’Dell, S. L. 2000, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 4012, X-Ray Optics, Instruments, and Missions III, ed. J. E. Truemper & B. Aschenbach, 2–16, doi: 10.1117/12.391545
  * Wes McKinney (2010) Wes McKinney. 2010, in Proceedings of the 9th Python in Science Conference, ed. Stéfan van der Walt & Jarrod Millman, 56 – 61, doi: 10.25080/Majora-92bf1922-00a
  * Wheatley et al. (2003) Wheatley, P. J., Mauche, C. W., & Mattei, J. A. 2003, MNRAS, 345, 49, doi: 10.1046/j.1365-8711.2003.06936.x
  * Wilson-Hodge et al. (2018) Wilson-Hodge, C. A., Malacaria, C., Jenke, P. A., et al. 2018, ApJ, 863, 9, doi: 10.3847/1538-4357/aace60
  * Worpel et al. (2020) Worpel, H., Schwope, A. D., Traulsen, I., Mukai, K., & Ok, S. 2020, A&A, 639, A17, doi: 10.1051/0004-6361/202038038
  * Xue et al. (2019) Xue, Y. Q., Zheng, X. C., Li, Y., et al. 2019, Nature, 568, 198, doi: 10.1038/s41586-019-1079-5
  * Yao et al. (2022) Yao, Y., Ho, A. Y. Q., Medvedev, P., et al. 2022, ApJ, 934, 104, doi: 10.3847/1538-4357/ac7a41
  * Yao et al. (2023) Yao, Y., Ravi, V., Gezari, S., et al. 2023, arXiv e-prints, arXiv:2303.06523, doi: 10.48550/arXiv.2303.06523
  * Yuan (2017) Yuan, W. 2017, in 7 years of MAXI: monitoring X-ray Transients, ed. M. Serino, M. Shidatsu, W. Iwakiri, & T. Mihara, 247
  * Zampieri et al. (2005) Zampieri, L., Mucciarelli, P., Pastorello, A., et al. 2005, MNRAS, 364, 1419, doi: 10.1111/j.1365-2966.2005.09671.x
  * Zhang et al. (2019) Zhang, S., Santangelo, A., Feroci, M., et al. 2019, Science China Physics, Mechanics, and Astronomy, 62, 29502, doi: 10.1007/s11433-018-9309-2
  * Zhang et al. (2020) Zhang, S.-N., Li, T., Lu, F., et al. 2020, Science China Physics, Mechanics, and Astronomy, 63, 249502, doi: 10.1007/s11433-019-1432-6


Analysis of Linux-PRNG (Pseudo Random Number Generator)

UGP Report

Author: Ayush Bansal (Student ID: 160177)
Advisor: Dr. Pramod Subramanyan &
Dr. Satyadev Nandakumar

Department of Computer Science and Engineering
Indian Institute of Technology, Kanpur

June 16, 2020

## Abstract

The Linux pseudorandom number generator (PRNG) is a PRNG with entropy inputs
and is widely used in many security-related applications and protocols. This
PRNG is written as an open-source code which is subject to regular changes. It
has been analysed in the works of Gutterman et al. [GPR06], Lacharme et al.
[LRSV12] and [KASN15], while in the meantime, several changes have been
applied to the code, to counter the attacks presented since then. Our work
describes the Linux PRNG of kernel versions 5.3 and upwards. We discuss the
PRNG architecture briefly and in detail about the entropy mixing function.

Our goal is to study the entropy mixing function and analyse it over two
properties, namely, injectivity and length of the longest chain. For this
purpose, we will be using SAT solving and model counting over targetted
formulas involving multiple states of the Linux entropy store.

###### Contents

  1. 1 Introduction
  2. 2 Architecture
    1. 2.1 General Structure
    2. 2.2 Entropy Sources
    3. 2.3 Entropy Estimation
    4. 2.4 Output Generation
  3. 3 Mixing Function
    1. 3.1 The Process
  4. 4 Design and Evaluation
    1. 4.1 Design
    2. 4.2 Evaluation
  5. 5 Conclusion/Future Work

##  1 Introduction

Many security protocols base their security on the impossibility of an
attacker being able to guess the random data, such as session keys for
cryptosystems or nonces for cryptographic protocols. However, the amount of
required random data can differ significantly with the application. Therefore,
random data generation should take into account the fact that the user can
request either high-quality random data or a great amount of pseudorandom
data. Even a recent article [Edg19] demanding a fix in Linux’s getrandom()
function to provide an alternative to get a great amount of pseudorandom data
without getting blocked for entropy.

A pseudorandom number generator with entropy inputs produces bits non-
deterministically as the internal state is frequently refreshed with
unpredictable data from one or several external entropy sources. It is
typically made of (1) several physical sources of randomness called entropy
sources, (2) a harvesting mechanism to accumulate the entropy from these
sources into the internal state, and (3) a post-processing procedure. The
latter frequently uses a cryptographically secure PRNG (CSPRNG) to generate
outputs and to update the internal state.

Figure 1: PRNG Model

In Unix-like operating systems, a pseudo-random number generator with input
was implemented for the first time for Linux $1.3.30$ in $1994$. The entropy
source comes from device drivers and other sources such as latencies between
user-triggered events (keystroke, disk I/O, mouse clicks, …). It is gathered
into an internal state called the entropy pool. The internal state keeps an
estimate of the number of bits of entropy in the internal state and
(pseudo-)random bits are created from the special files /dev/random and
/dev/urandom. Barak and Halevi [BH05] discussed the generator /dev/random
briefly, but its conformity with their robustness security definition is not
formally analysed.

The first security analysis of these generators was given in $2006$ by
Gutterman, Pinkas and Reinman [GPR06]. It was completed in $2012$ by Lacharme,
Röck, Strubel and Videau [LRSV12]. Gutterman et al. [GPR06] presented an
attack based on kernel version $2.6.10$ for which a fix was published in the
following versions. Lacharme et al. [LRSV12] gives a detailed description of
the operations of the generators and provides a result on the entropy
preservation property of the mixing function used to refresh the internal
state.

In the next few sections, we will discuss the Architecture of the Linux PRNG
briefly and in detail the mixing function applied over the entropy pool to
refresh the internal state of the random number generator. The works of
Lacharme et al. [LRSV12] suggested that the mixing function has the property
of entropy preservation, and analysing the same property is one of our goals.

The motivations behind this analysis are:

  * •

Gain insights into the working of the Linux PRNG

  * •

Gain a deeper undestanding of the entropy estimation and accumulation
processes.

  * •

Verify the entropy preservation properties as claimed in [LRSV12].

Previous works on the analysis of Linux PRNG claim that the mixing function
which is used to refresh the internal state preserves the entropy received
from various entropy sources, our primary goal with this analysis is to verify
this using the techniques of SAT solving and model counting.

Our goals regarding this analysis are:

  * •

Comment the property of injectivity of the entropy mixing function.

  * •

Estimate the length of the longest chain, i.e. the size of input bytes which
when supplied with an initial state of entropy pool to the mixing function
leaves the entropy pool unchanged.

##  2 Architecture

The Linux PRNG has been a part of the Linux kernel since $1994$. Ts’o wrote
the original version, and Mackall [MT09] later modified it. The generator,
apart from the entropy input hooks inserted into drivers, represents about
$2500$ lines of C code in a single source file, drivers/char/random.c.

###  2.1 General Structure

Unlike other PRNGs, the internal state of the Linux PRNG is divided into three
entropy pools, the input pool, the blocking pool and the non-blocking pool.
The blocking and the non-blocking pools together form the output pools. The
size of the input pool is $128$ $32$-bit words ($4096$ bits) and the size of
each output pool is $32$ $32$-bit words ($1024$ bits). The generator is
designed to perform the collection of entropy inputs as efficiently as
possible; therefore, it uses a linear mixing function instead of a more usual
hash function. The general structure of a Linux PRNG is shown in Figure 2.

Figure 2: PRNG Model [LRSV12]

The PRNG relies on external entropy sources. The various system events like
keyboard and mouse movements, disk events, and hardware interrupt inside the
kernel act as the entropy source for Linux PRNG and inputs are collected from
them. The collected inputs are accumulated inside the input pool. An entropy
counter is associated with each pool, decremented when entropy is extracted
from the pools and incremented when entropy is added to the pools. Entropy
transfers take place from the input pool to the output pools only when some
entropy needs to be extracted from Linux PRNG. Hence, the entropy counters of
the output pools remain close to zero except for the transition state. It
makes the entropy counter of the input pool as the most significant one as the
available entropy in Linux PRNG is reflected by the entropy counter value of
the input pool [LRSV12].

Linux PRNG provides two character interfaces /dev/random and /dev/urandom to
read the random output. The /dev/random reads from the blocking pool and
/dev/urandom read from the non-blocking pool. /dev/random provides
cryptographically stronger bytes, blocks if sufficient entropy is not present
in the pools and resumes when enough new entropy samples have been mixed into
the input pool. Thus, it limits the number of generated bits according to the
estimation of the entropy available in the PRNG. /dev/urandom always provides
the desired amount of bytes and does not block; it is meant for the fast
generation of large amounts of random data. In addition to these two character
interfaces, Linux PRNG also provides get_random_bytes() which is a kernel
interface. It allows the other kernel components to read from the non-blocking
pool.

Entropy accumulation in Linux PRNG is a process of three major steps, namely,
collecting entropy from various entropy sources, mixing the collected entropy
into the input pool using a mixing function and estimating the total entropy
associated with each input which is mixed into the input pool. Broadly, the
structure of Linux PRNG consists of four major components which are described
in the following subsections. Section 2.2 describes the various entropy
sources briefly used by the Linux PRNG for accumulating entropy. Section 3
describes the mixing function used for mixing the inputs collected from
different entropy sources into the input pool. The same mixing function is
also used when entropy is transferred from the input pool to the output pools
when the entropy content of the output pools is less than that of the
requested entropy bytes from Linux PRNG. Section 2.3 describes briefly the
entropy estimation process used by Linux PRNG to estimate the entropy
associated with each input which is mixed into the input pool. Section 2.4
briefly describes the output generation process in Linux PRNG, which is used
whenever entropy is extracted from the output pools or a transfer of entropy
occurs between the input pool and the output pools.

###  2.2 Entropy Sources

Entropy inputs are injected into the generator for initialization, and through
the updating mechanism, provides the backbone of the security of the PRNG. The
Linux PRNG is intended to be used independently of any specific hardware.
Therefore, it cannot rely on nondeterministic physical phenomena generally
used in the random generation, which require additional hardware.

The Linux PRNG processes events from different entropy sources, namely, user
inputs (keyboard and mouse movements), disk events, and hardware interrupts.
Each input generated from these entropy sources are mixed into the input pool
and consists of three values, as shown in Figure 3, also known as sample.

Figure 3: An Entropy Input

In the above sample,

  * •

num: It is a $32$-bit value representing the specific event type.

  * •

jiffies: It represents the jiffy count value of the system at which the events
mixed into the input pool of the Linux PRNG. ‘Jiffy’ is the time between two
ticks of the system timer interrupt, and the jiffy count value of a system
represents the total number of ticks of system timer interrupt from the boot
time.

  * •

cycles: It is a $32$-bit value representing the CPU cycle count value.

The functions add_input_randomness, add_disk_randomness and
add_interrupt_randomness of /drivers/char/random.c file of Linux kernel manage
the collection of inputs from different entropy sources of the Linux PRNG. All
these inputs are accumulated into the input pool of Linux PRNG through a
mixing function.

###  2.3 Entropy Estimation

The entropy estimation is one of the crucial steps for generation of data via
/dev/random. An accurate estimation of whether the corresponding pool contains
enough entropy to generate unpredictable output data is essential.

The entropy counter associated with each pool keeps an estimate of the entropy
content of that pool. Entropy estimation of a Linux PRNG is based on the
timing of the events generated from different entropy sources, which mixed
into the input pool. Although, both cycles and jiffies represents the timing
of the event, jiffies being the one having more coarser granularity is used
for estimating the entropy of Linux PRNG. The difference of jiffies associated
with each input event is used for entropy estimation.

###  2.4 Output Generation

There are three output interfaces provided by the Linux PRNG for extracting
entropy from the blocking and non-blocking pools. /dev/random and /dev/urandom
are the character interfaces for the users and get_random_bytes() is the
kernel interface for extracting entropy. /dev/random extracts entropy from
blocking pool and may block if enough entropy is not present, providing very
high-quality random bits. /dev/urandom can provide as many bits as requested,
extracting from the non-blocking pool. The function get_random_bytes is
available only within the kernel and extracts entropy from the non-blocking
pool.

The output generation function can be divided into two phases, namely,
feedback phase and extraction phase. It uses SHA-1 hash function in two-steps.

  1. 1.

All bytes of the pool are hashed to produce $5$-word hash and $20$ bytes are
mixed back into the pool using mixing function. Mixing back of generated hash
in the pool prevents the backtracing attacks. This step forms the feedback
phase of output generation function.

  2. 2.

$16$ words from the mixed pool content are again hashed along with the 5
output words from the previous step. The 20-byte output from this second hash
is folded in half to get a $10$ byte output.

The entropy counter of the output pool is finally decremented by the number of
bytes generated from the Linux PRNG.

##  3 Mixing Function

The structure of the mixing function of Linux PRNG is shown in Figure 4. This
function mixes one byte of the input at a time by first extending that one
byte to a $32$-bit word, followed by a rotation of the extended $32$-bit word
by a changing factor, and finally mixing it in the pool by using a linear
shift register. It is designed so that no entropy gets lost while diffusing
into the pools.

Figure 4: The mixing function [LRSV12]

The Mixing function is defined by the function mix_pool_bytes in
/drivers/char/random.c file of Linux kernel. The function mix_pool_bytes takes
three arguments.

  1. 1.

struct entropy_store *r: Entropy store is a structure which contains various
entities such as poolinfo containing the definition for both input and output
pools, pool containing the name of the pool being used for mixing the entropy
input, entropy count representing the entropy count of the respective pool.
The input pool is declared as an array containing $128$ words and the output
pools which includes both blocking and non-blocking pools are declared arrays
of $32$ words each. The variables add_ptr and input_rotate are defined as data
of type unsigned int (C data type).

  2. 2.

const void *in: Pointer to the input collected from various entropy sources
which is mixed into the entropy pools. When inputs are mixed into the input
pool from the function add_timer_randomness, in becomes a pointer to the
structure sample as shown in Figure 3.

  3. 3.

int nbytes: This represents the total number of bytes to be mixed into the
pool. The total number of bytes added to the input pool is either $12$ bytes
or $16$ bytes depending on the architecture of the system used.

The mixing function updates the input entropy store after mixing the input
bytes received from various entropy sources.

Apart from these function arguments, there are also different variables
declared inside the mixing function. unsigned long integers tap1, tap2, tap3,
tap4 and tap5 are declared inside the function, their values are
$104,76,51,25$ and $1$ respectively for the input pool and $26,19,14,7$ and
$1$ respectively for the output pools. A variable wordmask is also defined
inside the function mix_pool_bytes whose value is $127$ for the input pool and
$31$ for the output pools.

###  3.1 The Process

The input bytes also known as samples are mixed into the input pool using
mixing function, one byte at a time. For a $n$ byte sample, the whole process
of mixing is repeated $n$ times. The one-byte value of the sample is first
type casted to __u32 (expanded to $32$ bits) form of C language and is then
rotated with a function called rol32, defined in linux/bitops.h of Linux
kernel. The rol32 function takes two arguments, a word to be rotated ($32$
bit) and a factor shift by which that word is rotated.

$\text{w}=(\text{word}\gg\text{shift})\ |\ \text{word}\ll(32-\text{shift})$

The initial value of shift is $0$. The variable i declared inside the mixing
function is equal to the output of a function ACCESS_ONCE(x), where x is equal
to a variable add_ptr defined in the structure entropy store, this function is
defined as a macro in linux/compiler.h of Linux kernel. In each iteration, a
byte of the entropy input is mixed into the entropy pool via following steps:

  1. 1.

The byte representing one byte value of the input sample is expanded to $32$
bits, rotated using the rol32 function and the variable w is assigned its
value.

  2. 2.

The variable i, which was assigned the value add_ptr from the entropy store is
updated with (i - 1) & wordmask.

  3. 3.

The word w is then $XOR$ed at each of the tap locations defined for the
corresponding pool in the following way:

$\displaystyle w$ $\displaystyle=w\oplus r\rightarrow\text{pool}[i];$
$\displaystyle w$ $\displaystyle=w\oplus
r\rightarrow\text{pool}[(i+\text{tap1})\ \&\ \text{wordmask}];$ $\displaystyle
w$ $\displaystyle=w\oplus r\rightarrow\text{pool}[(i+\text{tap2})\ \&\
\text{wordmask}];$ $\displaystyle w$ $\displaystyle=w\oplus
r\rightarrow\text{pool}[(i+\text{tap3})\ \&\ \text{wordmask}];$ $\displaystyle
w$ $\displaystyle=w\oplus r\rightarrow\text{pool}[(i+\text{tap4})\ \&\
\text{wordmask}];$ $\displaystyle w$ $\displaystyle=w\oplus
r\rightarrow\text{pool}[(i+\text{tap5})\ \&\ \text{wordmask}];$

The word w is then finally mixed back into the entropy pool at the $i^{t}h$
location using the following:

$r\rightarrow\text{pool}[i]=(w\gg 3)\oplus\text{twist\\_table}[w\ \&\ 7];$

Twist table is defined in drivers/char/random.c as an array containing $8$
$32$-bit hexa-decimal values. These values are the monomials in the field
$(F_{2})/(Q)$ [Koo02]. $Q(x)$ is defined in [Koo02] as equal to
$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$,
is a CRC32 polynomial used for Ethernet protocol.

  4. 4.

Finally, the input_rotate value, i.e. shift is increased by a value of $7$ if
the value of i is non-zero, else it is incremented by 14.

When all the bytes of an entropy input are mixed into the entropy pool, the
value of input_rotate and i is then again accessed using the function
ACCESS_ONCE and is assigned to the respective variables.

##  4 Design and Evaluation

Our main goal, as discussed in Section 1 to analyse the Linux’s mixing
function and comment on the properties of injectivity and length of the
longest chain. With the help of this analysis, we can verify whether the
entropy once supplied to the mixing function is preserved or not.

For our analysis, we will use the techniques of SAT solving and model counting
in order to ensure that the function preserves entropy. We have imitated the
parts of code in /drivers/char/random.c concerning the mixing function and the
entropy store in scala as part of our tool Entropy-Mixer. In the next
subsection, we are going to discuss in detail the implementation design of
Entropy-Mixer.

###  4.1 Design

Our tool Entropy-Mixer, takes an initial entropy store and an array of entropy
bytes as input and applies the mixing function on the store, mixing one byte
at a time and updates the initial entropy store to the final state of the
entropy store after the mixing is complete. During this entire process, the
variables involved are bit-vector expressions. Hence, the final store
generated is also a bit-vector expression represented as an expression of
input entropy store and entropy bytes combined with logical bit operations.

The model structure of our tool is as follows:

  1. 1.

Expr Class: Denotes a boolean expression containing boolean variables and
boolean operators (each defined as a case class), an expression can be one of
the following.

     * •

A constant boolean value, i.e. true or false.

     * •

A boolean variable (value unknown), denoted by a name (string).

     * •

Complement of an expression, i.e. Not(expr).

     * •

Boolean operator applied over a list of expressions, such as and, or and
others.

  2. 2.

BitVector Class: Denotes a bit-vector of arbitrary but constant length defined
as an array of boolean expressions (using the Expr class).

  3. 3.

Entropy Store: Denotes the entropy pool as discussed in Section 3, the entropy
pool can be of size $128$ $32$-bit words in which case it is an input pool, or
it can be of size $32$ $32$-bit words becoming one of the output pools. Each
word is denoted as an instance of the BitVector class.

The mixing function involves a good amount of bit operations to be performed
on the data, in order to incorporate those in our model, we have designed
BitVectorOperations object to address our needs of bit operations. The
operations defined are as follows:

  1. 1.

bitOr, bitAnd, bitXor and bitXnor: These operations take $2$ bit-vectors of
same size (e.g. $32$ bit) and generate a bit-vector after applying bitwise or,
and, xor and xnor respectively on the $2$ bit-vectors.

  2. 2.

bitLeftShift and bitRightShift: These operations take a bit-vector and an
integer value, applies the bitwise left shift and right shift respectively to
generate the output bit-vector.

  3. 3.

expandBitVector: It takes as input a bit-vector and an integer value (greater
than size of bit-vector), expands the bit-vector to the provided size.

  4. 4.

threeMux: It takes an array of bit-vectors and a bitvector select value, and
it imitates the functionality of a $3$ pin multiplexer.

Using the above classes and operations, we imitate the code of mix_pool_bytes
function of Linux kernel in order to gain the final entropy store in the form
of bit-vector expressions to be used further by SAT solvers.

###  4.2 Evaluation

We have discussed in detail the design of our tool and model setup, in this
subsection, we will look at the functions we tried to analyse using SAT
solvers to judge the property of injectivity for the mixing function.

We used Cadical [Bie19] for SAT Solving and Maxcount [FRS17] solver for
Maximum Model Counting during our analysis.

The formulas that we analysed are as follows:

  1. 1.

Formula-1:

$(i_{1}\neq i_{2})\ \&\ (f(x,i_{1})=f(x,i_{2}))$ (1)

This formula checks the condition of $2$ different sets of entropy input bytes
(with the same size) being used as input for the mixing function (denoted by
$f$ here) and still producing the same state of entropy store.

  2. 2.

Formula-2:

$((x_{1}\neq x_{2})\ |\ (i_{1}\neq i_{2}))\ \&\
(f(x_{1},i_{1})=f(x_{2},i_{2}))$ (2)

This formula checks the condition of the final state of entropy stores being
same after the mixing even though the initial state of entropy stores was
different or the entropy bytes used for mixing were distinct (of same size but
different value).

For testing above formulas, we used the output pool as the entropy store, the
size of the output pool is $32$ $32$-bit words, the input entropy bytes will
be an array of size $8$ bit-vectors.

After running SAT Solvers on the above formulas:

  1. 1.

Formula-1: UNSAT upto size $88$ of input entropy bytes, i.e. variables $i_{1}$
and $i_{2}$.

  2. 2.

Formula-2: SAT upto size $288$ of input entropy bytes.

##  5 Conclusion/Future Work

We presented our design for Entropy-Mixerwhich takes as input an initial state
of the entropy store and an array of entropy bytes, applies the mixing
function over the entropy store, one byte at a time and produces the final
state of the entropy store. Entropy-Mixerwas used in analysing the property of
injectivity for the mixing function.

We targetted to comment on the property on injectivity of the mixing function
as one our main goals, but we have not achieved that yet, we still have to use
the technique of model counting in order to conclude the same. However, the
idea of Formula-2 (eq. 2) being satisfiable is an interesting result and this
is where we need to dig deeper.

We were not able to make too much progress on our second goal which was to
find the longest chain of inputs to retrieve back the original state, and we
have to figure out a method to test this out in future.

## References

  * [BH05] Boaz Barak and Shai Halevi.  An architecture for robust pseudorandom generation and applications to /dev/random.  01 2005.
  * [Bie19] Armin Biere.  Cadical at the sat race 2019.  2019\.
  * [Edg19] Jake Edge.  Fixing getrandom().  https://lwn.net/Articles/800509/, 09 2019.
  * [FRS17] Daniel J. Fremont, Markus N. Rabe, and Sanjit A. Seshia.  Maximum model counting.  In AAAI, 2017.
  * [GPR06] Zvi Gutterman, Benny Pinkas, and Tzachy Reinman.  Analysis of the linux random number generator.  IACR Cryptology ePrint Archive, 2006:86, 01 2006.
  * [KASN15] Rashmi Kumari, Mohsen Alimomeni, and Reihaneh Safavi-Naini.  Performance analysis of linux rng in virtualized environments.  page 29–39, 2015.
  * [Koo02] Philip Koopman.  32-bit cyclic redundancy codes for internet applications.  Proceedings International Conference on Dependable Systems and Networks, pages 459–468, 2002.
  * [LRSV12] Patrick Lacharme, Andrea Röck, Vincent Strubel, and Marion Videau.  The linux pseudorandom number generator revisited.  01 2012.
  * [MT09] Matt Mackall and Theodore Ts’o.  random.c - a strong random number generator.  /driver/char/random.c in Linux Kernel 2.6.30.7, https://www.kernel.org, 09 2009.