BlindStitch: Direct thread interleaving control for concurrency fuzzing of stripped binaries

Multithreaded programs are those pieces of software which organize tasks so to be runnable in parallel, unfortunately adding a considerable layer of complexity, increasing the possibility of introducing errors. Data race conditions are a category of concurrency bugs coming from the mismanagement of the communication between threads inside multithreaded programs, they lead to memory corruption potentially causing crashes or security breaches. During the years researchers have developed approaches to help finding race conditions, some integrated in the compilation pipeline, others aimed to check binaries. Some binaries are distributed as statically linked monolithic binaries stripped out of all symbols. Symbols, if available, ease investigation effort since they hint to semantic meaning of sections of binary. Fuzzing is a well-established technique for automatically discovering software vulnerabilities by giving programs unexpected inputs. Some recent works tried adding race condition vulnerability discovery to fuzzing, but their approaches are not optimal since they still rely on the operating system to manage threads, adding nondeterministic behavior to the target program execution undermining testing performance. This thesis presents a direct approach on concurrency fuzzing, where thread management is being emulated inside a modified version of QEMU user mode, and the interleaving is directly controlled based on a "a priori" determined schedule. This allows for exploring the interleaving space of the target program in a deterministic directed manner and to find race condition bugs independently from the realization of crashes. In addition to the main goal, we define a behavior based approach on understanding the semantic of program variables, allowing to find synchronization primitives to better direct interleaving space exploration and to enable smarter race detection. In conclusion, this thesis presents a direct and deterministic solution for detecting race conditions in multithreaded applications, contributing in the field of software testing and security. Future work includes researching for efficient interleaving exploration algorithms and integrate with static analysis techniques to help refining target bug research scope.

I programmi multithread sono software che organizzano lavori eseguendoli in parallelo, aggiungendo, però, un livello di complessità aumentando la possibilità di errori. Problemi noti come "data races" sono una categoria di errori di esecuzione concorrente scaturiti dalla malagestione della esecuzione parallela, e possono corrompere la memoria causando crash e brecce di sicurezza. Negli anni, ricercatori hanno sviluppato approcci per trovare questi problemi, alcuni integrati nella catena di compilazione, altri con lo scopo di controllare precompilati. Alcuni binari vengono distribuiti come monolitici integrando librerie e spogliati dei simboli; che, quando disponibili, aiutano l'investigazione permettendo di comprendere la funzionalità di sezioni di esso. Il Fuzzing è una nota tecnica per trovare vulnerabilità in maniera automatica dando al programma in prova dati in ingresso abnormi. Alcuni lavori recenti hanno provato ad aggiungere la ricerca di data races ai fuzzer, ma molti dei loro approcci si basano sul sistema operativo rendendoli non ottimali, visto che questo aggiunge un comportamento non deterministico all'esecuzione. Questa tesi propone un approccio diretto al fuzzing di esecuzione concorrente, dove la gestione dei flussi di esecuzione viene emulata mediante una versione modificata di QEMU user, e l'interscambio viene controllato da una scaletta impostata a priori. Questo permette di esplorare le possibili esecuzioni del programma in prova in maniera diretta e deterministica e di trovare problemi di esecuzione concorrente indipendentemente dalla loro manifestazione in crash. Inoltre, definiamo un approccio comportamentale per comprendere la semantica di variabili al fine di trovare primitive di sincronizzazione aiutando detta esplorazione. Concludendo, questa tesi presenta una soluzione diretta e deterministica per la ricerca di problemi di esecuzione concorrente in programmi multithread, contribuendo al campo del software testing e della security. Lavori futuri includono la ricerca di algoritmi di esplorazione dell'interscambio più efficienti, e di integrare tecniche di analisi statica per aiutare a concentrare la ricerca di problemi su porzioni di binario interessanti.