#  Challenging Machine Learning-based Clone Detectors via Semantic-preserving
Code Transformations

Weiwei Zhang, Shengjian Guo,Hongyu Zhang,Yulei Sui, Yinxing Xue, and Yun Xu
W. Zhang is a master student with school of Computer Science and Technology,
University of Science and Technology of China<EMAIL_ADDRESS>Y. Xue
and Y. Xu work in the School of Computer Science and Technology at the
University of Science and Technology of China<EMAIL_ADDRESS>S. G
works in the Baidu Security<EMAIL_ADDRESS>H. Zhang works in the University
of Newcastle<EMAIL_ADDRESS>Y. Sui works in the University of
Technology Sydney. yulei.sui@uts.edu.au(Corresponding author: Yinxing Xue.)
Manuscript received April 19, 2005; revised August 26, 2015.

###### Abstract

Software clone detection identifies similar or identical code snippets. It has
been an active research topic that attracts extensive attention over the last
two decades. In recent years, machine learning (ML) based detectors,
especially deep learning-based ones, have demonstrated impressive capability
on clone detection. It seems that this longstanding problem has already been
tamed owing to the advances in ML techniques. In this work, we would like to
challenge the robustness of the recent ML-based clone detectors through code
semantic-preserving transformations. We first utilize fifteen simple code
transformation operators combined with commonly-used heuristics (i.e., Random
Search, Genetic Algorithm, and Markov Chain Monte Carlo) to perform equivalent
program transformation. Furthermore, we propose a deep reinforcement learning-
based sequence generation (DRLSG) strategy to effectively guide the search
process of generating clones that could escape from the detection. We then
evaluate the ML-based detectors with the pairs of original and generated
clones. We realize our method in a framework named CloneGen (stands for Clone
Generator). In evaluation, we challenge the two state-of-the-art ML-based
detectors and four traditional detectors with the code clones after semantic-
preserving transformations via the aid of CloneGen.  Surprisingly, our
experiments show that, despite the notable successes achieved by existing
clone detectors, the ML models inside these detectors still cannot distinguish
numerous clones produced by the code transformations in CloneGen. In addition,
adversarial training of ML-based clone detectors using clones generated by
CloneGen can improve their robustness and accuracy. Meanwhile, compared with
the commonly-used heuristics, the DRLSG strategy has shown the best
effectiveness in generating code clones to decrease the detection accuracy of
the ML-based detectors. Our investigation reveals an explicable but always
ignored robustness issue of the latest ML-based detectors. Therefore, we call
for more attention to the robustness of these new ML-based detectors.

###### Index Terms:

Clone Detection, Code Transformaiton, Semantic Clone, Machinae Learning

##  1 Introduction

Code reuse via copy-and-paste actions is common in software development. Such
practice typically generates a large amount of similar code, which is often
called _code clones_. According to the large-scale study conducted by Mockus
[1], more than 50% of files were reused in some open-source projects. Though
code cloning may be helpful under proper utilization [2], it can also become
bad programming practice because of the painful maintenance costs [3]. For
example, Li et al. [4] reported that 22.3% of operating systems’ defects were
introduced by code cloning. Moreover, code cloning also brings intelligence
property violations [5, 6, 7] and security problems [4, 8].

In retrospect, source code clone detection is an active research domain that
attracts extensive attentions. Multiple clone detectors have been proposed
based on various types of code representations, including _Textual_ \- or
_Token_ -based [9, 10], _Ast_ -based [11], _PDG_ -based [12], etc. These
traditional detectors are primarily designed for syntax-based clone detection
(clones with syntactic similarity). Besides, many of them are of limited
capability (e.g., specialized for a certain type of clones) and low-efficiency
[13, 14].

Recently, the latest machine learning (ML) methods have been significantly
enhancing the capabilities of clone detectors. For example, FCDetector [15]
trains a DNN network to detect clones of functions by capturing code syntax
and semantic information through _AST_ (abstract syntax tree) and _CFG_
(control flow graph). ASTNN [16] maintains an _AST_ -based neural source code
representation that utilizes a bidirectional model to exploit the naturalness
of source code statements for clone detection. TBCCD [17] obtains structural
information of code fragments from _AST_ and lexical information from code
tokens and adopts a tree-based traditional approach to detect semantic clones.
CCLearner [18] extracts tokens from source code to train a DNN-based
classifier and then uses the classifier to detect clones in a codebase. These
new ML-based approaches fuse the latest ML techniques with the code features
extracted from clones, thus achieving highly accurate results. Usually, they
can detect most semantic clones with accuracy over 95% [15, 16, 17].

Though the new ML-based clone detectors have shown impressive accomplishments,
their effectiveness heavily relies on well-labeled training data [19]. The
performance of a detector trained with one dataset can be less effective in
detecting code clones in another dataset. Unlike simple texts, source code
contains both textual and structural information, which makes ground-truth
clone pairs more versatile. Hence, building a robust prediction model for code
clone detection is inherently challenging. For example, code fragments int
b=0; and int b;b=0; have the same semantics, but their _CFG_ and _AST_
slightly differ. Hence, rather than applying heavy code obfuscations and
compiler optimizations, can we merely generate light-weight source code
variations at some program locations to effectively lower the accuracy of a
ML-based detector? From this point, we investigate and observe that _adopting
semantic-preserving transformation of a code fragment is of practical
importance in validating the robustness of ML-based clone detectors._

Specifically, we present a framework, named CloneGen, that performs semantic-
preserving code transformations to challenge ML-based clone detectors. In
CloneGen, we have developed 15 lightweight and semantic-preserving code
transformations (e.g., variable renaming, for-loop to while-loop conversion,
code order swapping, etc.). In general, CloneGen targets the cheap yet
effective transformation (or a combination of transformations) on a given code
snippet to evade the clone detection. To effectively guide the combinations of
the 15 atomic transformations, CloneGen supports various heuristic strategies
(i.e., Random Search, Genetic Algorithm, and Markov Chain Monte Carlo).
Essentially, to quickly find the (near-) optimal solutions for evading clone
detection is an optimization problem of how to combine multiple
transformations. To address this, we design a deep reinforcement learning
(DRL) sequence generation model (called DRLSG), which uses a Proximal Policy
Optimization (PPO) strategy neural network [20] to guide the search process.

With CloneGen, we select unique code snippets from the widely used OJClone
datasets  [21]. Given a selected code snippet $x$, we generate semantic-
preserved variants and pair $x$ with each of them. Then, we feed the formed
clone pairs to the ML-based detectors to challenge whether they can still
determine these code clones produced by our framework.

To evaluate the effectiveness of CloneGen, clone pairs generated by CloneGen
are provided to the two state-of-the-art open-source ML-based detectors
(namely, ASTNN and TBCCD), as well as a baseline detector TextLSTM [22]. We
find that 40.1%, 32.9% and 44.2% of the clone pairs supplied by CloneGen can
successfully evade the detection of ASTNN, TBCCD, and TextLSTM, respectively.
Considering the original accuracy of these detectors (more than 95%) on the
OJClone datasets, experimental results prove that CloneGen is notably
effective in lowering the accuracy of the ML-based clone detectors via the
DRLSG-guided lightweight code transformations. Meanwhile, we further evaluate
the effectiveness of CloneGen in improving the robustness of ML-based clone
detectors via adversarial training. In the best case, adversarial training
improved the f-measure of the model by 43.9%. We find among the clone pairs
provided by DRLSG, 13.2% and 15.8% can still successfully escape from the
detection of ASTNN and TBCCD after adversarial training.

To summarize, we made the following contributions:

  * •

The design and implementation of CloneGen, which supports various heuristic
strategies to guide the code transformations and generate semantic-preserving
code clones to challenge the clone detectors.

  * •

The proposal of a new DRL-based strategy that dispatches multiple lightweight
yet effective code transformation operators at different program locations.

  * •

The evaluation of CloneGen upon the ML-based detectors (ASTNN, TBCCD, and
TextLSTM) and the traditional detectors (NiCad and Deckard). Results show
CloneGen can sharply decrease the detection accuracy of these detectors.

  * •

A further adversarial training of ML-based detectors using the clones produced
by CloneGen, which can improve the robustness of the assessed ML-based
detectors. Notably, the DRL-based strategy is most effective in lowering the
detection accuracy of the adversarial trained detectors.

⬇

1// #1 Original code

2int main(){

3 int a[6]={100,50,20,10,5,1},b[6];

4 int n,i,k;

5 scanf("%d",&n);//input

6 for(i=0; i<6; i++){

7 b[i]=0;}

8 for(k=0; k<6; k++){

9 for(i=0; n>=a[k]; i++){

10 n=n-a[k];

11 b[k]+=1;}}

12 for(i=0; i<6; i++){

13 printf("%d\n",b[i]);}

14 return 0; }

⬇

1// #2 Type IV clone code

2int main()

3{

4 int n,a[6],i;

5 int b[6]={100,50,20,10,5,1};

6 scanf("%d",&n);

7 for(i=0;i<6;i++)

8 {

9 a[i]=n/b[i];

10 n=n-a[i]*b[i];

11 printf("%d\n",a[i]);

12 }

13 return 0;

14}

⬇

1// #3 Code after equivalent transformation

2int main(){

3 int n, i, k1;

4 int a[(3 + 2 + 1)] = {100, 50, 20, (5 + 2.5 + 2.5), (2.5 + 1.25 + 1.25),
(0.5 + 0.25 + 0.25)};

5 int b[6];scanf("%d", &n);{ i = (0 + 0 + 0);

6 while (i < 6) {b[i] = (0 + 0 + 0);

7 i = i + 1; }; }

8 {k1 = 0;while(k1 < 6) {{i=0;

9 while(a[k1] <= n){i++;n = n - a[k1];

10 b[k1] += 1;};}k1 = k1 + 1;};

11 }{i = 0;while(i < 6) {

12 printf("%d\n", b[i]);i++;};

13} return 0;}

Figure 1: Motivating example of code clone at different levels. All the clone
instances are of the same semantics.

##  2 Preliminaries

###  2.1 Types of Clones and Clone Detection Methods

###### Definition 1

(Clone Types) According to [23], code clones are generally categorized into
four types, namely Type I, II, III, and IV, which represent the degrees of
code similarity between an original code piece and a new one, respectively.

  * •

Type I: The two code snippets are mostly identical except for the comments,
indentation, and layout.

  * •

Type II: The differences between two code snippets are limited in variable
names, function names, types, etc, in addition to differences due to Type I.

  * •

Type III: The two code snippets have slight modifications such as changed,
added, removed, or reordered statements, in addition to differences due to
Type I and II.

  * •

Type IV: Type IV only preserves semantic similarity. Thus, the two code
snippets may have similar functionality but different structural patterns.

Type I–III code clones are usually referred to as _syntactic_ clone, which
copies the code fragments and retains a large body of textual similarity. By
In contrast, if the copied code merely exposes functional similarity, such as
cloning presents a Type IV clone, a so-called _semantic_ clone.

Over years, various clone detectors have appeared in the literature [13, 14].
Typically, they convert software code under detection into specific
representations and develop methods to distinguish the similarities against
the generated representations. Before the emergence of ML-based detectors,
traditional detectors (e.g., CCAligner [10], Deckard [11], CCGraph [12])
mainly rely on _Token_ -, _AST_ -, or _PDG_ -representation to measure the
code similarity. Usually, they can successfully detect Type I–III syntactic
clones, but fail to match Type IV semantic clones. ASTNN [16] splits the whole
_AST_ into small statement trees for the finger-grained encoding of the
program lexical and syntactic information. FCDetector [15] adopts a joint code
representation of syntactic and semantic features generated from fusion
embedding. TBCCD [17] applies a tree-based convolution for semantic clone
detection, which leverages both the structural information from _AST_ and the
lexical information from code tokens. These ML-based detectors all achieve a
stunningly high detection accuracy on the experimental datasets, often with
the detection accuracy of more than 95% [15, 16, 17].

###  2.2 An Example of Clone Detection

Fig. 1 displays a code snippet $S$ and the Type IV and Mutated of clones on
$S$. Code $S$ come from the OJClone [21] database. It is to find the minimum
number of notes of different currency denominations (e.g., {100,50,20,10,5,1})
that sum up to the given amount (i.e., the input variable n). All the clones
in Fig. 1 are solutions to the same problem, but with different levels of
syntactic changes. Specifically, Type IV instance is more compact — it uses
division instead of continuous subtraction to obtain integer quotients at line
11, and finish the calculation and printing in one for a loop.

For this motivating example, the well-trained ASTNN, TextLSTM, and TBCCD can
all correctly match the Type IV code (ref. code snippets #2 in Fig.1) with the
original code (ref. code #1 in Fig.1) — ML-based detector success in
identifying the syntactic and semantic clones. By far, these ML-based
detectors seem to be quite effective, _but can they thoroughly address the
semantic clone detection problem_?

###  2.3 Motivation

With the above question, we manually create a clone code by applying several
lightweight code transformations. Given the code snippet #1 in Fig. 1, after
changing the variable name k at line 4, splitting large constants into smaller
ones at line 3, swapping the code order at lines 3,4, removing part of the
code comments at line 5, and converting a for-loop to while-loop at lines
7,8,9,12, we generate the code snippet #3 in Fig. 1).

Then, we construct two clone instances as {#1, #3} and {#2, #3} from pairing
the new code #3 with existing code pieces in Fig. 1. Now, we run ASTNN,
TextLSTM, and TBCCD on these new clone instances. We are curious to see
whether a few uncomplicated code variants could lead to some different
findings. Surprisingly, experimental results show that all three detectors
failed to classify all two code pairs to be code clones. This interesting
result implies that some cheap code-level changes could indeed nullify the
DNNs in these detectors, without using dedicated adversarial samples or heavy
code obfuscation (e.g., obfuscation based on encoding [24, 25, 26] and CFG-
flattening [27, 28]). This observation motivates us to investigate the
following questions to facilitate the automation of adversarial code clone
generation:

  * •

Can code clones from lightweight semantic-preserving transformations steadily
invalidate the detection of ML-based detectors?

  * •

What kind of _transformation strategy_ is needed to guide the effective
searching process of combining these semantic-preserving transformations?

  * •

Can we leverage the new clone instances from the semantic-preserving
transformations to improve the ML-based detectors and would the improvements
be explicitly beneficial?

To answer these questions, we propose and implement the clone generation
framework CloneGen.

Figure 2: CloneGen system overview

##  3 CloneGen: An Overview

In this section, we describe the overall workflow for evaluating ML-based
clone detectors, explain the three technical challenges we must address.

###  3.1 The Overview of CloneGen

Fig. 2 illustrates the overview of CloneGen. In general, CloneGen consists of
two phases: the _clone generation_ phase and the _detector evaluation_ phase.
The former takes a source code snippet as input, performs code equivalence
transformations, and outputs the mutated code snippets. The latter evaluation
phase feeds the original code snippets together with the newly generated ones
to a set of state-of-the-art clone detectors and outputs whether the new clone
pairs could be detected by these detectors.

For example, given code #1 in Fig. 1, the steps of producing code snippet #3
by CloneGen are as follows. First, it extracts features of code snippet #1 and
searches for the locations where code transformation could be applied (see §
4.2). Second, it adopts the predefined 15 atomic transformation operators to
make sure that all the performed changes preserve the semantics of the
original code (see § 4.1). Third, CloneGen also adopts a certain
transformation strategy that properly adjusts the probability of activating an
individual transformation operator (see § 4.3). Finally, by applying the
transformation operators in the order determined by the searching strategy,
new code that is more likely to escape from existing detectors can be
generated (see § 4.4). Till now, the clone generation phase is finished.

###  3.2 Technical Challenges

While the high-level idea appears to be straightforward, there are three
challenges to address for realizing CloneGen:

  * •

Transformation Operator. In this work, we require equivalence transformations,
which slightly modify the code syntactic but leave the code semantics intact.
Therefore, the operators in this study are different from _mutation operators_
in _mutation testing_ [29]. Mutation testing mutates source code for inserting
small faults into programs to measure the effectiveness of a test suite. So
mutators in mutation testing usually change code semantics during generating
new code. However, we aim to achieve semantic equivalence transformations.
Towards this goal, we adopt many transformation operators proposed in [30] and
[31]. In total, CloneGen supports 15 unique transformation operators,
including variable renaming, changing syntax structures with equivalent
semantic, adding junk code, deleting irrelevant code, reordering independent
code, etc. Details and examples can be found in § 4.1.

  * •

Encoding Schema. Before applying transformation operators, it is required to
localize potential code places applicable to proper operators. For example, we
must locate all the for-loop in code before we can decide whether to execute
the operator of Op2 (see Op2 in Tab. I). Thus, the code fragments that satisfy
the transformation conditions are abstracted to execute the encoding. The
abstraction needs to be fast and scalable as we target the large codebase in
evaluation. To address this issue, CloneGen develops a compact bitvector-based
representation for encoding the search space of changing a program function.
Specifically, suppose a function owns $n_{v}$ variables (i.e., function name,
function arguments, local variables and used global variables), $n_{f}$ for-
loop statements, $n_{w}$ while-loop statements, $n_{do}$ do-while statements,
$n_{ie}$ if-elseif statements, $n_{i}$ if-else statements, $n_{s}$ switch
statements, $n_{r}$ relational expressions, $n_{u}$ unary operations (e.g.,
i++), $n_{sc}$ self-changing operations (e.g., i+=1), $n_{c}$ constant values,
$n_{d}$ times of variable definition, $n_{b}$ code blocks ($\\{...\\}$),
$n_{is}$ blocks of isomorphic statements that have no dependency in the
control flow, and $n_{p}$ print and comment statements. The length of the
encoded bit vectors would be the sum of these values:

$\small l_{b}=sum(n_{v},n_{f},n_{w},n_{do},n_{ie},n_{i},n_{s},\\\
n_{r},n_{u},n_{sc},n_{c},n_{d},n_{b},n_{is},n_{p})$ (1)

During the generation phase, if a binary bit is enabled to be $1$, CloneGen
will apply the corresponding transformation operator to the code location.
However, it is still a difficult problem to have an optimal strategy of
applying operators that match specific code structure for an equivalence
transformation — generating semantic clones with various optimization goals.
Thus, we need a _transformation strategy_.

  * •

Transformation Strategy. As mentioned above, after defining transformation
operators and encoding the search space, there is another challenge: how
should we decide the chance of being enabled (i.e., $1$) for each bit after
encoding, to maximize the diversity of the generated semantic clones — to
challenge the existing ML-based clone detectors? Generally, it appears to be a
combinatorial optimization problem with a huge search space (for example, it
is $2^{45}$ for the code snippet #1 in Fig. 1) that could be addressed by
commonly-used heuristic strategies, such as Random-Search (RS), Genetic
Algorithm (GA) [32], Markov chain Monte Carlo (MCMC) [33], and the recently
popular Deep Reinforcement Learning (DRL), etc. These strategies usually need
some goals or objective functions (e.g., the fitness function in GA).
Regarding this challenge, in § 4.3, for the commonly-used strategies (RS, GA
and MCMC), we implement these strategies to guide the transformation based on
some existent studies [34, 35, 36]. However, it is not straightforward to
leverage DRL for this problem, for which we propose the DRLSG model in § 5.

##  4 CloneGen: Technical Approach

Table I: The descriptions and examples of 15 atomic transformation operators in CloneGen Transformation Operator |  Description |  Original |  Changed
---|---|---|---
Op1-ChRename |  Function name and variable name renaming. |  int i; |  int i1;
Op2-ChFor |  The for-loop is transformed into a while-loop. |  for(i=0;i<10;i++){ BodyA } |  i=0; while(i<10){ BodyA i++; }
Op3-ChWhile |  The while-loop is transformed into a for-loop. |  while(i<10){ BodyA } |  for(;i<10;){ BodyA}
Op4-ChDo |  The do-loop is transformed into a while-loop. |  do{ BodyA }while(i<10); |  BodyA while(i<10){ BodyA}
Op5-ChIfElseIF |  Transformation of if elseif to if else. |  if(grad<60) BodyA else if(grad<80) BodyB else BodyC |  if(grad<60) BodyA else{ if(grad<80) BodyB else BodyC }
Op6-ChIf |  Transformation of if else to if elseif. |  if(grad<60) BodyA else{ if(grad<80) BodyB else BodyC } |  if(grad<60) BodyA else if(grad<80) BodyB else BodyC
Op7-ChSwitch |  Transformation of the Switch statement to the if elseif statement. |  switch(a){ case 60: BodyA case 70: BodyB default: BodyC } |  if(a==60) BodyA else if(a==70) BodyB else BodyC
Op8-ChRelation |  Transformation of relational expressions. |  a<b |  b>a
Op9-ChUnary |  Modifications to unary operations. |  i++; |  i=i+1;
Op10-ChIncrement |  Modifications to incremental operations. |  i+=1; |  i=i+1;
Op11-ChConstant |  Modifying constants. |  8 |  (a-b) //8=a-b
Op12-ChDefine |  Modifications to variable definitions. |  int b=0; |  int b;b=0;
Op13-ChAddJunk |  Adding junk codes. |  if(a){ BodyA} |  if(a) { BodyA if(0) return 0; }
Op14-ChExchange |  Change the order of the statements in a block without data and control dependency. |  a=b+10; c=d+10; |  c=d+10; a=b+10;
Op15-ChDeleteComments |  Deleting statements that print debugging hints and comment. |  printf("test"); //comments |  //printf("test"); //comments

In this section, we elaborate on major steps of CloneGen.

###  4.1 Transformation Operator

CloneGen transforms the given program source code by a set of atomic
operations. These code transformations must not change the semantic of a
program. Thus, we formally define these operations as _equivalence
transformations_.

###### Definition 2

Equivalence Transformation. Let
$C\stackrel{{\scriptstyle\tau}}{{\longrightarrow}}C^{\prime}$ be a
transformation ($\tau$) of a code snippet $C$ into a code snippet $C^{\prime}$
based on the combinations of a set of atomic code transformation operators
$\mathcal{S}_{o}$, so $C$ and $C^{\prime}$ form a pair of semantic clones.

Tab. I summarizes all the atomic transformation operators in CloneGen. The
first column lists the operator names, the second column briefly describes how
each atomic operation takes effect, the third column shows a simple code
example before equivalence transformation and the last column gives the
transformed code after the transformation. Fig. 3 Representation of successive
formulations of code transformations. We have implemented these operators
based on Txl111Txl: a programming language that converts input to output by a
set of conversion rules, https://www.txl.ca/txl-abouttxl.html..

Transformations based on these 15 operators defined in Tab. I is _lightweight_
, as only lexical analysis in Txl is adopted. Since there are no complicated
operations on _CFG_ , _PDG_ , or call graph (_CG_), the transformation only
works at the syntax level. Meanwhile, the transformation manages to make
_semantic equivalence_ — all the operators guarantee to have the same
semantics before and after the transformation. Even for Op4 that changes a do-
while-loop statement into a while-loop, the body statement inside the do-
while-loop will be executed once before entering the transformed while-loop.
For Op14, we only reorder the statements without any data- or control-
dependency, as such analysis is fast and easy. For Op15, we only delete
comments or the statements that print debugging hints or intermediate results.
For the rest of the operators, it is straightforward that these operators
would not change code semantics (see operational semantics defined for these
operators in Fig. 3).

$\displaystyle\begin{aligned} &Symbols:\ \rightarrow\ means\ syntax\
transformation,\ \Downarrow\ means\ evaluation\ operation,\ Change\ function\
is\ a\ bijection\ function,\ \\\ &Dependency\ is\ a\ data\ and\ control\
dependency\ statements\ set\ in\ a\ block,\ Comments\ is\ a\ comment\
statement\ set,\ Printf\\\ &is\ a\ printf\ call\ statements\ set\ with\
constant\ arguments.\end{aligned}$

$\displaystyle\begin{aligned} E\rightarrow E^{\prime}&\quad S\rightarrow
S^{\prime}\\\ \hline\cr do\ S\ \quad while(E)\quad\rightarrow&\quad
S^{\prime};while(E^{\prime})\ S^{\prime}\end{aligned}$ (Op4-ChDo)

$\displaystyle\begin{aligned} S_{1}\rightarrow S_{1}^{\prime}\quad
E\rightarrow E^{\prime}&\quad S_{2}\rightarrow S_{2}^{\prime}\quad
S_{3}\rightarrow S_{3}^{\prime}\\\ \hline\cr for(S_{1};E;S_{2})\
S_{3}\rightarrow&\\{S_{1}^{\prime}\\};\quad
while(E^{\prime})\\{S_{3}^{\prime};S_{2}^{\prime}\\}\end{aligned}$ (Op2-ChFor)

$\displaystyle\begin{aligned} E&\rightarrow E^{\prime}\\\ \hline\cr E\
\texttt{+=}\ 1\quad\quad\rightarrow&\quad E^{\prime}\ \quad\texttt{=}\ \quad
E^{\prime}\ \texttt{+}\ 1\end{aligned}$ (Op10-ChIncrement)

$\displaystyle\begin{aligned} E\rightarrow E^{\prime}&\quad S\rightarrow
S^{\prime}\\\ \hline\cr if(E)\ \\{S\\}\rightarrow
if(E^{\prime})\quad&\\{S^{\prime};if(0)\ return\ 0;\\}\end{aligned}$
(Op13-ChAddJunk)

$\displaystyle\begin{aligned} S\rightarrow S^{\prime}&\quad E\rightarrow
E^{\prime}\\\ \hline\cr while(E)\ \quad S\quad&\rightarrow\quad
for(;E^{\prime};)\ S^{\prime}\end{aligned}$ (Op3-ChWhile)

$\displaystyle\begin{aligned} S\in&Comments\lor F\in Printf\\\ \hline\cr
S&\rightarrow\\{\\}\quad F(E)\rightarrow\\{\\}\end{aligned}$
(Op15-ChDeleteComments)

$\displaystyle\begin{aligned} E\rightarrow E^{\prime}&\quad id\rightarrow
id^{\prime}\\\ \hline\cr int\ id\ \texttt{=}\ E\quad\rightarrow&\quad int\
id^{\prime};\ id^{\prime}\ \texttt{=}\ E^{\prime}\end{aligned}$
(Op12-ChDefine)

$\displaystyle\begin{aligned} N_{1}\in[10..1000]\quad
N_{1},&N_{2},N_{3}\in\mathbb{Z}\quad\quad N_{2}\texttt{-}N_{1}\Downarrow
N_{3}\\\ \hline\cr N_{3}\rightarrow(&N_{2}\texttt{-}N_{1})\end{aligned}$
(Op11-ChConstant)

$\displaystyle\begin{aligned} E_{1}\rightarrow E_{1}^{\prime}\quad
E_{2}\rightarrow E_{2}^{\prime}\\\ \hline\cr E_{1}<E_{2}\rightarrow
E_{2}^{\prime}>E_{1}^{\prime}\end{aligned}$ (Op8-ChRelation)

$\displaystyle\begin{aligned} E_{1}\rightarrow E_{1}^{\prime}\quad
S_{1}\rightarrow\quad S_{1}^{\prime}\quad E_{2}&\rightarrow
E_{2}^{\prime}\quad S_{2}\rightarrow S_{2}^{\prime}\ \quad\quad
S_{3}\rightarrow S_{3}^{\prime}\\\ \hline\cr if(E_{1})\ S_{1}\ else\
\\{if(E_{2})\ S_{2}\ else\ S_{3}\\}&\rightarrow
if(E_{1}^{\prime})S_{1}^{\prime}\ elseif(E_{2}^{\prime})\ S_{2}^{\prime}\
else\ S_{3}^{\prime}\end{aligned}$ (Op6-ChIf)

$\displaystyle\begin{aligned} E&\rightarrow E^{\prime}\\\ \hline\cr
E\texttt{++}\rightarrow&E^{\prime}\ \texttt{=}\ \quad
E^{\prime}\texttt{+}1\end{aligned}$ (Op9-ChUnary)

$\displaystyle\begin{aligned} E_{1}\rightarrow E_{1}^{\prime}\quad
S_{1}\rightarrow S_{1}^{\prime}\quad E_{2}&\rightarrow E_{2}^{\prime}\quad
S_{2}\rightarrow S_{2}^{\prime}\quad S_{3}\rightarrow S_{3}^{\prime}\\\
\hline\cr if(E_{1})\ S_{1}\ elseif(E_{2})\ S_{2}\ else\ S_{3}&\rightarrow
if(E_{1}^{\prime})S_{1}^{\prime}\ else\ \\{if(E_{2}^{\prime})\ S_{2}^{\prime}\
else\ S_{3}^{\prime}\\}\end{aligned}$ (Op5-ChIfElseIf)

$\displaystyle\begin{aligned} id^{\prime}\quad\in\quad&change(id)\quad\\\
\hline\cr id&\rightarrow id^{\prime}\end{aligned}$ (Op1-ChRename)

$\displaystyle\begin{aligned} S_{1}\notin Dependency\quad S_{2}\notin
Dependency&\quad\quad S_{1}\rightarrow S_{1}^{\prime}\quad\S_{2}\rightarrow
S_{2}^{\prime}\\\ \hline\cr S_{1};S_{2}&\rightarrow
S_{2}^{\prime};S_{1}^{\prime}\end{aligned}$ (Op14-ChExchange)

$\displaystyle\begin{aligned} E\rightarrow E^{\prime}\quad S_{1}\rightarrow
S_{1}^{\prime}\quad S_{2}&\rightarrow S_{2}^{\prime}\quad S_{3}\rightarrow
S_{3}^{\prime}\\\ \hline\cr switch(E)\\{case\ N_{1}:\ S_{1}\quad case\
N_{2}:S_{2}\quad default:\ S_{3}\\}\rightarrow&if(E^{\prime}\ \texttt{==}\
N_{1})\ S_{1}\quad else\ if(E^{\prime}\ \texttt{==}\ &N_{2})\ S_{2}\ else\
S_{3}\end{aligned}$ (Op7-ChSwitch)

Figure 3: Operational semantics for the atomic code transformation operators.

###  4.2 Encoding

Before code transformation, it is required to identify _syntactic features_ ,
the places of code fragments applicable to an atomic operation in Tab. I. We
use the term _feature count_ to represent the number of code fragments on
which CloneGen performs the corresponding atomic operations. Tab. II
illustrates the feature and its feature count of code #1 in Fig. 1. The first
and second column corresponds to the atomic operations and the denoting
variables in Tab. I and the third column corresponds to their values. The last
column lists the bitvector after encoding code #1 in Fig. 1. For example, if
there are $4$ for-loop in a source code snippet, then the feature count of the
syntactic feature for-loop is $n_{f}=4$. In the third column, the value $0$
means that there are no places applicable to the corresponding atomic
operation. For example, no while-loop in code #1, and hence its value $n_{w}$
is $0$. There are $5$ variables {a, b, n, i, k} in code #1, so the feature
count for $n_{v}$ is $5$. Note that the main function cannot be renamed, so it
is excluded from the feature count of the feature $n_{v}$. Hence, for code
snippet #1 in Fig. 1, its bit-vector length $l_{b}$ is $45$ (the sum of column
“value” in Tab. II).

After we encode the transformation search space using the bit vector, the
length of the bit vector equals the feature count in the second column, where
an atomic operation would take effect on the features (i.e., applicable
places) for bit value $1$, and no effect for $0$. The symbol "n.a." means
there are no available features that match the corresponding atomic operation,
and the feature count must be $0$. We explain how to fill the bit vector with
various strategies in the next section.

Table II: Syntatic features and encoding of code #1 in Figure 1 Operator |  Count |  value |  Bitvector Encoding
---|---|---|---
Op1 |  $n_{v}$ |  5 |  001000
Op2 |  $n_{f}$ |  4 |  1111
Op3 |  $n_{w}$ |  0 |  n.a.
Op4 |  $n_{do}$ |  0 |  n.a.
Op5 |  $n_{ie}$ |  0 |  n.a.
Op6 |  $n_{i}$ |  0 |  n.a.
Op7 |  $n_{s}$ |  0 |  n.a.
Op8 |  $n_{r}$ |  4 |  0001
Op9 |  $n_{u}$ |  4 |  0110
Op10 |  $n_{sc}$ |  1 |  0
Op11 |  $n_{c}$ |  18 |  100011000000001011
Op12 |  $n_{d}$ |  2 |  01
Op13 |  $n_{b}$ |  5 |  00000
Op14 |  $n_{is}$ |  2 |  10
Op15 |  $n_{p}$ |  0 |  n.a

###  4.3 Transformation Strategy

After the encoding step, CloneGen needs a transformation strategy to generate
the semantic clones of diversity.

As discussed earlier, the search problem of finding an optimal sequence of
applying the atomic operations can be treated as a combinatorial optimization
problem. Thus, we may achieve different solutions by exploring existing
optimization algorithms. In CloneGen, we have already implemented three
commonly-used heuristic strategies, namely Random-Search (RS), Genetic
Algorithm (GA), Markov Chain Monte Carlo (MCMC). Details of each strategy are
as follows:

  * Random-Search: The RS strategy fills the bits in a bit vector with random values 0 or 1, with equal probability. Hence, this strategy does not take into account the source code structure under detection and the features employed by different clone detectors. Hence, the RS strategy favors generating semantic clones whose equivalent code changes are attributed to randomness [37].

  * Genetic Algorithm: The GA [38] strategy computes the similarity between the original code and the generated new code after each random generation. The idea is to generate the code that exhibits the most textual differences from the original code. Here we convert both code versions into strings and then calculate the string editing distance [39] between them to obtain the code similarity. An editing distance reflects how many modification steps it needs to convert one string into another, and it is used as the _fitness function_ in GA. Hence, the GA strategy favors generating semantic clones with big gaps (large editing distance) [35, 36].

  * Markov Chain Monte Carlo: The MCMC strategy uses the _n-gram_ algorithm to calculate the probability that determines how likely a sub-sequence follows its prefix. It is observed that software programs have probabilistic natures, which assign probabilities to different sequences of words [40, 34]. For a given sequence of code snippet $s=s_{1}s_{2}\cdots s_{n}$, we define $P\left(s_{n}\mid s_{n-k+1},\cdots,s_{n-1}\right)$ to approximate the probability of code statement $s_{n}$ occurring after statements $s_{n-k+1}$ to $s_{n-1}$. Inspired by [41], we also adopt the indicator _perplexity_ [41], to measure the probability magnitude of code occurrence. According to n-gram ($n=k$), the formula corresponds to:

$H_{\mathcal{M}}(s)=-\frac{1}{n}\sum_{1}^{n}\log
p_{\mathcal{M}}\left(s_{i}\mid s_{i-k+1}\cdots
s_{i-1}\right)(\operatorname{\tiny Perplexity})$

According to the above formula, this strategy guides code transformations
through several iterations and outputs the generated clones satisfying the
above perplexity condition. Hence, the MCMC strategy favors generating
semantic clones hard to understand (being high perplexing) [34].

Though the above three strategies are in general effective, they would not
take into consideration the feedback (e.g., detection results) of the assessed
clone detectors. To mitigate this limitation, we specially design and
implement a DRL-based method, named DRLSG, to interactively incorporate the
detectors’ results for generating further complicated semantic clones (see §
5).

###  4.4 Clone Generation

As shown in Fig. 2, CloneGen performs a lightweight transformation phase
guided by different strategies. For example, there are four for-loop in the
original code of Fig. 1. The last column of Tab. II shows the bit vectors from
the RS strategy. As stated in § 4.2, Bit value 1 in a bit vector means that
CloneGen must execute the code mutation operation at the corresponding code
fragment, while bit value 0 means CloneGen should keep the original code piece
unchanged. Since all bits for operator, Op2 have the value of $1$, CloneGen
transforms the four for-loop into semantics preserving while-loop, as shown by
code #3 in Fig. 1. Due to the randomness of these strategies, we could obtain
a large number of code variants (e.g., code #3 to code #1 in Fig. 1). For the
strategies other than RS (i.e., GA, MCMC, and DRLSG), not all code variants
will be retained — for effectiveness, only those satisfying certain
optimization goals (e.g., perplexity) will be retained.

Notably, our atomic operations are lightweight: according to our experiments
(as described in § 6), the transformation operations can be completed within a
relatively short time.

##  5 DRLSG: Theory and Design

In this section, we introduce the background knowledge of reinforcement
learning and our proposed Deep Reinforcement Learning Sequence Generation
(DRLSG) strategy.

###  5.1 Deep Reinforcement Learning

In recent years, deep reinforcement learning (DRL) algorithms have been used
in a variety of fields [42, 43, 44], most notably AlphaGo[45] to defeat the
best human players in Go, and DRL has quickly become the focus of the
artificial intelligence community. This paper is based on deep reinforcement
learning to generate high-quality source code for transformation sequences.
Before we start presenting our approach, we briefly introduce background
knowledge about DRL. The following formulation of a typical DRL process is
related to the presentation given in [46]

We briefly introduce the terms commonly used in DRL: Agent: The role of a
learner and decision-maker. Environment: Everything that is composed of and
interacts with something other than the agent. Action: The behavioral
representation of the agent body. State: The information that the capable body
obtains from the environment. Reward: Feedback from the environment about the
action. Strategy: The function of the next action performed by the agent based
on the state. on-policy: The policy that corresponds when the agent learns and
the agent interacts with the environment are the same. off-policy: The policy
when the agent to be learned and the agent interacting with the environment
are not the same.

In reinforcement learning, a policy indicates what action should be taken in a
given state and is denoted by $\pi$. If we use deep learning techniques to do
reinforcement learning, the strategy is a network. Inside the network, there
is a set of parameters, and we use $\theta$ to represent the parameters of
$\pi$ [47]. We take the environment output state ($s$) and the agent output
action ($a$), and string $s$ and $a$ all together, called a Trajectory
($\tau$), as shown in the following
equation:$\tau=\left\\{s_{1},a_{1},s_{2},a_{2},\cdots,s_{t},a_{t}\right\\}$
.You can calculate the probability of each trajectory occurring:

$\displaystyle p_{\theta}(\tau)$
$\displaystyle=p\left(s_{1}\right)\prod_{t=1}^{T}p_{\theta}\left(a_{t}\mid
s_{t}\right)p\left(s_{t+1}\mid s_{t},a_{t}\right)$ (2)

The reward function determines how many points are available for said action
now based on a certain action taken in a certain state. What we have to do is
to adjust the parameter $\theta$ inside the actor so that the value of
$\bar{R}_{\theta}=\sum_{\tau}R(\tau)p_{\theta}(\tau)$ is as large as possible.
We use gradient ascent because we want it to be as large as possible. We take
a gradient for $\bar{R}$, where only $p_{\theta}$ is related to $\theta$, so
the gradient is placed at $p_{\theta}$.

$\theta\leftarrow\theta+\eta\nabla\bar{R}_{\theta}$ (3)
$\displaystyle\nabla\bar{R}_{\theta}=E_{\tau\sim
p_{\theta}(\tau)}\left[R(\tau)\nabla\log p_{\theta}(\tau)\right]$ (4)

Proximal policy optimization(PPO) [20] is a variant of policy gradient. Using
$\pi_{\theta}$ to collect data, we have to sample the training data again when
$\theta$ is updated. So we want to go from on-policy to off-policy. We change
on-policy to off-policy by importance sampling, from $\theta$ to
$\theta^{\prime}$. So now the data is sampled with $\theta^{\prime}$, but the
parameter to be adjusted for training is the model $\theta$.

$\nabla\bar{R}_{\theta}=E_{\tau\sim
p_{\theta^{\prime}}(\tau)}\left[\frac{p_{\theta}(\tau)}{p_{\theta^{\prime}}(\tau)}R(\tau)\nabla\log
p_{\theta}(\tau)\right]$ (5)

###  5.2 DESIGN OF DRLSG

Figure 4: Deep reinforcement learning model

As shown in Fig. 4, our DRLSG model has two main components: agent and
environment. The agent mainly consists of a neural network, and here we choose
the openAI open source PPO222Stable Baselines3 is a set of reliable
implementations of reinforcement learning algorithms in PyTorch,
https://stable-baselines3.readthedocs.io/en/master/modules/ppo.html. model as
our agent. The input to the agent is the encoding vector (state) of the code,
and we train the agent to choose the corresponding transformation operator §
4.1, to maximize the reward value. The environment consists of three main
parts: the code transformation according to the action chosen by the agent,
the code is encoded to obtain the vector as the state of the environment, and
the reward is calculated for the current decision. Next, we describe the
specific design of the DRLSG.

####  5.2.1 Action Space

In our DRLSG task, the agent is trained to select the action to be performed
from the action space given a state. We use the 15 transformations designed as
the action space of the model, and in our task, the goal of the model is to
select a set of operations from the 15 transformations to transform the source
code. These transformations are shown in Tab. I, where we give descriptions of
the specific operations and simple examples, and in Fig. 3, where we give
formal definitions of the corresponding equivalent transformations.

####  5.2.2 Reward

The reward function is designed to guide the overall actions of the agent and
reward is the key to the DRL, we need to maximize the cumulative gain of the
agent. The main goal of our agent is to produce variant codes that can escape
detection by Ml-based clone tools. For this purpose, our reward function for
each step is formalized as Algorithm 1.

Input:

$action$: The current action performed by the agent.

$code_{o}$: The original code.

$code_{t}$: The current action gets the code snippet.

$code_{t-1}$:The code snippet of the previous state.

Output:

$reward$

1

2if  _!clone( $code_{o}$,$code_{t}$)_ then

3 $reward$=$nclone_{R}$

4 end if

5else

6 $reward$=-$clone_{R}$ * codeTextSim($code_{t}$,$code_{t-1}$)

7 end if

8if  _action==Op13_ then

9 $reward$=$reward$- $Op13\\_count$ * $Op13\\_penalty$

10 $Op13\\_count$++

11 end if

Algorithm 1 Reward Algorithm

As shown in Fig. 4 Our reward has two main components that make up the current
action to get the edit distance between $code_{t}$ and $code_{t-1}$, and the
current action to get the clone detection result between $code_{t}$ and
$code_{o}$. They constitute our reward, and we are considering a long-term
reward. We implement a text-based Siamese network source code clone detection
model, using two identical bidirectional LSTM (BiLSTM) networks in Siamese’s
architecture. The $code_{o}$ and $code_{t}$ are converted into text sequences
and fed into BiLSTM to obtain a representation of the code. If the TextLSTM
identifies the $code_{t}$ and the $code_{o}$ as non-clones, we assign a large
positive reward (Line 1-3 in Algorithm 1) and abort the current learning,
indicating that we have obtained a transformed sequence of the current code.

The edit distance indicates the minimum number of single-character editing
operations required to convert from one word to another. There are three types
of editing operations: insert, delete, and replace. For example, for the words
"kitten" and "sitting", the minimum single-character editing operations
required to convert from "kitten" to "sitting" are: substitution of "s" for
"k", the substitution of "i" for "e", and insertion of "g" at the end, so the
edit distance between these two words is 3 . We implemented a text sequence-
based code text similarity based on edit distance Code Text Similarity
(codeTextSim), defined as follows:

$\displaystyle
codeTextSim=1-\frac{editDistance(code_{t},code_{t-1})}{max(len(code_{t}),len(code_{t-1}))}$

where $len$ denotes the length of the code sequence, and if the edit distance
between two codes is 0, then their similarity is $codeTextSim=1.0$, which
means there is no difference between the two codes. If the action executed by
the current state model yields $code_{t}$ that does not change relative to the
$code_{t-1}$ of the previous state, then their $codeTextSim=0$. We give it a
negative penalty of $clone_{R}*codeTextSim$ (Line 4-6 in Algorithm 1). This is
designed to avoid the rewards in the environment being too sparse, to help
improve their learning efficiency and converge as quickly as possible [48].
since there is no limit to the amount of garbage code that can be inserted. To
control the code complexity, we use $Op13_{count}$ to count the number of
times op13 is used in the current round and give an additional negative
penalty $Op13_{penality}*Op13_{penality}$ (Line 7-10 in Algorithm 1) if the
action selected by the current agent is op13. In our implementation, we set
$nclone_{R}$, $clone_{R}$, and $Op13_{penalty}$ to 10, 0.5, and 0.5
empirically.

####  5.2.3 state

In DRL state represents the current state of the environment. In our model,
the transformation code obtained from the current action represents our
current state, which can be represented by the encoding vector of the code.
For a given source code we convert it into a sequence of texts sequence and
then encode it with a bidirectional LSTM model, which is the same as the clone
detection model mentioned in § 5.2.2.

##  6 Evaluation

In this section, we aim to investigate the following four research questions
(RQs) through the experimental evaluation:

  * •

RQ1: How effective are the different transformation strategies? How robustness
are the existing ML-based detectors in detecting the semantic clones generated
by CloneGen?

  * •

RQ2: How effective is our proposed DRLSG when detection results are available?
Can the ML-based detectors be enhanced by adversarial training with CloneGen?

  * •

RQ3: How effective are different types of atomic transformation operators?

  * •

RQ4: How accurate are the traditional clone detectors in detecting the
semantic clones produced by CloneGen?

###  6.1 Implementation and experimental setup

####  6.1.1 Datasets for CloneGen

In our evaluation, we use OJClone [21], a widely used database in source code
study [15, 16, 17, 21, 49, 50]. OJClone consists of 104 folders, each of which
contains 500 solutions (clones) to the same problem. The code from each
OJClone folder to form an initial dataset $D_{I}$, and apply the four
strategies (RS, GA, MCMC and DRLSG) to $D_{I}$ to construct four new datasets,
denoted as $D_{RS}$, $D_{GA}$, $D_{MCMC}$ and $D_{DRL}$, respectively.

Table III: The code generation time Time |  RS |  GA |  MCMC |  DRLSG
---|---|---|---|---
T(h) |  0.88 |  4.33 |  20.70 |  168

Tab. III shows the time consumed to transform 52,000 source code snippets in
the OJClone dataset by four transformation strategies. For each code snippet
in the 52,000, we apply the four different strategies to generate code pairs.
Notably, the RS strategy generates one code variant for each snippet, while
the other three strategies would generate many clone candidates and then use
the corresponding optimization goal to retain the best one. Finally, we have
the same size for these generated datasets:
$|D_{I}|=|D_{RS}|=|D_{GA}|=|D_{MCMC}|=|D_{DRL}|.$

The RS strategy takes only 0.88 hours, which is the fastest. The GA and MCMC
strategies need to do some code syntax analysis when transforming the code, so
they are slower than the RS strategy. The DRLSG strategy requires an ML-based
encoder to encode the source code and an ML-based detector to perform
similarity analysis, and only one operator is selected for each
transformation, so it is much slower.

####  6.1.2 Assessed Clone Detectors

There are many ML-based C++ source code clone detectors, including [15, 50,
16, 51, 50, 17, 49, 21, 52, 53] etc. However, some of them are not open
source, and some others have implementation issues when handling our dataset
(e.g., FCDetector [15]) . Finally, we adopt two open-source detectors ASTNN
[16] and TBCCD [17]. We also apply the TextLSTM [22] model on the OJClone
dataset. In the training/testing steps, we follow the guidelines provided in
their GitHub pages, and use the suggested parameters in their papers [16, 17]
to make fair comparisons. Here, TextLSTM is a model with a text embedding size
of 300 and a BiLSTM hidden layer size of 256. During the training process we
divided the dataset into training, validation, and test sets according to 80%,
10%, and 10%, and we used the Adam optimizer with a learning rate of 0.001 to
train 20 epochs and save the model with the best F1 during the training. The
above hyperparameters are empirically determined according to our experiments.

The detailed results are shown in Tab. IV, ASTNN and TBCCD are tested by our
replication. They both perform well on OJClone with $F1$ greater than 0.96.
OJClone has a big difference and belongs to type IV clone, which means that
the existing ML-based clone detectors have achieved good results, here the
TextLSTM $F1$ (0.991) is the best. Tab. V summarizes the time spent on setting
up the three ML-based detectors. TextLSTM spends the least time on data pre-
processing and ASTNN spends the least time on training and testing. TBCCD
takes the maximum time, about 1.38 hours, in pre-processing and 52 hours in
training and testing.

Table IV: Detection accuracy of the ML-based detectors on OJClone Tools |  P |  R |  F1
---|---|---|---
TextLSTM |  0.991 |  0.991 |  0.991
ASTNN |  0.996 |  0.960 |  0.977
TBCCD |  0.987 |  0.994 |  0.990
Table V: Time consumption of the ML-based clone detectors Tools |  Pre-processing(s) |  Training & Testing(s)
---|---|---
TextLSTM |  656 |  21963
ASTNN |  2412 |  7419
TBCCD |  4991 |  187467

####  6.1.3 Baseline Transformation Strategies

As introduced in §4.3, the search problem can be treated as a combinatorial
optimization problem. Thus, we may achieve different solutions by exploring
various optimization algorithms. In this paper, we also compare our proposed
DRLSG with the commonly-used heuristic strategies such as RS, GA, and MCMC. We
have derived the parameters for GA from the related work of [35, 36, 38]. For
MCMC, we have referblack to [34, 54] for the parameter setup.

####  6.1.4 Evaluation Metrics

After obtaining the four new datasets, we feed them to clone detectors under
test. Notably, to evaluate the robustness of the ML models inside the
detectors, the instances in our dataset have two types of labels: clone and
non-clone. For example, in the generated dataset $D_{RS}$, it consists of
52,000 clone pairs (each one from the original $D_{I}$ and the other one
generated by the RS strategy) and also 52,000 non-clone pairs (code pairs from
different folders transformed after the RS strategy).

We use Precision ($P$), Recall ($R$) and F1-Measure ($F_{1}$) Score to measure
the performance of the ML-based detector. Let $TP$ pblackict positive class as
positive, $FN$ pblackict positive class as negative, $FP$ pblackict negative
class as positive, and $TN$ pblackict negative class as negative, we compute
$P$, $R$, and $F_{1}$ as follows:

$P=\frac{TP}{TP+FP}\quad R=\frac{TP}{TP+FN}\quad F_{1}=\frac{2PR}{P+R}$ (6)

We use Recall (R) to measure the performance of traditional tools on detecting
code clones. Recall is an evaluation indicator commonly used by these
detectors (e.g., [55, 10]).

####  6.1.5 Environment

We conduct all the experiments on an AMAX computing server. It has two 2.1GHz
24-core CPUs, four NVIDIA GeForce RTX 3090 GPUs, and 384G memory.

###  6.2 RQ1: ML-based Detectors vs. CloneGen

In this section, we answer the RQ1, the effectiveness of CloneGen on bypassing
the ML-based clone detectors. Towards this goal, we use the initial datasets
$D_{I}$ as the training dataset for three assessed detectors. Then, for each
different strategy, we use the corresponding generated dataset
($D_{RS},D_{GA},D_{MCMC},D_{DRL}$) as the testing dataset.

Table VI: Results of the ML-based detectors in detecting clone pairs generated by CloneGen | TextLSTM | ASTNN | TBCCD
---|---|---|---
TestData | P | R | F1 | P | R | F1 | P | R | F1
$D_{RS}$ | 0.891 | 0.882 | 0.882 | 0.803 | 0.721 | 0.701 | 0.929 | 0.855 | 0.891
$D_{GA}$ | 0.713 | 0.679 | 0.666 | 0.770 | 0.641 | 0.592 | 0.822 | 0.671 | 0.739
$D_{MCMC}$ |  0.888 | 0.878 | 0.877 | 0.800 | 0.703 | 0.676 | 0.873 | 0.947 | 0.908
$D_{DRL}$ | 0.607 | 0.558 | 0.502 | 0.739 | 0.599 | 0.530 | 0.854 | 0.871 | 0.863

Next, we evaluate the robustness of these detectors against the code pairs
generated by CloneGen. Tab. VI shows the accuracy of the three detectors.
Generally, these ML-based detectors have varying accuracy regarding the four
transformation strategies.

TextLSTM directly converts the code into a sequence of texts, and then feeds
the code into an LSTM neural network to obtain the embedding vector of the
code, and then feeds the vector into a shallow feedforward neural network to
make a binary classification judgment, TextLSTM has the best clone detection
performance on the $D_{I}$ with an $F_{1}$ of 0.991 in Tab. IV. The $F_{1}$ of
TextLSTM ranges from 0.502 to 0.882 for four different strategies, all of
which affect TextLSTM compablack to the $F_{1}$ on the original dataset
(0.991). Among the four strategies, DRLSG (0.502) is the best in bypassing
TextLSTM detection, while RS (0.882) is the worst, indicating that random
transformations are more easily detected by TextLSTM.

ASTNN is a neural network built upon the _AST_ of a program. The _$F_{1}$_ of
ASTNN ranges from 0.530 to 0.701. In all four code transformation strategies,
the DRLSG strategy performs the best and the RS strategy performs the worst.
The result shows that different strategies can extensively bypass the _AST_
-based detection in ASTNN.

TBCCD uses structural _AST_ and token lexical information to generate a tree-
based convolutional neural network. According to Tab. VI, TBCCD has better
robustness than ASTNN and TextLSTM, with an average _$F_{1}$_ value of 0.850.
TBCCD performs best against MCMC with an _$F_{1}$_ of 0.908, indicating that
TBCCD is relatively insensitive to MCMC-guided transformation. The code clone
pairs generated from the GA strategy achieve _$F_{1}$_ =0.739 on TBCCD,
followed by DRLSG (0.863) and RS (0.891). This result indicates that the token
information increases the resilience of ML-based detectors against code
transformation.

In summary, from Tab. VI we observe that the pure _Text_ -based detector
(TextLSTM) can be easily bypassed with a high possibility. The models based on
hybrid abstractions of source code do achieve better resilience, especially
the TBCCD model which relies on both _Token_ and _AST_. From the CloneGen
perspective, the DRLSG strategy has shown the best effectiveness since it
performs best in testing TextLSTM and ASTNN.

Now, we answer the RQ1: the code pairs generated by CloneGen can effectively
bypass the detection of the state-of-the-art ML-based detectors, sharply
dropping _$F_{1}$_ of these detectors from 90+% to as low as 50%-70% in many
cases. TextLSTM, being most efficient, is the most fragile one with a low
_$F_{1}$_ of 0.421, TBCCD has the best robustness against CloneGen, but it
relies on very costly pre-processing and training. Last, ASTNN seems to strike
a balance in efficiency and robustness, as clone detection is just one of the
applications ASTNN supports.

###  6.3 RQ2: Adversarial Training with CloneGen

In this section, we try to answer the RQ2 with the experimental results. That
is, whether or not augmenting the training of ML-based detectors with
adversarial samples can defend CloneGen. The answer to RQ1 reveals the
robustness issues of the ML-based detectors. A common idea of reinforcing such
detectors is to fuse the spear into the shield, which means we can convert the
code clone pairs from CloneGen to be adversarial samples to re-train the ML
models.

Table VII: Results of the ML-based detectors with adversarial training in detecting clone pairs generated by CloneGen | TextLSTM | ASTNN | TBCCD
---|---|---|---
TestData | P | R | F1 | P | R | F1 | P | R | F1
$D_{I}$ | 0.995 | 0.995 | 0.995 | 0.994 | 0.965 | 0.979 | 0.981 | 0.984 | 0.983
$D_{RS}$ | 0.989 | 0.989 | 0.989 | 0.922 |  0.920 | 0.920 | 0.948 | 0.974 | 0.961
$D_{GA}$ | 0.954 | 0.952 | 0.952 | 0.891 | 0.880 | 0.879 | 0.928 | 0.971 | 0.949
$D_{MCMC}$ | 0.989 | 0.989 | 0.989 | 0.901 |  0.897 | 0.897 | 0.921 | 0.976 | 0.961
$D_{DRL}$ | 0.943 | 0.941 | 0.941 | 0.881 | 0.868 | 0.867 | 0.903 | 0.842 | 0.872

It is believed that training data significantly affects the performance of
deep learning models [19]. In general, the more complete the training data is,
the better performance the model achieves. Towards this goal, we enhance the
original dataset $D_{I}$ with the generated adversarial samples by four
different strategies. Consequently, we use the following datasets as the
training dataset: $D_{I}$\+ 25%$D_{RS}^{\prime}$\+
25%$D_{GA}^{\prime}$+25%$D_{MCMC}^{\prime}$+25%$D_{DRL}^{\prime}$. Here,
$D_{RS}^{\prime}$, $D_{GA}^{\prime}$, $D_{MCMC}^{\prime}$ and
$D_{DRL}^{\prime}$ are the new generated datasets by applying the four
different strategies on $D_{I}$ again (
$|D_{I}|=|D_{RS}^{\prime}|=|D_{GA}^{\prime}|=|D_{MCMC}^{\prime}|=|D_{DRL}^{\prime}|$).
Then, we use the following datasets as the testing dataset
($D_{RS},D_{GA},D_{MCMC},D_{DRL}$), which are the same as those used in §6.2.
Due to randomness of these strategies, the new generated datasets (e.g.,
$D_{RS}^{\prime}$) will not be identical to the testing datasets (e.g.,
$D_{RS}$). We re-train the models of the ML-based detectors without altering
any parameters.

Figure 5: F-measure before and after adversarial training

We also re-generate the $P$,$R$,$F_{1}$ values of each detector against the
transformation strategies in Tab. VII. For example, the row $D_{I}$ in Tab.
VII represents the accuracy of the retained models on the test dataset
$D_{I}$. Compablack with the row $D_{I}$ in Tab. IV, for TextLSTM, the
adversarial learning improves $P$, $R$, $F_{1}$ from 0.991 to 0.995. For
ASTNN, adversarial training slightly improves its accuracy, increasing $F_{1}$
from 0.977 to 0.979. For TBCCD, the new training results in a slight decrease
in $P$ and $F1$ to 0.981 and 0.983, $R$ slight increase to 0.984. The results
are reasonable, as the adversarial samples are quite different from the
original samples. Besides, the accuracy in Tab. IV is very high, we cannot
expect much improvement via the adversarial training.

Table VIII: The effectiveness of the transformation operator. | TextLSTM | ASTNN | TBCCD
---|---|---|---
| Original | Adversial | Original | Adversial | Original | Adversial
TestData | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1
$D_{I}$ | 0.991 | 0.991 | 0.991 | 0.995 | 0.995 | 0.995 | 0.996 | 0.960 | 0.977 | 0.994 | 0.965 | 0.979 | 0.987 | 0.994 | 0.990 | 0.983 | 0.983 | 0.983
$D_{Sem}$ | 0.899 | 0.891 | 0.890 | 0.995 | 0.995 | 0.995 | 0.856 | 0.817 | 0.811 | 0.927 | 0.927 | 0.927 | 0.941 | 0.918 | 0.929 | 0.957 | 0.971 | 0.964
$D_{Obf}$ | 0.730 | 0.701 | 0.691 | 0.969 | 0.969 | 0.969 | 0.787 | 0.700 | 0.675 | 0.905 | 0.901 | 0.901 | 0.864 | 0.856 | 0.860 | 0.940 | 0.989 | 0.964

Regarding the effectiveness of different strategies in escaping from the
detection, the dataset of clone pairs generated by the DRLSG strategy (i.e.,
$D_{DRL}$) achieves the worst detection accuracy among the last four rows in
Tab. VII — this result clearly shows clone pairs generated by the DRLSG
strategy are least detectable, and at least 13% of its generated clone pairs
cannot be detected by ASTNN and TBCCD. On the other side, the RS strategy
(i.e., $D_{RS}$) seems to be the least effective among the four strategies,
generating the most detectable clone pairs and resulting in high detection
accuracy. Last, the strategies GA (i.e., $D_{GA}$) and MCMC (i.e., $D_{MCMC}$)
show similar effectiveness, achieving the accuracy somewhere in between
$D_{DRL}$ and $D_{RS}$.

Regarding the robustness of different ML-based detectors in capturing various
generated clones, we find that the accuracy of these detectors is generally
satisfactory after adversarial training. As shown in Fig. 5, _in general,
adversarial training improves the robustness of these ML-based detectors by
increasing their $P$,$R$,$F_{1}$ values_. To be specific, the $F_{1}$ value of
TextLSTM has improved by 0.236 on average among all the strategies. In the
best case, it increase the $F_{1}$ by 0.439 on the $D_{DRL}$ dataset. For
ASTNN, the average increase of $F_{1}$ is 0.266, and it achieves a maximum
increase of 0.337 on the $D_{DRL}$ dataset. The last detector, TBCCD, and it
achieves an increase of only 0.085 on average, maximum increase of 0.210 on
the $D_{GA}$ dataset.

Now, we answer the RQ2: after the adversarial training with samples from
CloneGen, the $F_{1}$ values for the ML-based clone detectors _significantly_
increase, indicating that the adversarial training has enhanced the robustness
of the ML-based detectors. Meanwhile, the DRLSG strategy has exhibited the
best effectiveness in generating undetectable clones as it makes TextLSTM,
ASTNN, and TBCCD achieve the lowest accuracy among the four strategies.

Table IX: The _Recall_ values of traditional clone detectors TestData | SourcererCC | NiCad | CCAligner | Deckard
---|---|---|---|---
$D_{RS}$ | 0.006 | 0.027 | 0.100 | 0.110
$D_{GA}$ | 0.004 | 0.026 | 0.076 | 0.101
$D_{MCMC}$ | 0.008 | 0.046 | 0.083 | 0.100
$D_{DRL}$ | 0.001 | 0.027 | 0.070 | 0.099

###  6.4 RQ3: Effectiveness of Transformation Operators

In this section, we answer the RQ3 about the effectiveness of these atomic
transformation operators. Different from the previous experiments using all
operators, we apply and assess these operators group by group. In particular,
we divide our operations into two groups [26]: (1) those highly-relevant to
semantic clones (Op1-ChRename, Op2-ChFor, Op3-ChWhile, Op4-ChDo,
Op5-ChIfElseIF, Op6-ChIf, Op7-ChSwitch, Op8-ChRelation, Op9-ChUnary,
Op10-ChIncrement, Op12-ChDefine and Op14-ChExchange), and (2) those of simple
obfuscations (Op13-ChAddJunk, Op11-Constant, Op15-ChDelete).

To explore the impact of these operations on the clone detectors, we generate
two new clone datasets: the clone dataset ($D_{Sem}$) that applies only the
first group of operators and the dataset ($D_{Obf}$) that applies only the
second group.  To eliminate possible side-effects of different transformation
strategies, we do not use any above heuristic strategies.  Inside, our method
is straightforward in that it aggressively sets all bits in the bit vectors to
be 1 for certain transformation operators, resulting in the complete set of
code transformations at all qualified code locations.

The column ’Original’ in Tab. VIII indicates that the model is trained on the
$D_{I}$ dataset, and the column ’Adversarial’ indicates that the model is
trained by adding adversarial samples ($D_{I}$\+ 25%$D_{RS}^{\prime}$\+
25%$D_{GA}^{\prime}$+25%$D_{MCMC}^{\prime}$+25%$D_{DRL}^{\prime}$). The
$D_{I}$ row in Tab. VIII shows the accuracy on the original dataset, and the
$D_{Sem}$, $D_{Obf}$ indicate the accuracy on the dataset generated by the two
types of transformation operations.

Table X: Time consumption of the traditional clone detectors Detector |  Processing Number |  Times(m)
---|---|---
SourcererCC |  104 |  118
NiCad |  104 |  0.16
CCAligner |  104 |  12
Deckard |  104 |  221

In general, the accuracy of the model is significantly affected by the two
groups of transformation operators — no matter on column ’Original’ or
’Adversarial’, the $F_{1}$ values of the second row ($D_{Sem}$) and third
($D_{Obf}$) are always decreased, in contrast with the first row ($D_{I}$).
Between the two different groups of transformation, obfuscation-like
transformations (e.g., $D_{Obf}$) are better in bypassing the detection of
TextLSTM, ASTNN, TBCCD, with average F1 values of 0.742 and 0.945 in
’Original’ training and ’Adversarial’ training, respectively. Besides,
transformations for semantic clones $D_{Sem}$ are also valid in escaping from
the ML-based detection, with the average F1 values of 0.877 and 0.962. Hence,
the experiments prove that the obfuscation transformation operators are in
general more effective in affecting the accuracy of the ML-based clone
detectors.

Now, we answer the RQ3: from the experimental results, both groups of
transformation operators are effective in generating clone pairs that can
escape from the ML-based clone detectors. For these two groups, obfuscation-
like transformation operators are more effective and lower more detection
accuracy of TextLSTM and ASTNN.

###  6.5 RQ4: Traditional Detectors vs. CloneGen

In this section, we answer the RQ4, which explores whether or not traditional
clone detectors can defend CloneGen. While ML-based detectors have achieved
desirable performance, traditional detectors are still widely used in
practice. According to the previous study [56], traditional clone detector
Deckard achieves a poor recall (0.05) on the original OJClone dataset and
SourcererCC obtains a reasonable recall (0.74) on the original OJClone
dataset.

To explore to what extent the cloned code from CloneGen may escape from
traditional detectors, we conduct a set of experiments with four open-source
detectors as SourcererCC [55], Deckard [11], CCAligner [10], NiCad [57]. Tab.
IX shows the experimental results under the four different strategies. Tab. X
lists only the detection time of the four detectors, as traditional clone
detectors do not require a pre-processing or training stage and could perform
clone detection directly. Notably, column ’Processing Number’ refers to the
number of threads we run each detector in parallel to speed up the detection.
In practice, we run 104 threads (the same as the number of folders in
OJClone). If not using parallel detection, the traditional detectors would
take up to days or even one week to finish the detection.

Traditional detectors have no embedded ML models. Instead, they detect upon
the recognition of suspicious clone patterns within the source code
representation like token [10, 55], text [57], tree [11], dependency graph
[12] and so on. We treat them as black boxes, which are fed with the set of
generated code clone pairs from CloneGen and output the "clones or not"
decision. Finally, we calculate the overall _Recall_ values for each detector.

Overall, CloneGen makes the majority of the traditional detectors expose low
_recall_ values, with an average value of 0.049 for $D_{DRL}$. _Besides, the
DRLSG strategy is more effective than other strategies in beating the
traditional detectors_ , since more code changes bring more code syntactic
differences. This means that, under the DRLSG strategy, CloneGen can quickly
generate many code clone pairs that can bypass these detectors with more than
a 90% success rate. We examine the detectors whose _recall_ values are below
0.10. SourcererCC is a token-based detector that has the lowest _recall_
(0.001) and can be easily defeated. NiCad uses flexible, pretty-printing, and
code normalization to accurately detect intentional clones. It has the second-
lowest _recall_ (0.026). CCAligner uses a combination of sliding windows and
hashes to detect large-gap type clones. Its _recall_ is 0.07. Deckard is a
tree-based clone detection tool with a 0.099 _recall_ value.

Now, we answer the RQ4: the traditional clone detectors have no resistance to
the clone pairs generated by CloneGen, especially to the clone pairs in
$D_{DRL}$. For the tree-based detector (i.e., Deckard) that is believed to be
more robust than token-based ones, its detection recall is also less than 10%
on the datasets CloneGen generates.

##  7 Discussion

###  7.1 Threats to Validity

Threats to internal validity come from the parameter setup for the traditional
and the ML-based detectors used in this paper. To address this issue, for the
traditional detectors, we use their default settings. Since traditional
detectors usually have few parameters to tune, their results are quite stable.
For the ML-based detectors, we use the same parameters as those reported in
their papers [17, 16]. We also fine-tune the unreported parameters and finally
make the trained models reproduce similar results as those reported in the
corresponding papers. Through this rigorous process, we believe that we have
conducted fair comparisons between our approach and all the baseline clone
detectors in this study.

Threats to external validity mainly come from two aspects. First, we just use
the OJClone C language dataset to evaluate the detectors, which is a widely-
used open-source benchmark for large-scale semantic clone detection.
Currently, we have only done evaluations on C/C++ programs, however, like
other high-level languages (e.g., Java) that share similar language features
(e.g., object-orientation), we believe the evaluation findings could also be
generalized to clone detection for other high-level languages. Second, we
evaluate only three ML-based detectors in this paper due to the tool
availability issue. In the future, we would like to support more ML-based
detectors (e.g., [50, 51] when they are publicly available) or even code
plagiarism tools such as Moss [58].

###  7.2 Impact of Transformation Operators

Table XI: The transformation operators and their impact on the four commonly-
used representations of the code

Operator | AST | CFG | PDG | Token
---|---|---|---|---
Op1-ChRename |  |  |  |
Op2-ChFor |  |  |  |
Op3-ChWhile |  |  |  |
Op4-ChDo |  |  |  |
Op5-ChIfElseIF |  |  |  |
Op6-ChIf |  |  |  |
Op7-ChSwitch |  |  |  |
Op8-ChRelation |  |  |  |
Op9-ChUnary |  |  |  |
Op10-ChIncrement |  |  |  |
Op11-ChConstant |  |  |  |
Op12-ChDefine |  |  |  |
Op13-ChAddJunk |  |  |  |
Op14-ChExchange |  |  |  |
Op15-ChDeleteC |  |  |  |

∗Note that we use the symbol “ ”to denote severe effects, “ ”to denote only
minor effects, and “ ”to denote no effects.

As shown in Tab. XI, we have analyzed the impact of 15 proposed transformation
operators on the four commonly-used representations of source code. The impact
could be categorized into three levels. Firstly, severe impact (denoted by )
means that the operator breaks the original structure of the representation,
while minor impact (denoted by ) means that it only changes the node
properties of the representation (e.g., changing one node in _AST_ or _CFG_).
Last, no impact (denoted by ) means that neither the properties nor the
structure of the representation is modified.

Token-based detectors are susceptible to all the changes bought by the
transformation operators, except Op1 (identifier renaming) and Op14 (statement
exchanging). Hence, token-based detectors can only detect Type I and Type II
clones, and our operators can easily evade the token-based detectors (e.g.,
SourcererCC [55], CCAligner [10], CCFinderX [59]). AST-based detectors (e.g.,
Deckard [11]) perform better than the token-based ones, but the AST structure
is not resilient to control- or data-flow changes made by operators such as
Op2 to Op14. Therefore, AST-based detectors are good at detecting Type I and
II clones and these detectors could be evaded by our operators. In contrast,
CFG- or PDG-based detectors (e.g., CCGraph [12]) are more resilient to the
control- or data-flow changes. Especially for CFG-based detectors, they are
more resilient to the transformation performed by Op8 to Op11 (e.g., changing
while to for-loop). However, the Op4, Op7, Op12, and Op13 would have a severe
impact on the four representations, as the transformations brought by these
operators belong to Type-IV clones (i.e., semantic clones).

###  7.3 Lightweight Code Transformation or Obfuscators?

In this study, we use transformation operators and strategies and implement
our framework CloneGen to perform the lightweight semantic-preserving
transformation. Software obfuscators [60, 34, 61, 62, 27] can also enable
equivalence transformations of source code. The reasons why we do not employ
existing obfuscators in this work are threefold: 1) defeating clone detection
is essentially a trade-off problem that strikes the balance between costs in
code transformation and benefits from evasion. Obfuscators are generally not
free of charge and comparatively time-consuming. Hence, we offer a lightweight
yet effective code transformation approach. 2) Obfuscation is often utilized
to protect the IP (Intellectual Property). Therefore, the code after
obfuscation often has poor readability and maintainability. For example, for
the code int i = 1;, after the encoding by the obfuscator [62], it will
become:

⬇

1 language=c++,

2 backgroundcolor=\color{white},

3 extendedchars=true,

4
basicstyle=\fontsize{8}{8}\linespread{0.8}\selectfont\ttfamily,%\footnotesize\ttfamily,

5 %basicstyle=\footnotesize,

6 numbers=none,

7 numberstyle=\tiny\color{gray},

8 numberstyle=\color{gray},

9 keywordstyle=\color{blue},

10 xleftmargin=.25in,

11 breaklines=true,

12 captionpos=b,

13 keepspaces=true,

14 stepnumber=1,

15 aboveskip=1mm,

16 belowskip=0.5mm]

17int o_8ffc9af5e5913588bc0b7705602caf02= (0x0000000000000002 +
0x0000000000000201 + 0x0000000000000801 - 0x0000000000000A03);

3) More importantly, small rather than complicated transformations are much
easier for algorithm developers to analyze and debug robustness issues. Hence,
simple yet effective transformations are always favorable to algorithm
developers.

##  8 Related Work

###  8.1 Code Clone Detection

Generally, existing clone detectors can be classified as textual-based, token-
based, structural-based code cloning detection approaches. The textual-based
methods [9, 57, 63] represent code fragments in the form of strings. If the
text contents of the two code fragments are similar, they are considered
clones. The approaches described in [4, 10, 18, 55, 59] represent source code
as a series of token sequences and use different similarity detection
algorithms on the token sequences to detect code clones. The approaches
described in [11, 16, 64, 65] detect code similarity by extracting the syntax
of the code to obtain the semantic features of the code. Recently, some
approaches [6, 51, 66] perform code clone detection by extracting semantic
code features, for example using hybrid features, such as CFGs and ASTs of a
program [15, 67, 68], or through learning-based approaches [15, 16, 17, 18,
49, 51, 65, 67, 69, 70]. Regarding the assessment of clone detectors,
BigCloneBench [71] provide a clone detection benchmark to evaluate the clone
detectors, and existing studies [13, 72, 73, 74, 23, 75] focus on evaluating
traditional detectors in certain aspects, and there is still a lack of studies
that systematically challenge and assess the robustness of the recent ML-based
clone detectors.

###  8.2 Code Mutation

Code mutations are often used in code testing. Mutation testing, which
generates a large number of mutants that are automatically embedded in the
code to exercise a target program to detect its bugs [76, 77, 78, 79].
Mutation testing can also be used to test the effectiveness of code clone
detectors. Roy et al. [57] identified and standardized potential clones, and
then used dynamic clustering to perform simple text-line comparisons of
potential clones. Roy et al. [31] proposed a mutation insertion method to test
code clones. The idea is to reinsert an artificial piece of code into a piece
of source code so that different types of code clone pairs can be artificially
forged and then tested against the target clone detectors. Their proposed tool
is a random transformation of the code, which may change the semantics of the
original code. Svajlenko et al. [80] presented a benchmark framework based on
mutation analysis, which evaluates the recall rate of clone detection tools
for different types of clones and the editing of specific types of clones does
not require human intervention. Unlike approaches [80, 31] that can transform
code but cannot guarantee semantic preservation, our approach always generates
semantic equivalent clones for robustness validation. Recently, Zhang et al.
[54] only used one transformation operator (renaming variable), which is
included in this work, to prove that some source code processing methods
(e.g., ASTNN and Token-based LSTM models) are not sound in the code
classification problem. In this paper, our approach proves that the ML-based
clone detectors are not sound enough in detecting code clones after simple yet
effective equivalent transformations.

###  8.3 Code Obfuscation

Equivalence transformations are also commonly used in code obfuscation.
Program obfuscation is a set of semantic-preserving program mutation
techniques. It is mainly used to hide the intent of a program or to protect
the intellectual property of software before its release. Liu et al. [34]
proposed a language-model-based obfuscation framework. It makes code
refactoring tools like JSNice [81] more difficult to refactor a program.
Breanna et al. [35] presented Mossad, a method for making code plagiarism
tools by inserting junk code, which effectively defeats theft detectors such
as Moss [58]. Schulze et al [82] proposed to apply code obfuscations to
evaluate the robustness of some traditional clone detectors. They applied a
few code obfuscations semi-automatically to source code and did not consider
strategies to guide code mutation. The goal of our work is to conduct a simple
yet effective transformation to generate semantic clones to evade both
learning-based and traditional clone detectors. Rather than applying a heavy-
weight transformation (encoding [62], CFG flatten [27] or other compiler
optimizations [36]), our lightweight approach makes it easier for developers
to quickly discover and locate robustness issues in a clone detector.

##  9 Conclusion

This paper presents CloneGen, a lightweight yet effective code transformation
framework that can assess the robustness of ML-based clone detectors by
automatically generating clone pairs. several state-of-the-art ML-based and
traditional clone detectors. The experimental results show that our
lightweight transformations are effective in evaluating the robustness of
clone detectors and can significantly reduce the performance of three recent
ML-based detectors, i.e., ASTNN, TBCCD, TextLSTM. Our study reveals the
robustness implications of the machine learning-based clone detectors, which
calls for more robust and effective methods for data collection and model
training. One possible solution is to design a hybrid source code
representation to improve the capability of existing ML-based detectors. Our
source code and experimental data are publicly available at
https://github.com/CloneGen/CLONEGEN.

## References

  * [1] A. Mockus, “Large-scale code reuse in open source software,” in _First International Workshop on Emerging Trends in FLOSS Research and Development_. Minneapolis, MN, USA: IEEE, 2007, pp. 7 – 7.
  * [2] C. Kapser and M. W. Godfrey, “Cloning considered harmful" considered harmful: patterns of cloning in software,” _Empirical Software Engineering_ , vol. 13, no. 6, pp. 645–692, 2008.
  * [3] B. Laguë, D. Proulx, J. Mayrand, E. Merlo, and J. P. Hudepohl, “Assessing the benefits of incorporating function clone detection in a development process,” in _1997 International Conference on Software Maintenance_. Bari, Italy, Italy: IEEE, 1997, pp. 314–321.
  * [4] Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “Cp-miner: Finding copy-paste and related bugs in large-scale software code.” _IEEE Trans. Software Eng._ , vol. 32, no. 3, pp. 176–192, 2006.
  * [5] A. Alex. (2017) Moss, a system for detecting software plagiarism. [Online]. Available: https://theory.stanford.edu/~aiken/moss/
  * [6] C. Liu, C. Chen, J. Han, and P. S. Yu, “Gplag: detection of software plagiarism by program dependence graph analysis,” in _Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. Philadelphia, PA, USA: ACM, 2006, pp. 872–881.
  * [7] X. Wang, Y. chan Jhi, S. Zhu, and P. Liu, “Behavior based software theft detection,” in _Proceedings of the 2009 ACM Conference on Computer and Communications Security_. Chicago, Illinois, USA: ACM, 2009, pp. 280–290.
  * [8] J. F. Islam, M. Mondal, and C. K. Roy, “Bug replication in code clones: An empirical study,” in _IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering_ , K. Kontogiannis, F. Khomh, A. Chatzigeorgiou, M. Fokaefs, and M. Zhou, Eds. Suita, Japan: IEEE, 2016, pp. 68–78.
  * [9] S. Lee and I. Jeong, “Sdd: high performance code clone detection system for large scale source code,” in _OOPSLA_. San Diego, CA, USA: ACM, 2005, pp. 140–141.
  * [10] P. Wang, J. Svajlenko, Y. Wu, Y. Xu, and C. K. Roy, “Ccaligner: a token based large-gap clone detector,” in _Proceedings of the 40th International Conference on Software Engineering_ , M. Chaudron, I. Crnkovic, M. Chechik, and M. Harman, Eds. Gothenburg, Sweden: ACM, 2018, pp. 1066–1077.
  * [11] L. Jiang, G. Misherghi, Z. Su, and S. Glondu, “DECKARD: scalable and accurate tree-based detection of code clones,” in _29th International Conference on Software Engineering_. Minneapolis, MN, USA: IEEE Computer Society, 2007, pp. 96–105.
  * [12] Y. Zou, B. Ban, Y. Xue, and Y. Xu, “Ccgraph: a pdg-based code clone detector with approximate graph matching,” in _35th IEEE/ACM International Conference on Automated Software Engineering, ASE 2020, Melbourne, Australia, September 21-25, 2020_. Melbourne, Australia: IEEE, 2020, pp. 931–942.
  * [13] C. K. Roy, J. R. Cordy, and R. Koschke, “Comparison and evaluation of code clone detection techniques and tools: A qualitative approach,” _Science of computer programming_ , vol. 74, no. 7, pp. 470–495, 2009.
  * [14] A. Walker, T. Cerny, and E. Song, “Open-source tools and benchmarks for code-clone detection: past, present, and future trends,” _ACM SIGAPP Applied Computing Review_ , vol. 19, no. 4, pp. 28–39, 2020.
  * [15] C. Fang, Z. Liu, Y. Shi, J. Huang, and Q. Shi, “Functional code clone detection with syntax and semantics fusion learning,” in _ISSTA ’20: 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , S. Khurshid and C. S. Pasareanu, Eds. New YorkNYUnited States: ACM, 2020, pp. 516–527.
  * [16] J. Zhang, X. Wang, H. Zhang, H. Sun, K. Wang, and X. Liu, “A novel neural source code representation based on abstract syntax tree,” in _Proceedings of the 41st International Conference on Software Engineering_. Montreal, QC, Canada: ACM/IEEE, 2019, pp. 783–794.
  * [17] H. Yu, W. Lam, L. Chen, G. Li, T. Xie, and Q. Wang, “Neural detection of semantic code clones via tree-based convolution,” in _Proceedings of the 27th International Conference on Program Comprehension_ , Y. Guéhéneuc, F. Khomh, and F. Sarro, Eds. QC, Canada: IEEE / ACM, 2019, pp. 70–80.
  * [18] L. Li, H. Feng, W. Zhuang, N. Meng, and B. G. Ryder, “Cclearner: A deep learning-based clone detection approach,” in _2017 IEEE International Conference on Software Maintenance and Evolution_. Shanghai, China: IEEE, 2017, pp. 249–260.
  * [19] X. Zhu, C. Vondrick, C. C. Fowlkes, and D. Ramanan, “Do we need more training data?” _International Journal of Computer Vision_ , vol. 119, no. 1, pp. 76–92, 2016.
  * [20] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [21] L. Mou, G. Li, L. Zhang, T. Wang, and Z. Jin, “Convolutional neural networks over tree structures for programming language processing,” in _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence_ , D. Schuurmans and M. P. Wellman, Eds. Phoenix, Arizona, USA: AAAI Press, 2016, pp. 1287–1293.
  * [22] S. Xingjian, Z. Chen, H. Wang, D.-Y. Yeung, W.-K. Wong, and W.-c. Woo, “Convolutional lstm network: A machine learning approach for precipitation nowcasting,” in _Advances in neural information processing systems_ , 2015, pp. 802–810.
  * [23] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo, “Comparison and evaluation of clone detection tools,” _IEEE Trans. Software Eng._ , vol. 33, no. 9, pp. 577–591, 2007.
  * [24] A. Kovacheva, “Efficient code obfuscation for android,” in _International Conference on Advances in Information Technology_. Springer, 2013, pp. 104–119.
  * [25] K. Fukushima, S. Kiyomoto, T. Tanaka, and K. Sakurai, “Analysis of program obfuscation schemes with variable encoding technique,” _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , vol. 91, no. 1, pp. 316–329, 2008.
  * [26] H. Xu, Y. Zhou, Y. Kang, and M. R. Lyu, “On secure and usable program obfuscation: A survey,” _arXiv preprint arXiv:1710.01139_ , 2017.
  * [27] T. László and Á. Kiss, “Obfuscating c++ programs via control flow flattening,” _Annales Universitatis Scientarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Computatorica_ , vol. 30, no. 1, pp. 3–19, 2009.
  * [28] C. Wang, J. Hill, J. Knight, and J. Davidson, “Software tamper resistance: Obstructing static analysis of programs,” Technical Report CS-2000-12, University of Virginia, 12 2000, Tech. Rep., 2000.
  * [29] G. Petrovic and M. Ivankovic, “State of mutation testing at google,” in _Proceedings of the 40th International Conference on Software Engineering: Software Engineering in Practice, ICSE (SEIP) 2018, Gothenburg, Sweden, May 27 - June 03, 2018_ , F. Paulisch and J. Bosch, Eds. Gothenburg, Sweden: ACM, 2018, pp. 163–171.
  * [30] S. Danicic. (2007) Lava: A system for mutation testing of java programs. [Online]. Available: http://www.doc.gold.ac.uk/~mas01sd/mutants/index.html
  * [31] C. K. Roy and J. R. Cordy, “A mutation/injection-based automatic framework for evaluating code clone detection tools,” in _Second International Conference on Software Testing Verification and Validatio_. Denver, Colorado, USA: IEEE Computer Society, 2009, pp. 157–166.
  * [32] T. Bäck, _Evolutionary algorithms in theory and practice - evolution strategies, evolutionary programming, genetic algorithms_. New York,USA: Oxford University Press, 1996.
  * [33] M. Richey, “The evolution of markov chain monte carlo methods,” _Am. Math. Mon._ , vol. 117, no. 5, pp. 383–413, 2010.
  * [34] H. Liu, C. Sun, Z. Su, Y. Jiang, M. Gu, and J. Sun, “Stochastic optimization of program obfuscation,” in _Proceedings of the 39th International Conference on Software Engineering_. Buenos Aires, Argentina: IEEE, 2017, pp. 221–231.
  * [35] B. Devore-McDonald and E. D. Berger, “Mossad: defeating software plagiarism detection,” _Proceedings of the ACM on Programming Languages_ , vol. 4, no. OOPSLA, pp. 1–28, 2020.
  * [36] X. Ren, M. Ho, J. Ming, Y. Lei, and L. Li, “Unleashing the hidden power of compiler optimization on binary code difference: an empirical study,” in _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ , 2021, pp. 142–157.
  * [37] A. C. Florea and R. Andonie, “Weighted random search for hyperparameter optimization,” _International Journal of Computers, Communications & Control (IJCCC)_, vol. 14, no. 2, pp. 154–169, 2019.
  * [38] Z. Michalewicz, _Genetic algorithms+ data structures= evolution programs_. Springer Science & Business Media, 2013.
  * [39] G. Navarro, “A guided tour to approximate string matching,” _ACM computing surveys (CSUR)_ , vol. 33, no. 1, pp. 31–88, 2001.
  * [40] A. Hindle, E. Barr, M. Gabel, Z. Su, and P. Devanbu, “On the naturalness of software,” in _34th International Conference on Software Engineering_. Zurich, Switzerland: IEEE, 2012, pp. 837–847.
  * [41] C. Manning and H. Schutze, _Foundations of statistical natural language processing_. MIT press, 1999.
  * [42] S. Levine, C. Finn, T. Darrell, and P. Abbeel, “End-to-end training of deep visuomotor policies,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 1334–1373, 2016.
  * [43] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton _et al._ , “Mastering the game of go without human knowledge,” _nature_ , vol. 550, no. 7676, pp. 354–359, 2017.
  * [44] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [45] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot _et al._ , “Mastering the game of go with deep neural networks and tree search,” _nature_ , vol. 529, no. 7587, pp. 484–489, 2016.
  * [46] C. Szepesvári, “Algorithms for reinforcement learning,” _Synthesis lectures on artificial intelligence and machine learning_ , vol. 4, no. 1, pp. 1–103, 2010.
  * [47] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [48] A. Y. Ng, D. Harada, and S. Russell, “Policy invariance under reward transformations: Theory and application to reward shaping,” in _Icml_ , vol. 99, 1999, pp. 278–287.
  * [49] H. Wei and M. Li, “Positive and unlabeled learning for detecting software functional clones with adversarial training.” in _IJCAI_. Stockholm, Sweden: ijcai.org, 2018, pp. 2840–2846.
  * [50] Y.-Y. Zhang and M. Li, “Find me if you can: Deep software clone detection by exploiting the contest between the plagiarist and the detector,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33. Honolulu, Hawaii, USA: AAAI Press, 2019, pp. 5813–5820.
  * [51] G. Zhao and J. Huang, “Deepsim: deep learning code functional similarity,” in _Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. Lake Buena Vista, FL, USA: ACM, 2018, pp. 141–151.
  * [52] W. Wang, G. Li, S. Shen, X. Xia, and Z. Jin, “Modular tree network for source code representation learning,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 29, no. 4, pp. 1–23, 2020.
  * [53] L. Mou, G. Li, L. Zhang, T. Wang, and Z. Jin, “Convolutional neural networks over tree structures for programming language processing,” in _Thirtieth AAAI Conference on Artificial Intelligence_ , 2016.
  * [54] H. Zhang, Z. Li, G. Li, L. Ma, Y. Liu, and Z. Jin, “Generating adversarial examples for holding robustness of source code processing models,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 01, 2020, pp. 1169–1176.
  * [55] H. Sajnani, V. Saini, J. Svajlenko, C. K. Roy, and C. V. Lopes, “Sourcerercc: scaling code clone detection to big-code,” in _Proceedings of the 38th International Conference on Software Engineering_ , L. K. Dillon, W. Visser, and L. A. Williams, Eds. Austin, TX, USA: ACM, 2016, pp. 1157–1168.
  * [56] H. Wei and M. Li, “Supervised deep features for software functional clone detection by exploiting lexical and syntactical information in source code,” in _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence_. Melbourne, Australia: Morgan Kaufmann, 20017, pp. 3034–3040.
  * [57] C. K. Roy and J. R. Cordy, “Nicad: Accurate detection of near-miss intentional clones using flexible pretty-printing and code normalization,” in _The 16th IEEE International Conference on Program Comprehension_ , R. L. Krikhaar, R. Lämmel, and C. Verhoef, Eds. Amsterdam, The Netherlands: IEEE / ACM, 2008, pp. 172–181.
  * [58] S. Schleimer, D. S. Wilkerson, and A. Aiken, “Winnowing: local algorithms for document fingerprinting,” in _Proceedings of the 2003 ACM SIGMOD international conference on Management of data_. San Diego, California, USA: ACM, 2003, pp. 76–85.
  * [59] T. Kamiya, S. Kusumoto, and K. Inoue, “Ccfinder: a multilinguistic token-based code clone detection system for large scale source code,” _IEEE Trans. Software Eng._ , vol. 28, no. 7, pp. 654–670, 2002.
  * [60] A. Pawlowski, M. Contag, and T. Holz, “Probfuscation: an obfuscation approach using probabilistic control flows,” in _International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment_. San Sebastián, Spain: Springer, 2016, pp. 165–185.
  * [61] P. Wang, S. Wang, J. Ming, Y. Jiang, and D. Wu, “Translingual obfuscation,” in _2016 IEEE European Symposium on Security and Privacy (EuroS &P)_. Saarbrucken, Germany: IEEE, 2016, pp. 128–144.
  * [62] D. Picheta, “Code obfuscation for the c/c++ language,” _arXiv preprint arXiv:2003.03449_ , 2020.
  * [63] S. Kim, S. Woo, H. Lee, and H. Oh, “Vuddy: A scalable approach for vulnerable code clone discovery,” in _2017 IEEE Symposium on Security and Privacy (SP)_. San Jose, CA, USA: IEEE, 2017, pp. 595–614.
  * [64] I. D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier, “Clone detection using abstract syntax trees,” in _Proceedings. International Conference on Software Maintenance (Cat. No. 98CB36272)_. Bethesda, MD, USA, USA: IEEE, 1998, pp. 368–377.
  * [65] H. Wei and M. Li, “Supervised deep features for software functional clone detection by exploiting lexical and syntactical information in source code,” in _IJCAI_. Melbourne, VIC, Australia: Morgan Kaufmann, 2017, pp. 3034–3040.
  * [66] M. Wang, P. Wang, and Y. Xu, “Ccsharp: An efficient three-phase code clone detector using modified pdgs,” in _2017 24th Asia-Pacific Software Engineering Conference (APSEC)_. Nanjing, China: IEEE, 2017, pp. 100–109.
  * [67] A. Sheneamer and J. Kalita, “Semantic clone detection using machine learning,” in _2016 15th IEEE International Conference on Machine Learning and Applications_. Anaheim, CA, USA: IEEE, 2016, pp. 1024–1028.
  * [68] C. Ragkhitwetsagul, J. Krinke, and D. Clark, “A comparison of code similarity analysers,” _Empirical Software Engineering_ , vol. 23, no. 4, pp. 2464–2519, 2018.
  * [69] M. White, M. Tufano, C. Vendome, and D. Poshyvanyk, “Deep learning code fragments for code clone detection,” in _2016 31st IEEE/ACM International Conference on Automated Software Engineering (ASE)_. Singapore, Singapore: IEEE, 2016, pp. 87–98.
  * [70] W. Hua, Y. Sui, Y. Wan, G. Liu, and G. Xu, “Fcca: Hybrid code representation for functional clone detection using attention networks,” _IEEE Transactions on Reliability_ , 2020.
  * [71] J. Svajlenko and C. K. Roy, “Evaluating clone detection tools with bigclonebench,” in _2015 IEEE International Conference on Software Maintenance and Evolution (ICSME)_ , 2015.
  * [72] E. Burd and J. Bailey, “Evaluating clone detection tools for use during preventative maintenance,” in _Proceedings. Second IEEE International Workshop on Source Code Analysis and Manipulation_ , 2002, pp. 36–43.
  * [73] R. Tiarks, R. Koschke, and R. Falke, “An assessment of type-3 clones as detected by state-of-the-art tools,” in _2009 Ninth IEEE International Working Conference on Source Code Analysis and Manipulation_ , 2009, pp. 67–76.
  * [74] F. Van Rysselberghe and S. Demeyer, “Evaluating clone detection techniques from a refactoring perspective,” in _Proceedings. 19th International Conference on Automated Software Engineering, 2004._ , 2004, pp. 336–339.
  * [75] J. Svajlenko and C. K. Roy, “Evaluating modern clone detection tools,” in _2014 IEEE International Conference on Software Maintenance and Evolution_ , 2014, pp. 321–330.
  * [76] Y. Jia and M. Harman, “An analysis and survey of the development of mutation testing,” _IEEE Trans. Software Eng._ , vol. 37, no. 5, pp. 649–678, 2011\.
  * [77] X. Yao, M. Harman, and Y. Jia, “A study of equivalent and stubborn mutation operators using human analysis of equivalence,” in _36th International Conference on Software Engineering_. Hyderabad, India: ACM/IEEE, 2014, pp. 919–930.
  * [78] J. Zhang, L. Zhang, M. Harman, D. Hao, Y. Jia, and L. Zhang, “Predictive mutation testing,” _IEEE Trans. Software Eng._ , vol. 45, no. 9, pp. 898–918, 2019.
  * [79] P. McMinn, C. J. Wright, C. J. McCurdy, and G. M. Kapfhammer, “Automatic detection and removal of ineffective mutants for the mutation analysis of relational database schemas,” _IEEE Transactions on Software Engineering_ , vol. 45, no. 5, pp. 427–463, 2019.
  * [80] J. Svajlenko and C. Roy, “The mutation and injection framework: Evaluating clone detection tools with mutation analysis,” _IEEE Transactions on Software Engineering_ , vol. PP, no. 99, pp. 1–1, 2019.
  * [81] V. Raychev, M. Vechev, and A. Krause, “Predicting program properties from" big code",” _ACM SIGPLAN Notices_ , vol. 50, no. 1, pp. 111–124, 2015.
  * [82] S. Schulze and D. Meyer, “On the robustness of clone detection to code obfuscation,” in _2013 7th International Workshop on Software Clones (IWSC)_. San Francisco, CA, USA: IEEE, 2013, pp. 62–68.