Structure-based anomaly detection and clustering

Anomaly detection is a challenging problem encountered across various application domains, including healthcare, manufacturing, and cybersecurity. Numerous statistical methods have been proposed in the literature, each relying on specific assumptions about the data being analyzed. Many of these approaches are unsupervised, where anomalies are identified as samples that deviate from the expected patterns based on the underlying assumptions. This thesis presents new unsupervised solutions for the anomaly detection problem in two different settings. In the first part of the thesis, we address anomaly detection from the general perspective of identifying samples that do not conform to structured patterns. In this case, we focus on the scenario where genuine data can be described by low-dimensional manifolds, while anomalous data cannot and are therefore unstructured. Our main contribution to the research on structure-based anomaly detection is Preference Isolation Forest (PIF), a novel anomaly detection framework that combines the advantages of adaptive isolation-based methods with the flexibility of Preference Embedding. The main intuition is to embed the data into a high-dimensional Preference Space, by fitting a collection of low-dimensional manifolds, and to identify anomalies as the most isolated points within this space. We propose two different approaches to identify isolated points: Voronoi-IForest, which leverages on suitable distances between preferences to build an ensemble of isolation trees, and RuzHash-IForest, which exploits a Locality Sensitive Hashing (LSH) scheme to avoid the explicit computation of distances, hence reducing the computational complexity of the framework. Furthermore, we propose a sliding window-based extension of PIF, namely Sliding-PIF, which leverages a locality prior to address situations where the global nature of the low-dimensional manifolds is unknown, enabling anomaly detection when only local information is available. Experiments on both synthetic and real-world datasets demonstrate that PIF successfully discriminates between structured and unstructured data, and favorably compares with state-of-the-art anomaly detection techniques. We extend our work to a scenario closely related to structure-based anomaly detection, namely structure-based clustering. In structure-based clustering, the focus is on recovering individual genuine structures rather than identifying anomalies, which are usually detected as a byproduct of the structures recovery process. In the literature, structure recovery is typically addressed for the single-family scenario, where individual genuine structures can be described by a specific model family, whereas the multi-family structure recovery scenario has been much less investigated. We propose MultiLink, a novel structure-based clustering algorithm that simultaneously deals with multiple families of models in datasets contaminated by noise and outliers. In particular, MultiLink considers geometric structures defined by a mixture of underlying parametric models, and tackle the structure recovery problem by means of preference analysis and clustering. MultiLink combines on-the-fly model fitting and model selection in a novel linkage scheme that determines whether two clusters are to be merged. The resulting method features many practical advantages over traditional preference based methods, being faster, less sensitive to the inlier threshold, and able to compensate limitations deriving from initial models sampling. Experiments on several public datasets show that MultiLink performs competitively with state-of-the-art alternatives, both in single-family and multi-family problems. In the second part of the thesis, we focus on the more traditional setting of detecting anomalies as samples that lie in low-density regions, namely density-based anomaly detection. We start by addressing the challenging scenario where data comes as an endless stream that may exhibit dynamic behavior, and anomalies must therefore be detected in an online way. Anomaly detection literature is abundant with offline methods, which require repeated access to data in memory, and impose impractical assumptions when applied to a streaming context. Existing online anomaly detection methods generally fail to address these constraints, resorting to periodic retraining to adapt to the online context. We propose Online-IForest, a novel method explicitly designed for streaming conditions that seamlessly tracks the data generating process as it evolves over time. Online-IForest models the data distribution using an ensemble of multi-resolution histograms that track point counts within their bins, incorporating a dynamic mechanism to adjust histograms resolution and incrementally adapt to the data generating process. Experimental validation on real-world datasets demonstrate that Online-IForest is on par with online alternatives and closely rivals state-of-the-art offline anomaly detection techniques that undergo periodic retraining. Notably, Online-IForest consistently outperforms all competitors in terms of efficiency, making it a promising solution for applications where fast identification of anomalies is of primary importance such as cybersecurity, fraud and fault detection. Finally, we address a relevant anomaly detection problem in the industrial scenario, specifically the cybersecurity challenge of identifying new malware families. Classifying a malware into its respective family is essential for building effective defence against cyber threats, enabling cybersecurity organizations to detect, respond to, and mitigate malicious activities more efficiently. However, the steady emergence of new malware families makes it difficult to acquire a comprehensive training set that encompasses all classes needed for training machine learning models. Therefore, a robust malware classification system should accurately categorize known classes while also being able to detect new ones, an anomaly detection challenge referred to in the literature as open-set recognition. We propose, for the first time, to combine a tree-based Gradient Boosting classifier, which is effective in classifying high-dimensional data extracted from Android manifest file permissions, to an open-set recognition technique developed within the computer vision community, namely MaxLogit. Our approach can be seamlessly applied to a classification pipeline based on boosted decision trees, without even affecting the classification workflow. Experiments on public and private real-world datasets demonstrate the potential of our method, which has been deployed in Cleafy’s business environment and is currently part of their engine.

Il rilevamento delle anomalie è un problema complesso che si riscontra in diversi domini applicativi, tra cui sanità, produzione manifatturiera e cybersecurity. Numerosi metodi statistici sono stati proposti in letteratura, ciascuno basato su specifiche assunzioni sui dati analizzati. Molti di questi approcci sono non supervisionati, in cui le anomalie vengono identificate come campioni che deviano dai modelli attesi in base alle assunzioni sottostanti. Questa tesi presenta nuove soluzioni non supervisionate per il problema del rilevamento delle anomalie in due contesti differenti. Nella prima parte della tesi, affrontiamo il rilevamento delle anomalie dal punto di vista generale dell’identificazione di campioni che non rispettano schemi strutturati, denominato structure-based anomaly detection. In questo caso, ci concentriamo sullo scenario in cui i dati genuini possono essere descritti da varietà di bassa dimensionalità, mentre i dati anomali no e sono quindi non strutturati. Il nostro principale contributo alla ricerca sul rilevamento delle anomalie basato sulle strutture è Preference Isolation Forest (PIF), un nuovo framework che combina i vantaggi dei metodi adattivi di isolamento con la flessibilità del Preference Embedding. L'intuizione principale è quella di incorporare i dati in uno spazio di preferenze ad alta dimensionalità, adottando una collezione di varietà di bassa dimensionalità, e identificare le anomalie come i punti più isolati all'interno di questo spazio. Proponiamo due approcci per identificare i punti isolati: Voronoi-IForest, che sfrutta opportune distanze tra preferenze per costruire un insieme di alberi di isolamento, e RuzHash-IForest, che utilizza uno schema di Locality Sensitive Hashing (LSH) per evitare il calcolo esplicito delle distanze, riducendo così la complessità computazionale del framework. Inoltre, proponiamo un'estensione basata su finestra scorrevole di PIF, denominata Sliding-PIF, che sfrutta un criterio di località per affrontare situazioni in cui la natura globale delle varietà di bassa dimensionalità è sconosciuta, consentendo il rilevamento delle anomalie anche quando è disponibile solo informazione locale. Esperimenti su dataset sintetici e reali dimostrano che PIF distingue con successo tra dati strutturati e non strutturati e si confronta favorevolmente con tecniche dello stato dell'arte nel rilevamento di anomalie. Estendiamo il nostro lavoro a uno scenario strettamente legato al rilevamento delle anomalie basato sulle strutture, ovvero il clustering basato sulle strutture, denominato structure-based clustering. In questo caso, l'obiettivo è recuperare le singole strutture genuine piuttosto che identificare anomalie, le quali vengono solitamente rilevate come sottoprodotto del processo di recupero delle strutture. In letteratura, il recupero delle strutture viene tipicamente affrontato nello scenario single-family, dove ogni struttura genuina può essere descritta da una specifica famiglia di modelli, mentre lo scenario multi-family è stato molto meno esplorato. Proponiamo MultiLink, un nuovo algoritmo di structure-based clustering che gestisce contemporaneamente più famiglie di modelli in dataset contaminati da rumore e outlier. In particolare, MultiLink considera strutture geometriche definite da una combinazione di modelli parametrici sottostanti e affronta il problema del recupero delle strutture attraverso l’analisi delle preferenze e il clustering. MultiLink combina il fitting e la selezione dei modelli in tempo reale in un nuovo schema di linkage che determina se due cluster devono essere uniti. Il metodo risultante presenta numerosi vantaggi pratici rispetto ai metodi basati sulle preferenze tradizionali, essendo più veloce, meno sensibile alla soglia degli inlier e in grado di compensare limitazioni derivanti dal campionamento iniziale dei modelli. Esperimenti su diversi dataset pubblici dimostrano che MultiLink è competitivo con alternative dello stato dell'arte, sia in scenari single-family che multi-family. Nella seconda parte della tesi, ci concentriamo sul contesto più tradizionale di rilevamento delle anomalie basato sulla densità, denominato density-based anomaly detection, in cui le anomalie sono campioni che si trovano in regioni a bassa densità. Affrontiamo il difficile scenario in cui i dati arrivano come un flusso continuo che può presentare un comportamento dinamico, e le anomalie devono quindi essere rilevate in tempo reale. La letteratura sul rilevamento delle anomalie è ricca di metodi offline, che richiedono accesso ripetuto ai dati in memoria e impongono assunzioni poco pratiche nel contesto dello streaming. I metodi online esistenti generalmente non riescono a gestire queste limitazioni, affidandosi a riaddestramenti periodici per adattarsi al contesto online. Proponiamo Online-IForest, un nuovo metodo progettato esplicitamente per le condizioni di streaming, in grado di monitorare il processo generativo dei dati mentre evolve nel tempo. Online-IForest modella la distribuzione dei dati utilizzando un insieme di istogrammi multi-risoluzione che tengono traccia del conteggio dei punti all'interno dei loro bin, incorporando un meccanismo dinamico per regolare la risoluzione degli istogrammi e adattarsi incrementamente al flusso dei dati. Esperimenti su dataset reali dimostrano che Online-IForest è competitivo con le alternative online e si avvicina ai metodi offline dello stato dell'arte, senza bisogno di riaddestramenti periodici. In particolare, Online-IForest supera costantemente tutti i concorrenti in termini di efficienza, rendendolo una soluzione promettente per applicazioni in cui l’identificazione rapida delle anomalie è di primaria importanza, come la cybersecurity, la rilevazione di frodi ed il rilevamento di guasti. Infine, affrontiamo un problema rilevante nel contesto industriale, in particolare la sfida della cybersecurity nell’identificare nuove famiglie di malware. Classificare un malware nella sua famiglia di appartenenza è essenziale per costruire difese efficaci contro le minacce informatiche, consentendo alle organizzazioni di rilevare, rispondere e mitigare le attività dannose in modo più efficiente. Tuttavia, la continua comparsa di nuove famiglie di malware rende difficile ottenere un dataset di addestramento completo che includa tutte le classi necessarie per i modelli di machine learning. Pertanto, un sistema di classificazione robusto dovrebbe essere in grado di categorizzare accuratamente le classi note, ma anche di rilevare nuove classi, un problema di rilevamento delle anomalie noto in letteratura come open-set recognition. Proponiamo per la prima volta di combinare un classificatore basato su Gradient Boosting, efficace nella classificazione di dati ad alta dimensionalità estratti dai permessi del manifest file di Android, con una tecnica di open-set recognition sviluppata nella comunità della computer vision, chiamata MaxLogit. Il nostro approccio può essere integrato senza problemi in una pipeline di classificazione basata su alberi decisionali, senza alterare il flusso della classificazione. Esperimenti su dataset pubblici e privati dimostrano il potenziale del nostro metodo, che è stato implementato nell'ambiente aziendale di Cleafy ed è attualmente parte integrante del loro motore di rilevamento delle minacce informatiche.