Automated vulnerability analysis is an extremely active area of research, posing several challenges to the research community, and ultimately driven by a set of different techniques. Among them, Dynamic Symbolic Execution (DSE) stands out, providing extensive crash replayability and semantic insight. However, scaling DSE analysis to complex binaries is difficult, and virtually all currently proposed methods fall short on the state explosion problem. There have been attempts to survive path explosion (e.g., prioritizing promising paths or merging paths when the situation is appropriate); still, in general, this challenge to pure DSE engines is not yet surmounted, and most bugs discovered by such systems are shallow. We propose a novel approach to the problem: a smart triaging system that leverages machine learning techniques to replicate the expertise of a human analyst and lead to vulnerable paths discovery. Our approach uses the \texttt{angr} symbolic execution engine to monitor the execution of traces in vulnerable programs and extract relevant features (executed code, reachable code, relationships between variables, symbolic path constraints). After learning patterns from the extracted set of features, models are used to predict interesting execution paths in new programs. We evaluated our approach on the Cyber Grand Challenge (CGC) dataset, showing that the knowledge collected from the analysis of vulnerable traces, without any explicit prior knowledge on vulnerability patterns, is transferrable to unseen binaries, and leads to outperforming prior work in path prioritization by triggering more (and different) vulnerabilities.
L'analisi automatica di sistemi software è un campo di ricerca estremamente attivo, che presenta molteplici sfide per la comunità scientifica, ed è in ultima analisi guidato da un ristretto insieme di tecniche. Tra queste tecniche risalta in particolare l'esecuzione dinamica/simbolica (Dynamic Symbolic Execution, o DSE), che offre un delicato equilibrio tra riproducibilità e controllo semantico. Un sistema DSE emula l'esecuzione del programma utilizzando dei valori simbolici. Ogni volta che incontra una condizione, se entrambi i rami sono raggiungibili, l'esecuzione si divide e segue entrambe le tracce. Questo porta però ad una scalabilità estremamente limitata, dovuta al problema della "path explosion": dal momento che ogni condizione risulta nella creazione di due differenti tracce d'esecuzione, il numero di tracce aumenta esponenzialmente all'aumentare del numero di condizioni. Di conseguenza, questo tipo di analisi deve limitare l'esplorazione ad una parte del programma, in base alla quantità di tempo e risorse disponibili. Le soluzioni formalizzate per mitigare il problema della path explosion sono distinguibili in quattro categorie: hybrid fuzzing, esecuzione under-constrained, unione delle tracce d'esecuzione e prioritizzazione. Il nostro lavoro si concentra sulle tecniche di prioritizzazione. Infatti, le tecniche ad oggi proposte sono progettate per trovare uno specifico tipo di vulnerabilità (si veda ad esempio la tecnica loop-exhaustion, limitata alle vulnerabilità dovute ad un buffer sottodimensionato), questo le porta ad identificare solo uno spettro limitato e superficiale di vulnerabilità, rendendole incapaci di riconoscere ogni altro pattern potenzialmente vulnerabile. SyML nasce dall'esigenza di sviluppare una soluzione più sofisticata e generale al problema della path explosion. In particolare, questa tesi esplora l'efficacia di tecniche innovative per la prioritizzazione nella DSE, basate sull'apprendimento di pattern vulnerabili. Si basa sull'intuizione che, spesso, due tracce d'esecuzione distinte ma vulnerabili presentano pattern di programmazione ricorrenti (ad esempio specifiche funzioni di input/output, oppure specifiche sequenze di istruzioni), che possono essere riassunti da un insieme limitato di features. Un algoritmo di machine learning può a questo punto ragionare su questo insieme di dati, identificare dei buoni indicatori per un path vulnerabile, e quindi fornire previsioni accurate su nuovi programmi. Queste previsioni vengono poi usate per guidare l'esecuzione verso tracce più interessanti, permettendo infine di riconoscere vulnerabilità complesse. Al fine di validare le performance del nostro approccio, abbiamo implementato alcune tecniche note dallo stato dell'arte e confrontato i risultati dell'esplorazione. Abbiamo poi validato la nostra tecnica sul dataset della Cyber Grand Challenge (CGC), mostrando che la conoscenza raccolta dall'analisi di tracce vulnerabili è trasferibile ad altri programmi - sconosciuti al classificatore. I risultati ottenuti sono superiori rispetto a qualsiasi altro approccio dallo stato dell'arte, con un maggior numero ed un più ampio spettro di vulnerabilità riconosciute.
Towards advanced path prioritization in symbolic execution
RUARO, NICOLA
2019/2020
Abstract
Automated vulnerability analysis is an extremely active area of research, posing several challenges to the research community, and ultimately driven by a set of different techniques. Among them, Dynamic Symbolic Execution (DSE) stands out, providing extensive crash replayability and semantic insight. However, scaling DSE analysis to complex binaries is difficult, and virtually all currently proposed methods fall short on the state explosion problem. There have been attempts to survive path explosion (e.g., prioritizing promising paths or merging paths when the situation is appropriate); still, in general, this challenge to pure DSE engines is not yet surmounted, and most bugs discovered by such systems are shallow. We propose a novel approach to the problem: a smart triaging system that leverages machine learning techniques to replicate the expertise of a human analyst and lead to vulnerable paths discovery. Our approach uses the \texttt{angr} symbolic execution engine to monitor the execution of traces in vulnerable programs and extract relevant features (executed code, reachable code, relationships between variables, symbolic path constraints). After learning patterns from the extracted set of features, models are used to predict interesting execution paths in new programs. We evaluated our approach on the Cyber Grand Challenge (CGC) dataset, showing that the knowledge collected from the analysis of vulnerable traces, without any explicit prior knowledge on vulnerability patterns, is transferrable to unseen binaries, and leads to outperforming prior work in path prioritization by triggering more (and different) vulnerabilities.File | Dimensione | Formato | |
---|---|---|---|
thesis-ruaro-nicola.pdf
non accessibile
Descrizione: Thesis
Dimensione
2.54 MB
Formato
Adobe PDF
|
2.54 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/152245