Dynamic Taint Analysis in a Polyglot Virtual Machine

Jacob Kreindl

Abstract

Dynamic taint analysis is a popular program analysis technique which detects whether values from specific sources in the program under analysis propagate to specific sinks at run time. To enable such detection, the analysis taints values which originate from these so-called taint sources by decorating them with a taint label. The analysis then dynamically propagates these labels when the program under analysis derives new values from tainted ones. Thus, when the program under analysis uses a value at a taint sink, the analysis can determine whether that value originated from a taint source. With various adaptations, this generic program analysis technique has been applied in diverse fields such as program vulnerability detection and mitigation, software testing and debugging, program comprehension, and reverse engineering. Dynamic taint analysis has been implemented for various programming languages, for certain intermediate representations, and for native code. Some of these implementations even allow one to adapt certain analysis properties in order to serve as a basis for implementing new applications of dynamic taint analysis. Despite the large body of existing work on dynamic taint analysis, current implementations exhibit several limitations. In our research, which we present here, we resolve these limitations by exploiting the capabilities of virtual machines and managed runtimes. We implemented our ideas in TruffleTaint, a new dynamic taint analysis platform which is based on GraalVM.

The first limitation we address in our research is the restricted language support of current dynamic taint analysis platforms. Modern programs are often implemented in more than one programming language and thus often transfer data between code of different languages. These language interactions typically also occur between code in a high-level dynamic language, such as JavaScript, and code in a low-level representation such as native code. However, current dynamic taint analysis platforms typically target only a single programming language or program representation and thus fail to support such polyglot programs. GraalVM is a high-performance virtual machine (including an optimizing dynamic Just-In-Time compiler), which can execute polyglot programs using various interoperable language runtimes that are based on a common framework. We similarly designed TruffleTaint as a language-agnostic core framework with languagespecific front-ends. The core framework contains language-agnostic strategies to taint runtime values. Individual front-ends implement taint analysis with language-level semantics based on these strategies. Hence, TruffleTaint can propagate taint at source-level both in multiple languages and across language boundaries. Our prototype implementation targets JavaScript, Python, and LLVM IR, which is a low-level program representation into which, e.g., C/C++ code can be compiled. We evaluated TruffleTaint using an extensive test suite as well as JavaScript, Python, C/C++, and polyglot implementations of selected Shootouts benchmarks, which we augmented with taint sources and sinks such that they propagate tainted values as part of their main workload. Our evaluation shows that TruffleTaint is able to correctly propagate tainted values in each of these tests and benchmarks, which demonstrates TruffleTaint’s ability to propagate taint both in diverse languages and across language boundaries.

The second limitation we address is the performance overhead which dynamic taint analysis imposes on instrumented programs. Performance overhead is a general issue of dynamic taint analysis; even heavily optimized implementations slow down program execution by factors up to ~6x. Previous approaches to address this limitation, e.g., used separate static analysis to reduce the amount of run-time taint propagation or manually applied platform-specific low-level optimizations. Our approach, in contrast, leverages managed runtimes’ ability to dynamically compile frequently executed code at run time and to speculatively apply compiler optimizations such as constant propagation when they do so. In our approach, we observe run-time taint propagation in order to derive speculative assumptions, which we then direct the compiler to use when it compiles TruffleTaint’s instrumentation code. These assumptions enable additional opportunities for applying compiler optimizations, which replaces costly run-time taint propagation with comparatively cheap run-time checks for the continued validity of our assumptions. We also developed various kinds of shadow memory, e.g., for objects of high-level dynamic languages and for ranges of byte-addressable native memory of lower-level programming languages, and we use speculative optimizations for accessing them. Our evaluation shows that TruffleTaint exhibits an average peak performance slowdown of only ~1.89x on implementations of the Shootouts benchmarks in JavaScript and/or C/C++, with individual slowdowns ranging from 0x to ~5.06x. TruffleTaint performs similarly well on some SPECint 2017 benchmarks. We also found that TruffleTaint can outperform state-ofthe- art related work when the analyzed programs never actually operate on tainted data. In this case, our optimizations enable GraalVM’s JIT compiler to completely eliminate taint propagation from compiled code.

The third limitation we address is the limited adaptability of current dynamic taint analysis platforms. While some implementations of dynamic taint analysis are adaptable in principle, they are typically still limited with respect to which analysis properties can be adapted, to which degree these properties can be adapted, and how these adaptations may be specified. For example, some implementations support only specific taint label representations so that they can implement taint propagation more efficiently. However, such limitations can render the analysis platform unsuitable for certain applications of dynamic taint analysis. To lift such limitations, we developed label-defined dynamic taint analysis, a new scheme for specifying the properties of dynamic taint analysis. In this scheme, taint labels can specify how, when, and where they should be propagated by implementing the functions of a common interface for taint labels. Whenever a tainted value is used, the analysis platforms invokes these functions in order to make required analysis decisions. We show that label-defined dynamic taint analysis supports specifying any analysis property, including taint sources, propagation semantics, taint sinks, and taint sink actions, in detail. As such, it allows engineers to implement traditional dynamic taint analysis applications such as simple taint tracking between specific functions which act as taint sources and taint sinks, or recording the path of taint propagation when doing so. Moreover, label-defined dynamic taint analysis allows for advanced analysis specifications, which, e.g., compose separately specified analysis components or which instrument other label-defined dynamic taint analyses. For example, we used this capability to implement an analysis-independent profiling infrastructure for dynamic taint propagation. Our approach to dynamic taint analysis specification is by design languageagnostic with respect to both the programs under analysis and the analysis specification itself. We also integrated label-defined dynamic taint analysis with GraalVM’s extensive language support and its language-agnostic debugging infrastructure in order to provide a rich development environment for analysis specification. Finally, label-defined dynamic taint analysis is amenable to common optimizations for object-oriented programming languages on virtual machines. Our performance evaluation shows that label-defined dynamic taint analyses can reach performance similar to equivalent engine-integrated ones. As a result, label-defined dynamic taint analysis shows that advanced adaptability need not require a significant performance sacrifice for simpler analysis specifications and, thus, that the responsibility of trading off performance for advanced analysis complexity need not be made at the platform level.

Kurzfassung

Dynamische Taint Analyse ist eine populäre Programmanalysetechnik, die erkennt, ob zur Laufzeit Werte von bestimmten Quellpositionen in einem Programm zu bestimmten Zielpositionen (Senken) dieses Programms propagiert werden. Dazu markiert (tainted) die AnalyseWerte, die von sogenannten Taintquellen stammen, indem sie sie mit einem Taint Label versieht. Wenn zur Laufzeit neue Werte aus getainteten Werten abgeleitet werden, propagiert die Analyse die Taint Labels auf diese neuen Werte. Wenn ein Wert in einer Taintsenke verwendet wird, kann die Analyse somit feststellen, ob dieserWert aus einer Taintquelle stammt oder von einem solchen Wert abgeleitet wurde. Diese generische Programmanalysetechnik wird, mit verschiedenen Anpassungen, zu unterschiedlichen Zwecken verwendet, z. B. zur Erkennung und Behebung von Verwundbarkeiten, zum Testen und Debuggen von Software, und zum Reverse Engineering. Die dynamische Taint Analyse wurde in der Literatur für verschiedene Programmiersprachen, für verschiedene Zwischendarstellungen von Programmen und für Maschinencode beschrieben. Einige dieser Implementierungen erlauben auch die Anpassung bestimmter Analyseeigenschaften, wodurch sie als Grundlage für die Implementierung neuer Anwendungen der dynamischen Taint Analyse dienen können. Obwohl es bereits viele Implementierungen dieser Art gibt, weisen sie doch gewisse Einschränkungen auf. In unserer Forschung, die wir hier vorstellen, nutzen wir die Fähigkeiten von virtuellen Maschinen und verwalteten Laufzeitsystemen (Managed Runtimes) um diese Einschränkungen zu beseitigen. Wir haben unsere Ideen in TruffleTaint umgesetzt, einer neuen Plattform für dynamische Taint Analyse, die auf GraalVM basiert.

Zunächst widmen wir uns der Einschränkung, dass dynamische Taint Analysen üblicherweise nur eine Sprache oder Programmrepräsentation unterstützen. Moderne Programme sind oft in mehr als einer Programmiersprache implementiert und tauschen daher oft Daten zwischen verschiedenen Sprachen aus, typischerweise auch zwischen dynamischen Hochsprachen wie JavaScript und Zwischensprachen oder Maschinencode. Aktuelle Plattformen für dynamische Taint Analyse unterstützen aber generell nur eine einzige Programmiersprache oder Programmrepräsentation, und daher keine mehrsprachigen Programme. GraalVM ist eine hochleistungsfähige virtuelle Maschine mit einem optimierenden dynamischen Just-In-Time-Compiler, die mehrsprachige Programme mittels interoperabler Ausführungsumgebungen ausführen kann, die auf einem gemeinsamen Framework basieren. Wir haben TruffleTaint ebenso als ein sprachunabhängiges Kern- Framework mit separaten sprachspezifischen Frontends entworfen. Das Kern-Framework enthält sprachunabhängige Strategien, um Laufzeitwerte zu tainten, womit individuelle Frontends Taint Analyse mit Semantik auf Sprachebene implementieren. Dadurch kann TruffleTaint Taint sowohl in mehreren Sprachen propagieren, als auch über Sprachgrenzen hinweg. Unsere prototypische Implementierung unterstützt JavaScript, Python und LLVM IR, eine Zwischendarstellung, in die z.B. C/C++-Code kompiliert werden kann. Wir haben TruffleTaint mit einer umfangreichen Testsuite sowie mit JavaScript-, Python-, C/C++- und mehrsprachigen Implementierungen ausgewählter Shootouts-Benchmarks evaluiert, die wir mit Taintquellen und -senken erweitert haben, sodass sie als Teil ihrer Hauptarbeitslast getaintete Werte verwenden. Unsere Auswertung zeigt, dass TruffleTaint in der Lage ist, Taint Labels in jedem dieser Tests und Benchmarks korrekt zu propagieren, was seine Fähigkeit demonstriert, Taint in mehreren Sprachen und über Sprachgrenzen zu propagieren.

Das zweite Problem, dem wir uns widmen, ist der Laufzeit-Overhead, der durch dynamische Taint Analyse entsteht. Dieser Overhead ist ein generelles Problem der dynamischen Taint Analyse; selbst stark optimierte Implementierungen verlangsamen die Programmausführung um Faktoren von bis zu ~6x. Bisherige Ansätze zur Lösung dieses Problems verwenden etwa zusätzliche statische Analyse, um Taint Propagierung zur Laufzeit zu reduzieren, oder optimieren die Taint Analyse manuell für eine bestimmte Hardware-Plattform. Unser Ansatz nutzt hingegen die Fähigkeit von Laufzeitsystemen, häufig ausgeführten Code dynamisch zu kompilieren und dabei spekulativ Compiler- Optimierungen wie partielle Evaluierung durchzuführen. In unserem Ansatz beobachten wir Taint Propagierung zur Laufzeit, um zusätzliche Annahmen für den Compiler zu erstellen. Durch diese Annahmen kann der Compiler spekulativ zusätzliche Optimierungen auf TruffleTaints Instrumentierungscode anwenden und Taint Propagierung zur Laufzeit kann durch vergleichsweise effiziente Checks für die weitere Gültigkeit unserer Annahmen ersetzt werden.Wir haben außerdem verschiedene Arten von Schattenspeicher entwickelt, etwa für Objekte von dynamischen Hochsprachen, und wir verwenden spekulative Optimierungstechniken entwickelt, um effizient darauf zugreifen zu können. Unsere Evaluierung zeigt, dass TruffleTaint die Ausführung der Shootouts-Benchmarks in JavaScript und/oder C/C++ um einen durchschnittlichen Faktor von nur ~1.89x verlangsamt, wobei dieser Faktor bei einzelnen Benchmarks zwischen 0x und ~5.06x liegt. TruffleTaint schneidet auch bei einigen SPECint 2017-Benchmarks ähnlich gut ab. Weiterhin haben wir festgestellt, dass TruffleTaint den aktuellen Stand der Technik übertreffen kann, wenn die analysierten Programme nie mit getainteten Daten arbeiten. In diesem Fall ermöglicht unser Optimierungsansatz dem JIT-Compiler, die Taint-Propagierung völlig zu eliminieren.

Das dritte Problem, dem wir uns widmen, ist die begrenzte Anpassbarkeit dynamischer Taint-Analyse-Plattformen. Während bei einigen dieser Plattformen verschiedene Analyseeigenschaften angepasst werden können, gibt es doch gewisse Einschränkungen, welche Eigenschaften angepasst werden können, in welchem Maße sie angepasst werden können und wie diese Anpassungen spezifiziert werden können. Beispielsweise unterstützen manche Plattformen nur eine begrenzte Anzahl an verschiedenen Taint Labels, um Taint Propagierung effizienter implementieren zu können. Solche Einschränkungen können jedoch die Analyseplattform für bestimmte Anwendungen der dynamischen Taint Analyse ungeeignet machen. Um solche Einschränkungen zu vermeiden, haben wir labeldefinierte dynamische Taint Analyse entwickelt, ein neues Schema zur Spezifikation der Eigenschaften einer dynamischen Taint Analyse. In diesem Schema können Taint Labels angeben, wie, wann und wo sie propagiert werden sollen, indem sie die Funktionen einer klar definierten Schnittstelle für Taint Labels implementieren. Wann immer ein getainteter Wert verwendet wird, ruft die Analyseplattform diese Funktionen auf, um die erforderlichen Entscheidungen zur Taint Propagierung zu treffen. Wir zeigen, dass die labeldefinierte dynamische Taint Analyse die detaillierte Spezifikation jeder Eigenschaft dieser Analysetechnik, bestehend aus Taintquellen, Semantik der Taint Propagierung, Taintsenken und Reaktionen beim Eintreffen von getaintetenWerten bei Taintsenken, unterstützt. Dies ermöglicht es Entwicklern, traditionelle Anwendungen von dynamischer Taint Analyse zu implementieren, wie z.B. die einfache Verfolgung von Werten zwischen spezifischen Funktionen, die als Taintquellen und Taintsenken fungieren, oder die Aufzeichnung des Pfades der Werte zwischen diesen Funktionen. Darüber hinaus erlaubt die labeldefinierte dynamische Taint Analyse komplexere Analysespezifikationen, welche z.B. separat spezifizierte Analyseeigenschaften verbinden oder andere labeldefinierte dynamische Taint Analysen instrumentieren. Wir haben diese Fähigkeit beispielsweise genutzt, um eine analyseunabhängige Profiling-Infrastruktur für dynamische Taint Propagierung zu implementieren. Unser Ansatz zur Spezifikation dynamischer Taint Analysen ist sprachunabhängig, sowohl in Bezug auf die zu analysierenden Programme als auch auf die Analysespezifikation selbst. Wir haben die labeldefinierte dynamische Taint Analyse außerdem mit der umfangreichen Sprachunterstützung von GraalVM und deren sprachunabhängigen Debugging-Infrastruktur integriert, um eine vielseitige Entwicklungsumgebung für die Analysespezifikation zu schaffen.Weiterhin kann die labeldefinierte dynamische Taint Analyse von gängigen Optimierungsstrategien für objektorientierte Programmiersprachen auf virtuellen Maschinen profitieren. Unsere Leistungsevaluierung zeigt, dass labeldefinierte dynamische Taint Analysen eine ähnliche Leistung wie äquivalente plattformintegrierte Analysen erreichen können. Dadurch zeigt die labeldefinierte dynamische Taint Analyse, dass tiefgreifende Anpassungsfähigkeit keine signifikanten Leistungseinbußen für einfachere Analysespezifikationen erfordern muss, und damit auch, dass die Entscheidung zwischen Leistung und Analysekomplexität nicht auf der Plattformebene getroffen werden muss.

PhD thesis, Johannes Kepler University Linz, November 2024