The fork-join framework project is one of the more challenging programming assignments in the computer science curriculum at Virginia Tech. Students in Computer Systems must manage a pool of threads to facilitate the shared execution of dynamically created tasks. This project is difficult because students must overcome the challenges of concurrent programming and conform to the project's specific semantic requirements. When working on the project, many students received inconsistent test results and were left confused when debugging. The suggested debugging tool, Helgrind, is a general-purpose thread error detector. It is limited in its ability to help fix bugs because it lacks knowledge of the specific semantic requirements of the fork-join framework. Thus, there is a need for a special-purpose tool tailored for this project. We implemented Willgrind, a debugging tool that checks the behavior of fork-join frameworks implemented by students through dynamic program analysis. Using the Valgrind framework for instrumentation, checking statements are inserted into the code to detect deadlock, ordering violations, and semantic violations at run-time. Additionally, we extended Willgrind with happens-before based checking in WillgrindPlus. This tool checks for ordering violations that do not manifest themselves in a given execution but could in others. In a user study, we provided the tools to 85 students in the Spring 2017 semester and collected over 2,000 submissions. The results indicate that the tools are effective at identifying bugs and useful for fixing bugs. This research makes multithreaded programming easier for students and demonstrates that special-purpose debugging tools can be beneficial in computer science education. / Master of Science

Software applications’ performance is hindered by a variety of factors, but most notably by the well-known CPU-memory speed gap (often known as the memory wall). This results in the CPU sitting idle waiting for data to be brought from memory to processor caches. The addressing used by caches cause non-uniform accesses to various cache sets. The non-uniformity is due to several reasons, including how different objects are accessed by the code and how the data objects are located in memory. Memory allocators determine where dynamically created objects are placed, thus defining addresses and their mapping to cache locations. It is important to evaluate how different allocators behave with respect to the localities of the created objects. Most allocators use a single attribute, the size, of an object in making allocation decisions. Additional attributes such as the placement with respect to other objects, or specific cache area may lead to better use of cache memories. In this dissertation, we proposed and implemented a framework that allows for the development and evaluation of new memory allocation techniques. At the root of the framework is a memory tracing tool called Gleipnir, which provides very detailed information about every memory access, and relates it back to source level objects. Using the traces from Gleipnir, we extended a commonly used cache simulator for generating detailed cache statistics: per function, per data object, per cache line, and identify specific data objects that are conflicting with each other. The utility of the framework is demonstrated with a new memory allocator known as equivalence class allocator. The new allocator allows users to specify cache sets, in addition to object size, where the objects should be placed. We compare this new allocator with two well-known allocators, viz., Doug Lea and Pool allocators.

Dynamic Binary Modification (DBM) is a technique for modifying applications at runtime, working at the level of native code. It has numerous applications, including instrumentation, translation and optimisation. However, DBM introduces a performance overhead, which in some cases can dominate execution time, making many uses impractical. While avenues for reducing this overhead have been widely explored on x86, ARM, an architecture gaining widespread adoption, has received little attention. Consequently, the overhead of DBM on ARM, as reported in the literature and measured using the available DBM systems, has fallen behind the state-of-the-art by one or two orders of magnitude. The research questions addressed in this thesis are: 1) how to develop low overhead DBM systems for the ARM architecture, and 2) whether new optimisations are plausible and needed. Towards that end, a number of novel optimisations were developed and evaluated specifically to address the sources of overhead for DBM on various ARM microarchitectures. Furthermore, many of the optimisations in the literature were ported to ARM and evaluated. This work was enabled by a new DBM system, named MAMBO, created specifically for this purpose. MAMBO, using the optimisations presented in this thesis, is able to achieve an overhead an order of magnitude smaller than that of the most efficient DBM system for ARM available at the start of this PhD.

Indiana University-Purdue University Indianapolis (IUPUI) / Dynamic Binary Instrumentation (DBI) is one way to monitor a distributed system in real-time without modifying source code. Previous work has shown it is possible to instrument distributed systems using standards-based distributed middleware. Existing work, however, only applies to a single middleware, such as CORBA. This thesis therefore presents a tool named the Standards-based Distributed Middleware Monitor (SDMM), which generalizes two modern standards-based distributed middleware, the Data Distribution Service (DDS) and gRemote Procedure Call (gRPC). SDMM uses DBI to extract values and other data relevant to monitoring a distributed system in real-time. Using dynamic instrumentation allows SDMM to capture information without a priori knowledge of the distributed system under instrumentation. We applied SDMM to systems created with two DDS vendors, RTI Connext DDS and OpenDDS, as well as gRPC which is a complete remote procedure call framework. Our results show that the data collection process contributes to less than 2% of the run-time overhead in all test cases.

This report describes the architecture and implementation of a memory profiler for 3D graphics applications. The memory profiling is done for parts of the program which runs on the graphics processor and is responsible for rendering the image. The shaders are parsed and every memory instruction is instrumented with additional instruction for profiling. The results are then transferred from the video memory to CPU memory. Profiling is done for a frame and completes in less than three minutes. The report also describes various analyses that can be done using the results obtained from this profiler. The report discusses the design of an analytical cache model that can be used to identify candidate memory buffers suitable for caching among all the buffers used by an application. The profiler can segregate results for reads and writes separately, can handle all formats of texture access instructions and predicated instructions. / text

<div>Dynamic Binary Instrumentation (DBI) is one way to monitor a distributed system in real-time without modifying source code. Previous work has shown it is possible to instrument distributed systems using standards-based distributed middleware. Existing work, however, only applies to a single middleware, such as CORBA.</div><div><br></div><div>This thesis therefore presents a tool named the Standards-based Distributed Middleware Monitor (SDMM), which generalizes two modern standards-based distributed middleware, the Data Distribution Service (DDS) and gRemote Procedure Call (gRPC). SDMM uses DBI to extract values and other data relevant to monitoring a distributed system in real-time. Using dynamic instrumentation allows SDMM to capture information without a priori knowledge of the distributed system under instrumentation. We applied SDMM to systems created with two DDS vendors, RTI Connext DDS and OpenDDS, as well as gRPC which is a complete remote procedure call framework. Our results show that the data collection process contributes to less than 2% of the run-time overhead in all test cases.</div>

<p><em>Software Instrumentation is the process of collecting data during an application’s runtime,</em></p> <p><em>which will help us debug, detect errors and optimize the performance of the binary. The</em></p> <p><em>recent increase in demand for low latency and high throughput systems has introduced new</em></p> <p><em>challenges to the process of Software Instrumentation. Software Instrumentation, especially</em></p> <p><em>dynamic, has a huge impact on systems performance in scenarios where there is no early</em></p> <p><em>knowledge of data to be collected. Naive approaches collect too much or too little</em></p> <p><em>data, negatively impacting the system’s performance.</em></p> <p><em>This thesis investigates the overhead added by reservoir sampling algorithms at different</em></p> <p><em>levels of granularity in real-time instrumentation of distributed software systems. Also, this thesis describes the implementation of sampling techniques and algorithms to reduce the overhead caused by instrumentation.</em></p>

Despite the increasing attention to the topic of computer security, the amount of vulnerable software services is still high. The exploitation of a common vulnerability like memory management bugs brought to the development of an attack known as Return Oriented Programming (ROP). Such technique employs malicious memory injections to hijack the control flow of the targeted application and execute an arbitrary series of instructions. This thesis explores the design and implementation of a static binary rewriting tool able to instrument applications compiled for the Linux operating system in order to offer protection against ROP exploitation on x86 and ARM platforms. The instrumentation is achieved by extracting re-compilable assembler code from executable binary files which is then processed and modified. The effectiveness of such solution is tested with a selection of benchmarking utilities in order to evaluate the cost in terms of performance caused by its employment. The results obtained from these experiments show that on average the added overheads are acceptably low and, consequently, the proposed tool is a valid solution to improve the security of vulnerable applications when the original source code is not available. / Trots den ökande uppmärksamheten på ämnet datasäkerhet är mängden sårbara mjukvarutjänster fortfarande stor. Utnyttjandet av en vanlig sårbarhet som minneshanteringsfel har lett till utvecklingen av en attack som kallas Return Oriented Programming (ROP). Denna teknik utnyttjar skadliga minnesinjektioner för att ändra kontrollflödet för den riktade applikationen och utföra en godtycklig serie instruktioner. Detta exjobb undersöker utformningen och genomförandet av ett verktyg för statisk binär omskrivning som kan användas för att instrumentera applikationer för Linux-operativsystemet för att erbjuda skydd mot ROP-exploatering på x86- och ARM-plattformar. Instrumentering uppnås genom att extrahera återkompilerbar assemblerkod från exekverbara binära filer som sedan behandlas och modifieras. Effektiviteten av sådan lösning testas med ett urval av benchmarkingverktyg för att utvärdera kostnaden när det gäller prestanda som orsakas av dess användning. Resultaten från dessa experiment visar att de extra kostnaderna i genomsnitt är acceptabelt låga och, följaktligen, är det föreslagna verktyget en giltig lösning för att förbättra säkerheten för sårbara applikationer när den ursprungliga källkoden inte är tillgänglig.

In recent years there has been an increasing interest in dynamic taint tracing of compiled software as a powerful analysis method for security and other purposes. Most existing approaches are highly application specific and tends to sacrifice precision in favor of performance. In this thesis project a generic taint tracing tool has been developed that can deliver high precision taint information. By allowing an arbitrary number of taint labels to be stored for every tainted byte, accurate taint propagation can be achieved for values that are derived from multiple input bytes. The tool has been developed for x86 Linux systems using the dynamic binary instrumentation framework Valgrind. The basic theory of taint tracing and multi-label taint propagation is discussed, as well as the main concepts of implementing a taint tracing tool using dynamic binary instrumentation. The impact of multi-label taint propagation on performance and precision is evaluated. While multi-label taint propagation has a considerable impact on performance, experiments carried out using the tool show that large amounts of taint information is lost with approximate methods using only one label per tainted byte.

Η σχεδίαση μικροεπεξεργαστών είναι μια πολύπλοκη και σύνθετη διαδικασία, η οποία δυσκολεύει όσο οι τεχνολογικές εξελίξεις προχωράνε. Οι μελετητές της απόδοσης των μικροεπεξεργαστών, για να μελετήσουν την απόδοση ενός συστήματος καταλήγουν στη χρησιμοποίηση πλήρους προσομοίωσης, καάτι που είναι εξαιρετικά πολύπλοκο και χρονοβόρο. Σε αυτή την εργασία παρουσιάζεται ένα αναλυτικό μοντέλο που μοντελοποιεί τις επιδόσεις του επεξεργαστή με βάση το πρόγραμμα που εκτελεί και τα δομικά του χαρακτηριστικά. Το μοντέλο αυτό βασίζεται πάνω σε έναν εκτός σειράς υπερβαθμωτό επεξεργαστή. Η μοντελοποίηση βασίζεται στο γεγονός ότι ένας υπερβαθμωτός επεξεργαστής ο οποίος είναι ισορροπημένος διατηρεί σταθερή την απόδοση του εκτός αν συναντήσει ανασχετικά γεγονότα, όπως αποτυχία πρόσβασης στην κρυφή μνήμη ή λάθος στην πρόβλεψη διακλάδωσης. Τα δεδομένα του προγράμματος συλλέγονται κατά την εκτέλεση του προγράμματος με τη χρήση ενός εργαλείου παρεμβολής κώδικα σε εκτελέσιμο αρχείο, το οποίο ονομάζεται DIOTA. Παρουσιάζεται το μοντέλο σταθερής απόδοσης και μετριέται ο αντίκτυπος του κάθε ανασχετικού γεγονότος ξεχωριστά. / Microprocessor design is a complex and difficult process which day by day is getting more difficult as technology advances. Designers, in order to study the efficiency of a microprocessor tend to use full cycle simulation, which is extremely complex and time-consuming. In this thesis, an analytical model is presented, which is modelling the perfonmance of a proccessor in account with the executable and processor's functional characteristics. The model is based on an out of order superscalar processor. The modelling is based on the fact that a balanced superscalar processor is maintaining a steady performance rate, unless a disruptive miss event happens, such as a data cache miss or a branch misprediction. The data from the executable are gathered by using a binary rewriting tool, called DIOTA. The steady state model is being presented, and the impact of each miss event is measured.