Completed Thesis Projects

The battle of developing hardware Trojans and corresponding countermeasures has taken adversaries towards ingenious ways of compromising hardware designs by circumventing even advanced testing and verification methods. Besides conventional methods of inserting Trojans into a design by a malicious entity, the design flow for field-programmable gate arrays (FPGAs) can also be surreptitiously compromised to assist the attacker to perform a successful malfunctioning or information leakage attack. This thesis mainly focuses on the two aspects of hardware Trojans in reconfigurable systems, the defenders perspective which corresponds to the bitstream-level Trojan detection technique, and the attackers perspective which corresponds to a novel FPGA Trojan attack. From the defender's perspective, we introduce a first-ever successful pre-configuration countermeasure against the ``Malicious LUT''-hardware Trojan, by employing bitstream-level Proof-Carrying Hardware (PCH) and present the complete design-and-verification flow for iCE40 FPGAs. Likewise, from an attackers perspective, we present a novel attack that leverages malicious routing of the inserted Trojan circuit to acquire a dormant state even in the generated and transmitted bitstream. Since the Trojan is injected in a post-synthesis step and remains unconnected in the bitstream, the presented attack can currently neither be prevented by conventional testing and verification methods nor by bitstream-level verification techniques.

Die bisherige Forschung zu Proof-Carrying Hardware (PCH) hat dessen Machbarkeit und Nützlichkeit gezeigt und einen Ansatz zur Zertifizierung der funktionalen Äquivalenz zu einer Spezifikation geliefert, jedoch ohne PCH mit aktuellen Erkenntnissen, Methoden oder Werkzeugen formaler Hardwareverifikation zu verknüpfen. Aufgrund der Komplexität moderner Schaltungen und Verifikationsherausforderungen wie der Zustandsexplosion bei sequentiellen Schaltungen, limitiert diese Einschränkung sofort verfügbarer Verifikationslösungen die Anwendbarkeit des Ansatzes in einem größeren Kontext signifikant. Diese Dissertation schließt die Lücke zwischen PCH und modernen Entwicklungen in der Schaltungsverifikation und stellt Methoden und Werkzeuge zur Verfügung, welche die Zertifizierung einer großen Bandbreite von Schaltungseigenschaften ermöglicht; sowohl funktionale, als auch nicht-funktionale. Überdies werden erstmals Prototypen vorgestellt in welchen Schaltungen mittels PCH verifiziert werden, die auf tatsächlicher rekonfigurierbarer Hardware realisiert sind. Dank dieser Ergebnisse können Entwickler PCH zur Herstellung von Vertrauen in weit komplexere Schaltungen verwenden, unter Zuhilfenahme einer größeren Vielfalt von Eigenschaften, welche durch moderne, effiziente Spezifikationstechniken ausgedrückt werden können.

Traditionelle Cachedesigns verwenden konsolidierte Blöcke von Speicheradressbits um einen Cachesatz zu indizieren, vergleichbar mit der Anwendung einer Modulofunktion. Obwohl dieses modulobasierte Abbildungsschema in heutigen Cachestrukturen weit verbreitet ist, vor allem wegen seiner einfachen Anforderungen an das Hardwaredesign und seiner Effizienz für die Indizierung eufeinanderfolgender Speicheradressen, kann seine Verwendung für eine Vielzahl von Anwendungsdomänen mit unterschiedlichen Charakteristiken zu suboptimalen Ergebnissen führen. Diese Dissertation präsentiert einen neuen Typ von Cacheabbildungsschema, motiviert durch die Kombination programmierbarer Ressourcen mit der naturinspirierten Optimierung rekonfigurierbarer Hardware. Im Fokus dieser Forschung steht eine FPGA-basierte Cachestruktur für den first level Cache einer Mehrkernprozessorarchitektur, welche die Cacheindizierung dynamisch ändern kann. Um die Herausforderung rekonfigurierbarer Cacheabbildungen zu lösen, wird eine reprogrammierbare Boolesche Schaltung eingeführt, die auf Look-up Table (LUT) Speicherelementen basiert. Weiterhin wird eine Infrastruktur zur Effizienzmessung eingeführt, welche die zugrundeliege Mikroarchitektur überwachen kann, sowie eine adaptive Evaluationsstrategie präsentiert, die evolutionäre Algorithmen wirksam einsetzt, und die nicht nur anwendungsspezifische Abbildungen von Speicheradressen zu Cacheindizes für level one Caches evolvieren sondern dabei auch die Optimierungszeiten reduzieren kann. All diese Aspekte zusammen in einer prototypischen Implementierung auf einem FPGA für einen LEON3/Linux-basierten Mehrkernprozessor zeigen, dass evolvierbare Cacheabbildungsfunktionen Cache Misses reduzieren, sowie die Effizienz im Vergleich zu konventionellen Caches erhöhen können.

The use of heterogeneous computing resources, such as graphics processing units or other specialized co-processors, has become widespread in recent years because of their performance and energy efficiency advantages. Operating system approaches that are limited to optimizing CPU usage are no longer sufficient for the efficient utilization of systems that comprise diverse resource types. Enabling task preemption on these architectures and migration of tasks between different resource types at run-time is not only key to improving the performance and energy consumption but also to enabling automatic scheduling methods for heterogeneous compute nodes. This thesis proposes novel techniques for run-time management of heterogeneous resources and enabling tasks to migrate between diverse hardware. It provides fundamental work towards future operating systems by discussing implications, limitations, and chances of the heterogeneity and introducing solutions for energy- and performance-efficient run-time systems. Scheduling methods to utilize heterogeneous systems by the use of a centralized scheduler are presented that show benefits over existing approaches in varying case studies.

Monte-Carlo Tree Search (MCTS) is a class of simulation-based search algorithms. It brought about great success in the past few years regarding the evaluation of deterministic two-player games such as the Asian board game Go. In this thesis, we present a parallelization of the most popular MCTS variant for large HPC compute clusters that efficiently shares a single game tree representation in a distributed memory environment and scales up to 128 compute nodes and 2048 cores. It is hereby one of the most powerful MCTS parallelizations to date. In order to measure the impact of our parallelization on the search quality and remain comparable to the most advanced MCTS implementations to date, we implemented it in a state-of-the-art Go engine Gomorra, making it competitive with the strongest Go programs in the world. We further present an empirical comparison of different Bayesian ranking systems when being used for predicting expert moves for the game of Go and introduce a novel technique for automated detection and analysis of evaluation uncertainties that show up during MCTS searches.

Handling run-time dynamics on embedded system-on-chip architectures has become more challenging over the years. On the one hand, the impact of workload and physical dynamics on the system behavior has dramatically increased. On the other hand, embedded architectures have become more complex as they have evolved from single-processor systems over multi-processor systems to hybrid multi-core platforms.Static design-time techniques no longer provide suitable solutions to deal with the run-time dynamics of today's embedded systems. Therefore, system designers have to apply run-time solutions, which have hardly been investigated for hybrid multi-core platforms.In this thesis, we present fundamental work in the new area of run-time management on hybrid multi-core platforms. We propose a novel architecture, a self-adaptive hybrid multi-core system, that combines heterogeneous processors, reconfigurable hardware cores, and monitoring cores on a single chip. Using self-adaptation on thread-level, our hybrid multi-core systems can effectively perform performance and thermal management autonomously at run-time.

Reconfigurable circuit devices have opened up a fundamentally new way of creating adaptable systems. Combined with artificial evolution, reconfigurable circuits allow an elegant adaptation approach to compensating for changes in the distribution of input data, computational resource errors, and variations in resource requirements. Referred to as ``Evolvable Hardware'' (EHW), this paradigm has yielded astonishing results for traditional engineering challenges and has discovered intriguing design principles, which have not yet been seen in conventional engineering. In this thesis, we present new and fundamental work on Evolvable Hardware motivated by the insight that Evolvable Hardware needs to compensate for events with different change rates. To solve the challenge of different adaptation speeds, we propose a unified adaptation approach based on multi-objective evolution, evolving and propagating candidate solutions that are diverse in objectives that may experience radical changes. Focusing on algorithmic aspects, we enable Cartesian Genetic Programming (CGP) model, which we are using to encode Boolean circuits, for multi-objective optimization by introducing a meaningful recombination operator. We improve the scalability of CGP by objectives scaling, periodization of local- and global-search algorithms, and the automatic acquisition and reuse of subfunctions using age- and cone-based techniques. We validate our methods on the applications of adaptation of hardware classifiers to resource changes, recognition of muscular signals for prosthesis control and optimization of processor caches.

FPGAs, System on Chips und eingebettete Systeme sind heutzutage kaum mehr wegzudenken. Sie kombinieren die Rechenleistung von spezialisierter Hardware mit einer Software-ähnlichen Flexibilität. Zur Laufzeit können sie ihre Funktionalität anpassen, indem sie online neue Hardware Module beziehen und deren Funktionalität integrieren. Mit der Leistung wachsen auch die Anforderungen an rekonfigurierbare Hardware. Ihr Einsatz in immer sicherheitskritischeren Szenarien erfordert neue Wege um Sicherheit zu gewährleisten, da ein Versagen der Sicherheit gravierende Folgen mit sich bringt. Neben finanziellen Verlusten sind auch der Verlust von Menschenleben oder Einbußen in der nationalen Sicherheit denkbar. In dieser Arbeit stelle ich das neue und wegweisende Konzept der beweistragenden Hardware vor. Es ist eine Methode zur Verifizierung von Eigenschaften von Hardware Modulen um die Sicherheit der Zielplatformen zur Laufzeit zu garantieren. Der Produzent eines Hardware Moduls liefert, basierend auf den Sicherheitsbestimmungen des Konsumenten, einen Beweis der Sicherheit mit dem Rekonfigurierungsbitstrom. Die aufwendige Berechnung des Beweises steht im Kontrast zu der vergleichsweise unaufwendigen Überprüfung durch den Konsumenten. Ich präsentiere einen Prototypen basierend auf Open Source Werkzeugen und einer eigenen abstrakten FPGA Architektur samt Bitstromformat. Den Nachweis über die Nutzbarkeit von beweistragender Hardware erbringt die Evaluierung des Prototypen zur beispielhaften Anwendung der Sicherung von kombinatorischer und begrenzt sequenzieller Äquivalenz von Referenzmonitor-Modulen zur Speichersicherheit.

The paradigm shift towards many-core parallelism is accompanied by two fundamental questions: how should the many processors on a single die communicate to each other and what are suitable programming models for these novel architectures? In this thesis, the author tackles both questions by reviewing the reconfigurable mesh model of massively parallel computation for many-cores. The book presents the design, implementation and evaluation of a many-core architecture that is based on the execution principles and communication infrastructure of the reconfigurable mesh. This work fundamentally rests on FPGA implementations and shows that reconfigurable mesh processors with hundreds of autonomous cores are feasible. Several case studies demonstrate the effectiveness of programming and illustrate why the reconfigurable mesh is a promising model for many-cores.