This paper describes methods and procedures used for code analysis and transformation. It contains basic information of a science discipline called reverse engineering and its use in information technologies. The primary objective is a construction of a generic reverse compiler or decompiler, i.e. tool that can recompile from binary form (optionally from symbolic machine code) to a high level language. This operation is highly dependent on the concrete instruction set and processor architecture. This problem is solved with description of semantic of each instruction by a special language designed for this use. The output is the high level language code and is functionally equivalent to the input. The program is therefore able to work with each instruction set and code written by it can be transformed into the chosen high level language. This proposal is implemented in practice as a part of project Lissom. Generic decompiler is completely new idea. The thesis contains entirely new techniques from theory of compilers and optimizations made by the author.

This diploma thesis discusses the implementation of a GCC target for the Texas Instruments TMS320C6000 DSP platform. To this end, it makes use of mechanisms offered by GCC for porting to new target architectures. GCC internals such as the handling of conditional jumps and the layout of stack frames are investigated and applied to the new architecture. / Diese Diplomarbeit behandelt die Implementierung eines GCC-Targets für die DSP-Plattform TMS320C6000 von Texas Instruments. Dazu werden Mechanismen genutzt, die GCC für die Portierung auf neue Zielplattformen anbietet. GCC-Interna, wie die Behandlung bedingter Sprünge und das Layout von Stack-Frames, werden untersucht und auf die neue Architektur angewendet.

This diploma thesis discusses the applicability of GCC optimization algorithms for the TI TMS320C6x processor family. Conditional and Parallel Execution is used to speed up the resulting code. It describes the optimization framework of the GCC version 4.0 and the implementation details. / Diese Diplomarbeit behandelt die Anwendbarkeit der verschiedenen GCC Optimierungsalgorithmen für die TI TMS320C6x Prozessorfamilie. Bedingte und parallele Ausführbarkeit werden zur Beschleunigung eingesetzt. Sie beschreibt den Rahmen in dem die Optimierungen in Version 4.0 des GCC stattfinden und Details zur Implementierung.

A constraint is a formula in first-order logic expressing a relation between values of various domains. In order to solve a constraint, constructing a propositional encoding is a successfully applied technique that benefits from substantial progress made in the development of modern SAT solvers. However, propositional encodings are generally created by developing a problem-specific generator program or by crafting them manually, which often is a time-consuming and error-prone process especially for constraints over complex domains. Therefore, the present thesis introduces the constraint solver CO4 that automatically generates propositional encodings for constraints over structured finite domains written in a syntactical subset of the functional programming language Haskell. This subset of Haskell enables the specification of expressive and concise constraints by supporting user-defined algebraic data types, pattern matching, and polymorphic types, as well as higher-order and recursive functions. The constraint solver CO4 transforms a constraint written in this high-level language into a propositional formula. After an external SAT solver determined a satisfying assignment for the variables in the generated formula, a solution in the domain of discourse is derived. This approach is even applicable for finite restrictions of recursively defined algebraic data types. The present thesis describes all aspects of CO4 in detail: the language used for specifying constraints, the solving process and its correctness, as well as exemplary applications of CO4.

Une séparation existe de longue date entre les domaines de la compilation et de l'ordonnancement temps-réel. Si ces deux domaines ont le même objectif - la construction d'implantations correctes - la séparation se justifie historiquement par des différences significatives entre les modèles et les méthodes utilisés. Cependant, avec la complexification des applications et du materiel qui les exécute, les problèmes étudiés dans ces deux domaines se confondent désormais largement. Dans cette thèse, nous nous concentrons sur la génération automatique de code pour des systèmes de contrôle embarqué incluant des contraintes complexes (notamment temps-réel). A ces fins, nous défendons l'idée qu'il est profitable de fournir un effort commun de recherche entre ces deux communautés. En adaptant une technique de compilation au problème d'ordonnancement temps réel d'applications sur des architectures multiprocessurs, nous montrons à la fois les difficultés inhérentes à cet effort commun, mais aussi les possibles avancées qu'il porte. En effet, nous montrons que l'adaptation de techniques d'optimisation à de nouveaux objectifs, dans un contexte différent facilite le développement de systèmes de meilleure qualité. Nous proposons d'utiliser les formalismes et langages synchrones comme base formelle commune dans ce travail d'adaptation. Ceux-cis étendent naturellement les modèles classiques utilisés pour l'ordonnancement temps réel (graphes de tâches dépendentes) et la compilation (SSA et graphes de dépendence de données), et fournissent également des techniques efficaces pour la manipulation de structures de contrôle complexes. Nous avons implanté nos résultats dans le compilateur LoPhT. / There is a long standing separation between the fields of compiler construction and real-time scheduling. While both fields have the same objective - the construction of correct implementations – the separation was historically justified by significant differences in the models and methods that were used. Nevertheless, with the ongoing complexification of applications and of the hardware of the execution platforms, the objects and problems studied in these two fields are now largely overlapping. In this thesis, we focus on the automatic code generation for embedded control systems with complex constraints, including hard real-time requirements. To this purpose, we advocate the need for a reconciled research effort between the communities of compilation and real-time systems. By adapting a technique usually used in compilers (software pipelining) to the system-level problem of multiprocessor scheduling of hard real-time applications, we shed light on the difficulties of this unified research effort, but also show how it can lead to real advances. Indeed we explain how adapting techniques for the optimization of new objectives, in a different context, allows us to develop more easily systems of better quality than what was done until now. In this adaptation process, we propose to use synchronous formalisms and languages as a common formal ground. These can be naturally seen as extensions of classical models coming from both real-time scheduling (dependent task graphs) and compilation (single static assignment and data dependency graphs), but also provide powerful techniques for manipulating complex control structures. We implemented our results in the LoPhT compiler.

Most software projects today are written using programming languages. Compilers in turn translate programs written in these higher level languages into machine code, executable on actual hardware. Ensuring that these compilers function correctly is therefore paramount. Manually written test suites make sure that compilers functions correctly for some inputs, but can never hope to cover every possible use case. Thus, it is of interest to find out how other testing techniques can be applied. This project aimed to implement a random test program generator for Configura Magic (CM), a proprietary programming language used at Configura. Our tool is inspired by the widely successful C program generator Csmith. It is implemented by randomly generating an abstract syntax tree (AST) and unparsing it to produce correct code. Our tool found about 3 bugs in the CM compiler, Configura Virtual Machine (CVM), during its development.CVM was instrumented to get code coverage data after compiling programs. Compiling the CVM test suite (CTS) and Configura's main product CET (Configura Extension Technology)cover about 23% and 19% of the compiler respectively, while compiling programs generated by our tool only cover about 6%. But on the other hand, our generated programs uniquely cover about 0.2% that is not covered by CTS and CET. A backend for our tool that generates C-code was also implemented, to compare it against Csmith. The results show that on average (100 program generations 30 times, for a total of 3000 programs), our tool gets about 45% coverage while Csmith gets about 50% on the small C compiler TinyCC. Although our tool was mildly successful in finding bugs, the comparison between it and Csmith shows its potential to be even more effective.

Future computer processors may have tens or hundreds of cores, increasing the need for efficient parallel programming models. The nature of multicore processors will present applications with the challenge of diversity: a variety of operating environments, architectures, and data will be available and the compiler will have no foreknowledge of the environment until run time. Adaptive Online Parallelization (ADOPAR) is a unifying framework that attempts to overcome diver sity by separating discovery and packaging of parallelism. Scheduling for execution may then occur at run time when diversity may best be resolved. This work presents a compact representation of parallelism based on the task graph programming model, tailored especially for ADOPAR and for regular and irregular parallel computations. Task graphs can be unmanageably large for fine-grained parallelism. Rather than representing each task individually, similar tasks are grouped into task descriptors. From these, a task descriptor graph, with relationship descriptors forming the edges of the graph, may be represented. While even highly irregular computations often have structure, previous representations have chosen to restrict what can be easily represented, thus limiting full exploitation by the back end. Therefore, in this work, task and relationship descriptors have been endowed with instantiation functions (methods of descriptors that act as factories) so the front end may have a full range of expression when describing the task graph. The representation uses descriptors to express a full range of regular and irregular computations in a very flexible and compact manner. The representation also allows for dynamic optimization and transformation, which assists ADOPAR in its goal of overcoming various forms of diversity. We have successfully implemented this representation using new compiler intrinsics, allow ADOPAR schedulers to operate on the described task graph for parallel execution, and demonstrate the low code size overhead and the necessity for native schedulers.

It is a well known fact that scientific programs spend most of their running time in executing loops operating on arrays. The polyhedral model is a mathematical framework which was designed to optimize this process. Its use in automatic paralyzation of nested loops goes back to the work of Kuck (1978), who showed that the domain of nested loop with affine lower and upper bounds can be described in terms of a polyhedron, and the seminal work of Karp, Miller and Winograd (1967) on scheduling systems of uniform recurrence equations. For a long period of time Graphite (it is part of the GNU Compiler Collection) was relying on CLooG library to produce SSA intermediate representation from the polyhedral model. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. That is why the following goal was chosen: Creation of SSA generator based on Integer Set Library. / Как известно, большая часть времени исполнения программ, связанных с научными расчетами, тратится на выполнение циклов и взаимодействие с массивами. С целью оптимизации этого процесса был разработан математический фреймворк — полиэдральная модель. Первые её применения можно встретить в работах Дэвида Кука и Ричарда Карпа от 1978 и 1967 соответственно. С целью практического использования полиэдральной модели разрабатывались различные фреймоворки и библиотеки, поддерживающие работу с ней. Такими примерами служат библиотеки CLooG и ISL. В отличие от библиотеки CLooG, специализированной для генерации кода из поэлидарльной модели, библиотека ISL позволяет выполнять различные операции с целочисленными множествами и отношениями между ними. Со временем в библиотеке ISL появилась поддержка собственной генерации абстрактного синтаксического дерева. В рамках магистерской работы была поставлена следующая цель: Cоздание генератора промежуточного представления SSA из полиэдральной модели полностью независимого от библиотеки CLooG.

No description available.

Memory corruption attacks have existed in C and C++ for more than 30 years, and over the years many defenses have been proposed. In addition to that, a new class of attacks, Spectre, has emerged that abuse speculative execution to leak secrets and sensitive data through micro-architectural side channels. Many defenses have been proposed to mitigate Spectre as well. However, with every new defense a new attack emerges, and then a new defense is proposed. This is an ongoing cycle between attackers and defenders. There exists many defenses for many different attack avenues. However, many suffer from either practicality or effectiveness issues, and security researchers need to balance out their compromises. Recently, many hardware vendors, such as Intel and ARM, have realized the extent of the issue of memory corruption attacks and have developed hardware security mechanisms that can be utilized to defend against these attacks. ARM, in particular, has released a mechanism called Pointer Authentication in which its main intended use is to protect the integrity of pointers by generating a Pointer Authentication Code (PAC) using a cryptographic hash function, as a Message Authentication Code (MAC), and placing it on the top unused bits of a 64-bit pointer. Placing the PAC on the top unused bits of the pointer changes its semantics and the pointer cannot be used unless it is properly authenticated. Hardware security features such as PAC are merely mechanisms not full fledged defences, and their effectiveness and practicality depends on how they are being utililzed. Naive use of these defenses doesn't alleviate the issues that exist in many state-of-the-art software defenses. The design of the defense that utilizes these hardware security features needs to have practicality and effectiveness in mind. Having both practicality and effectiveness is now a possible reality with these new hardware security features. This dissertation describes utilizing hardware security features, namely ARM PAC, to build effective and practical defense mechanisms. This dissertation first describes my past work called PACTight, a PAC based defense mechanism that defends against control-flow hijack- ing attacks. PACTight defines three security properties of a pointer such that, if achieved, prevent pointers from being tampered with. They are: 1) unforgeability: A pointer p should always point to its legitimate object; 2) non-copyability: A pointer p can only be used when it is at its specific legitimate location; 3) non-dangling: A pointer p cannot be used after it has been freed. PACTight tightly seals pointers and guarantees that a sealed pointer cannot be forged, copied, or dangling. PACTight protects all sensitive pointers, which are code pointers and pointers that point to code pointers. This completely prevents control-flow hijacking attacks, all while having low performance overhead. In addition to that, this dissertation proposes Scope-Type Integrity (STI), a new defense policy that enforces pointers to conform to the programmer's intended manner, by utilizing scope, type, and permission information. STI collects information offline about the type, scope, and permission (read/write) of every pointer in the program. This information can then be used at runtime to ensure that pointers comply with their intended purpose. This allows STI to defeat advanced pointer attacks since these attacks typically violate either the scope, type, or permission. We present Runtime Scope-Type Integrity (RSTI). RSTI leverages ARM Pointer Authentication (PA) to generate Pointer Authentication Codes (PACs), based on the information from STI, and place these PACs at the top bits of the pointer. At runtime, the PACs are then checked to ensure pointer usage complies with STI. RSTI overcomes two drawbacks that were present in PACTight: 1) PACTight relied on a large external metadata for protection, whereas RSTI uses very little metadata. 2) PACTight only protected a subset of pointers, whereas RSTI protects all pointers in a program. RSTI has large coverage with relatively low overhead. Also, this dissertation proposes sPACtre, a new and novel defense mechanism that aims to prevent Spectre control-flow attacks on existing hardware. sPACtre is an ARM-based defense mechanism that prevents Spectre control-flow attacks by relying on ARM's Pointer Authentication hardware security feature, annotations added to the program on the secrets that need to be protected from leakage and a dynamic tag-based bounds checking mechanism for arrays. We show that sPACtre can defend against these attacks. We evaluate sPACtre on a variety of cryptographic libraries with several cryptographic algorithms, as well as a synthetic benchmark, and show that it is efficient and has low performance overhead Finally, this dissertation explains a new direction for utilizing hardware security features to protect energy harvesting devices from checkpoint-recovery errors and malicious attackers. / Doctor of Philosophy / In recent years, cyber-threats against computer systems have become more and more preva- lent. In spite of many recent advancements in defenses, these attacks are becoming more threatening. However, many of these defenses are not implemented in the real-world. This is due to their high performance overhead. This limited efficiency is not acceptable in the real-world. In addition to that, many of these defenses have limited coverage and do not cover a wide variety of attacks. This makes the performance tradeoff even less convincing. Thus, there is a need for effective and practical defenses that can cover a wide variety of attacks. This dissertation first provides a comprehensive overview of the current state-of-the-art and most dangerous attacks. More specifically, three types of attacks are examined. First, control-flow hijacking attacks, which are attacks that divert the proper execution of a pro- gram to a malicious execution. Second, data oriented attacks. These are attacks that leak sensitive data in a program. Third, Spectre attacks, which are attacks that rely on sup- posedly hidden processor features to leak sensitive data. These "hidden" features are not entirely hidden. This dissertation explains these attacks in detail and the corresponding state-of-the-art defenses that have been proposed by the security research community to mitigate them. This dissertation then discusses effective and practical defense mechanisms that can mitigate these attacks. The dissertation discusses past work, PACTight, as well as its contributions, RSTI and sPACtre, presenting the full design, threat model, implementation, security eval- uation and performance evaluation of each one of these mechanisms. The dissertation relies on insights derived from the nature of the attack and compiler techniques. A compiler is a tool that transforms human-written code into machine code that is understandable by the computer. The compiler can be modified and used to make programs more secure with compiler techniques. The past work, PACTight, is a defense mechanism that defends against the first type of attacks, control-flow hijacking attacks, by preventing an attacker from abusing specific code in the program to divert the program to a malicious execution. Then, this dissertation presents RSTI, a new defense mechanism that overcomes the limitations of PACTight and extends it to cover data oriented attacks and prevent attackers from leaking sensitive data from the program. In addition to that, this dissertation presents sPACtre, a novel defesnse mechanism that defends against Spectre attacks, and prevents an attacker from abusing a processor's hidden features. Finally, this dissertation briefly discusses a possible future direction to protect a different class of devices, referred to as energy-harvesting devices, from attackers.