# AndroClonium: Bytecode-Level Code Clone Detection for Obfuscated Android Apps

Ardalan Foroughipour, Natalia Stakhanova, Farzaneh Abazari, Bahman Sistany

<figure><img src="image_1.png" /></figure>

## To cite this version:

Ardalan Foroughipour, Natalia Stakhanova, Farzaneh Abazari, Bahman Sistany. AndroClonium: Bytecode-Level Code Clone Detection for Obfuscated Android Apps. 37th IFIP International Conference on ICT Systems Security and Privacy Protection (SEC), Jun 2022, Copenhagen, Denmark. pp.379-397, 10.1007/978-3-031-06975-8_22. hal-05319913

HAL Id: hal-05319913

https://inria.hal.science/hal-05319913v1

Submitted on 17 Oct 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# AndroClonium: Bytecode-Level Code Clone Detection for Obfuscated Android Apps

Ardalan Foroughipour¹(✉), Natalia Stakhanova¹(✉), Farzaneh Abazari¹, and Bahman Sistany²

¹ University of Saskatchewan, Saskatoon, Canada
{arf027,faa851}@usask.ca, natalia@cs.usask.ca

² University of Ottawa, Ottawa, Canada
bsistany@uottawa.ca

**Abstract.** Detecting code clones is essential for many security tasks, e.g., vulnerability detection, malware analysis, legacy software patching. In many of these security scenarios, source code is not available, leaving binary code analysis as the only option. Yet, evaluation of binary code is often exacerbated by the wide use of obfuscation. In this work, we propose an approach for obfuscation-resistant fine-grained detection of code clones in Android apps at the bytecode level. To mitigate inherent constraints of static analysis and to achieve obfuscation resistance, we partially simulate the execution of Android code, and abstract the resulting execution traces. We validate our approach's ability to detect different types of code clones on a set of 20 injected clones and explore its resistance against obfuscation on a set of 1085 obfuscated apps.

**Keywords:** Code clone · Obfuscation · Android · Smali code

## 1 Introduction

Software applications are no longer built from scratch. They are assembled from open source and third party code components, this phenomenon is commonly known as *code reuse* or *code cloning*. While code reuse is typically associated with legitimate software development, malware writers are no exception and reuse existing code and third-party components to expedite malware development. Establishing the presence of third-party code at the binary code level may facilitate efficient triage of unknown samples, accurate detection and understanding of malicious functionality. Besides malware detection and analysis, identification of code clones in binary code is an essential task for other security applications, e.g., for code attribution, vulnerability search, legacy software patching.

In spite of significant research efforts focused on binary code similarity detection in the recent years, this is still non-trivial task mainly due to the diversity of hardware architectures, software platforms and the wide use of code obfuscation. Code obfuscation has become a common approach for both legitimate
and malicious software to disguise its appearance, intent, and to protect it from reverse engineering and analysis techniques. The majority of the existing studies that focus on binary code similarity leverage static analysis methods, e.g., extracting function features from assembly code [10] and analyzing the control flow graph (CFG) [13]. Static analysis methods are fast but often fail to cope with more sophisticated cases of code reuse, i.e., the instances of reused code that are broken into small and non-contiguous pieces, reordered, and intertwined with other pieces of code. The wide use of obfuscation techniques also renders most of these existing static-analysis based approaches ineffective. On the other hand, current solutions that rely on dynamic analysis are difficult to automate. They tend to analyze an app as a black-box, and hence are not well-suited for fine-grained code clone detection.

In this work, we address these challenges and propose AndroClonium: an approach for obfuscation-resistant fine-grained detection of code clones in obfuscated Android apps. Since in security setting, source code is rarely available, we focus on detection of code clones through the analysis of Android binary code. More specifically, we disassemble the Android bytecode to the Smali format, which can be considered as an equivalent of the assembly language for Android bytecode. Our approach first disassembles the bytecode of an app to the Smali format and then simulates the execution of the Smali code to extract possible app execution traces. To analyze these traces, we employ program backward slicing to extract data-dependent instructions that bear semantic significance. Code slices further produce smaller code segments which are then analyzed for the potential code similarity. This approach allows us, even in presence of code obfuscation, to recognize syntactically similar code clones, referred to as *Type-3* clones in addition to some cases of syntactically different but semantically equivalent code clones, referred to as *Type-4* code clones.

We validate our approach on 20 manually injected code clone samples and investigate its the obfuscation resistance on 1085 open-source Android apps. Our approach achieved between 78% to 87% similarity between its findings before and after obfuscation was applied on 1085 apps. We further perform code clone detection among 1603 non-obfuscated apps collected from F-Droid market<fnref n="1" />. We compare the performance of our approach to another method-level clone detection tool called Nicad [19]. Although our approach for the most part agrees with Nicad, we observe that we are able to find significantly more code clones missed by Nicad. Finally, we investigate the applicability of our approach in detecting Android malware variants through the analysis of their code clones. Through the analysis of the binary's code clones, we identify unique code clones between different samples of a malware family that can be further used for detecting other variants of the malware family. Our approach was able to detect correctly 88% of apps based on the presence of code clones in their binary code. Our contributions in this work can be summarized as follows:

* We introduce an approach for the detection of non-contiguous code clones that can be employed both at method level and code slice level in obfuscated

<footnote n="1">¹ https://www.f-droid.org/.</footnote>
Android apps through analysis of their execution traces. To the best of our knowledge, this is the first work that offers detection of code clones in obfuscated Android apps.

* As an alternative to purely static or dynamic analysis approaches for analyzing Smali code, we have developed a Smali execution simulator to extract possible execution traces of an Android app. We offer our simulator and our dataset to the security community in an effort to facilitate research in this area<fnref n="2" />.

## 2 Background and Literature Review

Android apps are packaged and distributed in the `.apk` file format. Each `.apk` file, when decompressed, includes one or multiple `.dex` files that contain the logic of an app in the form of Dalvik bytecode. Earlier Android versions executed apps using the *Dalvik Virtual Machine* (DalvikVM) but from Android 5.0, DalvikVM was replaced by *Android-Runtime* environment (ART). Dalvik bytecode standard contains a small, high-level and object oriented instruction set. As a result, Dalvik instructions can be easily understood, modified and even in some cases, decompiled back to the original Java code. Due to the security implications of these, code optimization and obfuscation are commonly adopted to make analysis of the Android apps more challenging.

**Related Works:** Code clone detection is a well-studied problem that has been examined both at the source code level, usually for program comprehension or plagiarism detection, and at the binary code level for vulnerability analysis and malware detection. In the literature, code clones have been categorized into four types [20]: *Type-1*: code pieces that are textually identical except for white spaces, comments, or layout characteristics, *Type-2*: code pieces that are syntactically identical except for identifier names or literal values, *Type-3*: syntactically similar code pieces with minor differences at statement level that may differ by addition, removal, or modification of some statements, and *Type-4*: syntactically different but semantically identical code clones. The majority of the existing studies on source code clone detection employ text-based [19], token-based [17,20,21], tree-based [15] or graph-based [18] heuristics. For example, *Nicad* [19] is a text-based approach that uses normalization and LCS algorithm to detect code clones. The approaches proposed by *Kamiya et al.* [17] and *Duric et al.* [21] employ tokenized sequences. *Duric et al.* [21] leverage Running Karp-Rabin Greedy String Tiling (RKR-GST) algorithm, which involves tiling a string with matching substrings of another string and Winnoing algorithm for similarity comparison. *Yang et al.* [26] uses token-sequences for clone detection but also considers features such as lambda expressions, and anonymous classes. Another token-based code clone detection, *SourcererCC* [20] uses inverted-index and heuristics to improve scalability. An abstract syntax tree (AST)-based analysis is employed by *DECKARD* [15]. *Komondoor et al.* [18]

<footnote n="2">² https://cyberlab.usask.ca/publications.html.</footnote>
uses program dependence graphs (PDG) and the following program slicing to
find isomorphic sub-graphs and consequently detect duplicated code.

Detection of code clones in binary or byte code level has also been studied by researchers. At the function level, *Eschweiler et al.* [13] employed numerical and structural features for detection of code clones. *Ding et al.* [11] represented assembly codes as control flow graphs and detected clones by finding similar sub-graphs between functions. *Yang et al.* [27] proposed *Asteria*, a deep learning-based approach that learns semantic representation of binary functions by first decompiling the binary to source code and then extracting the source codes AST to find semantically similar functions. At the block level, *Yu et al.* [29] proposed a Java bytecode code clone detection tool based on instruction sequences and method calls as features to find code clones. Other studies have focused on finding semantically similar code in binaries. *Hu et al.* [14] proposed converting binaries to an intermediate representation and emulating selected codes with random values to extract semantic signatures. One major drawback of this approach is its limited code coverage since it relies on random values. To mitigate this problem, *Egele et al.* [12], proposed blanket execution, a dynamic analysis approach that performs repeated execution of binary functions using random values from the first un-executed instruction until every instruction has been executed at least once. Even though this solves the problem of code coverage, the approach still suffers from invalid executions.

In Android context, these approaches are not applicable since Android apps are developed in an event-oriented manner and rely heavily on user interactions which are major obstacle for efficient automated dynamic analysis. To detect code clones in Android apps, *Akram et al.* [2] proposed to analyze hashed n-grams extracted from the normalized decompiled code of .dex files. Other studies [3,9] explored code clone detection at application level and thus are not well suited for detection of fine-grade code clones between multiple applications. In this work, we address this concern and explore detection of code clones in a presence of obfuscation.

The categorization of obfuscation transformations were originally proposed
in a seminal work by Collberg at el. [8]. *Balachandran et al.* [5] expanded this
categorization by proposing several techniques specifically for Android apps, i.e.,
1) packed-switch construct, 2) try-catch construct, and 3) combination of the
last two techniques. Aonzo et al. [1] developed Obfuscapk, an obfuscation tool
for Android which supports a variety of obfuscation techniques such as layout
obfuscations, control-flow obfuscations, and string-encryption obfuscation.

While the obfuscation is common in legitimate and malicious apps, only a
few studies attempted to address obfuscation in Android setting, yet, none of
them focused specifically on clone detection. Wang et al. [23] and Bacci et al. [4]
proposed a machine learning based approaches to detect the obfuscators used
for obfuscating Android apps. Several studies explored deobfuscation of Android
apps. *Bichsel et al.* [6] introduced DeGuard, an approach for reversing layout
obfuscation of the program elements obfuscated with ProGuard. *Yoo et al.* [28]
introduced deobfuscation of string encryption, by dynamically execute Android
<figure><img src="image_4.png" /><figcaption>Fig. 1. The flow of the proposed approach</figcaption></figure>

apps on a modified Dalvik VM which captures the executed Dalvik instructions and the corresponding metadata which is then used to find the original values of obfuscated strings. Vos et al. [22] proposed ASTANA, that reverts obfuscated string literals to their original value by executing the string deobfuscation logic inserted by the obfuscation tool.

In summary, none of the existing code clone detection approaches consider code obfuscation.

# 3 Methodology

In this work, we leverage partial code execution to overcome challenges of purely static or dynamic approaches. Approaches that rely on static analysis do not perform well with obfuscated code due to uncertainties of predicting the run-time code behaviour. Dynamic analysis techniques although less affected by obfuscation, due to the semantic-preserving nature of code obfuscation, require generation of a sufficient number of valid inputs to achieve high code coverage. These challenges make the pure dynamic analysis not suitable for large code bases. In Android apps, this is exacerbated by relying heavily on user interactions with GUI. Thus, we propose a hybrid approach that partially executes Android bytecode to extract possible app execution traces. We simulate the execution of an Android app at Smali code level and therefore refer to this approach as Smali simulation. These obtained traces are then further analyzed to extract semantically significant parts of the code for detection of code clones. Figure 1 summarizes the flow of the proposed approach that follows four main steps: (1) Entry Point Extraction, (2) Execution simulation, (3) Execution trace analysis, and (4) Code clone detection.

## 3.1 Entry Point Extraction

Android apps unlike traditional programs do not contain a main method and are compromised of multiple entry points which are invoked by ART. Separating the entry point methods is beneficial for efficient simulation code. This approach allows to select relevant portions of code that would have been invoked during
an actual execution of an app, and effectively avoid unnecessary code simulation as Android apps often include residual and unused classes and APIs due to difference reasons such as obfuscation or inclusion of libraries.

Android apps consist of four key components as their building blocks, namely, Activities, Services, Broadcast receivers, and Content providers. These components can define and register methods that will act as the entry points to an Android app. We define app's *Entry Point Methods* as a set of methods in an Android app that are invoked by the Android framework during the execution of an app for performing a task. Android entry point methods can be categorized into 3 broad groups:

1. Methods defined by the Android app components, which are overridden by the developer and subsequently invoked by the Android system on certain events, e.g., the `Activity->onCreate(Bundle)` method.

2. Methods defined as event handlers which are registered into the system during execution of an application, e.g., `View.On ClickListener->Click(View)`.

3. Methods declared as the click event handlers in layout files, XML files that define the structure of a user interface of an Activity. For example, the element `<Button>` in a layout file can declare an `android:Click` property which should be invoked when a Click event happens.

Extraction of the entry points from the group (1) is trivial as they correspond to an Activity or a Service declared in app's `AndroidManifest.xml` file. Yet, locating the entry points from groups (2) and (3) is challenging, since they represent callbacks that are dynamically registered by the code of an app. We design a heuristic to extract these entry points through a static analysis of the app's Smali code and the corresponding layout files. We use a list of Android methods that if overridden by an app may act as entry points. The list was compiled through an analysis of previous studies that have extracted some of these methods [7,24]. We parse Smali code to detect if any of the methods in our list are overridden. For the overridden methods from the group (1) entry points, we check if their declaring component is registered in the `AndroidManifest.xml` file. For groups (2) and (3), we take a more conservative approach. We include all methods that override methods from our list of entry point methods and methods defined as the Click handlers in a layout file (if a method in an app matches it).

## 3.2 Execution Simulation

Once all app's entry points are obtained, the Smali simulation is performed for each entry-point method. Theoretically, any Smali instruction can be emulated at the application layer using the dynamic features of the ART such as reflection or method-handles. In practice, however, this requires correct values for the execution of these instructions. Yet, we observed that to determine code similarity, it is often unnecessary to know all precise values in real execution. Thus, we perform partial execution on Smali code by selectively executing instructions and leaving some unexecuted.
For modeling values corresponding to unexecuted instructions, we introduce the notion of *ambiguous value* which denotes any possible value in the execution. Our simulator takes a method's Smali code with its arguments as input and simulates its execution with the maximum threshold of 10 executions per method. In our currently implemented prototype, we use ambiguous values for all the input values needed to execute a method. While this may reduce the accuracy of simulation in some cases, we show empirically that this is sufficient to detect code clones. To realize our vision of such Smali simulator two challenges have to be addressed: 1) creating and loading a class into the ART, mirroring the types defined in the Smali files. 2) separating the methods that our simulator is allowed to execute from the methods that should not be invoked during the execution.

**Mirror Class Generation and Loading.** One major challenge in Smali code simulation is modelling user-defined classes. These classes declared in the .smali files need to be loaded into the ART as if they were loaded during an actual execution of an application. To solve this issue, we use the ByteBuddy framework [25], a dynamic Java class generator. With the help of ByteBuddy framework, we can dynamically create a class to ART that mirrors the Smali class. With this approach, the Smali class is loaded to the ART engine which is then treated as a regular Java class.

**Selecting Methods for Partial Execution.** The logic of partial execution is simple, if any method invocation that can return an unpredictable or invalid result should not be executed. For example, `Context->getPackageName()` API if executed in our custom execution environment, incorrectly returns the name of the simulator and not the package name of an app under analysis. Similarly, method invocations that perform I/O operations may produce unexpected results. To support partial execution, we separate methods bundled with ART into *safe* and *unsafe*. A method that can be correctly executed in the context of the simulator is considered to be *safe*. Similarly, we define a class as *safe* if it only includes *safe* methods. When an *unsafe* method is invoked, its return value is modelled using an *ambiguous value*. Furthermore, all mutable objects passed to this *unsafe* method are also replaced with *ambiguous values*.

To reduce the propagation of ambiguous values in our simulation, we also differentiate *pure* methods, methods that are functionally pure and do not change the state of passed arguments, i.e., do not assign a new value to any field or invoke methods which would change state of an object such as `ArrayList.add()` method. Hence, any invocation of a *pure* method with ambiguous value stops its propagation on mutable passed arguments. Other instruction that operates on an ambiguous value also usually results in an ambiguous value. If an instruction needs to branch on an ambiguous value, an execution branch path is chosen at random.

To separate safe and unsafe classes and methods from classes bundled with the ART, we create an initial set of safe classes manually. Based on this initial
set, we automatically extracts all other safe classes/methods bundled in Android Runtime that only use methods that previously have been marked as safe. To account for inheritance and overridden methods, we divide safe methods into two groups:

1) *static-safe methods*, i.e., static methods where all arguments are either from a static-safe class or an instance-safe class and all the invoked methods inside the method body are safe.

2) *instance-safe methods* i.e., methods with arguments including its reference object coming from an instance-safe class and with only all safe method invocations inside its body. In this definition, we include constructors as methods. Furthermore, a class is considered instance-safe if all of the methods it defines are safe, its super class is instance-safe and all of its child types are also instance-safe.

For extracting pure methods, similar to the safe methods, we start by manually creating a set of pure methods, and then recursively traverse Android Runtime code to extract other pure methods.

## 3.3 Execution Trace Analysis

For a given app, the simulator generates its possible execution traces (as an example see Fig. 2). These raw execution traces are further analyzed to extract semantically significant parts of code for detection of clones. This analysis consists of the following steps:

**Nested Execution Trace Extraction.** During simulation stage, all callee's invocations (and their corresponding instructions) are embedded in the caller execution trace. Hence, as we perform execution trace flattening in the next steps, it appears as if all instructions were executed by caller. In order to perform code clone detection on each method, we need to separate all the nested execution traces.

**Execution Trace Simplification.** The next step is to normalize and simplify the execution trace to purge any side effects obfuscation might have had on the execution trace. The simplification transformations we perform are as follows. 1) *Execution trace flattening*: an execution trace is modified so that the instructions in nested traces can be treated as if they were executed in their parent executions. To achieve this the register number used by nested execution traces has to be updated to new unused register numbers. Furthermore, the invocation call in the parent execution trace and the return instruction in the nested trace are substituted by new move instructions to connect the data dependency between nested and parent execution trace. 2) *Removing register aliasing*: register aliasing refers to cases when a single value is referenced by multiple registers. For backward slicing at a later stage, we need to remove any register aliasing in our execution
<figure><img src="image_5.png" /><figcaption>Fig. 2. An example source code of an app and a possible execution trace</figcaption></figure>

traces. 3) *Reflection normalization*: replaces any method invocation done using reflection with a normal method invocation. This transformation is not trivial since it requires to use new registers and add new instructions to with the correct data dependency relationship. 4) *Constant transformation simplification*: locates any method invocation that takes constant primitive values or strings as inputs and computes a new primitive value or string based on the inputs. After finding such methods, we replace the consequent Smali "move-result" instructions in the parent execution with the "const" Smali instructions.

**Important Instruction Extraction.** An important step in analyzing execution traces is to find semantically significant parts of it. Knowing that not all instructions bear the same significance, one key task is to define what instructions we consider semantically important. We consider instructions important if they can affect the system outside of the method's scope. From all Smali instructions, only few are capable of causing side effects outside of a method scope. Such instructions include 1) a method's return instruction which is not void, 2) invocation of Java or Android API methods that change global state such as reading from 'input' or writing to 'output', 3) invocations of methods that change the state of an object not created in local method scope, 4) changing the value of a static field of classes, 5) changing the value of an instance field of an object. Figure 2 shows the important instruction in execution trace.

Separating the return instruction or instructions that assign a new value to a field is straightforward, however, separating method invocations that can generate side effects is much more difficult. To find ART API invocations that change the global state of an application, e.g., printing or writing a value, we reuse our list of safe and pure methods. Essentially in our current implementation, any method invocation on unsafe methods is considered to potentially cause a side effect. For method invocations that change the state of a non-local object, we reuse our list of pure methods. In this case, any non-pure method invocation on
<figure><img src="image_6.png" /><figcaption>Fig. 3. Extracted slices and the corresponding fragments</figcaption></figure>

a non-local object is also considered to change its state. For example, adding a new value to an `ArrayList` object that has not been instantiated inside a method.

**Slice and Fragment Extraction.** Each important instruction usually depends on multiple instructions executed before it. We therefore need to discover and extract all data dependencies for each important instruction. We use *backward slicing* approach to partition execution traces into smaller and meaningful chunks of code. We denote a *slice* of a code with respect to an important instruction *in* and a single data value *x* involved in this instruction as a set of all preceding instructions that might affect the value of *x*. In essence, each slice corresponds to instructions that perform one semantically significant task in code.

We use *backward slicing* approach for two reasons: 1) control-flow can be modified by obfuscation and therefore might be difficult to simplify using only execution traces; 2) due to the fact that `Smali` is an object oriented instruction set, data-dependency between instructions includes significant semantic information.

Our next step is to break the slices into smaller pieces in order to capture small but semantically important code segments that can be shared between different methods. Given that instructions of a slice usually work with multiple objects and primitive values, we partition them into smaller sets of instructions each of which follows a single variable value. We refer to these partitions as *fragments*.

Finally, after separating fragments, we normalize them to remove minor differences caused by different literal values, user-defined type names, register numbers, and repeated instructions caused by loops and recursion. We keep instruction mnemonics and type identifiers only if they are not user-defined types. Figure 3 depicts extracted slices and the corresponding fragments for the example shown in Fig. 2.
## 3.4 Code Clone Detection

The last step is to detect code clones based on the partitioned fragments. In this work, we measure the similarity of two code pieces by calculating the Jaccard Index on two sets of fragments A and B. This similarity comparison can be both performed at the method level or the slice level which also makes our approach capable of finding smaller code clones.

$$ JaccardIndex = \frac{|A \cap B|}{|A \cup B|} $$

# 4 Validation and Experiments

Our simulator is implemented as an Android application for the Android version 26 or above. After installation, the simulator exposes APIs over the network which can be used to interact with it and perform Smali simulation. For our experiments, we installed our simulator on multiple emulated Android devices with 2 CPU cores and 4 GB of memory.

## 4.1 Dataset Creation

Due to the lack of labelled datasets containing Android code clones at bytecode level (with or without obfuscation), we ventured to create our set. We collected all available apps with multiple versions in the F-droid Android market. The resulting set had 5,045 Android app source projects for 1814 unique apps. From this set, we filtered apps containing code written in Kotlin, as our current implementation does not support Kotlin programming language, and removed apps that do not use the Gradle build tool as they cannot be compiled automatically. For the remaining projects we tried compiling them and those that did not produce any errors during build time were used in further analysis.

The total of 1751 projects from 685 unique apps were successfully compiled and comprise our non-obfuscated apps set. To generate obfuscated versions of these apps, we employed Obfuscapk [1], a free and open-source Android tool that includes a range of obfuscation techniques including some advanced approaches such as reflection and control flow obfuscation. To explore the obfuscation resiliency of our code clone detection approach, we obfuscate our compiled apps with various obfuscation techniques creating four different sets of obfuscated apps. Unfortunately, Obfuscapk failed to successfully obfuscate some of the apps with some obfuscation transformations. To ensure a proper comparison, for the further evaluation experiments, we used 1085 apps in the intersection of all these sets that all were successfully obfuscated. The summary of our created dataset is shown in Table 1.
<table><caption>**Table 1.** The summary of the employed datasets</caption><thead><tr><th>Dataset</th><th>Num. of apps</th></tr></thead><tbody><tr><td>Downloaded source code projects</td><td>5045</td></tr><tr><td>Successfully compiled projects</td><td>1751</td></tr><tr><td>Successfully simulated applications</td><td>1603</td></tr><tr><td>Successfully obfuscated applications:</td><td></td></tr><tr><td>Control-flow obfuscations</td><td>1320</td></tr><tr><td>Reflection obfuscations</td><td>1741</td></tr><tr><td>String encryption obfuscations</td><td>1740</td></tr><tr><td>All obfuscations (set used for evaluation)</td><td>1085</td></tr><tr><td>Banking malware applications</td><td>1076</td></tr></tbody></table>

## 4.2 Code Clone Detection Validation

In the first experiment, we examined the effectiveness of our approach in finding different types of code clones. We manually created 4 code clone samples for 5 different code snippets at source code level and injected them into an Android app. This resulted in 20 code clones which were then compiled to Smali code. Note that some differences in source code such as variable names are not present in the Smali code, and hence once compiled become a different types of code clones. Since our code clone analysis is based on the Smali code, we further modified some of the compiled Smali code to retain the types of code clones initially created in source code. Our modifications included removing the debugging information (for type-1 clones) and changing the register numbers (for type-2 clones). For type-3 and type-4 clones, no further changes were done since the differences in the source code were enough for creating type-3 and type-4 clones at the Smali code level. Table 2 shows our detection results for the injected code clone samples. The similarity results show that our approach is successful in finding type-1 to type-3 clones and also can detect some of the type-4 clones. The difference in results when detecting type-4 clones stems from the fact that our approach leverages data dependency between instructions and analyzes only semantically significant instructions for code clone detection. However, since the relationship between different types and APIs in Android Runtime is not captured, our approach can potentially miss some type-4 code clones. For example, our approach would not consider two code snippets that use different APIs for performing a file operation to be similar.
<table><caption>**Table 2.** Detection of injected code clones</caption><thead><tr><td>Code clone Name</td><td>Type-1</td><td>Type-2</td><td>Type-3</td><td>Type-4</td></tr></thead><tbody><tr><td>appendTextToFile</td><td>100%</td><td>100%</td><td>100%</td><td>44%</td></tr><tr><td>isTreeFull</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>removeDuplicatedInIntegerArrayList</td><td>100%</td><td>100%</td><td>100%</td><td>0%</td></tr><tr><td>reverseNumber</td><td>100%</td><td>100%</td><td>100%</td><td>26%</td></tr><tr><td>removeMiddleNodeInLinkedList</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr></tbody></table>

<table><caption>**Table 3.** Obfuscation resistancy validation</caption><thead><tr><td>Obfuscation set</td><td>Applied transformations</td><td>Num. apps</td><td>Num. methods</td><td>Avg. Sim.</td></tr></thead><tbody><tr><td>Control-flow obf.</td><td>CallIndirection, MethodOverload, ArithmeticBranch, Reorder, Goto, Nop</td><td>989</td><td>72638</td><td>84%</td></tr><tr><td>Reflection obf.</td><td>Reflection, AdvancedReflection</td><td>1017</td><td>7613</td><td>81%</td></tr><tr><td>String encryption obf.</td><td>ConstStringEncryption</td><td>1035</td><td>13836</td><td>87%</td></tr><tr><td>All obfuscations</td><td>All control-flow obf., All reflection obfuscations, ConstStringEncryption</td><td>846</td><td>53564</td><td>78%</td></tr></tbody></table>

## 4.3 Obfuscation Resistance Validation

To evaluate the obfuscation resistance of our approach against different obfuscation techniques, we use our four obfuscated datasets. In order to perform a valid and uniform comparison we discarded any apps with methods that failed to simulate properly. We manually analyzed the errors for such failures and noticed that most of the failures are caused by the ByteBuddy framework failing to dynamically create classes in cases when classes refer to types that do not exist in the apps .dex files. This however does not prevent an app from working in Android since the ART engine load classes lazily and the methods or fields with non-existent types are not invoked during execution. However, in our current implementation, classes are created and loaded eagerly, and thus, loading classes referring to non-existent types results in an error. When performing this experiment we also noticed that some transformations such as reflection do not affect all methods. Thus we base our evaluation on a set of methods that have been affected by the corresponding obfuscations. In this analysis, we consider the original set of non-obfuscated apps as a ground truth and evaluate our approach resiliency to obfuscation by comparing an obfuscated version of each app to its non-obfuscated counterpart.

The results of these comparisons are shown in Table 3. As the results show, string encryption has the highest similarity (87%), meaning 87% of fragments from non-obfuscated sets are found to be similar to the apps' set obfuscated with String encryption. The set with all obfuscations applied generated the largest number of methods (53,564) from 846 apps, and showed the minimum similarity (78%) which is expected due to complexity of obfuscation techniques. It should be noted though that after obfuscating apps with the control-flow and reflection transformations, our approach achieves 84% and 81% similarity with the non-obfuscated apps, respectively. In other words, our approach can detect code clones even in the presence of advanced obfuscation techniques, i.e., control-flow and reflection.
<table><caption>**Table 4.** Code clone detection among all non-obfuscated apps.</caption><thead><tr><th>Total</th><th colspan="6">Similarity range</th></tr></thead><tbody><tr><th colspan="8">Code clone clusters between different versions of apps</th></tr><tr><th>All clones</th><th>100%</th><th>96%—100%</th><th>92%—96%</th><th>88%—92%</th><th>84%—88%</th><th>80%—84%</th></tr><tr><td>29,744 (66%)</td><td>14,076 (47.32%)</td><td>1,802 (6.06%)</td><td>2,895 (9.73%)</td><td>3,504 (11.78%)</td><td>3,447 (11.59%)</td><td>4,020 (13.52%)</td></tr><tr><th colspan="8">Code clone clusters between different apps</th></tr><tr><th>All clones</th><th>100%</th><th>96%:100%</th><th>92%:96%</th><th>88%:92%</th><th>84%:88%</th><th>80%:84%</th></tr><tr><td>15,032 (34%)</td><td>3,562 (23.7%)</td><td>343 (2.28%)</td><td>1087 (7.23%)</td><td>2,122 (14.12%)</td><td>2,678 (17.82%)</td><td>5,240 (34.86%)</td></tr></tbody></table>

## 4.4 Inter-App Code Clone Detection

In this experiment, we investigate the presence of method-level code clones among all of our 1603 successfully simulated apps from our non-obfuscated set. To perform such comparison effectively, instead of performing computationally intensive pair-wise comparison, we grouped similar methods into clone clusters. We define a code clone cluster as a group of methods that were detected as identical to each other or similar (with similarity > 80%).

In this experiment, we discard very small methods, i.e., any methods that have less than four fragments. For Android apps, it is very common to include a group of libraries called support libraries in their build process to improve compatibility. After extracting code clone clusters, we also filtered the clusters that have been detected as the Android support library classes. In essence, in our analysis, we investigate the code clones appearing in user-defined code or any common library code that the developer has used. The results of our code clone analysis among all apps without Android support libraries are shown in Table 4. Out of 44,776 code clones, 29,744 code clones (66%) are associated with different versions of the same apps, while 15,032 (34%) are seen between different apps. Among 29,744 code clones, 47% are identical clones (100% similarity). This is expected as different versions of the same app typically contain a significant portion of identical code. The rest of the identified code clones show different code similarity as these are the modified code chunks. In the case of code clones found between different apps, we see that presence of identical code clones is less significant (23.7%) This also shows that code clones are a common phenomenon in Android applications and thus can be an effective way for analyzing and profiling Android applications.

To further investigate the extracted code clones, we randomly selected 15 clusters with different similarity degree and analyzed them manually. From the selected clusters, 12 clusters indeed contained correctly identified code clones, and 3 clusters contained methods that were not code clones. The code samples that were not correctly identified, shared one problem related to low code coverage for apps that use the Android support library classes.

The methods defined in support library classes perform many checks to validate the state of the device and if one of the checks fails, the method throws an exception. In the current implementation of our approach as we lack input generation and Ambiguous value is used as the reference object of each method,
<table><caption>**Table 5.** The comparison results with Nicad.</caption><thead><tr><td></td><td>Reported results</td></tr></thead><tbody><tr><td>Agreed clones</td><td>15,865 (81%)</td></tr><tr><td>Disagreed clones</td><td>3,565 (19%)</td></tr><tr><td>Not detected as clone by Nicad</td><td>312,906</td></tr><tr><td>Not detected as clone by AndroClonium</td><td>455,624</td></tr><tr><td>Not detected as clone by AndroClonium due to code coverage</td><td>443,393 (97.3%)</td></tr></tbody></table>

at each check a random path is taken which in most cases causes an exception to be thrown and thus the user defined code rarely is executed. This problem in the execution path causes many methods to be detected as clones since all of them show a similar execution trace leading to the throw exception.

## 4.5 Comparative Analysis

We further compare the code clone detection capabilities of our approach with the source code Nicad. Since Nicad was not designed for obfuscated code analysis, in this experiment we use non-obfuscated dataset. For fair comparison, we use pairs of different versions of apps as they are expected to contain code clones. Nicad leverages a threshold for declaring similar code pieces as clones, hence, in this analysis we set the threshold to 70% for both approaches.

The source code of 1,555 app-version pairs were analyzed by both approaches at the method level. Next, the findings of our approach on the Smali code that originated from source code files were compared with the findings of Nicad. When comparing two approaches, any method-clone pair with the difference of similarity degree less than 15% was marked as “Agreed clones”, if the difference in similarity was greater than 15% we marked it as “Disagreed clones”. For any clones that were detected by one tool, but not both we marked them as “Not detected” by the corresponding tool. In essence, these two groups include code clones that either of the tools failed to analyze or their similarity degree was <70% threshold. Table 5 shows our findings after comparing our approach with Nicad.

From 19,430 code clones found by both tools, 15,865 (81%) of code clones are clones that both tools agree on (similarity ≥ 70%) and 3,565 (19%) of clones were marked as disagreed clones. However, a vast difference between the clones detected by our approach and Nicad is also clear. Our approach found 312,906 clones not detected by Nicad. On the other hand, our approach missed 455,624 clones, more than 97% of them are due to code coverage problem. Another difference in the detected clones stems from the definition of code clones. Our approach when analyzing a method, considers the behaviour of all invoked nested methods as the behaviour of method under analysis, whereas most of the existing code clone detection tools do not. This is the design choice that we had to make since method in-lining or out-lining are common obfuscation techniques.
<table><caption>**Table 6.** Detection of malware apps</caption><thead><tr><th>Malware family</th><th>Num. of samples</th><th>Num. of identical clones</th><th>Num. of similar clones</th><th>Detected samples (only identical clones)</th><th>Detected samples (only similar clones)</th><th>Missed samples</th></tr></thead><tbody><tr><td>BankBot</td><td>136</td><td>224</td><td>581</td><td>90 (66.2%)</td><td>15 (11%)</td><td>31(22.8%)</td></tr><tr><td>Binv</td><td>2</td><td>8</td><td>5</td><td>2 (100%)</td><td>0 (0%)</td><td>0 (0%)</td></tr><tr><td>Citmo</td><td>3</td><td>42</td><td>10</td><td>3 (100%)</td><td>0 (0%)</td><td>0 (0%)</td></tr><tr><td>FakeBank</td><td>151</td><td>1216</td><td>1887</td><td>105 (69.5%)</td><td>18 (12%)</td><td>28 (18.5%)</td></tr><tr><td>SMSspy</td><td>131</td><td>1458</td><td>27540</td><td>130 (99.2%)</td><td>1 (0.8%)</td><td>0 (0%)</td></tr><tr><td>Sandroid</td><td>61</td><td>830</td><td>5620</td><td>60 (98.3%)</td><td>1 (1.7%)</td><td>0 (0%)</td></tr><tr><td>Spitmo</td><td>191</td><td>55</td><td>704</td><td>142 (74.3%)</td><td>44 (23%)</td><td>5 (2.7%)</td></tr><tr><td>Wroba</td><td>152</td><td>344</td><td>1004</td><td>106 (69.7%)</td><td>12 (7.9%)</td><td>34 (22.4%)</td></tr><tr><td>ZertSecurity</td><td>4</td><td>2</td><td>7</td><td>2 (50%)</td><td>1 (25%)</td><td>1 (25%)</td></tr><tr><td>Zitmo</td><td>142</td><td>531</td><td>837</td><td>116 (81.7%)</td><td>10 (7%)</td><td>16(11.3%)</td></tr><tr><td>Total</td><td>973</td><td>4710</td><td>38195</td><td>756 (77.5%)</td><td>102 (10.5%)</td><td>115 (12%)</td></tr></tbody></table>

## 4.6 Malware Detection Using Code Clone Fragments

We look at one of the practical applications of code clone detection. We investigate an ability of our approach to detect malware variants using code clones. In this experiment, we use a set of Android banking malware collected by [16]. The dataset consists of 973 malicious Android banking apps distributed across 10 malware families: BankBot, Binv, Citmo, FakeBank, Sandroid, SMSspy, Spitmo, Wroba, ZertSecurity and Zitmo.

Similar to our previous experiments, we extract code clones from banking binary samples and then cluster them based on their similarity. We define a code clone cluster as a group of methods that were detected as identical to each other or similar with similarity > 75%. We discard small methods with less than 3 fragments to highlight longer and more meaningful methods. Our analysis produces 47,149 code clone clusters among 973 apps. To further analyze detected code clone clusters, we first separate clusters with clones that are unique to one malware family and clones that have been seen among multiple families or benign apps. We leverage unique clones for malware detection. In our experiment, 91% of code clone clusters are unique and 9% of clusters contain code clones from apps in different malware families. To better explore the effectiveness of code clones for malware detection, we further divided the unique clones into identical clones (similarity = 100%) and similar clones (75% < similarity < 100%). For each malware sample, we then checked if it shares any unique clones with any other samples of its family and if so we marked it as detected. If no unique clones were found between the malware samples, we marked a sample as missed.

Table 6 shows our approach effectiveness in detection of malware samples. 77.5% of binary samples were correctly detected based on only identical code clones within their code. 10.5% were detected solely based on similar code clones. The total of 88% of apps were detected correctly based on the presence of code clones in their binary code.
# 5 Conclusion

In this paper, we introduced an approach for obfuscation-resistant fine-grained detection of code clones in obfuscated Android apps. Our approach uses program backward slicing on execution traces to extract semantically significant instructions based on data-dependency to overcome the challenges of purely static and dynamic approaches. We validated our approach, by comparing the results of our approach in presence and absence of obfuscation. We achieved 84%, 81%, 87%, 78% similarity when analyzing four obfuscated sets of Android apps. We compare the performance of our approach with Nicad in finding method-level code clone. We observe that both approaches agree on most of the code clones detected with high degree of similarity. Yet, our approach is able to find a significantly more code clones not detected by Nicad approach. e user-defined code in order to be semantic preserving.

The proposed approach is resistant to code obfuscation and is effective in finding different types of code clones at the binary level. We also have identified few limitations that our current prototype implementation has: limited code coverage and scalability. The code coverage problem mostly stems from the fact that our current implementation uses ambiguous values for all inputs and thus traverses undesired paths. While further differentiating inputs can produce higher code coverage, we leave it as future work. The scalability of our approach is another challenge as our current implementation needs to compare fragments for pairs of code for measuring code similarity. This can be also potentially improved by using heuristics based on the size of code for more efficient code clone detection. These implementation improvements would not fundamentally change the approach and would result in marginal gains.

# References

1. Obfuscapk: an open-source black-box obfuscation tool for android apps. SoftwareX, 11, 100403 (2020)

2. Akram, J., Shi, Z., Mumtaz, M., Luo, P.: DroidCC: a scalable clone detection approach for android applications to detect similarity at source code level. In: 2018 IEEE 42nd Annual Computer Software and Applications Conference (COMPSAC), vol. 1, pp. 100–105. IEEE (2018)

3. Alam, S., Riley, R., Sogukpinar, I., Carkaci, N.: Droidclone: detecting android malware variants by exposing code clones. In: 2016 Sixth International Conference on Digital Information and Communication Technology and its Applications (DIC-TAP), pp. 79–84. IEEE (2016)

4. Bacci, A., Bartoli, A., Martinelli, F., Medvet, E., Mercaldo, F.: Detection of obfuscation techniques in Android applications. In: Proceedings of the 13th International Conference on Availability, Reliability and Security, pp. 1–9 (2018)

5. Balachandran, V., Tan, D.J., Thing, V.L., et al.: Control flow obfuscation for android applications. Comput. Secur. 61, 72–93 (2016)

6. Bichsel, B., Raychev, V., Tsankov, P., Vechev, M.: Statistical deobfuscation of android applications. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 343–355 (2016)
7. Calzavara, S., Grishchenko, I., Maffei, M.: Horndroid: practical and sound static analysis of android applications by SMT solving. In: 2016 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 47–62. IEEE (2016)

8. Collberg, C., Thomborson, C., Low, D.: A Taxonomy of Obfuscating Transformations. Department of Computer Science, The University of Auckland, New Zealand, Technical report (1997)

9. Crussell, J., Gibler, C., Chen, H.: Scalable semantics-based detection of similar android applications. In: ESORICS, pp. 182–199 (2013)

10. David, Y., Yahav, E.: Tracelet-based code search in executables. Sigplan Not. 49(6), 349–360 (2014)

11. Ding, S.H., Fung, B.C., Charland, P.: Kam1n0: MapReduce-based assembly clone search for reverse engineering. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 461–470 (2016)

12. Egele, M., Woo, M., Chapman, P., Brumley, D.: Blanket execution: dynamic similarity testing for program binaries and components. In: 23rd USENIX Security Symposium (USENIX Security 14), San Diego, pp. 303–317. USENIX Association (2014)

13. Eschweiler, S., Yakdan, K., Gerhards-Padilla, E.: Discovre: efficient cross-architecture identification of bugs in binary code. In: NDSS, vol. 52, pp. 58–79 (2016)

14. Hu, Y., Zhang, Y., Li, J., Wang, H., Li, B., Gu, D.: Binmatch: a semantics-based hybrid approach on binary code clone analysis. In: 2018 IEEE International Conference on Software Maintenance and Evolution (ICSME), pp. 104–114. IEEE (2018)

15. Jiang, L., Misherghi, G., Su, Z., Glondu, S.: Deckard: scalable and accurate tree-based detection of code clones. In: 29th International Conference on Software Engineering ICSE 2007, pp. 96–105. IEEE (2007)

16. Kadir, A.F.A., Stakhanova, N., Ghorbani, A.A.: An empirical analysis of android banking malware. Protecting Mobile Networks and Devices: Challenges and Solutions, 209 (2016)

17. Kamiya, T., Kusumoto, S., Inoue, K.: CCfinder: a multilingualistic token-based code clone detection system for large scale source code. IEEE Trans. Softw. Eng. 28(7), 654–670 (2002). https://doi.org/10.1109/TSE.2002.1019480

18. Komondoor, R., Horwitz, S.: Using slicing to identify duplication in source code. In: Cousot, P. (ed.) SAS 2001. LNCS, vol. 2126, pp. 40–56. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-47764-0_3

19. Roy, C.K., Cordy, J.R.: NICAD: accurate detection of near-miss intentional clones using flexible pretty-printing and code normalization. In: 2008 16th IEEE International Conference on Program Comprehension, pp. 172–181 (2008). DOI: https://doi.org/10.1109/ICPC.2008.41

20. Sajnani, H., Saini, V., Svajlenko, J., Roy, C.K., Lopes, C.V.: SourcererCC: scaling code clone detection to big-code. In: Proceedings of the 38th International Conference on Software Engineering, pp. 1157–1168 (2016)

21. Đurić, Z., Gašević, D.: A source code similarity system for plagiarism detection. Comput. J. 56(1), 70–86 (2013)

22. de Vos, M., Pouwelse, J.: Astana: practical string deobfuscation for android applications using program slicing. arXiv preprint arXiv:2104.02612 (2021)

23. Wang, Y., Rountev, A.: Who changed you? Obfuscator identification for Android. In: 2017 IEEE/ACM 4th International Conference on Mobile Software Engineering and Systems (MOBILESoft), pp. 154–164. IEEE (2017)
24. Wei, F., Roy, S., Ou, X.: Amandroid: a precise and general inter-component data flow analysis framework for security vetting of android apps. ACM Trans. Priv. Secur. (TOPS) 21(3), 1–32 (2018)

25. Winterhalte, R.: Byte buddy - runtime code generation for the java virtual machine. https://bytebuddy.net/

26. Yang, J., Xiong, Y., Ma, J.: A function level java code clone detection method. In: 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), vol. 1, pp. 2128–2134. IEEE (2019)

27. Yang, S., Cheng, L., Zeng, Y., Lang, Z., Zhu, H., Shi, Z.: Asteria: deep learning-based ast-encoding for cross-platform binary code similarity detection. In: 2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) (2021)

28. Yoo, W., Ji, M., Kang, M., Yi, J.H.: String deobfuscation scheme based on dynamic code extraction for mobile malwares. IT Convergence Pract. 4(2), 1–8 (2016)

29. Yu, D., et al.: Detecting java code clones with multi-granularities based on bytecode. In: 2017 IEEE 41st Annual Computer Software and Applications Conference (COMPSAC), vol. 1, pp. 317–326. IEEE (2017)