## Static Analysis

Static analysis refers to methods used to analyze programs without requiring their execution. This analysis methodology leverages the definition of syntactic rules to scan programs so as to extract descriptive features.

For instance, to run on Windows an executable file must be in the *Portable Executable* (PE) file format. The layout of a PE file comprises a number of headers and sections that are read by the Windows loader when the file is mapped into memory. Figure 6.2 (page 309) shows the layout of different headers comprised in a PE file.

By simply parsing the sequence of bytes in the binary file, a static analyzer can find out that it is a PE file because it must start by the signature bytes (i.e. magic number) 'MZ' (0x4D 0x5A) and have a pointer at the offset 0x3C that points to the beginning of the COFF header, which starts with the magic number 'PE\0\0' (0x50 0x45 0x00 0x00)—otherwise the Windows loader does not map the file into memory. Likewise, the static analyzer can obtain a lot of other information contained in the header, such as:

- the target CPU architecture (e.g. x64, x86, ARM, etc) [field: Machine];

- the compilation timestamp [field: TimeStamp];

- whether the debug information was stripped [field: IMAGE_FILE_DEBUG_STRIPPED];

- whether it is a system file or a user program [field: IMAGE_FILE_SYSTEM];

- exported functions [export table];

- imported functions [import table];

- etc.

However, some fields in the header do not impact the correct execution of the file and therefore they can be modified by malware authors to mislead future analysis. For example, the field TimeStamp can reveal when the malware was generated, however it can be altered by the author to contain a fake timestamp; in some cases, the compiler sets a fixed timestamp to all generated files (e.g. Borland Delphi and its timestamp 1992-06-19 22:22:17 (Friday)), which can unwittingly provide indicators about the language and compiler used.

Another very useful method of static analysis is (machine) code disassembling, in which the instructions and identifiable data structures are parsed from the machine code of a program. The goal is to translate the sequences of bytes into (meaningful) syntactic units of the assembly language (asm) [71].
It is also possible to attempt to reconstruct the (high-level) source code directly from the machine code, a process known as *decompilation* (as it undoes the compilation process). This process is way harder than disassembling because many details concerning the abstractions of the high-level language (e.g. variables, arrays, objects, functions, etc.) are lost in the compilation process, whereas disassembling is about straightforward code translation (from machine code to asm). Figure 2.17 shows the transformations of a “hello world” code written in C.

<figure><img src="image_26.png" /><figcaption>Figure 2.17 – [De]compilation and [de]assembling of a “hello world” code in C.</figcaption></figure>

A well-established representation that facilitates the analysis of the execution flow of a program is the *control-flow graph* (CFG) [4]. It is a directed-graph representation of the program in which nodes correspond to *basic blocks* and edges correspond to deviation in the control flow; basic blocks are straight-line sequences of instructions that do not contain any jumps, with exception of the last instruction, and in which the first instruction is targeted by another deviation (e.g. jump, function call) in the control flow.

Figure 2.18 shows two disassembling representations of the same binary code. The left-hand side presents a plain textual representation in asm using *objdump* [26], whereas the right-hand side presents a CFG representation using *IDA Free* [231].

Disassembling and decompilation are operations tightly linked to the syntax of the analyzed (machine) code. However, as they are related to the instructions of the code, they can also capture traits of the code's semantics (which is not the case for all static analysis methods, e.g. file format analysis).
<figure><img src="image_27.png" /><figcaption>Figure 2.18 – Disassembling of a binary code: plain asm (left) and CFG (right).</figcaption></figure>

Dynamic Analysis

Dynamic analysis refers to methods used to analyze programs requiring their execution.
This analysis observes the program during its execution, taking into account how the exe-
cutable code evolves as it runs and how it interacts with other components of the system
(e.g. memory, file system, etc).

Standard *debugging* is a basic example of analysis method that can be considered as part of the dynamic analysis. It consists of an interactive method intermediated by a debugger that interacts with the operating system and alters parts of the code on the fly to inspect and control the execution of the code.

Figure 2.19 shows the screen of a debugging process using the GNU Debugger (GDB) [224]. It lists the data contained in each register, the disassembling of the code located in the surroundings of the address pointed by the instruction pointer (RIP) and the content located in the stack of the process. It is also possible to note that the execution of the code was held at the address whose tag is <main+4> and that the debugger awaits an input command.

Other tools such as *ProcMon* [188] interact with the operating system —in this case, through a Windows device driver [245] —to collect file system, registry and process/thread
<figure><img src="image_28.png" /><figcaption>Figure 2.19 – Disassembling of a binary code: plain asm (left) and CFG (right).</figcaption></figure>

activity in real time. Figure 2.20 shows the dashboard of ProcMon with a list of activities (referred as *events*) that were captured by the tool. Figure 2.21 shows the usage of ProcMon to capture details of running processes.

Other tools such as the *Wireshark* [57] use libraries for capturing network packets (libpcap on Unix and Npcap on Windows) in order to intercept (i.e. "sniff") the network traffic. For instance, Wireshark allows to perform deep inspection of hundreds of protocols, capture and analyze live network streams, and has many other useful capabilities for networking analysis. Figure 2.22 shows the Wireshark dashboard with a filter to only display TCP packages.

There are a lot of different dynamic analysis methods and tools that can be useful for
<figure><img src="image_29.png" /><figcaption>Figure 2.20 - Dashboard of ProcMon showing a list of intercepted events.</figcaption></figure>

malware analysis. They can target a specific piece of code (e.g. debugging), or the interactions of running processes and the operating system (e.g. file system monitoring, process monitoring, network sniffing, etc).

**Isolation (sandbox)** Independently of the chosen method, dynamic analysis unfolds as the code runs; when it comes to malware analysis, running unknown code can put the system in jeopardy. Therefore, a major concern in dynamic analysis of malware is *isolation*, i.e. scope limitation of processes that run on the system. This scope can be related to network, file system, process rights and interactions, etc.

The scope within the boundaries imposed by a security mechanism is usually referred as *a sandbox*. The most common isolation strategy involves the virtualization of a guest VM on which the unknown binary codes are executed and the data generated during the execution are collected for analysis. While this setup is the popular, it is important to note that the
<figure><img src="image_30.png" /><figcaption>Figure 2.21 – Details of process captured by ProcMon including image path, command line, user and session ID.</figcaption></figure>

concept of *sandbox* extends beyond this particular case.

Anti-Analysis Techniques

Anti-analysis techniques includes a set of different techniques intended to thwart or de-
lay the reverse engineering of a given piece of code or to identify whether it is running in-
side a sandbox. In turn, anti-reverse engineering techniques include techniques for anti-
disassembly, anti-debugging and various code obfuscation techniques. Malware leverage
these techniques to remain as undetectable for as much time as possible.

A very common technique used by the vast majority of malware in the wild is code ob-
fuscation through packing, intending to hinder static analysis. In its simplest form, packing
transforms the binary code of a program into a new representation in which the original
content is either compressed or encrypted and this process is reversed by a small unpacking
routine that reverses this transformation in runtime. Figure 2.23 shows the transformation
scheme of a simple packer. For more details about runtime packers refer to the work of
Ugarte et al [290].
<figure><img src="image_31.png" /><figcaption>Figure 2.22 – Wireshark dashboard with the inspection of TCP network packages.</figcaption></figure>

Code disassembling is targeted by some techniques like data and instruction interleaving, instructions reordering, abnormal conditions (e.g. JMP with the same target), opaque predicates, dead code insertion, etc.

Other techniques target dynamic analysis. This is the case for anti-debugging techniques, that attempt to detect whether a program execution is being inspected by a debugger. It can be done in many different ways, such as using the operating system API to check whether the running process is being traced (e.g. *IsDebuggerPresent*, *CheckRemoteDebuggerPresent*, *Nt-QueryInformationProcess*, *OutputDebugString* of the Windows API); checking the data structure of the running process to identify data flagged when a debugger in use (e.g. *BeingDebugged*, *ProcessHeap*, *NTGlobalFlag* of the Window's Process Environment Block); checking indicators on the system (e.g. debuggers default installation paths, residue in live memory

<footnote n="14">14. Image published at https://www.joesecurity.org/blog/8506317946374998489 (accessed October 2022)</footnote>
such as window name, etc); scanning the code of the process in memory to discover mod-
ifications made by a debugger (e.g. the existence of INT instructions); checking the time
difference between two instructions, which is supposed to be smaller than a threshold oth-
erwise it indicates the the code might be under debugging. When a debugger is detected, the
malware can decide to stop its execution or to modify its behavior skipping the execution of
malicious segments of the code.

Similarly, a malware can attempt to identify whether it is running on a virtualized en-
vironment to control its behaviour. Anti-VM techniques include the verification of indica-
tors of virtualization on the system (e.g. known files and folder created by expansion pack-
age such as VMware Tools, registry keys and values, standardized values for MAC address,
residues in live memory, etc) and presence of return value of instructions that differ on vir-
tualized environments (e.g. SIDT, SGDT, SLDT, CPUID, etc).

2.3.2 Malware Analysis Primitives

A plethora of malware analysis frameworks have been proposed. In general, however,
they are presented as full-fledged systems designed to fulfill specific objectives (e.g. mal-
ware detection, malware clustering) without following well-defined standards as to the fun-
damental building blocks of malware analysis. This hinders re-use and impairs analysis and
comparison of components conceived in different works.

**In this section our goal is to identify and introduce an organization related to malware analysis primitives that allows to describe most (ideally all) malware analysis frameworks.**

These primitives are abstract methods that provide a high level description of the tasks generally performed by malware analysis frameworks and that correspond to their most basic building blocks.

For this, we inspire from the purpose-oriented structure proposed in the survey by Ucci *et al* [287]. The authors define the following major objectives —*malware detection, malware similarity analysis* and *malware category detection* —as follows:

**Malware detection** aims to identify traits in programs that allow to assess whether a given sample is malicious. Depending on the context, this assessment can target a given malware family or some specific characteristic (e.g. if the file has a ZIP format, etc). Historically, this was the first major objective of malware analysis and it still stands as the most prevalent objective in malware research.

**Malware similarity analysis** is a broad topic, which concentrates on the simi-
larity/dissimilarity across sets of program instances. Ucci *et al* [287] split this topic
in four objectives: *variants detection, families detection, similarities detection and differences detection*.

**Malware category detection** aims to assign categories (e.g. spyware, ransomware, etc) to samples. However, albeit defined in the survey by Ucci et al [287], we do not further detail this topic because it conflicts with our axiology<fnref n="15" /> (**Axiology-1**, page 55). Malware category presupposes the existence of ontological traits that go beyond straightforward lineage (e.g. code reuse), since instances of the same category do not necessarily belong to the same family (otherwise categories would be equivalent to families). Furthermore, if an instance would belong to such category, this would implicate that such instance is a malware. However, according to our axiology, there are no ontological differentiation of malware and software at the *realization level*, which makes us reject this research path.

Both malware detection and malware similarity analysis are based on features generally extracted through either static or dynamic analysis, or a combination of both. Therefore, before detailing each topic related to the malware analysis objectives, we provide an overview of features frequently used for malware detection and similarity analysis as well as their usage in a typical malware analysis workflow as highlighted by Ucci et al [287], namely:

**Byte sequences** target the byte-level content of the machine code. This feature type includes chunks of bytes of fixed or variable length, sliding window of *n* bytes (known as *n*-grams), matching a given encoding pattern (i.e. ASCII strings). This feature type is widely studied and used in practice, since it is very versatile and can be easily extracted using static analysis.

**Opcode**s target machine-level operations contained in a binary file (program). Since the sample behaviour is determined by its instructions, the opcodes can to some extent represent the sample semantics. Opcode frequency is one of the most commonly used feature type [287].

**File characteristics** target certain information such as the header data that can be statically parsed from known structures. These information provides a large set of valuable information such as sections, imports, symbols, compilers, etc.

**API and System Calls** target the calls invoked during the sample execution, which can include external DLLs, calls to the operating system's API or direct system calls. They can be extracted through either static or dynamic analysis, but the latter is considered more trustworthy as information about function imports and system calls

<footnote n="15">15. **Axiology-1**: pursuing *no ontological difference between malware and software at the “realization level”*;</footnote>
can be easily obfuscated to counter static analysis. Similarly to opcodes, APIs and
system calls are related to the semantics of the sample —on a higher level though.

**Filesystem Activity** targets the operations executed by a sample to interact with the filesystem. In Windows it includes the information about the *Windows Registry*. By monitoring these activities it is possible to detect attempts to gain persistence in the system.

**Network Activity** targets the data exchanged over the network. The contacted addresses and the content of the network traffic can unveil communications with external controllers that participate in a cyberattack.

These features extracted from the sample are then transformed in order to be analyzed.
For malware detection, the goal is to identify the feature components that can better distin-
guish a given sample from the universe of all samples —a comparison of type 1-to-N. For
similarity analysis, the goal is to identify features that allow to distinguish and compare sets
of samples —comparisons of type 1-to-1, N-to-1 and N-to-N.

Figure 2.24 shows a typical malware analysis workflow that applies to both malware de-
tection and malware similarity analysis. It summarizes the general analysis process, in which
the workflow starts with the analysis of unknown samples in order to extract raw features that
are then transformed and analyzed. Additionally, the information obtained from the feature
analysis can be fed back into the workflow in order to enrich the information contained in
the raw features with extra metadata about the sample under analysis. This feedback loop
can take place in the form of malware signatures, malware classifiers, and others.

Next, we detail the practical objectives —malware detection and malware similarity anal-
ysis —and then we introduce a semi-formal description of malware analysis primitives.

Malware Detection

The main objective of *malware detection* is to provide methods that allow to identify ma-
licious traits in unknown programs. Incidentally, these methods can be used to identify
whether some given sample belongs to a specific malware family or whether it matches a
certain profile (e.g. being a PE file, being a ZIP file, etc).

The main approach used in practice is signature-based detection, as it pioneered the ad-
vent of malware detection and it has greatly evolved ever since. Recently, machine learning
has led to the development of several new approaches for detecting malware, reflecting its
increasing use in this area —refer to the survey by Singh and Sigh which includes many differ-
ent malware detection schemes (18 schemes based on syntactic signatures and 22 schemes
based on behavioral signatures) [263].

We now elaborate on signature-based detection—in particular, syntactic signatures with pattern matching—since it is the most fundamental and dominant method used in practice. Moreover, we use signature-based detection later on as benchmark for our proposed methods.

**Signature-based detection** Signatures refer to distinctive information corresponding to some set of samples that allows detecting them. Features extracted (and transformed) from one or multiple binary files are used to create a signature, which can be compared to features from an unclassified binary to determine whether it matches the signature.

The simplest kind of signatures are syntactic signatures [262, 277] whose detection rules are based on the binary file syntactic properties (like length, entropy, number of sections, or presence of certain strings). Alternatively, behavioral signatures [262, 277] can be created from the binary file behavioral properties, like file operations, registry operations, network operations, API calls, etc.

**Syntactic Signature (Pattern Matching)** Syntactic signatures are used to classify binaries by looking at particular patterns in their code. Due to the simplicity of syntactic pattern matching, these techniques tend to be very effective and efficient in practice. Nonetheless, it is not trivial to create and maintain syntactic signatures that are concomitantly specific enough to match only to the desired samples, but not so specific that they would match only very few instances of close variants. Furthermore, a signature may stop matching a certain file if it changes just marginally (maybe even by only a single byte), which is considered to be one of the main drawbacks of this method.

The principle of operation of syntactic signatures is to identify and record matching rules for sequences of bytes that describe proprieties such as file checksum [2], type, API calls [129], etc. Despite the limitations of syntactic signatures [220]—notably against obfuscation methods like packing—static syntactic signatures are largely employed in malware analysis. For example, ClamAV [52] allows using syntactic signature in the YARA [225] format for protection against malicious files, and VirusTotal [294] provides an interface that takes YARA signatures to lookup matching files across its whole database. Here we present the principles of syntactic pattern matching, providing three practical examples with different tools.

PEiD<sup>16</sup> is an old well-known tool used to detect PE malware, packers, and compilers.

<footnote n="16">16. Link: https://www.aldeid.com/wiki/PEiD</footnote>
Although the original developers have discontinued this tools, its user community continues to use and update it frequently due to its simple design and effectiveness.

PEID defines an underlying grammar for the creation of new matching rules. The inclusion of new rules can target a new malware, packer, or compiler without requiring updating the tool. As an example of a rule, we display the signatures for matching .NET objects below:

1 [.NET DLL -> Microsoft]
2 signature = 00 00 00 00 00 00 00 00 00 5F 43 6F 72 44 6C 6C
3 4D 61 69 6E 00 6D 73 63 6F 72 65 65 2E 64 6C 6C 00 00 ??
4 00 00 FF 25
5 ep_only = false
6
7 [.NET executable -> Microsoft]
8 signature = 00 00 00 00 00 00 00 00 5F 43 6F 72 45 78 65
9 4D 61 69 6E 00 6D 73 63 6F 72 65 65 2E 64 6C 6C 00 00 00
10 00 00 FF 25
11 ep_only = false
12
13 [.NET executable]
14 signature = FF 25 00 20 40 00 00 00 00 00 00 00 00 00 00 00
15 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
16 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
17 ep_only = true

Each rule starts with a string identifier between square brackets, which is displayed to the user when the rule is matched. The lines starting with the word *signature* (i.e. lines 2, 8 and 14) indicate the beginning of a signature definition as a byte array, where the marker "??" is used to match any byte. Finally, the *ep_only* line indicates whether the rule is expected to match only the bytes at the binary entry point or anywhere in the file.

The main limitation of PEID is the lack of expressiveness in its grammar rules. For instance, the most recent PEID database<fnref n="17" /> uses 829 rules (out of 3714) just to define version 1.25 of the VMProtect<fnref n="18" /> virtualization packer.

Another tool used for pattern matching on files is **DIE**<fnref n="19" />, which stands for “Detect It Easy”. DIE supports a JavaScript-like scripting language for creating signatures, which provides more expressiveness than PEID, specially due to the support of matching conditions.

<footnote n="17">17. Link: https://handlers.sans.org/jclausing/userdb.txt</footnote>

<footnote n="18">18. Link: http://vmpsoft.com/</footnote>

<footnote n="19">19. Link: https://github.com/horsicq/Detect-It-Easy</footnote>
An example of a DIE rule is shown below:

```javascript
// DIE's signature file

init("protector", "PE Intro");

function detect(bShowType, bShowVersion, bShowOptions) {
  if (PE compared PE "8B04249C60E8 5D81ED 80BD 0F8548")) {
    sVersion = "1.0";
    bDetected = 1;
  }
  return result(bShowType, bShowVersion, bShowOptions);
}
```

The rule matches files protected with PE Intro, which is detected by an expected sequence of bytes at the entry point. The rule starts by declaring a new signature at `init` and then by proving a description of the rule in the `detect` function.

Like PEiD, DIE has a simple flag (`PE compared PE .` as wildcards to match any byte. Rule matching is indicated by the variable `bDetected`, which is set to 1. DIE also supports more sophisticated rules that depend on multiple conditions and code reuse as in the rule below.

```javascript
// DIE's signature file

includeScript("rar");

function detect(bShowType, bShowVersion, bShowOptions) {
  detect_RAR(1, bShowOptions);
  return result(bShowType, bShowVersion, bShowOptions);
}
```

The main drawbacks of DIE are its verbose syntax and the need for an ad-hoc script for each rule; on top of that, DIE lacks detailed documentation and advanced features such as annotations or modularity.

The current de facto standard grammar/tool for the creation of syntactic signature is Yara [319]. Yara rules are defined using a JSON-like format, which provides higher expressiveness than PEiD and DIE rules.
Yara syntax defines three main fields: *meta*, which contains metadata that help identify the rule; *strings*, which contains a list of hexadecimal strings, text strings and regular expressions; *condition*, which defines boolean expressions over the elements present in the *strings* section.

```yara
rule silent_banker : banker
{
    meta:
        description = "This is just an example"
        threat_level = 3
        in_the_wild = true
    strings:
        $a = {6A 40 68 00 30 00 00 6A 14 8D 91}
        $b = {8D 4D B0 2B C1 83 C0 27 99 6A 4E 59 F7 F9}
        $c = "UVODFRYSIHLNWPEJXQZAKCBGMT"
    condition:
        $a or $b or $c
}
```

The rule above defines a Yara signature that matches files that contain any of the listed strings. Whenever a signature is matched, the tool outputs the rule name (i.e. *silent_banker*). On the same first line and separated by a colon, the string *banker* identifies the rule tag.

Yara supports many useful features that simplify the writing of signatures, such as modifier marks for strings (e.g. *ascii*, *wide*, *xor*), positional matching (address or offset), file size condition, extension modules (e.g. *PE*, *ELF*, *Cuckoo*), etc. Furthermore, Yara is a lightweight and fast tool that is available on multiple platforms (i.e. Windows, Linux and MacOSX) and can be accessed through interfaces such as CLI and Python scripts.

## (Malware) Similarity Analysis

Similarity analysis is a broad topic that concentrates on the analysis of similarity/dis-similarity across groups of software instances, which includes applications such as *variants detection*, *families detection*, *similarities detection* and *differences detection*, defined as follows:

**Variants detection** aims to develop methods that allow to recognize that an unknown sample is actually a variant of a known malware.

**Family detection** aims to develop methods that given an unknown sample allows to identify families the sample is likely to belong to.

**Similarity detection** consists in identifying common parts or any kind of commonalities in multiple samples.
**Differences detection** is in many aspect similar to similarity detection, but it targets differences instead of commonalities.

The features that dominate this axis of malware analysis are based on APIs and System Calls as well as behavioral features such as file operations, registry operations and network operations. All works but one analyzed in the survey by Ucci et al [287] are based on collections of APIs and System Calls.

As for the feature analysis, *variants detection* includes but is not limited to schemes based on Hidden Markov Models, rule-based classifiers, variants of the decision tree algorithm, clustering with locality sensitive hashing and DBSCAN clustering [287]. Family detection includes but is not limited to schemes based on variants of graph matching, logistic regression, variants of the decision tree algorithm, K-NN, SVM, neural networks, K-Means and K-Medoids algorithms, prototype-based clustering and hierarchical clustering [287]. Similarity detection includes but is not limited to schemes based on logistic regression, SVM, clustering with locality-sensitive hashing, prototype-based clustering and hierarchical clustering [287]. Differences detection includes but is not limited to schemes based on rule-based classifier, logistic regression, variants of the decision tree algorithm, K-NN, clustering with locality-sensitive hashing and prototype-based clustering.

## Malware Analysis Primitives

Here we propose *primitives* that are frequently found in malware analysis and describe them in a semi-formal notation. They can be seen as basic building blocks to design malware analysis frameworks without dealing with implementation details. Our intention is to **clearly define a taxonomy of malware analysis** that we use henceforth in the thesis. As to the best of our knowledge such formulation is the first-of-its-kind, thus it figures as contribution of the thesis.

Let $\mathcal{S}$ represent the set of [transformed features extracted from] *samples* that are subject to the analysis of a malware analysis framework. Let $\sim$ denote an equivalence relation on $\mathcal{S}$. We define as *family* ($\mathcal{F}_{\sim}$) the equivalence class $\mathcal{F}_{\sim} = [s]_{\sim}$, where $[s]_{\sim} := \{s' \in \mathcal{S} : s' \sim s\}$. If $s$ is considered malicious, then $\mathcal{F}_{\sim}$ is a *malware family*.

For a given $s, s_1, s_2 \in \mathcal{S}$ and a set of family $\{F_i\}$ such that $\bigcup\{F \in \{F_i\}\} = \mathcal{S}$, we define the following malware analysis primitives:
## Detection

$$ \mathcal{F}_{Detection}(s, F) = \begin{cases} 1, & \text{if } s \in F \\ 0, & \text{otherwise} \end{cases} \qquad (\text{Detection}) $$

where $F \in (F_i)$.

In the case of malware detection, $F$ corresponds to a family that includes all malware instances of $\mathcal{S}$.

## Similarity

$$ \mathcal{F}_{Sim}(s_1, s_2) \to \sigma \in [0, 1] \qquad (\text{Similarity}) $$

where $\sigma$ is proportional to the similarity between $s_1$ and $s_2$; $\sigma = 0$ denotes total dissimilarity, whereas $\sigma = 1$ denotes total similarity between $s_1$ and $s_2$.

## Search

$$ \mathcal{F}_{Search}(s) \to \{F, \emptyset\} \qquad (\text{Search}) $$

where $F = \{s' \in \mathcal{S} | s' \sim s\}$. If no such family exists in $(F_i)$, then $\mathcal{F}_{Search}$ outputs $\emptyset$.

## Classification

$$ \mathcal{F}_{Class}(s, \{F_i\}) \to \{i, \emptyset\} \qquad (\text{Classification}) $$

where $i$ is the index of $(F_i)$ such that $\forall F_i = \{s' \in \mathcal{S}, s' \sim s\}$.

If no such family exists in $(F_i)$, then $\mathcal{F}_{Class}$ outputs $\emptyset$.

## Clustering

$$ \mathcal{F}_{Clust}(\mathcal{S}) \to \{P_i\} \qquad (\text{Clustering}) $$

where $\{P_i\}$ is the set of disjoint partitions of $\mathcal{S}$ such that $\cup \{P_i\} = \mathcal{S}$.

## 2.4 Discussion

A key challenge currently in malware analysis is to respond to the quick expansion of malware in terms of prevalence and complexity, while traditional human-centered methodologies in use cannot evolve at the same pace. This situation imposes the coalescence of traditional and machine-centered methods, hence the ever growing influence of machine learning in malware analysis.
Considering figure 2.24 (page 109), with exception of the binary analysis phase, the de-
picted workflow could represent the phases of a standard machine learning analysis. Yet,
the adversarial model of malware analysis entails major challenges in feature extraction, as
malware creators use multiple techniques intending to mislead analyses, which makes the
application of machine learning methods particularly intricate in this case.

Furthermore, there are severe ontological and epistemological matters concerning mal-
ware (extensively discussed in chapter 1, page 25) that affect the usage of machine learning
in malware analysis. Humans can easily identify cats and dogs on pictures; however, when
it comes to malware classification, the categorization can become much more blurry —the
so-called “*gray zone*”, as it the case with PUPs (c.f. section 1.2.1, page 27) —thus having a
direct impact not only on supervised models, but also on any kind of external evaluation of
unsupervised models.

Another aspect that emerges from the combination of both research fields is (to some extent) the lack of congruence of some concepts and terminologies. For instance, the concept of “classification” in machine learning is closer to the concept of “detection” than “classification” itself in malware analysis. Such discrepancies can be source of misunderstanding when communicating about these fields. In this thesis we privilege the terminology issued from the malware analysis field, as defined in section 2.3 (page 87) and semi-formalized in section 2.3.2 (page 105).

**2.5 Conclusion**

In this section we presented the general, contextual background of the thesis. We started
with a presentation of topics related to machine learning, including definitions and termi-
nology as well as topics of supervised and unsupervised learning. Then we presented topics
of malware analysis, with special focus on malware in the form of binary files, before dis-
cussing some issues related to the combination of both fields.

Now that the thesis background is presented, we will move to the nub of the thesis where
our main contributions will be presented.
<figure><img src="image_32.png" /><figcaption>Figure 2.23 – Transformation scheme of a simple packer (file system view and memory view) ¹⁴.</figcaption></figure>
<figure><img src="image_33.png" /><figcaption>Figure 2.24 – Typical malware analysis workflow.</figcaption></figure>
<figure><img src="image_34.png" /></figure>
# CALL TRACING WITH SYMBOLIC EXECUTION

## 3.1 Introduction

Typically, the analysis of (malware) programs follows the dynamic and/or static analysis approaches. In dynamic analysis, programs are executed in an isolated environment with aim to understand their behavior. In static analysis, the program structures are parsed to extract data of interest without executing it.

The main limitation of dynamic analysis is code coverage, because the correct execution of the program strongly depends on the context provided by the analysis environment (e.g. sandbox), which makes it possible to finish the analysis without ever going over the most important segments of the program code. In malware analysis this problem is aggravated by the fact that malware often employ various techniques to hinder dynamic analysis.

Static analysis has a complete view over the binary code of the analyzed programs, but not executing them poses severe limitations to the analysis when the programs implement runtime modifications in their code or in any descriptive data. This is a major issue for malware analysis since malware very commonly use evasion techniques to thwart static analysis (e.g. packing, virtualization, etc), as discussed in section 2.3.1 (page 88).

As an alternative to cope with the limitations of dynamic and static analysis, we consider the use of *symbolic execution*. Symbolic execution is a method for program analysis that lies between static and dynamic analysis, and which *emulates* the execution of binary code while keeping a fine control over all elements of this analysis. Symbolic execution has been increasingly used as technique of *Formal Methods* to analyzed the correctness, reliability and security of software systems.

Tools relying on these approaches include compilers [53, 61], code analyzers [11, 32, 38, 136, 171], disassemblers, binary analysis engines [261], to name but a few. These tools combine formal methods, which aim to provide complete and correct coverage, with heuristics
that try to optimize and find approximate solutions when formal methods alone are too ex-
pensive or intractable. In practice these tools often come with hundreds or thousands of
configuration and tuning options that can be used to adjust their behavior to try and improve
their overall effectiveness. However, since many rely on other tools to solve sub-problems or
are applied in many scenarios, this configuration is frequently left to the default one or is set
up with a suboptimal setting.

This chapter considers the problem of program analysis (with aim to call tracing) assisted
by symbolic execution, particularly in the context of malware analysis, which is a challenging
scenario due to its peculiar adversary model. Despite the potential advantages of symbolic
execution, this technique is still seldom used for malware analysis. Therefore our main goal
in this chapter is to evaluate symbolic execution and improve its use in our scenario.

Our main analysis targets the machine code of binary files as presented in figure 2.14
(page 88). We are particularly interested in accurately determining the calls made during the
execution (either symbolic or not), especially the calls that may be initially obfuscated in the
code at rest (i.e. before execution). We assess various heuristics that can be used to guide
and optimize the symbolic execution for program analysis (in general).

As main contributions, we:

- assess the performance of different tactics (or a set of tactics combined by means of tacticals) on all types of angr requests [addresses RQ3.1];

- improve prioritization of state exploration by comparing heuristics that target different weak spots of symbolic execution [addresses RQ3.2];

- evaluate a big set of parameters according to their impact on malware classification and their mutual correlation to better understand the heuristics around angr that are more likely to succeed in our scenario [addresses RQ3.3];

**3.1.1 Research Questions**

This chapter addresses the top-level research question **TOP-RQ1**: *How to improve the ar-
senal of techniques currently used in malware analysis, in particular for the analysis of binary
files?*

To this end, we leverage symbolic execution as a promising technique. We guide our
study pursuing the following subordinate research questions:

**RQ3.1 How to tune the SMT solver to improve performance of symbolic execution?**
**RQ3.2** *How to effectively apply heuristics that reduce the problem of state explosion in symbolic execution?*

**RQ3.3** *What is the impact of enhancing symbolic execution for binary analysis in a malware classification scenario?*

**3.1.2 Chapter Outline**

The remainder of this chapter is organized as follows:

- Section 3.2 (page 113) presents the specific background of this chapter;

- Section 3.3 (page 123) presents the related works;

- Section 3.4 (page 127) presents our methodology, which details our approach for SMT optimization, improvement of symbolic execution and the impacts on malware classification;

- Section 3.5 (page 135) presents the experimental setup and the evaluation results.

- Section 3.6 (page 147) discusses results.

- Section 3.7 (page 151) concludes.

**3.2 Background**

This section presents the background related to the topics developed in this chapter. In section 3.2.1 (page 113) we introduce the topic of symbolic execution and in section 3.2.2 (page 122) we present the background on Frequent Subgraph Mining (FSM).

**3.2.1 Symbolic Execution**

Symbolic execution was initially proposed in the mid-70s by James C. King from the IBM Research Center [145] and has been traditionally considered as a static analysis technique [89]. However, in the early 2000s, Patrice Godefroid et al [104] combined the dynamic executions of programs with a parallel symbolic execution for the discovery of alternative execution paths. This approach is known as Dynamic Symbolic Execution (DSE) and is considered as a dynamic analysis technique [89].

Newer approaches use different strategies to “execute” the code, ranging from code interpretation (s.l. static) to binary instrumentation (s.l. dynamic). Consequently, symbolic
<figure><img src="image_35.png" /><figcaption>Figure 3.1 – Program analysis approaches as depicted by Julian Cohen at BlackHat 2014 [55].</figcaption></figure>

execution can be seen as a mixed approach that combines the strengths of static and dynamic techniques. Figures 3.1 shows a visual arrangement of different program analysis approaches presented by Julian Cohen at BlackHat 2014 placing symbolic execution at the center of the static-dynamic axis [55].

## Principles

In a standard execution, at any given time the values of variables have only a unique value. This is for instance the case of registers in a CPU. This execution model is referred as *concrete execution*, as variables are assigned with *concrete* values that change only when some —direct (e.g. `MOV`) or indirect (e.g. `ADD`) —assignment instruction is executed.

In symbolic execution, variables are *symbolic*, meaning that they are able to represent sets of possible concrete values. In contrast with concrete execution, symbolic variables accumulate constraints on the possible values for the variables as the code executes instead of representing a single value.

In symbolic execution, conditional statements are evaluated not just as *True/False* as
with concrete execution, but as satisfiable or unsatisfiable. This means that, given a sym-
bolic variable, both conditions of a statement can be satisfiable ("True") (in opposition to
unsatisfiable ("False")) at the same time. Due to that, the symbolic analysis can simultane-
ously take both execution paths of a branching, while the concrete execution can only take
one of them. Consequently, while concrete execution is able to traverse only one execution
trace at a time, symbolic execution can traverse multiple execution traces simultaneously.

To illustrate the difference between concrete and symbolic execution, we provide the
following toy example.

```c
#include <stdio.h>
/*
 * Trial and error to find a solution for x^2 - 3x - 4 = 0 for x >= 0
 */
int main() {
    int x;
    printf("Let's try to solve x^2 - 3x - 4 = 0 for x >= 0.
");
    printf("Enter a value for x:");
    scanf("%5d", &x);
    if (x * x - 3 * x - 4 == 0) {
        if (x >= 0)
            printf("%d is a positive root.\n", x);
        else
            printf("x has to be positive.\n");
    }
    else
        printf("%d is not a root.\n", x);
}
```

<caption>Figure 3.2 – Sample of a code for a trial and error solution of a quadratic equation.</caption>

In this example, x is taken as a user input [line 9]; then x is tested whether it is a non-
negative root of the equation x² - 3x - 4. If x satisfies both conditions [lines 10 and 11], then
the printf [line 12] is reached. The concrete execution of this example is straightforward: a
value is assigned to x and the code checks whether it is a non-negative root of the equation. It
is very efficient to test whether the input satisfies both conditions, however it is not equally
as straightforward to find a value for x which is a non-negative root of the equation. The
traces of execution for x = -1 and x = 0 are displayed in Fig. 3.3.

In contrast, it is possible to use symbolic execution to systematically explore all execution
traces. With symbolic execution, x is assigned with a symbolic variable which accumulates
constraints along the different execution paths. The roots of x² - 3x - 4 = 0 are x = -1 and
x = 4, therefore it follows:

— Line 11 is reached only if x is constrained to one of the root values (i.e. -1 or 4). In any other case, the execution will reach line 17.
<figure><img src="image_36.png" /><figcaption>Figure 3.3 – Example of concrete traces of trial and error root solution.</figcaption></figure>

— Line 12 is reached only if x is constrained to root values [line 10] and if it is positive [line 11], otherwise line 14 is reached.

Therefore the execution reaches line 12 only if x= 4. Fig. 3.4 depicts how symbolic execution proceeds, showing its constraints on the symbolic variables for each execution path, thus building a tree of execution traces, which extends the single execution trace of the concrete execution.

In a nutshell, symbolic execution traverses the code considering the register values as symbolic variables instead of concrete values. Thus, all possible execution paths are —*theoretically* —taken into account and the control flow of code (represented by the CFG) can be fully covered. When the execution encounters some branching condition, the current state of the execution is replicated into two new states along with the constraints on the set of symbolic variables corresponding to each path. These constraints create decision prob-
<figure><img src="image_37.png" /><figcaption>Figure 3.4 – Example of symbolic tracing of trial and error root solution.</figcaption></figure>

lems that can be computed —for testing their satisfiability under the given set of conditions
—with the aid of theorem solvers. For more details on symbolic execution, refer to the survey
of Baldoni et al. [17].

Satisfiability Modulo Theories (SMT)

Satisfiability Modulo Theories (SMT) address the problem of determining whether a math-
ematical formula is satisfiable (i.e. if there is an appropriate set of values for the variables that
can make a given formula true). It generalizes the boolean satisfiability problem (known as
SAT), which determines the satisfiability of Boolean formulas, to more complex formulas
that can include real numbers, integers, as well as various data structures such as lists, ar-
rays, bit vectors and strings.

Deciding the satisfiability of formulas can be very hard. SAT was the first combinatorial
problem shown to be NP-complete [105]. Furthermore, SAT is NP-hard because any prob-
lem in NP can be reduced into SAT in polynomial-time [93]; as the SMT problem includes
the SAT problem, SMT is itself also NP-hard. Depending on the background theory used in
SMT, it can even be undecidable [19]. Nonetheless, over the past decades SMT emerged as
a problem-solving method and has been used in practice to solve problems in business and
industry.

There are dozens of tools that target the SMT problem, which as referred as *SMT solvers*. They support languages that allow to express constraints and implement algorithms that solve the satisfiability of these constraints. Apart from technical characteristic (e.g. operating system, APIs, language bindings, etc), these tools are chiefly distinguished by their built-in theories and their underlying language.

Theories commonly supported include *linear arithmetic*, *non-linear arithmetic*, *empty theory*<fnref n="1" />, *bit-vectors* and *arrays*. For a gentle introduction on these theories, refer to the article of Barrett *et al* [21].

As a practical example, we chose to introduce the *z3 Theorem Prover* (z3). This choice is motivated by the fact that z3 is a popular well-established tool and because it is a component of our analysis framework (detailed later in section 3.5.1, page 136). z3 is a SMT solver developed by Microsoft Research [234], which supports all the aforementioned theories in addition to *datatypes*, *quantifiers* and *strings*.

Figure 3.5 depicts the overall systems diagram of z3. It shows the existing interfaces (top left), which interact with the *SMTLIB2* component. In turn, SMTLIB2 is a library that implements the SMT-LIB input/output language for SMT solvers as defined by SMT-LIB standard [20]. The formulas entered in the SMTLIB2 component are dispatched to the *solvers* in order to decide their satisfiability; possibly, these formulas can be pre-processed by the *tac-tics* component with the goal of simplifying them to the solvers. The *optimization* component allows to solve the satisfiability (modulo objective functions) to maximize or minimize values. The tutorial on z3 programming by Bjørner *et al* details all these components [27].

Figure 3.6 shows an example of a z3 code. It is written in SMT-LIB language, whose syntax is similar to LISP syntax —every expression is a legal *S-expression* of Common Lisp [20]. This example addresses the code illustrated in figure 3.2: initially a symbolic variable x is declared [line 2], then the constraints of being a root of equation $x^2 - 3x - 4 = 0$ [line 5] and a positive value [line 6] are declared; finally, the satisfiability of the constraints on x is verified [line 9] —which returns *sat* when the code is executed—and a representation of a model computed by the solver is provided [line 10] —which returns (*model* (*define-fun x () Int 4*)) when command (*get-model*) is invoked.

For greater details on the theoretical aspects of SMT, refer to Fontaine's habilitation [93]. For greater details on the practical matters related to SMT-LIB, refer to its official documentation.

<footnote n="1">1. Theory that deals with *uninterpreted functions*, which symbolically represent functions that are not explicitly defined.</footnote>
<figure><img src="image_38.png" /><figcaption>Figure 3.5 – Overall system architecture of z3 [27].</figcaption></figure>

1 ; Variable declarations
2 (declare-fun x () Int)
3
4 ; Constraints
5 (assert (= ( ( * x x ) ( * 3 x ) ) 4) 0))
6 (assert ( > x 0))
7
8 ; Solve
9 (check-sat)
10 (get-model)

<caption>Figure 3.6 – Example of z3 code in SMT-LIB language.</caption>

tation [20].

angr

angr [261] is a tool for the analysis of binary files, which supports concrete, symbolic and concolic (i.e. a mix of concrete and symbolic) execution. angr is written in Python and is delivered as a Python package composed of the following modules (shown in figure 3.7):

- CLE: stands for "CLE Loads Everything" and is responsible for loading binaries and libraries.

- Archinfo: contains architecture-specific information.

- PyVEX: Python module to handle VEX<fnref n="3" />, which is an intermediate representation that

<footnote n="2">2. Image published at https://angr.io/img/angr_diagram.png (accessed October 2022)</footnote>

<footnote n="3">3. VEX is an intermediate language used in Valgrind [204].</footnote>
<figure><img src="image_39.png" /><figcaption>Figure 3.7 – Overall architecture of angr².</figcaption></figure>

enables angr to analyze binaries that target different architectures.

— **Claripy**: module that interfaces with a constraint solver.

The execution starts by loading the binary, using the CLE module. For this, CLE needs
information about the target architecture of the program, which is provided by Archinfo.

Once the binary is loaded, the angr SimEngine creates a new *active state* —which con-
tains the program memory, registers, file system, and any other so-called “live data” —and
starts coordinating the execution.

In its standard configuration, the analysis progresses in steps in which angr uses cap-
stone [8] to disassemble the code in units corresponding to a *basic block*, then angr converts
it into VEX. Figure 3.8 shows an example of a code translation transforming asm instructions
into VEX *superblocks*.

angr uses VEX as intermediary representation for its SimEngine in order to support mul-
tiple architectures. By doing this, binary code of multiple architectures can be lifted to VEX
without modifying the overall workings of the analysis module.

As the analysis continues, each step accumulates all the constraints defined by the cur-
rent basic block in a new active state (which belongs to an *active stash*). The previous ac-
```
0x24F275: movl -16180(%ebx, %eax, 4), %eax
1: ------ IMark(0x24F275, 7) ------
2: t0 = Add32(Add32ITT32(12), # get %ebx and
Sh132ITT32(0), 0x2:18)), # %eax, and
0xFFFFFC0CC: I32) # compute addr
3: PUT(0) = LD1e: I32(t0) # put %eax

0x24F27C: addl %ebx, %eax
4: ------ IMark(0x24F27C, 2) ------
5: PUT(60) = 0x24F27C: I32 # put %eip
6: t3 = GET: I32(0) # get %eax
7: t2 = GET: I32(12) # get %ebx
8: t1 = Add32(t3, t2) # addl
9: PUT(32) = 0x3: I32 # put eflags val1
10: PUT(36) = t3 # put eflags val2
11: PUT(40) = t2 # put eflags val3
12: PUT(44) = 0x0: I32 # put eflags val4
13: PUT(0) = t1 # put %eax

0x24F27E: JMP*1 %eax
14: ------ IMark(0x24F27E, 2) ------
15: PUT(60) = 0x24F27E: I32 # put %eip
16: t4 = GET: I32(0) # get %eax
17: goto {Boring} t4
```

<caption>Figure 3.8 – Example of IR code in VEX (asm x86 instructions in comments) [204].</caption>

The state is partially saved in the program state history, before getting eventually disposed. Whenever the current state comes across a conditional jump, angr evaluates the satisfiability of all accumulated constraints according to the jump condition, proceeding as follows:

- If both possibilities (the condition and its negation) are satisfiable, angr creates two new active states and continues the analysis along each execution path.

- If only one of the conditions is satisfiable, angr creates a new active state that continues along the satisfiable execution path and a *dead-ended* state that indicates the end of the other execution path.

- If both possibilities are not satisfiable, angr created two *dead-ended* states that indicate the end of both execution paths.

Constraints are solved by SMT solvers interfaced by Claripy. The default SMT solver is Microsoft z3, however others can be plugged into angr by writing an appropriate Claripy backend.

The procedure described above emulates a bare metal environment. To support abstractions provided by an underlying operating system (such as files, network, processes and others) angr includes the SimOS module.
**Limitations**

The main limitation of the symbolic execution in practice is the state-space explosion (also referred as *path explosion*), which exhausts the resources available, such as memory and time. The main sources of state-space explosion are loops and function calls [17].

The ability to explore all the possible traces of a given binary is one of the main advantages of concolic execution. However, this can become an issue if the system does not have enough resources to support the analysis. This is aggravated if the analysis follows a *breadth-first search* (BFS) approach, which expands all execution paths in parallel. The main alternative is to adopt *depth-first search* (DFS), which traverses an execution path as far as possible before backtracking to the deepest unexplored branch; however, this case is particularly disturbed by loops and recursive calls.

Another critical potential weakness of symbolic execution is the constraint solving. Some malware include *opaque predicates* that are commonly used to hinder static analysis [197]. This technique adds conditional jumps that depend on many complex conditions, which always evaluates to true (or false) —thus always taking only one of the possible execution paths at runtime. As consequence, the SMT solver used in the concolic mode can struggle to solve these very complex expressions.

Finally, symbolic execution also struggles with runtime transformations of the code, such as self-modifying or just-in-time (JIT) compilation, that write the instructions in memory as the program executes. If the analysis comes across instructions that are symbolic at runtime, the concolic engine does not know the (symbolic) instruction that must be executed. One expensive solution would be to create active paths for all instructions that meet the constraints of the symbolic instruction; otherwise the symbolic execution stops or misses some potential branches [316]. A similar problem is encountered whenever the address of a jump is symbolic.

**3.2.2 Frequent Subgraph Mining (FSM)**

Frequent subgraph mining (FSM) is defined as finding all the subgraphs in a given graph that appear more times than a given value. More formally, we define FSM as follows:

**Definition 1 (Labeled Graph)** A labelled graph can be represented as $G(V, E, L_V, L_E, \varphi)$, where $V$ is a set of vertices, $E \subseteq V \times V$ is a set of edges; $L_V$ and $L_E$ are sets of vertex and edge labels respectively and $\varphi$ is a label function that defines the mapping $V \to V_L$ and $E \to L_E$. G is **connected** if it contains a path for every pair of vertices in it and **disconnected** otherwise.
**Definition 2 (Subgraph)** *Given two graphs* $G_1(V_1, E_1, L_{V_1}, L_{E_1}, \varphi_1)$ *and* $G_2(V_2, E_2, L_{V_2}, L_{E_2}, \varphi_2)$, 
$G_1$ *is a subgraph of* $G_2$, *if* $G_1$ *satisfies: (i)*$ V_1 \subseteq V_2$, *and* $\forall v \in V_1$, $\varphi_1(v) = \varphi_2(v)$, *$(ii) E_1 \subseteq E_2$, *and*
$\forall (u, v) \in E_1$, $\varphi_1(u, v) = \varphi_2(u, v)$.

Given a graph dataset, $D = \{G_0, G_1, \dots, G_n\}$, the support $\mathcal{S}(g)$ denotes the number of
graphs (in $D$) in which $g$ is a subgraph. The problem of frequent subgraph mining is to find
any subgraph $g$ s.t. $\mathcal{S}(g) \ge \tau_{min}$, where $\tau_{min}$ is a minimum support threshold.

An overview of frequent subgraph algorithms is given in the survey by Jiang et al [133],
where gSpan —a graph-based substructure pattern mining [318] —is one of the most fre-
quently cited FSM algorithms. gSpan builds a new lexicographic order and maps each graph
to a unique minimum depth-first search code which represents a canonical label. Based on
this lexicographic order, gSpan adopts the depth-first search strategy to mine frequent con-
nected subgraphs efficiently.

In comparison with algorithms based on embedding lists, gSpan is very efficient in terms
of memory usage. Experiments show that gSpan outperforms the runtime performance of
related works by an order of magnitude and is capable of mining large frequent subgraphs
in bigger graphs using lower support than its counterparts [318].

**3.3 Related Works**

To help understanding the contributions of this chapter, this section overviews some re-
lated works that adopt techniques that differ from ours but are somewhat similar in rela-
tion to the domain and settings. However, our work explores the optimization of an entire
toolchain, whereas the related works only relate to individual parts/aspects of our analysis.
The organization of this section aligns the related works to each component optimized in
this chapter.

**Symbolic Execution**

Symbolic execution can be use to analyze programs in many ways including source code
and binary code representations [17, 37]. However, since this thesis explores the analysis of
binary codes, the remainder of this section considers only symbolic execution in this context.

Several tools can perform binary analysis using symbolic execution [42, 46, 250, 261].
Although our work uses only angr [261] for the experiments, the concepts apply to tools in-
cluding Mayhem [42], S²E [46] and Triton [250] among others. In practice, each tool has its
own optimizations and weaknesses, as well as its own ability to be (re)configured to modify
its execution choices. Since the goal is to consider a holistic approach to the whole toolchain,
the results can be adapted to any of these tools (and others).

Our modifications to the behavior of the symbolic execution can be easily adapted to
other tools, in particular due to our focus on lightweight modifications that can yield sig-
nificant improvements when considering other components and algorithms used in our
toolchain. We believe that our heuristics can guide other symbolic execution experiments.

Other related works improve symbolic execution in some specific domains [83, 166, 167, 257]. In Li et al [167] the authors consider how to steer the symbolic execution engine to specific paths of interest. It considers the execution of sub-traces (constituted by *n* conditional branches) and uses statistical analysis on the sub-traces already covered to determine which execution states may steer towards the less explored paths. Others researches investigate the optimization of the SMT solver used in the symbolic execution engines [83, 166], but their focus is oriented towards the reduction of the input expressions that are treated by the SMT solver. Sen et al [257] consider the merging of states, which has some conceptual similarities with our trace merging strategies (discussed later in section 3.4.3, page 132); however, in their case the merging takes place during execution, which spares the creation of new auxiliary symbolic variables.

SMT Optimization

One of the main goals of this chapter is to find optimizations for the SMT solver for the
specific use case of symbolic execution engine [83, 166]. There are many studies on SMT op-
timization [83, 114, 166, 310], however they frequently focus on solving particular problems
whose the theory and expressions (handled by the SMT solver) are known beforehand.

Wintersteiger et al [310] optimize their SMT solver for quantified bitvector operations.
Similarly, Ramirez et al [114] optimize for linear integer/real arithmetics. Erete and Orso [83]
and Li et al [166] focus the problem of symbolic execution with SMT optimization, however
they work with fixed constraints, thus with expressions known in advance rather than gen-
erated in runtime during exploration.

Our work approaches SMT optimization from a very different perspective. Since there
is no way to know beforehand what expressions will be optimized, our approach intends to
target efficiency optimization. We analyze a large set of expressions extracted from a fixed set
of binary files and evaluate which expressions are the most expensive and which approaches
can result in the best performance improvements.
We welcome the use of our results to guide future SMT optimizations and the proposition of other approaches that target specific SMT problems. Since we have only studied readily available tactics, we recognize that the SMT optimization community can use our approach to study this problem differently (beyond tactical analysis only) to significantly optimize an SMT solver for a symbolic execution engine.

**Binary Exploration Heuristics**

Several sophisticated loop un-rolling strategies proposed in literature aim to perform an informed guess when no useful information could be extracted from the loop such as the Loop-Extended Symbolic Execution (LESE) [251], the Read-Write set (RWset) [28] and the bit-precise symbolic loop mapping [314].

LESE [251] introduces symbolic variables counting the number of times each loop is executed and then links these variables with features of a known input grammar such as variable-length or repeating fields. When new execution paths are generated due to a branch- ing condition, RWset [28] verifies the memory locations read and written by the code to de- termine if the remainder of the execution trace can explore new behaviors, or it prunes the execution path otherwise. The trace-based approach proposed in the bit-precise symbolic loop mapping [314] aims to identify the semantics of possible cryptographic algorithms used in obfuscated binary code.

Unlike these techniques, our approach is completely based on heuristics analysis, thus being much less computationally demanding.

**Malware Classification**

Malware classification is a widely explored area with many different approaches. In this chapter, we focused on malware classification based on behavioral signatures as is com- mon to other works in the literature [24, 40, 47, 67, 72, 94, 174, 266]. Our goal is to set up a toolchain optimization to benchmark its improvements on malware classification, however due to the huge lack of standard datasets for analysis, the direct comparison of our results with other works is impaired. Therefore, this section points to the works that are somehow related to ours, but taking into account the aforementioned caveat of direct comparison.

Many works have tried to classify PE (Windows) malware by their family, however none reports classification explores the use of symbolic execution. By extracting static features (i.e., textual and binary patterns) with YARA, Sun *et al* [275] achieved an F-score of 0.936
with a random forest classifier (RF) over a dataset constituted by 12 families. Still using a RF
but extracting behavioral traces through a concrete execution within the Cuckoo sandbox,
Hansen *et al* [118] achieved an F-score of 0.864 on a dataset of 5 malware families. Based
on an RF fed with a mix of static and dynamic features, obtained by the monitoring of the
execution using the HookMe tool, Tian *et al* [282] and Islam *et al* [131] achieved an accuracy
score of ~ 0.97 (misclassifications not reported).

A behavioral graph representation extracted by means of taint analysis and dynamic ex-
ecution in a sandbox was also adopted by Ding et al. [73]. In their work, the authors removed
duplicate sub-graphs representing identical call sequences and grouped all the sub-graphs
extracted from instances of the same malware family. The graph matching was then per-
formed by looking for graph isomorphism. Experiments on a dataset of 6 families with about
200 samples each obtained an accuracy of about 0.96 when doing binary classification be-
tween a given family and cleanware —no multi-class classification was performed, but six
independent binary classifiers were used for the results, one per family.

In Park et al [212] the authors considered dependency graphs and used graph similarity
to classify malware. Their approach aimed to create clusters of graphs based on their dis-
tance and to compare these clusters with ground truth for classification. When tested on a
dataset of 300 samples from 6 families their results were mixed with some families achieving
only ~ 20% accuracy. In contrast to our work, their clustering approach required to preset
the total number of clusters, which is rarely known in practice.

Said *et al* [24] used a common subgraph approach for binary classification —a single
malware family and the remainder of samples being cleanware —which is similar to our
approach. Their results achieved a very high accuracy score (they used F₀.₅-score attaining
99.40%) after tuning parameters to their algorithms. Yet, this was only for a single family and
not multi-class classification as we target in this chapter. Nonetheless, the optimizations in
our work can directly applied to their approach.

Other works [144, 212, 236, 283] follow similar approaches in concept. These include
using other forms of graphs to represent behavior and some form of graph similarity for
clustering of common behaviors [144, 212, 283].

Rieck et al [236] used Support Vector Machine (SVM) on a vector which represents the
behavior description obtained by running the malware on a sandboxed environment. They
claimed to improve results on malware not already detected by some other system by ap-
proximately 70%, but they do not provide details about their results. Like our approach they
detected malware families using behavioral signatures and machine learning techniques.
Kinable and Kostakis [144] used the clustering of call graphs to analyze malware samples. They used a dataset of 194 samples from 24 families and concluded that the K-medoid clustering is not effective for their scenario. The density-based cluster algorithm DBSCAN, not requiring any prior knowledge on the number of cluster, showed a better performance. Therefore DBSCAN was evaluated over two larger datasets respectively of 675 and 1050 samples. The results showed 29 correct clusters and 19 wrong clusters for the first dataset, and 36 correct and 14 wrong clusters for the second dataset. For both datasets a large amount of samples were not classified in any cluster (respectively 260 and 253). Unlike our approach (in the current chapter), Kinable and Kostakis adopted a unsupervised classifier, mainly focusing on the homogeneity of the clusters (i.e. samples within a cluster belonging to a single family). This choice had an impact on the number of clusters, which was significantly higher than the expected result as per the chosen ground truth.

Graph-based representations of malicious behaviors were also adopted for malware running on the Android platform. The samples were generally dynamically executed but similar classifiers were used as those adopted for classifying Windows malware, e.g. SVM [315], graph isomorphism [329], Markov Chain Monte Carlo sampling [96], graph kernel [99] and Convolution Neural Network [126]. Even if the absolute performance results of the classifiers cannot be directly compared with our work, the presence of several similarities with our behavioral analysis toolchain means that many of the optimizations and lessons learned on our work can apply in that case as well.

**3.4 Methodology**

This work builds a binary analysis toolchain based on symbolic execution to explore various choices in the formal approaches and heuristics used in the analysis. The goal is to better understand how to use these tools to represent malware behaviors and classify them according to this representation. This does not only provides insight on how to build more effective malware analysis engines, but also on how to tune the key components of such toolchains for the analysis of binary files.

Our approach to optimize the behavior analysis toolchain for malware analysis is sketched in a workflow in figure 3.9. Our dataset is composed of malware and cleanware that are analyzed to extract the SMT expressions that are generated during the symbolic execution, which are then fine-tuned using various tactics available in z3. The optimization of the symbolic execution is also made directly on the angr framework, with the proper evaluation of
the impact on malware classification with respect to our graph-based behavioral signatures.

<figure><img src="image_40.png" /><figcaption>Figure 3.9 – Overall workflow of our malware analysis toolchain</figcaption></figure>

More precisely, we composed a binary dataset consisting of malware and cleanware that was analyzed through a *k*-fold cross-validation. To optimize the SMT solver, a benchmark of SMT expressions extracted through the hooking of interactions between angr and the SMT solver (ref. 1 in figure 3.9) was built. The SMT tactics available in the z3 theorem solver was analyzed and combined to find the sweet spot between accuracy and performance, which was then integrated to our use of angr.

The implementation and optimization of binary exploration (ref. 2 in figure 3.9) as well as the heuristics for the graph generation (ref. 3 in figure 3.9) were addressed. Finally, the whole optimization of the symbolic execution, graph-building, and classification heuristics
were holistically evaluated in the context of malware detection and classification using a
full factorial design of experiments (with ANOVA [268] and correlation analyses) (ref. 4 in
figure 3.9).

This is a first-of-a-kind attempt to assess the impact of the different configuration options on the efficiency and efficacy of malware classification using symbolic execution. This analysis allowed us to gain insights on the interactions between the various components constituting the behavioral analysis toolchain.

**3.4.1 SMT Optimization**

One important efficiency concern is to remove infeasible states from angr exploration.
For instance, upon a conditional jump, depending on the constraints, it may be the case that
the constraint conditions may be met by only one execution path. To determine when states
are infeasible, angr calls an SMT solver and prunes the execution paths that were found in-
feasible.

In angr this is done by using the z3 solver to answer SMT decision problems with results
of: sat (satisfiable), unsat (unsatisfiable), or unknown. Typically an unknown result is due
to z3 failing to find a sat or unsat solution in reasonable time. The following requests to the
SMT solver are used in angr:

- simplify(): simplify constraints for a subsequent satisfiability check;

- satisfiable(): checks the constraints assigned to the current state;

- batch_eval(): evaluates a list of constraints and provides a solution;

- max()/min(): finds max/min value that respects the constraints.

The main limitation of symbolic execution in practice is state-space explosion, which
is the root cause of problems with consumption of resources (c.f. section 3.2.1, page 122).
Thus the best solution to these problems is to optimize the usage of the SMT solver in two
directions: provide an answer faster, and provide a sat or unsat answer instead of *unknown*.
This improves the accuracy of the exploration, and removes infeasible paths optimizing the
whole exploration.

Symbolic execution faces an accuracy/performance trade-off: more resources (time, memory, etc.) potentially lead to better exploration. Thus the optimization of core components of the symbolic execution such as the utilization of the SMT solver are crucial to improve the results.
The z3 theorem prover used by angr is equipped with a few hundred parameters, grouped
in modules, whose purpose is to tune z3 with the aim of speeding up the evaluation of the
constraints. By using the more than 300 available parameters, a Microsoft Research team
working on z3 has identified about 100 problem classes and designed optimized approaches
(tactics) to tackle them. Even when the class of problem for an expression is known, a tailored
tactic is not guaranteed to produce a benefit, since tactics are heuristic strategies and not
proven optimizations.

Tactics tend to be highly tuned for known classes of problems but may perform poorly for new classes of problems [198]. New tactics can be easily defined with the available parameters, and also by combining other tactics. A total of eight combinators of tactics known as *tacticals* [198] are available in z3. Tacticals operate by applying a set of tactics: sequentially, in parallel, or alternatively when a prior tactic fails.

For example, to simplify constraints angr uses a customized tactic built as a sequen-
tial application of five predefined tactics provided by z3. These five tactics are: simplify,
propagate-ineqs, propagate-values, unit-subsume-simplify, and aig, and respectively
correspond to: simplification, removal of inequalities, constant propagation, simplification
of unit clauses (i.e., clauses composed by a single boolean literal), and compression of Boolean
formulas. When no tactic is provided (named NO_TACTIC hereinafter), the z3 solver will try to
infer the logic the expression belongs to, and to apply the corresponding tactic (if available).

Previous works have considered optimizing the solver for a specific class of formulas e.g. quantified bitvector [310] or linear integer/real arithmetics [114]. Instead, in our work we do not have any a priori knowledge about the expressions generated during symbolic execution. It is important to note that, once instantiated, the z3 solver cannot change tactics. In the beginning of symbolic execution angr instantiates a solver that is used for all SMT requests.

Thus, we are looking for a tactic (or a set of tactics combined by means of tacticals) that
is expected to work efficiently on all types of angr requests. This analysis addresses the fol-
lowing question **RQ3.1: How to tune the SMT solver to improve performance of symbolic exe-**
**cution?**

**3.4.2 Enhanced Symbolic Execution**

State-space explosion is known to be a critical issue in symbolic execution. The leading
sources are loops and function calls (specially in the case of DFS exploration) or the existence
of many conditional jumps in the code (specially in the case of BFS exploration).

Our call tracer includes a parameter to limit the number of execution paths explored si-
multaneously. By default, at each execution step angr considers all paths that are not fin-
ished yet, thus exploring the binary following a BFS strategy. If parameter max-active-
paths is set, only a limited number of paths are executed while the rest await in a stash.
Thus the binary is explored in a combination of BFS and DFS, which potentially controls
overall memory consumption.

Due to the creation of new states on each conditional branch, loops are a particular concern for angr due to potential state explosion when loops have many iterations. To address this here we consider heuristics to detect potential state explosion in angr and reduce the number of active states. In practice, this is achieved by detecting how many times an instruction has been visited —we call this case a *concrete loop* —and if this goes over a threshold, then this active state moved to the stash. Stashed states are given low priority for angr to execute, but may be executed if no other active state is available.

We also consider the case of *symbolic loops*, in which an unconstrained variable may cause an infinite number of loops. For instance, if the code contains `while(i < x){i++}`, where x is an unconstrained symbolic variable, both conditions (i.e. `i < x` and `i ≥ x`) are always satisfiable. Similarly to concrete loops, when symbolic loops are detected the stashed states are given low priority for execution.

Another major issue, which is not discussed in other works (e.g. the survey of Boldoni et al [17]), relates to type signature and call convention. They are necessary to define the inputs and outputs of function calls and determine stack management. Whenever the analysis comes across a call to an unknown function, angr attempts to use heuristics to resolve the call, however there is a non-negligible risk of mismanaging the stack, thus engendering failures in the remainder of the analysis.

In angr, calls to external libraries can be replaced by symbolic procedures called *SimProcedures* to mitigate the problem of path explosion. In our analysis, we adopted this approach. *SimProcedures* are Python implementations of functions (i.e. procedures) that replace the execution of the code of the external library. Each *SimProcedure* requires the precise definition of the input and output parameters, i.e. the procedure *prototype*. The lacking or mismatching of these information can potentially lead the symbolic execution to a defective state. By the time of our analysis, angr had prototypes for about 100 Windows libraries (e.g. advapi, glibc and kernel32), accounting for about 3500 *SimProcedures*. We carried out a pre-analysis phase to extend angr with 24052 (stub) *SimProcedures* of function frequently found in our analysis with their correct call conventions and prototypes.

We also included a step timeout parameter, which defines a maximum time threshold
for the computation of a step during symbolic execution. This mainly corresponds to the
time consumed by Z3 and therefore is indirectly related to the SMT optimization analysis.

All the parametrization, improvements and heuristics developed around angr in our call
tracer intend to target **RQ3.2: How to effectively apply heuristics that reduce the problem of
state explosion in symbolic execution?**

**3.4.3 Impact on Malware Classification**

Although our main focus in this chapter is to assess and improve symbolic execution
for the effective extraction of execution traces, we are particularly interested in measuring
the impact of these improvements on behavioral-based malware classification. To this goal,
we considered External Call Dependency Graphs (ECDG) —a specialization of System Call
Dependency Graphs (SCDGs) that is detailed and studied in chapter 4 (page 153) —as in the
work of Said et al [24], which have been proved to be an effective approach to build binary
behavioral signatures [24, 40, 47, 67, 72, 94, 174, 266].

We use gSpan [318] as a common subgraph mining algorithm to compute the similarity
between ECDGs. The ECDGs are built from the calls traced during the symbolic execution
of the binary files. The binary files present in the training set constitute the basis of the
the supervised learning phase, in which ECDGs are labeled as malware (including family) or
cleanware according to the ground truth.

The symbolic execution used to trace the calls targets the external calls<fnref n="4" /> as well as their
address and arguments. For the description of the binary file's behavior, we focus only on
external calls and their relationships. The source address, arguments, and position in the
trace allow to understand the relations between the calls and to build a directed graph to
represent the behavior of the binary file.

The vertices of the ECDG represent the external calls, while the (directed) edges repre-
sent the information flows between calls (i.e., input/output from a call used as argument of
another call), where the direction reflects the order of the calls in the execution trace. If there
are external calls to functions with the same name but different addresses, then distinct ver-
tices are created. If not all the external calls have interdependencies (which is a very com-
mon case), the graph will contain several subgraphs representing different sub-behaviors
encoded in the binary. Furthermore, since symbolic execution can traverse multiple exe-
cution paths simultaneously, the graphs may contain disconnected components for each

<footnote n="4">4. External calls are calls to external libraries or system calls. Refer to chapter 4 (page 153) for a more detailed discussion about ECDGs.</footnote>
execution path.

Since several execution traces can be generated according to the conditional branches
that have been evaluated sat by the constraint solver, ECDGs can be built in different ways.
In particular, we consider three parametric heuristics:

* *merge-calls*: define whether external calls having the same name and address are merged or not. Merging the calls has the potential of providing a higher level of abstraction over the binary behavior by considering a more compact model and simplifying the graph traversal in the machine learning classification phase. However such an abstraction could cause the loss of some details important to discriminate the malware families.

* *disjoint union/traces-merge*: each individual trace traversal obtained with the symbolic analysis generates a subgraph. The disjoint union of these graphs is then used to include all the (sub)behaviors in a single graph (as in Said et al [24]). The alternative is to merge prefixes of traces to connect more components reducing the overall graph size (similarly to Macedo and Touili's [174] system call dependency trees). Unlike dynamic execution, where a single execution path is traversed, the symbolic execution comprises multiple traces due to the ability of exploring multiple execution paths in parallel. The *traces-merge* option attempts to generate more connected graphs (by looking for common prefixes in the set of traces), whereas the disjoint union pursuit a different approach, i.e. treating the traces as independent executions (as if multiple runs of concrete executions have been made).

* *min-trace-size*: a minimum number of calls have to be present in a trace to be valid, thus discarding shorter traces. The rational behind such a heuristic is that very short traces could prompt symbolic explorations of bad quality e.g., due to anti-analysis or obfuscation techniques. Discarding such traces could prevent biasing the classifier over graphs that do not represent the behavior of a malware family itself but only less important code segments (e.g. obfuscated header, in the case of packed binaries).

These parametric heuristics directly affect the malware classifier because they have an
impact on the set of execution traces used to build the ECDGs. The choices of these metrics
address **RQ3.3**: *What is the impact of enhancing symbolic execution for binary analysis in a*
*malware classification scenario?*

Additional parametric heuristics not considered here include max-trace-size and total-size-limit. We have not explored these two additional parametric heuristics because, according to our previous experience, both are only suitable for a scenario with resource con-
straints. Therefore, by not setting any bound to these parameters, we do not have to deal
with any limiting factor on the performance evaluation of the classifier.

The following graph metrics have been computed for each set of ECDGs: number of
unique system calls, number of edges, number of vertices, size of the largest weakly con-
nected component<sup>5</sup>, number of weakly connected components, graph density (defined as:
edges
 vertices·(#vertices·−1)
 ), and number of unique edges (i.e., information flow having same source,
destination and arguments).

Note that the efficiency and effectiveness of symbolic execution affect the quality of the information contained in the traces, therefore it influences the building of ECDG-based behavioral signature and the mining process. The aforementioned graph metrics are later used to form a feedback loop used for tuning the parameters of the symbolic execution, as shown in figure 3.9.

ECDG classification and evaluation

Here we present our multi-class classifier, which selects the most fitting malware family for a given binary file. Our approach exploits the mining of common behaviors for malware families. More precisely, the collection of ECDG behavioral signatures for each family of malware <fnref n="6" /> is mined to find common subgraphs using gSpan. The largest common subgraph found in the mining process becomes the ECDG-based behavioral signature for that malware family.

To classify a new binary given its ECDG, a comparison is done using the ECDG charac-
teristic of each malware family, i.e. a ECDG-based behavioral signature. This comparison is
carried out by using gSpan to find the largest common subgraph between the sample and the
family signature, i.e., how much of the malware family signature is contained in the sample.

We then compute the *similarity score* as the percentage of the malware family subgraph that is contained in the sample. A sample is then classified according to the malware family with which it has the highest similarity score, provided that this similarity is above a predefined threshold. If a sample does not meet the similarity threshold for any malware family, it is then classified as cleanware.

This approach replicates the approach used to classify a single malware family [24], but
in the context of multi-class classification using graph mining, which had not been studied
before.

<footnote n="5">5. Maximal subgraph in a directed graph for which there exists a path between each pair of vertices.</footnote>

<footnote n="6">6. Cleanware are not considered a family since they do not have a reason to share a common behavior.</footnote>
For a binary classifier (i.e., discerning malware from cleanware), it is possible to derive
several metrics (c.f. section 2.2.1, page 60): (i) *recall* (sometimes also called *sensitivity*) is
the number of correct positive classifications over the total number of positive cases, (ii) *precision* is the ratio of true positives over all the positive results returned by the classifier,
and (iii) *accuracy* (or *trueness*) is the ratio of correct classifications over the total number of
samples. We also take advantage of the *F-score* as a simple but effective metric to measure
the accuracy of a binary classifier.

Since in our context we are also interested in classifying the malware family of the sam-
ple, we adopted the *micro-average F-score* which considers the counting of correct and in-
correct classifications for each class independently before appropriately summing them up
to compute precision and recall.

In this classification problem, the usual trade-off between sensitivity and false positives comes to light and each model designer chooses how to balance it. Nonetheless, as a guiding principle, it is worth taking into account that mis-classifications between families are less severe than mis-classifications in a binary classifier. Moreover, problems could also arise by differences in the label assignment of external models, as the same instance can be tagged with different labels that indicate contradictory malware families. For this reason, we leveraged VirusTotal [294] for identifying the samples that have a large consistency on the attribution of the malware family.

**3.5 Experiments**

This section presents the experimental methods used to address the research questions posed in this chapter —in line with our proposed methodology. In the following, we first describe our implementation setup (section 3.5.1), then we focus on how we optimized z3 to improve the performance of symbolic execution of binary files (section 3.5.2), then we consider potential heuristics to improve the extraction of traces with angr tuning, and finally we describe the optimization of the whole binary analysis toolchain from the symbolic execution to extract the system calls, to the ECDG building process for the classification of binaries according to ECDG-based signatures.
3.5.1 Implementation Setup

The experiments have been performed on a cluster constituted by 12 machines having four Intel CPU E5-2660 v4 @ 2.00 GHz with 132 GB of RAM each, running Ubuntu 16.04 LTS. We refer to this cluster of machines as *Madlab*.

angr-extractor

Our **code analyzer** (i.e. angr-extractor) uses angr [261] *version 7.8.8.1* with *z3 version 4.5.1.0.post2* to build a software layer (written in Python) that traces the calls invoked by the main binary object <fnref n="7" /> to any shared object or system call (i.e. external call).

Instead of setting breakpoints at the addresses of the functions, as in traditional imple-
mentations of call tracers (e.g *ltrace* [33]), our symbolic tracer steps through code, inspecting
all active states whose execution addresses are outside the main object. When these states
are found, hinting that the execution of some external procedure may be ongoing, an at-
tempt to resolve the call is performed. To do it, the current address is looked up in angr
internal collectedmapping of addresses and *SimProcedures*, working as a generic hook to
any external call.

<figure><img src="image_41.png" /><figcaption>Figure 3.10 – Object code’s boundaries: *main object* (us) vs. *program* (state-of-the-art)</figcaption></figure>

To provide higher isolation for the analysis environment, we set angr not to execute code
outside the main object (*auto_load_libs* option unset). Missing *SimProcedures* are replaced
by stubs that only return an unconstrained symbolic variable, allowing to virtually resolve
any runtime dependency. As a side effect these *stub SimProcedures* may alter the real execu-
tion of the file.

<footnote n="7">7. Memory segment corresponding to the program binary code, without considering any shared object (i.e. dynamic loaded libraries)</footnote>
Additionally, notwithstanding angr fine heuristics, unknown call conventions and un-
known function signatures can also incur defective symbolic execution. Therefore, we ex-
tended angr with 24052 stub *SimProcedures* of functions commonly used (along with their
correct call conventions and signature definitions), which proved to be a very effective tac-
tics to improve the quality of symbolic executions.

Our symbolic execution implementation is parameterized with step timeout, max ac-
tive paths, loop threshold, branching loop threshold (for symbolic loops) and SMT
tactics (for the underlying z3 tactics). Several additional tunable parameters are fixed in
our experiments: the global timeout (fixed to 1h) which limits how long the angr-extractor
can run before terminating and the global memory limit (fixed to 10GB) which restricts how
much RAM the angr-extractor can use before stopping the creation of new active states.

ECDG-builder

The **graph builder** (i.e. ECDG-builder) builds ECDGs using the call traces generated by
the angr-extractor. Each call trace contains the external calls found during code analysis,
with their arguments and return value (if any).

This module was developed as an *ad-hoc Python* script. Note that symbolic execution
may traverse multiple execution paths during analysis, so instead of generating a single
(linked) list of calls it may produce a set of call lists. As discussed in section 3.4.3 (page 132),
this opens new possibilities for the definition of call graphs, which may combine calls found
in different execution traces.

Our implementation takes parameters to un/set disjoint union, merge calls and
merge trace. When disjoint union is set, functions comprised in different call traces are
not merged, but their interdependencies create edges between functions of all traces. When
merge calls is set, similar functions are grouped into a single node. When merge trace is
set, common call trace prefixes are combined into a single subtrace, thus transforming a set
of call traces into a tree-like structure. All options can be combined, except disjoint union
and merge traces that are mutually exclusive.

quickSpan

Our **graphs analyzer** (i.e. *quickSpan*) consists of an optimized implementation of *gSpan* [318]
in C to mine common subgraphs given a set of graphs.

Our quickSpan implementation supports many tunable options for different domains
and has achieved 35-fold speedup in comparison to Yan's original implementation with multi-threading, and 6-fold speedup with a single thread. It also reduces more than 100 times the memory usage, which makes it fit to mine large graphs with a low memory footprint.

Orqal

We deployed our experiments in a distributed architecture based on Docker, as all the
modules detailed above can be encapsulated in Docker containers [185]. Therefore we de-
veloped Orqal<fnref n="8" /> ([OR(Q)]chestration of [AL]gorithms), which aims to optimize the use of re-
sources on Madlab by orchestrating the different modules as individual Docker containers.

Orqal is a simple orchestrator (written in Python) to manage docker clusters, which mon-
itors and distributes the Docker workload on different nodes of Madlab. Orqal is provisioned
with a REST API that connectors can call to manage the Docker containers on the cluster (see
figure 3.11) to schedule jobs<fnref n="9" /> and retrieve data generated during the execution.

<figure><img src="image_42.png" /><figcaption>Figure 3.11 – Overall architecture of Orqal</figcaption></figure>

<footnote n="8">8. Available at https://github.com/scampion/orqal.</footnote>

<footnote n="9">9. We refer to each individual container run as a *job*, regardless the module in use.</footnote>
We also developed a Python connector (i.e. Orqal Client <sup>10</sup>) that allows to manage Orqal in Python scripts (e.g. in Jupyter notebooks [147]). No special configuration is needed on the nodes of the cluster other than the Docker service running and listening to a network port. Additionally, a dashboard is provided to monitor average load per node, jobs scheduling and a redoc API.

Dataset

Two different datasets were used in the experiments to prevent any overfitting of z3 op-
timization with the remainder of the analysis, which includes parameter tuning of symbolic
execution and evaluation of this tuning on ECDG classification.

For the first dataset we randomly select a subset of the binary files in our database to
obtain a set of SMT expressions for the purpose of benchmarking. This dataset included a
mix of malware collected from VirusTotal in 2018 and binary files manually obfuscated with
Tigress [56], which are likely to produce complex SMT expressions.

The second dataset is composed of 8 malware families —coupon-marvel, gamemodding, installbrain, multiplug, jeefo, detroie, mira and addrop—with 25 binary files for each. The malware samples were collected by Cisco in 2018 and provided to our research as part of a scientific project. An additional family of 25 cleanware binary files, taken from a fresh installed Windows 7 Pro was also included. The list of SHA1 and family of each binary in this dataset are reported on the tables in appendix 6.6.

**3.5.2 Optimizing z3 for symbolic execution of binary files**

To isolate the optimizations on z3 from those that concern angr, an *ad-hoc* experiment
was done to identify key tactics and tacticals. The experimental settings included a bench-
mark of SMT expressions extracted from symbolic executions of binary files (including both
malware and cleanware). The different z3 tactics were evaluated using these expressions
to identify the most promising tactics. The outcome of this analysis allowed to enhance
angr symbolic analysis with the best combination of tactics in the SMT solver setup. This
optimized setup was used in the remainder of our experiments, which concerns the whole
analysis toolchain (c.f. section 3.5.3, page 143).

A symbolic execution was performed on the selected binaries and the expressions re-
layed to z3 were recorded. From these expressions, we obtained a baseline benchmark (c.f.

<footnote n="10">10. Available at https://pypi.org/project/orqal/.</footnote>
table 3.1) of the number, kinds, and results of calls to be used for comparison later. We set a timeout of 2 minutes for symbolic execution, as it showed to be long enough to collect a suitable amount of expressions.

<table><caption>Table 3.1 – Benchmark of SMT expressions extracted through symbolic executions</caption><thead><tr><th></th><th>Dataset: Malware + Cleanware</th></tr></thead><tbody><tr><td># of files</td><td>906</td></tr><tr><td>extration from simplify()</td><td>54460</td></tr><tr><td>extration from satisfiable()</td><td>103881</td></tr><tr><td>extration from batch_eval()</td><td>47585</td></tr><tr><td>extration from max()</td><td>177439</td></tr><tr><td>extration from min()</td><td>112712</td></tr></tbody></table>

The expressions collected were solved by z3 with different tactics. As a result of these experiments an optimized set of tactics (combined in tacticals) was chosen to be used in the remainder of our experiments, which target the optimization of the whole toolchain. Note that finding an optimized tactic is only a partial answer to RQ3.2<sup>11</sup>, as part of the answer also comes from the incorporation of these results into the analysis toolchain.

## Results

To create an “optimized strategy” for the toolchain experiments, an evaluation of z3 behavior on typical angr calls was performed. The performance of z3 built-in tactics (including NO_TACTIC) on all the benchmark expressions was evaluated. Initially no limit was put on the resources available to solve the expressions and this led to some expressions requiring several hours for z3 to find definitive results with a given tactic. To achieve efficient symbolic execution in practice and resolve this potential time cost, a one-minute timeout was set for z3; unknown is returned when timeout is reached without a definitive answer (sat or unsat). The limit of one minute was chosen to allow sufficient time for z3 to attempt to solve the SMT expression, while not causing a prohibitive time cost in symbolic execution —where many calls to z3 are made for each binary, such as in the experiments considering the whole analysis toolchain in section 3.5.3.

The evaluation of each tactic on each SMT expression was repeated 30 times and the results averaged to prevent concerns from caching, scheduling, OS behavior, etc. Two metrics have been considered in the evaluation of the effectiveness of the tactics: execution time

<footnote n="11">11. RQ3.2: *How to effectively apply heuristics that reduce the problem of state explosion in symbolic execution?*</footnote>
and ability to successfully perform a satisfiability check. The baseline considered here is the NO_TACTIC tactic that does not exploit any special knowledge about the SMT expression to be solved. A summary of the performance of the selected tactics over the benchmark of SMT expressions is presented in table 3.2, the best result<fnref n="12" /> for each type of call being in bold.

<table><caption>Table 3.2 – Results of the selected z3 tactics of SMT expressions extracted for benchmark.</caption><thead><tr><th rowspan="2">Tactic</th><th colspan="2">simplify()</th><th colspan="2">satisfiable()</th><th colspan="2">batch_eval()</th><th colspan="2">max()</th><th colspan="2">min()</th></tr><tr><th># solved</th><th>Exec. time</th><th># solved</th><th>Exec. time</th><th># solved</th><th>Exec. time</th><th># solved</th><th>Exec. time</th><th># solved</th><th>Exec. time</th></tr></thead><tbody><tr><td>NO_TACTIC</td><td>54460</td><td>694.22812</td><td>103881</td><td>765.75330</td><td>47585</td><td>603.7525</td><td>177439</td><td>1764.67108</td><td>112712</td><td>1087.35926</td></tr><tr><td>qfufbv_ACK</td><td>54460</td><td><strong>386.65576</strong></td><td>103881</td><td>1139.12232</td><td>47585</td><td>449.5783</td><td>177439</td><td>1203.88404</td><td>112712</td><td>478.72028</td></tr><tr><td>solve-eqs</td><td>-</td><td>-</td><td>25136</td><td>20.14145</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>fnra-nlsat</td><td>642</td><td>90.17725</td><td>93194</td><td>78.75564</td><td>4783</td><td>196.3956</td><td>26419</td><td>189.45631</td><td>37930</td><td>199.52513</td></tr><tr><td>qfnra</td><td>642</td><td>4415.16436</td><td>93194</td><td>160.87066</td><td>4783</td><td>287.8888</td><td>26419</td><td>324.62751</td><td>37930</td><td>305.77329</td></tr><tr><td>qfid1</td><td>54460</td><td>3977.16036</td><td>103881</td><td><strong>671.98977</strong></td><td>47585</td><td>318.2233</td><td>177439</td><td>697.96655</td><td>112712</td><td>350.42974</td></tr><tr><td>qflra</td><td>54460</td><td>3968.18507</td><td>103881</td><td>2653.76949</td><td>47585</td><td><strong>279.9188</strong></td><td>177439</td><td>619.84178</td><td>112712</td><td>295.73773</td></tr><tr><td>qfauflia</td><td>54460</td><td>3954.05094</td><td>103881</td><td>1091.53502</td><td>47585</td><td>296.3621</td><td>177439</td><td><strong>605.63197</strong></td><td>112712</td><td>295.56502</td></tr><tr><td>smt</td><td>54460</td><td>3983.59492</td><td>103881</td><td>2645.59894</td><td>47585</td><td>284.2394</td><td>177439</td><td>610.80981</td><td>112712</td><td><strong>292.04155</strong></td></tr><tr><td>Total expressions</td><td>54460</td><td></td><td>103881</td><td></td><td>47585</td><td></td><td>177439</td><td></td><td>112712</td><td></td></tr></tbody></table>

For each of the winning tactics from table 3.2, a deeper analysis is performed to compare the calls of each type (e.g., simplify()) of a single binary, in order to prevent the overfitting of the tactic with respect to the expression type.

Results are presented in figure 3.12 where each plot compares the base time taken per binary (x-axis) with the time taken using the best tactic for that expression type (y-axis) as chosen from table 3.2. The x-axis is the NO_TACTIC and the y-axis is the compared tactic. Each data point represents the total execution time for all expressions from the corresponding function in a given binary. The dashed line in light green represents a linear regression model, such that if the green line is below the diagonal (in red), the customized tactic outperforms the default one in terms of execution time.

Figure 3.12a compares NO_TACTIC and qfufbv_ACK<fnref n="13" /> on the execution time to solve the benchmark's SMT expressions using simplify() (c.f. 3.4.1, page 129). Observe that (except for very few binaries) using qfufbv_ACK instead of the default tactic is clearly better.

As reported in the scatter plot in figure 3.12b the qfid1¹⁴ did not attain any significant improvement when considering the satisifiable() calls.

In contrast, the expressions from batch_eval() using the qflra<fnref n="15" /> instead of the NO_TACTIC has a clear benefits over all the binaries, except for very few cases (see figure 3.12c).

<footnote n="12">12. Note that this is the least time spent, potentially including the timeout in case of failure to find a solution.</footnote>

<footnote n="13">13. Quantified Free formulas (QF) over bitvectors (BV) with uninterpreted sort function (UF) and symbols solved with Ackermanization.</footnote>

<footnote n="14">14. Boolean combinations of inequality constituted by differences between integers variables and constants.</footnote>

<footnote n="15">15. QF linear real arithmetic, i.e., Boolean combinations of linear polynomials over real variables.</footnote>
<figure><img src="image_43.png" /><figcaption>Figure 3.12 – Execution time (in seconds) to solve the benchmark expressions.</figcaption></figure>
Table 3.2 shows that max() and min() are the most common requests and also account for most of the time spent by the solver. By selecting the right tactics, qfauflia<sup>16</sup> and smt<sup>17</sup>, the default configuration could be outperformed for all the binaries as shown in the scatter plots in figure 3.12d and e.

The results in table 3.2 and in the figure 3.12 confirm that adopting heuristics as proof
strategies is rarely a “one size fits all’ approach’ [198]. Therefore, we created a new “opti-
mized” strategy based on the best tactics on the benchmark (qfufbv_backr, qfidl, qflra,
qfauflia, and smt) combined with parallel tacticals —note that while qfidl did not pro-
duce significant advantage on binaries for satisfy() as shown in figure 3.12b, we still chose
to include it as there were cases where it showed a relative good performance. This “opti-
mized strategy” was compared with the default one in the remainder of our experiments.

The analysis above addresses **RQ3.1**<sup>18</sup>, because the usage of the z3 SMT prover can clearly
be optimized by changing the tactics. And it also partially addresses **RQ3.2**<sup>19</sup>, as a better us-
age of the toolchain resources can be achieved by improving the SMT tactics.

**3.5.3 Overall Toolchain Optimization**

Our evaluation is presented in figure 3.13, which shows the correlation between each
possible pair of: heuristics for graph building and symbolic execution, ECDGs metrics and
classifier's quality metrics (F-scores, accuracy and precision). For each graph metrics de-
scribed in section 3.4.3 (page 132) we computed some summary statistics (total, mean, stan-
dard deviation, min, quartiles Q₁, Q₂, Q₃ and max). Only the correlations with significance
level above 0.01 are considered here. The size of the circles and their color intensity repre-
sent how strong is the correlation (if any) between the pair of parameters indicated on the
border of the matrix.

The correlation matrix shows that the F-score by malware family is negatively correlated
to the presence of many unique edges and nodes, as well as to the learning time. The neg-
ative correlation of the unique edges and nodes contrasts with the positive correlation of
the nodes, edges and the connected components. This could be explained by the fact that
the gSpan mining overlooks the “uniqueness” of edges and nodes and obtains better perfor-
mances on larger connected sub-graphs (c.f. section 3.4.3, page 132). The negative correla-

<footnote n="16">16. Closed QF linear formulas over the theory of integer arrays extended with free sort and function symbols.</footnote>

<footnote n="17">17. Boolean SAT-based SMT solver.</footnote>

<footnote n="18">18. **RQ3.1: How to tune the SMT solver to improve performance of symbolic execution?**</footnote>

<footnote n="19">19. **RQ3.2: How to effectively apply heuristics that reduce the problem of state explosion in symbolic execution?**</footnote>
<figure><img src="image_44.png" /><figcaption>Figure 3.13 – Correlation matrix (*p*-value > 0.01) for the graph building and symbolic execution heuristics, graph metrics and performance of the classifier (some correlations have been removed from the plot for the sake of clarity).</figcaption></figure>
tion for learning time is due to the fact that gSpan spends more time to mine larger graphs.

Finally, the F-score by malware family is strongly correlated with the performance of the binary classifier, the latter having even stronger correlations with the graph metrics mentioned above. The graph-building heuristic *merge calls* (described in section 3.4.3, page 132) causes a significant reduction in the number of edges and size of the connected components. Even if this simplification significantly reduces the learning time, it costs the reduction in quality of the classifier. The *disjoint union* as a trace combination heuristic results in the presence of a higher number of sub-graphs and thus requires a higher learning time. On the other hand, the presence of a higher number of connected components, as observed before, increases the F-score. The last of the considered graph-building heuristics, the *minimum trace size*, does not present any significant correlation with any of the considered performance or graph metrics (and has been therefore omitted in the correlation matrix of figure 3.13).

The most interesting correlations to address our research questions are the following: the branching loop threshold, which allows to collect more unique calls and edges, but is not reflected in the F-score (that mainly depends on the connected components as already observed) —this result addresses **RQ3.2**. Furthermore, not restricting the setting of max-active-paths is positively correlated with the F-score thanks to its ability to explore the CFG in BFS order. Regarding **RQ3.1**<fnref n="20" /> our “optimized” z3 tactic has a positive correlation with the F-score (as later presented in section 3.5.4, page 146).

Therefore we can conclude that, considering the graph metrics and their impact on the F-score, the litmus test for the quality of an ECDG-based classifier is the presence and size of the connected components. This is an important and unexpected finding because, contrarily to what one might have expected, the cornerstone is not the number of (unique) calls that reflect how deep the code is explored. This could be explained considering how gSpan mining algorithm works and the adopted similarity metric based on the number of common edges between the extracted signatures and the ECDG of the sample to classify (c.f. section 3.4.3, page 132).

Here it is important to notice that the properties of the connected components are not under direct control for parametrization. In fact, they are the result of heuristics and techniques used during the analysis toolchain and are also influenced by the behavior of the binary itself. Even if it is not possible to identify which is the “best” size for the connected component, the appendix section 6.6 (page 310) explores the size and number of connected

<footnote n="20">20. **RQ3.1: How to tune the SMT solver to improve performance of symbolic execution?**</footnote>
components and their relationship with the performance of the classifier.

### 3.5.4 Impact of graph and execution heuristics

In our analysis of variance (ANOVA [268]), we first consider the main effect of each heuristic on the quality of the classifier. For the sake of conciseness, figure 3.14 shows only three of the seven factors analyzed. For the sake of completeness, the impact of all factors is reported in appendix section 6.6 (page 310).

<figure><img src="image_45.png" /><figcaption>Figure 3.14 – Main effects of the factors (x-axis) over the F-score (y-axis).</figcaption></figure>
Regarding **RQ3.1**, the “optimized” tactic for z3 allows the consolidation of the classifier to an F-score above 0.825, whereas the default version has widely spread performance even reaching a very low F-score of 0.65 (see figure 3.14c).

To address **RQ3.3**<fnref n="21" /> for the graph building heuristics, performing the disjoint union of the traces is generally preferable (see figure 3.14a), as well as to not merge the calls (not shown in the figure). Putting a limit to the minimum trace size to build a graph does not have a direct impact on the classifier. This happens because when angr is able to analyze the malware samples (see the following section 3.6), it is generally able to extract a substantial number of calls.

Limiting max-active-paths results in very inconsistent performance with F-score from 0.65 to 0.94. Finally, branching-loop-threshold and step-timeout show a similar behavior: when they are disabled, the performance is more stable. The overview above addresses **RQ3.3**, with significant relations between the outcomes of behavioral signatures and malware classification.

## 3.6 Discussion

In this section we discuss the results of the evaluation analysis taking into account the whole settings of the toolchain. During our experiments, the best classifier attained a F-score of 0.955 in the classification by malware family and 0.970 in the case of the binary classification. Based on our preliminary analysis we set a similarity threshold for gSpan of 0.7, further results supporting this are reported in appendix section 6.6 (page 310). This analysis addresses **RQ3.3** by showing that the multi-class classification based on ECDG as behavioral signatures (extracted through symbolic execution) is effective, albeit somewhat sensitive to the choices of other parameters in the experiments —note that the results here should not be considered a direct comparison with related works (c.f. section 3.3, page 123).

Our focus is the optimization of symbolic execution and heuristics evaluation. As already described in section 3.5 (page 135), the adoption of a full factorial design approach better suits our needs but is very computationally demanding. As a result, at first glance our dataset may appear small in terms of number of families and samples per family. However, we observe that symbolic execution trades more execution time for significantly more complete results, particularly on complex samples such as malware. Since we conducted

<footnote n="21">21. **RQ3.3:** What is the impact of enhancing symbolic execution for binary analysis in a malware classification scenario?</footnote>
full factorial experiments over 128 units and 5-fold cross validation, which yields 640 clas-
sification experiments each over 200 samples. In practice this makes our experiments quite
demanding; adding just 25 more samples (i.e. one family according to the family sizes in
our dataset) would cost a increment of over five days of computation time. Thus, despite its
seemly reduced size, the dataset is in practice larger than many works that address symbolic
execution, which analyze datasets ranging from a couple of dozen to a maximum of a few
hundred samples [47, 148, 192, 271, 316].

Results on a larger dataset would be ideal, however we note that using such intensive
techniques on all samples is largely an academic practice. In practice, both symbolic and dy-
namic execution are applied only to a *subset* of the collected malware samples, while other
less demanding techniques (e.g. syntactical signature matching) have not been able to pro-
vide enough confidence on the results [289].

To further complicate the direct comparison, the community lacks a common public
database with a large variety of well labeled malware [98]. This precludes the establish-
ment of a common ground truth across multiple works. Although the use of F-score is more
adopted in the community (even in case of multi-class classifiers), here we preferred to use
micro-average F-score (described in section 3.4.3, page 132) due to its ability to better cope
with classes and provide more precise results in presence of imbalance datasets.

We adopted a linear model to study the interaction between each pair of factors. For the
sake of brevity, here we only comment the significant observations of the corresponding 21
plots (reported in figures 6.5, 6.6 and 6.7 of appendix section 6.6, page 313). Trace merge
combined with merge calls is too aggressive in simplifying the graphs, producing a catas-
trophic effect on F-score when both options are used together. This is due to the fact that
both reduce the number of edges and connected components, with substantial degradation
on the most important graph metrics identified in section 3.5.3 (page 143).

Although graph-building heuristic *merge calls* generally have a negative effects on F-score, the optimized version of z3 is able to mitigate this drawback. A possible explanation points to the ability of the optimized z3 of actually determining the satisfiability of SMT constraints instead of returning *unknown* due to the solver's timeout. Therefore, it can extract more edges, which connect a larger number of nodes. The effects of merging calls and branching loop threshold appear to be closely dependent, but the interaction plot of *merge-calls* and *step-timeout* shows a clear independence of these factors.

A very interesting dependency exists between the z3 solver and the limit on the number
of max-active-paths. Limiting active paths is something usually done to partially reduce
memory consumption —so as to keep the performance degradation within tolerable boundaries —and to set the symbolic execution traversal to a configuration closer to Depth-First Search (DFS) instead of BFS. Here, we observe a significant performance decrease with the limitation of the max-active-paths, but our optimized version of z3 is able to almost completely remove such a negative impact on F-score —the degradation is still present but it is of about 0.01 instead of about 0.09.

Other plots provide some hints of dependencies such as: trace combination with min-trace-size and with branching-loop-threshold, merge-calls and min-trace-size, and z3 with branching-loop and step-timeout.

Finally, we consider the interactions between each possible combination of factors. The analysis shows several interaction effects asserted with a significance lower than 0.001. The Pareto chart (figure 6.4 of the appendix section 6.6, page 312) helped us to select the ones having more influence on F-score. The combination of trace-merge, merge-calls, optimized-z3, and unlimited max-active-paths has shown the most influential positive effect (above 0.3). This is followed by a negative effect of the combination of trace-merge, merge-calls, optimized-z3, no-branching-loop, and unlimited max-active-paths. Positive impact with a magnitude of about 0.2 on F-score are attributed to the sets of: (i) trace-merge, merge-calls, disabled branching-loop and unlimited max-active-paths, (ii) merge-calls and unlimited max-active-paths. The merge-calls heuristic also takes part in some of the subsequent sets having negative effects. This is exactly the opposite of what happens for the optimized z3 (which generally has a positive impact). We can thus conclude the following.

- merge calls is very “risky”, even if it appears in several of the best configurations. Alternatively, disjoint union has more constant performance than trace merge.

- max-active-paths (as expected) should be set to unlimited if there are no reasons to do otherwise.

- The optimized z3 is effective, even though it is not the performance leader; it supports many of the other configurations that may need it to be enabled due to resource constraints (e.g., max-active-paths).

- branching loop shows very seesawing effects depending on the configuration in which it is used. This factor requires further evaluation with a higher number of levels to better understand its performance.

- step timeout and min trace size do not have a noticeable effect on F-score.

The results of the factorial experiments show that in our context tuning symbolic execu-
tion is a very complex problem and that the sparsity of effects principle, which states that
the system is dominated by the effects of the main factors and low-order-factor interactions,
does not hold.

**3.6.1 Threats to Validity**

This section discusses the validity [244] of our study according to: construct, internal,
external validity and reliability.

*Construct Validity:* we have performed controlled experiments that allowed us to tune the environment and measure the metrics of interest. In this regard, no issue should arise from our experiential study. We remark that the presented exploratory study is more about exposing which factors are most likely to influence the outcome than on setting up a quantitative model.

*Internal Validity:* we performed a full factorial experiment design with the aim of getting rid of this threat to validity even if we had some *a priori* hypothesis on the most effective heuristics (e.g., the branching-loop-threshold and the z3-optimization) from previous experiments. This design choice has strictly impacted the external validity (discussed in the following). Indeed, by adopting the full factorial experiment design the number of experiments corresponds to `#levels^#factor`, where each experiment required about ~ 4 hours. Therefore adding a single factor would have meant performing 192 experiments instead of 128, hence an additional 1.5 week of computation, and adding two more families would take about 1 extra hour for each experiment. Notwithstanding, our experiment design with two levels per factor (as usually adopted in such a methodology) provides sounder results with respect to a fractional factorial design (the adoption of a response surface methodology is not feasible for timing reason). The choice of a full factorial design in place of a computationally lighter fractional one turned out to be wiser, since (as noted above) the sparsity of effects principle does not hold.

*External Validity & Reliability:* The choice of angr as our symbolic execution framework should not affect validity since the heuristics considered here could be implemented in other frameworks with some engineering effort (e.g., writing plugins for S2E or Triton). Datasets are a common concern in malware research. Our dataset was limited to binaries in PE format and considering 8 known malware families (and an additional group of cleanware samples) collected in 2018 (that we have not extended for experiment timing reasons as discussed above).

The labeling by antivirus is a challenge; our dataset considered samples where a very
strong consensus was shown by the antivirus engines on VirusTotal and therefore the con-
struction of a similar dataset should be straightforward.

Another area to consider is the effect of packed binaries since the symbolic execution
framework could spend time analyzing the packers (instead of the packed binary payloads)
and therefore extract very similar ECDGs. In our case, a post-analysis examination with
VirusTotal allowed to verify that all but one samples in the *addrop* family—which was packed
with NSIS —were unpacked. Therefore it shows that, even in the case of limited symbolic ex-
ecution due to packing, the rest of the analysis is still effective.

Lastly, general limitations of symbolic execution frameworks could limit the applicabil-
ity of the considered malware classification approach. angr has a limited set of models for
external calls and only for specific versions of libraries. Lack of information for other exter-
nal calls or incorrect models due to changes in different versions of the library could prevent
a complete and correct analysis. The same limits are also present in cases when particular
input parameters or network resources are required to start the execution. Assuming the use
of a similar set of malware families (and a family classification consistent with ours), having
adopted the ANOVA test and k-fold validation obtaining evidence with a low significance
level (0.001), our findings should be congruent with ones hypothetically drawn by other re-
searchers (and thus reliable).

**3.7 Conclusion**

The tools used to determine software correctness, reliability, and security rely on many
formal and heuristic configurations. This chapter explored the role of these in the scenario
of malware program analysis, chosen as a particularly challenging form of software analysis.
The results addressed three research questions, overall giving deeper insight into the usage
and configuration of symbolic execution tools.

Our results here showed:

(i) how to tune an SMT solver for symbolic execution (c.f. section 3.5.2, page 139), addressing RQ3.1²²;

(ii) how to prioritize state exploration and parametrize heuristics to improve symbolic ex-
ecution (c.f. section 3.5.3, page 143), addressing **RQ3.2**<fnref n="23" />;

<footnote n="22">22. **RQ3.1: How to tune the SMT solver to improve performance of symbolic execution?**</footnote>

<footnote n="23">23. **RQ3.2: How to effectively apply heuristics that reduce the problem of state explosion in symbolic execution?**</footnote>
(iii) and that there are many positive and negative correlations between heuristics for binary analysis based on symbolic execution in a malware classification scenario (c.f. section 3.5.4, page 146), addressing RQ3.3²⁴.

In particular, the latter shows that significant improvements can be made in analysis engines and toolchains, and that components cannot be optimized in isolation, thus the optimization of the whole toolchain must be considered altogether.

<footnote n="24">24. RQ3.3: What is the impact of enhancing symbolic execution for binary analysis in a malware classification scenario?</footnote>
# STRUCTURAL-BASED BINARY CODE SIMILARITY

## 4.1 Introduction

Historically, malware analysis has heavily resorted to manual creation of signatures for detection and classification. This human-action-based method is very costly and time consuming, thus unable to handle the exponential growth in number of unique malware instances [108]. A solution is to widely automate malware analysis. Towards this goal, this chapter aims to improve the computational cost of existing (and possibly future) malware search and malware clustering algorithms —although the creation of new algorithms for these problems is outside of our scope.

In this chapter we analyze *External Calls Dependency Graphs* (ECDGs) as a promising call graph representation, and a *similarity function* ($\sigma^{ECDG}$) that is reliably *accurate* and *robust*<fnref n="1" />. We show that they lead to an *efficient computation* of binary code similarity able to underpin the construction of frameworks for malware search and clustering.

In our experiments, $\sigma^{ECDG}$ provides highly descriptive *cluster prototypes* that can help to scale up clustering, assist human-based analysis and improve classification models for malware analysis. We devote special attention to the *evaluation methodology*, an intricate issue that directly influences research validity but that is often overlooked. For this, we propose the *Accuracy and Robustness (AnR) paradigm* as guideline to create more *reliable* experiments.

As main contributions, we:

- propose the Accuracy and Robustness (AnR) paradigm for more reliable evaluation methodologies [addresses RQ4.3];

- propose ECDGs, as a more a compact call (dependency) graph enabling more efficient binary similarity computation [addresses RQ4.1];

<footnote n="1">1. Robustness relates to the ability to resist to semantic transformation.</footnote>
— propose a new similarity function for ECDGs that is efficient, accurate and robust [addresses RQ4.2].

Our implementation also provides practical contributions, namely the practical study of symbolic execution to trace external calls, the evaluation of gSpan as a practical algorithm for sub-graph isomorphism, and the evaluation of cluster prototypes extraction to represent malware families. Our whole evaluation is based on experiments with malware samples collected in the wild from real-world dataset feeds.

**4.1.1 Research Questions**

We address the top-level research question **TOP-RQ2**: *How to compute the similarity of unknown programs with high accuracy while being friendly to search and clustering algorithms for malware analysis?*

For this, we break down this backbone question into the following subordinate research questions:

**RQ4.1** *How to get more precise structural representations of programs wrt. state-of-the-art (with no information loss)?*

**RQ4.2** *How to exploit this structural representation to define a similarity function that is friendly to binary code search/clustering schemes?*

**RQ4.3** *Establishing ground truth for malware analysis is an undecidable problem, so how to evaluate this similarity function?*

**4.1.2 Chapter Outline**

The remainder of this chapter is organized as follows:

— Section 4.2 (page 113) presents the specific background of this chapter;

— Section 4.3 (page 159) presents the related works;

— Section 4.4 (page 163) presents our methodology, which introduces ECDGs, similarity function $\sigma^{ECDG}$ and the Accuracy-and-Robustness (AnR) paradigm;

— Section 4.5 (page 168) presents the experimental setup and the evaluation results.

— Section 4.6 (page 182) discusses results.

— Section 4.7 (page 186) concludes.
**4.2 Background**

This section sets the notations used in this chapter (4.2.1), and recalls important notions
on binary code similarity (4.2.2) and hybrid clustering (4.2.3).

**4.2.1 Notations and Definitions**

**Definition 3 (set and multiset)** *We refer as set a collection of elements without repetition, whereas a multiset (or mset) designates a collection of elements in which repetition is allowed.*

**Definition 4 (cardinality)** *The cardinality of a set S is notated as |S|.*

Let $\sim$ denote an equivalence relation on A and $x \in A$. The **equivalence class** of x is the set of all elements of A that are related to x, i.e. $[x]_{\sim} = \{y \in A | x \sim y\}$.

Given a set S, its **indexed family** $\mathcal{I}_S$ consists of an index set defined by a surjective function $x : \mathcal{I}_S \to S$ such that $i \to x_i = x(i), \forall i \in \{1, \dots, |S|\}$.

A **labeled graph** is notated $G(V, E, L_V, L_E, \varphi)$, where $V$ is a multiset of nodes (also notated as $\mathcal{N}(G)$), $E \subseteq V \times V$ is a set of edges, $L_V$ and $L_E$ are sets of node and edge labels respectively, and $\varphi$ is a label function that defines the mapping $V \to V_L$ and $E \to L_E$.

**A directed graph** is a graph where edges $E$ are ordered pairs of elements of $V$. A **directed acyclic graph** is a directed graph with no directed cycle.

Given two graphs $G_1(V_1, E_1, L_{V_1}, L_{E_1}, \varphi_1)$ and $G_2(V_2, E_2, L_{V_2}, L_{E_2}, \varphi_2)$, $G_1$ is a **subgraph** of $G_2$ if $G_1$ satisfies: (i) $V_1 \subseteq V_2$, and $\forall v \in V_1$, $\varphi_1(v) = \varphi_2(v)$, (ii) $E_1 \subseteq E_2$, and $\forall (u, v) \in E_1$, $\varphi_1(u, v) = \varphi_2(u, v)$. This relationship is notated $G_1 \subseteq G_2$.

$G$ is a **connected graph** if it contains a path for every pair of vertices in it. $G$ is **disconnected** (or **disjoint**) otherwise.

A subgraph of $G$ is a **connected component** iff there exists a path between any pair of vertices in it. We notate the set of all **connected components** of $G$ as $\mathcal{CC}(G)$. The **largest connected component** (in number of edges) is noted as $\mathcal{CC}_{max}(G)$.

Given the graphs $G_1$ and $G_2$, $G'$ is a **common subgraph** of $G_1$ and $G_2$ iff $G' \subseteq G_1 \land G' \subseteq G_2$. We note the **largest common subgraph** (which can be disjoint) as $G_1 \cap G_2$.

More information on graphs can be found in [264].

**4.2.2 Binary Code Similarity**

Haq and Caballero point out three main characteristics of binary similarity approaches [119]:
* the type of comparison: identical, similar, equivalent;

* the granularity of the binary code instances (e.g., instructions, basic blocks, functions);

* the number of input instances being compared: one-to-one, one-to-many, many-to-many.

**Comparison type** Two (or more) instances of binary code are *identical* if they have the same syntax, i.e., the same encoding representation [119]. It is a straightforward comparison that is easy to check: the instances of binary code are either identical or they are not. Such comparison approach is very precise, however it is not robust as small —possibly frivolous —changes in the binary code (e.g. metadata as such the compilation date) result in segments of binary code that are no longer identical.

Two (or more) instances of binary code are *equivalent* if they have the same semantics, i.e., if they implement exactly the same functionality [119]. Two identical instances of binary code are unequivocally equivalent, since they impose the same *correctness jurisdiction* (c.f. section 1.2.2, page 36) over the hardware upon execution. Nonetheless, instances of binary code that are very different can be equivalent if they provide the same functionalities: *"equiv-alence does not care about the syntax of the binary code"* [119]. Lakhotia et al [157] show that proving the equivalence of arbitrary instances of binary code can be reduced to the halting problem and is therefore *undecidable*. In practice, determining binary code equivalence is a very expensive process that can only be performed for small instances of binary code [119].

Two (or more) instances of binary code can be considered *similar* if their syntax, semantics, or structure are similar [119]. Structural similarity compares graph representations of the binary code, sitting in between syntactic and semantics. The intuition is that structural representations of the binary code are derived from a syntactic parsing of binary code, but they are able to in some extent express its semantics by capturing the inner data flow dependencies of the instances of binary code. Structural similarity is robust against multiple syntactical transformation, but sensitive to transformations that change code structure such as code inlining or removal of unused function parameters [119];

**Comparison granularity** Instances of binary code can be compared at different granularities, the most common levels being: instruction, basic block, functions, and whole programs [119]. Possibly, approaches that target finer granularity can be combined to attain coarser granularity approaches; due to that, there is a distinction between *input granularity*, which refers to the instances of binary code that are provided as input in the comparison
approaches, and the *approach granularity*, which is the approach target similarity.

**Number of inputs** Approaches for measuring binary code similarity can involve different multiplicities of binary code instances. They can compare instances of binary code in one-to-one (OO), one-to-many (OM) or many-to-many (MM) relationship.

One-to-one approaches compare an original instance of binary code to a target instance of binary code; most OO approaches perform *binary code diffing* [119]. One-to-many approaches compare a *query* instance of binary code to many target instances of binary code; most OM approaches perform binary code search [119]. In contrast to OO and OM approaches, MM approaches do not distinguish between source and target instances; all input instances are considered equal and compared against each other. These approaches typically perform *binary code clustering* [119].

### 4.2.3 Hybrid Clustering

Traditional clustering methods follow specific approaches such as Hierarchical, Partition and Density methods (c.f section 2.2.3, page 75). In contrast, hybrid methods combine different approaches with aim of optimizing their strongest points.

**HDBSCAN** HDBSCAN [39] has similar advantages as DBSCAN (c.f. section 2.2.3, page 78) being able to produce clusters of arbitrary shapes, different sizes and densities, while handling outliers as noise to avoid polluting the clustering model with irrelevant samples. However, HDBSCAN greatly improves on DBSCAN by adding a *hierarchical clustering strategy*; instead of computing clusters based on parametric global density (as DBSCAN does) [183], HDBSCAN obtains highly-varied cluster with different densities. Besides, HSBCAN improves on OPTICS algorithm [10], which also includes a hierarchical strategy, by tackling the limitation of finding just a single global cut/density threshold, which restrains the clustering to a *flat* partition [39].

Table 4.1 shows different strategies taken by clustering methods and how HDBSCAN differs from previous methods. Distance-based methods consider the distance between data points and clusters, whereas density-based methods look to regions surrounding data points and the number of neighbors contained therein. Flat methods provide a set of clusters without any explicit structure relating them together, whereas hierarchical methods provide a (hierarchical) inner structuring of the clusters.
<table><caption>Table 4.1 – Dimensions of clustering methods & methods instances</caption><thead><tr><th></th><th>Flat</th><th>Hierarchical</th></tr></thead><tbody><tr><th>Distance/Parametric</th><td>K-Means</td><td>Agglomerative</td></tr><tr><th>Density/Non-Parametric</th><td>DBSCAN</td><td>HDBSCAN</td></tr></tbody></table>

Similarly to OPTICS (c.f. section 2.2.3, page 78), HDBSCAN works with the reachability distance as metric. However, instead of building a reachability plot for the choice of a cut-off value for $\epsilon'$, HDBSCAN interprets the data points as a graph where the points are vertices and the edges are the mutual reachability distances between them. The graph is extended with self-loops for all vertices having the core distance as weight and then the minimum spanning tree [107] for this graph is computed (forming the MST$_{ext}$ as shown in figure 4.1).

<figure><img src="image_46.png" /><figcaption>Figure 4.1 – Example of MST$_{ext}$ (the color scale of the edges reflects the mutual reachability distance) [163]</figcaption></figure>

The MST$_{ext}$ is converted into a hierarchy of connected components, which results in
a dendrogram as depicted in figure 4.2a. The distance axis indicates the distances (*dist*) between the set of elements included in each branching of a clade<fnref n="2" />, while $\lambda$ is defined as $\lambda := \frac{1}{dist}$. This dendrogram is reinterpreted with respect to the chosen *minimum cluster size*. As long as the “splitting” (as shown in the dendrogram of figure 4.2a) of a cluster does not generate a new cluster (of the minimal size), it is simply considered that the original cluster is losing points (thus technically not splitting). This results in a condensed dendrogram of the hierarchy of connected components of $MST_{ext}$, as shown in figure 4.2b.

Finally, the clusters that persist for a longer $\lambda$ interval are chosen, with the additional requirement that when a cluster is selected, none of its descendants can be chosen any more. The minimal value of $\lambda$ for these clusters are taken, resulting in a final clustering that contains clusters of different densities. Figure 4.2b shows the selected clusters for the previous example of condensed dendrogram.

The complexity of HDBSCAN is dominated by the construction of $MST_{ext}$, which was initially implemented using Prim's algorithm (whose complexity is roughly $\mathcal{O}(n^2)$) [221]. The accelerated version of HDBSCAN [182], which replaces the exact computation of the minimal spanning tree for an approximation version [177], reduces the complexity to roughly $\mathcal{O}(n\log(n))$. Furthermore, further significant improvements in the accelerated HDBSCAN version made possible to obtain a Python implementation of HDBSCAN—compatible with scikit-learn [214]—that is very efficient in practice [184].

## 4.3 Related Works

Our focus in this chapter is on the representation of programs through *call graphs* (ECDGs), benefiting from their *structural similarities* (c.f. section 4.2.2, page 155). For this reason, this chapter entails a closer relationship to researches that study the similarity of binary codes based on structural similarities, especially in the case of *call graphs*.

### 4.3.1 Call Graphs for Binary Code Similarity

The concept of *call graphs* dates back as early as 1979 [246], and as of 2004 [90] a plethora of studies targeting structural similarities for malware analysis have been made. Initially the focus was on the quality of disassemblers, graph formats (i.e. creating labels or grouping nodes) and graph matching algorithms, because feature extraction was done statically [152,

<footnote n="2">2. Stacked branches that break down into further smaller branches up to the leaves, where are the data elements.</footnote>
<figure><img src="image_47.png" /><figcaption>Figure 4.2 – Example of dendrogram showing the hierarchy of connected components of $MST_{ext}$ [163].</figcaption></figure>
[161, 258, 312]. Several *similarity functions* have been proposed and served as basis for code diffing tools, like *BinDiff* [330] and *radiff2* (used in this chapter as benchmark). The main drawback of these approaches is that they operate on hefty graph representations, that though detailed are very expensive to handle in practice, especially considering that graph matching problems fall into the NP class. Furthermore, pure static analysis is more susceptible to syntactical mutations, which can impact the result of the whole similarity analysis.

As of 2007 [16], researches related to *dependency graphs* emerge as dynamic analysis gains traction on malware analysis domain. There too, different graph formats and graph similarity functions, based on various graph matching algorithms, have been proposed [47, 80, 113, 194, 211]. In this case, the main drawback is that the tracing of calls (and OS resources) is done through filters placed as kernel modules/drivers, which is unable to distinguish traces of interest, i.e. those generated by the program main object, from spurious traces generated by shared modules (i.e. library code). This mixture in the traces muddles the subsequent analysis and, once again, produces bigger graph representations that are expensive to process.

Many different representations based on graph notations have been proposed to analyze and characterize programs (e.g. control flow graphs). They model programs as graphs and aim to examine *structural similarities* of codes, which provide analysis techniques that are likely more robust. In malware behavioral research, the most frequently adopted graph representation is in the form of *call graphs* (and derivations), which models the relationships between caller and callee procedures.

The general framework of call graph analysis comprises two main parts[80]:

- **Graph construction algorithm**, which defines the graph format and describes how the calls and any further objects of interest (e.g. OS resources) are obtained through binary analysis in order to construct the graphs.

- **Graph matching algorithm**, which describes how the graphs are compared with the others in order to produce the analysis results.

The *call graph construction* requires static or dynamic binary analysis to obtain the calls. Traditionally, this task has been fulfilled through static analysis [161, 258, 312], where a dis-assembly tool is used to parse binary code and identify caller and callee procedures. The main drawback is that functions imported at runtime —which is common for obfuscation methods like packing—are overlooked.

In the case of dynamic analysis, calls are intercepted and logged at execution time when the monitored/hooked functions are called. This extraction method cannot ensure total
code coverage, nonetheless it has presented positive results for detecting obfuscated mal-
ware [47, 80].

The definition of the graph format has a major impact on the quality of results obtained
by the graph matching algorithm. Christodorescu defined *malspec* as a specification of malici-
cious behavior that consists of a labeled directed graph where the nodes are (Windows) sys-
tem calls and the edges represent argument dependencies between them [47]—to give an
example: $\texttt{RegCreateKeyA} \stackrel{0 \to 1}{\longrightarrow} \texttt{RegCloseKeyA}$ indicates the first argument of RegCloseKeyA
is the return of RegCreateKeyA. Wang *et al.* [298] refer to *Malspec* as *system call dependency
graph* (SCDG).

Shang et al. [258] define the *function-call graph*, which is reused later by Wu et al. [312]. It consists of a direct graph where the nodes are the 5-tuples defined by (function name, function type, pointer to the function first callee, pointer to the function first caller, opcode sequence) and the edges are drawn from caller to callee functions. The function type is determined according to three categories: local-subroutine, DLL function and statically-linked function.

Lee et al. [161] define the *code graph*, which consists of a direct graph whose nodes are function categories and edges are drawn from caller to callee function. The function categories encompass 128 groups that are built from the relationship of 32 kernel objects (e.g. process, memory, socket, etc.) and 4 actions of function behaviors (i.e. open, read, write and close).

Park et al. [211] define two different graphs: i) the kernel object behavioral graphs (KOBG) capturing the interactions between kernel objects that are created and used during execution; ii) the weighted common behavioral graphs (WCBG) constructed by computing the *weighted minimum common supergraph* with the KOBGs obtained from samples of the same family. Using both definitions, the paper proposes a new graph format using kernel objects as vertices and their relationships as edges. The relationships capture resources that are created/used by different system calls during execution. A final graph (the WCBG) is proposed which allows the detection by family and not only on an instance basis.

Elhadi et al. [80] combine and extend the representations of call graphs and *KOBG* to define the *API call graph*. In their proposal, vertexes can represent either system calls or kernel objects captured during the binary analysis, whereas edges are drawn according to different types of dependency relationships between nodes (i.e. sequence, data, declaration or API call).

Table 4.2 shows the different graph formats, binary analysis methods and graph matching
<table><caption>Table 4.2 – Malware detection based on call graphs</caption><thead><tr><th>Graph format</th><th>Analysis</th><th>Graph matching</th></tr></thead><tbody><tr><td>SCDG [47]</td><td>Dynamic</td><td>Minimal Constrast Subgraph</td></tr><tr><td>function-call [312]</td><td>Static</td><td>Sim(G<sub>1</sub>, G<sub>2</sub>) = <sup>2E(G<sub>1</sub>∩G<sub>2</sub>)</sup>&frasl;<sub>E(G<sub>1</sub>)+E(G<sub>2</sub>)</sub></td></tr><tr><td>code graph [161]</td><td>Dynamic</td><td>Sim(G<sub>1</sub>, G<sub>2</sub>) = <sup>E(G<sub>1</sub>∩G<sub>2</sub>)</sup>&frasl;<sub>E(G<sub>1</sub>∪G<sub>2</sub>)</sub></td></tr><tr><td>KOBG/WCBG [211]</td><td>Dynamic</td><td>Minimum Common Supergraph</td></tr><tr><td>API call graph [80]</td><td>Dynamic</td><td>Graph Edit Distance</td></tr></tbody></table>

algorithms chosen in several related works. The results obtained are promising though their validation is impaired by the relatively small malware datasets used [65]. Another important limitation is the need for a ground truth, which implies a very costly manual process to be accomplished in advance.

## 4.4 Methodology

Here we introduce *External Calls Dependency Graphs* (ECDGs) (section 4.4.1, page 163) and their associated similarity function (section 4.4.2, page 164), before introducing the *Accuracy & Robustness Paradigm* (AnR Paradigm) to establish a methodology of framework evaluation (section 4.4.3, page 165). ECDGs are compact, semantic-descriptive and robust *structural representations* of binary codes. The ECDG-associated similarity function can be used in practical search and clustering frameworks. The AnR Paradigm sets the basis for our experimental procedure.

### 4.4.1 External Calls Dependency Graph (ECDG)

A call graph is a direct graph whose nodes represent functions and edges represent one or more invocations of these functions [246]. An ECDG is a call graph whose nodes are restricted to *external calls*, meaning calls to external functions, i.e. system or library calls [144, 151]<fnref n="3" />. ECDGs are modeled in the form of a dependency graph whose edges represent shared arguments between external calls.

The ECDG definition resembles those of *malspec* [47] and *System-call Dependency Graphs (ScD-Graphs)* [205]. ECDGs may be considered as an instance of *malspec* in which the program main object code (see figure 3.10) defines the boundaries of the *trusted computing base*, instead of the whole image of program as in the original work. For *ScD-Graphs*, the

<footnote n="3">3. Unlike the references, we foresee the loading of new (external) functions at runtime.</footnote>
main differences are our extended scope (library calls not being overseen), and the use of labeled edges providing higher precision to our similarity function.

Formally an **External Call Dependency Graph (ECDG)** is a directed acyclic graph $G(V, E, L_V, L_E, \varphi)$ whose node labels $L_V$ are symbolic names of external functions, edges labels $L_E$ are *def-use* dependencies [47] between these functions and $\varphi$ is the labeling function.

The formal definition of a ECDG $\mathcal{G} = (V, E, \gamma, \rho)$ follows as in [47]:

- $V$ is vertex-set and $E$ is edge-set, $E \subseteq V \times V$

- $\gamma$ associates vertices with symbolic functions, $\gamma: V \to \Sigma \times 2^{Vars}$

- $\rho$ associates constraints with nodes and edges, $\rho: V \cup E \to \mathcal{L}$

In our study, a major difference in the graph specification introduced by the use of symbolic execution is the fact each analysis produced a set of traces instead of a single execution path. Therefore, the graph construction can be parameterized to merge common subtraces and/or common *external functions* (i.e. node tags). This parameter choice changes the description of the binary semantic, therefore impacting the evaluation of their structural similarities.

ECDGs are a good alternative for call graphs that incorporate all *def-use* dependencies between calls of a binary program —thus having the potential to be a precise structural representation —while getting rid of nonessential external calls, thereby making this call graph representation more compact (and therefore more suitable for graph matching algorithms). The analysis of ECDGs addresses **RQ4.1: How to get more precise structural representations of programs wrt. state-of-the-art (with no information loss)?**

### 4.4.2 Similarity Function ($\sigma^{ECDG}$)

Our similarity function definition targets the *largest common connected components* of the graphs as well as the *common nodes*. The *common connected components* capture common sub-behaviors, while the *common nodes* spot some degree of implementation resemblance. Thus, our similarity function combines a *localized* behavioral view of the graphs (encompassed in the edges) with a *holistic* behavioral view (encompassed in the nodes) —malware analysis schemes which are based on features computed from plain call tracing are homologous to node-only analysis of ECDGs [3, 45, 141].

The **similarity of two call graphs** $G_1$ and $G_2$ is defined as:

$$ \sigma_{\alpha}(G_1, G_2) = \alpha \sigma_{\text{nodes}}(G_1, G_2) + (1 - \alpha) \sigma_{\text{edges}}(G_1, G_2), $$
where $\alpha \in [0, 1]$ is the **node-edge factor (nef)**.

The **node similarity** $\sigma_{nodes}$ is defined as:

$$ \sigma_{nodes}(G_1, G_2) = \frac{|\mathcal{N}(G_1) \cap \mathcal{N}(G_2)|}{min(|\mathcal{N}(G_1)|, |\mathcal{N}(G_2)|)} $$

The **edge similarity** $\sigma_{edges}$ is defined as:

$$ \sigma_{edges}(G_1, G_2) = \frac{|\mathcal{CC}_{max}(G_1 \cap G_2)|}{min(|\mathcal{CC}_{max}(G_1)|, |\mathcal{CC}_{max}(G_2)|)} $$

Thus, $\sigma_{\alpha}$ combines localized and holistic views of the graph, allowing efficient algorithms to independently compute $\sigma_{edges}$ and $\sigma_{nodes}$. This would be impaired by greedier definitions that take many common disjoint components into account. We use $\sigma^{ECDG}$ to denote the computation of our similarity function on ECDGs.

Since symbolic analysis can generate traces from different execution paths, it is important to balance the two-folded view (localized and holistic) in the graph similarity. For instance, if the largest execution paths of a pair of binaries are the same, independently of any major differences in shorter execution paths, they attain maximal edge-based similarity. However overly relying on common nodes for the similarity definition can produce higher similarity values for graphs with very different edges, thus very different call interdependencies. Either way, graphs that are in fact similar attain high similarities for both components (i.e. edge and node).

Our similarity function ($\sigma^{ECDG}$) is agnostic and therefore it can be used by different search and clustering schemes that are based on pairwise similarity/distances of data points. By proposing a similarity function that can prove to be efficient to compute while being accurate and robust, we address **RQ4.2: How to exploit this structural representation to define a similarity function that is friendly to binary code search/clustering schemes?**

### 4.4.3 Accuracy-and-Robustness (AnR) Paradigm

Methodologies for evaluating malware analysis framework are key to malware analysis research, however a systematic discussion about this topic is often neglected. Evaluations are based on measurements gauged in experiments that use some specific evaluation dataset; however, different datasets may bring different difficulty levels to different experiment setups. This issue becomes prominent when the evaluation methodology requires the definition of (malware) families to provide labels for measuring performance, due to the lack
of outright definition of these categories.

Formal studies on “computer viruses” (malware) show that defining a perfect detector is an undecidable problem [256], conflicting with the ambition of the detection primitive (c.f. section 2.3.2, page 105). The *Template Matching Problem*, which decides whether a given piece of code matches a template behavior in order to build semantic-aware detectors [48], is also *undecidable* [256]. Both results pinpoint that defining perfect (malware) families is theoretically *impossible*.

Li et al. [165] address this issue in the context of malware clustering, studying whether performance results are biased towards high accuracy depending on the methodology followed to select the ground truth. They first compare clustering results of a prior work [23] against clustering frameworks from another domain (plagiarism detection), replicating the same experiment on the same dataset. Then they redo the experiments on all different settings using a new dataset. As in the prior work [23], the ground truth for the F-measure evaluation is set by selecting only samples for which different antivirus tools agree on labeling (antivirus consensus). All frameworks attained good scores on the first dataset (F-measure from 0.943 to 0.960), but performed poorly on the new one (F-measure from 0.609 to 0.630). The authors hypothesize that this may come from the differences in the difficulty level of the datasets (i.e. easy-to-cluster vs difficult-to-cluster), pointing that the **elaboration of a sound evaluation methodology as an open problem**.

Towards this goal, **we propose the Accuracy-and-Robustness (AnR) paradigm as guideline in the evaluation of malware analysis frameworks.** AnR consists in conducting evaluation as a two-phased experiment, in which one phase assesses the *Accuracy* attained by the framework, and the other its *Robustness*.

The **accuracy phase** assesses the framework on a dataset that is likely to be *easy* to evaluate. The main goal is to verify whether the framework is able to generate results that are similar to the ground truth, the latter being assumed accurate by design. This means that the dataset composition should follow more *stringent methodologies*, which are likely to provide less intrinsic disparity between samples, e.g.:

**Outsource consensus:** given a sample, this strategy establishes the ground truth (malware family) by running a malware analysis on multiple anti-malware engines and selecting the label that comes out as consensus (if any). This strategy typically benefits from platforms that aggregates multiple sources of analysis, such as VirusTotal [294]. The weaknesses of this approach are the inconsistencies among analysis results and lack of
universal standards to generate labels [248]. As pointed by Li et al. [165], by enforcing
consensus among results, the diversity representation within the dataset is drastically
reduced.

**Very specific string matching (VSSM)** works on strings<sup>4</sup> that are strong indicators of a given sample and therefore can be used in very specific syntactical signatures, which incurs in extremely low false positive rates [240]. This idea is applied in YarGen [241].

Multiple stringent methodologies may be used to establish different ground truths on a
same dataset, enabling cross-validation for further validation of the results. Furthermore, a
balanced dataset should be privileged to improve the *significance* of the results [165].

The **robustness phase** assesses the framework on a very diversified dataset, which is able to represent a *real world scenario*. For this, the dataset should be built with *looser methodologies*, e.g.:

**Manual labeling** of the whole dataset, ideally following a unique guideline to assign labels to samples.

**Direct outsourcing** that takes as ground truth the output of one single anti-malware. This approach avoid the sample discard issue when anti-malware engines do not agree on labels in the consensus case.

**Public, acknowledged signatures (PAS)** employed to detect specific malware families in the wild (ITW). These rules are often tuned to avoid false positives, while remaining fairly general to maximize variant detection.

In the robustness phase it is essential to purposefully and gradually include *noise*<fnref n="5" /> in the dataset, to measure the impact on the evaluation metrics. This acts as a control group in the evaluation. Therefore, unlike in the accuracy phase, our primarily concern is to observe the inner differences of metric values as noise is inserted, not to seek straightforward correspondence with the ground truth.

Despite the practical consequences that impact the evaluation of malware analysis frame-
works, the problem addressed here has an epistemological nature. Therefore, its solutions
can be to some extent elusive to put in practice. By phasing the experiments and measuring
the metrics evolution as the dataset profile changes (according to some tangible heuristics),
we address **RQ4.3: Establishing ground truth for malware analysis is an undecidable problem, so how to evaluate this similarity function?**

<footnote n="4">4. Not only “text strings”, but generic sequence of bytes, much like in Yara rules.</footnote>

<footnote n="5">5. Samples that do not correspond to any malware family.</footnote>
## Our Evaluation Methodology

We measure and analyze different partitions of our dataset, under the premise that each partition is a “corrupted” version of a true partition but that their combination converges to the truth.

Since we obtain these partitions through unsupervised learning (i.e. clustering) we hinge on external labels only for performance measurements —also under the premise that these labels represent a corrupted version of the truth.

Furthermore, to optimize the computation of clusters, we choose algorithms that can work with precomputed pairwise similarities/distances (computed as $1 - \sigma^{ECDG}$). This incurs a huge initial cost (i.e. $\mathcal{O}(n^2)$) to compute all pairwise distances in order to build the similarity/distance matrix. However, since it can be reused by different algorithms and parameterizations, it fits our goal of producing different partitions of our dataset.

# 4.5 Experiments

This section evaluates the *accuracy* and *robustness* of ECDGs according to $\sigma^{ECDG}$ with a data-driven approach that follows our AnR Paradigm (section 4.4.3). With exception of the dataset, we reuse the experimental setup of the previous chapter (see section 3.5.1). Therefore, in the remainder of this section we present the evaluation dataset (section 4.5.1), the performance benchmark of $\sigma^{ECDG}$ (section 4.5.2), the benchmark comparing $\sigma^{ECDG}$ and *radiff2* (section 4.5.3), the initial parametrization (section 4.5.4), the AnR experiments (section 4.5.5) and a prototype analysis (section 4.5.6).

## 4.5.1 Dataset

We rely on *syntactical signatures* (Yara rules) for dataset composition, because they are typically very precise, with very low false positive rates, and stable in terms of reproducibility across datasets.

To build our evaluation dataset while avoiding defective call traces (see section 3.5.1), we only selected files whose ECDGs have at least 100 edges. Thus, we selected 1,5K samples from a total of 7,306 traces organized in three groups:

* **Group I** contains 600 files matching with manually crafted Yara rules following the VSSM rationale, equally balanced into four families with no overlap between families.
* **Group II** contains 1,001 files from 16 different families defined by public, real-world Yara rules of public repositories (i.e. Yara-Rules, InQuest and McAfee ATR Team), following the PAS rationale, where families are unbalanced and may overlap.

* **Group III** contains 499 randomly chosen benign, cleanware files, with no prior knowledge about them.

Table 4.3 shows the number of samples per family and their corresponding class.

<table><caption>Table 4.3 – Evaluation dataset</caption><thead><tr><th>family</th><th>class</th><th>source ("rare string" or [repository] yar file)</th><th>#samples</th></tr></thead><tbody><tr><td>Mira</td><td>I</td><td>"Mira.h"</td><td>150</td></tr><tr><td>Shohdi</td><td>I</td><td>"USR_Shohdi_Photo_USR"</td><td>150</td></tr><tr><td>Bogy</td><td>I</td><td>"BOGY'S GAME ENGINE"</td><td>150</td></tr><tr><td>TwarBot</td><td>I</td><td>"TwarBot"</td><td>150</td></tr><tr><td>spyeye</td><td>II</td><td>[Yara-rules] MALWMiscelanea.yar</td><td>162</td></tr><tr><td>Wabot</td><td>II</td><td>[Yara-rules] MALW_Wabot.yar</td><td>162</td></tr><tr><td>IceID_Bank_trojan</td><td>II</td><td>[Yara-rules] MALW_IcedID.yar</td><td>149</td></tr><tr><td>shylock</td><td>II</td><td>[Yara-rules] MALW_Miscelanea.yar</td><td>109</td></tr><tr><td>Bublik</td><td>II</td><td>[Yara-rules] MALW_Bublik.yar</td><td>88</td></tr><tr><td>sakula_v1_3</td><td>II</td><td>[Yara-rules] RAT_Sakula.yar</td><td>80</td></tr><tr><td>Njrat</td><td>II</td><td>[Yara-rules] RAT_Njrat.yar</td><td>58</td></tr><tr><td>njrat1</td><td>II</td><td>[Yara-rules] RAT_Njrat.yar</td><td>58</td></tr><tr><td>win_exe_njRAT</td><td>II</td><td>[Yara-rules] RAT_Njrat.yar</td><td>58</td></tr><tr><td>Cerberus</td><td>II</td><td>[Yara-rules] RAT_Cerberus.yar</td><td>50</td></tr><tr><td>Glasses</td><td>II</td><td>[Yara-rules] MALW_Glasses.yar</td><td>45</td></tr><tr><td>Mirage_APT</td><td>II</td><td>[Yara-rules] APT_Mirage.yar</td><td>41</td></tr><tr><td>ClamAV_Emotet_String_Aggregate</td><td>II</td><td>[InQuest] ClamAV_Emotet_String_Aggregate.rule</td><td>36</td></tr><tr><td>Monero_Mining_Detection</td><td>II</td><td>[McAfee ATR Team] MINER_Monero.yar</td><td>27</td></tr><tr><td>Warp</td><td>II</td><td>[Yara-rules] MALW_Warp.yar</td><td>9</td></tr><tr><td>Cleanware</td><td>III</td><td>-</td><td>499</td></tr></tbody></table>

### 4.5.2 Benchmark: Framework

Our focus in this chapter is the study of ECDGs and $\sigma^{ECDG}$; nonetheless, generating the ECDGs for the new dataset requires to repeat part of the experimental procedure of section 3.5.3 (page 143). The difference is that previously ECDGs were computed for a smaller dataset with many different parametrizations, whereas now we use a single set of parameters —chosen from the lessons learnt in chapter 3 (page 111)—with a bigger and more diversified dataset.

This section provides another benchmark for the symbolic execution of our toolchain. Here we use the new dataset (c.f. section 4.5.1, page 168) in complement to the one studied
in chapter 3.

This benchmark includes the total number of traces, i.e. 7,306 prior selection. The pa-
rameters for the symbolic execution with *angr-extractor* (see section 3.5.1) are the following:

*   *Max memory:* 8GB

• *timeout:* 3600s

• step timeout: 8s

• symbolic loop threshold: 4

• max active paths: 8

The default solver for the z3 backend used by Claripy was changed to:

s = z3.ParOr(
z3.Tactic(tactic='qflra', ctx self._context),
z3.Tactic(tactic='qfidl', ctx =self._context),
z3.AndThen(
z3.Tactic(tactic= 'solve-eqs',ctx =self._context),
z3.Tactic(tactic='fail', ctx =self._context)), # from satisfiable
z3.Tactic(tactic='qfufbv_ackr', ctx =self._context), #from AND-ing batch_eval
z3.Tactic(tactic='qfauflia', ctx =self._context), # from max()
z3.Tactic(tactic= 'smt',ctx =self._context), # from min()
z3.Tactic(tactic= 'qfbv',ctx =self._context),
z3.Tactic(tactic= 'qfaufbv',ctx =self._context)
).solver()

The profile of the extraction times for traces is shown in figure 4.3. The majority of the
analysis take under 10 minutes [600s] to complete, averaging an extraction time of 583s. The
stop causes are largely dominated (~ 93%) by the memory consumption that exceeds the
predefined limit; this is a known issue with symbolic execution (as discussed in section 3.2.1,
page 113). The remainder of the analysis terminates because there are no more traces to be
explored (~ 7%) and in very few cases the 1h timeout was reached.

Figure 4.4 shows the distribution of maximum memory taken in the course of the sym-
bolic execution per time of analysis. The colors show the stop cause for each execution and
the radius size of each point represent the quantity of calls obtained in the given analysis
run.
<figure><img src="image_48.png" /><figcaption>Figure 4.3 – Profile of the extraction time for all the traces</figcaption></figure>
<figure><img src="image_49.png" /><figcaption>Figure 4.4 – Distribution of maximum memory vs time per analysis. The colors show the stop cause and the radius of each entry is proportional to the number of calls extracted.</figcaption></figure>
4.5.3 Benchmark: $\sigma^{ECDG}$ vs. radiff2

To evaluate the time efficiency of $\sigma^{ECDG}$ in a practical scenario, we carried out a benchmark evaluation comparing our approach against radiff2, an open-source tool dedicated to binary comparison in radare2 suite [228]. For this, we attempted to compute all pairwise similarities with the files of group I. However since radiff2 can take an overwhelmingly long time to compute all pairwise similarities, we stopped the process after three weeks of computation, obtaining ~ 175k pairwise similarities (for each of radiff2 and $\sigma^{ECDG}$) that we named *Benchmark-DS*.

Our framework keeps a cache of the already computed ECDGs, which greatly speeds up the whole computation process. Table 4.4 notates this optimization by cached-(CA + GC) + $\sigma^{ECDG}$. To measure the storage cost of this trade-off, we plotted the graph for *file size* vs. *#edges* taking into account over 10K files shown in figure 4.5. The scattered points have an almost linear profile and their linear regression results in a slope of 44.81(±0.02) edges by Kb of storage, where the biggest cache file takes 113Kb for 4806 edges.

<figure><img src="image_50.png" /><figcaption>Figure 4.5 – Plot of *#edges* vs. *cache size* (KB) for 12K random files</figcaption></figure>

Table 4.4 shows that $\sigma^{ECDG}$ largely outperforms (in time) radiff2, achieving a speedup gain of 3.30x and 354.11x for the standard and cache-enhanced implementations wrt. radiff.

It also shows that individual jobs in the *code analysis* and *graph generation* stage are much more expensive than the *graph analysis* jobs (i.e. $\sigma^{ECDG}$). However the latter largely
<table><caption>Table 4.4 – Benchmark evaluation</caption><thead><tr><th>Stage</th><th>Dataset group</th><th>job time<br>MEAN (SD, MED)</th><th>% common<br>subgraph</th></tr></thead><tbody><tr><td>Code analysis (CA)<br>Graph generation (CG)</td><td>I + II + III</td><td>640.32s (419s, 478s)</td><td></td></tr><tr><td>σ<sup>ECDG</sup></td><td>I</td><td>10.27s (25s, 3ms)</td><td>54,84%</td></tr><tr><td>σ<sup>ECDG</sup></td><td>II</td><td>8.67s (20,6s, 4ms)</td><td>57,45%</td></tr><tr><td>σ<sup>ECDG</sup></td><td>II + III</td><td>7.21s (19.5s, 4ms)</td><td>51,60%</td></tr><tr><td>radiff2</td><td>Benchmark-DS</td><td>4181.35s (6580s, 2031s)</td><td></td></tr><tr><td>CA + GC + σ<sup>ECDG</sup></td><td>Benchmark-DS</td><td>1266.78s (570s, 1104s)</td><td></td></tr><tr><td>cached-(CA + GC) + σ<sup>ECDG</sup></td><td>Benchmark-DS</td><td>11.81s (24s, 2.5s)</td><td></td></tr></tbody></table>

dominates the overall calculation time because it requires a quadratic number of computations (to build the similarity/distance matrix), while the former ones grow linearly with respect to the total number of instances. So our modular approach allowed us to devote more effort to the gSpan implementation, reducing memory footprint more than 100x, achieving 35x speedup with multi-threading and up to 6x speedup with a single thread wrt. original implementation [318].

To compare the similarity results of $\sigma^{ECDG}$ and radiff2, their values were split into four categories: strong-dissimilarity ($\in [0, 0.25]$), weak-dissimilarity ($\in [0.25, 0.5]$), weak-similarity ($\in [0.5, 0.75]$) and strong-similarity ($\in [0.75, 1]$).

<figure><img src="image_51.png" /><figcaption>Figure 4.6 – Contingency matrix of $\sigma^{ECDG}/radiff2$</figcaption></figure>

Figure 4.6 shows the contingency matrix of $\sigma^{ECDG}/radiff2$, where each cell contains the
percentage of pairs in *Benchmark-DS* whose similarity felt into weak/strong similarity/dis-
similarity (notated as SIM/~SIM) for $\sigma^{\text{ECDG}}$ and *radiff2*. Ideally, supposing that $\sigma^{\text{ECDG}}$ and *radiff2* were both flawless, all values would be placed in the matrix main skew diagonal. However, we note that in general $\sigma^{\text{ECDG}}$ is able to find stronger similarities than *radiff2* for the same pair of files. In particular, $\sigma^{\text{ECDG}}$ found strong similarities where *radiff2* found weak and strong dissimilarities for 12.04% and 4.94% of the file pairs, respectively. A hypothesis to explain the differences in the similarity values obtained with $\sigma^{\text{ECDG}}$ and *radiff2* is the fact that $\sigma^{\text{ECDG}}$ targets semantic similarity whereas *radiff2* relies on comparisons of the programs control-flow graphs.

**4.5.4 Parametrization: NEF Selection**

We do an exploratory analysis to select a value for parameter *nef*, as required by the setup of *σ<sup>ECDG</sup>* (c.f. section 4.4.2, page 164). Since *group I* contains files corresponding to the most trustworthy ground truth in the dataset, we use this group for the analysis. Furthermore, we target the *homogeneity score* as our main metric of interest.

In this exploration, we build various similarity/distance matrices containing all pairwise
computations of $\sigma^{\text{ECDG}}$ with different *nef* values. For each matrix we compute clustering in-
stances using different algorithms: Agglomerative, DBSCAN, HDBSCAN and OPTICS. For
algorithms that require input parameters (i.e. DBSCAN and Agglomerative), we performed a
hyper-parameter tuning, which adds up to four more clustering instances for each *nef* iter-
ation.

Figure 4.7 shows the *nef* exploration for HDBSCAN with homogeneity score as target metric —the remaining curves are shown in appendix section 6.7.1 (page 334). Overall, the profile of all metric curves for OPTICS and HDBSCAN are fairly similar, whereas HBSCAN and Agglomerative have significantly different performances depending on the metric chosen as target. In all cases, the best scores are achieved with *homogeneity* or *silhouette* as target metric, while the worst are obtained with the *completeness* score. When tuned by *silhouette* score, both HDBSCAN and Agglomerative clustering displayed a decay in completeness score for *nef* ≥ 0.5.

As outcome of the whole exploratory analysis, we selected value 0.25 for *nef*, because it
provides positive results for all metrics, in particular for the *homogeneity score*. It also takes
both nodes and edges components of $\sigma^{\text{ECDG}}$ into account, thus balancing between localized
and holistic views of the graphs.

We present and discuss only the clustering results of HDBSCAN in the following exper-
<table><caption>Table 4.5 – Clusterings for nef = 0.25</caption><thead><tr><th></th><th>DBSCAN</th><th>HDBSCAN</th><th>OPTICS</th><th>Aggl.</th></tr></thead><tbody><tr><td>#clusters</td><td>6</td><td>7</td><td>7</td><td>13</td></tr><tr><td>#noise</td><td>5</td><td>4</td><td>2</td><td>3</td></tr><tr><td>silhouette</td><td>0.969</td><td>0.955</td><td>0.956</td><td>0.978</td></tr><tr><td>similarity</td><td>0.946</td><td>0.954</td><td>0.949</td><td>0.991</td></tr><tr><td>homogeneity</td><td>0.995</td><td>0.983</td><td>0.978</td><td>0.995</td></tr><tr><td>completeness</td><td>0.846</td><td>0.796</td><td>0.796</td><td>0.828</td></tr></tbody></table>

iments, since the exploratory analysis shows very stable and good results for homogeneity and completeness scores.

<figure><img src="image_52.png" /><figcaption>Figure 4.7 – nef exploration for HDBSCAN</figcaption></figure>

### 4.5.5 Accuracy-and-Robustness (AnR) Analysis

Our experiments aim to evaluate $\sigma^{ECDG}$ accuracy, robustness and practical efficiency, all prerequisites to enable functional application like malware search and malware clustering.
## Accuracy phase

We evaluate $\sigma^{ECDG}$ accuracy, only on files in *group I*. This phase derive directly from the *nef* selection exploratory analysis. Here we detail the corresponding experiment, i.e. clustering of *group I* files with HDBSCAN and *nef* = 0.25.

Clustering results for this phase (see also table 4.5, column HDBSCAN) are shown in table 4.6, and illustrated in the heatmap figure 4.8. They contain 8 clusters and 4 singletons, with 0.955 silhouette, 0.954 mean similarity, 0.983 homogeneity and 0.796 completeness, the latter two computed with Yara rules created for the definition of the *group I*.

<table><caption>Table 4.6 – Accuracy phase clusters</caption><thead><tr><th>Cluster</th><th>#samples</th><th>Similarity</th><th>Yara Rule</th><th>#samples (per rule)</th></tr></thead><tbody><tr><td>0</td><td>127</td><td>0.979</td><td>Shohdi</td><td>127</td></tr><tr><td rowspan="2">1</td><td rowspan="2">132</td><td rowspan="2">0.96</td><td>Shohdi</td><td>2</td></tr><tr><td>TWarBot</td><td>130</td></tr><tr><td>2</td><td>132</td><td>0.998</td><td>Mira</td><td>132</td></tr><tr><td>3</td><td>18</td><td>1.000</td><td>Mira</td><td>18</td></tr><tr><td>4</td><td>6</td><td>0.998</td><td>Shohdi</td><td>6</td></tr><tr><td>5</td><td>150</td><td>0.994</td><td>Bogy</td><td>150</td></tr><tr><td>6</td><td>10</td><td>0.701</td><td>Shohdi</td><td>10</td></tr><tr><td rowspan="2">7</td><td rowspan="2">21</td><td rowspan="2">1.0</td><td>Shohdi</td><td>1</td></tr><tr><td>TWarBot</td><td>20</td></tr></tbody></table>

The clusters are very well discriminated. Out of 600 files, only 3 samples are found in mixed clusters (according to our ground truth): two Shohdi samples in cluster #1 and one in cluster #7, both composed predominantly of TWarBot samples. All other clusters are pure and cluster #5 is complete, including all 150 Bogy samples.

## Robustness phase

We evaluate the robustness of $\sigma^{ECDG}$ using *real world* samples (*group II* files). We assess how much the clustering degrades as *noise* (*group III* files) is gradually inserted in the evaluation dataset. Table 4.7 shows the clusterings (HDBSCAN with *nef* = 0.25) of the initial state (*group II* files) and of the final state (*group II* and *group III* files).

The initial clustering results in 20 clusters with 54 singletons (figure 4.10), with scores of 0.789 silhouette, 0.974 mean similarity, 0.746 homogeneity and 0.712 completeness, where the two last metrics are computed with public Yara rules (i.e. PAS) as ground truth.
<table><caption>Table 4.7 – Robustness phase clusters: initial (group II) and final (group II + group III)</caption><thead><tr><th colspan="4">Cluster index</th><th colspan="4">Initial</th><th colspan="4">Final</th></tr><tr><th>Initial</th><th>Final</th><th>#samples</th><th>Similarity</th><th>Yara rule</th><th>#samples (per rule)</th><th>#samples</th><th>Similarity</th><th>Yara rule</th><th>#samples (per rule)</th><th>#samples</th><th>Similarity</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>9</td><td>0.978</td><td>ClamAV_Emotet_String_Aggregate</td><td>9</td><td>9</td><td>0.978</td><td>ClamAV_Emotet_String_Aggregate</td><td>9</td><td>9</td><td>0.978</td></tr><tr><td>4</td><td>1</td><td>10</td><td>0.951</td><td>spyeye</td><td>2</td><td>10</td><td>0.951</td><td>spyeye</td><td>2</td><td>10</td><td>0.951</td></tr><tr><td>3</td><td>2</td><td>158</td><td>0.987</td><td>Glasses</td><td>8</td><td>158</td><td>0.987</td><td>Glasses</td><td>8</td><td>158</td><td>0.987</td></tr><tr><td>-</td><td>3</td><td></td><td></td><td>Wabot</td><td>158</td><td>5</td><td>0.98</td><td>Wabot</td><td>158</td><td>1</td><td>0.98</td></tr><tr><td>12</td><td>4</td><td>7</td><td>1.000</td><td>spyeye</td><td>7</td><td>7</td><td>1.000</td><td>spyeye</td><td>7</td><td>1</td><td>1.000</td></tr><tr><td>13</td><td>5</td><td>19</td><td>0.993</td><td>spyeye</td><td>19</td><td>19</td><td>0.993</td><td>spyeye</td><td>19</td><td>2</td><td>0.993</td></tr><tr><td>14</td><td>6</td><td>18</td><td>0.998</td><td>spyeye</td><td>18</td><td>18</td><td>0.998</td><td>spyeye</td><td>18</td><td>2</td><td>0.998</td></tr><tr><td>9</td><td>7</td><td>23</td><td>0.995</td><td>spyeye</td><td>23</td><td>23</td><td>0.995</td><td>spyeye</td><td>23</td><td>3</td><td>0.995</td></tr><tr><td>6</td><td>8</td><td>11</td><td>0.819</td><td>spyeye</td><td>11</td><td>14</td><td>0.605</td><td>spyeye</td><td>11</td><td>3</td><td>0.605</td></tr><tr><td>10</td><td>9</td><td>15</td><td>0.993</td><td>spyeye</td><td>15</td><td>15</td><td>0.993</td><td>spyeye</td><td>15</td><td>3</td><td>0.993</td></tr><tr><td>11</td><td>10</td><td>6</td><td>1.000</td><td>spyeye</td><td>6</td><td>6</td><td>1.000</td><td>spyeye</td><td>6</td><td>4</td><td>1.000</td></tr><tr><td>8</td><td>11</td><td>59</td><td>0.992</td><td>ClamAV_Emotet_String_Aggregate</td><td>1</td><td>59</td><td>0.992</td><td>ClamAV_Emotet_String_Aggregate</td><td>1</td><td>5</td><td>0.992</td></tr><tr><td></td><td></td><td></td><td></td><td>Njrat</td><td>58</td><td></td><td></td><td>Njrat</td><td>58</td><td>5</td><td>0.992</td></tr><tr><td></td><td></td><td></td><td></td><td>njrat1</td><td>58</td><td></td><td></td><td>njrat1</td><td>58</td><td>5</td><td>0.992</td></tr><tr><td></td><td></td><td></td><td></td><td>win_exe_njRAT</td><td>58</td><td></td><td></td><td>win_exe_njRAT</td><td>58</td><td>5</td><td>0.992</td></tr><tr><td>2</td><td>12</td><td>10</td><td>0.995</td><td>IceID_Bank_trojan</td><td>10</td><td>10</td><td>0.995</td><td>IceID_Bank_trojan</td><td>10</td><td>1</td><td>0.995</td></tr><tr><td>-</td><td>13</td><td></td><td></td><td></td><td></td><td>24</td><td>0.997</td><td>Glasses</td><td>1</td><td>2</td><td>0.997</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>IceID_Bank_trojan</td><td>21</td><td>2</td><td>0.997</td></tr><tr><td></td><td></td><td></td><td></td><td>Warp</td><td>1</td><td></td><td></td><td>Warp</td><td>1</td><td></td><td>0.997</td></tr><tr><td></td><td></td><td></td><td></td><td>Wabot</td><td>4</td><td></td><td></td><td>Wabot</td><td>4</td><td></td><td>0.997</td></tr><tr><td>1</td><td>14</td><td>187</td><td>0.997</td><td>Glasses</td><td>1</td><td>193</td><td>0.998</td><td>cleanware</td><td>10</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>IceID_Bank_trojan</td><td>26</td><td></td><td></td><td>IceID_Bank_trojan</td><td>23</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>sakula_v1_3</td><td>80</td><td></td><td></td><td>sakula_v1_3</td><td>80</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>Bublik</td><td>88</td><td></td><td></td><td>Bublik</td><td>88</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>ClamAV_Emotet_String_Aggregate</td><td>5</td><td></td><td></td><td>ClamAV_Emotet_String_Aggregate</td><td>5</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>Glasses</td><td>32</td><td></td><td></td><td>Glasses</td><td>32</td><td>2</td><td>0.998</td></tr><tr><td>7</td><td>15</td><td>128</td><td>0.994</td><td>Mirage_APT</td><td>41</td><td>127</td><td>0.998</td><td>Mirage_APT</td><td>41</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>Cerberus</td><td>49</td><td></td><td></td><td>Cerberus</td><td>49</td><td>2</td><td>0.998</td></tr><tr><td></td><td></td><td></td><td></td><td>spyeye</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-</td><td>16</td><td></td><td></td><td></td><td></td><td>5</td><td>0.934</td><td>cleanware</td><td>5</td><td>2</td><td>0.934</td></tr><tr><td>-</td><td>17</td><td></td><td></td><td></td><td></td><td>24</td><td>0.998</td><td>cleanware</td><td>24</td><td>2</td><td>0.998</td></tr><tr><td>-</td><td>18</td><td></td><td></td><td></td><td></td><td>34</td><td>0.990</td><td>cleanware</td><td>34</td><td>2</td><td>0.990</td></tr><tr><td></td><td></td><td></td><td></td><td>ClamAV_Emotet_String_Aggregate</td><td>5</td><td></td><td></td><td>ClamAV_Emotet_String_Aggregate</td><td>1</td><td>2</td><td>0.990</td></tr><tr><td></td><td></td><td></td><td></td><td>Glasses</td><td>2</td><td></td><td></td><td>Glasses</td><td>2</td><td>2</td><td>0.990</td></tr><tr><td></td><td></td><td></td><td></td><td>spyeye</td><td>12</td><td></td><td></td><td>spyeye</td><td>12</td><td>2</td><td>0.990</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>cleanware</td><td>40</td><td>2</td><td>0.990</td></tr><tr><td>5</td><td>19</td><td>19</td><td>0.877</td><td>ClamAV_Emotet_String_Aggregate</td><td>1</td><td>55</td><td>0.516</td><td>ClamAV_Emotet_String_Aggregate</td><td>1</td><td>2</td><td>0.516</td></tr><tr><td></td><td></td><td></td><td></td><td>Monero_Mining_Detection</td><td>6</td><td>16</td><td>0.988</td><td>Monero_Mining_Detection</td><td>7</td><td>2</td><td>0.988</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>cleanware</td><td>8</td><td>2</td><td>0.988</td></tr><tr><td>18</td><td>21</td><td>5</td><td>1.000</td><td>Monero_Mining_Detection</td><td>5</td><td>6</td><td>0.998</td><td>Monero_Mining_Detection</td><td>6</td><td>2</td><td>0.998</td></tr><tr><td>-</td><td>22</td><td></td><td></td><td></td><td></td><td>10</td><td>0.959</td><td>Warp</td><td>2</td><td>2</td><td>0.959</td></tr><tr><td>-</td><td>23</td><td></td><td></td><td></td><td></td><td>8</td><td>0.985</td><td>cleanware</td><td>8</td><td>2</td><td>0.985</td></tr><tr><td>-</td><td>24</td><td></td><td></td><td></td><td></td><td>12</td><td>0.867</td><td>cleanware</td><td>1</td><td>2</td><td>0.867</td></tr><tr><td>-</td><td>25</td><td></td><td></td><td></td><td></td><td>10</td><td>0.927</td><td>cleanware</td><td>11</td><td>2</td><td>0.927</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>IceID_Bank_trojan</td><td>9</td><td>2</td><td>0.927</td></tr><tr><td>17</td><td>26</td><td>133</td><td>0.995</td><td>IceID_Bank_trojan</td><td>26</td><td>133</td><td>0.995</td><td>IceID_Bank_trojan</td><td>26</td><td>2</td><td>0.995</td></tr><tr><td></td><td></td><td></td><td></td><td>shylock</td><td>109</td><td></td><td></td><td>shylock</td><td>109</td><td>2</td><td>0.995</td></tr><tr><td></td><td></td><td></td><td></td><td>spyeye</td><td>1</td><td></td><td></td><td>spyeye</td><td>1</td><td>2</td><td>0.995</td></tr><tr><td></td><td></td><td></td><td></td><td>Monero_Mining_Detection</td><td>11</td><td></td><td></td><td>Monero_Mining_Detection</td><td>11</td><td>2</td><td>0.995</td></tr><tr><td></td><td></td><td></td><td></td><td>IceID_Bank_trojan</td><td>84</td><td>108</td><td></td><td>IceID_Bank_trojan</td><td>83</td><td>2</td><td>0.995</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>cleanware</td><td>13</td><td>2</td><td>0.995</td></tr><tr><td>16</td><td>28</td><td>27</td><td>0.995</td><td>Glasses</td><td>1</td><td>29</td><td>0.997</td><td>Glasses</td><td>1</td><td>2</td><td>0.997</td></tr><tr><td></td><td></td><td></td><td></td><td>spyeye</td><td>25</td><td></td><td></td><td>spyeye</td><td>25</td><td>2</td><td>0.997</td></tr><tr><td></td><td></td><td></td><td></td><td>ClamAV_Emotet_String_Aggregate</td><td>1</td><td></td><td></td><td>cleanware</td><td>3</td><td>2</td><td>0.997</td></tr><tr><td>-</td><td>29</td><td></td><td></td><td></td><td></td><td>13</td><td>0.954</td><td>cleanware</td><td>13</td><td>2</td><td>0.954</td></tr><tr><td>noise</td><td></td><td></td><td></td><td></td><td>54</td><td></td><td></td><td></td><td>340</td><td></td><td></td></tr></tbody></table>
<figure><img src="image_53.png" /><figcaption>Figure 4.8 – Heatmap of clusters in the *accuracy phase*</figcaption></figure>

This experiment creates a majority of pure clusters (11 of 20), especially for smaller clusters, which suggests that $\sigma^{\text{ECDG}}$ can discriminate MW families at the variant level. For instance, *spyeye* produces 7 pure clusters and another one which is almost pure (25 of 27 samples). In addition, some bigger clusters are completely or almost pure. Cluster #3 is pure, with 158 *Wabot* samples and cluster #8 includes 58 *Njrat* samples from a total of 59 samples.

Cluster #1 (187 samples) has the greatest number of different families (6), dominated by *Bublik* (88 samples) and *sakula_v1_3* (80 samples). Furthermore, 13 samples are detected by both Yara rules, which suggests some commonality between both families. Similarly, cluster #17 includes all 109 *shylock* samples along with 26 *IceID_Bank_trojan*, two samples being detected by both Yara rules.

Our clustering also exposes lower quality Yara rules like *ClamAV_Emotet_String_Aggregate*, which performs poorly. Indeed, this rule was heuristically generated, as revealed by its description:“a pruned aggregate of all Emotet related strings extracted from ClamAV on 2019-07-03”. Yet, out of 36 samples detected by this rule, 9 sit together in pure cluster #0 and 13 others appear scattered in 5 other clusters. This result reinforces our claim that $\sigma^{\text{ECDG}}$ is *accurate*.

To evaluate the robustness of our behavioral clustering, **we gradually introduce clean-**
**ware samples of group III** to act as noise in the dataset and we measure the disturbance introduced by this action. Figure 4.10 shows the initial clustering, before inserting clean-ware samples in the dataset, and figure 4.11 shows the final clustering, after the insertion of the cleanware samples. Figure 4.9 shows the impact of *group III* files on our target clustering metrics<fnref n="6" />.

Homogeneity slightly increases after inserting 50% benign files (1/3 of the whole final dataset). Silhouette is the most affected metric, being impacted by new, rather small, spurious clusters. The final clustering achieved scores of 0.464 silhouette, 0.950 mean similarity, 0.738 homogeneity and 0.607 completeness. The NMI measured between the initial and final clusterings was 0.974, meaning that the information loss due to insertion of noise was only marginal.

Table 4.7 displays the clusters after complete insertion of *group III* files in the final clustering. As expected, most cleanware are not included in any cluster, which increases the number of singletons (noise) from 30 in the initial clustering to 340 in the final one. Most of thee original clusters remain unaffected (grey rows in table 4.7), only 4 being altered by the inclusion of a few cleanware instances (red rows). A few clusters finish with less files or have some files replaced, which increases the clusters mean average similarity (green rows). Ten new clusters are created (yellow rows), of which four of them comprising only cleanware, and the others include a few malware samples but with relatively low average similarity.

The results confirm that $\sigma^{ECDG}$ is *robust* even with highly polluted datasets.

### 4.5.6 Prototype Analysis

A cluster prototype is defined as *a data object that is representative of the other objects in the cluster* [278]. Here, for a given cluster, we define the *cluster prototype $P_τ(C)$* as the greatest common connected subgraph with minimum support threshold $τ$ (c.f. section 3.2.2, page 122) for the entire set of graphs in this cluster. We explore the *cluster prototypes* by incrementing $τ$ from 0.05 to 1.0 with 0.05 steps, trying to compute prototypes for all clusters at each iteration. We repeat this with the clusterings of the *accuracy phase* and the initial clustering of the *robustness phase*.

For the clusterings of the *accuracy phase*, all support values below 1 successfully produce prototypes for *all clusters*. Only one cluster fails to provide a prototype for support value equal 1. Figure 4.12a shows an example of *cluster prototype* obtained during the *accuracy*

<footnote n="6">6. To recall the definition and use of evaluation metrics, refer to the sections 2.2.1 (page 60) and 2.2.3 (page 82).</footnote>
<figure><img src="image_54.png" /><figcaption>Figure 4.9 – Noise evaluation in the *robustness phase* [HDBSCAN (nef =0.25)]</figcaption></figure>

<figure><img src="image_55.png" /><figcaption>Figure 4.10 – Initial clusterings: *group II* files</figcaption></figure>
<figure><img src="image_56.png" /><figcaption>Figure 4.11 – Final clusterings: *group II* + *group III* files</figcaption></figure>

*phase* for cluster#5, which corresponds to the *Bogy* family (cluster #5). For the initial clustering of the *robustness phase*, when *nef* ≤ 0.5 all clusters successfully produce prototypes, i.e. at least one common subgraph can be found in half of samples for each individual cluster. For greater *nef* values, the rate of prototypes decreases almost linearly. This means that the clusters have in general a core of nearly half of their samples that bear a high similarity, while the other half of the samples (i.e. less similar) gets gradually incorporated in the cluster. Figure 4.13 shows the percentage of clusters that successfully produce prototypes as function of the support.

This behavior is convenient to unveil hidden similarities between malware families and variants, which would be impossible with the all-or-nothing approach of syntactical signatures. Figure 4.12b shows an example of *cluster prototype* obtained for cluster#2.

**4.6 Discussion**

This chapter analyzes $\sigma^{ECDG}$, which proved to be an efficient structural representation of programs that is reliably accurate and precise. We first tackled general research issues, namely the paradigm that guide our malware analysis evaluation (c.f. section 4.4.3, page 165).
<figure><img src="image_57.png" /><figcaption>Figure 4.12 – Examples of clustering prototypes</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>Figure 4.13 – Prototype exploration for the *robustness phase*</figcaption></figure>
After showing that code similarity schemes can be extended to address search and clustering, we focused on the analysis of ECDGs and $\sigma^{ECDG}$ in terms of properties desired to implement practical frameworks.

ECDGs are obtained from dependencies between external calls, therefore they are beyond the reach of any purely syntactic obfuscation (e.g. instruction replacement, opaque predicates, etc.), although syntax obfuscation can still be effective in thwarting the underlying analysis for the call tracing (e.g. our symbolic execution). Some obfuscation techniques, such as packing, can also insert new code (e.g. unpacking stub) with new external calls; however as long as this code does not interfere with the original one, the new additional calls will ensue as disjoint components added to the original ECDG, without breaking our method. To be effective against ECDG itself, the obfuscation needs to actually replace external calls or alter their argument dependencies; this procedure is much more complex than syntactic obfuscation and is not yet observed in the wild.

Furthermore, although unfit for large datasets, our evaluation clustering is able to assess the efficiency, accuracy and robustness of $\sigma^{ECDG}$. This construction can be practical with clustering strategies like those proposed by Kostakis [151] and Zhang et al [326], keeping the same properties verified here.

Table 4.4 shows that $\sigma^{ECDG}$ calculation throughout the whole dataset has median time in the order of milliseconds, and that inclusion of noise results in lower average time to compute similarity. Indeed, gSpan typically finishes very quickly when two (or more) input graphs do not have any common subgraph. Assuming that samples of a same family represent just a small part of an entire dataset, this behavior is suitable to address the search problem, which makes $\sigma^{ECDG}$ a good practical alternative for this problem.

Our prototype analysis (section 4.5.6, page 180) shows that many cluster prototypes are naturally produced, even when bigger support values are used. This is a positive consequence of using *subgraph isomorphism* as basis of $\sigma^{ECDG}$, which opens the possibility for optimization strategies like *scalable clustering* [235]. Furthermore, the cluster prototypes obtained are very descriptive (c.f. figure 4.12b), which allows assisting human analysis or training models for specific malware families.

*Limitations.* Our call extraction module extends angr with 24,052 new stub *Sim Procedures* of commonly used functions, highly improving code coverage, hence the quality of our ECDGs. However, our experiments have limits related to state explosion in symbolic execution [17]; the main reason for job termination (93%) during *code analysis* was memory exhaustion. Additionally, the limitations of symbolic execution to handle packed binaries are
well known. To address this, we tested angr option to enable self-modifying code support<sup>7</sup>,
but this setting did not produce any noticeable gain. We noticed that packed samples often
resulted in the extraction of few calls of the unpacking routines (e.g. *LoadLibraryA* and *Get-ProcAddress*), nonetheless several samples of the evaluation dataset were flagged by packing
detection tools. Due to the 100 edges threshold (c.f. section 4.5.1, page 168) and the use of
syntactical signatures, which are likely to fail with packed samples, the removal of packed
binaries was not specifically handled in our work.

A possible mitigation for both issues is a smarter combination of *concrete* and *symbolic* execution (i.e. *concolic execution*) instead of pure symbolic execution. This technique should be able to bypass the unpacking routine of (simple) packers and to perform expensive analyses (i.e. CPU and memory intensive) only in a few parts of the code. To further improve the quality of call dependencies for edges in ECDGs, instead of plain comparison of (symbolic) values, a future work can include the implementation of taint analysis, where arguments and returns of functions are more finely tracked.

The computation of our similarity/distance matrix for the evaluation clearly does not scale for very big datasets. So our *evaluation* dataset for this paper is restricted in size, but this does not affect our method itself nor its practical usability. Indeed, it is only used to evaluate the accuracy and robustness of *σ<sup>ECDG</sup>*, as well as to produce benchmarks that assess its efficiency in practice. Overall, the problem of clustering scalability (i.e. a scheme that requires asymptotically less pairwise computations) is out of the scope of this work. Nonetheless, such clustering can of course benefit from more efficient, accurate and robust pairwise similarity computations.

**4.6.1 Threats to Validity**

This section discusses the validity [244] of our study according to: construct, internal,
external validity and reliability.

*Construct Validity:* we conducted a controlled experiment following the Accuracy and Robustness paradigm, which allows to assess individually and incrementally the properties of accuracy and robustness of our similarity function $\sigma^{ECDG}$. To support this evaluation, we painstakingly built our evaluation dataset leveraging a combination of heuristics that are likely to select samples in accordance with the desired profile. In this regard, no issue should arise from our experiential study.

<footnote n="7">7. Parameter that enables the emulation of code from the current state instead of the original memory, notwithstanding memory protections.</footnote>
*Internal Validity:* our analysis follows an incremental approach, which intends to isolate the properties assessed in each evaluation phase. This diligence expressly aims to improve the internal validity of the study, therefore no issue regarding this matter should arise.

*External Validity:* the foundations of our work methodology are akin to other already validated in the literature —ECDG is a special type of call graph, which are well-established in malware analysis, and our similarity function $\sigma^{ECDG}$ is based on properties exploited by traditional methods for graphs comparison (i.e. common nodes and common subgraphs). Furthermore, our evaluation uses learning methods without any *ad-hoc* customization to our scenario, thus not affecting the generalization of these algorithms. In this sense, there should be no issue with generalization of the methodologies proposed in this study. However, the evaluation dataset can be problematic to generalization as the true profile of the population of malware and cleanware is unknown; therefore, it is impossible to know for a fact where our dataset misrepresents the true population, which could engender a selection bias issue. This is withal an unmanageable issue, which is a common concern in malware research.

*Reliability:* our study is based on a set of concepts and methods that are of public knowledge and well established in literature. We provide all details necessary to reproduce the analysis, and our dataset was sufficiently large to avoid the occurrence of serendipitous results (specially when considering the computation of all pairwise similarities). Furthermore, our construction uses public available Yara rules that allow to replicate the generation process of a new dataset with properties similar to ours.

## 4.7 Conclusion

We defined ECDG, a new call graph to optimize the representation of argument dependencies between calls, that allows concise structural representation with no information loss. It has a major positive impact on performance, because graph matching algorithms, which are very expensive, can deal with much smaller graphs.

We proposed a new similarity function $\sigma^{ECDG}$ that is efficient, achieving a speedup gain of 3.30x and 354.11x for the standard and cache-enhanced implementations wrt. *radiff*. Our similarity function is also reliably *accurate* and *precise*. To support this, we built an evaluation framework to cluster samples based on $\sigma^{ECDG}$ and we evaluated the results under the AnR paradigm.

The *accuracy phase* produced almost unerring results, with homogeneity score of 0.983,