Der vierte Band der wissenschaftlichen Schriftenreihe Eingebettete Selbstorganisierende Systeme widmet sich der Entwicklung von Fehlermodellen für eingebettete, verteilte Multi – Prozessorsysteme. Diese werden zu einem hierarchischen Netzwerk zur Steuerung von Flugzeugen (Avionik) verbunden und mehr und mehr im Automotive Bereich eingesetzt. Hier gilt es höchste Sicherheitsstandards einzuhalten und maximale Verfügbarkeit zu garantieren. Herr Fischer integriert die Modellierung von möglichen Fehlern in den Entwurfsprozess. Auf Grundlage des π-Kalküls entwickelt Herr Fischer ein formales Fehlermodell, das eine einheitliche Modellierung von Fehlerfällen unterstützt. Dabei werden interessante Bezüge zur Bi-Simulation sowie zu Methoden des Modell Checkings hergestellt. Die theoretischen Ergebnisse werden an einem komplexen Beispiel anschaulich illustriert. So kann der Leser die Mächtigkeit des entwickelten Ansatzes nachvollziehen und wird motiviert, die entwickelte Methodik auf weitere Anwendungsfälle zu übertragen. / The 4th volume of the scientific series Eingebettete, selbstorganisierende Systeme (Embedded Self-Organized Systems) outlines the design of fault models for embedded distributed multi processor systems. These multi processor systems will be connected to a hierarchical network to control airplanes (avionics) and also be used more and more in the automotive area. Here it is essential to meet highest safety standards and to ensure the maximum of availability. Mr Fischer integrates the modelling of potential faults into the design process. Based on the pi-calculus, he develops a formal framework, which supports a standardised modelling of faults. Thereby, interesting connections to the Bi-Simulation as well as to methods of the Model checking are established. The theoretical results are depicted on a complex example. So it is possible for the reader to understand the complexity of this approach and is motivated to use the developed methodology in other applications. I am glad that Mr Fischer publishes his important research in this scientific series.

Event Stream Processing (ESP) is a well-established approach for low-latency data processing enabling users to quickly react to relevant situations in soft real-time. In order to cope with the sheer amount of data being generated each day and to cope with fluctuating workloads originating from data sources such as Twitter and Facebook, such systems must be highly scalable and elastic. Hence, ESP systems are typically long running applications deployed on several hundreds of nodes in either dedicated data-centers or cloud environments such as Amazon EC2. In such environments, nodes are likely to fail due to software aging, process or hardware errors whereas the unbounded stream of data asks for continuous processing. In order to cope with node failures, several fault tolerance approaches have been proposed in literature. Active replication and rollback recovery-based on checkpointing and in-memory logging (upstream backup) are two commonly used approaches in order to cope with such failures in the context of ESP systems. However, these approaches suffer either from a high resource footprint, low throughput or unresponsiveness due to long recovery times. Moreover, in order to recover applications in a precise manner using exactly once semantics, the use of deterministic execution is required which adds another layer of complexity and overhead. The goal of this thesis is to lower the overhead for fault tolerance in ESP systems. We first present StreamMine3G, our ESP system we built entirely from scratch in order to study and evaluate novel approaches for fault tolerance and elasticity. We then present an approach to reduce the overhead of deterministic execution by using a weak, epoch-based rather than strict ordering scheme for commutative and tumbling windowed operators that allows applications to recover precisely using active or passive replication. Since most applications are running in cloud environments nowadays, we furthermore propose an approach to increase the system availability by efficiently utilizing spare but paid resources for fault tolerance. Finally, in order to free users from the burden of choosing the correct fault tolerance scheme for their applications that guarantees the desired recovery time while still saving resources, we present a controller-based approach that adapts fault tolerance at runtime. We furthermore showcase the applicability of our StreamMine3G approach using real world applications and examples.

Technological advances drive hardware to ever smaller feature sizes, causing devices to become more vulnerable to transient faults. Applications can be protected against faults by adding error detection and recovery measures in software. This is popularly achieved by applying automatic program transformations. However, transformations applied to program representations at abstraction levels higher than machine instructions are fundamentally incapable of protecting against vulnerabilities that are introduced during compilation. In particular, a large proportion of a program’s memory accesses are introduced by the compiler backend. This report presents a backend that protects these accesses against faults in the memory system. It is demonstrated that the presented backend can detect all single bit flips in memory that would be missed by an error detection scheme that operates on the LLVM intermediate representation of programs. The presented compiler backend is obtained by modifying the LLVM backend for the x86 architecture. On a subset of SPEC CINT2006 the runtime overhead incurred by the backend modifications amounts to 1.50x for the 32-bit processor architecture i386, and 1.13x for the 64-bit architecture x86_64. To achieve comprehensive detection of memory faults, the modified backend implements an adjusted calling convention that leaves library function calls transparent and intact.

It is a fact that software has bugs. These bugs can lead to failures. Especially dependability and security failures are a great threat to software users. This thesis introduces four novel approaches that can be used to automatically harden software at the user's site. Automatic hardening removes bugs from already deployed software. All four approaches are automated, i.e., they require little support from the end-user. However, some support from the software developer is needed for two of these approaches. The presented approaches can be grouped into error toleration and bug removal. The two error toleration approaches are focused primarily on fast detection of security errors. When an error is detected it can be tolerated with well-known existing approaches. The other two approaches are bug removal approaches. They remove dependability bugs from already deployed software. We tested all approaches with existing benchmarks and applications, like the Apache web-server.:1 Introduction 1 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Automatic Hardening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Theses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Enforcing Dynamic Personalized System Call Models 9 2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 SwitchBlade Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 System Call Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1 Personalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Model Learner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.1 Problem: False Positives . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.2 Data- ow-Based Learner . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5 Taint Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5.1 TaintCheck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5.2 Escaping Valgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5.3 Replay of Requests . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.6 Model Enforcement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.6.1 Loading the System Call Model . . . . . . . . . . . . . . . . . . . . 31 2.6.2 Checking System Calls . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 Synthetic Exploits . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.2 Apache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.7.3 Exploits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.7.4 Micro Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.7.5 Model Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.7.6 Stateful Application . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Speculation for Parallelizing Runtime Checks 43 3.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1.1 Compiler Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.2 Runtime Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3 Deterministic Replay and Speculation . . . . . . . . . . . . . . . . . . . . . 52 3.3.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 Switching Code Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.4.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.2 Integration with parexc chkpnt . . . . . . . . . . . . . . . . . . 58 3.4.3 Code Transformations . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4.4 Stack-local Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Speculative Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.5.2 Deadlock Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.5.3 Storage Back-ends . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.6 Parallelized Checkers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.6.1 Out-of-Bounds Checks . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.6.2 Data Flow Integrity Checks . . . . . . . . . . . . . . . . . . . . . . 71 3.6.3 FastAssert Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.6.4 Runtime Checking in STM-Based Applications . . . . . . . . . . . . 72 3.7 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.7.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.7.2 Checking Already Parallelized Applications . . . . . . . . . . . . . . 77 3.7.3 ParExC Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4 Automatically Finding and Patching Bad Error Handling 83 4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3 Learning Library-Level Error Return Values from System Call Error Injection 89 4.3.1 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.3.2 E cient Error Injection . . . . . . . . . . . . . . . . . . . . . . . . 91 4.3.3 Obtain OS Error Specification . . . . . . . . . . . . . . . . . . . . . 92 4.4 Finding Bad Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.4.1 Argument Recording . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.4.2 Systematic Error Injection . . . . . . . . . . . . . . . . . . . . . . . 94 4.4.3 Static Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.5 Fast Error Injection using Virtual Machines . . . . . . . . . . . . . . . . . 99 4.5.1 The fork Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.5.2 Virtual Machines for Fault Injection . . . . . . . . . . . . . . . . . . 101 4.6 Patching Bad Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.6.1 Error Value Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.6.2 Preallocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.6.3 Patch Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.7 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.7.1 Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5 Robustness and Security Hardening of COTS Software Libraries 117 5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.3 Test Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.3.1 Ballista Type System . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.3.2 Meta Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.3.3 Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.3.4 Type Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.3.5 Type Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.3.6 Reducing the Number of Test Cases . . . . . . . . . . . . . . . . . . 128 5.3.7 Other Sources of Test Values . . . . . . . . . . . . . . . . . . . . . . 130 5.4 Checks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.4.1 Check Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.4.2 Parameterized Check Templates . . . . . . . . . . . . . . . . . . . . 133 5.5 Protection Hypotheses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 5.5.1 Minimizing the Truth Table . . . . . . . . . . . . . . . . . . . . . . 134 5.5.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.6.1 Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 5.6.2 Autocannon as Dependability Benchmark . . . . . . . . . . . . . . 138 5.6.3 Protection Hypotheses . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6 Conclusion 143 6.1 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 References 147 List of Figures 159 List of Tables 163 Listings 165

Energy consumption is a major concern in Wireless Sensor Networks (WSNs) resulting in a strong demand for energy-aware communication technologies. In this context, several unequal cluster-based routing protocols have been proposed. However, few of them adopt energetic analysis models for the calculation of the optimal cluster radius and several protocols can not realize an optimal workload balance between sensor nodes. In this scope, the aim of the dissertation is to develop a cluster-based routing protocol for improving energy efficiency in WSN. We propose a Fuzzy-based Energy-Aware Unequal Clustering algorithm (FEAUC) with circular partitioning to balance the energy consumption between sensor nodes and solve the hotspot problem created by a multi-hop communication. The developed FEAUC involves mainly four phases: An off-line phase, a cluster formation phase, a cooperation phase and data collection phase. During the off-line phase, an energy analysis is performed to calculate the radius of each ring and the optimal cluster radius per ring. The cluster formation phase is based on a fuzzy logic approach for the cluster head (CH) selection. The cooperation phase aims to define an intermediate node as a router between different CHs. While, in the data collection phase, transmitting data packet from sensor nodes to their appropriate CHs is defined as an intra-cluster communication, and transmitting data from one CH to another until reaching the base station, is defined as an inter-cluster communication. The feasibility of the developed FEAUC is demonstrated by elaborating comparison with selected referred unequal clustering algorithms considering different parameters, mainly, the energy consumption, battery lifetime, time to first node shuts down (FND), time of half of nodes off-line (HND) and time to last node dies (LND). Although, the developed FEAUC is intended to enhance the network lifetime by distributing the large load of CH tasks equally among the normal nodes, running the clustering process in each round is an additional burden, which can significantly drain the remaining energy. For this reason, the FEAUC based protocol has been further developed to become a fault tolerant algorithm (FEAUC-FT). It supports the fault tolerance by using backup CHs to avoid the re-clustering process in certain rounds or by building further routing paths in case of a link failure between different CHs. The validation of the developed FEAUC in real scenarios has been performed. Some sensor nodes, powered with batteries, are deployed in a circular area forming clusters. Performance evaluations are carried out by realistic scenarios and tested for a real deployment using the low-power wireless sensor node panStamp. To complete previous works, as a step of proof of concept, a smart irrigation system is designed, called Air-IoT. Furthermore, a real-time IoT-based sensor node architecture to control the quantity of water in some deployed nodes is introduced. To this end, a cloud-connected wireless network to monitor the soil moisture and temperature is well-designed. Generally, this step is essential to validate and evaluate the proposed unequal cluster-based routing algorithm in a real demonstrator. The proposed prototype guarantees both real-time monitoring and reliable and cost-effective transmission between each node and the base station.:1 Introduction 2 Theoretical background 3 State of the art of unequal cluster-based routing protocols 4 FEAUC: Fuzzy-based Energy-Aware Unequal Clustering 5 Experimental validation of the developed unequal clustering protocol 6 Real application to specific uses cases 7 Conclusions and future research directions / Der Energieverbrauch ist ein Hauptanliegen in drahtlosen Sensornetzwerken (WSNs), was zu einer starken Nachfrage nach energiebewussten Kommunikationstechnologien führt. In diesem Zusammenhang wurden mehrere ungleiche clusterbasierte Routing-Protokolle vorgeschlagen. Allerdings verwenden nur die wenigsten energetische Analysemodelle für die Berechnung des optimalen Cluster-Radius, und mehrere Protokolle können keine optimale Auslastungsbalance zwischen Sensorknoten realisieren. In diesem Zusammenhang ist es das Ziel der Dissertation, ein clusterbasiertes Routing-Protokoll zur Verbesserung der Energieeffizienz im WSN zu entwickeln. Wir schlagen einen Fuzzy-basierten Energy-Aware Unequal Clustering-Algorithmus (FEAUC) mit zirkulärer Partitionierung vor, um den Energieverbrauch zwischen Sensorknoten auszugleichen und das durch eine Multi-Hop-Kommunikation entstehende Hotspot-Problem zu lösen. Der entwickelte FEAUC umfasst hauptsächlich vier Phasen: Eine Offline-Phase, eine Clusterbildungsphase, eine Kooperationsphase und eine Phase der Datensammlung. Während der Offline-Phase wird eine Energieanalyse durchgeführt, um den Radius jedes Ringes und den optimalen Cluster- Radius pro Ring zu berechnen. Die Clusterbildungsphase basiert auf einem Fuzzy-Logik-Ansatz für die Clusterkopf (CH)-Auswahl. Die Kooperationsphase zielt darauf ab, einen Zwischenknoten als einen Router zwischen verschiedenen CHs zu definieren. In der Datensammelphase wird die Übertragung von Datenpaketen von Sensorknoten zu ihren entsprechenden CHs als eine Intra-Cluster-Kommunikation definiert, während die Übertragung von Daten von einem CH zu einem anderen CH bis zum Erreichen der Basisstation als eine Inter-Cluster-Kommunikation definiert wird. Die Machbarkeit des entwickelten FEAUC wird durch die Ausarbeitung eines Vergleichs mit ausgewählten referenzierten ungleichen Clustering-Algorithmen unter Berücksichtigung verschiedener Parameter demonstriert, hauptsächlich des Energieverbrauchs, der Batterielebensdauer, der Zeit bis zum Abschalten des ersten Knotens (FND), der Zeit, in der die Hälfte der Knoten offline ist (HND) und der Zeit bis zum letzten Knoten stirbt (LND). Obwohl mit dem entwickelten FEAUC die Lebensdauer des Netzwerks erhöht warden soll, indem die große Last der CH-Aufgaben gleichmäßig auf die übrigen Knoten verteilt wird, stellt die Durchführung des Clustering-Prozesses in jeder Runde eine zusätzliche Belastung dar, die die verbleibende Energie erheblich entziehen kann. Aus diesem Grund wurde das auf FEAUC basierende Protokoll zu einem fehlerto-leranten Algorithmus (FEAUC-FT) weiterentwickelt. Er unterstützt die Fehlerto-leranz durch die Verwendung von Backup-CHs zur Vermeidung des Re-Clustering-Prozesses in bestimmten Runden oder durch den Aufbau weiterer Routing-Pfade im Falle eines Verbindungsausfalls zwischen verschiedenen CHs. Die Validierung des entwickelten FEAUC in realen Szenarien ist durchgeführt worden. Einige Sensorknoten, die mit Batterien betrieben werden, sind in einem kreisförmigen Bereich angeordnet und bilden Cluster. Leistungsbewertungen warden anhand realistischer Szenarien durchgeführt und für einen realen Einsatz unter Verwendung des drahtlosen Low-Power-Sensorknoten panStamp getestet. Zur Vervollständigung früherer Arbeiten wird als Schritt des Proof-of-Concept ein intelligentes Bewässerungssystem mit der Bezeichnung Air-IoT entworfen. Darüber hinaus wird eine IoT-basierte Echtzeit-Sensorknotenarchitektur zur Kontrolle derWassermenge in einigen eingesetzten Knoten eingeführt. Zu diesem Zweck wird ein mit der Cloud verbundenes drahtloses Netzwerk zur Überwachung der Bodenfeuchtigkeit und -temperatur gut konzipiert. Im Allgemeinen ist dieser Schritt unerlässlich, um den vorgeschlagenen ungleichen clusterbasierten Routing-Algorithmus in einem realen Demonstrator zu validieren und zu bewerten.Der vorgeschlagene Prototyp garantiert sowohl Echtzeit-Überwachung als auch zuverlässige und kostengünstige Übertragung zwischen jedem Knoten und der Basisstation.:1 Introduction 2 Theoretical background 3 State of the art of unequal cluster-based routing protocols 4 FEAUC: Fuzzy-based Energy-Aware Unequal Clustering 5 Experimental validation of the developed unequal clustering protocol 6 Real application to specific uses cases 7 Conclusions and future research directions