DSI2: Identifizieren dynamischer Datenstrukturen durch Beobachtung von Programmabläufen

• Antragsteller: Professor Dr. Gerald Lüttgen
• Fachliche Zuordnung: Softwaretechnik und Programmiersprachen
• Förderung: Förderung von 2014 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 242347041

Dieses Projekt entwickelt neuartige Techniken und Tools zur automatischen und zuverlässigen Identifizierung dynamischer Datenstrukturen in Softwareprogrammen, basierend auf einer Analyse von Programmausführungen. Aufgrund der Vielfalt und Komplexität von Implementierungsstilen in realer Software, wie bspw. bei der zyklischen, doppelt-verketteten Liste des Linux-Kernels, ist dies eine große Herausforderung. Eine derartige Programmanalyse kann für die Program Comprehension (z.B. zum besseren Verständnis von Legacy Code), die formale Programmverifikation (z.B. zur automatischen Generierung von Verifikationsaussagen) oder das Reverse Engineering (z.B. zur Malware-Analyse) eingesetzt werden.Seit Juni 2014 entwickeln und evaluieren wir das Softwarewerkzeug "Data Structure Investigator" (DSI), welches den Stand der Wissenschaft in zweierlei Hinsicht verbessert. Zum einen verwendet DSI eine fortschrittliche Speicherabstraktion, die den zahlreichen Implementierungsvarianten von Datenstrukturen in C-Code, einschl. maßgeschneiderter Speicherallokatoren und architekturspezifischer Optimierungen, genügt. Da Operationen auf Datenstrukturen deren tatsächliche Form temporär kaschieren, verwendet DSI zum anderen einen auf Indizien basierten Ansatz, der degenerierte Formen toleriert. Zusätzlich haben wir DSI erfolgreich prototypisch eingesetzt: Für die Program Comprehension haben wir ein Visualisierungstool entwickelt, um listenbasierte Datenstrukturen verständlich zu machen. Für die Programmverifikation mit dem Tool VeriFast haben wir einen Generator für Verifikationsaussagen gebaut, der DSIs Output zur automatischen Synthese einfacher Aussagen über C-Programme, wie bspw. Form-Invarianzen, verwendet. Für das Reverse Engineering haben wir DSI mit dem externen Typinferenztool Howard und Intels Instrumentierungsframework PIN gekoppelt, um einfache Komponenten von Malware zu analysieren.Ausgehend von unseren Prototypen wird das hier beantragte Folgeprojekt DSIs Anwendbarkeit in drei Richtungen signifikant erweitern. Erstens soll der DSI-Ansatz für die Analyse reichhaltigerer Strukturen (z.B. balancierte Bäume und komplexe Verschachtelungen) und von Payload Data (z.B. sortierte Listen und Bäume) vertieft werden. Zweitens soll DSI für das Reverse Engineering und die Analyse von Malware weiterentwickelt werden, was neuartige Typinferenzen auf Binärcode und die Entwicklung eines DSI Plug-ins für den populären IDA Pro-Disassembler und -Debugger erfordert; zudem soll die Eignung von DSIs Analyse-Output zur Verbesserung von Malware-Signaturen und -Klassifizierungen geprüft werden. Drittens soll das VeriFast Plug-in neu konzipiert werden, um die zahlreichen in der Praxis vorkommenden C-Implementierungsstile behandeln zu können. Das verbesserte DSI-Tool soll durch reale Fallstudien evaluiert und zudem der Fachöffentlichkeit zugänglich gemacht werden.

• DFG-Verfahren: Sachbeihilfen