Mercredi 30 janvier 2019

Parallélisation automatique d’applications de traitement d’images sur processeur pluricoeur MPPA

Pierre Guillou, MINES ParisTech, CRI, Fontainebleau

Slides

Mes travaux de recherches ont porté, depuis le début de ma thèse au centre de recherche en informatique des Mines, sur la compilation d’applications de traitement d’images à destination du processeur MPPA de Kalray. Cette présentation me donnera l’occasion de résumer ces travaux et en particulier ceux effectués durant l’année 2017. Au programme : bibliothèques de traitement d’images, environnements d’exécutions parallèles et compilation source-à-source.

Optimisation de code MATLAB et modèles de performance

Patryk Kiepas, MINES ParisTech, CRI, Fontainebleau

Slides

Nids de boucles polyédriques et schedules OpenMP : plus difficile qu’il n’y paraît

Harenome Ranaivoarivony-Razanajato, INRIA Strasbourg

Slides

Les outils de parallélisation automatiques basés sur le modèle polyédrique génèrent du code instrumenté avec des directives OpenMP. Ces annotations (omp parallel for) restent basiques et ne tirent pas parti de l’ensemble des clauses OpenMP disponibles. Notamment, la clause schedule permet de modifier la distribution des itérations lors de la parallélisation selon plusieurs politiques (static, dynamic, guided) et une taille de découpage. Ces paramètres de la clause schedule peuvent avoir une grande influence (positive ou négative) sur les performances finales. L’enjeu est donc de trouver, pour un nid de boucles donné, le couple de paramètres adéquat. Cet exposé présentera les premiers travaux et résultats en ce sens.

The Polyhedral Model Beyond Loops – Recursion Optimization and Parallelization Through Polyhedral Modeling

Salwa Kobeissi , INRIA Strasbourg

Slides

There may be a huge gap between the statements outlined by programmers in a program source code and instructions that are actually performed by a given processor architecture when running the executable code. This gap is due to the way the input code has been interpreted, translated and transformed by the compiler and the final processor hardware. Thus, there is an opportunity for efficient optimization strategies, that are dedicated to specific control structures and memory access patterns, to apply as soon as the actual runtime behavior has been discovered, even if they could not have been applied on the original source code.

In this paper, we develop this idea by identifying code extracts that behave as polyhedral-compliant loops at runtime, while not having been outlined at all as loops in the original source code. In particular, we are interested in recursive functions whose runtime behavior can be modeled as polyhedral loops. Therefore, the scope of this study exclusively includes recursive functions whose control flow and memory accesses exhibit an affine behavior, which means that there exists a semantically equivalent affine loop nest, candidate for polyhedral optimizations. Accordingly, our approach is based on analyzing early executions of a recursive program using a Nested Loop Recognition (NLR) algorithm, performing the affine loop modeling of the original program runtime behavior, which is then used to generate an equivalent iterative program, finally optimized using the polyhedral compiler Polly. We present some preliminary results showing that this approach brings recursion optimization techniques into a higher level in addition to widening the scope of the polyhedral model to include originally non-loop programs.

The Dicer: differential performance profiling over trace chunks with randomized

Byron Hawkins, INRIA Rennes

Slides

In response to the ever-present demand for increasing performance in terms of program execution time, it has become common practice in the development lifecycle of a program to examine its performance for missed optimization opportunities. This effort focuses primarily on well-known and well-understood optimizations that are each designed to address the program’s usage of one specific hardware resource, such as the CPU cache or the micro-op dispatch ports. But even though each of these optimizations may be relatively simple to apply, it can be difficult to determine (a) which hardware resources are under-utilized by a program, and (b) what is preventing the program from making full use of those resources. The analysis is complicated by the potential for performance influences to span a large number of instructions. These influences may occur only under specific conditions such as a threshold size of program input data or a threshold number of loop iterations. For example, a large computational loop may be free of load dependencies and appear to be CPU bound, yet stall on load instructions for certain input sets because the particular sequence of memory address access prevents the CPU from effectively leveraging its cache hierarchy. It is also common for one performance limitation to lead to another related limitation, effectively creating a system of limitations that cannot easily be addressed in isolation. For example, the same computational loop might suffer from additional pipeline stalls when loads are not available in cache, because the compiler generated an instruction schedule that is normally efficient but does not account for the special case of long latency loads.

State-of-the-art profiling techniques are limited in accuracy, requiring developers to invest significant manual effort in the discovery of performance opportunities and diagnosis of performance deficiencies. General profiling tools typically report performance observations in terms of elapsed time between program points or the most frequently active code regions, which gives a developer no direct information about the efficiency of hardware resource utilization. Specialized tools may leverage hardware performance counters to provide a more detailed profile, but these are often subject to a skid factor in the correlation between profile data and program instructions. Advances in hardware supported profiling eliminate skid, but these improvements are only available on recent CPU models and in limited scenarios. In addition, the resulting profile contains significantly more detail for the developer to interpret in terms of performance optimizations and deficiencies.

Differential performance profiling (DPP) has been developed to improve the effectiveness of performance profiling, based on the intuition that developers typically discover program performance characteristics by experimenting with changes to the program inputs. This process, although time consuming, focuses on the specific factors that make a difference in program performance. When successful, less effort is required to interpret the results because a differential result naturally reveals the root cause of observed performance behavior. But thus far, DPP has focused mainly on variations of program inputs, which again limits the granularity of the results and cannot target specific performance factors in isolation. To improve precision and control in DPP, we are developing an automated profiling tool called the Dicer based on the binary instrumentation platform Padrone. With support for selective instrumentation, Padrone is able to generate and execute program variations while imposing minimal interference on the low-level performance behaviors of those variations. Fine-grained process control further allows Padrone to explore the performance characteristics of both program sub-regions and execution trace chunks in isolation, while avoiding the difficulty of transforming or refactoring the original program. By collecting a broad range of differential profiles that focus narrowly on the code structure at program hot spots, the Dicer can isolate and report the specific performance factors that make an observable difference in real native executions. Although the Dicer is still in early development, preliminary results indicate significant potential for this approach to improve the accuracy, completeness and usability of automated performance profiling.

Méthodologie de placement d’algorithmes sur GPU

Florian Gouin, MINES ParisTech, CRI Fontainebleau

Towards a Formalized Compilation Scheme for Solidity Contracts

Emilio Gallego, MINES ParisTech, CRI Fontainebleau

In the last few years, permissionless distributed execution platforms
have gained enormous popularity, as they have become a computing environment of choice for decentralized asset management. Concretely, the Ethereum project implements a distributed ledger featuring a Turing-complete execution engine with read/write capability to the underlying blockchain-based storage. Thus, users can immutably store and interact with other “smart contracts”, which has allowed the development of rich trustless applications. However, lack of central control does come at a prize: once a contract is deployed to the blockchain, its code is in
principle immutable, thus bugs take a very different dimension as the same autonomy that makes the permissionless setting interesting works against the effective mitigation of vulnerabilities.

In the talk, we will review the basics of the Ethereum execution
platform: the EVM, and of the Solidity programming language. We will discuss a few example smart contracts that make interesting targets for the verification of high-level properties.

Optimisation de code avec des techniques de machine learning

Maksim Berezov, MINES ParisTech, CRI Fontainebleau

Slides

Semantic Array Dataflow Analysis

Paul Iannetta, Univ.Claude Bernard Lyon 1

Slides

Contrôle de passes à grain fin pour l’obfuscation de code

Equipe Epona, Quarkslab

Slides

L’obfuscation du code consiste à transformer le code et les données de sorte qu’un attaquant ne puisse récupérer aucune information utile de l’exécutable. Ces transformations ont un coût : l’astuce consiste à équilibrer l’impact sur le temps d’exécution et la taille du code d’une part,  et le niveau de protection d’autre part. Puisque le développeur est celui qui connaît les parties sensibles du code et les contraintes de performances, c’est lui qui spécifie les fonctions ou les données à protéger et comment. Les obfuscations sont enchaînées les unes après les autres dans l’espoir d’améliorer le “niveau de protection” de l’application. Le Pass Manager classique du compilateur permet de chaîner les obfuscations les unes après les autres en ciblant certaines entités dans leur ensemble (sur une fonction / unité de compilation entière). Cette approche présente plusieurs limitations. Tout d’abord, l’utilisateur ne peut pas cibler avec précision du code ou des données générés ou mutés par une obfuscation appliquée précédemment. Ce manque de précision du ciblage peut conduire soit à ne pas obfusquer certaines opérations, ce qui donne un niveau de protection réduit, soit à obfusquer des parties de code qui ne le nécessitent pas, avec un impact négatif sur les performances et la taille du code. Par exemple, l’obfuscation appelé Call Graph Flattening transforme chaque appel de fonction en un appel via une indirection. L’index de cette indirection est une constante, qui pourrait être à son tour obfusquée par une passe d’opacification de constantes.
Dans cet exposé, nous présentons un mécanisme à grain fin qui permet un chaînage précis des obfuscations. Notre approche est basée sur une structure de données que nous avons appelée “Value Views” implémentée sous la forme  d’un set qui garde une trace des entités qu’il contient: quand une de ces entités est supprimée du code, elle est automatiquement supprimée du set. Dans notre modèle, chaque Pass consomme et produit des Value Views. Cette approche a été implémentée dans Epona, un obfuscateur basé sur LLVM, où certaines de nos ofuscations ont déjà été portées dans ce modèle. Le but de ce mécanisme est de pouvoir écrire des obfuscations de haut niveau en composant des obfuscatons existantes, et éventuellement d’exposer ces mécanismes au travers d’un langage de scripting qui permettra au développeur de mieux adapter les obfuscations à ses besoins.

Building a Virtual Machine obfuscation

Manuel Carrasco, Quarkslab

In this presentation we are going to talk about how we built a Virtual Machine obfuscation, the challenges this protection faced, and how we tackled them. The goal of a code obfuscation is to hide the intention, logic and data present in a code, to hamper the attempts to understand it. This obfuscation is implemented as an LLVM pass that takes a section of a program to obfuscate and:
– translates the LLVM-IR to a custom Virtual Machine bitcode
– embeds a Virtual Machine interpreter into the original program
– the target code section is replaced by an invocation to the  interpreter using the bitcode

We protected a hashing algorithm using this method and organized a contest around it. Manually reverse engineering attempts resulted in complete failure. This technique can still be piled with other obfuscation techniques. Even if the manual reverse attempts would have succeeded, the original code was also obfuscated using these other techniques. In order to complicate things even further, the Virtual Machine instantiation is parametrized such that changes are introduced between the synthesized interpreters. In this way the reverser’s previous knowledge becomes useless for a new reversing session. Nevertheless, we encountered stronger enemies. Modern reverse engineers rely on automatic or semi-automatic deobfuscation tools. These tools use taint analysis and dynamic symbolic execution (DSE) of binaries to build  a symbolic expression of the result in terms of the program’s input.  These techniques can filter all the Virtual Machine’s machinery.
A part of this work consisted on identifying the limitations of these tools and implementing countermeasures for them.

Génération automatique de codes adaptatifs

Maxime Schmitt, ICPS, Strasbourg

Les techniques reposant sur des calculs approchés sont nécessaires pour obtenir un résultat dans un temps acceptable pour des programmes de calcul intensif tels que les simulations numériques. Les outils de compilation actuels ne permettent pas d’utiliser de telles techniques, les développeurs doivent donc posséder l’expertise requise pour utiliser ces méthodes et gérer les difficultés d’implémentation. Nous proposons des annotations destinées au compilateur pour générer automatiquement un code adaptatif, c’est à dire qui est capable de cibler les ressources de calcul aux endroits importants de l’application. Sans modifier son algorithme, l’utilisateur fournit les informations de haut niveau, telles que les transformations à utiliser pour diminuer le coût des calculs, les données importantes de l’application à superviser et le grain de la grille adaptative à utiliser, et laisse le compilateur générer les versions approchées à partir du code original. Nous proposons également un algorithme qui automatise la découverte de ces paramètres dans le cadre de calculs à stencil.

L’intérêt de RISC-V pour la recherche en compilation

Christian Fabre – CEA LETI, Grenoble

« Par les expérimentations qu’elle permet sur les architectures, l’initiative RISC-V offre des opportunités pour des coopérations de recherche en compilation et en architecture. Nous essaierons de présenter quelques-unes de ces opportunités, mais aussi de discuter certaines des difficultés de la mise en œuvre d’une recherche pluridisciplinaire en ces domaines. »

Compilation et optimisation de code en présence d’annotations de sécurité

Son Tuan Vu,Sorbonne Université, LIP6

Slides

Résumé court : Cet exposé présente une exploration de l’expression et de la propagation de propriétés fonctionnelles et non fonctionnelles à travers le flot de compilation

Résumé long (en anglais) : Program analysis and program transformation systems need to express additional program properties, to specify test and verification goals, and to enhance their effectiveness. Such annotations are typically inserted to the representation on which the tool operates; e.g., source level for establishing compliance with a specification, and binary level for the validation of secure code. While several annotation languages have been proposed, these typically target the expression of functional properties. For the purpose of implementing secure code, there has been little effort to support non-functional properties about side-channels or faults. Furthermore, analyses and transformations making use of such annotations may target different representations encountered along the compilation flow.
We extend an annotation language to express a wider range of functional and non-functional properties, enabling security-oriented analyses and influencing the application of code transformations along the compilation flow. We translate this language to the different compiler representations from abstract syntax down to binary code. We explore these concepts through the design and implementation of an optimizing, annotation-aware compilation framework, capturing annotations from the program source and propagating and emitting these on binary code, so that test and verification tools operating on binaries can make use of these annotations

Outils de développement pour la compilation

Pierre Guillou, MINES ParisTech, CRI, Fontainebleau

Slides / 

Le développement des compilateurs et interpréteurs open-source, tels que GCC ou Clang/LLVM, a permis l’émergence d’outils d’aide au
développement. Nous tâcherons ici de présenter l’écosystème des langages C et C++, au travers notamment des outils associés au compilateur Clang, des systèmes de compilation, et du protocole Language Server.

Accélération matérielle pour la traduction dynamique de programmes binaires

Simon Rokicki, INRIA Rennes

Slides

Nos travaux portent sur l’utilisation de techniques d’accélération matérielle pour la conception de processeurs VLIW basés sur l’optimisation dynamique de binaires. Dans ce type de machine, les instructions du programme exécuté par le processeur sont traduites et optimisées à la volée par un outil de compilation dynamique intégré au processeur. Ce procédé permet de mieux exploiter les ressources du processeur cible, mais est délicate à exploiter car le temps de cette recompilation impacte de manière très significative l’effet global de ces optimisations.
Dans ces travaux, nous montrons que l’utilisation d’accélérateurs matériels pour certaines étapes clés de cette compilation (construction de la représentation intermédiaire, ordonnancement des instructions), permet de ramener le temps de compilation à des valeurs très faibles (en moyenne 6 cycles par instruction, contre plusieurs centaines dans le cas d’une mise en œuvre classique). Nous avons également montré comment ces techniques peuvent être exploitées pour offrir de meilleurs compromis performance/consommation sur certains types de noyaux de calculs.

Underspecified 1-synchronous clocks and non-determinism

Guillaume IOOSS, ENS, Paris

Slides

Early work on a compiler flow for emerging variable precis

Tiago Trevisan Jost – CEA LETI, Grenoble

Slides

« Most computations on real numbers manipulate them as floating point (FP) numbers encoded in a limited precision, i.e., finite number of bits. Determining the precision necessary to a given application is a difficult task. If too many bits are employed, time, memory and power are wasted in computing useless bits. If the number of bits is not sufficient algorithms may not converge or the results are numerically wrong. To support precision optimization, flexible FP formats emerge, e.g., Unum, Posit. This talk will highlight the compiler-level problems in optimization and code generation related to variable precision formats. »

Data-Flow/Dependence Profiling for Structured Transformations

Fabian Gruber – Inria Grenoble

Slides

Building of a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of non-Affine Programs Scalable

Manuel Selva – Inria Grenoble

Slides