Mit Hilfe der Technik des Automatischen Differenzierens (AD) lassen sich für Funktionen, die als Programmquellcode gegeben sind, Ableitungsinformationen rechentechnisch effizient und mit geringem Aufwand für den Nutzer bereitstellen. Eine Variante der Implementierung von AD basiert auf der Überladung von Operatoren und Funktionen, die von vielen modernen Programmiersprachen ermöglicht wird. Durch Ausnutzung des Konzepts der Überladung wird eine interne Funktions-Repräsentation (Tape) generiert, die anschließend für die Ableitungsberechnung herangezogen wird. In der Dissertation werden neue Techniken erarbeitet, die eine effizientere Tape-Erstellung und die parallele Tape-Auswertung ermöglichen. Anhand von Laufzeituntersuchungen für numerische Beispiele werden die Möglichkeiten der neuen Techniken verdeutlicht. / Using the technique of Automatic Differentiation (AD), derivative information can be computed efficiently for any function that is given as source code in a supported programming languages. One basic implementation strategy is based on the concept of operator overloading that is available for many programming languages. Due the overloading of operators, an internal representation of the function can be generated at runtime. This so-called tape can then be used for computing derivatives. In the thesis, new techniques are introduced that allow a more efficient tape creation and the parallel evaluation of tapes. Advantages of the new techniques are demonstrated by means of runtime analyses for numerical examples.

Eine der größten Herausforderungen in Data Science ist heutzutage, Daten miteinander in Beziehung zu setzen und ähnliche Daten zu finden. Hierzu kann der aus relationalen Datenbanken bekannte Join-Operator eingesetzt werden. Das Konzept der Ähnlichkeit wird häufig durch mengenbasierte Ähnlichkeitsfunktionen gemessen. Um solche Funktionen als Join-Prädikat nutzen zu können, setzt diese Arbeit voraus, dass Records aus Mengen von Tokens bestehen. Die Arbeit fokussiert sich auf den mengenbasierten Ähnlichkeitsjoin, Set Similarity Join (SSJ). Die Datenmenge, die es heute zu verarbeiten gilt, ist groß und wächst weiter. Der SSJ hingegen ist eine rechenintensive Operation. Um ihn auf großen Daten ausführen zu können, sind neue Ansätze notwendig. Diese Arbeit fokussiert sich auf das Mittel der Parallelisierung. Sie leistet folgende drei Beiträge auf dem Gebiet der SSJs. Erstens beschreibt und untersucht die Arbeit den aktuellen Stand paralleler SSJ-Ansätze. Diese Arbeit vergleicht zehn Map-Reduce-basierte Ansätze aus der Literatur sowohl analytisch als auch experimentell. Der größte Schwachpunkt aller Ansätze ist überraschenderweise eine geringe Skalierbarkeit aufgrund zu hoher Datenreplikation und/ oder ungleich verteilter Daten. Keiner der Ansätze kann den SSJ auf großen Daten berechnen. Zweitens macht die Arbeit die verfügbare hohe CPU-Parallelität moderner Rechner für den SSJ nutzbar. Sie stellt einen neuen daten-parallelen multi-threaded SSJ-Ansatz vor. Der vorgestellte Ansatz ermöglicht erhebliche Laufzeit-Beschleunigungen gegenüber der Ausführung auf einem Thread. Drittens stellt die Arbeit einen neuen hoch skalierbaren verteilten SSJ-Ansatz vor. Mit einer kostenbasierten Heuristik und einem daten-unabhängigen Skalierungsmechanismus vermeidet er Daten-Replikation und wiederholte Berechnungen. Der Ansatz beschleunigt die Join-Ausführung signifikant und ermöglicht die Ausführung auf erheblich größeren Datenmengen als bisher betrachtete parallele Ansätze. / One of today's major challenges in data science is to compare and relate data of similar nature. Using the join operation known from relational databases could help solving this problem. Given a collection of records, the join operation finds all pairs of records, which fulfill a user-chosen predicate. Real-world problems could require complex predicates, such as similarity. A common way to measure similarity are set similarity functions. In order to use set similarity functions as predicates, we assume records to be represented by sets of tokens. In this thesis, we focus on the set similarity join (SSJ) operation. The amount of data to be processed today is typically large and grows continually. On the other hand, the SSJ is a compute-intensive operation. To cope with the increasing size of input data, additional means are needed to develop scalable implementations for SSJ. In this thesis, we focus on parallelization. We make the following three major contributions to SSJ. First, we elaborate on the state-of-the-art in parallelizing SSJ. We compare ten MapReduce-based approaches from the literature analytically and experimentally. Their main limit is surprisingly a low scalability due to too high and/or skewed data replication. None of the approaches could compute the join on large datasets. Second, we leverage the abundant CPU parallelism of modern commodity hardware, which has not yet been considered to scale SSJ. We propose a novel data-parallel multi-threaded SSJ. Our approach provides significant speedups compared to single-threaded executions. Third, we propose a novel highly scalable distributed SSJ approach. With a cost-based heuristic and a data-independent scaling mechanism we avoid data replication and recomputation. A heuristic assigns similar shares of compute costs to each node. Our approach significantly scales up the join execution and processes much larger datasets than all parallel approaches designed and implemented so far.

Mathematical definitions provide a precise, unambiguous way to formulate concepts. They also provide a common language between disciplines. Thus, they are the basis for a well-founded scientific discussion. In addition, mathematical definitions allow for deeper insights into the defined subject based on mathematical theorems that are incontrovertible under the given definition. Besides their value in mathematics, mathematical definitions are indispensable in other sciences like physics, chemistry, and computer science. In computer science, they help to derive the expected behavior of a computer program and provide guidance for the design and testing of software. Therefore, mathematical definitions can be used to design and implement advanced algorithms. One class of widely used algorithms in computer science is the class of particle-based algorithms, also known as particle methods. Particle methods can solve complex problems in various fields, such as fluid dynamics, plasma physics, or granular flows, using diverse simulation methods, including Discrete Element Methods (DEM), Molecular Dynamics (MD), Reproducing Kernel Particle Methods (RKPM), Particle Strength Exchange (PSE), and Smoothed Particle Hydrodynamics (SPH). Despite the increasing use of particle methods driven by improved computing performance, the relation between these algorithms remains formally unclear. In particular, particle methods lack a unifying mathematical definition and precisely defined terminology. This prevents the determination of whether an algorithm belongs to the class and what distinguishes the class. Here we present a rigorous mathematical definition for determining particle methods and demonstrate its importance by applying it to several canonical algorithms and those not previously recognized as particle methods. Furthermore, we base proofs of theorems about parallelizability and computational power on it and use it to develop scientific computing software. Our definition unified, for the first time, the so far loosely connected notion of particle methods. Thus, it marks the necessary starting point for a broad range of joint formal investigations and applications across fields.:1 Introduction 1.1 The Role of Mathematical Definitions 1.2 Particle Methods 1.3 Scope and Contributions of this Thesis 2 Terminology and Notation 3 A Formal Definition of Particle Methods 3.1 Introduction 3.2 Definition of Particle Methods 3.2.1 Particle Method Algorithm 3.2.2 Particle Method Instance 3.2.3 Particle State Transition Function 3.3 Explanation of the Definition of Particle Methods 3.3.1 Illustrative Example 3.3.2 Explanation of the Particle Method Algorithm 3.3.3 Explanation of the Particle Method Instance 3.3.4 Explanation of the State Transition Function 3.4 Conclusion 4 Algorithms as Particle Methods 4.1 Introduction 4.2 Perfectly Elastic Collision in Arbitrary Dimensions 4.3 Particle Strength Exchange 4.4 Smoothed Particle Hydrodynamics 4.5 Lennard-Jones Molecular Dynamics 4.6 Triangulation refinement 4.7 Conway's Game of Life 4.8 Gaussian Elimination 4.9 Conclusion 5 Parallelizability of Particle Methods 5.1 Introduction 5.2 Particle Methods on Shared Memory Systems 5.2.1 Parallelization Scheme 5.2.2 Lemmata 5.2.3 Parallelizability 5.2.4 Time Complexity 5.2.5 Application 5.3 Particle Methods on Distributed Memory Systems 5.3.1 Parallelization Scheme 5.3.2 Lemmata 5.3.3 Parallelizability 5.3.4 Bounds on Time Complexity and Parallel Scalability 5.4 Conclusion 6 Turing Powerfulness and Halting Decidability 6.1 Introduction 6.2 Turing Machine 6.3 Turing Powerfulness of Particle Methods Under a First Set of Constraints 6.4 Turing Powerfulness of Particle Methods Under a Second Set of Constraints 6.5 Halting Decidability of Particle Methods 6.6 Conclusion 7 Particle Methods as a Basis for Scientific Software Engineering 7.1 Introduction 7.2 Design of the Prototype 7.3 Applications, Comparisons, Convergence Study, and Run-time Evaluations 7.4 Conclusion 8 Results, Discussion, Outlook, and Conclusion 8.1 Problem 8.2 Results 8.3 Discussion 8.4 Outlook 8.5 Conclusion

As a modern tomographic technique, Positron-Emission-Tomography (PET) enables non-invasive imaging of metabolic processes in living organisms. It allows the visualization of malfunctions which are characteristic for neurological, cardiological, and oncological diseases. Chemical tracers labeled with radioactive positron emitting isotopes are injected into the patient and the decay of the isotopes is then observed with the detectors of the tomograph. This information is used to compute the spatial distribution of the labeled tracers. Since the spatial resolution of PET devices increases steadily, the whole sensitive process of tomograph imaging requires minimizing not only the disturbing effects, which are specific for the PET measurement method, such as random or scattered coincidences, but also external effects like body movement of the patient. Methods to correct the influences of such patient movement have been developed in previous studies at the PET center, Rossendorf. These methods are based on the spatial correction of each registered coincidence. However, the large amount of data and the complexity of the correction algorithms limited the application to selected studies. The aim of this thesis is to optimize the correction algorithms in a way that allows movement correction in routinely performed PET examinations. The object-oriented development in C++ with support of the platform independent Qt framework enables the employment of multiprocessor systems. In addition, a graphical user interface allows the use of the application by the medical assistant technicians of the PET center. Furthermore, the application provides methods to acquire and administrate movement information directly from the motion tracking system via network communication. Due to the parallelization the performance of the new implementation demonstrates a significant improvement. The parallel optimizations and the implementation of an intuitive usable graphical interface finally enables the PET center Rossendorf to use movement correction in routine patient investigations, thus providing patients an improved tomograph imaging. / Die Positronen-Emissions-Tomographie (PET) ist ein modernes medizinisches Diagnoseverfahren, das nichtinvasive Einblicke in den Stoffwechsel lebender Organismen ermöglicht. Es erfasst Funktionsstörungen, die für neurologische, kardiologische und onkologische Erkrankungen charakteristisch sind. Hierzu werden dem Patienten radioaktive, positronen emittierende Tracer injiziert. Der radioaktive Zerfall der Isotope wird dabei von den umgebenden Detektoren gemessen und die Aktivitätsverteilung durch Rekonstruktionsverfahren bildlich darstellbar gemacht. Da sich die Auflösung solcher Tomographen stetig verbessert und somit sich der Einfluss von qualitätsmindernden Faktoren wie z.B. das Auftreten von zufälligen oder gestreuten Koinzidenzen erhöht, gewinnt die Korrektur dieser Einflüsse immer mehr an Bedeutung. Hierzu zählt unter anderem auch die Korrektur der Einflüsse eventueller Patientenbewegungen während der tomographischen Untersuchung. In vorangegangenen Studien wurde daher am PET Zentrum Rossendorf ein Verfahren entwickelt, um die nachträgliche listmode-basierte Korrektur dieser Bewegungen durch computergestützte Verfahren zu ermöglichen. Bisher schränkte der hohe Rechenaufwand den Einsatz dieser Methoden jedoch ein. Diese Arbeit befasst sich daher mit der Aufgabe, durch geeignete Parallelisierung der Korrekturalgorithmen eine Optimierung dieses Verfahrens in dem Maße zu ermöglichen, der einen routinemässigen Einsatz während PET Untersuchungen erlaubt. Hierbei lässt die durchgeführte objektorientierte Softwareentwicklung in C++ , unter Zuhilfenahme des plattformübergreifenden Qt Frameworks, eine Nutzung von Mehrprozessorsystemen zu. Zusätzlich ermöglicht eine graphische Oberfläche die Bedienung einer solchen Bewegungskorrektur durch die medizinisch technischen Assistenten des PET Zentrums. Um darüber hinaus die Administration und Datenakquisition der Bewegungsdaten zu ermöglichen, stellt die entwickelte Anwendung Funktionen bereit, die die direkte Kommunikation mit dem Bewegungstrackingsystem erlauben. Es zeigte sich, dass durch die Parallelisierung die Geschwindigkeit wesentlich gesteigert wurde. Die parallelen Optimierungen und die Implementation einer intuitiv nutzbaren graphischen Oberfläche erlaubt es dem PET Zentrum nunmehr Bewegungskorrekturen innerhalb von Routineuntersuchungen durchzuführen, um somit den Patienten ein verbessertes Bildgebungsverfahren bereitzustellen.

Many fluid flow processes in nature and technology are characterized by the presence and coexistence of two ore more phases. These two- or multiphase flows are furthermore characterized by a greater complexity of possible flow phenomena and phase interactions then in single phase flows and therefore the numerical simulation of these multiphase flows is usually demanding a much higher numerical effort. The presented work summarizes the research and development work of the author and his research group on "Numerical Methods for Multiphase Flows" at the University of Technology, Chemnitz over the last years. This work was focussed on the development and application of numerical approaches for the prediction of disperse fluid-particle flows in the field of fluid mechanics and process technology. A main part of the work presented here is concerned with the modelling of different physical phenomena in fluid-particle flows under the paradigm of the Lagrangian treatment of the particle motion in the fluid. The Eulerian-Lagrangian approach has proved to be an especially well suited numerical approach for the simulation of disperse multiphase flows. On the other hand its application requires a large amount of (parallel) computational power and other computational ressources. The models described in this work give a mathematical description of the relevant forces and momentum acting on a single spherical particle in the fluid flow field, the particle-wall interaction and the particle erosion to the wall. Further models has been derived in order to take into account the influence of particle-particle collisions on the particle motion as well as the interaction of the fluid flow turbulence with the particle motion. For all these models the state-of-the-art from literature is comprehensively discussed. The main field of interest of the work presented here is in the area of development, implementation, investigation and comparative evaluation of parallelization methods for the Eulerian-Lagrangian approach for the simulation of disperse multiphase flows. Most of the priorly existing work of other authors is based on shared-memory approaches, quasi-serial or static domain decomposition approaches. These parallelization methods are mostly limited in theire applicability and scalability to parallel computer architectures with a limited degree of parallelism (a few number of very powerfull compute nodes) and to more or less homogeneous multiphase flows with uniform particle concentration distribution and minor complexity of phase interactions. This work now presents a novel parallelization method developed by the author, realizing a dynamic load balancing for the Lagrangian approach (DDD - Dynamic Domain Decomposition) and therefore leading to a substantial decrease in total computation time necessary for multiphase flow computations with the Eulerian-Lagrangian approach. Finally, the developed and entirely parallelized Eulerian-Lagrangian approach MISTRAL/PartFlow-3D offers the opportunity of efficient investigation of disperse multiphase flows with higher concentrations of the disperse phase and the resulting strong phase interaction phenomena (four-way coupling). / Viele der in Natur und Technik ablaufenden Strömungsvorgänge sind durch die Koexistenz zweier oder mehrerer Phasen gekennzeichnet. Diese sogenannten Zwei- oder Mehrphasensysteme zeichnen sich durch ein hohes Maß an Komplexität aus und erfordern oft einen sehr hohen rechentechnischen Aufwand zu deren numerischer Simulation. Die vorliegende Arbeit faßt langjährige Forschungs- und Entwicklungsarbeiten des Autors und seiner Forschungsgruppe "Numerische Methoden für Mehrphasenströmungen" an der TU Chemnitz zusammen, die sich mit der Entwicklung und Anwendung numerischer Berechnungsverfahren für disperse Fluid-Partikel-Strömungen auf dem Gebiet der Strömungs- und Verfahrenstechnik befassen. Ein wesentlicher Teil der Arbeit befaßt sich mit der Modellierung unterschiedlicher physikalischer Phänomene in Fluid-Partikel-Strömungen unter dem Paradigma der Lagrange'schen Betrachtungsweise der Partikelbewegung. Das Euler-Lagrange-Verfahren hat sich als besonders geeignetes Berechnungsverfahren für die numerische Simulation disperser Mehrphasenströmungen erwiesen, stellt jedoch in seiner Anwendung auch höchste Anforderungen an die Ressourcen der verwendeten (parallelen) Rechnerarchitekturen. Die näher ausgeführten mathematisch-physikalischen Modelle liefern eine Beschreibung der auf eine kugelförmige Einzelpartikel im Strömungsfeld wirkenden Kräfte und Momente, der Partikel-Wand-Wechselwirkung und der Partikelerosion. Weitere Teilmodelle dienen der Berücksichtigung von Partikel-Partikel-Stoßvorgängen und der Wechselwirkung zwischen Fluidturbulenz und Partikelbewegung. Der Schwerpunkt dieser Arbeit liegt im Weiteren in der Entwicklung, Untersuchung und vergleichenden Bewertung von Parallelisierungsverfahren für das Euler-Lagrange-Verfahren zur Berechnung von dispersen Mehrphasenströmungen. Zuvor von anderen Autoren entwickelte Parallelisierungsmethoden für das Lagrange'sche Berechnungsverfahren basieren im Wesentlichen auf Shared-Memory-Ansätzen, Quasi-Seriellen Verfahren oder statischer Gebietszerlegung (SDD) und sind somit in ihrer Einsetzbarkeit und Skalierbarkeit auf Rechnerarchitekturen mit relativ geringer Parallelität und auf weitgehend homogene Mehrphasenströmungen mit geringer Komplexität der Phasenwechselwirkungen beschränkt. In dieser Arbeit wird eine vom Autor entwickelte, neuartige Parallelisierungsmethode vorgestellt, die eine dynamische Lastverteilung für das Lagrange-Verfahren ermöglicht (DDD - Dynamic Domain Decomposition) und mit deren Hilfe eine deutliche Reduzierung der Gesamtausführungszeiten einer Mehrphasenströmungsberechnung mit dem Euler-Lagrange-Verfahren möglich ist. Im Ergebnis steht mit dem vom Autor und seiner Forschungsgruppe entwickelten vollständig parallelisierten Euler-Lagrange-Verfahren MISTRAL/PartFlow-3D ein numerisches Berechnungsverfahren zur Verfügung, mit dem disperse Mehrphasenströmungen mit höheren Konzentrationen der dispersen Phase und daraus resultierenden starken Phasenwechselwirkungen (Vier-Wege-Kopplung) effektiv untersucht werden können.

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.

Gas-Partikel-Stroemungen finden sich in weiten Bereichen der Energie- und Verfahrenstechnik. Beispiele fuer haeu- fig anzutreffende Problemstellungen sind der Transport, die Separation oder die Injektion eines Gemisches aus festen Partikeln und einem Traegergas. Fuer die numerische Simulation solcher disperser Mehr- phasenstroemungen hat sich das Lagrange-Verfahren als besonders geeignet erwiesen. Andererseits stellt die An- wendung dieses Berechnungsverfahrens hoechste Anforderun- gen an die Ressourcen der verwendeten Rechner. Dies gilt im besonderen Masse fuer die Simulation von Stroemungen mit einer moderaten bis hohen Partikelbeladung, in denen die Partikel-Partikel-Kollisionen einen grossen Einfluss auf das Stroemungsverhalten haben. Um das grosse Leistungspotential, das heutige massiv par- allele Hochleistungsrechner bieten, effizient zu nutzen, wurden im Rahmen dieser Arbeit parallele Simulationsalgo- rithmen fuer die numerische Berechnung kollisionsbehafte- ter Gas-Partikel-Stroemungen entwickelt. Die Effizienz dieser Algorithmen wurde anhand verschiedener Testfaelle untersucht. Auf der Grundlage der dabei erzielten Ergeb- nisse wurden Vorschlaege fuer weitere Entwicklungsmoeg- lichkeiten erarbeitet. / Gas-particle-flows can be found widely in the field of energy production and process engineering. Examples for applications of such kind of flows are transport, se- paration or injection of a mixture of solid particles and a gaseous phase. The Lagrangian approach has proved to be a suitable means for the numerical simulation of disperse multiphase flows. On the other hand its application requires a large amount of computational power, especially when flows with a mo- derate or high particle loading are computed and particle- particle collisions have a significant influence on the flow. In order to use efficiently the large computational power that parallel computers provide nowadays, parallel algo- rithms for the numerical simulation of gas-particle flows including particle-particle collisions were developed in the cource of this work. The algorithms' efficiency was investigated considering different test cases. On the basis of the results suggestions for further developments were made.

We study anomalous diffusion on fractals with a static external field applied. We utilise the master equation to calculate particle distributions and from that important quantities as for example the mean square displacement <r^2(t)>. Applying different bias amplitudes on several regular Sierpinski carpets we obtain maximal drift velocities for weak field strengths. According to <r^2(t)>~t^(2/d_w), we determine random walk dimensions of d_w<2 for applied external fields. These d_w corresponds to superdiffusion, although diffusion is hindered by the structure of the carpet, containing dangling ends. This seems to result from two competing effects arising within an external field. Though the particles prefer to move along the biased direction, some particles get trapped by dangling ends. To escape from there they have to move against the field direction. Due to the by the bias accelerated particles and the trapped ones the probability distribution gets wider and thus d_w<2. / In dieser Arbeit untersuchen wir anomale Diffusion auf Fraktalen unter Einwirkung eines statisches äußeres Feldes. Wir benutzen die Mastergleichung, um die Wahrscheinlichkeitsverteilung der Teilchen zu berechnen, um daraus wichtige Größen wie das mittlere Abstandsquadrat <r^2(t)> zu bestimmen. Wir wenden unterschiedliche Feldstärken bei verschiedenen regelmäßigen Sierpinski-Teppichen an und erhalten maximale Driftgeschwindigkeiten für schwache Feldstärken. Über <r^2(t)>~t^{2/d_w} bestimmen wir die Random-Walk-Dimension d_w als d_w<2. Dieser Wert für d_w entspricht der Superdiffusion, obwohl der Diffusionsprozess durch Strukturen des Teppichs, wie Sackgassen, behindert wird. Es schient, dass dies das Ergebnis zweier konkurrierender Effekte ist, die durch das Anlegen eines äußeren Feldes entstehen. Einerseits bewegen sich die Teilchen bevorzugt entlang der Feldrichtung. Andererseits gelangen einige Teilchen in Sackgassen. Um die Sackgassen, die in Feldrichtung liegen, zu verlassen, müssen sich die Teilchen entgegen der Feldrichtung bewegen. Somit sind die Teilchen eine gewisse Zeit in der Sackgasse gefangen. Infolge der durch das äußere Feld beschleunigten und der gefangenen Teilchen, verbreitert sich die Wahrscheinlichkeitsverteilung der Teilchen und somit ist d_w<2.

As a modern tomographic technique, Positron-Emission-Tomography (PET) enables non-invasive imaging of metabolic processes in living organisms. It allows the visualization of malfunctions which are characteristic for neurological, cardiological, and oncological diseases. Chemical tracers labeled with radioactive positron emitting isotopes are injected into the patient and the decay of the isotopes is then observed with the detectors of the tomograph. This information is used to compute the spatial distribution of the labeled tracers. Since the spatial resolution of PET devices increases steadily, the whole sensitive process of tomograph imaging requires minimizing not only the disturbing effects, which are specific for the PET measurement method, such as random or scattered coincidences, but also external effects like body movement of the patient. Methods to correct the influences of such patient movement have been developed in previous studies at the PET center, Rossendorf. These methods are based on the spatial correction of each registered coincidence. However, the large amount of data and the complexity of the correction algorithms limited the application to selected studies. The aim of this thesis is to optimize the correction algorithms in a way that allows movement correction in routinely performed PET examinations. The object-oriented development in C++ with support of the platform independent Qt framework enables the employment of multiprocessor systems. In addition, a graphical user interface allows the use of the application by the medical assistant technicians of the PET center. Furthermore, the application provides methods to acquire and administrate movement information directly from the motion tracking system via network communication. Due to the parallelization the performance of the new implementation demonstrates a significant improvement. The parallel optimizations and the implementation of an intuitive usable graphical interface finally enables the PET center Rossendorf to use movement correction in routine patient investigations, thus providing patients an improved tomograph imaging. / Die Positronen-Emissions-Tomographie (PET) ist ein modernes medizinisches Diagnoseverfahren, das nichtinvasive Einblicke in den Stoffwechsel lebender Organismen ermöglicht. Es erfasst Funktionsstörungen, die für neurologische, kardiologische und onkologische Erkrankungen charakteristisch sind. Hierzu werden dem Patienten radioaktive, positronen emittierende Tracer injiziert. Der radioaktive Zerfall der Isotope wird dabei von den umgebenden Detektoren gemessen und die Aktivitätsverteilung durch Rekonstruktionsverfahren bildlich darstellbar gemacht. Da sich die Auflösung solcher Tomographen stetig verbessert und somit sich der Einfluss von qualitätsmindernden Faktoren wie z.B. das Auftreten von zufälligen oder gestreuten Koinzidenzen erhöht, gewinnt die Korrektur dieser Einflüsse immer mehr an Bedeutung. Hierzu zählt unter anderem auch die Korrektur der Einflüsse eventueller Patientenbewegungen während der tomographischen Untersuchung. In vorangegangenen Studien wurde daher am PET Zentrum Rossendorf ein Verfahren entwickelt, um die nachträgliche listmode-basierte Korrektur dieser Bewegungen durch computergestützte Verfahren zu ermöglichen. Bisher schränkte der hohe Rechenaufwand den Einsatz dieser Methoden jedoch ein. Diese Arbeit befasst sich daher mit der Aufgabe, durch geeignete Parallelisierung der Korrekturalgorithmen eine Optimierung dieses Verfahrens in dem Maße zu ermöglichen, der einen routinemässigen Einsatz während PET Untersuchungen erlaubt. Hierbei lässt die durchgeführte objektorientierte Softwareentwicklung in C++ , unter Zuhilfenahme des plattformübergreifenden Qt Frameworks, eine Nutzung von Mehrprozessorsystemen zu. Zusätzlich ermöglicht eine graphische Oberfläche die Bedienung einer solchen Bewegungskorrektur durch die medizinisch technischen Assistenten des PET Zentrums. Um darüber hinaus die Administration und Datenakquisition der Bewegungsdaten zu ermöglichen, stellt die entwickelte Anwendung Funktionen bereit, die die direkte Kommunikation mit dem Bewegungstrackingsystem erlauben. Es zeigte sich, dass durch die Parallelisierung die Geschwindigkeit wesentlich gesteigert wurde. Die parallelen Optimierungen und die Implementation einer intuitiv nutzbaren graphischen Oberfläche erlaubt es dem PET Zentrum nunmehr Bewegungskorrekturen innerhalb von Routineuntersuchungen durchzuführen, um somit den Patienten ein verbessertes Bildgebungsverfahren bereitzustellen.

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