# Fire retainment on Cayley graphs

Gideon Amir  Bar-Ilan University, Ramat Gan 52900, Israel.
<EMAIL_ADDRESS>,  Rangel Baldasso  Leiden University, 2300 RA Leiden, The
Netherlands<EMAIL_ADDRESS>,  Maria Gerasimova  Westfälische
Wilhelms-Universität Münster, 48149 Münster, Germany<EMAIL_ADDRESS>and  Gady Kozma  The Weizmann Institute of Science, Rehovot 76100, Israel.
<EMAIL_ADDRESS>
###### Abstract.

We study the fire-retaining problem on groups, a quasi-isometry
invariant11footnotemark: 1 introduced by Martínez-Pedroza and Prytuła [8],
related to the firefighter problem. We prove that any Cayley graph with
degree-$d$ polynomial growth does not satisfy $\\{f(n)\\}$-retainment, for any
$f(n)=o(n^{d-2})$, matching the upper bound given for the firefighter problem
for these graphs. In the exponential growth regime we prove general lower
bounds for direct products and wreath products. These bounds are tight, and
show that for exponential-growth groups a wide variety of behaviors is
possible. In particular, we construct, for any $d\geq 1$, groups that satisfy
$\\{n^{d}\\}$-retainment but not $o(n^{d})$-retainment, as well as groups that
do not satisfy sub-exponential retainment.

_Keywords and phrases._ Fire containment; Cayley graphs.

MSC 2010: 05C63, 05C57, 20F65, 05C10.

##  1\. Introduction

22footnotetext: See Section 2 for some caveats.

Let $G$ be an infinite connected graph and $\\{f(n)\\}$ be a sequence of
positive integers. Assume that a fire breaks out in a finite subset $F_{0}$ of
the vertices of $G$. At each unit of time $n$, at most $f(n)$ vertices that
are not on fire are declared protected and the fire spreads to all non-
protected vertices that neighbor at least one vertex already on fire. Denote
by $U$ the collection of vertices that are never on fire. The graph $G$ is
said to have the $\\{f(n)\\}$-retaining property if, for every choice of
initially burnt vertices $F_{0}$, there exists a strategy for protecting at
most $\\{f(n)\\}$ vertices at step $n$ such that the set $U$ has growth
function equivalent to the growth function of $G$.

We use the standard equivalence relation between functions in which $f\preceq
g$ if there exists a constant $C>0$ s.t. $f(n)\leq Cg(Cn)+C$ for all $n$ and
$f\simeq g$ if $f\preceq g$ and $g\preceq f$. It is well-known that up to this
equivalence relation, the growth rate of a group is a quasi-isometry
invariant.

The notion of fire retaining is in fact a quasi-isometry geometric invariant
(for monotone non-decreasing functions $f$) that was introduced by Martínez-
Pedroza and Prytuła [8] as a variant of the firefighter problem first proposed
by Hartnell [4]. In the firefighter problem, one looks for strategies such
that the set $G\setminus U$ of vertices that are eventually on fire is finite.
Whenever this is possible for every finite initial set $F_{0}$, one says that
$G$ has the $\\{f(n)\\}$-containment property. Of course, if $G$ has the
$\\{f(n)\\}$-containment property, it also has the $\\{f(n)\\}$-retainment
property.

The graph $G$ is said to satisfy polynomial containment of degree $d$
(respectively, polynomial retainment of degree $d$) if it has the
$\\{f(n)\\}$-containment property (respectively, $\\{f(n)\\}$-retainment
property) for $f(n)=Kn^{d}$, for some $K\geq 0$. Dyer, Martínez-Pedroza, and
Thorne [3] established that having polynomial containment of degree $d$ is a
quasi-isometry invariant, while the analogous statement for polynomial
retainment of degree $d$ was proved in [8].

The following result was established in [3].

######  Theorem 1.1.

([3, Theorem 2.3]) Let $G$ be a connected graph with polynomial growth of
degree at most $d$. Then $G$ satisfies polynomial containment of degree $d-2$.

Develin and Hartke [2] conjectured the converse should hold for the
$d$-dimensional integer lattice, and this was recently verified to hold for
Cayley graphs of groups with polynomial growth by Amir, Baldasso, and Kozma
[1].

######  Theorem 1.2.

([1, Theorem 1]) Let $G$ be the Cayley graph of a group with polynomial growth
of degree at least $d\geq 2$. Then $G$ does not have the
$\\{f(n)\\}$-containment property, for any $f(n)=o(n^{d-2})$.

Our first result in the present paper is an analogue to Theorem 1.2 for the
retaining property, which in particular answers Question 1.5 of [8].

######  Theorem 1.3.

Let $G$ be the Cayley graph of a group with polynomial growth of order $d$.
Then $G$ does not have the $\\{f(n)\\}$-retaining property for any
$f(n)=o(n^{d-2})$.

The result above in particular implies that the notions of fire retainment and
fire containment behave similarly on Cayley graphs of groups with polynomial
growth.

The fire-retaining problem on Cayley graphs with faster-than-polynomial growth
presents a richer behavior due to the lack of monotonicity, since the fact
that $G$ has the $\\{f(n)\\}$-retainment property does not necessarily imply
an analogous statement for subgraphs of $G$. In particular, the two notions of
fire retainment and fire containment can behave very differently. For free
groups, for example, the fire-retaining problem is solved by protecting only
one vertex, while fire containment can only be achieved by functions $f$ with
exponential growth ([7]). More than that, it is not hard to see that the
product $F_{k}\times\mathbb{Z}^{d}$ between the free group with $k$ generators
and $\mathbb{Z}^{d}$ has polynomial retainment of degree $d-1$. The second
contribution of the current paper is a general lower bound for retainment in
direct products, which in particular implies that for
$F_{k}\times\mathbb{Z}^{d}$ this is indeed the best possible.

######  Theorem 1.4.

Let $G$ and $H$ be groups with exponential and subexponential-growth,
respectively. The group $G\times H$ does not have the $\\{f(n)\\}$-retainment
property for any function $f$ satisfying

(1.1) $\sum_{k=1}^{10n}f(k)=o(v_{H}(n)),$

where $v_{H}(n)=|B^{H}_{n}|$ denotes the growth function of $H$.

As a corollary, we obtain a negative result for retainment in the case when
$H$ has polynomial growth.

######  Corollary 1.5.

Assume that $G$ has exponential growth and $H$ has polynomial growth of degree
$d$. Then $G\times H$ does not have the $\\{f(n)\\}$-retainment property for
any function $f$ satisfying $f(n)=o(n^{d-1})$.

In Theorem 1.4, we do not have any restrictions for the retainment of the
group $G$. It might be, as in the case of the free group $F_{k}$, that only a
constant number of vertices needs to be protected in order to guarantee fire
retaining. One may hope that if more vertices are needed to attain fire-
retaining on $G$, then this can be translated into a better lower bound for
$G\times H$. This prompts us to propose the following question:

######  Question 1.6.

Assume that $G$ and $H$ are groups with exponential and subexponential growth,
respectively. Assume that $G$ does not have the $\\{g(n)\\}$-retainment
property and let $f$ be a function satisfying (1.1). Under these hypotheses,
is it true that $G\times H$ does not have the $\\{f(n)\cdot g(n)\\}$-retaining
property?

An interesting special case of Question 1.6 is that of taking a direct product
of $\mathbb{Z}$ with the hyperbolic disc. The hyperbolic disk itself has a
simple strategy that allows to retain a constant proportion of the disc by
protecting only 2 vertices in each turn, by simply following arbitrary
different geodesics to infinity (see Figure 1). It is well-known there are
many groups, such as fundamental groups of a surface groups of genus $g\geq 2$
that are quasi-isometric to the hyperbolic disc (see e.g. [5]). Thus by quasi-
isometry invariance of fire-retaining there are (hyperbolic) groups of
exponential growth for which protecting a constant number of vertices each
round is enough for retaining, but protecting only a finite amount of vertices
overall is not.

Figure 1. The hyperbolic disk - a seven regular triangulation. The vertices in
red are (the beginning of) the set of vertices we protect, and the numbers
indicate on which turn we protect them.

We say that a function $f$ has subexponential growth if

(1.2) $\lim_{n}\frac{1}{n}\log f(n)=0.$

When both $G$ and $H$ have exponential growth, we prove that the product does
not have the $\\{f(n)\\}$-retaining property, for any $f$ with subexponential
growth.

######  Theorem 1.7.

If $G$ and $H$ are groups with exponential growth, then $G\times H$ does not
have the $\\{f(n)\\}$-retainment property for any function $f$ with
subexponential growth.

Note that since any two exponential growth functions are equivalent, by the
definition of retainment any finitely generated group $G$ satisfies
$\\{f(n)\\}$-retainment for any function $f$ of exponential growth, thus the
above theorem is tight.

Our last theorem considers wreath products (sometimes known as “lamplighter”
groups, see Section 5 for background and definitions). We prove that any non-
trivial wreath product does not have the retainment property for any
subexponential function.

######  Theorem 1.8.

For any infinite group $G$ and any group $H$ with more than one element, the
wreath product $H\wr G$ does not satisfy $\\{f(n)\\}$-retainment for any
subexponential function $f$.

This theorem is tight in the same sense as Theorem 1.7 and its proof can be
found in Section 5.

Since exponential retainment holds trivialy for any finitely generated group,
we define a new notion we dub strong retainment that asks for protecting a
positive portion of the graph (see Section 2). We end Section 5 showing that
for the lamplighter on $\mathbb{Z}$,
$LL(\mathbb{Z}):=\mathbb{Z}_{2}\wr\mathbb{Z}$ with the switch-walk-switch
generators, $f(n)=4\sqrt{2}^{n}$ is enough to get strong retainment. A slight
modification of the proof of Theorem 1.8 shows that for a given Cayley graph
of the lamplighter group there is no strong retainment for all functions $f$
with small enough exponential growth. Thus one gets exponential lower and
upper bounds for strong retainment on $LL(\mathbb{Z})$.

Acknowledgments. GA and MG were supported by the Israel Science Foundation
Grant 957/20. RB has counted on the support of the Mathematical Institute of
Leiden University. GK was supported by the Israel Science Foundation Grant
607/21 and by the Jesselson Foundation.

##  2\. Notation and preliminaries

In this section, we introduce the notation that will be used throughout the
text.

Let $G$ be a finitely generated group, and fix $S$ a symmetric finite set of
generators for $G$. We consider the Cayley graph of $(G,S)$ and identify its
set of vertices with $G$. Denote by $e=e_{G}$ the identity element on $G$ and,
for a given $R\in\mathbb{Z}\cap[0,\infty)$, let $B_{R}=B_{R}^{G}=B(e,R)$ be
the ball centered in $e$ with radius $R$ with respect to the graph distance.
Furthermore, consider the growth function $v_{G}:\mathbb{N}_{0}\to\mathbb{R}$
defined as

(2.1) $v_{G}(R)=|B_{R}|.$

When the group $G$ is clear from context, we will denote $v_{G}$ simply by
$v$.

Let $f:\mathbb{N}\to\mathbb{N}$ be a sequence of non-negative integers. Assume
that, at time zero, a fire breaks on a finite subset $F_{0}$ of $G$. At
subsequent integer times $n\in\mathbb{N}$, a set $W_{n}$ of size at most
$f(n)$ vertices which are not on fire are declared safe. After that, spread
the fire from $F_{n-1}$ to all neighboring sites that are not safe. Denote the
set of vertices on fire at time $n$ by $F_{n}$ and by $U$ the set of vertices
that are never on fire. We call $\\{W_{n}\\}_{n\in\mathbb{N}}$ an
$\\{f(n)\\}$-allowed strategy if $|W_{n}|\leq f(n)$, for all $n\in\mathbb{N}$.
We say that $G$ has the $\\{f(n)\\}$-fire retaining property if, for every
choice of $F_{0}$, there exists an $\\{f(n)\\}$-allowed strategy such that the
growth of $U$ with respect to the graph metric in $G$ is equivalent to the
growth of $G$.

The group $G$ has polynomial growth of order $d$ if

(2.2) $v_{G}(n)\simeq n^{d},$

meaning that $\frac{v_{G}(n)}{n^{d}}$ is bounded from above and below by
positive constants. The group $G$ has exponential growth if

(2.3) $v_{G}(n)\simeq\gamma^{n},$

for some $\gamma>1$. Groups might also have intermediate growth, in the sense
that it has super-polynomial and subexponential growth functions.

For polynomial growth groups, $G$ has the $\\{f(n)\\}$-retaining property if,
for any finite initial set $F_{0}$, there exist a constant
$c_{\textnormal{\tiny\ref{c:safe_growth}}}=c_{\textnormal{\tiny\ref{c:safe_growth}}}(F_{0})>0$
and an $\\{f(n)\\}$-allowed strategy $\\{W_{n}\\}_{n\in\mathbb{N}}$ such that

(2.4) $\left|U\cap B_{n}\right|\geq
c_{\textnormal{\tiny\ref{c:safe_growth}}}v_{G}(n),$

for all $n$ large enough.

When $G$ is a group with intermediate or exponential growth, the fire
retainment property is not equivalent to having a positive fraction of
vertices not on fire as in (2.4). Indeed, in the exponential-growth case for
example, any two exponential functions have equivalent growth, which in
particular implies that fire retainment can be achieved by protecting an
amount of vertices that grows as a vanishing proportion of the graph and still
has equivalent growth function. Motivated by this, we introduce the concept of
strong retainment. In analogy to the polynomial-growth case, we say that a
graph $G$ has the strong $\\{f(n)\\}$-retaining property if, for any finite
initial set $F_{0}$, there exist a constant
$c_{\textnormal{\tiny\ref{c:safe_growth_2}}}=c_{\textnormal{\tiny\ref{c:safe_growth_2}}}(F_{0})>0$
and an $\\{f(n)\\}$-allowed strategy $\\{W_{n}\\}_{n\in\mathbb{N}}$ such that

(2.5) $\left|U\cap B_{n}\right|\geq
c_{\textnormal{\tiny\ref{c:safe_growth_2}}}v_{G}(n),$

for all $n$ large enough. Notice that strong retainment is equivalent to
(weak) retainment if $G$ has polynomial growth (see (3.2)).

Martínez-Pedroza and Prytuła [8] proved that for polynomial growth groups,
fire retaining is a quasi-isometry invariant in the sense that if, a Cayley
graph $G$ satisfies $\\{f(n)\\}$-retainment and $H$ is quasi-isometric to $G$,
then $H$ satisfies $\\{h(n)\\}$-retainment for some $h\simeq f$. The same
remains true also for non-polynomial growth if one demands that $f$ is
increasing. It is also quite straightforward that this is also the case if $f$
fixates on $0$ after finitely many steps (what is called in [8] “constant step
retainment”).

For a set $A\subset G$, denote the vertex boundary of $A$ by

(2.6) $\partial A=\\{x\in G:\text{there exists }y\in A\text{ with }x\sim
y\\}.$

##  3\. Proof of Theorem 1.3

This section contains the proof of Theorem 1.3. We retain the notation $F_{n}$
and $W_{n}$ from the previous section. The key observation for the proof is
that $\partial\left(\cup F_{n}\right)\subset\cup W_{n}$. More precisely, we
will use the relation

(3.1) $\partial F_{n}\subset\left(F_{n+1}\setminus
F_{n}\right)\bigcup\cup_{k=0}^{n+1}W_{k}.$

We will also need an “initialization step” – that if we do not have
containment then for a large enough initial fire and time many vertices are on
fire. Precisely,

######  Lemma 3.1.

Let $G$ be the Cayley graph of a group with polynomial growth of order $d$.
Then for any $f(n)=o(n^{d-2})$ and any $R_{0}$ sufficiently large there exists
a constant
$c_{\textnormal{\tiny\ref{c:containment}}}=c_{\textnormal{\tiny\ref{c:containment}}}(f,R_{0})$
such that if the initial set $F_{0}$ is taken to be $B_{R_{0}}$ then for all
$\\{f(n)\\}$-allowed strategies $\\{W_{n}\\}_{n\in\mathbb{N}}$,

(3.2) $\left|F_{n}\right|\geq
c_{\textnormal{\tiny\ref{c:containment}}}n^{d},\text{ for all
}n\in\mathbb{N}.$

###### Proof.

This is proved exactly as in [1] (see the proof of Theorem 1, and, in
particular, Equation (4) there). We skip the details. ∎

The core of the proof of Theorem 1.3 is the following argument, which we will
make precise below: assume that we have retainment but not containment, then
for a large enough initial fire and time, both the set of vertices on fire
$F_{n}$ and the set of vertices that are not on fire must hold a positive
portion of the ball $B_{n}$. We then use an isoperimetric inequality to deduce
that the boundary between these two sets is large inside the ball. All the
vertices in this boundary must either catch fire next turn or be protected (at
that step or before). The upper bound on the number of vertices being
protected now translates to a lower bound on the number of new vertices
catching fire. This lower bound implies that in $O(n)$ steps we exhaust all
vertices inside the ball, reaching a contradiction.

Note that the isoperimetry we need is a lower bound on the number of boundary
vertices between $S\cap B_{n}$ and $B_{n}\setminus S$ for a given set $S$.
This is quite different than the usual isoperimetric inequality as sometimes
most of the boundary vertices of $S$ may lie outside the ball. For instance,
if the Cayley graph is a tree (as in the case of the free group) one may
divide $B_{n}$ into two equal size sets with only one boundary vertex between
them (compare with the fact that each of these sets has a large boundary of
its own). The isoperimetric inequality we use is given in Lemma A.2. We are
now ready to give the proof of the theorem.

###### Proof of Theorem 1.3.

Assume the opposite, i.e., that there exists $f(n)=o(n^{d-2})$ such that, for
all initial fires $F_{0}$, there exists an $\\{f(n)\\}$-allowed strategy for
which $U$ has polynomial growth of order $d$. Choose $F_{0}$ such that (3.2)
is true, and consider $c_{\textnormal{\tiny\ref{c:growth}}}$ and
$n_{0}\in\mathbb{N}$ such that (2.4) holds for all $n\geq n_{0}$. Furthermore,
by choosing $n_{0}$ large enough, we can suppose that $F_{n}\subset B_{2n}$,
for all $n\geq n_{0}$.

Combining now Lemma A.2 with Equations (2.4) and (3.2) yields, for all $k\geq
n$,

(3.3) $\begin{split}\left|B_{3n}\cap\partial
F_{k}\right|&\geq\frac{c_{\textnormal{\tiny\ref{c:growth}}}}{n\cdot
v(2n)}\left|F_{k}\cap B_{n}\right|\cdot\left|B_{n}\setminus F_{k}\right|\\\
&\geq\frac{c_{\textnormal{\tiny\ref{c:growth}}}c_{\textnormal{\tiny\ref{c:safe_growth}}}c_{\textnormal{\tiny\ref{c:containment}}}}{n\cdot
v(2n)}n^{2d}\\\ &\geq Cn^{d-1},\end{split}$

for some positive constant $C$.

Fix $\tilde{C}$ such that, for all $n\in\mathbb{N}$,

(3.4) $(\tilde{C}-1)\frac{C}{2}n^{d}\geq v(3n).$

Notice that if we have, for all $k\in[n,\tilde{C}n]$,

(3.5) $\left|\left(F_{k+1}\setminus F_{k}\right)\cap
B_{3n}\right|>\frac{C}{2}n^{d-1},$

then

(3.6) $\begin{split}\left|F_{\tilde{C}n}\cap
B_{3n}\right|&\geq\sum_{k=n}^{\tilde{C}n}\left|\left(F_{k+1}\setminus
F_{k}\right)\cap B_{3n}\right|\\\
&\geq\sum_{k=n}^{\tilde{C}n}\frac{C}{2}n^{d-1}\\\
&\geq\left(\tilde{C}n-n\right)\frac{C}{2}n^{d-1}\\\ &>v(3n),\end{split}$

a contradiction.

This implies that there exists $k\in[n,\tilde{C}n]$ such that

(3.7) $\left|\partial F_{k}\cap B_{3n}\right|\geq Cn^{d-1}\text{ and
}\left|\left(F_{k+1}\setminus F_{k}\right)\cap
B_{3n}\right|\leq\frac{C}{2}n^{d-1}.$

Together with Equation (3.1), we obtain

(3.8) $\left|\bigcup_{j=1}^{k}W_{j}\right|\geq\frac{C}{2}n^{d-1}.$

However, we also have the bound

(3.9)
$\left|\bigcup_{j=1}^{k}W_{j}\right|\leq\sum_{j=1}^{k}f(j)\leq\sum_{j=1}^{\tilde{C}n}f(j)=o(n^{d-1}).$

These two equations yield a contradiction and imply that $G$ does not have the
$\\{f(n)\\}$-retaining property. ∎

##  4\. Proofs of Theorems 1.4 and 1.7

We now proceed with the proof of Theorems 1.4 and 1.7. They follow basically
the same strategy and for that reason we choose to present them together. We
retain the notation $F_{n}$ and $W_{n}$ from Section 2.

The base structure of both proofs as follows: first, we prove an
initialization step (Lemma 4.1 and Corollary 4.2) showing that if we are well
below the containment threshold then many vertices will be on fire. Then, we
examine how the fire spreads on well-chosen fibers of the Cartesian product
$G\times H$, alternating between long stretches where we follow only the
spread on fibers of the form $G\times{h}$ and ${g}\times H$. Assumptions (1.1)
and (1.2) allow us to apply the pigeonhole principle in order to prove the
existence of such fibers. The final important observation is that, if there
exists a vertex $x\in G$ such that the fiber $\\{x\\}\times H$ eventually
contains both a vertex on fire and a vertex not on fire, then it necessarily
contains at least one protected vertex.

######  Lemma 4.1.

Assume $G$ is a group that does not satisfy the $\\{g(n)\\}$-containment
property and let $f\leq g$. There exists a finite set $F_{0}$ of vertices
initially on fire such that, for any $\\{f(n)\\}$-allowed strategy, we have

(4.1) $|F_{n}|\geq\sum_{k=1}^{n}g(k)-f(k),\text{ for all }n\in\mathbb{N}.$

###### Proof.

Since $G$ does not satisfy the $\\{g(n)\\}$-containment property, there exists
a finite set $F_{0}$ for which we necessarily have

(4.2) $|F_{n+1}\setminus F_{n}|\geq g(n)-f(n),\text{ for all }n\in\mathbb{N}.$

Indeed, if this were not the case and, for all $F_{0}$, there exists some $n$
such that the equation above does not hold, we can protect $g(n)$ vertices at
step $n$ and contain the fire.

The proof is now complete by noticing that

(4.3) $|F_{n}|\geq\sum_{k=1}^{n}|F_{k}\setminus
F_{k-1}|\geq\sum_{k=1}^{n}g(k)-f(k).$

∎

######  Corollary 4.2.

Assume that $G$ has exponential growth. Then, there exists a constant
$c_{\textnormal{\tiny\ref{c:fire_spread}}}>0$ such that, for every function
$f(n)\leq e^{c_{\textnormal{\tiny\ref{c:fire_spread}}}n}$, there exists a
finite set $F_{0}$ of vertices initially on fire such that, for any
$\\{f(n)\\}$-allowed strategy, we have

(4.4) $|F_{n}|\geq e^{c_{\textnormal{\tiny\ref{c:fire_spread}}}n},\text{ for
all }n\in\mathbb{N}.$

###### Proof.

This is a consequence of Lemma 4.1 together with the fact that the graph $G$
does not satisfy exponential containment for any rate smaller than the growth
rate of $G$ (see Lehner [7]). ∎

We are now ready to prove Theorem 1.4.

###### Proof of Theorem 1.4.

Choose $F_{0}$ as in Corollary 4.2 and declare all vertices in
$F_{0}\times\\{e_{H}\\}$ as initially on fire in $G\times H$. Set
$k=\max\\{|x|:x\in F_{0}\\}$, and choose $n\geq k$. Consider an
$\\{f(n)\\}$-allowed strategy for the fire-retaining problem on $G\times H$,
and denote by $F_{n}$ the number of vertices on fire at step $n$. Observe
that, due to Corollary 4.2, we have

(4.5) $\Big{|}F_{n}\cap\big{(}G\times\\{e_{H}\\}\big{)}\Big{|}\geq
e^{c_{\textnormal{\tiny\ref{c:fire_spread}}}n},\text{ for all
}n\in\mathbb{N}.$

Denote now by $P_{n}=\bigcup_{k=1}^{10n}W_{n}$ the collection of protected
vertices up to time $10n$, and notice that

(4.6) $|P_{n}|\leq\sum_{i=1}^{10n}f(i)=o(v_{H}(n)).$

In particular, there exists at least one $x\in G$ such that $(x,e)\in F_{n}$
and such that the set $\\{x\\}\times B^{H}_{n}$ has no protected vertices up
to time $3n$. This then implies that, by running the process up to time $3n$,
all vertices in $\\{x\\}\times B^{H}_{n}$ are on fire.

Once again using the fact that $|P_{n}|=o(v_{H}(n))$, there exists $y\in
B^{H}_{n}$ such that

(4.7) $P_{n}\cap\big{(}G\times\\{y\\}\big{)}=\emptyset.$

This then implies that, by time $5n$, all vertices on
$B^{G}_{2n}(x)\times\\{y\\}$ are on fire, which yields that all vertices on
$B^{G}_{n}\times\\{y\\}$ are also on fire.

We now run the process up to time $9n$. Since the whole set
$B_{n}^{G}\times\\{y\\}$ is on fire at time $5n$, if $(a,b)\in B^{G}_{n}\times
B^{H}_{n}$ is not on fire at time $9n$, then

(4.8) $P_{n}\cap\big{(}\\{a\\}\times B^{H}_{n}\big{)}\neq\emptyset.$

This then implies that, if $U$ denotes the set of vertices that are never on
fire,

(4.9) $\Big{|}U\cap\big{(}B^{G}_{n}\times B^{H}_{n}\big{)}\Big{|}\leq
v_{H}(n)|P_{n}|=o(v_{H}(n)^{2}).$

Since this is subexponential, it is asymptotically slower than the growth of
$G\times H$ and the proof is and concluded. ∎

The proof of Theorem 1.7 follows essentially the same steps.

###### Proof of Theorem 1.7.

Due to (1.2), we can choose $F_{0}\subset G$ and $\tilde{F}_{0}\subset H$ as
in Corollary 4.2. Declare all vertices in
$\big{(}F_{0}\times\\{e_{H}\\}\big{)}\cup\big{(}\\{e_{G}\\}\times\tilde{F}_{0}\big{)}$
as initially on fire in $G\times H$.

Denote by $P_{n}$ the collection of protected vertices up to time $10n$, and
write $P_{G}$ and $P_{H}$ to its projection on $G$ and $H$, respectively.

Proceeding as in the proof of Theorem 1.4 (using the fact that $f$ has
subexponential growth), if $(x,y)\in B^{G}_{n}\times B^{H}_{n}$ is not on fire
by time $10n$, then $x\in P_{G}$ and $y\in P_{H}$. In particular, if $U$
denotes the set of vertices never on fire, then

(4.10) $\Big{|}U\cap\big{(}B^{G}_{n}\times
B^{H}_{n}\big{)}\Big{|}\leq|P_{G}\times
P_{H}|\leq\Big{(}\sum_{i=1}^{10n}f(i)\Big{)}^{2}=o(e^{Kn}),$

for every $K>0$, which concludes the proof. ∎

##  5\. Fire retaining on lamplighter groups

Given two discrete groups $G,H$, the (restricted) wreath product $H\wr G$ is
the semidirect product $G\ltimes\bigoplus_{G}H$. Each element in the wreath
product is a pair $(g,L)$ with $g\in G$ and $L\in\bigoplus_{G}H$. Recall that
elements in $\bigoplus_{G}H$ are functions from $G$ to $H$ that differ from
the identity in only finitely many places. The product rule is given by
$(g_{1},L_{1})(g_{2},L_{2})=(g_{1}g_{2},L_{1}L_{2}^{g_{1}})$, where
$L_{1}L_{2}^{g_{1}}(s)=L_{1}(s)L_{2}(g_{1}^{-1}s)$. Wreath products play an
important role in geometric group theory and often serve as a rich source of
examples.

The name lamplighter groups comes from thinking of the coordinate $g\in G$ as
the position of a lamplighter that walks on $G$ and may change the lamps by
changing the lamp at his position. We use this terminology and call $L$ the
lamp configuration. Fix two generating sets $S_{G},S_{H}$ of $G,H$
respectively. We refer to elements of the form $(s_{g},e_{H})$ with $s_{g}\in
S_{G}$ as “walk” and elements of the form $(e_{G},\delta_{h})$, for $h\in
S_{H}$, with $\delta_{h}(e_{G})=h$ and $\delta_{h}(g)=e_{H}$ for $g\neq e_{G}$
as switches. Unless otherwise stated we will take as a generating set the
switch-walk-switch elements, that is elements of the form $S_{1}WS_{2}$, where
$S$ switches lamps and $W$ is a walk generator. By quasi-isometry invariance
this choice does not matter for the sake of the main theorem.

###### Proof of Thereom 1.8.

Denote $\Gamma=H\wr G$, and let $f$ be some subexponential function. By
Corollary 4.2 given a large enough initial fire $F_{0}$, for all large enough
$n$ there are exponentially many vertices on fire inside $B_{n}$. Assume by
contradiction that $\Gamma$ does satisfy $\\{f(n)\\}$-retainment. Then for
$F_{0}$ there is some $\\{f(n)\\}$\- allowed strategy for which for all large
enough $n$ the set of vertices never on fire inside $B_{n}$ is also
exponentially large. From now on we fix this $\\{f(n)\\}$-allowed strategy.
All together we conclude that there exists some $c>0$ such that, for all large
enough $n$, $|U\cap B_{n}(\Gamma)|,|F_{n}\cap B_{n}(\Gamma)|\geq e^{cn}$. To
reach a contradiction, we will find exponentially large subsets
$A=\\{a_{i}\\}\subset(F_{n}\cap B_{n})$ and $B=\\{b_{i}\\}\subset(U\cap
B_{n})$ with some good properties, and a set of paths
$\gamma_{i}:a_{i}\rightarrow b_{i}$ so that these paths are pairwise disjoint
(i.e. $\gamma_{i}$ and $\gamma_{j}$ do not intersect for $i\neq j$) and the
length of each path $\gamma_{i}$ is at most $100n$.

Before constructing the sets $A,B$ and the paths $\gamma_{i}$, let us show how
we use these paths to reach a contradiction from which the theorem follows.
Let $P$ denote the set of all protected vertices till time $101n$. Since $f$
is subexponential, for any large enough $n$, $|P|<|A|$. Therefore there is at
least one $i$ for which no vertex in $\gamma_{i}$ is protected until time
$101n$. Since $a_{i}$ is on fire at time $n$, the fire will spread unhindered
through $\gamma_{i}$ until it reaches $b_{i}$ before time $n+100n$. Thus
$b_{i}$ will eventually catch fire contradicting the fact that $b_{i}\in U$.

It remains now to construct the sets $A,B$ and the paths $\gamma_{i}$. Since
$U\cap B_{n}$ and $F_{n}\cap B_{n}$ are exponential in size, by a simple
pigeonhole principle we can always find subsets $A=\\{a_{i}\\}_{i\in I}\subset
F_{n}\cap B_{n}$ and $B=\\{b_{i}\\}_{i\in I}\subset U\cap B_{n}$ of
exponential size (i.e. $|A|,|B|\geq e^{c_{1}n}$ for some suitable
$c_{0}<c_{1}<c$ and any large enough $n$) such that one of the following four
cases holds:

  1. (1)

All elements in $A\cup B$ have different lamp configurations.

  2. (2)

All elements in $A\cup B$ have different lamplighter positions.

  3. (3)

All elements in $A$ have different lamp configurations, all elements in $B$
have the same lamp configuration and different lamplighter positions, and the
lamp configuration of the elements of $B$ does not appear in the elements of
$A$.

  4. (4)

All elements in $B$ have different lamp configurations, all elements in $A$
have the same lamp configuration and different lamplighter positions, and the
lamp configuration of the elements of $A$ does not appear in the elements of
$B$.

(Note that if $G$ is of subexponential growth, we could always find subsets
satisfying the first clause, but in the general case this is not true _a
priori_). Before going over the different cases, let us set some notation. The
elements of $A$ will be denoted $a_{i}=(x_{i},k_{i})$ where $x_{i}$ is the
lamp configuration (that is supported on $B_{n}$) and $k_{i}$ is the
lamplighter position in $G$. Similarly, elements of $B$ are
$b_{i}=(y_{i},l_{i})$ with lamps $y_{i}$ and lamplighter positions $l_{i}$.
For an element $g\in G$ we denote by $\overrightarrow{g}$ some (arbitrarily
chosen) fixed geodesic path from $e_{G}$ to $g$ in $G$, and for an element
$k\in G$ we denote by $k\overrightarrow{g}$ the translation of the path
$\overrightarrow{g}$ by $k$ (i.e. making the same steps only starting from $k$
instead of $e_{G}$). Finally, we fix two elements $g,g^{*}\in G$ with
$\operatorname{dist}(g,e_{G})=5n$ and $\operatorname{dist}(g^{*},e_{G})=10n$,
and choose some non-identity generator $h$ of $H$. We are now ready to go over
the cases one by one, constructing the paths $\gamma_{i}$ and diluting the
sets if needed.

  1. (1)

Case 1: If the “all off” configuration is in one of $A$ or $B$, remove it. We
construct the paths $\gamma_{i}:a_{i}\rightarrow b_{i}$ as follows

    1. (a)

Move the lamplighter to $g$ by following some geodesic.

    2. (b)

Make a copy of the lamp configuration $x_{i}$ around $g$, so that the lamps in
$B_{n}(g)$ are just a translation by $g$ of the lamps in $B_{n}$. (this can be
achieved simply by multiplying by $a_{i}$).

    3. (c)

Move the lamplighter to $k_{i}g^{*}$ along some geodesic.

    4. (d)

Make another copy of the lamp configuration $x_{i}$ around $g^{*}$.

    5. (e)

Move the lamplighter to $e_{G}$ along some geodesic.

    6. (f)

Change the lamps in $B_{n}$ from $x_{i}$ to $y_{i}$ (in the shortest way).

    7. (g)

Move the lamplighter to $g$.

    8. (h)

Turn off all the lamps in $B_{n}(g)$.

    9. (i)

Move the lamplighter to $g^{*}$ (along some geodesic in $G$).

    10. (j)

Turn off all the lamps in $B_{n}(g^{*})$.

    11. (k)

Move the lamplighter to $l_{i}$ reaching $b_{i}$.

We claim that the paths $\gamma_{i}$ are disjoint for $i\neq j$. To see this,
note that at any step of the path, either the configuration inside
$B_{n}(e_{G})$ is $x_{i}$ (steps $1$-$5$) or the lamp configuration in
$B_{n}(g)$ is a copy of $x_{i}$ (steps $3-7$) or the lamp configuration in
$B_{n}(g^{*})$ is a copy on $x_{i}$ (steps $5-9$) or the lamp configuration in
$B_{n}(e_{G})$ is $y_{i}$ (steps $7-11$). Since the $x_{i}^{\prime}s$ and
$y_{i}^{\prime}s$ are all distinct for different $i$’s, a vertex in
$\gamma_{i}$ cannot be in $\gamma_{j}$. To bound the length of $\gamma_{i}$
note that each “move” step takes at most $11n$ steps, and each “copy/change
the lamps” step takes at most $2n$ steps.

  2. (2)

Case 2: We construct the paths $\gamma_{i}:a_{i}\rightarrow b_{i}$ as follows

    1. (a)

Move the lamplighter to $k_{i}g$ along the path $k_{i}\overrightarrow{g}$.

    2. (b)

Light the lamp at $k_{i}g$ to value $h$.

    3. (c)

Move the lamplighter to $l_{i}g^{*}$ along some geodesic.

    4. (d)

Light the lamp at $l_{i}g^{*}$ to value $h$.

    5. (e)

Move the lamplighter to $k_{i}g$ along some geodesic.

    6. (f)

Turn off the lamp at $k_{i}g$.

    7. (g)

Use some geodesic in $\Gamma$ to turn the lights in $B_{n}(e_{G})$ to $y_{i}$.

    8. (h)

Move the lamplighter to $l_{i}g^{*}$ along some geodesic.

    9. (i)

Turn off the lamp at $l_{i}g^{*}$.

    10. (j)

Move the lamplighter backwards along the path $l_{i}\overrightarrow{g^{*}}$ to
$l_{i}$, reaching $b_{i}$.

Once again the length of the paths created is bounded by $100n$ as the
geodesics in $G$ we move along are of length at most $11n$, and changing the
lamps in $B_{n}(e_{G})$ to $y_{i}$ takes at most $2n$ steps once the
lamplighter is in $e_{G}$.
In this construction we do not claim that all the paths we constructed are
disjoint, but that each path $\gamma_{i}$ only intersects $\leq 1000n^{2}$
other paths. Thus filtering out any path $\gamma_{i}$ that intersects some
$\gamma_{j}$ for $j<i$ will leave us with an exponential family of disjoint
paths (and diluted yet exponential families $A^{\prime}\subset A$ and
$B^{\prime}\subset B$ with the corresponding indexes), completing the case. To
see the claim, first note that since
$k_{i},k_{j},k_{i}g,k_{j}g,l_{i},l_{j},l_{i}g^{*},l_{j}g^{*}$ are all
different for $i\neq j$, the paths cannot intersect while the lamp at $k_{i}g$
or $l_{i}g^{*}$ is on. Thus we need only worry about vertices of step $1$ or
step $10$, overlapping with vertices from the same steps for different $j$’s.
For this, enumerate the vertices on the paths
$\overrightarrow{g},\overrightarrow{g^{*}}$. Let $g_{m},g^{*}_{m}$ denote the
$m$th vertex in $\overrightarrow{g},\overrightarrow{g^{*}}$. Note that since
these are geodesics, $g_{r}\neq g_{q}$ and $g^{*}_{r}\neq g^{*}_{q}$ for any
$r\neq q$. Using inverses we conlcude that for any $i,j$ there is at most one
pair of indeces $r,q$ so that $k_{i}g_{r}=k_{j}g_{q}$, and therefore that the
vertices of step $1$ of $\gamma_{i}$ can intersect at most $25n^{2}$ different
paths $\gamma_{j}$. The same argument works for step $10$ giving a bound of
$100n^{2}$. This concludes the construction for this case.

  3. (3)

Cases 3 and 4. Without loss of generality, we may assume all the $a_{i}$’s
have different lamp configurations, different from $y$ which is the common
lamp configuration for all $b_{i}\in B$, which in turn each have different
lamplighter positions. If roles are reversed we simply reverse the roles in
the construction. We construct the paths $\gamma_{i}$ from $b_{i}$ to $a_{i}$
as follows:

    1. (a)

Move the lamplighter along $\overrightarrow{g}$ to $l_{i}g$.

    2. (b)

Light the lamp at $l_{i}g$ to value $h$.

    3. (c)

Use some geodesic to change the lamps in $B_{n}$ to $x_{i}$.

    4. (d)

Use some geodesic to get the lamplighter to $l_{i}g$.

    5. (e)

Turn off the lamp at $l_{i}g$.

    6. (f)

Use some geodesic to get the lamplighter to $k_{i}$ reaching $a_{i}$.

As in the previous case, since $l_{i}\neq l_{j}$ for $i\neq j$, the paths
$\gamma_{i},\gamma_{j}$ can only intersect when the lamps at $l_{i}g$ and
$l_{j}g$ are off. Since the configurations $x_{i}$ and $x_{j}$ differ, it
remains that intersections between $\gamma_{i}$ and $\gamma_{j}$ can only
happen from vertices at step $1$ of the path. The same argument as before now
gives that each $\gamma_{i}$ intersects at most $25n^{2}$ different
$\gamma_{j}$’s.

The proof now concludes by diluting the set of paths as before. ∎

We finish this section by showing that it is possible to get strong retainment
in the standard lamplighter group on $\mathbb{Z}$ by protecting an exponential
number of vertices with exponent strictly small than the growth rate.

######  Theorem 5.1.

Let $\Gamma$ be the Cayley graph of the lamplighter group
$\mathbb{Z}_{2}\wr\mathbb{Z}$ w.r.t. the switch-walk-switch generating set.
Then $\Gamma$ satisfies $f(n)=2^{(n+2)/2}$ strong retainment.

###### Proof.

Given an initial fire $F_{0}\subset\Gamma$, we can find some $r$ such that
$F_{0}\subset B_{r}$ and choose a parameter $M>r$. The set we are going to
save (that will never burn) will be the set

(5.1)
$S=\Big{\\{}\big{(}(a_{i}),k\big{)}\in\Gamma\,:\begin{array}[]{c}a_{0}=a_{1}=a_{2}=\dotsb=a_{M}=1,\\\
a_{i}=0,\text{ for all }i<0,\text{ and }k>M+1\end{array}\Big{\\}}.$

A straightforward calculation shows that $\frac{|S\cap
B_{R}|}{|B_{R}|}\rightarrow 2^{-M-3}$ as $R\rightarrow\infty$.
To save this set, the vertices we protect will be

(5.2)
$P=\partial_{v}^{in}S=\Big{\\{}\big{(}(a_{i}),k\big{)}\in\Gamma\,:\begin{array}[]{c}a_{i}=0,\text{
for all }i<0,\\\ a_{0}=\dotsb=a_{M}=1,\text{ and }k=M+2\end{array}\Big{\\}}.$

We will protect these vertices in lexicographical order over the rest of the
lamps $a_{M+1}$, $a_{M+2}$ …, protecting by time $n$ all vertices of the form
$P_{n}=\big{\\{}\big{(}(a_{i}),k\big{)}\in P\,:\,a_{i}=0\,\text{ for all
}i>M+n/2\big{\\}}$. This can be done by protecting $2^{(n+2)/2}$ vertices on
turn $n$. It now remains to show that the set $S$ never catches fire. Assume
by contradiction that some vertices in $S$ do catch fire, and let $v$ be one
of the vertices of $S$ that catches fire first, and denote by $n$ the time at
which it catches fire. Then $v\in\partial_{v}^{in}S=P$, and in particular $v$
is of the form $v=(\underline{a},M+2)$. Since $v$ caught fire at time $n$, it
cannot belong to $P_{n}$, hence there is some $i>M+n/2$ for which $a_{i}=1$.
This implies $\operatorname{dist}(v,e)>M+n$ which in turn implies
$\operatorname{dist}(v,F_{0})>n$, contradicting the fact that $v$ caught fire
at time $n$. ∎

##  Appendix A Isoperimetry

For a function $f:G\to\mathbb{R}$, define its discrete derivative at a given
oriented edge $e=(e^{-},e^{+})$ as

(A.1) $\nabla f(e)=f(e^{+})-f(e^{-}).$

Moreover, for a subset $B\subset G$, let

(A.2) $||f||_{L^{1}(B)}=\sum_{x\in B}|f(x)|,$

and

(A.3) $||\nabla f||_{L^{1}(B)}=\sum_{e\in\vec{E}(B)}|\nabla f(e)|,$

where $\vec{E}(B)=\\{e=(e^{-},e^{+}):\,e^{-},e^{+}\in B\text{ and
}\\{e^{-},e^{+}\\}\in E(G)\\}$.

######  Lemma A.1.

Let $G$ be a finitely generated group. For every integer $R\geq 1$ and
function $f:B_{3R}\to\mathbb{R}$,

(A.4) $||f-f_{R}||_{L^{1}(B_{R})}\leq 2R\frac{v(2R)}{v(R)}||\nabla
f||_{L^{1}(B_{3R})},$

where $f_{R}$ denotes the average of $f$ over $B_{R}$

(A.5) $f_{R}=\frac{1}{v(R)}\sum_{x\in B_{R}}f(x).$

The proof follows the steps from [6], which proves an analogous inequality for
the $L^{2}$ norm.

###### Proof.

Fix an integer $R\geq 1$. Define, $\delta f:B_{3R}\to\mathbb{R}$ as

(A.6) $\delta f(x)=\sum_{y\sim x,\,y\in B_{3R}}|f(y)-f(x)|,$

and notice that $||\delta f||_{L^{1}(B_{3R})}=||\nabla f||_{L^{1}(B_{3R})}$.
For every $y\in G$, consider a path of minimal length
$\gamma_{y}:\\{1,\dots,|y|\\}\to G$ from the identity element $e\in G$ to $y$.
If $y\in B_{2R}$, then

(A.7) $\sum_{x\in B_{R}}\sum_{i=1}^{|y|}\delta f(x\gamma_{y}(i))\leq
2R\sum_{z\in B_{3R}}\delta f(z),$

since the map from $B_{R}\times\\{1,\dots|y|\\}$ to $B_{3R}$ that maps $(x,i)$
to $x\gamma_{y}(i)$ is at most $2R$ to one.

Observe now that, for each $x\in B_{R}$,

(A.8) $\begin{split}\sum_{x\in B_{R}}|f(x)-f_{R}|&\leq\frac{1}{v(R)}\sum_{x\in
B_{R}}\sum_{y\in B_{R}}|f(x)-f(y)|\\\ &\leq\frac{1}{v(R)}\sum_{x\in
B_{R}}\sum_{y\in B_{R}}\sum_{i=1}^{|x^{-1}y|}\delta f(x\gamma_{x^{-1}y}(i))\\\
&\leq\frac{1}{v(R)}\sum_{x\in B_{R}}\sum_{w\in B_{2R}}\sum_{i=1}^{|w|}\delta
f(x\gamma_{w}(i))\\\ &\leq\frac{1}{v(R)}\sum_{w\in B_{2R}}2R\sum_{z\in
B_{3R}}\delta f(z)\\\ &\leq 2R\frac{v(2R)}{v(R)}||\nabla
f||_{L^{1}(B_{3R})},\end{split}$

concluding the proof. ∎

The lemma above can be used to deduce isoperimetric inequalities for subsets
of balls of Cayley graphs. Recall from (2.6) that $\partial A$ denotes the
vertex boundary of $A\subset G$. If we consider $f=\mathbf{1}_{A}$, it is a
straightforward calculation that

(A.9) $||\nabla f||_{L^{1}(B_{R})}\leq 2|S|\cdot\left|B_{R}\cap\partial
A\right|.$

Besides,

(A.10) $||f-f_{R}||_{L^{1}(B_{R})}=\frac{2}{v(R)}|B_{R}\setminus A|\cdot|A\cap
B_{R}|.$

Combining the two equations above can be combined with Lemma A.1 we write

$\displaystyle 2|S|\cdot\left|B_{3R}\cap\partial A\right|$
$\displaystyle\stackrel{{\scriptstyle\textrm{(\ref{eq:nabla})}}}{{\geq}}||\nabla
f||_{L^{1}(B_{3R})}\stackrel{{\scriptstyle\textrm{\ref{lemma:poincare}}}}{{\geq}}\frac{v(R)}{2Rv(2R)}||f-f_{R}||_{L^{1}(B_{R})}$
$\displaystyle\stackrel{{\scriptstyle\textrm{(\ref{eq:average})}}}{{=}}\frac{1}{Rv(2R)}|B_{R}\setminus
A|\cdot|A\cap B_{R}|.$

We have thus obtained the following isoperimetric inequality.

######  Lemma A.2.

There exists a positive constant $c_{\textnormal{\tiny\ref{c:growth}}}>0$ such
that, for all subsets $A\subset G$,

(A.11) $\left|B_{3R}\cap\partial
A\right|\geq\frac{c_{\textnormal{\tiny\ref{c:growth}}}}{R\cdot
v(2R)}|B_{R}\setminus A|\cdot|A\cap B_{R}|.$

## References

  * [1] Gideon Amir, Rangel Baldasso, and Gady Kozma.  The firefighter problem on polynomial and intermediate growth groups.  Discrete Mathematics, 343(11):112077, 2020.
  * [2] Mike Develin and Stephen G. Hartke.  Fire containment in grids of dimension three and higher.  Discrete Applied Mathematics, 155(17):2257–2268, 2007.
  * [3] Danny Dyer, Eduardo Martínez-Pedroza, and Brandon Thorne.  The coarse geometry of Hartnell’s firefighter problem on infinite graphs.  Discrete Mathematics, 340(5):935–950, 2017.
  * [4] Bert Hartnell.  Firefighter! An application of domination.  In The 24th Manitoba Conference on Combinatorial Mathematics and Computing, University of Minitoba, Winnipeg, Canada, 1995, 1995.
  * [5] Ilya Kapovich and Nadia Benakli.  Boundaries of hyperbolic groups.
  * [6] Bruce Kleiner.  A new proof of Gromov’s theorem on groups of polynomial growth.  Journal of the American Mathematical Society, 23(3):815–829, 2010\.
  * [7] Florian Lehner.  Firefighting on trees and Cayley graphs.  Australasian Journal of Combinatorics, 75(1):66–72, 2019.
  * [8] Eduardo Martínez-Pedroza and Tomasz Prytuła.  Coarse geometry of the fire retaining property and group splittings.  arXiv preprint arXiv:1904.04658, 2019.


11institutetext:  University of Szeged, Software Engineering Department
11email<EMAIL_ADDRESS>22institutetext: MTA-SZTE Reserach Group on
Artificial Intelligence, ELKH
33institutetext: FrontEndART Ltd., Szeged, Hungary
33email<EMAIL_ADDRESS>
# A Comparison of Different Source Code Representation Methods for
Vulnerability Prediction in Python

Amirreza Bagheri 11 Péter Hegedűs 2233

###### Abstract

In the age of big data and machine learning, at a time when the techniques and
methods of software development are evolving rapidly, a problem has arisen:
programmers can no longer detect all the security flaws and vulnerabilities in
their code manually. To overcome this problem, developers can now rely on
automatic techniques, like machine learning based prediction models, to detect
such issues. An inherent property of such approaches is that they work with
numeric vectors (i.e., feature vectors) as inputs. Therefore, one needs to
transform the source code into such feature vectors, often referred to as code
embedding. A popular approach for code embedding is to adapt natural language
processing techniques, like text representation, to automatically derive the
necessary features from the source code. However, the suitability and
comparison of different text representation techniques for solving Software
Engineering (SE) problems is rarely studied systematically. In this paper, we
present a comparative study on three popular text representation methods,
word2vec, fastText, and BERT applied to the SE task of detecting
vulnerabilities in Python code. Using a data mining approach, we collected a
large volume of Python source code in both vulnerable and fixed forms that we
embedded with word2vec, fastText, and BERT to vectors and used a Long Short-
Term Memory network to train on them. Using the same LSTM architecture, we
could compare the efficiency of the different embeddings in deriving
meaningful feature vectors. Our findings show that all the text representation
methods are suitable for code representation in this particular task, but the
BERT model is the most promising as it is the least time consuming and the
LSTM model based on it achieved the best overall accuracy(93.8%) in predicting
Python source code vulnerabilities.

###### Keywords:

vulnerability prediction code embedding comparative study machine learning

##  1 Introduction

Security bugs (i.e., vulnerabilities) in software are becoming more and more
difficult to identify in today’s applications, allowing hackers and attackers
to profit from their exploit. Every year, tens of thousands of such
vulnerabilities are discovered and fixed. Manually auditing source code and
finding vulnerabilities is costly at best, if not impossible at all.
Therefore, researchers and practitioners have proposed various tools that can
help in discovering vulnerabilities automatically. Classical vulnerability
detection tools rely on static [10, 3, 17] or dynamic [22, 20, 24] code
analysis, symbolic execution or taint analysis. However, with the advent of
efficient machine learning techniques, new approaches appear that try to solve
Software Engineering (SE) problems by training AI prediction models on large
amount of annotated code samples. Vulnerability detection is one typical such
SE task that has been addressed with these new ML approaches. As of today,
using prediction models to decide if a source code fragment is vulnerable or
has became a very common and effective approach. An inherent property of such
approaches is that they can work with numeric vectors (i.e., feature vectors)
as inputs.Therefore, one needs to transform the source code into such feature
vectors, often referred to as code embedding. This process can be either
manual (i.e., defining and extracting features from source code manually, like
lines of code, number of branches, code complexity) or automatic (i.e.,
applying ML based techniques to automatically learn the vector representation
of code). A popular approach for automatic code embedding is to adapt natural
language processing techniques, like text representation [26], to
automatically derive the necessary features from the source code.Despite their
popularity, the suitability and comparison of different text representation
techniques for solving SE problems has been rarely studied
systematically.Given the fact that the accuracy of prediction models relies
heavily on the appropriate representation of input data, we need empirical
data about the effect of such representations on the underlying SE task to be
solved.

In this paper, we present a comparative study of three popular text
representation methods, word2vec [9], fastText [15], and BERT [11] applied to
the SE task of detecting vulnerabilities in Python code. We applied a data
mining approach to collect a suitable training data for training vulnerability
prediction models.Using a heuristic approach (i.e., searching for simple terms
indicating security fixes in commit logs) we collected a large volume of
Python source code from GitHub in both vulnerable and fixed forms.We generated
the vector representation of these code fragments using automatic code
embedding based on the word2vec, fastText, and BERT text representation
methods and used a Long Short-Term Memory [23] network to create a
vulnerability prediction model based on them. Training the LSTM model with the
same architecture on each of the different code representations, we could
compare the efficiency of the various embeddings in deriving meaningful
feature vectors for vulnerability prediction. We investigated the following
two research questions using the above described methodology:

RQ1: Is there a significant difference in the performance of the vulnerability
prediction models based on the different code embedding methods?

RQ2: Are some of the code embedding methods more suitable for predicting
certain types of vulnerabilities than others?

Our findings show that all the text representation methods are suitable for
code representation in this particular task, but the BERT model is the most
promising, as it is the least time consuming, and the LSTM model based on it
achieved the best overall accuracy(93.8%) in predicting Python source code
vulnerabilities. Regarding the various vulnerability types, we observed slight
variances in model performances based on the applied source code embeddings.
Nonetheless, the prediction model based on the word2vec representation of code
clearly outperformed models based on fastText and BERT for detecting SQL
injection, while in case of Command Injection, Cross-Site Request Forgery
(XSRF), Remote Code Execution (RCE), and Path Disclosure the BERT based models
achieved better results than models based on the other two embeddings.

The rest of the paper is organized as follows. In Section 2 we introduce works
that are similar to ours. Section 3 gives details about our dataset collection
methodology, while in Section 4 we describe our overall approach for the
systematic comparison of the different source code embedding methods. Section
5 contains the comparison results. We summarize the set of threats to the
validity of our work in Section 6 and conclude our findings in Section 7.

##  2 Related Work

Solving a SE task with machine learning requires the input source code to be
represented as a numeric vector. Therefore many approaches have been proposed
for deriving meaningful code representations to feed into ML models.

Alon et al. [2] introduce code2vec, a neural model for representing snippets
of code as continuous distributed vectors. The method first breaks down the
code to a collection of paths in its abstract syntax tree. Then, the network
learns the atomic representation of each path while simultaneously learning
how to aggregate a set of them.

Lozoya et al. [16] introduce a new code embedding technique called commit2vec
based on code2vec. This representation focuses on embedding code changes
rather than code snapshots, which they used to successfully train models to
detect vulnerability fixing commits.

Ben-Nun et al. [4] propose a code embedding technique called inst2vec that is
based on an Intermediate Representation (IR) of the code that is independent
of the source programming language. They provide a novel definition of
contextual flow for this IR, leveraging both the underlying data- and control-
flow of the program. The athors of the paper demonstrate the effectiveness of
the approach on compute device mapping, optimal thread coarsening and
algorithm classification .

Mou et al. [18] propose the “coding criterion” to build program vector
representations, which are the premise of deep learning for program analysis.
They evaluate the learned vector representations both qualitatively and
quantitatively.

In our work, we do not propose new code embedding techniques, rather evaluate
the impact of different text representation methods (i.e., word embeddings)
used as code representations for vulnerability prediction. As these techniques
are usually used under the hood of the more complex code representations, this
is a natural first step towards better understanding the application of
natural language processing techniques for solving SE tasks.

There are also many related works that focus on vulnerability prediction or
similar SE tasks based on word embeddings in particular. Harer et al. [13] use
word2vec to create word embeddings for C/C++ tokens. Based on this code
representation they successfully train machine learning models to predict the
results of static analyzers.

White et al. [27] apply word2vec in the scope of automatic program repair. In
their approach, DeepRepair, they create Java token embeddings that they use to
start a recursive encoder for abstract syntax trees. Chen and Monperrus [7]
use word2vec to create Java token embeddings for automated program repair as
well, in order to find the correct ingredients.

Unlike the works mentioned above, we are not focusing on creating a state-of-
the-art prediction model for a particular SE task. Rather, we investigate the
capabilities of various text vectorization techniques as source code
representations in the context of identifying vulnerabilities in Python code
with ML.

The work of Russel et al. [19] is the closest one to ours. They developed a
fast and scalable vulnerability detection tool based on deep feature
representation learning that directly interprets lexed source code. They
compared the bag-of-words (BOW) based simple source code embedding with code
representations learned by CNN and RNN models automatically (i.e., with an
embedding layer). Although our approach is similar, we do not compare
different ML models and automatic code representation learning, but explicitly
compare the effect of applying word embeddings as features for an LSTM
prediction model. To the best of our knowledge, ours is the first attempt to
systematically evaluate the impact of word2vec, fastText, and BERT-based code
embeddings on vulnerability prediction.

##  3 Dataset Extraction

In order to compare the various word embedding based code representations, we
need a training dataset for the vulnerability prediction model relying on
them. We applied a data mining approach to gather actual vulnerability fixes
from various repositories and use them to train our model to recognize
different patterns of security vulnerabilities in source code. We chose GitHub
as our data source as it contains a wide range of open source applications,
including Python source code, which we focus on in this work. We searched for
commits in Python projects with some vulnerability related keywords included
in their commit messages. There are numerous types of security vulnerabilities
in programming languages, but most of them are spread across languages. We
focus on some of the most popular vulnerability types, namely SQL and command
injection, cross-site scripting, cross-site request forgery, remote code
execution, and path disclosure. Our overall data mining process is displayed
in Figure 1.

Figure 1: GitHub data mining process to find vulnerability fixes

###  3.1 Mining GitHub

We followed the guidance provided by Chaturvedi et al. [6], who demonstrated
how to use tools and datasets to mine database repositories and assist us in
gathering data in this time-consuming task. The first step is to collect a
large number of commits that are candidate vulnerability fixes. We searched
for vulnerability fixing commits by querying GitHub data through its public
REST API. Because of GitHub constraints, we first had to extract a dataset
containing commits coming from different language projects and then filter out
data related to Python projects. We ended up collecting approximately 70k
commits yielding to 140k Python code snippets (vulnerable and fixed together)
from 14k different Python projects. To facilitate reproducibility, we
published all the collected data and processing scripts in the form of an
online appendix.111https://doi.org/10.5281/zenodo.4703996

###  3.2 Filtering the Data

After collecting the candidate commits, we filtered them based on some
security relevant keywords. Some sample keywords we use in the heuristic data
collection scripts are shown in Figure 2. For the complete list of search
terms, see the script source in the online appendix package.

Figure 2: Security related search terms used by our heuristic data collection
script

We used the PyDriller tool [21] to download repositories and look for relevant
commits and extract information from them. We also filtered out commits that
did not contain changes in files with ’.py’ extension. Once we identified the
commits that are related to vulnerability fixes, we downloaded the changed
source code before and after the fixes. It turned out that downloading the
source code in a reasonable amount of time was possible if all of the scanning
was done ahead of time in a clever way to keep the number of downloaded
repositories to a bare minimum. The diffs files we downloaded are essentially
large text files that represent the changes in the source code introduced by a
commit; however, they contained some unnecessary details (file name, line
number) that we eliminated before assembling the final dataset using the
previous and subsequent versions of the code snippet. Both snippets contained
the changed lines so we could extract and label the functions in the previous
version as vulnerable while after the fix, they become not vulnerable.

###  3.3 Labels

After filtering the commits based on their messages and downloaded the
relevant code changes in form of diffs, we created the final labeled dataset
as follows. We removed the comments from the affected code blocks because they
are unlikely to impact a file’s vulnerability. After that, we extracted the
fragments of code (i.e., code blocks) from the diff files that were affected
by the fix in the commit and assigned the vulnerable label to its pre-fixed
version while not vulnerable label was assigned to its fixed form. However, it
is not trivial to identify the exact code blocks within the whole source file
that were affected by a vulnerability fixing change. For this, we analyzed the
downloaded diff files and implemented the algorithm presented by Hovsepyan et
al. [14] and Wartschinski et al. [25] to find the appropriate code block.

##  4 Approach

The primary goal of this work is to compare various embedding layers based on
text representations in order to determine their capabilities in detecting
vulnerabilities in Python programs. To achieve an objective comparison, we
need to apply the different source code embedding methods selected with the
same ML algorithm trained on the same dataset. We evaluate the embedding
methods by training a Long Short-Term Memory (LSTM) model with the same hyper-
parameters on the dataset described in Section 3.

###  4.1 The Evaluated Embedding Layers

To encode the code tokens we need to transfer the code tokens into vectors
using one of our selected embedding methods (word2vec, fastText and BERT). For
word2vec and fastText we need to train a model that learns the embeddings
based on a large corpus of Python source code. To collect this, we also mined
GitHub for popular Python projects.

####  4.1.1 Word2vec:

Word2vec is one of the most widely adopted word embedding methods to represent
source code in vector form. To derive word2vec based source code embeddings,
we needed to train a suitable word2vec model on Python source code to encode
the code tokens into word2vec vectors. Training the word2vec model requires a
large corpus of Python source code (for further reference, see the works of
Bhoopchand et al. [5] and Allamanis et al. [1]).

To collect such a corpus, we searched for popular projects on GitHub. GitHub
uses two metrics to measure a repository’s popularity: stars (user-created
highlights) and forks (number of copies of a repository). The list of selected
repositories with a high number of stars and forks used as a code corpus is
available in our online appendix. We used PyDriller [21] for querying the most
popular projects and downloading their source files. The resulting source
code, 11 million lines in total from 38 of the most popular projects, is
simply concatenated to create a single massive Python code file. Another
script is then used to fix any issues with the text, such as indentation
errors. We transform the Python programs into Python tokens using the built-in
Python tokenizer. We delete the comments from files and add new lines at the
end of the file. Tabs and indentations have been normalized. The word2vec
model is then trained on the corpus using the Gensim
222https://radimrehurek.com/gensim/ Python package (see Figure 3). All the
word2vec training scripts are also part of our online appendix.

Figure 3: Transforming code into vectors

####  4.1.2 FastText:

We use the exact same process for calculating fastText [15] embeddings as for
word2vec. This means, we apply the same data analysis and tokenizer scripts
and train the embedding model with the same Python code corpus. We chose
fastText as a study subject because word2vec only learns vectors for words
that are complete in the training corpus. FastText, on the other hand, learns
vectors for both the n-grams and the full words contained inside each word.
FastText uses the mean of the target word vector and its component n-gram
vectors for training at each step. The change derived from the error is then
applied uniformly to all of the vectors that were combined to form the target.
This adds a significant amount of extra computation to the training step. A
word must sum and average its n-gram component parts at each point.

####  4.1.3 BERT:

Bidirectional Encoder Representations from Transformers (BERT) is a Google-
developed Transformer-based machine learning technique for natural language
processing (NLP) pre-training [11]. Jacob Devlin and his Google colleagues
developed and released BERT in 2018. We selected this embedding method for
comparison due to its recent successes within the NLP field. As the BERT model
is pre-trained on natural language texts, to adopt it to source code, we used
its Microsoft’s variant, called CodeBERT [12]. CodeBERT is a pre-trained BERT
model for programming languages. In the context of this paper, we used BERT
only as an embedding method and we feed all output tokens to an LSTM model.
The biggest difference between BERT and the other two embedding methods is
that the training part of the embedding model is done in advance using a huge
corpus in case of BERT, while for word2vec and fastText, we need to do the
training locally. This means that CodeBERT can be used out of the box, without
having to train a model for token embeddings.

###  4.2 Preparing the Data for Classification

The collected vulnerability dataset (see Section 3) contains data in the form
of vulnerable and not vulnerable code snippets. We need to transform these
into a list of tokens (such as ’+’, ’for’, ’init’) and convert each token into
its vector representation according to the different embedding methods. Each
list of such vectors (representing the list of tokens of the underlying code
snippet) will be labeled, where label ’1’ means that the code is vulnerable
and ’0’ means it is not vulnerable. Since ML models require a fix-sized input,
we took the overall length of the concatenated vectors for the longest code
snippet in our dataset and padded all the shorter ones with zeros to make them
have the same length.

We split the training dataset into three sets, train, validation and test. 80%
of the data selected randomly is used for training, 10% for validating and 10%
for testing. Note that the validation data is only used to evaluate the model
performance but all the results are presented on the test data, which the
model has never seen before, applying a 10-fold cross-validation.

###  4.3 Training the LSTM

After transforming each of our learning samples into a fix-sized numeric
vector, we are ready for training the LSTM model on them. For the
implementation of the model, we used the Keras library [8]. The first
component of the model is the LSTM layer, which learns the features associated
with the label of the code snippet (i.e., whether it is vulnerable or not). We
can use a variety of hyper-parameters for the model, like dropout.

Then, there is an activation layer that creates a dense output layer with one
neuron. We used the Sigmoid activation function as our aim is to predict
between two classes: vulnerable and not vulnerable. We applied different
hyper-parameters and tried out several different combinations of them as a
set. Technically, the evaluation metric and loss functions are also hyper-
parameters. We chose to compare the model performances based on the F1-score
metric.

Figure 4: The steps of creating and evaluating the vulnerability prediction
models based on different code representations

Our model’s base hyper-parameter is the number of neurons, which has a direct
impact on its learning capacity; the more neurons we use, the more complex
structures our model can recognize, but the training can also take longer.
Finally, we have the number of epochs, or the number of times the learning
algorithm can iterate over the entire training data set, which we set to 100
and 200. The high-level overview of our code representation
evaluation/comparison process is shown in Figure 4.

##  5 Results

With data mining, we created a large dataset of Python code snippets from
GitHub and labeled them as being vulnerable or not vulnerable based on
detected vulnerability fixing commits. The dataset covers six common types of
vulnerabilities (SQL and command injection, cross-site scripting, cross-site
request forgery, remote code execution, and path disclosure). We trained an
LSTM classifier using different embedding layers (i.e., word2vec, fastText,
and BERT) with different hyper-parameters to compare the impact of the three
different source code embeddings on vulnerability detection predicting
performance.

Figure 5: LSTM model results using word2vec, fastText and BERT with various
epochs and dropout ratio

The results of the LSTM models based on the three different code embedding
layers are displayed in Figures 5 and 6. Figure 5 shows the changes in F1
scores based on the number of epochs and ratio of dropout applied for the
training. As can be seen, the results are very close for the three embedding
approaches. Word2vec based results are slightly outperforming the others for
small number of epochs and high droput rate. However, for more than 75 epochs
and a droput rate lower than 20%, BERT based models perform the best.

Figure 6: LSTM model results using word2vec, fastText and BERT with various
number of neurons and batch sizes

Figure 6 depicts F1 score changes based on the hyper-parameters of neuron
counts and batch sizes. Again, the results achieved with the different
embedding methods are very close. For smaller number of neurons, word2vec
based models work better, while for large number of neurons, BERT becomes
superior to others. BERT is also the best performing model when it comes to
various batch sizes. It works best with batch sizes between 400 and 600. It is
also true, that word2vec slightly outperforms fastText when applying larger
batch sizes.

LSTM models using the BERT-based code representation achieve, on average, an
accuracy of 93.8%, a recall of 83.2%, a precision of 91.4%, and an an F1 score
of 87.1%. The models based on the word2vec code representation achieve, on
average, an accuracy of 91%, a recall of 86.1%, a precision of 88.2%, and an
F1 score of 85.6%. While fastText code representation based models achieve, on
average, an accuracy of 91.8%, a recall of 86.4%, a precision of 85.1%, and an
F1 score of 84%, on average, an accuracy of 91%, a recall of 81%, a precision
of 90% and an F1 score of 82%. Based on the results, we can answer RQ1 as
follows.

RQ1. We did not observe significant differences in the vulnerability
prediction performances of the LSTM models trained on different code
embeddings. All of them are suitable the represent code for this task (all the
models achieve an accuracy above 90%). However, for BERT based models seems to
perform slightly better, especially using larger batch sizes and smaller
dropout rate.

To answer RQ2, we calculated the same performance measures grouped by the
different vulnerability types. We categorized each code snippet according to
the keywords found in the vulnerability fixing commit. As it can be seen from
Figures 7, 8, and 9, there is not much variance in model performance values
within the categories.

Figure 7: LSTM+word2vec results for each vulnerability categories

The word2vec based models (see Figure 7) show the least variance in model
performances within vulnerability categories. The only minor exception is the
recall for XSS, which is clearly lower than that of the others or the average,
mostly because finding good vulnerable dataset of it is difficult and we think
that we didn’t train it with enough data. On the other hand, word2vec based
models perform the best among all in detecting SQL injection vulnerabilities.

Figure 8: LSTM+fastText results for each vulnerability categories

The fastText based models (see Figure 8) show a higher variance within
vulnerability categories. They have similar average performance values to the
word2vec based models, but are less effective in finding XSS, XSRF, and Path
disclosure types of vulnerabilities.

Figure 9: LSTM+BERT results for each vulnerability categories

The BERT based models (see Figure 9) have the highest average performance
measures and the variance in the values is small within the categories. The
only exception is SQL injection, where BERT based models are less efficient
than the other models (recall of 78%, F1 score of 80.1%). However, in case of
Command Injection, Cross-Site Request Forgery (XSRF), Remote Code Execution
(RCE), and Path Disclosure the BERT based models achieved better results than
models based on other embeddings. We can sum up the above observations to
answer RQ2 as follows.

RQ2. The prediction models based on the different code representations show
balanced performance measures within vulnerability categories. However, we
found that vulnerability fix detection on top of word2vec-based embedded code
outperform others in detecting SQL injection, while all the remaining
vulnerability types are detected most effectively when BERT based models were
used for code embedding .

##  6 Threats to Validity

The heuristic data collection is a major threat to the validity of the
results. With a keyword based commit search we might include irrelevant
commits (that do not fix vulnerabilities) and we might miss out those that fix
vulnerabilities but do not contain the searched keywords. To mitigate this
threat, we manually investigated a small sample of the collected data, which
we found to be accurate in the majority of cases. Since we collected a very
large amount of such training data, the impact of several mis-classified
commits should be negligible.

Many scenarios exist where a weakness arises from the interaction of lines of
code that are distributed over a large file (or multiple files). However,
since the examples for vulnerabilities used to train the model only
concentrate on the immediate vicinity of fixed lines, the model might be
unable to learn the consequences of far-reaching dependencies. Even though our
results might not generalize to all of the different types of vulnerabilities,
we believe these preliminary empirical results are already valuable.

Limitations in the chosen approach may also be a threat to the internal
validity. We selected one specific prediction model to compare three different
code embedding algorithms. Different ML models might yield to different
results. In the future, we plan to extend our scope and add multiple ML models
and code embeddings to the comparison.

##  7 Conclusion

In this paper, we presented an empirical study where we performed the
comparison of three word embedding based code representation methods in the
context of vulnerability prediction in Python code. These methods – word2vec,
fastText, and BERT – adopted from the field of natural language processing,
are widely used in practice to represent source code as numeric vectors and
solve SE tasks (e.g., code summarization, bug detection, or finding copy-
pasted code parts) with ML models trained on these representations. Despite
their popularity, very few works evaluate and compare their impact on the
prediction performances of the ML models relying on them.

With a data mining approach, we collected vulnerability fixing commits from
which we could extract vulnerable (before the fix) and not vulnerable (after
the fix) code snippets that formed our training dataset (140k Python code
snippets in total). We applied the three investigated code embeddings to these
code snippets and fed the resulting vectors into the same LSTM architecture to
train a prediction model. Our findings show that all the text representation
methods are suitable for code representation in this particular task, but the
BERT model is the most promising as it is the least time consuming and the
LSTM model based on it achieved the best overall accuracy(93.8%) in predicting
source code vulnerabilities. Regarding the various vulnerability types, we
observed slight variances in model performances based on the applied source
code embeddings. Nonetheless, the prediction model based on the word2vec
representation of code clearly outperformed models based on fastText and BERT
for detecting SQL injection, while in case of Command Injection, Cross-Site
Request Forgery (XSRF), Remote Code Execution (RCE), and Path Disclosure the
BERT based models achieved better results than models based on other
embeddings.

Our future work will focus on using different classifiers and improving the
approach for labelling the data, collecting a dataset of higher quality, and
leveraging the commit context to create actionable fix recommendations. The
work could also be extended to other programming languages or types of
vulnerabilities.

## Acknowledgment

The presented work was carried out within the SETIT Project
(2018-1.2.1-NKP-2018-00004)333Project no. 2018-1.2.1-NKP-2018-00004 has been
implemented with the support provided from the National Research, Development
and Innovation Fund of Hungary, financed under the 2018-1.2.1-NKP funding
scheme. and supported by the Ministry of Innovation and Technology NRDI Office
within the framework of the Artificial Intelligence National Laboratory
Program (MILAB). The research was partly supported by the EU-funded project
AssureMOSS (Grant no. 952647).

Furthermore, Péter Hegedűs was supported by the Bolyai János Scholarship of
the Hungarian Academy of Sciences and the ÚNKP-20-5-SZTE-650 New National
Excellence Program of the Ministry for Innovation and Technology.

## References

  * [1] Allamanis, M., Sutton, C.: Mining source code repositories at massive scale using language modeling. In: 2013 10th Working Conference on Mining Software Repositories (MSR). pp. 207–216. IEEE (2013)
  * [2] Alon, U., Zilberstein, M., Levy, O., Yahav, E.: code2vec: Learning distributed representations of code. Proceedings of the ACM on Programming Languages 3(POPL), 1–29 (2019)
  * [3] Arroyo, M., Chiotta, F., Bavera, F.: An user configurable clang static analyzer taint checker. In: 2016 35th International Conference of the Chilean Computer Science Society (SCCC). pp. 1–12. IEEE (2016)
  * [4] Ben-Nun, T., Jakobovits, A.S., Hoefler, T.: Neural code comprehension: A learnable representation of code semantics. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. p. 3589–3601. NIPS’18, Curran Associates Inc., Red Hook, NY, USA (2018)
  * [5] Bhoopchand, A., Rocktäschel, T., Barr, E., Riedel, S.: Learning python code suggestion with a sparse pointer network. arXiv preprint arXiv:1611.08307 (2016)
  * [6] Chaturvedi, K.K., Sing, V., Singh, P.: Tools in mining software repositories. In: 2013 13th International Conference on Computational Science and Its Applications. pp. 89–98. IEEE (2013)
  * [7] Chen, Z., Monperrus, M.: The remarkable role of similarity in redundancy-based program repair. arXiv preprint arXiv:1811.05703 (2018)
  * [8] Chollet, F., et al.: Keras: The python deep learning library. Astrophysics Source Code Library pp. ascl–1806 (2018)
  * [9] Church, K.W.: Word2vec. Natural Language Engineering 23(1), 155–162 (2017)
  * [10] Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Miné, A., Monniaux, D., Rival, X.: The astrée analyzer. In: European Symposium on Programming. pp. 21–30. Springer (2005)
  * [11] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv:1810.04805 (2018)
  * [12] Feng, Z., Guo, D., Tang, D., Duan, N., Feng, X., Gong, M., Shou, L., Qin, B., Liu, T., Jiang, D., et al.: Codebert: A pre-trained model for programming and natural languages. arXiv preprint arXiv:2002.08155 (2020)
  * [13] Harer, J.A., Kim, L.Y., Russell, R.L., Ozdemir, O., Kosta, L.R., Rangamani, A., Hamilton, L.H., Centeno, G.I., Key, J.R., Ellingwood, P.M., Antelman, E., Mackay, A., McConley, M.W., Opper, J.M., Chin, P., Lazovich, T.: Automated software vulnerability detection with machine learning (2018)
  * [14] Hovsepyan, A., Scandariato, R., Joosen, W., Walden, J.: Software vulnerability prediction using text analysis techniques. In: Proceedings of the 4th international workshop on Security measurements and metrics. pp. 7–10 (2012)
  * [15] Joulin, A., Grave, E., Bojanowski, P., Douze, M., Jégou, H., Mikolov, T.: Fasttext.zip: Compressing text classification models. arXiv:1612.03651 (2016)
  * [16] Lozoya, R.C., Baumann, A., Sabetta, A., Bezzi, M.: Commit2vec: Learning distributed representations of code changes. SN Computer Science 2(3), 1–16 (2021)
  * [17] Olesen, M.C., Hansen, R.R., Lawall, J.L., Palix, N.: Coccinelle: Tool support for automated cert c secure coding standard certification. Science of Computer Programming 91, 141–160 (2014)
  * [18] Peng, H., Mou, L., Li, G., Liu, Y., Zhang, L., Jin, Z.: Building program vector representations for deep learning. In: Zhang, S., Wirsing, M., Zhang, Z. (eds.) Knowledge Science, Engineering and Management. pp. 547–553. Springer International Publishing, Cham (2015)
  * [19] Russell, R., Kim, L., Hamilton, L., Lazovich, T., Harer, J., Ozdemir, O., Ellingwood, P., McConley, M.: Automated vulnerability detection in source code using deep representation learning. In: 2018 17th IEEE international conference on machine learning and applications (ICMLA). pp. 757–762. IEEE (2018)
  * [20] Skaletsky, A., Devor, T., Chachmon, N., Cohn, R., Hazelwood, K., Vladimirov, V., Bach, M.: Dynamic program analysis of microsoft windows applications. In: 2010 IEEE International Symposium on Performance Analysis of Systems & Software (ISPASS). pp. 2–12. IEEE (2010)
  * [21] Spadini, D., Aniche, M., Bacchelli, A.: Pydriller: Python framework for mining software repositories. In: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. pp. 908–911 (2018)
  * [22] Srivastava, A., Eustace, A.: Atom: A system for building customized program analysis tools. ACM SIGPLAN Notices 39(4), 528–539 (2004)
  * [23] Sundermeyer, M., Schlüter, R., Ney, H.: LSTM neural networks for language modeling. In: 13th Annual Conference of the International Speech Communication Association (2012)
  * [24] Waddington, D.G., Roy, N., Schmidt, D.C.: Dynamic analysis and profiling of multithreaded systems. In: Advanced Operating Systems and Kernel Applications: Techniques and Technologies, pp. 156–199. IGI Global (2010)
  * [25] Wartschinski, L.: Detecting Software Vulnerabilities with Deep Learning. Master’s thesis, Humboldt University, Berlin (2014)
  * [26] Wen, Y., Zhang, W., Luo, R., Wang, J.: Learning text representation using recurrent convolutional neural network with highway layers. arXiv preprint arXiv:1606.06905 (2016)
  * [27] White, M., Tufano, M., Martinez, M., Monperrus, M., Poshyvanyk, D.: Sorting and transforming program repair ingredients via deep learning code similarities. 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER) (Feb 2019)