<p>In object oriented programming, a Call Graph represents the calling relationships between the program’s methods. To be more precise, a Call Graph is a rooted directed graph where each node of the graph represents a method and each edge <em>(u, v)</em> represents a method call from method <em>u </em>to method <em>v.</em></p><p><em></em>Focus of this thesis is on building a framework for Call Graph construction algorithms which can be used in program analysis. Our framework is able to be initialized by different front-ends and constructs various Call Graph algorithms. Here, we instantiate framework with two bytecode readers (ASM and Soot) as front-ends and implement three Call Graph construction algorithms (CHA, RTA and CTA).<em></em></p><p>At first, we used two above mentioned bytecode readers to read the bytecode of a specific Java program, then we found reachable methods for each invoked method; meanwhile we kept obtained details on our own data structures.  Creating data structures for storing required information about Classes, Methods, Fields and Statements, gives us a great opportunity to implement an independent framework for applying well known Call Graph algorithms. As a result of these data structures, Call Graph construction will not depend on bytecode readers; since, whenever we read the bytecode of a program, we accumulate all necessary points in pre-defined data structures and implement our Call Graphs based on this accumulated data.</p><p>Finally, the result is a framework for different Call Graph construction algorithms which is the goal of this thesis. We tested and evaluated the algorithms with a variety of programs as the benchmark and compared the bytecode readers besides the three Call Graph algorithms in different aspects.</p>

La compréhension des objets dans les programmes orientés objet est une tâche impor- tante à la compréhension du code. JavaScript (JS) est un langage orienté-objet dyna- mique, et son dynamisme rend la compréhension du code source très difficile. Dans ce mémoire, nous nous intéressons à l’analyse des objets pour les programmes JS. Notre approche construit de façon automatique un graphe d’objets inspiré du diagramme de classes d’UML à partir d’une exécution concrète d’un programme JS. Le graphe résul- tant montre la structure des objets ainsi que les interactions entre eux. Notre approche utilise une transformation du code source afin de produire cette in- formation au cours de l’exécution. Cette transformation permet de recueillir de l’infor- mation complète au sujet des objets crées ainsi que d’intercepter toutes les modifications de ces objets. À partir de cette information, nous appliquons plusieurs abstractions qui visent à produire une représentation des objets plus compacte et intuitive. Cette approche est implémentée dans l’outil JSTI. Afin d’évaluer l’utilité de l’approche, nous avons mesuré sa performance ainsi que le degré de réduction dû aux abstractions. Nous avons utilisé les dix programmes de réfé- rence de V8 pour cette comparaison. Les résultats montrent que JSTI est assez efficace pour être utilisé en pratique, avec un ralentissement moyen de 14x. De plus, pour 9 des 10 programmes, les graphes sont suffisamment compacts pour être visualisés. Nous avons aussi validé l’approche de façon qualitative en inspectant manuellement les graphes gé- nérés. Ces graphes correspondent généralement très bien au résultat attendu. Mots clés: Analyse de programmes, analyse dynamique, JavaScript, profilage. / Understanding of objects in object-oriented programs is an important task for understanding the code. JavaScript (JS) is a dynamic object-oriented language, Its dynamic nature makes understanding its source code very difficult. In this thesis, we focus on object analysis in JS programs to automatically produce a graph of objects inspired by UML class diagrams from an execution trace. The resulting graph shows the structure of the objects as well as their interconnections. Our approach uses a source-to-source transformation of the original code in order to collect information at runtime. This transformation makes it possible to collect complete information with respect to object creations and property updates. From this information, we perform multiple abstractions that aim to generate a more compact and intuitive representation of objects. This approach has been implemented in the JSTI prototype. To evaluate our approach, we measured its performance and the graph compression achieved by our abstractions. We used the ten V8 benchmarks for this purpose. Results show that JSTI is efficient enough to be used in practice, with an average slowdown of around 14x. Moreover, for 9 out of the 10 studied programs, the generated object graphs are sufficiently small to be visualized directly by developers. We have also performed a qualitative validation of the approach by manually inspecting the generated graphs. We have found that the graphs generated by JSTI generally correspond very closely to the expected results. Keywords: Program analysis, dynamic analysis, JavaScript, profiling.

Highly dynamic languages like Smalltalk do not have much static type information immediately available before the program runs. Static types can still be inferred by analysis tools, but historically, such analysis is only effective on smaller programs of at most a few tens of thousands of lines of code. This dissertation presents a new type inference algorithm, DDP, that is effective on larger programs with hundreds of thousands of lines of code. The approach of the algorithm borrows from the field of knowledge-based systems: it is a demand-driven algorithm that sometimes prunes subgoals. The algorithm is formally described, proven correct, and implemented. Experimental results show that the inferred types are usefully precise. A complete program understanding application, Chuck, has been developed that uses DDP type inferences. This work contributes the DDP algorithm itself, the most thorough semantics of Smalltalk to date, a new general approach for analysis algorithms, and experimental analysis of DDP including determination of useful parameter settings. It also contributes an implementation of DDP, a general analysis framework for Smalltalk, and a complete end-user application that uses DDP.

La compréhension des objets dans les programmes orientés objet est une tâche impor- tante à la compréhension du code. JavaScript (JS) est un langage orienté-objet dyna- mique, et son dynamisme rend la compréhension du code source très difficile. Dans ce mémoire, nous nous intéressons à l’analyse des objets pour les programmes JS. Notre approche construit de façon automatique un graphe d’objets inspiré du diagramme de classes d’UML à partir d’une exécution concrète d’un programme JS. Le graphe résul- tant montre la structure des objets ainsi que les interactions entre eux. Notre approche utilise une transformation du code source afin de produire cette in- formation au cours de l’exécution. Cette transformation permet de recueillir de l’infor- mation complète au sujet des objets crées ainsi que d’intercepter toutes les modifications de ces objets. À partir de cette information, nous appliquons plusieurs abstractions qui visent à produire une représentation des objets plus compacte et intuitive. Cette approche est implémentée dans l’outil JSTI. Afin d’évaluer l’utilité de l’approche, nous avons mesuré sa performance ainsi que le degré de réduction dû aux abstractions. Nous avons utilisé les dix programmes de réfé- rence de V8 pour cette comparaison. Les résultats montrent que JSTI est assez efficace pour être utilisé en pratique, avec un ralentissement moyen de 14x. De plus, pour 9 des 10 programmes, les graphes sont suffisamment compacts pour être visualisés. Nous avons aussi validé l’approche de façon qualitative en inspectant manuellement les graphes gé- nérés. Ces graphes correspondent généralement très bien au résultat attendu. Mots clés: Analyse de programmes, analyse dynamique, JavaScript, profilage. / Understanding of objects in object-oriented programs is an important task for understanding the code. JavaScript (JS) is a dynamic object-oriented language, Its dynamic nature makes understanding its source code very difficult. In this thesis, we focus on object analysis in JS programs to automatically produce a graph of objects inspired by UML class diagrams from an execution trace. The resulting graph shows the structure of the objects as well as their interconnections. Our approach uses a source-to-source transformation of the original code in order to collect information at runtime. This transformation makes it possible to collect complete information with respect to object creations and property updates. From this information, we perform multiple abstractions that aim to generate a more compact and intuitive representation of objects. This approach has been implemented in the JSTI prototype. To evaluate our approach, we measured its performance and the graph compression achieved by our abstractions. We used the ten V8 benchmarks for this purpose. Results show that JSTI is efficient enough to be used in practice, with an average slowdown of around 14x. Moreover, for 9 out of the 10 studied programs, the generated object graphs are sufficiently small to be visualized directly by developers. We have also performed a qualitative validation of the approach by manually inspecting the generated graphs. We have found that the graphs generated by JSTI generally correspond very closely to the expected results. Keywords: Program analysis, dynamic analysis, JavaScript, profiling.

We are in the era of multicore machines, where we must exploit thread level parallelism for programs to run better, smarter, faster, and more efficiently. In order to increase instruction level parallelism, processors and compilers perform heavy dataflow analyses between instructions. However, there isn’t much work done in the area of inter-thread dataflow analysis. In order to pave the way and find new ways to conserve resources across a variety of domains (i.e., execution speed, chip die area, power efficiency, and computational throughput), we propose a novel framework, termed Contech, to facilitate the analysis of multithreaded program in terms of its communication and execution patterns. We focus the scope on shared memory programs rather than message passing programs, since it is more difficult to analyze the communication and execution patterns for these programs. Discovering patterns of shared memory programs has the potential to allow general purpose computing machines to turn on or off architectural tricks according to application-specific features. Our design of Contech is modular in nature, so we can glean a large variety of information from an architecturally independent representation of the program under examination.

This dissertation attacks the well-known problem of path-imprecision in static program analysis. Our starting point is an existing static program analysis that over-approximates the execution paths of the analyzed program. We then make this over-approximating program analysis more precise for automatic testing in an object-oriented programming language. We achieve this by combining the over-approximating program analysis with usage-observing and under-approximating analyses. More specifically, we make the following contributions. We present a technique to eliminate language-level unsound bug warnings produced by an execution-path-over-approximating analysis for object-oriented programs that is based on the weakest precondition calculus. Our technique post-processes the results of the over-approximating analysis by solving the produced constraint systems and generating and executing concrete test-cases that satisfy the given constraint systems. Only test-cases that confirm the results of the over-approximating static analysis are presented to the user. This technique has the important side-benefit of making the results of a weakest-precondition based static analysis easier to understand for human consumers. We show examples from our experiments that visually demonstrate the difference between hundreds of complicated constraints and a simple corresponding JUnit test-case. Besides eliminating language-level unsound bug warnings, we present an additional technique that also addresses user-level unsound bug warnings. This technique pre-processes the testee with a dynamic analysis that takes advantage of actual user data. It annotates the testee with the knowledge obtained from this pre-processing step and thereby provides guidance for the over-approximating analysis. We also present an improvement to dynamic invariant detection for object-oriented programming languages. Previous approaches do not take behavioral subtyping into account and therefore may produce inconsistent results, which can throw off automated analyses such as the ones we are performing for bug-finding. Finally, we address the problem of unwanted dependencies between test-cases caused by global state. We present two techniques for efficiently re-initializing global state between test-case executions and discuss their trade-offs. We have implemented the above techniques in the JCrasher, Check 'n' Crash, and DSD-Crasher tools and present initial experience in using them for automated bug finding in real-world Java programs.

Profiling techniques to detect performance bugs in applications are usually customized to detect a specific bug pattern and involve significant engineering effort. In spite of this effort, many techniques either suffer from high runtime overheads or are imprecise. This necessitates the design of a common and efficient instrumentation substrate that profiles the flow of objects during an execution. Designing such a substrate which enables profile generation precisely with low overhead is non-trivial due to the number of objects created, accessed and paths traversed by them in an execution. In this thesis, we design and implement an efficient instrumentation substrate that efficiently generates object flow profiles for Java programs, without requiring any modifications to the underlying virtual machine. We achieve this by applying Ball-Larus numbering on a specialized hy-brid ow graph (hfg). The hfg path profiles that are collected during runtime are post-processed o ine to derive the object flow profiles. We extend the design to handle inter-procedural objec flows by constructing flow summaries for each method and incorporating them appropriately. We have implemented the substrate and validated its efficacy by applying it on programs from popular benchmark suites including dacapo and java-grande. The results demonstrate the scalability of our approach, which handles 0.2M to 0.55B object accesses with an average runtime overhead of 8x. We also demonstrate the effectiveness of the generated profiles by implementing three client analyses that consume the profiles to detect performance bugs. The analyses are able to detect 38 performance bugs which when refactored result in signi cant performance gains (up to 30%) in running times.

Certains environnements ont besoin de plusieurs compilateurs, par exemple un pour le système d'exploitation, supportant la norme C/C++ complète, et l'autre pour les applications, qui supporte éventuellement un sous-ensemble de la norme, mais capable de fournir plus de performance. Le maintien de plusieurs compilateurs pour une plateforme cible représente un effort considérable. Il est donc plus facile d'implémenter et de maintenir un seul outil responsable des optimisations particulières au processeur ciblé. Il nous faut alors un moyen de relier ces compilateurs à l'optimiseur, de préférence, en gardant au passage certaines structures de données internes aux compilateurs qui, soit prendraient du temps, soit seraient impossible à reconstruire à partir du code assembleur par exemple. Dans cette thèse, nous introduisons Tirex, une représentation textuelle intermédiaire pour échanger des informations de bas niveau, déjà dépendantes de la cible, entre les compilateurs, les optimiseurs et les autres outils de la chaîne de compilation. Notre représentation contient un flot d'instructions du processeur cible, mais garde également la structure explicite du programme et supporte la forme SSA (Static Single Assignment). Elle est facilement extensible et très flexible, ce qui permet de transmettre toute donnée jugée importante à l'optimiseur. Nous construisons Tirex par extension de MinIR, une représentation intermédiaire elle-même basée sur un encodage YAML des structures du compilateur. Nos extensions de Tirex comprennent: l'abaissement de la représentation au niveau du processeur cible, la conservation du flot de données du programme, ainsi que l'ajout d'informations sur les structures de boucles et les dépendances de données. Nous montrons que Tirex est polyvalent et peut être utilisé dans une variété d'applications différentes, comme par exemple un environnement d'exécution virtuel (VEE),et fournit une base forte pour un environnement d'analyse du programme. Dans le cadre d'un VEE, nous présentons un interprèteur de la forme SSA et un compilateur just-in-time (JIT). Nous montrons comment l'interprétation d'une représentation au niveau du processeur cible élimine la plupart des problèmes liés à l'exécution en mode mixte. Nous explorons également les questions liées à l'interprétation efficace d'une représentation de programme sous la forme SSA. / Some environments require several compilers, for instance one for the operating system, supporting the full C/C++ norm, and one for the applications, potentially supporting less but able to derive more performance. Maintaining different compilers for a target requires considerable effort, thus it is easier to implement and maintain target-dependent optimizations in a single, external tool. This requires a way of connecting these compilers with the target-dependent optimizer, preferably passing along some internal compiler data structures that would be time-consuming, difficult or even impossible to reconstruct from assembly language for instance. In this thesis we introduce Tirex, a Textual Intermediate Representation for EXchanging target-level information between compilers, optimizers an different tools in the compilation toolchain. Our intermediate representation contains an instruction stream of the target processor, but still keeps the explicit program structure and supports the SSA form(Static Single Assignment). It is easily extensible and highly flexible, which allows any data to be passed for the purpose of the optimizer. We build Tirex by extending the existing Minimalist Intermediate Representation (MinIR), itself expressed as a YAML textual encoding of compiler structures. Our extensions in Tirex include: lowering the representation to a target level, conserving the program data stream, adding loop scoped information and data dependencies. Tirex is currently produced by the Open64 and the LLVM compilers, with a GCC producer under work. It is consumed by the Linear Assembly Optimizer (LAO), a specialized, target-specific, code optimizer. We show that Tirex is versatile and can be used in a variety of different applications, such as a virtual execution environment (VEE), and provides strong basis for a program analysis framework. As part of the VEE, we present an interpreter for a Static Single Assignment (SSA) form and a just-in-time (JIT) compiler. We show how interpreting a target-level representation eliminates most of the complexities of mixed-mode execution. We also explore the issues related to efficiently interpreting a SSA form program representation.

Dynamic analysis of binary files is an area of computer science that has many purposes. It is useful when it comes to debugging software in a development environment and the developer needs to know which statements affected the value of a specific variable. But it is also useful when analyzing a software for potential vulnerabilities, where data controlled by a malicious user could potentially result in the software executing adverse commands or executing malicious code. In this thesis a tool has been developed to perform dynamic analysis of x86 binaries in order to generate dynamic control-dependence graphs over the execution. These graphs can be used to determine which conditional statements that resulted in a certain outcome. The tool has been developed for x86 Linux systems using the dynamic binary instrumentation framework PIN, developed and maintained by Intel. Techniques for utilizing the additional information about the control flow for a program available during the dynamic analysis in order to improve the control flow information have been implemented and tested. The basic theory of dynamic analysis as well as dynamic slicing is discussed, and a basic overview of the implementation of a dynamic analysis tool is presented. The impact on the performance of the dynamic analysis tool for the techniques used to improve the control flow graph is significant, but approaches to improving the performance are discussed.

In object oriented programming, a Call Graph represents the calling relationships between the program’s methods. To be more precise, a Call Graph is a rooted directed graph where each node of the graph represents a method and each edge (u, v) represents a method call from method u to method v. Focus of this thesis is on building a framework for Call Graph construction algorithms which can be used in program analysis. Our framework is able to be initialized by different front-ends and constructs various Call Graph algorithms. Here, we instantiate framework with two bytecode readers (ASM and Soot) as front-ends and implement three Call Graph construction algorithms (CHA, RTA and CTA). At first, we used two above mentioned bytecode readers to read the bytecode of a specific Java program, then we found reachable methods for each invoked method; meanwhile we kept obtained details on our own data structures.  Creating data structures for storing required information about Classes, Methods, Fields and Statements, gives us a great opportunity to implement an independent framework for applying well known Call Graph algorithms. As a result of these data structures, Call Graph construction will not depend on bytecode readers; since, whenever we read the bytecode of a program, we accumulate all necessary points in pre-defined data structures and implement our Call Graphs based on this accumulated data. Finally, the result is a framework for different Call Graph construction algorithms which is the goal of this thesis. We tested and evaluated the algorithms with a variety of programs as the benchmark and compared the bytecode readers besides the three Call Graph algorithms in different aspects.