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

HAL
open science

# Data-driven malware classification assisted by machine learning methods

Cassius Puodzius

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

## To cite this version:

Cassius Puodzius. Data-driven malware classification assisted by machine learning methods. Other [cs.OH]. Université de Rennes, 2022. English. NNT: 2022REN1S090. tel-04072990v4

HAL Id: tel-04072990

https://theses.hal.science/tel-04072990v4

Submitted on 18 Apr 2023

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
UNIVERSITÉ DE

RENNES 1

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

# THÈSE DE DOCTORAT DE

L'UNIVERSITÉ DE RENNES 1

ÉCOLE DOCTORALE N° 601

Mathématiques et Sciences et Technologies
de l'Information et de la Communication

Spécialité : INFO

Par

Cassius PUODZIUS

## Data-Driven Malware Classification Assisted by Machine Learning Methods

Thèse présentée et soutenue à Rennes, le 19 décembre 2022

Unité de recherche : INRIA

### Rapporteurs avant soutenance :

Jacques KLEIN PR Université du Luxembourg

Amedeo NAPOLI DR Emérite (HDR) CNRS, LORIA

### Composition du Jury :

Président : Nathalie BERTRAND PR (HDR) Université Rennes 1

Examineurs : Eric ALATA MCF INSA Toulouse

Olivier BARAIS PR Université Rennes 1

Jacques KLEIN PR Université du Luxembourg

Amedeo NAPOLI DR Emérite (HDR) CNRS, LORIA

Olivier ZENDRA CR INRIA Rennes

Dir. de thèse : Ludovic ME DR INRIA Rennes
<figure><img src="image_5.png" /></figure>
ACKNOWLEDGEMENT

I express my heartfelt gratitude to my advisors, *Olivier Zendra* and *Annelie Heuser*, for their unrelenting support, guidance, and encouragement throughout my thesis. Their patience, knowledge, and wisdom have been indispensable in guiding me through the research process. Their insights, feedback, and suggestions have been essential in shaping my research and this thesis. I am thankful for the privilege of working with such dedicated advisors.

I extend my gratitude to my thesis supervisor, *Ludovic Mé*, for their support throughout my thesis. I am truly grateful for the chance to work with such an accomplished researcher who was always available to offer valuable assistance whenever needed.

I also extend my thanks to the members of my thesis committee, *Nicolas Rougier* and *Veronica Valeros*, for their insightful feedback and suggestions. I am grateful for their time, expertise, and invaluable contributions to the process.

I acknowledge the support and resources provided by INRIA, through the TAMIS and DiverSE teams, which made this research possible. I am thankful for the opportunities and facilities provided by the institution that helped me conduct my research and complete this thesis.

Over the almost five years that I have been in INRIA I had the privilege of meeting and working with many talented colleagues. I extend my gratitude to my numerous colleagues for their support and encouragement throughout my thesis journey. Their camaraderie and professional insights have been a source of motivation and inspiration. I am grateful for the positive work environment and the opportunity to learn from such brilliant individuals.

In terms of my personal life, this thesis engendered major changes. Venturing to France and starting a new life in Rennes was a formidable challenge. Therefore, I want to express my greatest gratitude to my family and friends (old ones and new ones), who have supported me throughout this long and adventurous journey. Their encouragement and support helped me to stay motivated and focused during the challenging times. I am truly grateful for their love and support.

Special thanks to my dear sweetheart, *Angèle Chevillard*, for her unwavering support and tireless efforts in overcoming the challenges we faced together, making the fulfillment of
thesis possible. I extend my gratitude to my in-laws, who provided me with immense support and comfort throughout my thesis journey. Their love and encouragement have been a source of strength, and I am grateful for the bond we have formed.

Deepest gratitude to my beloved friends who have been a part of this journey. Their encouragement, companionship, and support have been integral to this experience and have made it truly memorable. To mention but a few: *Jean Carlos Padilha*, *Gustavo Santos Guimarães* (our *Guga*), *Lucas Souza*, my dear friends of the "Petit Comité", *Collectif Caxangá*, *Toucouleurs*. There are no words to express my gratitude for everything we have been through together and I am deeply thankful for it.

Last but not least, my family. My deepest gratitude to my family, who have been my source of support and encouragement throughout this journey. Despite the challenges posed by the COVID-19 pandemic, despite time and distance, I always felt their presence. I am truly thankful for their encouragement and for always being there for me, through thick and thin. Their constant love and belief in me have provided me with the strength to face the challenges and pursue my dreams. I am really grateful to have such a supportive family.

My utmost gratitude goes to my parents, *Vera Lopes de Oliveira* and *Douglas Napoleão Puodzius*, for their steadfast love and caring throughout this journey. Despite the challenges we faced, their belief in me has pushed me to reach this far and I couldn't be more grateful. I am proud to call you my parents and I will be forever grateful for the role you have played in shaping who I am today. Thank you for always being there for me and for always believing in me.

Finally, I would like to dedicate this thesis to the memory of my dear uncle, *Jairo Luis Soares Tenório*, who was a constant source of inspiration. His untimely passing during the course of my studies was a great loss, but his spirit remains with me, pushing me forward. He was devoted to helping me from the very beginning of this journey and his shining example served as a guiding light throughout. I am forever grateful for his guidance and inspiration, and this achievement would not have been possible without him. I hope that in some way, this dedication will serve as a testament to the impact he had on my life and to the legacy he left behind.
# RÉSUMÉ ÉTENDU

Les logiciels malveillants, ou malwares, sont un problème majeur dans le domaine de la sécurité informatique. Leur capacité à se dissimuler et à éviter la détection les rend extrêmement dangereux pour les entreprises, les gouvernements et les particuliers. Historiquement, l'analyse des malwares était une tâche manuelle, nécessitant une expertise humaine pour identifier ses caractéristiques et pour les classer en fonction de leurs comportements. Cependant, cette approche est coûteuse en ressources et chronophage, ce qui ne permet pas de faire face aux scénarios modernes de cybermenaces.

L'automatisation de l'analyse des malwares est donc devenue un enjeu majeur dans le domaine de la sécurité informatique. L'objectif de cette thèse est d'améliorer l'automatisation de l'analyse des malwares en adoptant une approche dirigée par les données et en évitant autant que possible l'intervention humaine. Pour cela, nous nous concentrons sur la classification des malwares, qui permet d'optimiser le traitement de grands corpus de malwares en identifiant les ressemblances entre des instances similaires.

Afin de travailler sur les thématiques principales, cœur de notre recherche, nous avons établi l'axiologie de notre étude. Cette étape préliminaire nous a permis de poser les bases de notre recherche en définissant les fondements qui ont guidé notre démarche scientifique tout au long de cette thèse.

En résumé, dans ce chapitre, nous avons discuté des aspects ontologiques et épistémologiques de l'analyse des malwares. Nous avons adopté une approche en deux volets pour établir une ontologie de malware : une approche historique et une approche analytique. L'approche historique consiste à examiner l'histoire de l'émergence des concepts dans le domaine de l'analyse des malwares, tandis que l'approche analytique se concentre sur un examen conceptuel de ce dernier. Nous avons également discuté de l'épistémologie de la recherche en malware. Pour cela, nous avons souligné que la recherche en malware est principalement *fondationnaliste* et nous avons identifié certaines limites à cette approche. Nous avons également reconnu que la sécurité informatique est une activité socialement enracinée, qui ne peut être complètement exemptée d'intervention humaine. Or, par ailleurs, nous pouvons nous appuyer sur l'apprentissage machine pour largement alléger et optimiser l'effort d'analyse.
Dans l'ensemble, notre discussion ontologique et épistémologique nous a permis de formuler un paradigme de recherche pour la suite de notre étude de classification des malwares. Ensuite, nous avons structuré notre travail en trois étapes principales, qui ont permis d'approfondir et de compléter les objectifs que nous nous étions fixés.

Dans un premier temps, nous avons étudié de nouvelles façons d'exploiter l'exécution symbolique dans l'analyse des malwares, en accordant une attention particulière à l'utilisation optimale des tactiques des solveurs SMT et aux réglages des hyperparamètres. La méthode d'exécution symbolique est une alternative aux méthodes d'analyse plus courantes, telles que l'analyse statique et l'analyse dynamique. En effet, l'analyse dynamique présente une importante limitation vis-à-vis de la couverture du code, tandis que l'analyse statique a une vue complète du code binaire, mais ne peut pas l'exécuter. Quant à l'analyse symbolique, elle permet d'émuler l'exécution du code binaire tout en gardant un contrôle précis sur tous les éléments de l'analyse, ce qui peut résoudre ces limitations. Dans ce contexte, nous avons évalué l'exécution symbolique, ainsi qu'amélioré son utilisation dans le cadre de l'analyse des malwares. Nous nous sommes intéressés en particulier à la détermination précise des appels effectués lors de l'exécution, y compris les appels qui peuvent être initialement obscurcis dans le code source. Nous avons évalué différentes techniques pour guider et optimiser l'analyse symbolique, en mesurant leur impact sur la classification des malwares. Les résultats obtenus montrent que l'exécution symbolique peut être utile en pratique pour l'analyse des malwares; de plus, l'optimisation des paramètres de l'analyseur peut largement améliorer sa performance.

Dans un deuxième temps, nous nous sommes concentrés sur la représentation du comportement des logiciels, en accordant une attention particulière à sa précision et à sa robustesse. Nous proposons ainsi une méthode d'analyse basée sur les graphes de dépendance des appels externes (ECDG) pour la représentation du comportement, ainsi qu'une fonction de similarité ($\sigma^{ECDG}$) pour leur comparaison. Cette représentation est compacte, pour autant elle n'engendre pas de perte d'information; ainsi elle permet d'accélérer son traitement par des algorithmes d'analyse des graphes. Cette étude propose également une méthodologie d'évaluation avec le paradigme "Accuracy and Robustness (AnR)", utilisé pour l'analyse des résultats obtenus lors de nos expérimentations. Ces résultats ont montré que la méthode proposée est efficace et a un potentiel important pour la classification et la détection des malwares. Les principales contributions incluent donc la proposition du paradigme AnR pour une méthodologie d'évaluation plus fiable, l'introduction d'ECDGs pour une représentation plus compacte des graphes d'appels, et la définition de la fonction de similarité ($\sigma^{ECDG}$),
avérée efficace, précise et robuste pour comparer des ECDGs.

Enfin, dans un troisième temps, nous nous sommes focalisés sur le partitionnement des logiciels, en concevant une méthode qui ne restreint pas la combinaison des caractéristiques syntaxiques et comportementales. Elle peut permettre également une montée en charge conséquente des analyses en pratique. Pour cela, nous avons élaboré une nouvelle stratégie de traitement basée sur des techniques de partitionnement d'ensemble, combinées avec la représentation vectorielle des données extraites des logiciels.

Les méthodes traditionnelles basées sur des signatures sont sujettes à des techniques anti-analyse efficaces pour échapper à la détection. Pour pallier à cette insuffisance, il est nécessaire d'améliorer l'efficacité de l'apprentissage automatique dans l'analyse des logiciels malveillants. Pour ce faire, il faut résoudre plusieurs défis majeurs, notamment la sélection des caractéristiques, leur représentation et l'exactitude des algorithmes d'apprentissage automatique. Dans ce contexte, l'approche de sélection des caractéristiques hybrides basée sur l'analyse dynamique et statique est prometteuse. Elle diversifie les outils et les techniques utilisés pour extraire les caractéristiques, tout en fournissant plusieurs vues du jeu de données qui peuvent être interprétées comme des partitions imparfaites convergentes vers une vraie partition, une fois combinées.

En résumé, cette troisième partie décrit la conception d'un cadre de classification des malwares appelé EMB-DUET. Ce cadre est capable de traiter des caractéristiques hétérogènes, ce qui permet d'améliorer les performances globales. Pour améliorer l'efficacité de l'apprentissage automatique, le cadre utilise la technique de plongement numérique (numerical embedding) pour transformer les vues non structurées en vecteurs numériques, pouvant être efficacement analysés par différents algorithmes. Les méthodes de clustering par ensemble (ensemble clustering) sont utilisées pour consolider toutes les vues individuelles en un seul clustering. Notre étude décrit également l'impact et les effets de différents hyperparamètres impliqués dans EMB-DUET et la vectorisation des ECDGs basée sur la technique de régression SVM.

Les contributions principales de cette partie sont donc la proposition d'EMB-DUET comme cadre de classification de données, ainsi que la vérification de l'exactitude et de la robustesse offertes par l'agrégation des différentes vues de données (à savoir, les strings, les n-grammes et les ECDGs). EMB-DUET s'avère capable de traiter des caractéristiques hétérogènes en s'appuyant sur le plongement numérique pour améliorer les performances globales. En outre, cette étude fournit des directives pour le réglage approprié des hyperparamètres impliqués dans EMB-DUET, ainsi que pour l'apprentissage de la représentation vectorielle des
ECDGs avec la régression SVM.

En résumé, nos principales contributions sont les suivantes :

- Élaboration d'une ontologie réaliste pour la caractérisation des instances de programmes malveillants.

- Discussion des implications épistémologiques et des limites de l'utilisation de l'apprentissage automatique dans la classification des malwares.

- Analyse de l'effet des différents paramètres heuristiques sur les solveurs SMT dans l'utilisation de l'exécution symbolique pour tracer les appels de programmes pour la construction des ECDGs.

- Étude de l'efficacité, exactitude et robustesse des ECDGs en tant que représentation singulière (birthmark) pour la structure des programmes informatiques.

- Proposition d'EMB-DUET en tant que cadre polyvalent de classification des malwares, utilisant des techniques de plongement numérique pour le traitement efficace de grands corpus de données.

En conclusion, la thèse étudie la problématique de la classification des malwares et s'attaque au scénario moderne des malwares multiples et hautement complexes en s'appuyant sur des méthodes d'apprentissage automatique. La thèse examine également les questions ontologiques et épistémologiques liées à la recherche sur les malwares et à l'apprentissage automatique. Notre étude est donc menée en trois étapes qui suivent l'enchainement basique des étapes de l'apprentissage automatique: i) [extraction des données] l'amélioration des outils pour l'analyse des malwares, ii) [transformation des données] l'étude de la représentation comportementale des codes binaires et iii) [analyse des données] la proposition d'un framework polyvalent appelé EMB-DUET.

Les résultats de nos expériences ont montré que notre méthode de classification de logiciels malveillants était efficace pour gérer des ensembles de données complexes et multifacettes. Les contributions de cette thèse ont ainsi permis de proposer une approche innovante et efficace pour la classification des malwares dans un contexte de haute complexité.
# TABLE OF CONTENTS

<table><tr><td>Introduction</td><td>15</td></tr><tr><td>Context &amp; Motivation</td><td>15</td></tr><tr><td>Problem Statement</td><td>19</td></tr><tr><td>Research Objectives</td><td>22</td></tr><tr><td>Research Questions</td><td>22</td></tr><tr><td>Contributions</td><td>23</td></tr><tr><td>Thesis Outline</td><td>23</td></tr><tr><td>1 Epistemological View on Malware Research</td><td>25</td></tr><tr><td>1.1 Introduction</td><td>25</td></tr><tr><td>1.2 An Ontology of Malware</td><td>26</td></tr><tr><td>1.2.1 Historical Approach</td><td>27</td></tr><tr><td>1.2.2 Analytical Approach</td><td>34</td></tr><tr><td>1.3 An Epistemology of Malware Research</td><td>44</td></tr><tr><td>1.3.1 Background</td><td>45</td></tr><tr><td>1.3.2 Epistemological Matters of Cybersecurity</td><td>50</td></tr><tr><td>1.4 An Axiology</td><td>54</td></tr><tr><td>1.5 Conclusion</td><td>56</td></tr><tr><td>2 General Background</td><td>57</td></tr><tr><td>2.1 Introduction</td><td>57</td></tr><tr><td>2.2 Machine Learning</td><td>57</td></tr><tr><td>2.2.1 Definitions and Terminology</td><td>58</td></tr><tr><td>2.2.2 Supervised Learning</td><td>64</td></tr><tr><td>2.2.3 Unsupervised Learning</td><td>74</td></tr><tr><td>2.3 Malware Analysis</td><td>87</td></tr><tr><td>2.3.1 Binary Analysis</td><td>88</td></tr><tr><td>2.3.2 Malware Analysis Primitives</td><td>98</td></tr><tr><td>2.4 Discussion</td><td>106</td></tr></table>
<table><tbody><tr><td>2.5</td><td>Conclusion</td><td>107</td></tr><tr><td>3</td><td>Call Tracing with Symbolic Execution</td><td>111</td></tr><tr><td>3.1</td><td>Introduction</td><td>111</td></tr><tr><td>3.1.1</td><td>Research Questions</td><td>112</td></tr><tr><td>3.1.2</td><td>Chapter Outline</td><td>113</td></tr><tr><td>3.2</td><td>Background</td><td>113</td></tr><tr><td>3.2.1</td><td>Symbolic Execution</td><td>113</td></tr><tr><td>3.2.2</td><td>Frequent Subgraph Mining (FSM)</td><td>122</td></tr><tr><td>3.3</td><td>Related Works</td><td>123</td></tr><tr><td>3.4</td><td>Methodology</td><td>127</td></tr><tr><td>3.4.1</td><td>SMT Optimization</td><td>129</td></tr><tr><td>3.4.2</td><td>Enhanced Symbolic Execution</td><td>130</td></tr><tr><td>3.4.3</td><td>Impact on Malware Classification</td><td>132</td></tr><tr><td>3.5</td><td>Experiments</td><td>135</td></tr><tr><td>3.5.1</td><td>Implementation Setup</td><td>136</td></tr><tr><td>3.5.2</td><td>Optimizing z3 for symbolic execution of binary files</td><td>139</td></tr><tr><td>3.5.3</td><td>Overall Toolchain Optimization</td><td>143</td></tr><tr><td>3.5.4</td><td>Impact of graph and execution heuristics</td><td>146</td></tr><tr><td>3.6</td><td>Discussion</td><td>147</td></tr><tr><td>3.6.1</td><td>Threats to Validity</td><td>150</td></tr><tr><td>3.7</td><td>Conclusion</td><td>151</td></tr><tr><td>4</td><td>Structural-Based Binary Code Similarity</td><td>153</td></tr><tr><td>4.1</td><td>Introduction</td><td>153</td></tr><tr><td>4.1.1</td><td>Research Questions</td><td>154</td></tr><tr><td>4.1.2</td><td>Chapter Outline</td><td>154</td></tr><tr><td>4.2</td><td>Background</td><td>155</td></tr><tr><td>4.2.1</td><td>Notations and Definitions</td><td>155</td></tr><tr><td>4.2.2</td><td>Binary Code Similarity</td><td>155</td></tr><tr><td>4.2.3</td><td>Hybrid Clustering</td><td>157</td></tr><tr><td>4.3</td><td>Related Works</td><td>159</td></tr><tr><td>4.3.1</td><td>Call Graphs for Binary Code Similarity</td><td>159</td></tr><tr><td>4.4</td><td>Methodology</td><td>163</td></tr><tr><td>4.4.1</td><td>External Calls Dependency Graph (ECDG)</td><td>163</td></tr></tbody></table>
<table><tbody><tr><td>4.4.2</td><td>Similarity Function ($\sigma^{ECDG}$)</td><td>164</td></tr><tr><td>4.4.3</td><td>Accuracy-and-Robustness (AnR) Paradigm</td><td>165</td></tr><tr><td>4.5</td><td>Experiments</td><td>168</td></tr><tr><td>4.5.1</td><td>Dataset</td><td>168</td></tr><tr><td>4.5.2</td><td>Benchmark: Framework</td><td>169</td></tr><tr><td>4.5.3</td><td>Benchmark: $\sigma^{ECDG}$ vs. radiff2</td><td>173</td></tr><tr><td>4.5.4</td><td>Parametrization: NEF Selection</td><td>175</td></tr><tr><td>4.5.5</td><td>Accuracy-and-Robustness (AnR) Analysis</td><td>176</td></tr><tr><td>4.5.6</td><td>Prototype Analysis</td><td>180</td></tr><tr><td>4.6</td><td>Discussion</td><td>182</td></tr><tr><td>4.6.1</td><td>Threats to Validity</td><td>185</td></tr><tr><td>4.7</td><td>Conclusion</td><td>186</td></tr><tr><td>5</td><td>EMB-DUET: Multi-Feature Clustering Based on Numerical Embedding</td><td>189</td></tr><tr><td>5.1</td><td>Introduction</td><td>189</td></tr><tr><td>5.1.1</td><td>Research Questions</td><td>190</td></tr><tr><td>5.1.2</td><td>Chapter Outline</td><td>191</td></tr><tr><td>5.2</td><td>Background</td><td>191</td></tr><tr><td>5.2.1</td><td>Support-Vector Machines (SVMs)</td><td>191</td></tr><tr><td>5.2.2</td><td>Embedding Learning</td><td>195</td></tr><tr><td>5.2.3</td><td>Clustering Ensembles</td><td>201</td></tr><tr><td>5.3</td><td>Related Works</td><td>204</td></tr><tr><td>5.3.1</td><td>Hybrid Features for Malware Analysis</td><td>204</td></tr><tr><td>5.3.2</td><td>Numerical Embedding for Malware Analysis</td><td>207</td></tr><tr><td>5.4</td><td>Methodology</td><td>208</td></tr><tr><td>5.4.1</td><td>EMB-DUET</td><td>208</td></tr><tr><td>5.4.2</td><td>$\sigma^{ECDG}$-learning with SVM Regression</td><td>210</td></tr><tr><td>5.5</td><td>Experiments</td><td>212</td></tr><tr><td>5.5.1</td><td>Implementation Setup</td><td>212</td></tr><tr><td>5.5.2</td><td>Dataset</td><td>216</td></tr><tr><td>5.5.3</td><td>$\sigma^{ECDG}$-Learning with SVM Regression</td><td>218</td></tr><tr><td>5.5.4</td><td>EMB-DUET</td><td>227</td></tr><tr><td>5.6</td><td>Discussion</td><td>252</td></tr><tr><td>5.6.1</td><td>Threats to Validity</td><td>255</td></tr><tr><td>5.7</td><td>Conclusion</td><td>256</td></tr></tbody></table>
<table><tr><td><strong>Conclusion</strong></td><td style="text-align: right;"><strong>259</strong></td></tr><tr><td style="padding-left: 2em;">5.7.1 Future Work</td><td style="text-align: right;">262</td></tr><tr><td><strong>Bibliography</strong></td><td style="text-align: right;"><strong>269</strong></td></tr><tr><td><strong>6 Appendix</strong></td><td style="text-align: right;"><strong>301</strong></td></tr><tr><td style="padding-left: 2em;">6.1 Basic Formal Ontology (BFO)</td><td style="text-align: right;">301</td></tr><tr><td style="padding-left: 2em;">6.2 Logistic Equation and the Sigmoid Function</td><td style="text-align: right;">303</td></tr><tr><td style="padding-left: 2em;">6.3 Density-Based Clustering Methods</td><td style="text-align: right;">307</td></tr><tr><td style="padding-left: 2em;">6.4 Mutual Information</td><td style="text-align: right;">308</td></tr><tr><td style="padding-left: 2em;">6.5 PE Headers</td><td style="text-align: right;">309</td></tr><tr><td style="padding-left: 2em;">6.6 Call Tracing with Symbolic Execution</td><td style="text-align: right;">310</td></tr><tr><td style="padding-left: 4em;">6.6.1 Supplementary analysis</td><td style="text-align: right;">310</td></tr><tr><td style="padding-left: 4em;">6.6.2 Evaluation Dataset</td><td style="text-align: right;">331</td></tr><tr><td style="padding-left: 2em;">6.7 Structural-Based Binary Code Similarity</td><td style="text-align: right;">334</td></tr><tr><td style="padding-left: 4em;">6.7.1 NEF Selection: Detailed Analysis</td><td style="text-align: right;">334</td></tr><tr><td style="padding-left: 2em;">6.8 EMB-DUET: Multi-Feature Clustering Based on Numerical Embedding</td><td style="text-align: right;">344</td></tr><tr><td style="padding-left: 4em;">6.8.1 SVM</td><td style="text-align: right;">344</td></tr><tr><td style="padding-left: 4em;">6.8.2 EMB-DUET</td><td style="text-align: right;">345</td></tr></table>
Context & Motivation

The eminence of computer systems in our society is patent. The presence of information
technology in our society is ubiquitous and in the course of the last decades it has revolu-
tionized the ways in which individuals communicate, learn, work, do shopping, travel, and
so forth.

The dawn of this technological revolution can be traced back to the works on computabil-
ity theory started by Alan Turing in the 1930's, passing through the construction of the first
general-purposed machines in the 1940's, the creation of the first programming languages in
the 1950's and the prototyping of the modern computer in the 1960's. As of the 1970's —with
the invention of *floppy disks* and the *Ethernet*, the release of the first video-game (Atari) and
the foundation of technology companies, like Microsoft and Apple, that popularized the use
of computer technology —information technology ceases being a subject circumscribed to
academic and military research to start gaining a foothold in society.

The 1980's marks the advent of personal computers; the 1990's the creation of the world wide web and the first uses of website in everyday life (like Google Search launched in 1998); the 2000's the popularization of the Internet with the expansion of social medias; and the 2010's the progress of cloud computing and the widespread use of smartphone and other connected devices. The bottom line is that we have been witnessing progressive waves of a digital revolution, which is becoming increasingly accelerated and pervasive in society over time.

The International Telecommunication Union (ITU) <fnref n="1" /> estimates that the number of indi-
viduals who have used the Internet attained 4.9 billion people in 2021 [132], which corre-
sponds to 62.5% of the world population. According to the World Economic Forum's (WEF)
2020 Global Risk Report [305], there are one million additional people joining the Internet ev-
ery day. Due to COVID, in the last few years the increase of internet users soared —which is
referred as the “COVID connectivity boost”. ITU estimates that the COVID pandemic brought
an increment of 782 million Internet users in a period of just two years, which accounts for

<footnote n="1">1. The United Nations specialized agency for information and communication technologies.</footnote>
the largest annual connectivity growth rates ever recorded.

The report of the United Nations (UN) Secretary-General's High-level Panel on Digital Cooperation [210] recommends that by 2030, "every adult should have affordable access to digital networks, as well as digitally-enabled financial and health services", as digital technologies are deemed imperative to fulfill the Sustainable Development Goals (SDGs) endorsed by 193 UN member states in 2015. In Europe, the European Commission (EC) established as connectivity objective that for all European households, rural or urban, they must have access to an internet connectivity of at least 100 Mbps, upgradable to Gigabit speed [59].

On top of that, new technologies such as the 5G network and the Internet of Things (IoT)<fnref n="2" /> usher in yet another technological disruption.

Cisco estimates [51] that the number of connected devices will grow from 18.4B in 2018 to 29.3B in 2023, which corresponds to 3.6 devices per capita in 2023. The profile of these devices is also evolving: in 2018, only 33% (6.1B) of all networked devices were IoT devices<fnref n="3" />, while 27% (4.9B) were smartphones and 12% (2.2B) were PCs and Tablets; by 2023, it is estimated that 50% (14.7B) of the networked devices will be IoT devices, while 23% (6.7B) will be smartphones and only 7% (2.1B) will be PCs and Tablets. As for the profile of the network connection, Cisco estimates that by 2023, 45% of all networked devices will be connected through mobile network, whereas the remainder will be connected through wires or Wi-Fi; 5G will account for 10.6% of total mobile connections by 2023, compared to 0% in 2018.

These new technologies are bringing more convergence of the digital and physical worlds, as IoT devices have been integrated into everyday objects (e.g. clothing, manufactured products, foodstuffs, medicines, etc). McKinsey Global Institute estimates that by 2030, "IoT could enable $5.5 trillion to $12.6 trillion in value globally, including the value captured by consumers and customers of IoT products and services" [49]; from which, the largest amount of potential economic is in the factory setting (~ 26%) —which includes standardized production environments in manufacturing, hospitals, and other areas —and the second largest is in the human-health setting (~ 10% – 14%).

The projected scenario is a world in which computer technology is ever more integrated in everyday life, ever more ubiquitous, and performing critical tasks that have been traditionally accomplished offline. Therefore, "global security and stability are increasingly dependent on digital security" [210].

Near the end of the first decade of the years 2000, global leaders in the public and pri-

<footnote n="2">2. Roughly, the IoT consists of sensors and actuators that are connected by networks to computing systems.</footnote>

<footnote n="3">3. Cisco's report refers to *Machine-to-Machine (M2M) modules*.</footnote>
vate sectors engaged in a broad range of initiatives and directives to secure the cyberspace. The WEF's 2010 Global Risk Report [299] included "critical information systems and cyber-vulnerability" in the section of risks to keep on the radar, as they were still perceived by experts as relatively low in terms of likelihood and severity, and among the least interconnected risks. Yet, the WEF 2010 report called leaders to give greater attention to cybersecurity fore-seeing that "the increasing complexity and rapid development of dynamic systems and networks, the sophistication of changing threats and the presence of intrinsic vulnerabilities present demanding challenges to the information society".

Notwithstanding the efforts to secure the cyberspace, numerous cyber incidents loomed large in the course of the last decade. Some of the major security breaches include the PlayStation Network outage in 2011 [50], in which the personal data of 77M accounts were compromised and the services of PlayStation 3 and PlayStation Portable were temporarily down; the Yahoo! data breach [106] in 2012, which leaked the credential of almost half million user accounts; the Target [62] and Home Depot [164] security breaches in 2013 and 2014 —where around 40M and 56M credit card data were respectively stolen —that were widely reported in the press and had heavy consequences in their business; the Sony Pictures hack, in which the attackers released confidential data from the studio containing information about employees and their families, emails between employees, information about executive salaries at the company, copies of then-unreleased Sony films, plans for future Sony films, scripts for certain films, and more; the theft of $81 million from the Bangladesh Central Bank in 2016 by the manipulation of the SWIFT global payments network [324].

Another facet of cyber security which is also on the rise is cyberwarfare. Sophisticated cyber attacks are prepared and perpetrated by nation-sponsored actors for different purpose, such as spying and sabotage.

The first time that "a known cyber attack had coincided with a shooting war" was during the in Russo-Georgian War in 2008, when a unremitting campaign of distributed denial-of-service attacks (DDoS) and defacement attacks targeted numerous South Ossetian, Georgian, Russian and Azerbaijani organisation [178]. Amidst the conflicts between Russia and Ukraine, major cyber incidents were also recorded, as the cyber attack against the Ukrainian power grid on 23 December, 2015, which resulted in power outages for roughly 230K consumers [88]; or the recent attacks against Ukranian government sites in the prelude of the 2022 Russian invasion of Ukraine [219].

The first publicly known cyberweapon to target industrial control systems (a.k.a. SCADA systems) was Stuxnet. It was uncovered in 2010, targeting the Iran's nuclear programme,
including the uranium enrichment centrifuges at the Natanz facility [87]. It was a highly
sophisticated piece of software, reported to be developed under an American-Israeli coop-
eration [249]. Stuxnet was a real eye-opener in terms of the potential peril that cyberthreats
can pose to the real world.

Equally highly sophisticated cyberweapons have already fallen into the wrong hands, as consequence of operational mistakes made by national agencies. WannaCry, which broke out in May 2017, used cyberweapons developed by the US National Security Agency (NSA) that were stolen by a hacker crew called Shadow Brokers [35]; it led to a cyberattack with unprecedented scale, which impacted over 10K organizations and 200K individuals in over 150 countries [168]. Other cyberattacks like NoPetya, which caused disruption around the world and infected companies in 64 countries, were also made possible by the leak of state-sponsored cyberweapons [297].

The safeguard of political elections is another consequential domain that has been tar-
geted by cyberthreats. An incipient episode was the DDoS attacks ahead of the 2010 Myan-
mar general election against Burma's main Internet provider, the Ministry of Post and Telecom-
munication. These attacks succeeded in flooding the network links, which teared down the
Internet of the country and restricted the flow of information over the election period [36].

During the 2008 US presidential elections, the campaigns of Barack Obama and John Mc-
Cain were hacked by allegedly Chinese units. On May 29, 2009, the US President Obama re-
ferred to the attacks at an event to announce the plans for securing US digital future: “Hack-
ers gained access to emails and a range of campaign files, from policy position papers to
travel plans”. Officials and former campaign officials acknowledged that the security breach
was far more serious than has been publicly known, involving the potential compromise of
a large number of internal files [130].

The 2016 US presidential elections were also target of cyberattacks by foreign actors. Ac-
cording to Intelligence Community Assessment (ICA) [127], Russians were directly ordered
by the Russian President Vladimir Putin to perpetrate the attack. However, according to
CIA this time the goal was to actively intervene in the election, rather than just undermine
confidence in the US electoral system [82]. Thousands of hacked emails from the Demo-
cratic National Committee (DNC) and others, including Hillary Clinton's campaign chair-
man, were leaked through WikiLeaks. According to ICA, Russians also collected informa-
tion from Republic-affiliated targets, but they did not conduct an equivalent disclosure cam-
paign.

The 2017 French presidential elections were also target of a similar cyberattack. Two days
before the scheduled vote, just hours before the election media blackout <fnref n="4" />, more than 20K e-mails related to the campaign of Emmanuel Macron were disclosed on WikiLeaks. This e-mail leak spread swiftly under the hashtag #MacronLeaks on Twitter and Facebook.

As illustrated by the aforementioned episodes, cyberthreats have been expanding, while becoming more targeted and sophisticated. In the view of this evolution, cyberattacks (and alike, e.g. "data fraud or theft") were listed in the *Top 5 Risks by Likelihood* seven times in five WEF's Global Reports from 2012 to 2019 [300–304] —both cyberattacks and data fraud or theft were in the top 5 risks in 2018 and 2019 [306, 307]. In the last two editions of report, the methodology has evolved to include the *Global Risks Horizons*, which considers the risks according to different time frames: in both cases *Cybersecurity Failure* is the top technological short-risk (0 – 2 years), being 4th in 2021 and 7th in 2022 when all risks are considered.

Cybersecurity is the leading technological issue at the center of concerns for a safer world, which has even become a new domain of war. In May 2011, the US *International Strategy for Cyberspace* [122] was released, being announced as the first time that the US has laid out an approach that unifies their engagement with international partners on the **full range of cyber issues**. As deterrence measure, it was declared in this document that “when warranted, the United States will respond to hostile acts in cyberspace as we would to any other threat to our country”. In July 2011, the US Department of Defense (DoD) declared the cyberspace as a new operational domain in addition to land, sea, air and space [70]. In the same vein, in 2014 NATO endorsed an *Enhanced Cyber Defence Policy*, which established that cybersecurity became part of the Alliance’s core task of collective defense [201]; in 2016, NATO recognized cyberspace as a new operational domain [202].

Within this context, this thesis addresses the problem of *malware classification*, which is an important component of a complete strategy for the security of digital systems.

# Problem Statement

In this thesis we tackle the issue of cybersecurity via Data-Driven Malware Classification Assisted by Machine Learning Methods.

Malware is a prevalent cyberthreat that put the digital security in jeopardy worldwide. In 2019 the number of known malware exceeded the mark of one billion instances, by May 2022 this number already surpasses 1.35B instances, and over 450K new malware instances are

<footnote n="4">4. Period of time when candidates and the media are prevented from commenting on campaign activities.</footnote>
discovered every day [280]. Moreover, the complexity of malware also evolves over time with
new obfuscation techniques and new attack methods. This combination of factors poses
new challenges for the protection of computer systems against malware.

Historically, malware analysis has heavily resorted to human action to manually create signatures that have been used to detect and classify malware. This tradition comes from the dawn of the anti-malware industry at the end of the 1980's, when the computational power available to fight malware was much more limited than today, but the number of samples to process was just as small —in 2008, Dr. Jan Hruska (co-founder of Sophos) refers to “tens of viruses per month” in the 1980's [123].

Initially, the objective of malware classification was closely connected to malware identi-
fication, which was used in the lineage of malware families. However, with the emergence of
techniques such as polymorphism, which produces many different-looking versions of the
same software components, the number of new potential malware instances to analyze ev-
ery day skyrocketed —in 2015, Microsoft refers to “tens of millions of daily data points to be
analyzed as potential malware” [187]. For this reason, malware classification gained a key
role in the workflow of anti-malware systems, being principally used to break down large
amounts of data into subgroups of manageable sizes, thus optimizing the use of human ex-
pertise in the overall analysis.

There has been a remarkable evolution in the workflows of signature creation over the last
decades: Anti-malware companies and the practitioner community have developed many
(proprietary and public domain) languages to support the creation of signatures; analysis
frameworks have integrated pipelines to bolster cooperation between human analysts and
machines, using the prior constituted knowledge database in the analysis of new coming
malware and to implement large scale QA procedures to validate newly created signatures;
security products (with virtually no exception) have integrated the support to share and fetch
new signatures; the community has developed (open and closed) platforms to support large
scale sharing and reuse of signatures.

Yet, the procedure to create and test new signatures is inherently very costly and time consuming; signatures are barely able to keep the pace with the current state of affairs and they are certainly unfit to cope with future cyber threat scenarii. Due to shortcomings of the signature-based strategy, over the last decade there has been a great effort to find viable alternatives.

The solution to this plight relies not only on widely automating malware analysis, but
also on making the end-to-end classification analysis as autonomous as possible. Toward
this goal, *machine learning*-based approaches stand out as a promising alternative, as they have been increasingly used to analyze large and heterogeneous corpora of data, like those in the malware analysis scenario. Therefore, in our work we consider a malware classification framework that relies on machine learning to optimize the handling of large malware corpora.

## Our Approach

Our strategy targets the identification of inherent characteristics that allow to measure the resemblance of different software instances. This allows to optimize the analysis of large data corpora, since the analysis of an individual instance —which may well involve costly human expertise —can be propagated to similar instances with basis on the inherent characteristics identified by the classification framework, thereby producing an application effect.

Withal, this plan entails intricate issues. *How to get a description that suffices to represent inherent characteristics of malware? How to measure the resemblance of malware instances based on their inherent characteristics? How to evaluate the success of a malware classification framework?* These are some of the challenging questions that this thesis addresses.

Orthogonally to these issues, we have to overcome manifold practical hurdles. A satisfactory framework for malware classification should provide high quality analysis, being able to produce results with high accuracy, resist to the profusion of anti-analysis techniques frequently employed by malware and be scalable, so as to concretely withstand the surfeit of malware in current and future cyber threat landscapes.

To address the multiaxial issues involved in the creation of a successful malware classification framework, we take an accruing approach. First, we focus on the conceptual basis of our work in order to define our axiology, which stipulates the guiding principle of the methodologies developed in this thesis. Then we concentrate on each stage of our malware classification workflow, which includes the enhancement of tooling for malware analysis, the improvement of software characteristics representations and the design of alternative analysis methodologies that can provide the required accuracy, robustness and scalability.
## Research Objectives

This thesis addresses the problem of malware classification taking an approach in which human intervention is spared as much as possible. We steer clear of subjectivity inherent to human analysis by designing malware classification solely based on data obtained directly from malware analysis, thus taking a *data-driven approach*.

Our objective is to enhance the automation of malware analysis and to straighten the use of machine learning methods with aim to autonomously spot and reveal hidden commonalities within large data corpora. Improving the automation of malware analysis involves the development of new tools and methods for extracting inherent characteristics of software instances; in its turn, improving the autonomy of *malware classification* requires to restrain it to data obtained through direct analysis only, without the handicap of trusting indirect information exterior to the boundaries of the system.

This multifaceted desideratum entails not only technical challenges but also acute epistemological concerns. Although machine learning has been proving to be a top-notch alternative for such complex scenarios, leveraging it to pull off malware analysis is far from being straightforward. We endeavor to improve the application of machine learning in the field of malware analysis —though we do not intend to improve the state-of-the-art of the machine learning field itself. Therefore, we dedicate special attention to methodological aspects that impact the setup of our experiments as well as the evaluation of the results.

## Research Questions

In this thesis we take an accruing approach. To reflect this plan, we organize our research based on top-level research questions that outline each stage of our workflow for *malware classification*, which comprehends *data extraction → data transformation → data analysis*.

Our top-level research questions are:

**TOP-RQ1** *How to improve the arsenal of techniques currently used in malware analysis, in particular for the analysis of binary files?*

**TOP-RQ2** *How to compute the similarity of unknown programs with high accuracy while being friendly to search and clustering algorithms for malware analysis?*

**TOP-RQ3** *How to design a data-driven clustering framework that is accurate, robust and scalable?*
## Contributions

As main contributions of this thesis we:

- review epistemological matters that severely impact the use of machine learning for malware analysis; thanks to this review we propose a realist ontology of malware and we settle our axiology [chapter 1 (page 25)].

- study how to optimize the setup of symbolic execution in the context of malware analysis [chapter 3 (page 111)];

- study a graph-based representation to characterize the behavior of computer programs and propose a related similarity function that is accurate and robust [chapter 4 (page 153)];

- propose an evaluation paradigm for the evaluation of frameworks for malware classification [chapter 4 (page 153)];

- propose a data-driven clustering approach that can work with multiple heterogeneous features, which is thus prone to high accuracy and robustness, while being inherently scalable [chapter 5 (page 189)].

As positive externalities, the development of this thesis also promoted contributions on the applied aspects necessary to set the study up. This includes:

- the development of an analysis tool for call tracing based on symbolic execution [section 3.5.1 (page 136)];

- the optimization of a graph mining algorithm implementation [section 3.5.1 (page 137)];

- the development of a docker-based container orchestration to scale up malware analysis [section 3.5.1 (page 138)];

- the integration into our analysis framework of publicly available external tools [section 5.5.1 (page 212)].

In all these cases, our experiments produced benchmarks that contribute to improve the state-of-the-art of malware research.

## Thesis Outline

This thesis is structured in two segments. Initially, in chapters 1 (page 25) and 2 (page 57) we unravel the theoretical foundation that support our research. Then, in chapters 3 (page 111), 4
(page 153) and 5 (page 189), we tackle the nub of the thesis, which contains our main contri-
butions.

More specifically, this thesis is organized as follows:

- chapter 1 (page 25) draws a general overview on epistemological issues related to malware research. Our intent is to clearly establish our axiology, which guides the remainder of our study;

- chapter 2 (page 57) contains background material on machine learning and malware analysis;

- chapter 3 (page 111) presents our study on the use and optimization of symbolic execution for call tracing in malware analysis;

- chapter 4 (page 153) targets the behavioral representation of computer programs in the form of graphs and studies our proposition for an associated similarity function;

- chapter 5 (page 189) tackles the issues of multi-feature analysis and scalability in malware clustering;

- Finally, the last chapter (page 259) concludes this thesis and presents possible future perspectives.
# EPISTEMOLOGICAL VIEW ON MALWARE RESEARCH

## 1.1 Introduction

Malware research is the field that studies subjects related to malware analysis, which is a discipline that analyzes computer programs and other artifacts in order to assess the degree of danger that they carry to users and systems.

This rather generic definition derives from the broad spectrum of computer threats that can be subject to malware analysis. Even the term malware — portmanteau for *malicious software* — is an “umbrella term” defined to accommodate all different definitions of malicious programs (e.g. computer virus, worm, trojan horse, etc).

The lack of an agreed taxonomy establishing a common understanding of terms and definitions (i.e. a *domain ontology*) is an old problem in the field. To illustrate it, we can cite the Virus Bulletin editorial of December 1989 [79] where the authors raised the lack of consensus to define a “*terminology for defining different types of computer virus*” nor the existence of any “*standard nomenclature to identify specific viruses*”. This still remains an open problem in the community to date.

This ontological gap goes against the current trend in malware research, which focuses on machine learning to aid analysis. How can we teach machines about things that we did not figure out yet? How can we evaluate results if we do not know the answers?

In part, this challenge derives from idiosyncrasy of the malware analysis field, which is highly dynamic and strongly influenced by the industry, thus less keen to *epistemological* thinking and more driven by problem solving (i.e. *Episteme* versus *Technē*).

In this chapter, our motivation is to closely review how knowledge is created in the field and how it evolves afterwards (i.e. the structures of knowledge). We endeavor to lay out an epistemological view on malware research, which will enable us to determine our research paradigm more precisely. This research paradigm will then ground our methodolo-
gies throughout our study.

We organize this section in three parts: an ontology (section 1.2, page 26), an epistemology (section 1.3, page 44) and an anxiology (section 1.4, page 54). This organization intends to shed light on underlying assumptions taken by research works, but that are quite often implicitly rather than explicitly defined. Each of these three parts views the research field from a different angle, where we are interested in answering the following questions:

— “What does exist (in the malware research field) ?” [Ontology]

— “What can we know? How do we know what we claim to know?” [Epistemology]

— “What do we value to guide our research?” [Axiology]

## 1.2 An Ontology of Malware

> *The variables of quantification, 'something', 'nothing', 'everything', range over our whole ontology, whatever it may be; and we are convicted of a particular ontological presupposition if, and only if, the alleged presuppositum has to be reckoned among the entities over which our variables range in order to render one of our affirmations true.*

Willard Van Orman Quine (1980).
“From a Logical Point of View”, p.13,
Harvard University Press.

Ontology contemplates the description of existence. In Philosophy, the term was often synonym of *metaphysics*, referring to subjects that are “beyond Physics”<fnref n="1" />. Philosophically, the term *ontology* expresses the reflection about what *might exist*. In the scientific context —often referred as “*domain ontology*”—it describes the fundamental analysis that seeks to identify key concepts in the study of a subject. In the domain of computer security, ontologies are for the most part “taxonomies, definitions and collections of the varieties of flaws, prophylactics and preventatives” [253].

<footnote n="1">1. *Physics* was better understood as a synonym for what we know as *Science* today.</footnote>
A good starting point to initiate an ontological analysis of the malware research field is the simple concept of *malware*. Interestingly, the term malware postdates the existence of the field. Many sources attribute the creation of this term “malware” to Yisrael Radai in 1990 [81], however it is hard to find evidences online to confirm that nowadays. Nonetheless, the very first time the term appeared in a Virus Bulletin edition was in march 1992 [78].

We adopt two approaches to establish an ontology of the malware research field: historical and analytical. The former identifies key concepts that emerged organically in the field in the course of its history, whereas the latter builds on existing ontologies of computation systems to extend them in the context of malware research.

**1.2.1 Historical Approach**

This section provides an overview of history-oriented ontologies of malware proposed in the literature. As a foundation to appreciate these ontological proposals, we begin with a brief historical introduction that intend to highlight the challenges entailed by this approach. Therefore, beyond the genuine intention of recollecting a (brief) timeline of major events in malware history, we are specially interested in understanding how new concepts and taxonomies emerged and how they evolved over time.

**A Brief History of Malware**

An inchoate idea of a malicious program has been around since at least 1949, when John Von Neumann presented the conception of *self-reproducing automaton* in a series of lectures [295]. This notion of self-reproducibility is invariably found in the early ages of malware history, because of the inherent need of computer threats to spread<fnref n="2" />.

The first documented program to exploit the ability of self-replication was dubbed the *Creeper*, in 1971. The *Creeper* was written by Bob Thomas at BBN as an experiment, where the program was able to self-replicate onto other computers connected to the local network and to trigger the execution of these copies. As a result of its execution, the “infected” system printed the message "I’M THE CREEPER : CATCH ME IF YOU CAN". Despite not attempting to cause any harm to the system, the *Creeper* is broadly considered as the first **computer worm**. Interestingly though, the term *worm* actually postdates the *Creeper*; it originally comes from a John Brunner’s 1975 science-fiction novel called *The Shockwave Rider* and was adopted by John Shoch and Jon Hupp at Xerox PARC in 1979 [260].

<footnote n="2">2. Since the advent of *Advanced Persistence Threats* (APT)s [101] this requirement is no longer imperative.</footnote>
In 1984, Fred Cohen defined the concept of a **computer virus** as a program capable of attaching itself to other programs (i.e. "infect") causing them to become viruses as well [54]. In this paper, Cohen mounted experiments to validate in practice the implementation of a real computer virus, to observe it and to propose preventive measures and countermeasures against viral infection. Cohen also provided several interesting results such as the *undecid-ability proof of a universal virus detector*.

In addition, Cohen's paper mentioned the Xerox worm program and the potential danger of using computer viruses in conjunction with a "*Trojan horse*" that could clearly cause widespread denial of services and/or unauthorized manipulation of data. It is interesting to notice that the term *Trojan Horse*, which is still highly used —in its short form, i.e. *trojan* —was already present at the time of Cohen's paper.

[Computer] Trojan horses were (semi-)formally defined by Ken Thompson in his 1983 Turing Award acceptance lecture "Reflections on Trusting Trust" [281]. Thompson described a compiler that deliberately introduces bugs during the compilation process, denoting the addition of unexpected and concealed code in programs <fnref n="3" />. Thompson acknowledged the Air Force Data Service Center (AFDSC) report released in 1973 for describing —hence conceiv-ing—the possibility of a *trojan horse* on early implementation of Multics. It is also possible to find a prior usage of the term *trojan horse* in a 1971 Bell Labs' manual [156].

At the time, there was already a heed about what is currently known as **backdoor** (then referred as *"trap door"*). In 1967, H.E. Petersen and R. Turn discussed about privacy issues concerning the (back then) recent advances in computer systems allowing multi-user support [216]. They defined *trap doors* as entry points planted in the system and conceived the possibility of an active infiltrator that knows about them (e.g. "unscrupulous programmers or maintenance engineers") or who probes for it. Despite the long-lasting concerns toward this threat, backdoor installers became widely adopted by malware writers only starting from late 1990's, after the disclosure of *Back Orifice* at Def Con 6 [64] in 1998.

With the advent of personal computers as commercial success in the 1980's, malware started to expand fast. The first malware that appeared *in the wild* (i.e. not as part of a lab experiment) was the *Elk Cloner*, written around 1982. It was an instance of what is currently known as **boot sector virus** (or even a primitive version of a **bootkit**), because it modified the boot sector of floppy disks to install a copy of its payload. Computer booted from an infected floppy disk would load the virus in the memory, which would await until an uninfected disk be inserted into the computer in order to copy itself in the disk, thus spreading the infection

<footnote n="3">3. This strategy is comparable to the current *software supply chain attack* (e.g. 2019 *Barium's attack* [323]).</footnote>
from disk to disk. Despite targeting the boot sector of floppy disks, the *Elk Cloner* did not
damage any system file; instead it displayed a little poem as a prank.

The first computer virus to target IBM PCs became known by the name of *Brain*, because
it deliberately included the following signature message in the program:

Welcome to the Dungeon ©1986 Basit & Amjads (pvt). BRAIN COMPUTER
SERVICES 730 NIZAM BLOCK ALLAMA IQBAL TOWN LAHORE-PAKISTAN PHONE:
430791,443248,280530.

Similarly to the *Elk Cloner*, the *Brain* virus also affected the boot sector of floppy disks to insert a self-replication copy on them. *Brain* is yet another example of non-destructive computer virus; the authors of *Brain*, the brothers Amjad Farooq Alvi and Basit Farooq Alvi, told in an interview [311] that they acted on an experimental motivation to find out how far and quick this virus could spread.

The first Internet malware became known by the name of “Morris worm”, since it was
written by graduate student Robert Morris at the Cornell University. It spread out in Novem-
ber 1988, exploiting several vulnerabilities: cracking of password files, abuse of the debug
option in the Unix sendmail program, buffer overflow attack on Unix finger daemon pro-
gram [44]. Similarly to the Creeper, the Morris worm was not deliberately programmed for
damage; again, the purpose was an intellectual and computing exercise, although it did not
have any kind of consent of the potential affected parties.

The emerging trend of malware that targeted an ever larger basis of computers in the end of the 1980's, promoted the advent of anti-malware programs. *Flushot Plus* by Ross Greenberg was the first anti-malware software to be released in 1987. In 1989, John McAfee released the VirusScan™ program, which could detect and repair several viruses at one shot [247]. Other companies like Sophos, Avira and F-Secure were also founded before the end of the decade.

The concept of **rootkit** appeared in the beginning of the 1990's. These are programs
developed to conceal the presence of their payload, avoiding analysis and detection while
maintaining privileged access to a target system [143]. The first rootkit (is believed to have)
appeared in 1990, written by Lane Davis and Riley Dake for the Sun operating system [34]
—hence the name combining “root” + “kit”. The first public rootkit for Windows appeared
only in 1999, written by Greg Hoglund and called NTRootkit (as it targeted the WindowsNT
operating system).

During the 1990's the awareness about malware grew considerably. For instance, *Michelangelo* became the first computer virus to attain worldwide attention in 1992. This virus, which
targeted DOS systems, was designed to infect and remain dormant until March 6 (the birthday of the Michelangelo painter, hence the name), date on which the virus overwrites critical system data, including the boot and file allocation table (FAT) records, rendering the disk unusable.

As of 1990's the profile of malware shifted, as they started being more frequently oriented
towards profitable activities (e.g. spamming). It is in the 1990's that spyware —portman-
teau for "spying software" —emerged. The origin of the term is unclear, however the first
record of the term spyware that can be found nowadays dates from 1995 in a Usenet post by
Roland Vossen, who was mocking the marketing strategy of Microsoft [296]. Spyware began
to be used in the context of computer software in 1999 when Zone Labs used it in a press
release for its Zone Alarm firewall product [60]. In 2000, Gibson Research launched the first
anti-spyware product called OptOut, which described spyware as "any software that employs
a user's Internet connection in the background (the so-called 'backchannel') without their
knowledge or explicit permission".

As of the years 2000's, spyware gained great notoriety as the threat spread; in 2002 the Federal Trade Commission (FTC) logged up to 150K identity theft complaints and in 2004 this number grew to 250K [97]. In 2005 the FTC provided the following comprehensive definition for spyware: "software that aids in gathering information about a person or organization without their knowledge and that may send such information to another entity without the consumer's consent, or that asserts control over a computer without the consumer's knowledge".

Around the same time, the other prevalent threat to appear was **Adware**, which was defined as “small pieces of code installed on the client machine whose primary purpose is to achieve highly targeted marketing by a number of methods: Displaying usually an excessive number of pop-up advertisements; Installing toolbars full of adverts; Modifying Browser settings such as the default home page favourites; Hijacking website searching and use.” [259].

Due to the numerous similarities of techniques used by adware and spyware there has
been a huge lack of consensus about what distinguishes one malware type from the other,
which was subject of intense discussions in the first decade of 2000. Another debate that un-
folded around adware was whether it should be classified as malware or simply as potentially
unwanted program (PUP).

**Ransomware** is yet another example of computer threat, which demands a ransom to undo the damage caused after hijacking personal data through the use of encryption or blocking the normal use of system. The former, which demands a ransom to decrypt the hi-
jacked data, is known as *crypto-ransomware*, and the latter, which demands a ransom to to
release the system, is known as *locker-ransomware*. The *crypto-ransomware* was presented
by A. Young and M. Yung at the 1996 IEEE Security and Privacy conference [321] decades
before it becomes a major widespread threat in the wild.

Despite of being currently a major threat, the first documented ransomware dates back
1989. It became known as *AIDS* (a.k.a *PC Cyborg*) because it was present in a floppy disk
with the inscription "AIDS Information Introductory Diskette". When the malware
was executed, it would hide all folders in the system and encrypt the files on the C: drive.
Then, it would display a ransom message demanding $189 to be directed to the *PC Cyborg
Corporation*, otherwise the compromised systems would not be restored.

*Crypto-ransomware* “reemerged” with *GPcoder* in 2005 after a lull of 15 years. The attack included the encryption of many files of predetermined extensions; in each directory including an encrypted file, *GPcoder* would leave a ransom note with an e-mail address to communicate with the malware authors and eventually get the corresponding decoder [102]. Since then, *crypto-ransomware* became a major threat specially in the second decade of 2000’s after the advent of *cryptocurrencies*, which can anonymize wallets to receive payments (e.g. *bitcoin*).

So far we named but a few concepts (often associated with malware types) that have
emerged throughout history. Yet, there are major inconsistencies with respect to the char-
acteristics taken into account depending on the definition. For example, *trojans* and *back-
doors* are very different from *worms* and *viruses*: *worms* and *viruses* are essentially defined by
their propagation techniques; *trojans* bear upon some concealed functionality in a program
(notwithstanding which functionality it might be); *backdoors* are specifically related to the
concealment of entry points in the system and the possibility of exploiting them.

Furthermore, by the definition of *trojan* sketched above, we note that the frontier dis-
tinguishing malware from ordinary software quickly becomes flimsy, due to the potential
subjectivity involved in the definition of what an “expected functionality” may be. The same
subjectivity judgement blurs the distinction between *spyware* and *adware*, or even whether
*adware* are malware or *PUP*.

On top of that, in the course of the last decade we have seen a great evolution in the
complexity of malware. For instance, *Stuxnet* (2010) was a modular malware that had *worm*
capabilities, while targeting SCADA systems acting as a *rootkit*; *Mirai* (2016) was a *botnet*
that targeted IoT devices to install *backdoors* and remotely control these devices in order to
perpetrate *DDoS attacks* against other systems on the Internet; *WannaCry* (2017) displayed
*worm* capabilities in the propagation phase, exploiting vulnerable systems on the network, and executed a *ransomware* payload on the vulnerable systems.

As we have seen through the aforementioned examples, concepts and taxonomy widely adopted by practitioners in the malware analysis field appear and evolve organically, following the sequence of events that eventuate in the field —or even from popular culture, as we have seen terms like *worm* being borrowed from sci-fi novels. This constant adaptation is a major challenge for the establishment of a historical-oriented ontology for malware research. For instance, in 2006 Giri *et al* wrote: “Self-replicating malware can use file infection or mass mailing to spread. Ransomware falls in the category of Trojans that are non-self-replicating malware and that use different methods for transmitting themselves.” [102]; however, after *WannaCry*, this distinction is no longer true.

## History-Oriented Ontologies of Malware

We consider as history-oriented an ontology whose constituent concepts (or entities) are by-product of the organic evolution of malware analysis throughout its history. Several ontologies concerning malware can be found in the literature, and almost invariably they can be categorized as history-oriented.

Swimmer was one of the first to attempt formally defining an ontology of malware [276]. Swimmer described a malware class hierarchy that reflected the types of malware as existing at the time. Swimmer also provided descriptions to identify characteristics that one expects to find in malware, mapping them to corresponding types of malware. Finally, Swimmer expressed his ontology using the Web Ontology Language (OWL) [181] so as to make it public available for universal usage, specially for alerts, malware descriptions and intrusion detection response systems. Figure 1.1 shows the malware class hierarchy class as defined by Swimmer [276].

Mundie and McIntire sought to build an ontology for malware (analysis) to tackle the lack of common vocabulary and shared concepts. They acknowledged that “nowhere in cybersecurity community is the lack of a common vocabulary, and the problems it causes, more apparent than in malware analysis” [199]. To address this problem, they established a methodology for mining malware-related terms in a database containing 10 years of emails, so as to build a controlled vocabulary of ~270 malware analysis terms—which clearly follows a history-oriented approach. Based on the mined terms, Mundie and McIntire provided a taxonomy and constructed two ontologies in OWL: a static ontology and an intentional ontology, respectively defined as “an ontology that describes static aspects of the world, i.e.,
<figure><img src="image_6.png" /><figcaption>Figure 1.1 – Swimmer’s ontology of malware classes</figcaption></figure>

what things exist, their attributes and relationships" and "an ontology that encompasses the
world of things agents believe in, want, prove, disprove, or argue about".

Gregio *et al* pointed the obsolescence of prior ontologies: “Current efforts are based on an obsolete hierarchy of malware classes that defines a malware family by one single prevalent behavior (e.g., viruses infect other files, worms spread and exploit remote systems autonomously, Trojan horses disguise themselves as benign programs, and so on)” [110]. They proposed to move away from the identification of inherent characteristic as a sort of definition of malware and focus attention on behaviors, in order to define an ontology that addresses behavioral aspects and activities performed by malicious programs. However, the authors also sidestepped the more deep ontological issue of clearly defining the nature of malware by only dealing with “suspicious activities” as subject of their ontology.

Xia *et al* addressed the gap between malware ontology and behaviors in a practical case [313]. They took a subset of Swimmer’ malware ontology [276] and defined a set of behaviors to find correspondences between malware classes and behaviors using several mining algorithm. Nevertheless, the subset of malware classes used was still very reduced (i.e. only five types) and therefore meager to provide an extensive description that could accomplish the practical use. Furthermore, the detection method as designed suffers from the limitation of malware classes as ontological entities, which are *far from adequate to address the issue of modern malware*<fnref n="4" />, as asserted by Gregio *et al* [110], Orbst *et al* [207] and others.

MALOnt [230] takes an approach that is similar to the one by Mundie and McIntire [199]. However, instead of mining email, Rastogi *et al* analyze a corpus of threat reports to extract

<footnote n="4">4. As previously discussed, malware classes may become inaccurate or obsolete due to the evolution of malware (e.g. the definition of *ransomware* by Giri *et al* [102])</footnote>
the data elements that underpin their ontology, which comprises entities and relationships
in the form of knowledge graphs. Once again, the approach is guided by the organic devel-
opment of the field.

In addition to self-proclaimed ontologies, several standards, taxonomies, and languages involving malware have been proposed for practical reasons (e.g. data exchange). It is the case of OpenIOC [255], MAEC [176] and others. They can provide useful information and thoughts about malware description and outline some ontology of malware, despite not being their main intent.

1.2.2 Analytical Approach

Alternatively to the historical-based approach, which deals with concepts that came about organically, it is possible to conceive an ontology of malware entirely through reasoning. By construction, this method is likely to devise a simpler and more coherent ontology.

Ontologies of Software

Before delving into the discussion about malware ontology, let us first review the exis-
tent ontologies of software, since malware, by definition, is a specific kind of software (i.e. a
"malicious kind").

In turn, the ontologies of software are subsumed in the ontology of computational sys-
tems. Therefore, we start by presenting the two main approaches pursued by the philosophy
of computer science [7]:

— a first view that considers a **conceptual ontology**, which breaks down computation
systems on the basis of a hierarchy of levels of abstraction;

— a second view that considers a **realistic ontology**, which analyze computational sys-
tems as a composition of two distinct ontological entities (i.e. software and hardware)

**Method of Abstraction** Abstraction is in the core of sciences such as mathematics or com-
puter science. Sciences benefit largely from abstractions when analyzing complex systems
by abstracting away finer details of these systems into some “higher level” description that
contains only the most relevant attributes. Despite widely applied in sciences, historically
this approach has found little application in philosophy: the formalization of levels of ab-
straction (i.e. “the method of abstraction”) as a conceptual and phenomenological frame-
work for analysis was only recently proposed by Floridi and Sanders [91].
This approach formalizes the representation of an object of study (referred as *system*) as a set of *observables*, which are in turn interpreted from *typed variables* together with statements of what features of the system they represent. The set of observables used to describe a system is called *Level of Abstraction (LoA)*.

For instance (as presented in [91]), when analyzing the taste of wines, one can describe them in terms of attributes that commonly appear on ‘tasting sheets’: ‘nose’ (representing bouquet), ‘legs’ or ‘tears’ (viscosity), ‘robe’ (peripheral colour), ‘colour’, ‘clarity’, ‘sweetness’, ‘acidity’, ‘fruit’, ‘tannicity’, ‘length’ and so on; each attribute corresponds to an *observable* that is described by some determined typed value, and the set of all values (i.e. observables) forms a “tasting LoA”. If the purpose is the analysis of the market of wine, instead of adopting the “tasting LoA”, one would be rather interest in a “purchasing LoA” consisting of observables like ‘maker’, ‘region’, ‘vintage’, ‘supplier’, ‘quantity’, ‘price’, and so on.

The method of abstraction is in fact an epistemological levelism method; however, whenever applied it requires an “ontological commitment”, meaning that the theory commits itself ontologically by opting for a specific LoA [91]. Still, one must not assume that LoA has the cogency of a universal ontological theory [254]<fnref n="5" />, in the sense pursued by some branches of natural sciences, i.e. a mereological theory with a lowest level on which subsequent levels piles up (e.g. as the theory of “reductive levels” defended in [209]). Yet, for some anthropogenic systems (e.g. computer systems) the method of abstraction can perfectly underpin ontological theories.

Primiero was the first to devise an ontology of computer systems in terms of LoA [222]. The main interest is how Primiero ponders upon the ontological and epistemological relationships inferred (or implied) at the interfacing of each one of the following layers: (i) Intention, (ii) Specification, (iii) Algorithm, (iv) High-level programming language instructions, (v) Assembly/machine code operations, and (vi) Execution.

The overall LoAs of computer systems as proposed by Primiero [222] are depicted in figure 1.2. Primiero defends that computer systems are built from an *intention* that aims at a *problem*, which is *reflected by* a task *fulfilled* by an algorithm, and so forth. This interplay goes up to the physical level, keeping corresponding stances of epistemic interpretation at each stage (e.g. “electrical charge” → “action”). According to this view, no LoA taken in isolation is able to define what a computational system is (nor to determine how to distinguish software from hardware); the computational systems are instead defined by the whole ab-

<footnote n="5">5. In the sense of “metaphysics”; not to confuse with the broader meaning of “ontology” that has been in use here (e.g. domain ontology).</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 1.2 – Primiero’s ontology of computer systems [222].</figcaption></figure>

straction hierarchy.

Describing in detail Primiero’s ontology of computer systems goes beyond our scope and intentions. However, as these LoAs follow the lines of textbook abstraction layers of computer organization, it is possible to point a shortcoming of this ontology: the computation model that guides this ontology is oversimplified as if all computer programs ran on bare metal machines —it does not consider other types of execution such as interpreted code, intermediate representations, virtual machines, hardware emulation, etc.

Yet, it is important to notice that the *Intention* is a constituent part of the ontology of computer system. As a matter of fact, the purpose-oriented aspect of computer systems (expressed here by the stance of *Intention*) —further discussed below—is constantly subsumed in the ontology of computer systems.

**Hardware and Software** This approach regards algorithms, source codes, and programs as belonging to the category of abstract entities (i.e. *software*), while microprocessors, hard drives, and computing machines fall in the category of physical entities (i.e. *hardware*). This view is, however, not unanimous and even the mere differentiation between the concepts of hardware and software is still in debate.

Moor seems to be the first to propose an ontology of computing systems [196]. Moor starts by giving some examples of programs that contradict commonsense about “hardware” as defined in a dictionary entry (i.e. “the physical units making up a computer system (Chandor [1970], p. 179)”). According to Moor, programming of early digital systems was
commonly done by plugging in wires and toggling switches, thus being physical/tangible<fnref n="6" />. For Moor, a more accurate definition for computer programs would be “a set of instructions which a computer can follow (or at least there is an acknowledged effective procedure for putting them into a form which the computer can follow) to perform an activity.”, thus following that computer programs can be understood on the physical level as well as the symbolic level. Therefore, to Moor, the dichotomy of software/hardware was only pragmatic, but not ontological.

Tanenbaum agrees in essence with Moor's view. He sees the structure of computer organizations in terms of layers <fnref n="7" />. By noting that “programs written in a computer's true machine language (level 1) can be directly executed by the computer's electronic circuits (level 0), without any intervening interpreters or translators” and that “any instruction executed by the hardware can also be simulated in software”, Tanenbaum concludes that “hardware and software are logically equivalent” [279].

Suber's essay [274] goes further, stating that hardware is part of the software ontology. Suber argues that software (or program, interchangeably) can be defined as “*pattern* that is readable and executable by a machine”, where pattern takes a “broad sense to signify any definite structure, not in the narrow sense that requires some recurrence, regularity, or symmetry”. Suber then analyzes the concepts of machine *readability* and *executability*, and argues that any pattern *P* can fulfill both properties, because even if *P* is seen as noise for a machine *M* and language *L*<fnref n="8" />, there exists a machine *M'* and language *L*' for which *P* is meaningful, regardless whether their existence is currently unknown. Then, Suber defines the *freedom of interpretation* as the “the flexibility to read intrinsically unmeaning formal patterns as holding a given meaning” and the *freedom of formalization* as the “the complementary flexibility to create a formalism or code to express a given meaning”. These definitions open up an unlimited freedom of means for conceiving machines and languages, thus following that in principle “everything is software”, given that any concrete object displays patterns. The immediate corollary is that “hardware, in short, is also software”.

Duncan agrees only partially with Tanenbaum's views and finds Moor's and Suber's positions implausible [76]. Duncan acknowledges that hardware and software are logically equivalent, but he diverges from Tanenbaum's claim that “the boundary between hardware and software is arbitrary and constantly changing.”;

<footnote n="6">6. In this sense, it is possible increment the list of examples with other technologies such as punched cards or hardware description languages (HDL) and programmable logic devices (PLD).</footnote>

<footnote n="7">7. In the lines of the hierarchy of levels of abstraction.</footnote>

<footnote n="8">8. Maybe “grammar” would be a more appropriate term.</footnote>
Duncan's critics to Moor's argument consider the proposed ontology too limited, as it
consists of only three main "kinds of thing": the symbolic level of computer programs, the
physical level of computer programs, and the activities related to each level. This is the rea-
son why Moor is not able to find any significant ontological differences between software
and hardware.

As for Suber's ontology of software, Duncan summarizes it with the following syllogistic
argument:

(P1) Software is a pattern that can be read and executed.

(P2) A pattern can be read and executed if it can in principle satisfy the physical and grammatical conditions of readability and the requirement of executability.

(P3) All patterns can satisfy the physical and grammatical conditions of readability and the requirement of executability.

(P4) All concrete objects display patterns.

(C1) All concrete objects can satisfy the physical and grammatical conditions of readability and the requirement of executability.

(C2) Therefore, all concrete objects are software.

(P5) Hardware is a concrete object.

(C3) Therefore, hardware is software.

Duncan then points that there is a flaw in the logical sequence (P3) → (P4) → (C1). According to Duncan, the premise that “all concrete objects display patterns” does not allows one to conclude that “all concrete objects are patterns”. Rather, the conclusion of Suber’s argument should have been that “all concrete objects *display* software patterns”. Duncan also provides the following example redolent of absurdity:

(P1) Software is a pattern that can be read and executed.

(P6) A peanut butter sandwich is a concrete object.

(C4) Therefore, a peanut butter sandwich is software (from C2).

(C5) Therefore, a peanut butter sandwich is a pattern that can be read and executed
(from P1 and C4).

Duncan argues that even if one could hold that (C4) is in fact valid, despite sounding
implausible, this would raise the question about “how to distinguish the various types of
software in the world”. Therefore, to Duncan, Suber’s ontology of software is to little or no
avail in practice.

Towards the formulation of an ontology of software, Duncan takes up on Turner descrip-
tion of computation artifact<fnref n="9" /> (e.g. computer program) as *specifications* [285]. For Turner, “programming and specification are not easily separable activities” inasmuch as programming is not an aimless activity and “any articulation of its goals constitutes a specification” —even if the description of the goals is created *post hoc* and quite informally. Nonetheless, Duncan points the lack of a detailed ontological theory distinguishing software and hardware as a shortcoming of Turner’s work.

Turner’s conceptualization of specification says that “something is a specification when it is given *correctness jurisdiction* over an artifact”. In other words, a specification has to provide a “criterion of *correctness* or *malfunction* for purported artifacts”. Turner notes that such analysis of specification is an idealization, meaning that it should not be taken as an exact reflection of practice; in practice not every software project will evolve from prescribed specifications, however the purpose-oriented nature (or *teleological function*) of a software project delimits a sort of specification —as illustrated by Turner: “For example is there a specification for a search engine? Yes. It has to be a search engine not a language translator. It may be vague, but it is still a specification”.

To formulate an ontology of software, Duncan analyzes the notion of *correctness juris-
diction* through the lens of the Basic Formal Ontology (BFO) [12]<fnref n="10" />. Duncan maps Turner’s
*correctness jurisdiction* to the BFO’s definition of *role*; in particular, it is defined a **normative**
*role*<fnref n="11" />, due to its “authority to govern” (of software over hardware <fnref n="12" />). Duncan argues that
the notion of *correctness jurisdiction* as BFO’s role category is suitable because “an entity can
lose its *correctness jurisdiction* without being physically changed”. For example, a machine
that fails to execute the instructions encoded in a software is defective; however, a software
that is found to contain mistakes (i.e. *bugs*) no longer implies the machine to be defective,
but instead it loses its *correctness jurisdiction* over the expected behavior of the machine.

Duncan thus proposes an ontology of software, capable of distinguishing software pro-
gram from computer hardware, as follows: “software program: a *specification* that consists
of one or more programming language instructions and whose concretization is embodied
by an artifact that is designed so that a physical machine may read the concretized instruc-

<footnote n="9">9. Artifact can be defined as “a product of human workmanship”, in contrast to a “natural object”.</footnote>

<footnote n="10">10. For the sake of contextualization, we provide a brief introduction on BFO in the appendix section 6.1.</footnote>

<footnote n="11">11. There is no specification of role types in the BFO hierarchy; therefore, *normative role* is not a proper BFO type. Here, Duncan uses the word *normative* to emphasize the quality of “correctness jurisdiction” for the BFO concept of *role*.</footnote>

<footnote n="12">12. Duncan argument about “normative role” goes beyond “the authority to govern how a physical device is constructed or behaves” (here referred as *software over hardware*), but delineating all details of this argument goes beyond the scope of this thesis.</footnote>
tions” [76].

We note that this ontology neatly depends on Turner’s conceptualization of *specification* —not only “software program” is defined as a kind of specification *per se*, but also a *programming language* is defined as a *specification* that provides syntactic rules for expressions and semantics to determine computation operations that result from the execution of such expressions.

In a previous work, Duncan proposed an ontology of software, which held a more straight-forward bind with BFO and was also capable of differentiating hardware and software [75]. This version of Duncan’s ontology follows the steps detailed below:

*Is software a continuant or an occurrent entity?*

Observing that software is an entity that maintains its identity through time, Duncan concludes that software is a *continuant entity*.

*Is software an independent continuant or a dependent continuant?*

Duncan defines hardware as an *independent continuant* and software as a *dependent continuant*, inasmuch as software bears on hardware to be realizable<fnref n="13" />.

*Is software a generically dependent continuant or a specific dependent continuant?*

Duncan splits two aspects embodied in software: the encoding facet (at any level, e.g. source code), which is a *generically dependent continuant* as it can be copied and exists in multiple places, and the **teleological function** of the software (referred as *computational function*), which is a *specific dependent continuant*.

*Which kind of specific dependent continuant is a computational function?*

Duncan observes that “any instance of this [*computational*] function is actualized in the running of some particular computational process, and the particular computational process could not exist without the instance of a piece of computing hardware on which the process runs”, concluding that computational function is therefore a realizable entity. In particular, Duncan describes *computational function* under the BFO’s concept of *function*, since it fulfills some essentially end-directed activity, which is defined (explicitly or not) by the programmer who realizes (i.e. implements) it into some software program (i.e. encoding).

Duncan thus provides the following ontological definitions for software:

<footnote n="13">13. There is an acknowledged lack of clarity on this argument in the text as Duncan goes over it too quickly.</footnote>
**piece of computing hardware:** An *independent continuant* that is intentionally designed for the actualization of one or more computational functions.

**computational function:** A *realizable entity* that inheres in one or more pieces of computing hardware. The actualization or manifestation of a *computational function* is an essentially end-directed activity in virtue of the kind(s) of context(s) that the computing hardware is made for.

**software application:** A *generically dependent continuant* that encodes a representation of one or more *computational functions* (realizable functions).

The search for distinguishing hardware and software has set the ground for a dialectics that highlights the essence of software; in particular, the duality of *computational function* and *software application* is a noteworthy outcome that can have practical effects in the development of methods for software analysis.

## An Ontology of Malware

Here we move forward with the discussion about malware ontology. There exist scant propositions of malware ontologies that follow an analytical approach.

The appreciation of malware analysis (and malware classification) through the lens of the philosophy of technology is very recent, notwithstanding the profound conceptual issues that malware analysis entails. First we briefly present some contributions of philosophy of technology on the subject of malware ontology, then we discuss issues related to malware ontology with basis on the concepts previously presented.

**Malware as Malfunction-Inducing Artifacts** Primiero *et al* provide definitions for malware and malware types based on existing malware taxonomy [223]. They do not have the ambition of reformulating the ontology of malware from the ground up, instead they aim to obtain a general, language-independent functional description of malware. They note that malware categorization through specific languages (along the lines of the historical approach seen above) is “extensive and it offers a detailed identification of all properties of malware artifacts”, which is the reason why they cannot explain what makes certain software to be malware.

The central concept in Primiero's ontological and functional analysis of malware is software malfunction. Floridi *et al* developed the notion of malfunctioning software based on
the view that software are human-made and teleological artifacts, that can therefore mal-
function [92].

Malfunctioning occurs when the artifact does not do what it is supposed to do. Floridi *et al* distinguish two kinds of malfunction: a negative malfunction, referred as *dysfunction*, when an “artifact instance<fnref n="14" /> either does not (sometimes) or cannot (ever) do what it is supposed to do”; and a positive malfunction, referred as *misfunction*, when an “artifact instance may do what it is supposed to do, but it also yields some unintended and undesirable effect(s), at least occasionally”.

Primiero *et al* consider these definitions in the presence of malfunctioning inducing software, which they proposes as a definition for malware. Starting from a pragmatic taxonomy that classifies malware into four ground types, they recast these definitions in the form of conceptual formulations.

For instance, the definition of type 0 malware is recast from “an attack of the system limited to monitoring activities and possibly data leaks, without inducing any interruption of the system’s functionalities” to a malware that incurs in “no compromise of target system functionalities (no side effects, no dysfunctioning) but production of additional, unintended functionalities (misfunctioning)”.

Detailing Primiero’s ontology of malware goes beyond the scope of this thesis. Yet, once
again the basis for his ontology is oversimplified as it considers only software that “enacts
the exploitation and installation phases to attack the system”; existing malware types can
nonetheless have other purposes that are not reached by this definition (e.g. ransomware,
adware). Yet, creating a correspondence between malware and malfunctioning artifact is a
major contribution of this work.

**A Realistic Ontology of Malware** Seemingly, no previous work in literature attempted to propose a malware ontology in terms of a *realistic* ontology<sup>15</sup>.

Starting from the premise that malware must be a special type of software (i.e. a mali-
cious type), like any regular software, malware also embody the duality of software appli-
cation and computational function. The difference between malware and regular software
resides precisely in the facet of computational function, which involves an essential end-
directed activity that is malicious (in the case of malware). As for the software application

<footnote n="14">14. Floridi *et al* use the term “token” in the paper.</footnote>

<footnote n="15">15. The only reference found is a project by Timothy Schuler on Ontological Engineering at University at Buffalo, where an ontology for malware classification is presented. Link to the YouTube video: https://www.youtube.com/watch?v=22J6c0sPgHw.</footnote>
aspect, there is no reason to distinguish malware from regular software. Consequently, malware can be defined as a software whose the computation function fulfills a *malicious* purpose.

**Software Misfunction** According to the reasoning above, malware is a software whose essential end-directed activity is malicious. This definition implies the notion of *malice*, i.e. the deliberate intent of the software creator to cause harm to another party.

However a cyberattack may occur without any software purposefully created with malice. Indeed, a weak email password that is cracked by an attacker, or a backdoor that is obtained through a (legitimate) remote access software, are examples in which cyberattacks take place without involving malware. In both cases regular software are *abused* by an attacker who acts with malice.

Being an artifact, software has the inherent property of possibly *misfunctionning* (as defined by Floridi *et al* [92]). This concerns any software artifact and can be exploited in the course of a cyberattack, thus it can be claimed that any software bears a risk of being abused by a threat actor. In BFO language, this scenario can be described as a software that takes up the *role* of malware through the abuse of a malfunction in the course of a cyberattack.

As a consequence, in principle malware analysis cannot be restricted to (outright) malware only. It must instead deal with any kind of software. Beyond the detection and classification of outright malware —which is sometimes very straightforward, for cases like *ransomware*—malware analysis should embrace a more refined analysis of software in general, including those that are not malware (a.k.a. *cleanware* or *goodware*).

From a risk-based standpoint, while it is clear that malware are placed at the peak of the (computer security) risk spectrum, malware analysis should also strive to place goodware in this risk spectrum. Therefore, understanding commonalities between goodware and malware instances is essential to the success of malware analysis.
1.3 An Epistemology of Malware Research

One of the goals of scientific theorising is
to develop concepts which are adequate
to the phenomena under study. In my
view, things should work the same way
in epistemology. We want to know what
knowledge actually amounts to, not
what our folk concept of knowledge is,
since, just as with our pretheoretical
concept of acidity, it might contain all
sorts of misunderstandings and leave
out all manner of important things.

Hilary Kornblith

Epistemology comes from the Greek words *epistéme* and *logos*, where the former can be translated as *knowledge* (or “understanding”, or “acquaintance”) and the latter can be translated as “reason”, or “study of”. The goal is to understand the ways of knowledge and how we can gain knowledge. Historically, epistemology deal with the fundamental questions like [309]:

— What is knowledge, and what do we mean when we say that we *know* something?

— What is the source of knowledge, and how do we know if it is *reliable*?

— What is the scope of knowledge, and what are its *limitations*?

Here we are interest in analyzing theses questions in the context of malware research. However, before any attempt to contemplate knowledge through the prism of any epistemology of malware analysis, it is important to settle a basic understanding of these topics in a conceptual sense. Still, we do not intend to provide an extensive introduction about epistemology as treated in Philosophy; instead, we want to put forward the notions that were developed throughout centuries of debate, which can shed light on tacit assumptions presented in the methodologies of many studies. For a more comprehensive introduction, a curious lector may be interest in reading [272] and [128].
**1.3.1 Background**

The aforementioned fundamental epistemological questions are crucial to understand
how to shape knowledge and how to wittingly apply it to tackle practical problems (e.g. mal-
ware analysis). Indeed, these are very intricate questions that can be barely untangled.

This short background on epistemology intends to provide elements to unravel some im-
portant aspects of epistemology that clue in on answers to the fundamental epistemological
questions.

**What is knowledge?** In the study of knowledge, the very first objective is defining what type of knowledge interests epistemology. One can know how to play guitar, but not know anything about music theory or how a guitar is built; the opposite may also occur, meaning that one can know everything about music theory and guitar fabrication, but be unable to play music on a guitar. The former type of knowledge is related to procedural knowledge ('i.e. 'knowing-how'), whereas the latter is related to propositional <sup>16</sup> knowledge (i.e. "knowing-that"). Furthermore, "knowing-that" <sup>17</sup> should be distinguished from "knowledge by acquaintance" (i.e. "knowing-of") <sup>18</sup>, where the former is expressed in a declarative sentence or an indicative proposition (e.g. "Alice knows that Bob is a musician"), and the latter is constituted by familiarity with or direct awareness of the subject (e.g. "Alice knows Bob"). Epistemology is fundamentally interested in the type of knowledge related to propositional knowledge —henceforth implied in the use of the term "knowledge".

A very influential epistemological formulation is the notion of knowledge as *justified true belief* (known as JTB analysis), around which many philosophical debates gravitate. With aim of unpacking this notion, it is defended by many theorists —with many objections in many aspects by many other theorists —that JTB analysis holds because of the following arguments:

*The Truth Condition:* Most epistemologists consider that one can only know propositions that are true; otherwise they cannot be, or express, facts, and therefore they cannot be known. Here the notion of Truth is metaphysical, as opposed to epistemological: "truth is a matter of how things *are*, not how they can be *shown* to be" [128].

<footnote n="16">16. A proposition is a sentence capable of being true or false. For instance, the sentence "look at the sky" is not a proposition, whereas the sentence "the sky is blue" is a proposition.</footnote>

<footnote n="17">17. Associated with Latin word scientia, that originates the French verb savoir.</footnote>

<footnote n="18">18. Associated with Latin word cognitio, that originates the French verb connaitre.</footnote>
*The Belief Condition:* The belief condition is slightly more controversial than the truth condition [128]. The motivation for this condition leans upon the claim that you can only know what you believe, and failing to believe in something precludes knowing it. For the JTB analysis, “belief” means *full* belief, or *outright* belief. To believe *outright* that some proposition holds it is not enough to have a pretty high confidence, it is something closer to a commitment or a being sure.

*The Justification Condition:* True beliefs are not enough to establish knowledge. Alice can outright believe that it is currently sunny in Copacabana, without being there nor having any weather information about this location, and it can actually be that it is sunny there at this very moment. As such, Alice's proposition is a true belief but this proposition does not qualifies as knowledge, since it is the mere outcome of a lucky guess<sup>19</sup>. The role of justification in the JTB analysis is to ensure that luck does not play a primary role in producing true belief. (True) knowledge in some epistemic sense must be proper or appropriate, hence *justified* [128].

Besides criticisms regarding the JTB analysis (that goes beyond our scope), a major pitfall of this approach is assessing whether these conditions are met. For instance, how can one assess that the truth condition for a given proposition is met? What is the metaphysical nature of truth? Can we ever expect to reach Truth? If not, does it preclude the creation of knowledge? In the remainder of this section we present some theories that can help to scrutinize the attainability of each condition.

**Theories of Truth** There are a multitude of theories addressing the “problem of truth”, stated as: what truths are, and what (if anything) makes them true. The most significant ones for the contemporary philosophical literature include the *correspondence*, *coherence*, and *pragmatist* theories of truth [103]. An elementary summary of these theories is provided below:

*The Correspondence Theory of Truth:* An ontological thesis is at the core of this theory: a belief is true if there exists an appropriate entity —a fact—to which it corresponds. If there is no such entity, the belief is false [103]. Here, facts are composed of particulars and properties or relations or universals. More importantly, facts are entities in their own right that exist in the world. Therefore, propositions are true when they *correspond*

<footnote n="19">19. Some epistemologists consider the sole factor of “true belief” a form of *weak* knowledge.</footnote>
to a (metaphysical) fact that exists in the world. The truth of the proposition "the sun shines in Copacabana" denotes that the fact <sun, Copacabana, now> currently belongs in the world, while the contrary fact <rain, Copacabana, now> does not.

*The Coherence Theory of Truth:* To this theory, a belief is true if and only if it is part of a coherent system of beliefs [103]. Thus, a proposition is true if it is subsumed in a belief of a system (or “significant whole”). For the coherence theory, truth is a content-to-content (or belief-to-belief) relation —which is different from the neo-classical correspondence theory, where truth is rather a content-to-world relation.

*The Pragmatist Theory of Truth:* A very different perspective to truth is taken by pragmatist theorists. To pragmatists, truth is what “is useful to believe and has practical values in our lives”. Simply put: “truth is what works”. Another important disposition of this theory is the tentative nature of truth. A frequently-quoted passage in Charles Peirce’s “How to Make Our Ideas Clear” (1878) asserts [41]: *All the followers of science are fully persuaded that the processes of investigation, if only pushed far enough, will give one certain solution to every question to which they can be applied. (...) The opinion which is fated to be ultimately agreed to by all who investigate, is what we mean by the truth.*

All these theories are subject to critics. The major pitfall related to the *Correspondence Theory of Truth* relates to the critic that one cannot experience reality firsthand as it is; instead one always experience *through* (potentially deceptive) sensors—even with respect to the “personal experience”, which is mediated by the individual's sensory organs and mind. As for the *Coherence Theory of Truth*, its main issue relates to the possibility of constructing a theory that is (intrinsically) a coherent theory, but actually biased. With respect to the *Pragmatist Theory of Truth*, the main critics is that ideas that “work” may not necessarily match with the common understanding of truth.

**Justification: Internalism vs. Externalism** According to the JBT analysis of knowledge, when deciding whether a proposition may be accounted as knowledge, the proposition must successfully observe the justification condition. Nonetheless, nothing is said about what makes a justification valid. What makes a belief properly justified? What types of evidences are relevant in determining justification? What counts as evidence for justifying a belief? In a nutshell, what is evidence?

Evidences are the constituent of a *knowledge base*. They can be obtained through per-
ceptual, introspective, memorial, and intuitional experiences, or resorting to reliable source,
where a reliable source is one that tends to result in mostly true beliefs [272]. Toward this
end, two main schools of thoughts exist with different views on what counts as evidence:
*internalism* and *externalism*.

According to the internalist view, the justification has to have *access* to internal evidential
reasons of a justified belief. It means that upon reflection one must be able to *recognize* the
justification for holding a certain belief. According to the externalist view, justification is the
result of an attitude that prevents beliefs from being accidentally true; even if one cannot
recognize how the belief itself is justified. For externalists, justification is *truth-conducive*.

To illustrate the differences between the internalism and externalism views, let us imag-
ine that two people are trying to predict the birth date of a baby. Person A believes that
the delivery date will be within 130 days, based on the results of clinical examination, ul-
trasonography, and human chorionic gonadotropin pregnancy tests. In turn, person B be-
lieves that the delivery date will be within 130 days because it will be the first full moon after
the 9th month of pregnancy. Both are justified in their beliefs: person A adheres to scien-
tific knowledge about estimation of delivery date and the outcome of direct examination,
whereas person B adheres to cultural creeds that say that full moons are auspicious to child-
birth. Both may turn out to be correct if the child actually is born within 130 day. In this
case, externalists (may) admit that both people *knew* that the birth date would be within 130
days, because both of them held a justified true belief. However, internalists do not accept
the justification of person B for the estimation of the birth date, because there is no clear-cut
causal relation between the baby in the womb and the Moon; therefore internalists would
say that only person A knew the birth date of the child.

The epistemological difference between both justification is that the former one is a **dox-**
**astic justification**, whereas the latter is a **propositional justification**. They are defined as
follows: “One has propositional justification when one *has justification* for belief in a propo-
sition (i.e., when one possesses good reasons, evidence, or justification to believe a proposi-
tion). One has doxastic justification when one not only has justification to believe a propo-
sition *but also believes* the proposition and believes it at least partly on the basis of good
reasons, evidence, or justification one has.” [120]. According to this definition, *doxastic jus-
tification* sets stronger requirements than *propositional justification* to be fulfilled; on the
other hand, one does not always has access to internal evidential reasons of a belief, which
make this requirement much harder (sometimes impossible) to be met.

Two more basic concepts are important to nuance the internalist and externalist think-
ing: evidentialism and reliabilism. Evidentialists value the possession of firsthand evidences for justifying beliefs; for instance, a “experientialist” version of evidentialism would only count firsthand experience as evidence for justification. On the contrary, reliabilists value reliable sources (e.g. experiments) for justifying beliefs, where a source is reliable just in case it tends to result in mostly true beliefs. Evidentialism is typically associated with internalism, and reliabilism with externalism [272].

Returning to the example of the childbirth date prediction, let us admit by a fact that the full moon indeed does not have any interference in the pregnancy whatsoever. This scenario boils down to the *Gettier problem*, since “neither the possession of adequate evidence, nor origination in reliable faculties, nor the conjunction of these conditions, is sufficient for ensuring that a belief is not true merely because of luck” [272]. It means that holding justified true belief may not always be sufficient to knowledge. Detailing the implications of the Gettier problem and all the theories of knowledge that emerged thereupon is beyond the scope of this thesis; yet, the JTB analysis is a good starting point to reach a better understanding of knowledge.

**The Regress Problem and the Structures of Knowledge**

In the traditional justification method, evidences are required to hold a belief as knowledge. However, evidences are constituent of some knowledge base, thus being themselves also knowledge that must be justified. This inference relationship engenders a recursive link of reason for reason, which is known as the “regress problem”.

To address the regress problem, epistemologists conceived four possible structures of knowledge:

**Foundationalism:** according to this theory, there are certain beliefs that are “self-evident truths”, or *basic*, which are exempted from any justification. There are supplementary beliefs (i.e. *nonbasic* beliefs) that need to be justified, having a proper *basing relation* [150] in the steps of a justification that backtracks down to basic beliefs. To foundationalists, the structure of knowledge is like a building, consisting of a superstructure of nonbasic truths that rests upon a foundation of basic truths [272], thus having a ground level where the regress problem reaches an end.

**Coherentism:** coherentists reject the idea that there are any basic beliefs [272]. To them, justified beliefs receive justification from other beliefs in their epistemic neighborhood. The more these beliefs dovetail in a coherent way (i.e. without contradictions), the better
justified they are. To coherentists, the structure of knowledge is like a web, where the
strength of any given area depends on the strength of the surrounding areas [272], thus
having loops where the regress problem gets trapped.

***Infinitism:*** infinitists claim that that infinite evidential chains can provide justification to their members [58]. Infinitists do not consider the regress problem incompatible with the building of knowledge.

***Skepticism:*** Skeptics reject all the other epistemological structures, which leads to the conclusion that (true) knowledge is impossible. Therefore, to skeptics it is indeed impossible to deal with the regress problem.

The most popular school of thoughts among epistemologists is the foundationalism, followed by coherentists. Infinitists appeared recently in the debate and is still in development. Skeptics is the least adopted school of thought.

This short background on epistemology provides some clues to untangle the aforemen-
tioned fundamental epistemological questions: Knowledge can be thought (despite limi-
tations) in terms of the *JTB analysis*; the source and scope of knowledge depends on the
*Structure of Knowledge* adopted, which sets the conditions and limitations for knowledge
building; finally, the *reliability* of knowledge depends on the requirements for *justification*,
which must be met in order to validate the constitution of knowledge. These concepts will
guide our subsequent epistemological discussion about malware research.

1.3.2 Epistemological Matters of Cybersecurity

**Epistemological Diagnosis of Current Malware Research** In this section we elaborate a concise epistemological diagnosis of malware research. The epistemological diagnosis aims to identify how knowledge is structured in malware research 20.

Botacin *et al* define *malware research* as “a term used in the literature to describe a wide
field of work that embraces multiple goals” and they provide an extensive list of research ob-
jectives in malware analysis (e.g. malware detector, family classifiers, honeypots, etc) [29].
For our diagnosis, the marker to identify the *malware researches* of interest is the use of in-
stances of malware in some part of the experimental process. This criterion encompasses an
overwhelming majority of malware-related studies —not to say all practical ones.

<footnote n="20">20. Our allusion to *malware research* is intentionally open, along the lines of several related works whose subject is the meta-study of scientific methods and methodologies existent in the literature.</footnote>
Notwithstanding the methods and methodologies<fnref n="21" />, these studies have to inevitably confront a bootstrapping problem: software instances recognized as malware —or alike, e.g. belonging to a malware family —are needed in order to build and/or evaluate a malware analysis systems.

As a rule, this problem is addressed through the prior constitution of a set of annotated
software instances that are assumed to be *known malware* (or malware family, or malware
type, etc), which are designated as **ground truth**.

Analyzing prior works, Kantchelian *et al* identified four main approaches to assign ground-truth labels to datasets [140]: 1) label data manually, 2) use labels from a single source, 3) use labels from a single anti-virus vendor, and 4) use labels from multiple anti-virus vendor.

In case 1, software instances are analyzed by experts in order to (manually) assign them
to ground-truth categories.

In case 2, instances are taken from public repositories (e.g. Anubis, VX Heavens, Wildlist Collections and Malfease dataset <fnref n="22" />) that have their own methods for assigning instances to ground-truth categories <fnref n="23" />.

In case 3, the labels come directly from the anti-malware products which, despite working as black-boxes, have technical documents alluding to a combination of machine learning algorithms and expert knowledge in the analysis [154]. Botacin *et al* summarized this case as a “combination of all aforementioned techniques [pattern matching signature, heuristics and machine learning] in their detection engines”, concluding that “their detection rates and labels are biased by all these factors at the same time”. [30]. Case 4 is merely an extension of case 3 <fnref n="24" />.

Examining the aforementioned approaches through the prism of the epistemological
regress problem, we almost invariably get to a situation where the human analysis process
takes the lead, with few exceptions (e.g. Anubis). Even in the case of machine learning al-
gorithms, depending on the approach taken, ground knowledge may be traced back to hu-
man analysis. The process to produce labels in which the assignment is the outcome of a
firsthand human analysis —or derived through some rule derivation process (e.g. pattern
matching signatures) —can be biased due to the inherent subjectivity of human analysis.

Epistemologically, when studies in malware research use ground-truth primordially de-

<footnote n="21">21. *Methodology* refers to the overarching strategy and rationale used to address a research problem, whereas *methods* refers to specific algorithms and procedures used to collect and analyze data.</footnote>

<footnote n="22">22. Listed here as in the paper [140], even though some of them do not exist anymore.</footnote>

<footnote n="23">23. For instance, Anubis used the clustering method proposed by Bayer et al. [22], whereas VX Heavens gradually builds an inventory of malware samples gathered from reports of security companies.</footnote>

<footnote n="24">24. Case 3 can also be seen a particular case of case 2.</footnote>
rived (directly or indirectly) from human analysis, the manual analysis is tacitly assumed as
being *true* (along the lines of the Pragmatist Theory of Truth), product of an *outright belief*
(of the analyst) and exempted from any further *justification* (along the lines of the proposi-
tional justification).

Such ground-truth is predominantly adopted by our scientific community as *basic knowl-
edge* upon *nonbasic knowledge* (i.e. new methods and methodologies for malware analysis)
are built. Thus, we can claim that *Foundationalism* is the prevalent epistemological *structure*
*of knowledge* in malware research.

**Pitfalls of externalist justification for malware research**

When a study takes ground-truth as an opaque value that underpins an evaluation process without carefully identifying its relationship with the observables, the study takes an *externalist* approach. For as long as the outcome of the evaluation process is considered positive —and reliable, for reliabilists—the study is considered (externally) justified.

This is a practical approach, because it is not always possible to recognize a direct link
between observables and the ground-truth, while it is still possible to measure their correla-
tion. However, this entails some hazards that must be taken into account.

For instance, in a study conducted at Harrisburg University, researchers developed a
software for automated computer facial recognition that was allegedly capable of predict-
ing whether someone is prone to be a criminal <sup>25</sup>. According to this research, the software
could “predict if someone is a criminal based solely on a picture of their face”, with “80 per-
cent accuracy and with no racial bias”. This study was heavily criticized by a coalition of 2425
professors, researchers, practitioners, and students in the fields of anthropology, sociology,
computer science, law, science and technology studies, information science, mathematics
(and more), who released a public letter to debunk this study <sup>26</sup>, pointing weaknesses on the
adopted premises.

Other examples of similar scientific blunder are the 2016's *"Automated Inference on Crim- inality Using Face Images"*<fnref n="27" /> by Xiolin Wu and Xi Zhang at Shanghai Jiao Tong University or the 2017's *"Deep neural networks are more accurate than humans at detecting sexual ori- entation from facial images"*<fnref n="28" /> by Yilun Wang and Michal Kosinski at Stanford University.

<footnote n="25">25. Link to the press release announcing this publication: https://archive.md/N1HVe#selection-159
3.69-1593.197</footnote>

<footnote n="26">26. Link: https://medium.com/@CoalitionForCriticalTechnology/abolish-the-techtoprisonpi
peline-9b5b14366b16</footnote>

<footnote n="27">27. Link: https://arxiv.org/pdf/1611.04135.pdf</footnote>

<footnote n="28">28. Link: https://osf.io/zn79k/</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 1.3 – Example of flawed external justification</figcaption></figure>

The former proposes an “automated inference on criminality based solely on still face im-
ages, which is free of any biases of subjective judgments of human observers”, “achieving
89.51% accuracy” (according to their ground-truth) —*criticized* by engineers from Stanford
and Google 29 —the latter uses deep neural networks to determine the subjects sexual orien-
tation solely based on their faces, achieving accuracy rates of 91% and 83% when distinguish-
ing sexual orientation for men and women respectively (according to their ground-truth)
—which was also subject of *critics* 30 .

All these examples fall into a practice known as *Physiognomy*, which was completely
abandoned by the scientific community and is understood nowadays to be a pseudoscience
(with deep racist traits) [270]. Beyond the ethical issues, note that the culprit does not re-
side in the adopted methods (as *Techne*), but instead in the basal knowledge on which the
methodology (as *Episteme*) operates.

At least in hypothesis, some approaches used in malware analysis can potentially sustain
the same malformation of *Techne* and *Episteme*, which can be very difficult to spot. Despite
not engendering the same ethical implications, this circumstance must avoided (or acknowl-
edged as a threat to validity) by methodologies adopted in malware analysis.

<footnote n="29">29. Link: https://medium.com/@blaisea/physiognomys-new-clothes-f2d4b59fdd6a</footnote>

<footnote n="30">30. Link: https://qz.com/1078901/a-stanford-scientist-says-he-built-a-gaydar-using-the-lamest-ai-to-prove-a-point/</footnote>
**Security as Social Knowledge** Ground-truth is a far-reaching problem in malware research. Even when the epistemological stance concerning ground-truth is left aside, studies struggle with issues like inconsistency (i.e.multiple ground-truth sources providing contradictory labels), instability (i.e. labels change over time), delay (i.e. labels may not be readily available when data is collected), etc.

A standpoint that helps understanding the overwhelming complexity in establishing ba-
sic knowledge (i.e. ground truth) in the field is to consider security as a *social* discipline.
Schaefer firmly claims “(computer) security is social”[253], as there is no “act of nature” (e.g.
law of physics, molecular binding, etc) ruling data; on the contrary, they are representation
of *ideas* instilled through custom, culture and law, by education and training, hence social.

Scharfer elaborates on the essences of security; for him, security is a “risk tradeoff” be-
tween greater or lesser *control* for better or worse consequences. This view outlines the na-
ture of security as the rationale for *control*. In computer security this control is exerted on
data, therefore the rule of thumb in this case is *differentiating data* (harmful data from harm-
less data).

In malware analysis this reasoning seems to hold as the final goal is to differentiate pro-
grams (i.e. data) into the categories harmful (i.e. malicious) and harmless programs. We
may also be interested in many other intermediate goals (e.g. variant detection, malware
families, etc) but they are auxiliary to the ultimate goal of protecting computer systems, thus
precluding the execution of malicious programs whenever possible.

This social perspective highlights a pitfall in malware research related to the creation
of ground-truth, which excessively depends on (too few) experts that are in charge of label
creation. Other strategies hinging on methods and methodologies borrowed from social sci-
ences (e.g. internal validity, external validity, construct validity, and statistical conclusion
validity) could be applied for creating ground-truth, specially when it comes to “qualitative
data” related to malware.

1.4 An Axiology

In the previous sections we examined several important issues from different perspec-
tives that underlie malware research. Our discussion about the ontology of malware provides
a fundamental analysis about the nature of malware; our discussion about the epistemology
of malware research aims to identify how the prior knowledge about existing cyber threats
influences the construction of new knowledge about new threats, scrutinizes the pitfalls of
certain justification strategies and determines the social dimension of (computer) security.

These topics, although all-important, are almost always implicit in studies about the methodologies of malware research. We take another approach; by developing the discussion about these topics we are able to firmly ground our *research paradigm*, namely:

**Axiology-1** pursuing no ontological difference between malware and software at the “realization level”;

**Axiology-2** being more coherent driven;

**Axiology-3** being more doxastically justified;

In accordance to item **Axiology-1**, we do not seek any malware trait that is manifested at the “realization level” (e.g. a sequence of bytes that is inherently malicious). We understand that the malice in software is revealed within a context of use, which can even denature software that were not designed to be malicious —hence not malware, by definition —into acquiring the role of malware depending on this context.

However, we do assent to the idea of *software birthmarks*, which are properties of software instances which provide a unique identity to them [203]. Software birthmarks allow to distinguish software instances according to the degree of commonalities shared among them. This shapes the notion of (software) families (that can happen to be malicious or not) and precludes the practical use of “malware types” (e.g. virus, trojan, etc) that emerged organically throughout history.

While the analysis of software birthmarks can be fully automated, the assessment of malice in software (or at least the degree it can be harmful) depends on some human judgment at some point in chain inasmuch as (computer) security is a socially-rooted activity. Nonetheless, automated analysis could leverage software birthmarks to propagate former analysis of software instances onto new similar ones, thus producing an amplification effect that can optimize the use of any necessary human effort dedicated to malware analysis.

Additionally, in our research paradigm we strive to steer clear of subjectivity inherent to human analysis by following items **Axiology-2** and **Axiology-3**. The intention is not to rebuild malware analysis from scratch ignoring any kind of human analysis. Instead, we want to bootstap from established research (which is predominately foundationalist-based) toward a more coherent-based knowledge justification in which we privilege observables that can be measured and are internal to the system over external ground-truth knowledge.

We still deem valuable and necessary to count on external knowledge to establish a ground-truth. In the evaluation process, in particular, external knowledge is very important as we
only have access to a tiny part of reality through our dataset. But our aim is to build meth-
ods and methodologies that lean more and more on data obtained from direct analysis, thus
emancipating our analysis framework from external dependencies.

The goal is to shift the paradigm in which knowledge is propagated as a cascade, where
past information propagate onto new information, to a new paradigm where software birth-
marks are used as a network that connects software instances, carrying information from
one end to another.

1.5 Conclusion

In this chapter we exposed our research paradigm, which entails a broader discussion
about ontology and epistemology in malware research. This is necessary because malware
analysis is a field highly driven by problem-solving thinking that has been evolving organi-
cally over the last decades.

Initially we adopt a twofold approach to establish an ontology of malware, i.e. a histor-
ical one and an analytical one. The historical-based approach reviews the history of how
concepts emerged in the field, and then present several ontologies that were proposed fol-
lowing this perspective. The quick obsolescence of historical-based ontologies is a particu-
lar hitch of this approach, which happens due to the accelerated pace in which new threats
emerge and new concepts are created in response. The analytical approach works through
a more perennial reasoning, building a parallel between malware and software, in view of
malware as a special kind of software (i.e. a malicious kind). This approach allows to identify
the teleological function inherent to software, providing a basis for a definition of malware
as software that have an essential end-directed malicious function. On the other hand, this
approach also reveals that malware analysis cannot be restrict to (pure) malware, since soft-
ware can misfunction and thus assume the role of malware.

Then, we provide an epistemological discussion about malware research. We recognize
malware research as being predominately foundationalist, and we identify some pitfalls that
need to be avoided. Furthermore, we take notice of (computer) security as a socially-rooted
activity, which precludes the idealistic conceptualization of a framework that would com-
pletely exempt from any human intervention.

All identified limitations mold the pieces of a puzzle that compose our research paradigm.
As a result, they allowed us to set up our axiology, which guides the methods and method-
ologies proposed all along this thesis.
# GENERAL BACKGROUND

## 2.1 Introduction

This section presents the general background with fundamental topics that situates the entire body of the thesis. Here we provide a literature review broadly introducing themes that are proper to the thesis. Greater details as well as the state-of-the-art for each topic are presented in the next chapters, as they are more relevant to each contribution.

This chapter is organized in two parts (machine learning and malware analysis) reflecting the two research fields that ground our study. This general background starts with a review about machine learning (section 2.2, page 57), then addresses malware analysis (section 2.3, page 87). This order is preferable since the latter is increasingly dependent on machine learning methods.

## 2.2 Machine Learning

Machine Learning is a branch of artificial intelligence that emulates the process of learning, aiming to give machines (or in fact IT systems) the ability to learn from previous information. Mohri et al give a broad definition of machine learning as “computational methods using experience to improve performance or to make accurate predictions” [195]. This definition entails the use of past information available for the learning process, i.e. the notion of *experience*.

In the classical computational approach, tasks are carried out by algorithms designed to mechanically solve specific problems. For instance, given a graph as input to the Dijkstra's algorithm, it can output the shortest path between any two given nodes. Machine learning takes another approach, as it leverages existent data related to the targeted problem in order to autonomously figure out solutions.

According to this approach, instead of finding the best solution through a task-oriented algorithm (e.g. Dijkstra's algorithm), data about the structure of the graph can be learnt by
a machine learning algorithm, which becomes able to output a short (perhaps the shortest)
path between a pair of nodes provided as input. Arthur Samuel, a computer scientist who
pioneered the study of artificial intelligence, defines machine learning as "the study that
gives computers the ability to learn without being explicitly programmed" [115].

Despite the lack of guarantee that this output actually is the best solution —which can
be understood at first glance as a handicap —experience shows that machine learning algo-
rithms are in practice able to converge to (quasi-)optimal solutions, by improving the quality
and size of the data available during the learning process.

Typically, the information used in machine learning is supplied in the form of data that are processed by agnostic algorithms, independently of the subject represented by the data. Conceivably, raw data can be enriched with additional meta-information —most often by human experts, referenced as “expert knowledge” —that can be leveraged during the learning process.

Machine Learning is currently used as an important tool in a plethora of areas, such as natural language processing, speech recognition, computer vision, among many others. Mohri et al express the practical motivation for using machine learning as follows: “The main practical objectives of machine learning consist in generating accurate predictions for unseen items and of designing efficient and robust algorithms to produce these predictions, even for large-scale problems” [195].

2.2.1 Definitions and Terminology

Machine Learning has its own vocabulary, which we define below and use hereinafter:

* Sample (or Data Points or Example): unit of data used in the algorithms.

• Features: set of attributes or characteristics associated to a sample.

* Labels: meta-data assigned to the samples.

* [Machine Learning] Model: an instantiation of a [Machine Learning] algorithm.

Machine learning instantiations are stateful due to the need of maintaining internal states
that are updated during the learning process, hence the importance of referring to each in-
stantiation as an individual *model*. Note that two models of the same algorithm differ be-
cause they may undergo different learning processes (by learning from different data, by
randomness of internal states, etc), therefore the results obtained may differ in use.
**Classes of Learning Problems in Machine Learning**

The classes of learning problems addressed by machine learning include [195]:

* Classification: category assignment to unclassified items based on priory classified.

• Regression: prediction of new data points based on a set of known data points.

• Ranking: ordering of items according to some malleable criterion.

* Clustering: partition of items into homogeneous regions.

* Dimensionality reduction or manifold learning: transformation of a given representation of items into a lower-dimensional representation which preserves properties of the initial representation.

In this thesis we are specially interested in the problems of classification and clustering; therefore, henceforth, we implicitly assume these problems as our use cases/contexts of machine learning.

**Phases of Machine Learning Algorithms**

Machine learning algorithms have to 1) learn from previous experiences and 2) make predictions. Therefore, as a rule, they comprise two main routines: *fit* and *predict*. This dichotomy, associated with the fact that in general learning (i.e. *fit* routine) and prediction (i.e. *predict* routine) do not take place concomitantly, implies the notion of *phases* when working with machine learning algorithms.

In the *learning phase* (also referred as *training phase*) the fit routine is evoked with some (learning) data corpus. Depending on the usage goal, the expected results of the subsequent prediction routine for the data corpus can be already known or not.

For instance, in the case of classification models the categories associated with the learn-
ing data are already known beforehand, whereas in the case of clustering there is no prior
information about the regions shaped by the data points. In the former case, during the
learning phase the goal of the model is to fit its internal states according to the learning data
in order to reproduce predictions corresponding to the expected categories as much as pos-
sible; in the latter, the goal of the model is to fit its internal states so as to partition the space
in regions according to the learning data points.

To measure the performance of models once the learning phase is complete, the *valida-
tion phase* (also named *test phase*) often benefits from the prediction routine. In this phase,
<figure><img src="image_9.png" /><figcaption>Figure 2.1 – Visualization of bias and variance errors as darts at a dartboard².</figcaption></figure>

predictions on new data (i.e. data not used during the learning process) are made and the
results are evaluated according to some *ground truth* <fnref n="1" />.

Making sense of this phase can be tricky because the expected responses for the test data are already known beforehand (i.e. in accordance with the ground truth); however, the test data is completely new to the model, since they were not used during the learning phase. The goal is, therefore, to measure how well predictions of the (trained) model can match with the ground truth.

**Ground Truth-Dependent Evaluation Metrics**

Several metrics commonly used when measuring models performance during the validation phase are ground truth-dependent. They allow to measure prediction errors and thus to evaluate how successful was the training of the model.

There are two fundamental causes for prediction errors: *bias* and *variance* [115]. The former refers to the type of error occurred when the predictions deviate from the expected values (i.e. ground truth); the latter refers to the type of error produced by the internal deviation of the predictions. A model that makes predictions with low bias is qualified as *accurate*, while a model with low variance is qualified as *precise*.

<footnote n="1">1. Establishing a ground truth involves epistemological issues that may be extremely challenging in practice. Refer to section 1.3.2 (page 50) for an extensive discussion of this topic in the context of cybersecurity.
2. Image published at https://www.mfg-space.com/wp-content/uploads/4-situations-of-your-CNC-machined-parts.jpg (accessed October 2022)</footnote>
<figure><img src="image_10.png" /></figure>

Several metrics are commonly used to measure the performance of models. A simple applied example is screening studies. When assessing a prediction model used to diagnose whether patients have a particular disease, we basically find the following scenarios: when the model correctly predicts that a sick person is sick, this prediction is a *true positive*; when the model correctly predicts that a healthy person is healthy, this prediction is a *true negative*; when the model wrongly predicts that a healthy person is sick, this prediction is a *false positive*; when the model wrongly predicts that a sick person is healthy, this prediction is a *false negative*.

With these four outcomes it is possible to measure the *accuracy*, *precision*, and *recall* of the model. For a set of *N* predictions, let *TP* designate the number of true positives, *TN* the number of true negatives, *FP* the number of false positives, and *FN* the number of false negatives. The model *accuracy* (*ACC*) is computed as follows:

$$ACC = \frac{TP + TN}{N} \qquad (2.1)$$

In general, producing correct predictions (i.e. accuracy) is a primary goal of machine learning models. However, from equation 2.1 we observe that different models can attain the same level of accuracy in very different ways: for instance, a model which is good at
predicting that a patient is healthy but bad in predicting that a patient is sick —i.e. good TP and bad TN —may attain the same accuracy of a model which is bad at predicting that a patient is healthy but good in predicting that a patient is sick —i.e. bad TP and good TN.

Therefore, it is necessary to consider the *sensitivity* and the *specificity* of the model to better understand how true positives and false negatives interplay. The model *sensitivity* (or *recall* (R) or TPR, i.e. true positive rate) evaluates the rate of true positive predictions among the totality of positive predictions, whereas the model *specificity* (or *selectivity* (S) or TNR, i.e. true negative rate) evaluates the rate of true negatives predictions among the totality of negative predictions.

$$R = TPR = \frac{TP}{TP + FN} \quad (2.2) \quad S = TNR = \frac{TN}{TN + FP} \quad (2.3)$$

We notice that the *specificity* of the model increases inasmuch as the rate of negative predictions grows. However, the number of negative predictions can be increased at the expense of producing false negatives —in the extreme case of a model that always outputs a negative prediction, the *selectivity* attains $S = 1$. On the other hand, *sensitivity* increases inasmuch as the rate of positive predictions grows, therefore *specificity* and *sensitivity* are mutually complementary measures.

Another supplementary notion is the *precision* (P) of the model, which measures the rate of correct positive predictions and is computed as follows:

$$P = \frac{TP}{TP + FP} \quad (2.4)$$

Precision measures how good the positive predictions of a model are, while recall measures how good the model is in not missing any positive predictions. Both values can be combined in a unique score like the *F-score*, computed as the harmonic mean of precision and recall:

$$F = \frac{1}{\frac{1}{2}P^{-1} + \frac{1}{2}R^{-1}} = \frac{2}{P^{-1} + R^{-1}} = 2\frac{P \cdot R}{P + R} \quad (2.5)$$

A more general definition of F-score is the *F-score*, which introduces a factor $\beta$ to counterbalance the importance of precision or recall in the final value. It is defined as follows<fnref n="3" />:

<footnote n="3">³. The reason for using $\beta^2$ instead of simply $\beta$ is because this parameter is derived from Van Rijsbergen's effectiveness measure which attaches $\beta$ times as much importance to recall as precision, i.e. $\frac{\partial F_{\beta}}{\partial P} = \frac{\partial F_{\beta}}{\partial R}$.</footnote>
$$F_{\beta} = \frac{1}{\frac{1}{\beta^2+1} P^{-1} + \frac{\beta^2}{\beta^2+1} R^{-1}} = (1 + \beta^2) \frac{P \cdot R}{\beta^2 P + R} \quad (2.6)$$

It is trivial to notice that standard F-score is the special case of $F_{\beta}$-score in which $\beta = 1$.

## Learning Paradigms

Three major learning paradigms are used in machine learning:

* *Supervised Learning* in which examples are provided along with labels at the learning phase. The fitting routine hinges on the classification of known examples to adjust internal parameters of the model in order to set up the prediction routine for the classification of new (unseen) examples.

* *Unsupervised Learning* in which examples do not have ready available labels at the learning phase. The fitting routine looks for affinities between data points across the whole set of examples, creating groups of similar objects accordingly (referred as *clusters*)<fnref n="4" />.

* *Reinforcement Learning* in which agents<fnref n="5" /> deduct how to perform a certain action through a series of trial and error that receive rewards and punishments every so often.

Examples of applications of these paradigms include, respectively, algorithms that:

- can learn how to identify cats and dogs on pictures given a set of pictures (of cats and dogs) and their corresponding classes (i.e. labels indicating whether a given picture contains a cat or a dog). After the training phase, the model becomes able to predict the classes of new pictures (i.e. never before seen by the model);

- form clusters in which consumers with similar buying habits are put together according to their transaction history on a shopping website. These clusters allow to constitute a set of consumer profiles that buy on the shopping website.

- can train agents to play Atari games [193] through a numerous repetition of game playing while adapting strategies according to the result of each game instance —i.e. a reward whenever the strategy leads to a victory or a punishment whenever it leads to a loss.

<footnote n="4">4. Dimensionality reduction methods are another example of unsupervised learning, however we do not detail them here since they are not used in the remainder of the thesis.</footnote>

<footnote n="5">5. In the context of reinforcement learning taxonomy, *agents* is the taxonomy equivalent to *models*.</footnote>
In the context of this thesis, **we only use supervised learning and unsupervised learning** and, therefore, we only detail these two learning paradigms henceforth.

### 2.2.2 Supervised Learning

The main goals as well as the overall working principles of supervised learning were discussed above. In this section we provide a more detailed presentation of this topic, which includes the description of several important methods and the discussion of methodological concerns related to supervised learning.

**Supervised Learning Methods**

Here we provide a brief introduction of different classification methods used in supervised learning: Logistic Regression, Naive Bayes, Decision Trees, k-Nearest Neighbors (k-NN) and Neural Networks. The purpose here is to present some of the main strategies used in supervised machine learning, starting from methods originated from traditional statistics (e.g. Logistic Regression, Naive bayes), which fall under supervised machine learning as they leverage training data to fit a prediction routine, up to more recent methods (e.g. neural networks), which were developed for the purpose of supervised machine learning.

**Method 1: Logistic Regression** The logistic regression is used to solve the problem of binary classification. During the learning phase, the logistic regression method fits a sigmoid function$^6$ ($\sigma$) to the set of training data, hence the name *logistic regression*.

The learning routine is given as input a set of training data {$X_i$} whose labels belong to one of two (mutual exclusive) classes: {$X_{1,j}$} and {$X_{0,k}$}, where {$X_{1,j} \cup X_{0,k}$} = {$X_i$} and {$X_{1,j} \cap X_{0,k}$} = $\emptyset$. In the statistical notation it means that $P(X_i) = 1$ if it belongs to the reference class (say, $X_i \in \{X_{1,j}\}$) or $P(X_i) = 0$, otherwise (i.e. $X_i \in \{X_{0,k}\}$).

The learning algorithm uses *logit* (the inverse function of the sigmoid function) to re-shift the coordinates system in such a way that the values of the sigmoid become represented by a line as shown in figure 2.2.

Then, the best fitting line is found through an iterative procedure that maximizes its total likelihood. Figure 2.3 shows how to obtain the values of the logit projection $Y_i$ for the training data points. Since the computation of the likelihood depends on the class of the data point,

<footnote n="6">6. Details about the sigmoid function and some of its properties are provided in the appendix section 6.2 (page 303).</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 2.2 – Coordinate re-scaling using the *logit* function</figcaption></figure>

the training data {$X_i$} is split in two, for data points that do (in blue) and do not (in red) belong to the reference class (i.e. respectively {$X_{1,j}$} and {$X_{0,k}$}).

The computation of likelihood of a data point then goes as follows:

$$P(X_i) = \begin{cases} \sigma(Y_{1,j}) & \exists X_{1,j} \rightarrow X_i, \text{ if } X_i \in \{X_{1,j}\} \\ 1 - \sigma(Y_{0,k}) & \exists X_{0,k} \rightarrow X_i, \text{ otherwise} \end{cases}$$

Finally, the total likelihood of a candidate sigmoid curve is computed as $\sum P(X_i), \forall \{X_i\}$. The sigmoid curve that provides the maximum total likelihood ($\sigma_\beta$) is used in the prediction routine to output whether an unseen data point (Z) belongs to the reference class (i.e $\sigma_\beta(Z) \ge 0.5$) or not (i.e $\sigma_\beta(Z) < 0.5$).

Logistic regression is a *discriminative classifier*, because it directly computes the probability of a data point belonging to a class, i.e. the *posterior probability*. The predicted class ($\hat{c}$) is the one which maximizes $\sigma_{c,\beta}^7$, i.e. $\hat{c} = \underset{c \in C}{\arg\max} \sigma_{c,\beta}(Z) = \underset{c \in C}{\arg\max} P(c|Z)$.

**Method 2: Naive Bayes** Naive Bayes is another method for binary classification. This method is based on the Bayes' Theorem, which we recall below:

**Theorem 1 (Bayes theorem)** *The posterior probability $P(H|E)$ of an hypothesis $H$ being true given an evidence $E$, can be computed from the prior probability of hypothesis being true $P(H)$, the probability of seeing the evidence $P(E)$ and the likelihood of the evidence given the hypoth-

<footnote n="7">7. The notation denotes a multiclass generalization, where $C$ is the set of classes and $\sigma_{c,\beta}$ is the logistic regression for the class $c \in C$.</footnote>
<figure><img src="image_12.png" /><figcaption>Figure 2.3 – Logit projects of two points of different classes</figcaption></figure>

esis P(E|H) as follows

$$P(H|E) = \frac{P(H) \cdot P(E|H)}{P(E)}$$

In this case, the classifier also selects the class which maximizes the posterior probability given a data point (Z). However, instead of directly computing the posterior probability of each class, this method used the Bayes' Theorem to switch to the analysis of *prior probabilities* and *likelihoods*.

$$\hat{c} = \arg\max_{c \in C} P(c|Z) = \arg\max_{c \in C} \frac{P(Z|c) \cdot P(c)}{P(Z)} \leftarrow \boxed{\text{Bayes' Theorem}}$$

Since the $P(Z)$ is constant independently of the class $c \in C$, the prediction of $\hat{c}$ can be simplified to:

$$\hat{c} = \arg\max_{c \in C} P(Z|c) \cdot P(c)$$

where $P(Z|c)$ is the likelihood of seeing $Z$ in $c$ and $P(c)$ is the probability of a random data point belonging to the class $c$.

Expanding the representation of $Z$ in the form of a feature vector $Z = \{z_1, \dots, z_n\}$, we have:

$$\hat{c} = \arg\max_{c \in C} P(z_1, \dots, z_n|c) \cdot P(c)$$
The naive assumption assumes that Z features are independent, and therefore $P(z_1, \cdots, z_n|c) = P(z_1|c) \cdots P(z_n|c)$. This simplified further the computation of the prediction to:

$$ \hat{c} = \arg\max_{c \in C} P(c) \prod_{i \in \{1, \cdots, n\}} P(z_i|c) $$

In Naive Bayes, the learning routine uses the training data to set up the probabilistic models that are used to compute each factor of $P(Z|c)$ and $P(c)$. This can be as simple as a frequency model, where:

$$ \begin{aligned} P(z_i|c) &= \frac{|\{z_i \in X, x \in C\}|}{|C|} \\ P(c) &= \frac{|C|}{\sum_{c_i \in C} |c_i|} \end{aligned} $$

Naive Bayes is a *generative classifier*, because it estimates the *prior probability* of $P(c)$ and the *likelihood* of $P(Z|c)$ for each class to select the one that maximizes the posterior probability of $\hat{c}$, instead of directly predicting the posterior probability for each class. Discussing limitations and optimizations of the Naive Bayes method is beyond the scope of this thesis.

**Method 3: Decision Trees** Decision Tree is a popular method used in multiclass classification. The classifier is organized in the form of a tree whose internal nodes (i.e. nodes that have children) represent classification criteria and leaves represent the prediction classes that fulfill all criteria accumulated in the path traversed all the way up to the root node.

Figure 2.4 shows a generic decision tree which includes four criterion with two conditions each (represented by $C_{i,j}$). If all criterion conditions are mutually exclusive and collectively exhaustive, the overall decision tree will also be so.

Given an example to be classified and conditions $\{C_{1,2}, C_{2,II}\}$, the prediction is Class II. Similarly, given conditions $\{C_{1,3}, C_{3,4}, C_{4,II}\}$ the prediction is Class II.

The learning routine is used to build the decision tree that better fits the training data by reducing the overall *impurity* or *entropy*. These measures are most commonly computed over a random variable Y which takes values $\{y_1, \cdots, y_n\}$, as follows:

$$ Gini(Y) = 1 - \sum_{i} P(y_i)^2 \qquad (\text{Gini Impurity}) $$
<figure><img src="image_13.png" /><figcaption>Figure 2.4 – Depiction of a generic decision tree.</figcaption></figure>

$$H(Y) = -\sum_{i} P(y_i) \log_{2}(P(y_i)) \quad (\text{Entropy})$$

A common fitting method starts by choosing the criterion that produces the minimal score (e.g. gini impurity or entropy) to be the root of the decision tree. Then, it gradually insert new levels in the tree by including new criteria such that the score of the overall tree is minimized as much as possible. For each path, if its score cannot be minimized by the inclusion of new criteria or if there is no criterion left to be included, the node splitting terminates. The final decision tree is the one for which there is no longer any node splitting to be done.

**Method 4: k-Nearest Neighbors** k-Nearest Neighbors (a.k.a. k-NN) is another method used for multiclass classification. Unlike the previous methods, k-NN requires the notion of distance between data points, thereby engendering the notion of coordinate points in a hyperspace.

During the learning phase, when parameter k is known the k-NN classifier does not need any kind of fitting, except on account of optimization. The training data contains a set of points {Pᵢ} and their corresponding classes, to which it is possible to create a mapping such that $C(Pᵢ) = cᵢ \in C$.

To predict the class of a unclassified data point Pₓ the k-NN classifier first finds the k closest (neighbor) points {P<sub>N₁</sub>, ..., P<sub>Nₖ</sub>} to Pₓ, i.e. $d(Pᵢ, Pₓ) \le d(Pⱼ, Pₓ), \forall i \in \{N₁, ..., Nₖ\} \land j \notin \{N₁, ..., Nₖ\}$. Then the prediction class is defined as the one which is the most present among
<figure><img src="image_14.png" /><figcaption>Figure 2.5 – Simple example of 1-NN with two points and their classification regions.</figcaption></figure>

the nearest neighbors {$P_{N_1}, \cdots, P_{N_K}$} of $P_x$, i.e.:

$$ \hat{c} = \arg\max_{c_i \in C} |\{\mathcal{C}(P_i) = c_i, i \in \{N_1, \cdots, N_K\}\}| $$

Since the prediction class depends exclusively on the location of a point in the hyper-plane, it is possible to define regions corresponding to the class predictions. Figure 2.5 depicts the simplest case, where $k = 1$ and the training data contains only {$P_1, P_2$}. The frontier that separates two regions is called *decision boundary*, since the prediction changes when the boundary is crossed.

In practice, most of the times the optimal value for $k$ is unknown, therefore the learning routine can test different values and choose the best one according to some given criteria. Further discussing special cases (e.g. tie in the number of leading classes among the $k$ nearest neighbors), limitations and optimizations of the $k$-NN method is beyond the scope of this thesis.

**Method 5: Neural Networks** Neural Networks (NN) refer to models used in different supervised learning applications (especially for multiclass classification), which are built from special mathematical functions (referred as *artificial neuron*) that mimic the operating mode of biological neurons.

An artificial neuron follows the subdivision of a biological neuron, which comprises three main parts:

- the *dendrites* (a.k.a *dendritic tree*), which allow the cell to receive signals from the upstream neuron and transmit it down to the body of the neuron;
<figure><img src="image_15.png" /><figcaption>Figure 2.6 – Mathematical model of a neuron (a.k.a artificial neuron).</figcaption></figure>

— the soma, which combines all the signals transmitted by the dendrites;

— and the axon, which is activated once a certain signal potential is reached, firing the transmission of a downstream signal.

Figure 2.6 shows the mathematical model of a neuron, and the respective subdivisions of a neuron cell that each part represents. The input values $x_1, \dots, x_n \in \{0, 1\}$ (that models the signals received by the dendrites) are multiplied by weights $w_1, \dots, w_m$ (that model the synaptic connection between neurons), then they go through an adder (that models the soma) and finally the output value $y$ is activated (i.e. $y = 1$) if the accumulated value goes beyond a threshold ($\tau$), otherwise nothing happens (i.e. $y = 0$).

Basically, the neuron is activated if $\sum_{i=1}^{m} w_i x_i > \tau$. It is possible to simplify the mathematical notation to remove the use of an explicit variable for the threshold by setting $x_0 = -1$ and $w_0 = \tau$, i.e.:

$$y = \varphi(\sum_{i=0}^{m} w_i x_i)$$

where $\varphi$ is known as the activation function, which is “activated” (i.e. outputs 1) if the input value is positive$^8$. Various activation functions can be chosen, depending on the properties

<footnote n="8">8. The magnitude of the output for the activation function in the immediate neighborhood around 0 varies</footnote>
sought in the application.

A Neural Network is composed of multiple neurons that can be interconnected in the most different ways, which is referred as the *architecture* of the neural network. They form an approximation function that fits an unknown function *f* given a limited set of images (*Y*) and preimages (*X*) thereof, i.e. $X = \{x^{[1]}, \dots, x^{[m]}\}$ and $Y = \{f(x^{[1]}), \dots, f(x^{[m]})\}$.

To measure how well the approximation succeeded in fitting the underlying function *f* (i.e. the learning performance) it is necessary to define an *objective function* that undergoes an optimization process for maximizing (or minimizing) it; the objective function is called *performance function* ($\mathcal{P}$) if the learning goal is to maximize it, otherwise it is called *loss function* ($\mathcal{L}$).

The *optimization function* depends on the prediction output of the neural network and the true value (i.e. $\hat{Y}$ and $Y$), while the prediction itself depends on $X$ and on the internal set of weights of the neural network ($W$). Therefore the loss function $\mathcal{L}$ and the performance function $\mathcal{P}$ are both functions of $X$, $W$ and $Y$.

A common method to minimize the *loss function* is the *Gradient Descent*—correspondingly, the analogous method for *performance function* maximization is called *Gradient Ascent*. It uses the geometric fact that the *gradient* of function ($F$) points towards its steepest descent, if $F$ is continuous and convex. Thus, in order to iteratively progress towards a local minimum of $F$, the *gradient descent* computes:

$$a_{n+1} = a_n - \gamma \nabla F(a_n) \qquad (\text{Gradient Descent})$$

where $\gamma$ is the *learning rate*. For an adequate value of $\gamma$, the computation of the gradient descent results in a monotonic sequence such that $F(a_0) \ge F(a_1) \ge F(a_2) \ge \dots$.

In the context of neural networks, gradient descent can be used in the training process to minimize the *loss function*. Each iteration of the learning process (referred as *epoch*) computes the gradient of the loss function with respect to $W$ so as to find the set of values that minimizes the prediction errors. This part of the training method is usually referred as *back-propagation*, because the prediction errors obtained with the values $W$ of the $i$-th epoch are used in the computation of new values for $W$ used in the $i+1$-th epoch, i.e.:

$$W_{[i+1]} = W_{[i]} + \gamma \nabla_W \mathcal{L}(X, W_{[i]}; Y).$$

<footnote>depending on its particular formulation.</footnote>
<figure><img src="image_16.png" /><figcaption>Figure 2.7 – Examples of underfitting, overfitting and optimal fitting.</figcaption></figure>

**Methodological Concerns of Supervised Learning**

Some issues in supervised learning are not particular to any singular method, they are in-
stead inherent to the bound between data and algorithm and thus being latent to any chosen
method. This section discusses the issues of overfitting, selection bias and cross-validation,
as they are pertinent to any supervised learning method.

**Underfitting & Overfitting** When a model is trained the goal is to set up its internal states so as to produce trustworthy predictions. Therefore, it is expected that a successfully trained model is able to 1) reproduce predictions of known data points —i.e. produce predictions that do not deviate too much from the expected results —and 2) produce good predictions for unknown data points, thus allowing the learning data to be generalized to unknown data.

Depending on the inner workings of the model, the trained model may come short in
reproducing predictions of known data or in producing good predictions for unknown data
(or both).

When the former case occurs the model *underfits* the data, since it fails to adequately
capture the underlying structure of the data. When the latter case occurs but the model is
nevertheless able to reproduce predictions of known data points (used in the training pro-
cess), the model *overfits* data. Overfitting occurs because the model is overly sensible to
residual variations (i.e. noise), thus it captures every slight deviation.

Figure 2.7 provides a visual representation of underfitting (on the left) and overfitting (on the right). For comparison, the figure also displays an optimal fitting (in the middle). It is possible to see that the underfitted model is unable to make correct predictions thus incur-
<figure><img src="image_17.png" /><figcaption>Figure 2.8 – Visual representation of selection bias.</figcaption></figure>

ring a high *bias* error. The overfitted model has lower bias error, however it is excessively
flexible in fitting the prediction function to the learning samples. Accordingly, intervals that
lack learning data produce poor predictions. Therefore, overfitted models generally suffer
from high *variance* error and cannot be generalizable to unknown data.

**Selection bias** Selection bias occurs when the learning data are not representative of the phenomena intended to be learnt and generalized. Since the data do not represent the general case, it carries an inherent bias error that spoils any attempt of learning from it.

Figure 2.8 shows the representation of a selection bias, where the population is misrep-
resented by the data points selected inside the red circle. Despite the majority of blue points
in the overall population, the most frequent color within in the selected population is gray.

**Cross-validation** The effectiveness of supervised learning substantially depends on the quality of the learning data. However, in practice data are often not available in the quantity and quality required to properly train the models. To cope with this problem, it is common to validate models using resampling methods. One of these methods is cross-validation.

Cross-validation is carried out in multiple rounds where the entire data corpus available
is partitioned into a learning and a validation sampling of the dataset. As the same data point
can fall in the learning sampling in one round and the validation sampling in another round,
there is no clear-cut distinction between learning and validation data when cross-validation
is used.
<figure><img src="image_18.png" /><figcaption>Figure 2.9 – Example of 5-fold cross validation.</figcaption></figure>

In each round, the model is trained from scratch using the round's learning sampling and then evaluated with the round's validation sampling. Since for a given round, none of the data in the validation sampling is used for learning, this avoids problems related to overfitting. Furthermore, since the selection of the learning and validation sampling is done randomly, problems related to selection bias are avoided. Once all the rounds are completed, the results of all evaluations are averaged in order to produce a final overall evaluation result.

A popular method is the *k*-fold *cross validation*. In this method, the data corpus is split in *k* chunks and a total of *k* training and evaluation rounds take place. At each round, one of the chunks is chosen as validation dataset, with the condition that it was not previously chosen, and the other *k* − 1 chunks are used to train the model. At the end, the *k* evaluation results are averaged to produce a single final result. Figure 2.9 shows an example of 5-fold cross validation.

### 2.2.3 Unsupervised Learning

The main goals and overall working principles of unsupervised learning were previously discussed; here we provide a more detailed presentation of this topic including the description of important methods and a methodological discussion.

#### Distance Metrics

All methods presented here are based on some metric which measures the similarity or dissimilarity between data points. This is actually necessary for the vast majority of existing clustering methods. The chosen distance metric largely influences the final result of the clustering methods.
The distance between x and y is denoted by $d(x, y)$ and must obey the fundamental prop- erties of metric spaces, i.e.:

$$ \text{— } d(x, y) = 0 \iff x = y $$

$$ \text{— } d(x, y) = d(y, x) $$

$$ \text{— } d(x, z) \le d(x, y) + d(y, z) $$

**Minkwoski Metric** Given two $n$-dimensional data points $x = (x_1, \cdots, x_n)$ and $y = (y_1, \cdots, y_n)$, the Minkowski metric is defined as [237]:

$$ d(x, y) = (\sum_{i} |x_i - y_i|^p)^{1/p} \qquad (\text{Minkowski metric}) $$

where $p \in \mathbb{N}^+$ is the order of the metric.

The most commonly used metrics are the Euclidean distance ($p = 2$), the Manhattan distance ($p = 1$) and the Chebyshev distance ($p \to \infty$).

## Methods of Unsupervised Learning

Here we provide a brief introduction of different clustering methods used for unsuper- vised learning.

**Hierarchical Methods** Hierarchical clustering methods operate in multiple iterations in which the elements are joined together—or split apart—forming new cluster configurations with one less—or one additional—cluster at each round, hence the hierarchical notion. The goal is to follow a greedy strategy in which the cluster configuration of the $n$-th iteration is evolved into the optimal configuration of the $n + 1$-th iteration through the merging of two clusters, or the splitting of a single cluster in two.

There are two main approaches for the hierarchical method: *agglomerative cluster*, which operates from the bottom up; and the *divisive cluster*, which operated from the top down.

The **agglomerative** approach starts by assigning each item to a cluster of a single element each (also known as *singleton*). It then proceeds by reducing the number of clusters by one at each iteration and by merging together the two most similar clusters.

Thereby, at each iteration a new hierarchical level is created. This continues as long as no cluster overruns the cut-off condition set as parameter —this value can be provided in terms of distance between elements of a cluster. Figure 2.10 shows a dendogram with the cut-off parameter set to 0.7, which results in two clusters (i.e. {$a, b$}, {$c, d, e$}).
The **divisive** approach is similar to the agglomerative, however instead of starting with
individual clusters, it starts with all elements as part of a unique cluster. Each iteration then
creates a new hierarchical level by selecting the pair of elements with highest dissimilarity
(say x₁ and x₂) when considering the most dissimilar pair of element in each cluster; the
cluster containing x₁ and x₂ is thus split into two new respective clusters, and the remaining
elements are moved into the closest one of the new clusters (i.e. considering their distance
wrt. x₁ or x₂).

<figure><img src="image_19.png" /><figcaption>Figure 2.10 – Example of a dendogram with cut-off set to 0.3.</figcaption></figure>

The measure of similarity or dissimilarity used in the merging/division process follows
the chosen *linkage* method. The *single-link* clustering considers the distance between two
clusters as the shortest distance between any two elements of both clusters. The *complete-link* considers the longest distance between any two members. The *average-link* considers the average of all distances between the elements of each cluster.

The main drawbacks of single-link and average-link are, respectively:

- Merging (or not splitting) two clusters due to outliers that are incidentally close (this is known as the *chaining effect* [237])

- Splitting of elongated clusters or merging of small clusters that surround elongated clusters.

In general, complete-linkage produces more compact clusters, whereas single-linkage
produces more versatile clusters. Another general drawback of hierarchical methods is their
complexity, which is too costly for medium and large datasets. For a set of *n* elements in
total, the time and memory complexity of the standard agglomerative clustering are $\mathcal{O}(n)$
and $\Omega(n^2)$, respectively. The time complexity of the divisive clustering is $\mathcal{O}(2^n)$ due to an
exhaustive search of the most dissimilar element for each iteration, which is overwhelmingly costly.

**Partitioning Methods** Partitioning methods arrange a set of elements into a pre-determined number of clusters. The goal is to maximize the similarity of elements within the same cluster, while being constraint to a pre-set number of clusters. The partition methods algorithms generally follow an error minimization strategy, in which the distances between the elements and the cluster representative points are computed to be as close as possible.

The most popular partition method is **K-Means**, where *K* represents the number of clusters pre-set by the user. For K-Means, a cluster representative point is its centroid, computed as the mean coordinate of all the elements in the cluster, i.e.:

$$ \mu_i = \frac{1}{|C_i|} \sum_j c_{i,j} \qquad (\text{Centroid of i-th cluster}) $$

where cluster $C_i = \{c_{i,0}, \cdots, c_{i,n}\}$.

In K-Means the goal is to find the optimal coordinates of *K* centroids. Once computed the optimal centroids, the *K* clusters are formed by assigning each element to the nearest cluster —measured as the distance between the element and each cluster centroid.

To find the optimal centroids, the naive version of K-means starts by randomly selecting an initial position for *K* reference centroids and then iterates through the following loop:

1. Assign each element to the cluster corresponding to the nearest centroid;

2. Recompute the centroid of each cluster, using the new computed values as the reference centroids in the next iteration.

In general, this loop iterates until the values of the reference centroids converge, i.e. when the new centroids recomputed in a new iteration are the same as the ones in the previous iteration. Other stop conditions can also be used, such as a pre-defined value for the number of iterations.

The time complexity of K-Means is $O(T \cdot K \cdot N \cdot M)$ [237], where *T* is number of loop iterations, *N* is the total number of elements and *M* is the number of features per element. Given the quick convergence of K-Means in practice, its complexity is roughly linear with respect to *N*. Efficiency is thus one of the main advantages of K-Means.

The two main drawbacks of K-Means are the requirement of pre-selecting a fixed number of clusters and its sensitivity to the selection of the initial reference centroids, which can
often converge to local rather than global minima. Furthermore, K-Means is also sensitive
to noisy data and outliers.

To cope with K-Means weaknesses many options for optimization exist, such as the Forgy
initialization [117] and K-Means++ [13], which target the initial centroid selection, to men-
tion just a few. There are also modifications of K-Means that use other representative values
for each cluster instead of the centroids, such as the Partition Around Medoids (PAM), which
uses medoids<fnref n="9" /> to represent clusters, or the K-Medians, which uses the median of the ele-
ments instead of the mean as centroid.

**Density Models** Density models analyze the surrounding regions of each element to identify whether the point has many neighbors within this nearby region, thus denoting that the element is located in a high density region, or whether it is the opposite, indicating that the element is located in a low density region. Elements belonging to the same high-density regions are included in the same cluster.

A popular density-based clustering algorithm is DBSCAN (Density-Based Spatial Clustering of Applications with Noise). The algorithm is given the parameters $\epsilon$ and *MinPts* that specify the radius of the nearby region and the minimal threshold for the number of points within a region, and it classifies the points $\{P_i\}$ as core points, (density)-reachable and outliers (or noise) as follows:

- $P_i$ is a *core point* if its nearby region of radius $\epsilon$ contains at least *MinPts* points (including $P_i$).

- $P_i$ is *directly reachable* from $P_j$ if $d(P_i, P_j) \le \epsilon$.

- $P_i$ is *reachable* from $P_j$ if for every point in $\mathcal{R} = \{P_k\} \cup \{P_i, P_j\}$ there is another directly reachable point in $\mathcal{R}$.

- $P_i$ is a *border point* if it is reachable from a core point but is not itself a core point.

- $P_i$ is a *noise point* if it is neither a *core point* nor a *reachable* points.

Figure 2.11 shows the analysis of $p_c$ (in blue), where the directly reachable points $P_{DR} = \{p_i : d(p_i, p_c) \le \epsilon\}$ (in red) are within the circle of radius $\epsilon$ (in blue) centered in $p_c$ and the remaining reachable points $P_R = \{p_i : \exists p_j \in \{p_c\} \cup P_{DR} : d(p_i, p_j) \le \epsilon\}$ (in green) are within the circles of radius $\epsilon$ centered in $P_{DR}$ (in dashed red lines). Noise points with respect to $p_c$, i.e. $P_N = \{p_i : \exists p_j \in \{p_c\} \cup P_{DR} \cup P_R : d(p_i, p_j) \le \epsilon\}$, are represented in gray color. If *MinPts*

<footnote n="9">9. The element of the cluster whose sum of dissimilarities to all other the elements in the cluster is minimal.</footnote>
<figure><img src="image_20.png" /><figcaption>Figure 2.11 – DBSCAN (reference: blue point): directly reachable points in red and ( indirectly ) reachable points in green.</figcaption></figure>

≤ 4, then p_c is classified as a core point, which also implies that the colored (i.e. not gray) points form a cluster.

The algorithm starts with the analysis of an arbitrary point to verify whether this point is a core point. If enough points are in its ε-neighborhood, a new cluster is started and all reachable points are included in this cluster; otherwise the point is tentatively marked as noise, as it can later be reachable by some cluster. The process continues until all density-connected points (hence clusters, depending on *MinPts*) are found. The pseudocode of DBSCAN is provided in algorithm 1 (page 307).

The complexity for the non-optimized implementation of DBSCAN is $O(n^2)$, because all
pairwise distances between the points have to be computed. If a distance matrix is used
—which takes $(n^2-n)/2$ distance computations to be built—DBSCAN runs in constant time
(i.e. $O(1)$), but takes $O(n^2)$ of memory, whereas the basic implementation takes only $O(n)$
of memory. It is possible to speed-up the computation using an indexing structure to find
the neighbors of a point in $O(\log n)$, which results in an overall complexity of $O(n\log n)$ for
DBSCAN.

The advantages of DBSCAN include:

* no need for specifying the number of clusters in advance;

* ability to find arbitrarily-shaped clusters;

* notion of noise points;

* robustness to outliers.

On the other hand, DBSCAN is non-deterministic because any border point that is reachable from multiple clusters is assigned to the first one formed during the execution of the algorithm, which follows a random order. Furthermore, having a single value for $\epsilon$ may not be an optimal fit depending on the profile of the dataset to be clustered.

DBSCAN is very sensitive to parameter settings. To reduce this sensitivity, OPTICS (Ordering Points To Identify the Clustering Structure) was proposed [9]. Instead of operating on a pre-fixed value for $\epsilon$ to form clusters as DBSCAN does, OPTICS uses $\epsilon$ as a “generating distance” to look for higher density regions and orders the points in such a way that the value for a cut-off parameter $\epsilon'$ ($0 \le \epsilon' \le \epsilon$) can be chosen to form clusters a posteriori.

To help defining OPTICS, let's define function $N_{\epsilon}(p)$, which returns all neighbors points of $p$ within distance $\epsilon$, and function $M_{\epsilon}(p, i)$, which given a point $p$ returns the distance of its i-th closest point within the $\epsilon$-neighborhood. OPTICS defines the concepts of core distance ($D_{core}$) and reachability distance ($D_{reach}$) as follows:

$$D_{core}^{\epsilon,MinPts-1}(p) = \begin{cases} \emptyset, & \text{, if } |N_{\epsilon}(p)| < MinPts \\ M_{\epsilon}(p, MinPts), & \text{, otherwise} \end{cases}$$

$$D_{reach}^{\epsilon,MinPts}(p_1, p_2) = \begin{cases} \emptyset, & \text{, if } |N_{\epsilon}(p)| < MinPts \\ \max(D_{core}^{\epsilon,MinPts}(p_1), d(p_1, p_2)), & \text{, otherwise} \end{cases}$$

To establish an ordering for the points, OPTICS processes each of them, finding their core-distance and their reachability-distance. For this, the main loop of the OPTICS algorithm proceeds as follows:

1. randomly visit a unprocessed point and verify whether it is a core point. If it is not a core point, it is marked as processed and the main loop restart;

2. iteratively collect density-reachable points in the $\epsilon$-neighborhood, mark them as processed and insert them in a seed-list;
<figure><img src="image_21.png" /><figcaption>Figure 2.12 – Example of a reachability plot and the corresponding clusters<fnref n="10" />.</figcaption></figure>

3. sort the points in the seed-list according to their reachability-distance to the closest core point;

Once completed the main loop, the order as well as a minimum reachability-distance for all the points are available. This allows drawing a reachability plot, where the y-axis contains values for the minimum reachability-distances and the x-axis simply contains the order of the points. Figure 2.12 shows an example of a reachability plot.

The final clusters can be formed by choosing any value for $\epsilon'$ ($0 \le \epsilon' \le \epsilon$) and checking which points mutually have minimum reachability-distances below this threshold. By construction, these points are together “in the valleys” of the reachability graph, as their are part

<footnote n="10">10. Image published at https://drek453711klr.cloudfront.net/rhys/Figures/fig18-6_alt.jpg (accessed October 2022)</footnote>
of the same seed-list and therefore density-reachable.

Although being a little less time-efficient than DBSCAN, the complexity of OPTICS does not change. Both algorithms are heavily dominated by the runtime of the $\epsilon$-neighborhood scanning. The original paper reports a ratio of 1.6x the runtime of DBSCAN for OPTICS [9].

## Evaluation of Unsupervised Learning

Unsupervised learning aims to analyze data based on their inner structure, which allows to reveal patterns that were not previously known. To validate the outcome of the learning, independently of the method chosen, it is required to evaluate the quality of the final clustering. This allows not only to measure the performance of a clustering instance, but also to compare different clusterings that use different methods, thus providing a means to choose the best method according to the topology of the data.

When the unsupervised learning analysis is supplemented with a test data for which the expected results (i.e. ground truth) are known, it is possible to measure scores that are ground-truth dependent—including the scores seen above in section 2.2.1 (page 60). Other evaluation methods take into account only the inner structure of the data; thus not requiring any ground-truth knowledge and being ready applicable to any kind of data partitioning.

**External Evaluation** For a given set of points $\Pi = \{p_1, \cdots, p_N\}$, the external evaluation requires the knowledge of a ground-truth for the clustered data. Notating this reference “golden standard” classes (i.e. ground truth) as $\mathcal{C} = \{C_1, \cdots, C_n\}$—such that $\cup \mathcal{C} = \Pi$ and $C_i \cap C_j = \emptyset$ for $i \neq j$—and the partitions obtained from clustering as $\mathcal{P} = \{P_1, \cdots, P_{n'}\}$—such that $\cup \mathcal{P} = \Pi$ and $P_i \cap P_j = \emptyset$ for $i \neq j$—we define some metrics used for external evaluation. For this, we define the class matching of a cluster $C_i \in \mathcal{C}$ as:

$$ \mathcal{M}(\mathcal{P}, C_i) = \{|P_j \cap C_i|, \forall j \in \{1, \cdots, n'\} \wedge P_j \in \mathcal{P}\} $$

Two commonly used external metrics to evaluate a clustering are *purity* and *entropy*, defined as follows [327]:

$$ P(\mathcal{C}, \mathcal{P}) = \frac{1}{|\Pi|} \sum_{C_i \in \mathcal{C}} \max(\mathcal{M}(\mathcal{P}, C_i)) \quad (\text{Purity}) $$

$$ H(\mathcal{C}, \mathcal{P}) = \sum_{C_i \in \mathcal{C}} \frac{|C_i|}{|\Pi|} H(C_i, \mathcal{P}) \quad (\text{Entropy}) $$
where the term $H(C_i, \mathcal{P})$ corresponds to the entropy of an individual cluster, which is computed as follows:

$$H(C_i, \mathcal{P}) = - \sum_{P_j \in \mathcal{P}} \frac{|C_i \cap P_j|}{|C_i|} \log_2 \left( \frac{|C_i \cap P_j|}{|C_i|} \right) \quad (\text{Entropy of a single cluster})$$

This entropy measure corresponds precisely to the entropy above (equation Entropy, page 68), where the probability terms $P(y_i)$ are replaced by the frequency of each class in the cluster (i.e. $|C_i \cap P_j|/|C_i|$).

Hypothetically, the quality of the clustering improves with the increment of the purity value. As for the entropy, clusterings with the lower entropy values are (hypothetically) better. The pitfall of these metrics is the fact that larger numbers of clusters facilitate having a high scores for purity and a low scores for entropy, as demonstrated by Uddin et al. [288].

A complementary notion related to entropy is the **mutual information** (MI), which measures the mutual dependence between two random variables. It is originated from the probability theory, but it can also be applied in clustering evaluation.

The MI quantifies the “amount of information” obtained about one random variable when the other random variable is observed. Therefore, for two random variables X and Y, the mutual information is defined as follows:

$$I(X, Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X, Y) \quad (\text{MI of random variables})$$

This definition can be expanded<fnref n="11" /> to:

$$I(X, Y) = \sum_{x \in X, y \in Y} p(x, y) \log_2 \left( \frac{p(x, y)}{p(x)p(y)} \right) \quad (\text{MI of random variables})$$

In the context of clustering evaluation, the same concept can be applied. In this case, the MI measures how much information the reference classes $\mathcal{C}$ and the clustering partitioning $\mathcal{P}$ have in common. Their MI is computed as follows:

$$I(\mathcal{C}, \mathcal{P}) = \sum_{C \in \mathcal{C}, P \in \mathcal{P}} \frac{|C \cap P|}{|\Pi|} \log_2 \left( \frac{|C \cap P|}{|C| |P|} \right) \quad (\text{MI - Clustering})$$

It is possible to normalize the MI value so as to limit the range within the interval from 0 to 1, which is referred as the **normalized mutual information** (NMI). The most used normalization was proposed by Kvalseth [153] and it consists in dividing $I(x, Y)$ by $1/2(H(X) +$

<footnote n="11">11. Details in appendix section 6.4 (page 308).</footnote>
$H(Y))^{12}$, i.e.:

$$NMI(X, Y) = \frac{2 \cdot I(X, Y)}{H(X) + H(Y)} \qquad (\text{Normalized Mutual Information})$$

Vihn et al. demonstrated that the measures of MI and NMI are biased towards the number of clusters, i.e. increasing the number of clusters results in better scores for MI and NMI. Therefore they propose a variation of the MI called adjusted mutual information (AMI) as follows:

$$AMI(X, Y) = \frac{I(X, Y) - \mathbb{E}\{I(X, Y)\}}{\max\{H(X), H(Y)\} - \mathbb{E}\{I(X, Y)\}} \qquad (\text{Adjusted Mutual Information})$$

where $\mathbb{E}\{I(X, Y)\}$ is the expected value of $I(X, Y)$. The AMI is in the range from 0 to 1, being equal 1 when the two clusterings are identical, and close to zero in case both clusterings are purely random. However, the AMI is not a metric as it does not satisfy the required properties (see section 2.2.3, page 74).

The V-measure is another popular entropy-based measure used for external evaluation [239]. Rosenberg and Hirschberg inspired from the F-score (equation 2.6, page 63) to propose the V-measure as the harmonic means of two complementary measures, i.e. homogeneity (h) and completeness (c):

$$V_{\beta} = \frac{1}{\left(\frac{\beta}{1+\beta}\right) c^{-1} + \left(\frac{1}{1+\beta}\right) h^{-1}} = \frac{(1+\beta)hc}{\beta h + c} \qquad (\text{V-score})$$

where $\beta$ is a weighted factor similar to the one in $F_{\beta}$, which gives more importance to completeness when $\beta > 1$ and more importance to homogeneity when $\beta < 1$<fnref n="13" />.

The homogeneity score measures the class distribution within each cluster, providing higher score when clusters contain elements of less classes —ideally a single class, where the homogeneity is maximal (= 1).

The authors consider how close a given clustering is to this ideal by examining the conditional entropy of the class distribution given the proposed clustering. In the perfectly homogeneous case, $H(\mathcal{C} | \mathcal{P}) = 0$. In an imperfect situation, the value is normalized by the maximum reduction in entropy the clustering information could provide, i.e. $H(\mathcal{C})$. Therefore the homogeneity is defined as:

<footnote n="12">12. Other variants also exist, refer to [293] for more information on about NMI.</footnote>

<footnote n="13">13. In contrast to the definition of $F_{\beta}$, Rosenberg and Hirschberg do not take into account the Van Rijsbergen's effectiveness measure, therefore the weighted factor is simply $\beta$ instead of $\beta^2$.</footnote>
$$h(\mathcal{C}, \mathcal{P}) = \begin{cases} 1, & \text{, if } H(\mathcal{C}, \mathcal{P}) = 0 \\ 1 - \frac{H(\mathcal{C}|\mathcal{P})}{H(\mathcal{C})}, & \text{, otherwise} \end{cases} \qquad (\text{homeogeneity})$$

The completeness score is symmetrical to the homogeneity score, but it considers the class distribution over all the clusters, providing higher score when the elements of the same class are member of less clusters —ideally a single cluster, where the completeness is maximal (= 1). Through a similar reasoning as above, the completeness score is defined as:

$$c(\mathcal{C}, \mathcal{P}) = \begin{cases} 1, & \text{, if } H(\mathcal{C}, \mathcal{P}) = 0 \\ 1 - \frac{H(\mathcal{P}|\mathcal{C})}{H(\mathcal{P})}, & \text{, otherwise} \end{cases} \qquad (\text{completeness})$$

**Internal Evaluation** For a given set of points $\Pi = \{p_1, \dots, p_N\}$ and a partitioning $\mathcal{P} = \{P_1, \dots, P_n\}$ —such that $\cup \mathcal{P} = \Pi$ and $P_i \cap P_j = \emptyset$ for $i \neq j$—the internal evaluation relies only on the information contained in the data about the internal structure of the partitioning.

The basic drive for internal measures is to have elements of the same cluster as similar as possible, while having elements of different clusters as distinct as possible. To this end, internal measures are often based on two criteria: *cohesion* and *separation*.

**Cohesion** measures how compact are the elements within a cluster. It is often based on the variance measures of the elements, where lower variance indicates better compactness. Another possibility is to base this measure on distances (maximum/average pairwise or maximum/average center-based distances).

**Separation** measures how distinct (or well-separated) is a cluster from another. It is often based on pairwise distances between cluster centers or pairwise minimum distances between elements in different clusters. This measure can also be based on the cluster density.

One of the first measures that combine both criteria was proposed by Joseph Dunn in 1974 and it is currently known as **Dunn's index** [77]. It is defined as the ratio of the smallest distance between clusters (i.e. separation) and the maximum cluster diameter (i.e. cohesion), being computed as follows:

$$DI(\mathcal{P}) = \frac{\min_{i \le i < j \le n} \delta(P_i, P_j)}{\max_{1 \le k \le m} \Delta(P_k)} \qquad (\text{Dunn's index})$$

where the distance between clusters $\delta(P_i, P_j)$ and the diameter of the cluster $\Delta(P_k)$ can be computed in different ways. The original proposition considers:
$$ \delta(P_i, P_j) = \min_{p_i \in P_i, p_j \in P_j} d(p_i, p_j) \qquad (2.7) $$

$$ \Delta(P_k) = \max_{p_i, p_j \in P_k} d(p_i, p_j) \qquad (2.8) $$

For $DI \to 0$, it follows that $\Delta(P_k) \gg \delta(P_i, P_j)$. It means that smaller values of $DI$ correspond to compact clusters and well-separated clusters. The weaknesses of Dunn's index are its time complexity and its sensitivity to outliers, as they can increase the diameter of clusters [116].

A popular measure for internal evaluation, which is more robust than Dunn's index, is the cluster **silhouette** [242]. It is a distance-based that ranges from -1 to +1, where higher values indicate higher similarity among elements of the same cluster (i.e. cohesion) and higher distinction with elements of other clusters (i.e. separation). The computation of the silhouette of a point $p_i \in \Pi$ such that $p_i \in P_\alpha$ ($\alpha \in \{1, \dots, n\}$) is composed of two factors, i.e the average dissimilarity of $P_i$ to all other points in $P_j$ and the minimum average dissimilarity of $p_i$ and $p \in \Pi \land p \notin P_j$, as follows:

$$ a(p_i) = \frac{1}{|P_\alpha| - 1} \sum_{p_j \in P_\alpha} d(p_i, p_j) \qquad (\text{avg. dissimilarity within cluster}) $$

$$ b(p_i) = \min_{P_j \in \mathcal{P} \setminus P_\alpha} \frac{1}{|P_\alpha|} \sum_{p_j \in P_j} d(p_i, p_j) \qquad (\text{min avg. dissimilarity with other clusters}) $$

A graphical representation of both factors is provided in figure 2.13. Once these factors have been obtained, the silhouette of point $p_i$ is defined as follows:

$$ s(p_i) = \begin{cases} \frac{b(p_i) - a(p_i)}{\max\{a(i), b(i)\}}, & \text{if } \max\{a(i), b(i)\} > 0 \\ 0, & \text{otherwise} \end{cases} \qquad (\text{silhouette}) $$

The factor $a(p_i)$ is not defined for singletons, therefore in this case the value for $s(p_i)$ is defined as 0. For $s(p_i) \to 1$, it follows that $b(p_i) \gg a(p_i)$; likewise, for $s(p_i) \to -1$, it follows $a(p_i) \gg b(p_i)$. The former case indicates that the cluster is compact and far from other clusters, whereas the latter indicates that the distances of elements in the same cluster are way bigger than the distance with points of another cluster.

It is possible to measure the silhouette score of a cluster by taking the mean silhouette
<figure><img src="image_22.png" /><figcaption>Figure 2.13 – Silhouette of point $p_i$: depiction of factors $a(p_i)$ and $b(p_i)$.</figcaption></figure>

value of the points that it contains. The silhouette coefficient is defined as the mean silhouette over all elements.

## 2.3 Malware Analysis

Malware can have many forms, including malicious scripts, fileless malware, to name but a few. However, in this thesis we are interested only in malware in the form of binary executable files (as depicted in figure 2.14). Therefore we start this section with a review of topics related to the analysis of binary files —insofar as it is useful in malware analysis —before providing a literature review on topics of malware analysis and introducing the concept of malware analysis primitives.
<figure><img src="image_23.png" /><figcaption>Figure 2.14 – Thesis scope: Malware Analysis of Binary Files</figcaption></figure>

2.3.1 Binary Analysis

Binary analysis refers to the analysis of *machine code* that can be executed by a CPU,
given the right architecture and external dependencies (e.g. operating system, DLL, etc). In
the overwhelming majority of the cases, the analysis has access only to the malware in the
form of a (executable) binary file without the corresponding source code, hence the interest
for binary analysis.

Syntax and Semantics

When analyzing machine code (or any code) two dimensions can be to considered: syn-
tax and semantics. Syntax concerns the rules guiding the formation of the code, which in-
cludes the available instructions and their grammatical relations. Semantics concerns the
meaning of a sequence of instructions —more precisely its *teleological function*, as discussed
in section 1.2.2 (page 34) —often simply referred as the *functionality*.

Computer programs (be they malware or not) have to adhere to the syntax rules of the
target platform to execute. A central task in malware analysis involves the analysis of un-
known programs (typically through reverse-engineering) in order to evaluate their level of
maliciousness.

There is an intrinsic bound between syntax and semantics, as two program instances
with similar syntax are likely to have similar semantics. Nonetheless, two program instances
with very different syntax can still have the same semantics—which is a fact largely exploited
by malware authors so as to preclude analysis and keep their programs undetectable.
<figure><img src="image_24.png" /><figcaption>Figure 2.15 – Extended compilation process as depicted in [119]</figcaption></figure>

Syntax is stiff, thus easy to analyze (specially by computers). Therefore syntax-based analysis is generally efficient and precise. However, as adversaries can circumvent this analysis through semantics-preserving transformations (i.e., not changing the program functionality), the Achilles heel of this approach is its robustness.

Semantics is flexible, therefore harder to model and analyze. Semantic-based analysis is generally less efficient and more prone to higher variance; however it is harder circumvent, hence more robust.

## Compilation Process

As a general rule, machine code is produced by a *compilation process* to which a *source code* is given as input, and an object file is generated as output. Different object files are then linked together to form the binary (executable) program.

Ul Haq and Caballero detail the transformation of source code into machine code in their *extended compilation process* [119]. This extended definition is convenient because it considers semantics-preserving transformations along the compilation, which are not very usual in regular compilation processes but are indeed very frequent for malware.

Semantics-preserving transformations for malware are typically *obfuscations* intended to hamper the reverse-engineering analysis of the binary code. They can take place before compilation, altering the source code to produce a new transformed (e.g. obfuscated) version of the original source code, or after, altering the binary program to produce a new transformed (e.g. obfuscated) version of the original program. Source code transformations are platform-safe but dependent on the programming language of the source code, whereas binary code transformations are independent from the programming language but specific to the target platform.
<figure><img src="image_25.png" /><figcaption>Figure 2.16 – Stages of a typical compilation process (i.e. three-stage compiler).</figcaption></figure>

**Intermediate Language (IL)** In general, the compilation process does not transform high-level code directly into low-level code. Instead, the compiler first transforms high-level code into an *intermediate representation* (e.g. AST, intermediate language), which is then transformed into low-level code (as shown in figure 2.16) that is translated into machine code.

By using an intermediate representation, the compiler can attain a separation of concerns: the compiler front-end checks the syntax and semantics of the high-level language, whereas the compiler back-end optimizes and produces the code of the specific targeted CPU architecture. This allows to simplify optimization at each stage of the compilation process.

Intermediate representations also facilitate the portability of source codes on multiple platforms, since they breaks the one-to-one dependency between high-level and low-level languages —otherwise, for a given language, a full native compiler would be necessary for each targeted CPU architecture.

The overwhelming majority of programming frameworks, including the main ones, benefit from intermediate languages: Microsoft's *Common Intermediate Language* (CIL) is used to support dozens of languages (including C#, C++, PowerShell) on multiple architectures; the very popular GNU Compiler Collection (GCC) [269], which supports multiple languages such as C, C++, Objective-C and Go, using GENERIC [186] as its intermediate language; Clang, which is also a very popular front-end and is the main competitor of GCC [146], uses LLVM intermediate language to support C, C++ and Objective-C compilation [159].