This work endeavours to achieve technology transfer between established best-practice in academic high-performance computing and current techniques in commercial high-productivity computing. It shows that a credible high-performance message-passing communication library, with semantics and syntax following the Message-Passing Interface (MPI) Standard, can be built in pure C# (one of the .Net suite of computer languages). Message-passing has been the dominant paradigm in high-performance parallel programming of distributed-memory computer architectures for three decades. The MPI Standard originally distilled architecture-independent and language-agnostic ideas from existing specialised communication libraries and has since been enhanced and extended. Object-oriented languages can increase programmer productivity, for example by allowing complexity to be managed through encapsulation. Both the C# computer language and the .Net common language runtime (CLR) were originally developed by Microsoft Corporation but have since been standardised by the European Computer Manufacturers Association (ECMA) and the International Standards Organisation (ISO), which facilitates portability of source-code and compiled binary programs to a variety of operating systems and hardware. Combining these two open and mature technologies enables mainstream programmers to write tightly-coupled parallel programs in a popular standardised object-oriented language that is portable to most modern operating systems and hardware architectures. This work also establishes that a thread-to-thread delivery option increases shared-memory communication performance between MPI ranks on the same node. This suggests that the thread-as-rank threading model should be explicitly specified in future versions of the MPI Standard and then added to existing MPI libraries for use by thread-safe parallel codes. This work also ascertains that the C# socket object suffers from undesirable characteristics that are critical to communication performance and proposes ways of improving the implementation of this object.

abstract: Most embedded applications are constructed with multiple threads to handle concurrent events. For optimization and debugging of the programs, dynamic program analysis is widely used to collect execution information while the program is running. Unfortunately, the non-deterministic behavior of multithreaded embedded software makes the dynamic analysis difficult. In addition, instrumentation overhead for gathering execution information may change the execution of a program, and lead to distorted analysis results, i.e., probe effect. This thesis presents a framework that tackles the non-determinism and probe effect incurred in dynamic analysis of embedded software. The thesis largely consists of three parts. First of all, we discusses a deterministic replay framework to provide reproducible execution. Once a program execution is recorded, software instrumentation can be safely applied during replay without probe effect. Second, a discussion of probe effect is presented and a simulation-based analysis is proposed to detect execution changes of a program caused by instrumentation overhead. The simulation-based analysis examines if the recording instrumentation changes the original program execution. Lastly, the thesis discusses data race detection algorithms that help to remove data races for correctness of the replay and the simulation-based analysis. The focus is to make the detection efficient for C/C++ programs, and to increase scalability of the detection on multi-core machines. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2015

Concurrent software executes multiple threads or processes to achieve high performance. However, concurrency results in a huge number of different system behaviors that are difficult to test and verify. The aim of this dissertation is to develop new methods and tools for modeling and analyzing concurrent software systems at design and code levels. This dissertation consists of several related results. First, a formal model of Mondex, an electronic purse system, is built using Petri nets from user requirements, which is formally verified using model checking. Second, Petri nets models are automatically mined from the event traces generated from scientific workflows. Third, partial order models are automatically extracted from some instrumented concurrent program execution, and potential atomicity violation bugs are automatically verified based on the partial order models using model checking. Our formal specification and verification of Mondex have contributed to the world wide effort in developing a verified software repository. Our method to mine Petri net models automatically from provenance offers a new approach to build scientific workflows. Our dynamic prediction tool, named McPatom, can predict several known bugs in real world systems including one that evades several other existing tools. McPatom is efficient and scalable as it takes advantage of the nature of atomicity violations and considers only a pair of threads and accesses to a single shared variable at one time. However, predictive tools need to consider the tradeoffs between precision and coverage. Based on McPatom, this dissertation presents two methods for improving the coverage and precision of atomicity violation predictions: 1) a post-prediction analysis method to increase coverage while ensuring precision; 2) a follow-up replaying method to further increase coverage. Both methods are implemented in a completely automatic tool.

Concurrency bugs are extremely hard to detect due to huge interleaving space. They are happening in the real world more often because of the prevalence of multi-threaded programs taking advantage of multi-core hardware, and microservice based distributed systems moving more and more applications to the cloud. As the most common non-deadlock concurrency bugs, atomicity violations are studied in many recent works, however, those methods are applicable only to single-variable atomicity violation, and don't consider the specific challenge in distributed systems that have both pessimistic and optimistic concurrency control. This dissertation presents a tool using model checking to predict atomicity violation concurrency bugs involving two shared variables or shared resources. We developed a unique method inferring correlation between shared variables in multi-threaded programs and shared resources in microservice based distributed systems, that is based on dynamic analysis and is able to detect the correlation that would be missed by static analysis. For multi-threaded programs, we use a binary instrumentation tool to capture runtime information about shared variables and synchronization events, and for microservice based distributed systems, we use a web proxy to capture HTTP based traffic about API calls and the shared resources they access including distributed locks. Based on the detected correlation and runtime trace, the tool is powerful and can explore a vast interleaving space of a multi-threaded program or a microservice based distributed system given a small set of captured test runs. It is applicable to large real-world systems and can predict atomicity violations missed by other related works for multi-threaded programs and a couple of previous unknown atomicity violation in real world open source microservice based systems. A limitation is that redundant model checking may be performed if two recorded interleaved traces yield the same partial order model.

In this thesis an operational semantics for a subset of the Java Virtual Machine (JVM) is developed and presented. The subset contains standard operations such as control flow, computation, and memory management. In addition, the subset contains a treatment of parallel threads of execution. The operational semantics are embedded into a $µ$-calculus based proof assistant, called the VeriCode Proof Tool (VCPT). VCPT has been developed at the Swedish Institute of Computer Science (SICS), and has powerful features for proving inductive assertions. Some examples of proving properties of programs using the embedding are presented. / I det här examensarbetet  presenteras en operationell semantik för en delmängd av Javas virtuella maskin. Den delmängd som hanteras innehåller kontrollflöde, beräkningar och minneshantering. Vidare beskrivs  semantiken för parallella exekveringstrådar. Den operationella semantiken formaliseras i en bevisassistent for $µ$-kalkyl, VeriCode Proof Tool (VCPT). VCPT har utvecklats vid Swedish Institiute of Computer Science (SICS), och har kraftfulla tekniker för att bevisa induktiva påståenden. Några exempel på bevis av egenskaper hos program användandes formaliseringen presenteras också.

Thema dieser Arbeit ist die Entwicklung eines Kommunikationsteilsystems fuer das Experimentiersystem CHEOPS zur Ermoeglichung einer Interobjektkommunika- tion zwischen Objekten auf dem gleichen bzw. verschiedenen Systemen. Ausgangspunkte stellen dabei eine verfuegbare Implementation eines Ethernet- Treibers der Kartenfamilie WD80x3 fuer MS-DOS, eine geforderte Kommunikations- moeglichkeit mit UNIX-Prozessen sowie die dort benutzbaren Protokoll-Familien dar. Die Arbeit beschaeftigt sich mit der Analyse und Konzipierung des Ethernet- Treibers sowie der Internet-Protokoll-Familie fuer CHEOPS als auch deren Implementation resultierend in einem minimalen Grundsystem. Weiterhin wird ein erster Entwurf fuer ein spaeter weiterzuentwickelndes bzw. zu vervoll- staendigendes Netz-Interface vorgeschlagen und durch eine Beispiel-Implemen- tierung belegt.

This thesis proposes a new methodology to extend the software performance engineering process. Common performance measurement and tuning principles mainly target to improve the software function itself. Hereby, the application source code is studied and improved independently of the overall system performance behavior. Moreover, the optimization of the software function has to be done without an estimation of the expected optimization gain. This often leads to an under- or overoptimization, and hence, does not utilize the system sufficiently. The proposed performance improvement methodology and framework, called dynamic performance stubs, improves the before mentioned insufficiencies by evaluating the overall system performance improvement. This is achieved by simulating the performance behavior of the original software functionality depending on an adjustable optimization level prior to the real optimization. So, it enables the software performance analyst to determine the systems’ overall performance behavior considering possible outcomes of different improvement approaches. Moreover, by using the dynamic performance stubs methodology, a cost-benefit analysis of different optimizations regarding the performance behavior can be done. The approach of the dynamic performance stubs is to replace the software bottleneck by a stub. This stub combines the simulation of the software functionality with the possibility to adjust the performance behavior depending on one or more different performance aspects of the replaced software function. A general methodology for using dynamic performance stubs as well as several methodologies for simulating different performance aspects is discussed. Finally, several case studies to show the application and usability of the dynamic performance stubs approach are presented.

The goal of this dissertation is to present new and improved techniques for fully automatic verification of sequential and concurrent software libraries. In most cases, automatic software verification is plagued by undecidability, while in many others it suffers from prohibitively high computational complexity. Model checking -- a highly successful technique used for verifying finite state hardware circuits against logical specifications -- has been less widely adapted for software, as software verification tends to involve reasoning about potentially infinite state-spaces. Two of the biggest culprits responsible for making software model checking hard are heap-allocated data structures and concurrency. In the first part of this dissertation, we study the problem of verifying shape properties of sequential data structure libraries. Such libraries are implemented as collections of methods that manipulate the underlying data structure. Examples of such methods include: methods to insert, delete, and update data values of nodes in linked lists, binary trees, and directed acyclic graphs; methods to reverse linked lists; and methods to rotate balanced trees. Well-written methods are accompanied by documentation that specifies the observational behavior of these methods in terms of pre/post-conditions. A pre-condition [phi] for a method M characterizes the state of a data structure before the method acts on it, and the post-condition [psi] characterizes the state of the data structure after the method has terminated. In a certain sense, we can view the method as a function that operates on an input data structure, producing an output data structure. Examples of such pre/post-conditions include shape properties such as acyclicity, sorted-ness, tree-ness, reachability of particular data values, and reachability of pointer values, and data structure-specific properties such as: "no red node has a red child'', and "there is no node with data value 'a' in the data structure''. Moreover, methods are often expected not to violate certain safety properties such as the absence of dangling pointers, absence of null pointer dereferences, and absence of memory leaks. We often assume such specifications as implicit, and say that a method is incorrect if it violates such specifications. We model data structures as directed graphs, and use the two terms interchangeably. Verifying correctness of methods operating on graphs is an instance of the parameterized verification problem: for every input graph that satisfies [phi], we wish to ensure that the corresponding output graph satisfies [psi]. Control structures such as loops and recursion allow an arbitrary method to simulate a Turing Machine. Hence, the parameterized verification problem for arbitrary methods is undecidable. One of the main contributions of this dissertation is in identifying mathematical conditions on a programming language fragment for which parameterized verification is not only decidable, but also efficient from a complexity perspective. The decidable fragment we consider can be broadly sub-divided into two categories: the class of iterative methods, or methods which use loops as a control flow construct to traverse a data structure, and the class of recursive methods, or methods that use recursion to traverse the data structure. We show that for an iterative method operating on a directed graph, if we are guaranteed that if the number of destructive updates that a method performs is bounded (by a constant, i.e., O(1)), and is guaranteed to terminate, then the correctness of the method can be checked in time polynomial in the size of the method and its specifications. Further, we provide a well-defined syntactic fragment for recursive methods operating on tree-like data structures, which assures that any method in this fragment can be verified in time polynomial in the size of the method and its specifications. Our approach draws on the theory of tree automata, and we show that parameterized correctness can be reduced to emptiness of finite-state, nondeterministic tree automata that operate on infinite trees. We then leverage efficient algorithms for checking the emptiness of such tree automata to obtain a tractable verification framework. Our prototype tool demonstrates the low theoretical complexity of our technique by efficiently verifying common methods that operate on data structures. In the second part of the dissertation, we tackle another obstacle for tractable software verification: concurrency. In particular, we explore application of a static analysis technique based on interprocedural dataflow analysis to predict and document deadlocks in concurrent libraries, and analyze deadlocks in clients that use such libraries. The kind of deadlocks that we focus result from circular dependencies in the acquisition of shared resources (such as locks). Well-written applications that use several locks implicitly assume a certain partial order in which locks are acquired by threads. A cycle in the lock acquisition order is an indicator of a possible deadlock within the application. Methods in object-oriented concurrent libraries often encapsulate internal synchronization details. As a result of information hiding, clients calling the library methods may cause thread safety violations by invoking methods in a manner that violates the partial ordering between lock acquisitions that is implicit within the library. Given a concurrent library, we present a technique for inferring interface contracts that speciy permissible concurrent method calls and patterns of aliasing among method arguments that guarantee deadlock-free execution for the methods in the library. The contracts also help client developers by documenting required assumptions about the library methods. Alternatively, the contracts can be statically enforced in the client code to detect potential deadlocks in the client. Our technique combines static analysis with a symbolic encoding for tracking lock dependencies, allowing us to synthesize contracts using a satisfiability modulo theories (SMT) solver. Additionally, we investigate extensions of our technique to reason about deadlocks in libraries that employ signalling primitives such as wait-notify for cooperative synchronization. We demonstrate its scalability and efficiency with a prototype tool that analyzed over a million lines of code for some widely-used open-source Java libraries in less than 50 minutes. Furthermore, the contracts inferred by our approach have been able to pinpoint real bugs, i.e. deadlocks that have been reported by users of these libraries. / text

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-13T17:20:26Z No. of bitstreams: 1 AYLA DEBORA DANTAS DE SOUZA REBOUÇAS - TESE PPGCC 2010..pdf: 2130099 bytes, checksum: 004385606718ac74b12c8332e37b890c (MD5) / Made available in DSpace on 2018-08-13T17:20:26Z (GMT). No. of bitstreams: 1 AYLA DEBORA DANTAS DE SOUZA REBOUÇAS - TESE PPGCC 2010..pdf: 2130099 bytes, checksum: 004385606718ac74b12c8332e37b890c (MD5) Previous issue date: 2010-08-30 / CNPq / Testar sistemas com múltiplas threads é uma atividade que envolve vários desafios. O fato de serem inerentemente não determinísticos torna tanto a implementação desses sistemas quanto a implementação de seus testes suscetível a erros. É comum existirem testes nestes sistemas que falham em apenas algumas execuções, sem que as causas dessas falhas sejam faltas na aplicação (também conhecidas como defeitos oubugs), mas sim devido a problemas nos testes. Por exemplo, isso pode acontecer se a fase dos testes em que são feitas as verificações (asserções) for executada em momentos inadequados. Isso é freqüente quando os testes envolvem operações assíncronas. Deve-se evitar que nestes testes as asserções sejam feitas antes que essas operações tenham sido concluídas ou também que sejam feitas em um momento tardio, quando o sistema mudou de estado e as condições verificadas não são mais satisfeitas, gerando assim falsos positivos. Testes que não são confiáveis, como os que falham devido a tais problemas, levam os desenvolvedores a desperdiçar muito tempo procurando faltas de software que não existem. Além disso, os desenvolvedores podem perder a confiança nos testes parando de acreditar que falhas em certos testes são devidas a faltas, mesmo quando este é o caso. A existência de tais cenários foi o que motivou este trabalho, que tem como objetivo evitar que asserções em testes sejam feitas cedo ou tarde demais. Para atingir esse objetivo, apresenta-se uma abordagem baseada na monitoração e controle das threads daaplicação e quedê suporte ao desenvolvimento de testes corretos de sistemas multi-threaded. A abordagem visa facilitar a implementação de testes envolvendo operações assíncronas e aumentar a confiança dos desenvolvedores nos seus resultados. Esta abordagem foi avaliada através de estudos de caso utilizando uma ferramenta de suporte ao teste de sistemas multi-threaded, desenvolvida para este trabalho, e também através de sua modelagem formal utilizando a linguagem TLA+, com o objetivo de demonstrar que asserções antecipadas e tardias não ocorrem quando ela é utilizada. / Testing multi-threaded systems is quite a challenge. The inherent non-determinism of these systems makes their implementation and the implementation of their tests far more susceptible to error. It is common to have tests of these systems that may not sometimes pass and whose failures are not caused by application faults (bugs), but by problems with the tests. For instance, thiscan happen when there are asynchronous operations whose corresponding test verifications (assertions) are performed at inappropriate times. Unreliable tests make developers waste their time trying to find non-existing bugs, or else make them search for bugs in the wrong place. Another problem is that developers may cease to believe that certain test failures are caused by software bugs even when this is the case. Scenarios like these have motivated this work. Our main objective is to avoid test failures that are caused, not by application defects, but by test assertions performed either too early or too late. In order to achieve this goal, we present an approach whose basic idea is to use thread monitoring and control in order to support the development of multi-threaded systems tests involving asynchronous operations. This approach is intended to make it easier the development of correct tests for these systems and also to improve developers’ confidence on the results of their tests. The proposed approach has been evaluated through case studies using a tool to support the development of multi-threaded systems tests (developed for this work) and also by formally modeling the approach using theTLA+ language in order to prove that early and late assertions do not occur when this approach isused.

Thema dieser Arbeit ist die Entwicklung eines Kommunikationsteilsystems fuer das Experimentiersystem CHEOPS zur Ermoeglichung einer Interobjektkommunika- tion zwischen Objekten auf dem gleichen bzw. verschiedenen Systemen. Ausgangspunkte stellen dabei eine verfuegbare Implementation eines Ethernet- Treibers der Kartenfamilie WD80x3 fuer MS-DOS, eine geforderte Kommunikations- moeglichkeit mit UNIX-Prozessen sowie die dort benutzbaren Protokoll-Familien dar. Die Arbeit beschaeftigt sich mit der Analyse und Konzipierung des Ethernet- Treibers sowie der Internet-Protokoll-Familie fuer CHEOPS als auch deren Implementation resultierend in einem minimalen Grundsystem. Weiterhin wird ein erster Entwurf fuer ein spaeter weiterzuentwickelndes bzw. zu vervoll- staendigendes Netz-Interface vorgeschlagen und durch eine Beispiel-Implemen- tierung belegt.