11institutetext: University of Cagliari, Cagliari (CA) 09123, Italy 11email:
<EMAIL_ADDRESS>22institutetext: Georgetown
University, Washington, DC 20057 22email<EMAIL_ADDRESS>
# Can you See me? On the Visibility of NOPs against Android Malware Detectors

Diego Soi 11 0009-0009-0092-9067 Davide Maiorca 11 0000-0003-2640-4663 Giorgio
Giacinto 11 0000-0002-5759-3017 Harel Berger 22 0000-0001-6035-5127

###### Abstract

Android malware still represents the most significant threat to mobile
systems. While Machine Learning systems are increasingly used to identify
these threats, past studies have revealed that attackers can bypass these
detection mechanisms by making subtle changes to Android applications, such as
adding specific API calls. These modifications are often referred to as No
OPerations (NOP), which ideally should not alter the semantics of the program.
However, many NOPs can be spotted and eliminated by refining the app analysis
process. This paper proposes a visibility metric that assesses the difficulty
in spotting NOPs and similar non-operational codes. We tested our metric on a
state-of-the-art, opcode-based deep learning system for Android malware
detection. We implemented attacks on the feature and problem spaces and
calculated their visibility according to our metric. The attained results show
an intriguing trade-off between evasion efficacy and detectability: our metric
can be valuable to ensure the real effectiveness of an adversarial attack,
also serving as a useful aid to develop better defenses.

###### Keywords:

Android, Malware, Evasion, Visibility

##  1 Introduction

With its 70% global market share, Android has become a major target for
malware aimed at compromising the devices’ confidentiality, integrity, and
availability. During the second quarter of 2023, there was a notable increase
in malicious software variants, with over 350,000 new instances identified.
This surge particularly involved a rise in Ransomware and banking Trojans
[15].

Extensive research on Android security has led to the development of various
Machine Learning-based defences. These systems employ traditional and deep
learning techniques, achieving high accuracy and low false positive rates.
However, the mutable nature of ML-based systems has inspired adversaries to
develop powerful methods to bypass these defences, a concept widely known as
Adversarial Machine Learning [6, 13, 7]. Research conducted over the last
decade demonstrated that a set of subtle, fine-grained alternations in Android
executable code or permissions can significantly impair the accuracy of these
classifiers. Fortifying learning-based detection systems remains an open and
challenging problem.

A critical aspect of these attacks is how they are translated into the
_problem space_ , i.e., the process of embedding into real samples evasive
modifications carried out on the feature level. These changes, often called
’no operations’ (or NOPs), are designed not to affect the application’s
semantics during its execution. NOPs can be implemented in multiple ways:
previous works [21] injected portions of benign samples to produce real
evasive applications, while others employed redundant or unsatisfied
conditions (e.g., fake conditional jumps). Notably, some NOPs possess
attributes that make them more perceptible than others to human analysts and
machines, thus simplifying the development of countermeasures to detect them
(e.g., a sequence of repeated calls to functions that do not perform any
action is easily recognizable). Yet, to the best of our knowledge, the impact
of the _visibility_ and _detectability_ of such NOPs remains unexplored.

Our paper introduces an innovative visibility metric named Clarity Complexity
Connection (CCC), aimed at quantifying the ease with which humans can detect
NOPs. The CCC metric considers three cardinal components: i) the
_predictability_ of the injected code line, ii) the _complexity_ of the NOP,
according to the quantity and diversity of injected instructions, and iii) the
NOP’s _distinguishability_ relative to the application’s original codebase.

We applied our metric to various NOPs employed to evade a popular state-of-
the-art learning-based system. In particular, we created NOP-based attacks in
the problem space to evaluate their visibility. Our results show that
effective adversarial attacks should be crafted by considering their
stealthiness when developing real evasive applications. In particular, most
organizations rely on two layers of security - human experts and detection
systems, and the proposed metric can be flexibly employed as a way to consider
detection attempts that come both. Our findings also reveal that the proposed
CCC metric can serve as a valuable tool in enhancing and assessing the
robustness of malicious detectors against various degrees of NOP injections.

The rest of the paper is organized as follows. First, we describe related work
(Section 2). Next, we give background on Android and Smali language (Section
3). Then, we present our methodology in Section 4. Our experiments and results
are described in Section 5. Finally, we discuss our insights and future
directions (Section 6).

##  2 Related Work

In this section, we review important studies concerning anti-malware detection
techniques such as NOPs (or similar approaches).

NOP or No-Operations involves the insertion of non-functional code or
instructions within malicious Android applications. This term mainly concerns
explicit NOP commands [24] that are added to the original code. Christodorescu
et al. [9] showed that explicit NOPs could evade signature-based malware
detection systems. In ADAM [29] and DroidChameleon [23], the authors listed
explicit NOPs as one of their attack vectors. In addition, Rastogi et al. [22]
and Faruki et al. [12] implemented explicit NOPs that were effective against
several commercial AVs.

Another attack vector similar to NOPs is the insertion of dead code. Dead code
[16] is program code that can not be executed and is usually obsolete,
redundant, or accidentally left in the program, no longer serving any purpose.
Aonzo et al. [3] created a tool called ObfuscAPK, in which (among other attack
vectors) dead code was introduced. This instance of dead code comprises
mathematical computations and a conditional branch instruction, intentionally
structured so that the branch is guaranteed to never be triggered. Lin et al.
[19] suggested inserting codes after a jump API call that will surely be
executed. The code after the jump is dead code, as it would not be executed.

Another similar attack vector is Defunct code/Junk code [2]. Junk code indeed
runs (in contrast to the dead code), but does not contribute to the code’s
functionality. An example can be found in Shankarapani et al. [26]. The
authors suggested assembly junk code, in which redundant register mathematical
were added to the original code. A similar junk code is also described in the
work of Rastogi et al. [23]. Hammad et al. [14] suggested comments, and
debugging information as another type of junk code. Bacci et al. [4] presented
an attack of additional registers and the use of them in non-relevant
commands. Rosenberg et al. [25] implemented system calls with no effect. Chen
et al. [8] proposed Android-HIV, in which apps with generated calls to blank
functions were introduced. Vasan et al. [27] added re-assigning the same value
of a variable ($x=x$).

These previous works showed that the NOP addition technique (and similar
techniques) can circumvent known malware detectors and AVs. However, as far as
we know, none of the previous works has thoroughly explored the visibility of
such attacks by considering humans and machines. In other words, these works
did not quantify how easy or hard it is to detect and eliminate the NOPs and
defunct code.

##  3 Android applications

Android applications are packed as zip archives using the APK format [28]
which contains all resources required by Android to install and execute the
application. These consist in several elements among which the most important
are (_i_) the AndroidManifext.xml file that holds various information, among
which the necessary _permissions_ to use restricted functionalities (i.e. API
calls), _services_ , _actions_ , and _components_ to run background tasks and
communicate with the resource provider; (_ii_) XML files and raw resources
(i.e. images, icons, etc.); (_iii_) lib directory to save CPU-specific
libraries; and (_iv_) one or more .dex files.

Android apps are often written in Java/Kotlin and compiled in Dalvik bytecode
(.dex file), which results from compiling the bytecode throughout a dex
compiler. After that, the Android virtual machine DVM (Dalvik Virtual Machine)
or ART (Android RunTime), introduced in later Android versions, can execute
the application source code.

The reverse process (i.e., disassembling the APK), done by tools like
APKtool111https://apktool.org/, can extract all APK resources and disassemble
.dex files into Smali code, an assembly-like programming language for low-
level programming in Android. Smali code is simple to read since it represents
the bytecode in a human-readable format. Smali syntax is similar to
Jasmine’s222https://jasmin.sourceforge.net/ syntax. The lines are categorized
into one of the following: (_a_) comments, which are the notes embedded into
the source code starting with $\\#$; (_b_) directives, which define classes,
methods, registers starting with .; (_c_) instructions, which are the bytecode
opcodes consisting of a name and one or more parameters.

Listing 1 shows a simple Java class whose Smali code representation is
depicted in Listing 2. Different opcodes are included, and among them, sget-
object retrieves the value of a static field of type ”Object” to put it in
register v0; invoke-virtual invokes println non-static method on v0 passing p0
parameter; eventually return-void indicates the end of a method without
returning a specific value.

⬇

1package com.apk.demo;

public class Demo {

3 public static String printMessage(String str) {

System.out.println(str);

5 }

}

Listing 1: Java code defining a class called Demo.

⬇

1.class@ public Lcom/apk/Demo;

.super@ Ljava/lang/Object;

3.source@ ”Demo.java”

# direct methods@@

5.method@ public static printMessage(Ljava/lang/String;)V;

.param@ p0, ”str”

7 .prologue@

sget-object v0, Ljava/lang/System;->out:Ljava/io/PrintStream;

9 invoke-virtual {v0, p0}, Ljava/io/PrintStream;->println(Ljava/lang/String;)V

return-void

11.end@ method

Listing 2: Smali code corresponding to the class defined in Listing 1. The
constructor has been omitted for brevity. Blue strings are comments, red lines
are directives, and the cyan lines are instruction opcodes.

##  4 Methodology

This section describes our new visibility metric through its three major
components (Sections 4.1-4.5), by giving three representative
examples.(Section 4.6). We also describe the target system (Section 4.7), and
we present the attacker model and several practical evasion attacks on Smali
code to assess the utility of the CCC metric (Section 4.8).

###  4.1 Visibility

Evasion attacks against learning-based systems should typically feature two
major characteristics:

  * •

They should be efficient on the _feature space_ , i.e., producing an evasive
feature vector starting from the original one. Various metrics such as recall,
F1, and accuracy can be used to assess the efficacy of these attacks.

  * •

Such attacks should also preserve the functionality and semantics of the
original samples (i.e., they should be transferred to the so-called problem
space [5, 21]). In other words, attackers should be able to produce a
functional application that implements the feature-space modifications.

In this paper, we add another fundamental characteristic these attacks should
have: the injected modifications should be _hard to detect_ or, in other
words, _less visibile_ to human perception. Organizations tend to use two
layers of security - human experts and ML-based detection systems. This metric
paves the way for quantifying the difficulty of human experts to correctly
identify attacks (i.e., the _visibility_ of the attacks). Intuitively, various
no-operations opcodes scattered through the executable can be a clear sign of
manipulation by a human expert. Conversely, a single injected Smali
instruction may be indistinguishable from the rest of the code both by humans
and machines. More formally, given a malicious sample file $S$, a set of
functions $s_{i}=\\{s_{1},s_{2},s_{3}...s_{n}\\}\subseteq S$, and a set of
lines added to $s_{i}$ termed $l_{i}=\\{l_{1},l_{2},l_{3}...l_{n}\\}$ that an
attacker added to evade detection, can the following questions be answered?

RQ1: How clear is it that the set $l_{i}$ constitutes a code of attack against
a malware detection system and has no meaning? Indeed, some operations, such
as explicit NOPs, are clearly an artificial addition to $S$ and regularly,
these operations will be described as having no effect.

RQ2: How fast can $l_{i}$ be identified as a code of attack? Indeed, based on
the king of operation encountered when following the functions $s_{i}$, the
time to assess the meaning of the line $l_{i}$, in the case it is a single
line or a loop with multiple computations, may be different.

RQ3: What is the level of connection between $l_{i}$ to the original $s_{i}$?
If $l_{i}$ uses original variables from $s_{i}$, it is difficult to separate
$l_{i}$ from $s_{i}$. In this case, one usually sees $l_{i}$ as any other
lines of code from $s_{i}$. On the other hand, if $l_{i}$ does not include any
use of original variables of $s_{i}$, one can disconnect $l_{i}$ easily with
no great influence on $s_{i}$ and $S$. In this case, $l_{i}$ can be identified
easily as an unrelated piece of code to $s_{i}$ and $S_{i}$.

To address these questions, we propose a metric called CCC, considering
multiple elements. CCC is composed of the following elements:

  1. 1.

Clarity

  2. 2.

Complexity

  3. 3.

Connection

An evasive set of lines $l_{i}$ that receives a CCC value $\sim 1$ is visible
and can be identified as a suspicious tool to evade malware detection.
Conversely, a CCC value $\sim 0$ is a sign of seemingly invisible evasive
code. Now, we define each element separately. For each element in CCC, we
equally split the interval of [0,1] based on representative cases.

###  4.2 Clarity

Clarity addresses RQ1. This element describes if $l_{i}$ is clear to be an
injected code in $S$. A human expert easily identifies a simple instruction
such as explicit NOP as an injected instruction, as it holds no meaning.
Conversely, a more complex instruction using variables may seem less clear.
Variables conceal the nature of the injected code because they imitate a more
meaningful view by a human expert. Two main cases are considered:

  1. 1.

If $l_{i}$ includes an explicit NOP, its clarity rate is considered high, as
it is clearly an addition to the original code $S$. As far as we know, no NOP
instruction is natively present in Android apps. This is understandable, as
NOPs serve no purpose besides evading detection. For this case, $C_{1}(S)=1$.

  2. 2.

If $l_{i}$ does not include any explicit NOP, it is less clear how to define
the clarity element. Thus, we evaluate the average ratio of $l_{i}$ and the
original code lines $s_{i}$. We note that for small $s_{i}$, the addition may
be more identifiable, as the basic functionality is simple. Therefore, the
addition of lines is recognizable. In complex and long functions, the same
amount of lines will be less visible. Instead of using the actual amount of
added lines $|l_{i}|$, we use exponential transformation $e^{|l_{i}|}$, as
representing the added lines. Human perception of changes in a codebase can be
non-linear. Applying the exponential transformation exclusively to the added
lines reflects this non-linear perception, where the perceived impact
increases more rapidly with increasing the size of the additions. This aligns
with how humans may intuitively assess the significance of the added lines.
Also, in larger codebases, a simple linear scaling might lead to saturation,
where the modification ratio reaches a ceiling quickly. The exponential
transformation helps avoid such saturation, allowing the metric to continue
increasing at a more noticeable rate for larger additions. Formally, we
compute,

$C_{1}(S)=\sum_{i=1}^{n}\frac{\frac{e^{|l_{i}|}}{e^{|l_{i}|}+|s_{i}|}}{n}$

###  4.3 Complexity

Complexity addresses RQ2. This element describes how resourceful an
identification of $l_{i}$ should be. When $l_{i}$ composes only one-liner
perturbation, such as single NOP lines, the complexity is low. A more complex
case is with a single function or condition. A condition splits the flow of
the code into two options/parts. Therefore, the code analysis now includes two
branches, which are more complex to analyze. An even more complex case is with
a loop or a nested condition with degree n, as now the analysis may need to do
n iterations on $l_{i}$. The extreme case is reserved for complex
computations, such as recursion. The cases are defined as follows:

  1. 1.

If $l_{i}$ is a series of explicit NOPs or single API calls, its complexity
rate is considered low. This is because the process needed to identify it is
just going over the file and determining the nature of each single line with a
small context (before and after the line). For this case, $C_{2}(l_{i})=0$.

  2. 2.

If $l_{i}$ is a single function or a conditional, the process of determining
its nature is more complex. An analysis of the function operation or the
branches of the condition is needed. In this case, a human expert needs to
have a simulated memory of variables’ values and the connections between
variables to be able to determine the nature of $l_{i}$. Therefore, in this
case, $C_{2}(l_{i})=0.33$.

  3. 3.

The next value is assigned for $l_{i}$ when it is a loop or a nested condition
with degree n. This case sometimes requires iterating on the code a couple of
times, thus resulting in a higher complexity rate. For this case,
$C_{2}(l_{i})=0.66$.

  4. 4.

The last and extreme value is assigned for complex computational tasks, such
as recursion or a series of nested loops. Following recursion, for example, is
a tough assignment for human experts, and therefore is assigned with the
maximum values. For this case, $C_{2}(l_{i})=1$.

We define $C_{2}$ to be the complexity element of a test sample file $S$ as
follows:

$C_{2}(S)=\frac{\sum_{i=1}^{n}C_{2}(l_{i})}{n}$

###  4.4 Connection

Connection addresses RQ3. This element addresses the difficulty of detachment
of the code snippet $l_{i}$ from $s_{i}$. A simple set $l_{i}$ that is not
connected to parts of the original functions $s_{i}$ is easy to remove.
Consequently, in this case, $l_{i}$ can be viewed as an external part of
$s_{i}$. On the other hand, the set $l_{i}$ that uses original variables is
more difficult to remove, as it needs a more in-depth connection of the
$s_{i}$. Three cases are considered:

  1. 1.

The connection value is low if there are no real attachments from $l_{i}$ to
$s_{i}$, such as in the case of explicit NOP or API calls without variables.
Another case is if the set $l_{i}$ constitutes a function that is not called
from the original code. Thus, in these cases, $C_{3}(l_{i})=0$.

  2. 2.

If $l_{i}$ includes one original variable from $s_{i}$, the $C_{3}$ value is
higher, as now $l_{i}$ ”seems” interconnected to $s_{i}$. A human expert needs
to follow the modifications to this variable during $l_{i}$ to be able to
separate the set $l_{i}$ from the original code $s_{i}$. Thus, in this case,
$C_{3}(l_{i})=0.5$.

  3. 3.

For the last case, $l_{i}$ incorporates more than one original variable from
$s_{i}$. Thus, it may seem as if $l_{i}$ is indistinguishable from the
original code of $s_{i}$. This case is different from the last case, as in
this current case, a human expert needs to keep in mind the values of
different variables and watch their changes during the simulation of the code.
Following only one variable is easier. Therefore, in this case, we determine
that $C_{3}(l_{i})=1$.

We define $C_{3}$ to be the connection element of a sample file $S$ as
follows:

$C_{3}(S)=\frac{\sum_{i=1}^{n}C_{3}(l_{i})}{n}$

###  4.5 CCC

The notion of visibility is to quantify how hard it is to identify an attack.
Therefore, a high complexity ($C_{2}$) value contributes to a more invisible
attack, suggesting more resources to acknowledge the attack. Also, a high
value of connection ($C_{3}$) determines that it is more difficult to
distinguish between the original code lines and the new code lines. Therefore,
the CCC formula uses the values of $1-C_{2}(S)$ and $1-C_{3}(S)$ instead of
the positive values.

Additionaly, a set of weights $\\{w_{i}:i=1..3\\}$ is assigned for the three
Cs. A naive set of weights is {0.33, 0.33, 0.33}. However, it is not a clear
cut to give each part the same weight. For example, a long list of consecutive
NOPs, also known as NOP sled [1], can be easily identified. This is true, as
even if a software developer mistakenly added a single NOP to its code, the
probability that he will do so with a long list of NOPs is negligible. Using a
long list of NOPs is too suspicious from being a natural part of an app. It
can be a part of an original malicious app or an addition to a benign one. In
both cases, the list of NOPs tends to signal malicious activity. Therefore,
$C_{1}$ plays a vital part in addressing visibility and should be assigned
with a reasonable weight.

Also, if a set of code lines does not have any connection to the code (i.e.,
$1-C3(S)\sim 1$, is is reasonable to say that the code is redundant and does
not run at all (a.k.a. junk code). A simple example is a non-called function
added to the original code. This is a red light for manipulating the code,
since a product version of an app regularly does not include redundant
functions. As a consequence, $C_{3}$ should get a reasonable weight.

However, the complexity value $C_{2}$ aspect does not have clear cuts as the
other two aspects. This aspect relates to the complexity of the code snippet.
A very complex code or a very subtle code does not necessarily state anything
about its nature. It is just the way the code is organized. However, as a
human expert’s ability to identify a malicious code snippet is affected by its
complexity, we included it in the CCC metric.

Consequently, the $w_{1}$ and $w_{3}$ receive a higher value than $w_{2}$.
Now, we define the CCC metric:

$CCC(S)=w_{1}*C_{1}(S)+w_{2}*(1-C_{2}(S))+w_{3}*(1-C_{3}(S))$

Given the above-mentioned observations on the differences between the weights,
we pick the values of 0.4,0.2,0.4 for $w_{i}$, respectively. Other weights can
be picked as well. This analysis is left for future work. Thus, our final
version of the CCC visibility metric is:

$CCC(S)=0.4*C_{1}(S)+0.2*(1-C_{2}(S))+0.4*(1-C_{3}(S))$

###  4.6 Representative Examples

We present three representative code snippets showing different attack
scenarios to demonstrate our innovative CCC metric. The demo evaluation is
summarized in Table 1. We start with two simple functions on two integers -
addition and subtraction (Listings 3):

⬇

1.method@ public static addTwoIntegers(II)I;

.registers@ 3

3 add-int v0, v1, v2

return v0

5.end method

7.method@ public static subtractTwoIntegers(II)I;

.registers@ 3

9 sub-int v0, v1, v2

return v0

11.end method

Listing 3: Small code snippet with addition and subtraction functions. Red
lines are directives

In the following, we report three examples that are based on these simple
functions.

####  4.6.1 Simple NOPs (EX_1)

In this example (Listings 4), we added a set of three NOPs to two original
functions. The $C_{1}$, $C_{2}$, $C_{3}$ values for $EX_{1}$ are 1, 0, 0,
respectively, and the final CCC value is 1. The full calculation is available
in Appendix 0.A.1. The high CCC value pinpoints that $EX_{1}$ is pretty simple
to distinguish from the original code. This is understandable, as the code
snippet includes only NOPs, a suspicious set of lines.

⬇

1.method@ public static addTwoIntegers(II)I;

.registers@ 3

3 add-int v0, v1, v2

nop

5 nop

nop

7 return v0

.end method

9

.method@ public static subtractTwoIntegers(II)I;

11 .registers@ 3

sub-int v0, v1, v2

13 nop

nop

15 nop

return v0

17.end method

Listing 4: Small code snippet with simple NOPs additions. Red lines are
directives, cyan lines are additions to the code.

####  4.6.2 Loop & Addition (EX_2)

In this example (Listings 5), we used the same simple functions as before. We
added a loop to the original code with a simple addition. The $C_{1}$,
$C_{2}$, $C_{3}$ values for $EX_{2}$ are 0.98, 0.66, 1, respectively, and the
final CCC value is 0.46. The full calculation is available in Appendix 0.A.2.
The CCC value of 0.46 implies that $EX_{2}$ demonstrates a slightly tricky
code, that is not trivial to distinguish from the original one. The small
amount of original code contributes to the magnitude of $C_{1}$, therefore the
value is not negligible. For longer functions, the addition of only 5 lines
has a smaller effect. For simplicity, we demonstrated the metric on a small
code snippet. This code snippet includes an advanced connection to the
original code. An in-depth understanding of the loop is needed to analyze it
correctly.

⬇

1.method@ public static addTwoIntegers(II)I;

.registers@ 3

3 add-int v0, v1, v2

const/4 v1, 0 # Initialize loop variable to 0

5 :start_loop

# Check if the loop variable is less than v0@@

7 if-ge v1, v0, :end_loop

# Add v2 to itself and store the result in v2@@

9 add-int v2, v2, v2

# Increment the loop variable@@

11 add-int/lit8 v1, v1, 1

goto :start_loop

13 :end_loop

return v0

15.end method

17.method@ public static subtractTwoIntegers(II)I;

.registers@ 3

19 sub-int v0, v1, v2

const/4 v1, 0 # Initialize loop variable to 0

21 :start_loop

# Check if the loop variable is less than v0@@

23 if-ge v1, v0, :end_loop

# Add v2 to itself and store the result in v2@@

25 add-int v2, v2, v2

# Increment the loop variable@@

27 add-int/lit8 v1, v1, 1

goto :start_loop

29 :end_loop

return v0

31.end method

Listing 5: A code snippet with simple loop and mathematical addition. Red
lines are directives, cyan lines are additions to the code.

⬇

1.method@ public static addTwoIntegers(II)I;

.registers@ 3

3 add-int v0, v1, v2

# Compare v2 with 0

5 if-ge v2, 0, :skip_print

# Code to print nothing (invoke-static)

7 invoke-static {}, Ljava/lang/System;->outPrintln()V

:skip_print

9 return v0

.end method

11

.method@ public static subtractTwoIntegers(II)I;

13 .registers@ 3

sub-int v0, v1, v2

15 # Compare v2 with 0

if-ge v2, 0, :skip_print

17 # Code to print nothing (invoke-static)

invoke-static {}, Ljava/lang/System;->outPrintln()V

19 :skip_print

return v0

21.end method

Listing 6: A code snippet with simple condition and API call (print). Red
lines are directives, cyan lines are additions to the code.

####  4.6.3 Condition & API Call (EX_3)

In this example (Listings 6), we used the same original functions as well. We
added to the original code a condition with a simple API call of print (with
no content). $C_{1}$, $C_{2}$, and $C_{3}$ values for $EX_{3}$ are 0.79, 0.33,
0.5, respectively, and the final CCC value is $0.65$. The full calculation is
available in Appendix 0.A.3. The CCC value of 0.65 implies that $EX_{3}$ is
less invisible than $EX_{2}$. This is because the condition makes it harder to
analyze on the one hand, and the API call makes it easier as it does not
include any use of original variables. Thus, only one original variable is
used, which makes it less connected to the original code.

Table 1: CCC demo examples. The weights for $C_{1}$, $1-C_{2}$, & $1-C_{3}$ are 0.4, 0.2, 0.4, respectively. |  $C_{1}$ |  $1-C_{2}$ |  $1-C_{3}$ |  $CCC$
---|---|---|---|---
$EX_{1}$ |  1 |  1 |  1 |  1
$EX_{2}$ |  0.98 |  0.66 |  1 |  0.46
$EX_{3}$ |  0.79 |  0.33 |  0.5 |  0.65

###  4.7 Target System

The target machine we used was proposed by McLaughlin et al. [20], a DL
detection system based on a Convolutional Neural Network. The system’s
features are opcode sequences statically extracted by reading the disassembly
Smali file. These are represented as one-hot vectors, projected into an
embedding space to generate a matrix $P$ with dimensions $n\times k$, where
$k$ is the embedding space’s dimensionality, and $n$ is the number of original
opcodes.

The detection system consists of 1D CNN layers, with the first one taking the
$n\times k$ matrix as input. The output of the last CNN layer undergoes a max
pooling layer, followed by fully-connected layers. Eventually, a softmax
function computes the classification score of benign and malware classes
(i.e., classes 0 and 1).

###  4.8 Evasion Attacks

In this section, we present the attacker model and three evasion attacks we
implemented to assess the practicality of the CCC metric.

####  4.8.1 Attacker Model

The attacker in this work has access to the pre-processing that is done to
extract the opcodes and feature representation (i.e., opcodes one-hot
encoding) of the target system. Thus, the attacker can be considered a gray-
box attacker.

Figure 1: The attack process for SIO attack. Opcode sequences contain $1$ as
padding between Smali functions. After opcode shifting, sequences contain
additional opcodes (i.e. 22, 22, 255, 255 representing const, const, x, x).
The attack will find the best opcodes reducing the maliciousness score to
change the injected ”255”. Note that IMI attack works similarly but the added
opcodes represent const, if-eqx, x, x.

####  4.8.2 Attacks

The three attacks we implement are based on the instrumentation of Obfuscapk
(a Python modular tool used to obfuscate APKs in different ways [3]) and SecML
(an automatic framework to create feature-space adversarial examples [10]). In
particular, we created a custom injection tool capable of creating fully
working APKs modified through the injection of single smali instructions. More
specifically, the attacks are implemented as follows:

  1. 1.

Simple NOP: The first attack is simple and injects regular NOP instructions
inside the Smali code. That is performed by employing Obfuscapk on the test
samples.

  2. 2.

Simple Opcode & Impossible If: The other two attacks are a shift attack on
each Smali code method that is analyzed by the target system (i.e., all Smali
files up until $8192$ opcodes). The attack process is shown in Figure 1. The
steps for these attacks are as follows: First, we extract the opcodes like the
target system, shifting them to add more instructions based on the attack
variants. Then, we employed SecML optimizer and a modified version of the
discretize byte evasion [11, 17] to select opcodes x so that the confidence of
the malware class drops under a certain threshold. The two attack variants
are:

    1. (a)

Simple opcode attack (SIO): const, const, x, x.

    2. (b)

Impossible if attack (IMI): const, if-eqz, x, x

Listings 7 and 8 demonstrate the use of the simple opcode and impossible if
attacks.

⬇

1.method@ public static addTwoIntegers(II)I;

.registers@ 4 # inserting one more register

3 const v0, 0x8

const v3, 0xA

5 sub-int v0, v0, v3

xor-int v0, v0, v3

7 add-int v0, v1, v2

return v0

9.end method

Listing 7: A code snippet with simple opcode attack (SIO). Red lines are
directives, cyan lines are additions to the code.

⬇

1.method@ public static addTwoIntegers(II)I;

.registers@ 3

3 const v0, 0x1

if-eqz v0, :impossible

5 sub-int v0, v1, v2

xor-int v0, v1, v2

7 :impossible

add-int v0, v1, v2

9 return v0

.end method

Listing 8: A code snippet with impossible if (IMI). Red lines are directives,
cyan lines are additions to the code.

##  5 Experimental Details

In this section, we present the dataset, the two experiments, and the
experimental evaluation.

###  5.1 Dataset

The dataset consists of apps from Androzoo and VirusShare. Specifically,
Androzoo samples were labeled using VirusTotal APIs, considering the number of
sandboxes and antivirus vendors identifying them as malicious. Specifically,
if at least two of them flagged the app as malware, we labeled it accordingly.
The dataset encompasses around $10000$ applications (i.e., $5000$ APKs per
category) developed from $2008$ to $2022$ whose hashes are listed in Anonymous
GitHub. We divided the dataset into training and test sets at an 80/20 ratio.

###  5.2 Experiments

To measure the effectiveness of the attacks, we ran an experiment in which we
manipulated a set of random $\sim 1000$ malicious applications by each one of
the attacks. All three attacks were constructed employing ObfuscAPK and SecML.
We reconstructed all manipulated Smali files to build a working APK. Table 2
presents the classification and visibility results. We also run the simple
opcode attack with different lengths of injected opcode set. We tested this to
see how the visibility value changes according to different amounts of
injected content. We tested the same applications for this experiment as well.

Additionally, to assess whether the obfuscated APKs are still functional, we
tested $\sim 30\%$ of the manipulated apps using an emulated environment
employing Android Studio and Droidbot [18], a test input generator for
Android. The testing involves running the applications for one minute to
discern any discrepancies between the original applications and their modified
counterparts. The results are then analyzed to confirm that the obfuscated
APKs are functioning as expected.

###  5.3 Results - Exp 1: Assessing visibility

The goals of this experiment are to assess how specific NOP-based attacks
affect the classifier’s decision, and to understand what is the visibility
value.

Simple NOP attack In the case of the NOP attack, as described in Section
4.6.1, the $CCC$ value is equal to $1$ since it is easy, even automatically,
to recognize the presence of the injection and possibly eliminate it. Running
the attack on our target system, resulted in an accuracy rate of 0.92,
precision rate of 0.89, recall rate of 0.93, and f1-score of 0.91.

SIO attack. For the simple opcode attack (SIO) exampled in Listings 7, the CCC
value is computed as follows: $C_{1}(SIO)=0.82$, as the additional lines are
only 4 lines in comparison to the number of original method lines (i.e., 12 on
average). This computation has been done, averaging the clarity on all the
modified samples. $C_{2}(SIO)=0$, because its complexity rate is low.
$C_{3}(SIO)=1$, as there is more than one original variable in use. Thus,
$CCC(SIO)=0.53$. The SIO attack against the target system got an accuracy rate
of 0.51, a precision rate of 0.68, a recall rate of 0.24, and an f1-score of
0.35.

IMI attack. Listing 8 shows an example of the IMI attack we performed. In this
case, we can compute the CCC value as follows: $C_{1}(IMI)=0.82$, as there are
4 additional lines (excluding the tag) out of the total number of original
method lines (i.e., 12 on average). $C_{2}(IMI)=0.33$, as there is a use of a
conditional instruction. $C_{3}(IMI)=1$, as more than one original variable is
used. Thus, $CCC(IMI)=0.46$.

The IMI attack against the target system got an accuracy rate of 0.59, a
precision rate of 0.77, a recall rate of 0.38, and an F1-score of 0.51. Table
2 summarizes the classification and visibility results. The results highlight
a notable decrease in metrics during the performed attack. Specifically, the
accuracy rate drops by 32%-45%, and the recall rate declines by 48%-69%,
suggesting a significant reduction in the overall effectiveness of recognizing
malicious samples during the attack.

Choosing the third type of attack (i.e., _IMI_) might be more favorable for
evading human detectability. Despite having a higher recall than the SIO
attack, the CCC value is slightly lower. The SIO attack seems more effective
in means of recall and, as a consequence, a better competitor against the
detection system. However, as the CCC value shows, its visibility value is
higher. Therefore, it is less effective in a setting of both a detection
system and a human expert than in an IMI attack.

Table 2: Classification and visibility results. The metrics are precision, recall, f1-score, and our CCC visibility metric. |  Original APKs |  Simple NOP |  Simple Opcode |  Impossible IF
---|---|---|---|---
CCC |  - |  1 |  0.53 |  0.46
Accuracy |  0.92 |  0.60 |  0.51 |  0.59
Precision |  0.89 |  0.85 |  0.68 |  0.77
Recall |  0.93 |  0.45 |  0.24 |  0.38
F1-score |  0.91 |  0.61 |  0.35 |  0.51

###  5.4 Results - Exp 2: CCC vs Recall

A second experiment explored the relationship between CCC value and recall by
employing the simple opcode attack with varying numbers of injected opcodes.
Figure 2 illustrates the findings, revealing a kind of proportionality between
visibility and the number of injections. Indeed, as explained in Section 4.1,
a larger amount of injected opcodes increases the opportunity of a human
expert to identify the attacks (i.e. a higher visibility value). Additionally,
as expected, the recall decreases because the more opcodes chosen by the
attacker, the lower the model’s capability to recognize malicious samples is.

One would have expected that the CCC metric would have a minor effect on the
recall. This is a reasonable assumption, as the more opcodes injected in the
app, the more non-malicious it seems in the view of the detection system and
more visible in the view of a human expert. However, as we constructed our
metric, the CCC value was not solely computed by the amount of code injected
into the sample in the clarity element $C_{1}$, but also by the complexity of
the code $C_{2}$ and the connection between the injected and the original one
$C_{3}$ which normalize the increase in CCC value. Still, there is an increase
in visibility, which confirms our theory that more injected code means less
recall and higher CCC.

Figure 2: Relationship between CCC value and recall with SIO attack. The
values are the mean of the recall and CCC values for the test samples.

##  6 Discussion and Conclusion

This paper proposes a new visibility metric called CCC, which quantifies the
difficulty required to detect evasion adversarial examples. A common
misconception in the security community is to focus on strengthening the
detection systems against new threats without considering the human aspect.
Based on our novel metric, it is clear that both aspects of security should be
addressed, as attacks can overcome both. We analyze various evasion attacks
with traditional metrics and our CCC value drawing insights considering the
tradeoff between the efficacy, in terms of recall, and the visibility of the
attack, showing that a more effective attack is the one with a good
combination between CCC and recall. Our findings underscore the importance of
the CCC metric in bolstering a two-layered defence system, combining ML-based
detection with human expertise.

Our metric paves the way for understanding the connection between a human
expert’s view of a manipulated sample and the view of a detection system on
the same subject. However, our research has some limitations. First, we did
not fully evaluate the different weights of the three elements of CCC.
Optimization of the different components of CCC is an open issue that we aim
to explore in future work. Additionally, we want to expand the variety of
detection systems (from both academia and the industry) and evasion attacks in
Android malware detection to get a broader view of the impact of our metric in
this domain. At last, we aim to extend our metric’s applicability to other
malware detection domains, like PDF and PEs, which will be explored in future
works.

The threat of evasion attacks is yet to be mitigated. More attacks are devised
daily. We hope our new metric will aid in correctly mapping the risk levels of
attacks and train both human and ML-based detection systems against these
attacks.

Acknowledgements. This work was partially supported by project SERICS
(PE00000014) under the NRRP MUR program funded by the EU - NGEU.

## References

  * [1] Akritidis, P., Markatos, E.P., Polychronakis, M., Anagnostakis, K.: Stride: Polymorphic sled detection through instruction sequence analysis. In: IFIP TC11 20th International Information Security Conference, 2005. Springer (2005)
  * [2] Altenberg, L.: Emergent phenomena in genetic programming. In: Evolutionary programming—proceedings of the third annual conference. World Scientific (1994)
  * [3] Aonzo, S., Georgiu, G.C., Verderame, L., Merlo, A.: Obfuscapk: An open-source black-box obfuscation tool for android apps. SoftwareX 11 (2020), https://www.sciencedirect.com/science/article/pii/S2352711019302791
  * [4] Bacci, A., Bartoli, A., Martinelli, F., Medvet, E., Mercaldo, F., Visaggio, C.A., et al.: Impact of code obfuscation on android malware detection based on static and dynamic analysis. In: ICISSP (2018)
  * [5] Berger, H., Hajaj, C., Dvir, A.: Evasion is not enough: A case study of android malware. In: International Symposium on Cyber Security Cryptography and Machine Learning. Springer (2020)
  * [6] Biggio, B., Corona, I., Maiorca, D., Nelson, B., Srndic, N., Laskov, P., Giacinto, G., Roli, F.: Evasion attacks against machine learning at test time. In: Machine Learning and Knowledge Discovery in Databases - European Conference. vol. 8190 (2013), https://doi.org/10.1007/978-3-642-40994-3_25
  * [7] Biggio, B., Roli, F.: Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognition 84 (2018), https://www.sciencedirect.com/science/article/pii/S0031320318302565
  * [8] Chen, X., Li, C., Wang, D., Wen, S., Zhang, J., Nepal, S., Xiang, Y., Ren, K.: Android hiv: A study of repackaging malware for evading machine-learning detection. IEEE Transactions on Information Forensics and Security 15 (2019)
  * [9] Christodorescu, M., Jha, S.: Static analysis of executables to detect malicious patterns. In: 12th USENIX Security Symposium (USENIX Security 03) (2003)
  * [10] Demetrio, L., Biggio, B.: secml-malware: A python library for adversarial robustness evaluation of windows malware classifiers (2021)
  * [11] Demetrio, L., Coull, S.E., Biggio, B., Lagorio, G., Armando, A., Roli, F.: Adversarial exemples: A survey and experimental evaluation of practical attacks on machine learning for windows malware detection. ACM Trans. Priv. Secur. 24(4) (2021), https://doi.org/10.1145/3473039
  * [12] Faruki, P., Bharmal, A., Laxmi, V., Gaur, M.S., Conti, M., Rajarajan, M.: Evaluation of android anti-malware techniques against dalvik bytecode obfuscation. In: 2014 IEEE 13th TrustCom (2014)
  * [13] Goodfellow, I., Shlens, J., Szegedy, C.: Explaining and harnessing adversarial examples. In: 3rd ICLR (2015), http://arxiv.org/abs/1412.6572
  * [14] Hammad, M., Garcia, J., Malek, S.: A large-scale empirical study on the effects of code obfuscations on android apps and anti-malware products. In: Proceedings of the 40th international conference on software engineering (2018)
  * [15] Kaspersky: It threat evolution in q2 2023. mobile statistics (2023)
  * [16] Knoop, J., Rüthing, O., Steffen, B.: Partial dead code elimination. ACM Sigplan Notices 29(6) (1994)
  * [17] Kolosnjaji, B., Demontis, A., Biggio, B., Maiorca, D., Giacinto, G., Eckert, C., Roli, F.: Adversarial malware binaries: Evading deep learning for malware detection in executables (2018), https://doi.org/10.23919/EUSIPCO.2018.8553214
  * [18] Li, Y., Yang, Z., Guo, Y., Chen, X.: Droidbot: A lightweight ui-guided test input generator for android. In: 39th ICSE-C. IEEE Press (2017), https://doi.org/10.1109/ICSE-C.2017.8
  * [19] Lin, D., Stamp, M.: Hunting for undetectable metamorphic viruses. Journal in computer virology 7 (2011)
  * [20] McLaughlin, N., Martinez del Rincon, J., Kang, B., Yerima, S., Miller, P., Sezer, S., Safaei, Y., Trickel, E., Zhao, Z., Doupé, A., Joon Ahn, G.: Deep android malware detection. CODASPY ’17 (2017), https://doi.org/10.1145/3029806.3029823
  * [21] Pierazzi, F., Pendlebury, F., Cortellazzi, J., Cavallaro, L.: Intriguing properties of adversarial ML attacks in the problem space. In: 2020 IEEE Symposium on Security and Privacy (2020), https://doi.org/10.1109/SP40000.2020.00073
  * [22] Rastogi, V., Chen, Y., Jiang, X.: Catch me if you can: Evaluating android anti-malware against transformation attacks. IEEE Transactions on Information Forensics and Security 9(1) (2013)
  * [23] Rastogi, V., Chen, Y., Jiang, X.: Droidchameleon: evaluating android anti-malware against transformation attacks. In: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security (2013)
  * [24] Reilly, E.D.: No-op. In: Encyclopedia of Computer Science (2003)
  * [25] Rosenberg, I., Shabtai, A., Rokach, L., Elovici, Y.: Generic black-box end-to-end attack against state of the art api call based malware classifiers. In: 21st International Symposium, RAID 2018. Springer (2018)
  * [26] Shankarapani, M.K., Ramamoorthy, S., Movva, R.S., Mukkamala, S.: Malware detection using assembly and api call sequences. Journal in computer virology 7 (2011)
  * [27] Vasan, D., Alazab, M., Venkatraman, S., Akram, J., Qin, Z.: Mthael: Cross-architecture iot malware detection based on neural network advanced ensemble learning. IEEE Transactions on Computers 69(11) (2020)
  * [28] Wojtek Kaliciński: Smallerapk, part 1: Anatomy of an apk, https://medium.com/androiddevelopers/smallerapk-part-1-anatomy-of-an-apk-da83c25e7003, medium - Android Developers. Online - Accessed: 2023-11
  * [29] Zheng, M., Lee, P.P., Lui, J.C.: Adam: an automatic and extensible platform to stress test android anti-virus systems. In: International conference on detection of intrusions and malware, and vulnerability assessment. Springer (2012)

##  Appendix 0.A Full Calculations - Code Examples (Section 4.6)

In this appendix, we show the full calculations of the examples in Section
4.6.

###  0.A.1 Simple Nops

The following calculations refer to the addition of three NOPs.

For $C_{1}(EX_{1})$, the value is 1, as $EX_{1}$ includes explicit NOPs (at
least one). This is a red flag for manipulation of an original code.

For $C_{2}(EX_{1})$, we get:

$C_{2}(EX_{1})=\sum_{i=1}^{n}\frac{C_{2}(l_{i})}{n}=\frac{0}{2}+\frac{0}{2}=0$

, as EX1 includes only NOPs.

For $C_{3}(EX_{1})$, we get:

$C_{3}(EX_{1})=\sum_{i=1}^{n}\frac{C_{3}(l_{i})}{n}=\frac{0}{2}+\frac{0}{2}=0$

Thus, the CCC of EX1 is:

$\displaystyle CCC(EX_{1})$
$\displaystyle=w_{1}*C_{1}(EX_{1})+w_{2}*(1-C_{2}(EX_{1}))+w_{3}*(1-C_{3}(EX_{1}))$
$\displaystyle=0.4*1+0.2*(1-0)+0.4*(1-0)=1$

###  0.A.2 Loop & Addition (EX_2)

The following calculations refer to a loop with simple addition. For these
calculations, we consider the lines of the constant, loop increment,
condition, and additional additions (the tags of the loops are eliminated from
the computations, as they are basically semantic pointers). Thus, the
additional code in each function is 5 lines, and the original code in each
function consists of 2 lines.

For $C_{1}(EX_{2})$, we get:

$C_{1}(EX_{2})=\sum_{i=1}^{n}\frac{\frac{e^{|l_{i}|}}{e^{|l_{i}|}+|s_{i}|}}{n}=\frac{\frac{e^{5}}{e^{5}+2}+\frac{e^{5}}{e^{5}+2}}{2}=0.98$

For $C_{2}(EX_{2})$, as EX2 includes a loop, we get:

$C_{2}(EX_{2})=\sum_{i=1}^{n}\frac{C_{2}(l_{i})}{n}=\frac{0.66}{2}+\frac{0.66}{2}=0.66$

For $C_{3}(EX_{2})$, we get:

$C_{3}(EX_{2})=\sum_{i=1}^{n}\frac{C_{3}(l_{i})}{n}=\frac{1}{2}+\frac{1}{2}=1$

Thus, the CCC of EX2 is:

$\displaystyle CCC(EX_{2})$
$\displaystyle=w_{1}*C_{1}(EX_{2})+w_{2}*(1-C_{2}(EX_{2}))+w_{3}*(1-C_{3}(EX_{2}))$
$\displaystyle=0.4*0.98+0.2*(1-0.66)+0.4*(1-1)=0.46$

###  0.A.3 Condition & API Call (EX_3)

The following calculations refer to a condition and an API call. For these
calculations, we consider the lines of the condition and the print command
(the tags of the condition are eliminated from the computations, as they are
basically semantic pointers). Thus, the additional code in each function is 2
lines, and the original code in each function consists of 2 lines.

Thus, we get for $C_{1}(EX_{3})$:

$C_{1}(EX_{3})=\sum_{i=1}^{n}\frac{\frac{e^{|l_{i}|}}{e^{|l_{i}|}+|s_{i}|}}{n}=\frac{\frac{e^{2}}{e^{2}+2}+\frac{e^{2}}{e^{2}+2}}{2}=0.79$

For $C_{2}(EX_{3})$, as EX3 includes a condition, we get:

$C_{2}(EX_{3})=\sum_{i=1}^{n}\frac{C_{3}(l_{i})}{n}=\frac{0.33}{2}+\frac{0.33}{2}=0.33$

For $C_{3}(EX_{3})$, we get:

$C_{3}(EX_{3})=\sum_{i=1}^{n}\frac{C_{3}(l_{i})}{n}=\frac{0.5}{2}+\frac{0.5}{2}=0.5$

Thus, the CCC of EX3 is:

$\displaystyle CCC(EX_{3})$
$\displaystyle=w_{1}*C_{1}(EX_{3})+w_{2}*(1-C_{2}(EX_{3}))+w_{3}*(1-C_{3}(EX_{3}))=$
$\displaystyle=0.4*0.79+0.2*(1-0.33)+0.4*(1-0.5)=0.65$