Les systèmes embarqués sont largement utilisés de nos jours. Pour des raisons d'efficacité, les plus contraints en termes de ressources sont toujours programmés en C et en assembleur. L'adoption de langages de plus haut niveau tels que C# ou Java offrirait plus d'abstraction au programmeur, ce qui réduirait les temps de développement et par conséquent le coût de ces systèmes. Certains d'entre eux ont déjà migré vers de tels langages, comme les téléphones mobiles ou les tablettes tactiles, mais ils sont équipés d'une grande quantité de mémoire externe et ne reflètent pas la majorité des systèmes embarqués.Cette thèse s'intéresse à l'implémentation de Java et .NET pour l'embarqué, et plus spécifiquement à la compilation efficace du polymorphisme. Ce polymorphisme génère un certain coût à l'exécution, comme des indirections dans le cas des appels de méthodes (polymorphisme d'inclusion), ou de la duplication de code dans le cas de la généricité (polymorphisme paramétrique). De nombreuses techniques d'implémentation ont été proposées, notamment pour Java. Il reste cependant à identifier lesquelles sont applicables pour le type de systèmes que nous ciblons, et à en concevoir de nouvelles pour certains aspects comme la généricité. Nous partons du principe que les techniques globales (hypothèse du monde clos) sont les mieux adaptées. Par l'analyse de types, nous détectons qu'une partie importante des programmes est monomorphe et qu'elle peut donc être compilée sans surcoût. Pour implémenter le polymorphisme restant, nous choisissons la technique la mieux adaptée au matériel cible. Nous proposons également une implémentation de la généricité qui est adaptée aux systèmes embarqués. D'après nos évaluations, l'impact négatif du polymorphisme sur l'efficacité est largement réduit. L'efficacité du code optimisé devrait s'approcher de celle du C, et les techniques que nous employons pourraient être applicables dans le contexte plus général du chargement dynamique. / Nowadays, embedded systems are ubiquitous. For efficiency reasons, most constrained systems are still programmed in C and assembly. Adopting higher-level languages such as C# or Java should enhance the level of abstraction offered to programmers and reduce development time and cost for these systems. A small part of them have migrated to such languages, like smartphones and tablet computers, but they have a large amount of external memory available and do not represent the majority of embedded systems.This thesis focuses on the implementation of Java and .NET for embedded systems, and more especially on the efficient compilation of polymorphism. Polymorphism generates an overhead at run-time, such as indirections when methods are invoked (inclusion polymorphism) or code duplication in the case of generics (parametric polymorphism). Many implementation techniques have been proposed, especially for Java. However, it remains to identify which ones are applicable in the context of low-end embedded systems. We consider that whole program optimization (closed-world assumption) is well-suited in this context. Using type analysis, we observe that most part of programs is monomorph, therefore it can be compiled with no overhead with respect to C. In order to implement the remaining polymorphism, we choose the technique which is better suited for the target hardware. We also propose an appropriate implementation of run-time generics. Our results show that the negative impact of polymorphism is mostly reduced. The efficiency of the optimized code should be comparable with C, and the techniques we employ could be applicable in the context of dynamic loading (open-world assumption).

Sans exécuter une application, est-il possible de prévoir quelle est la méthode cible d’un site d’appel ? Est-il possible de savoir quels sont les types et les valeurs qu’une expression peut contenir ? Est-il possible de déterminer de manière exhaustive l’ensemble de comportements qu’une application peut effectuer ? Dans les trois cas, la réponse est oui, à condition d’accepter une certaine approximation. Il existe une classe d’algorithmes − peu connus à l’extérieur du cercle académique − qui analysent et simulent un programme pour calculer de manière conservatrice l’ensemble des informations qui peuvent être véhiculées dans une expression.Dans cette thèse, nous présentons ces algorithmes appelés CFAs (acronyme de Control Flow Analysis), plus précisément l’algorithme multivariant k-l-CFA. Nous combinons l’algorithme k-l-CFA avec l’analyse de taches (taint analysis),qui consiste à suivre une donnée sensible dans le flot de contrôle, afin de déterminer si elle atteint un puits (un flot sortant du programme). Cet algorithme, en combinaison avec l’interprétation abstraite pour les valeurs, a pour objectif de calculer de manière aussi exhaustive que possible l’ensemble des comportements d’une application. L’un des problèmes de cette approche est le nombre élevé de faux-positifs, qui impose un post-traitement humain. Il est donc essentiel de pouvoir augmenter la précision de l’analyse en augmentant k.k-l-CFA est notoirement connu comme étant très combinatoire, sa complexité étant exponentielle dans la valeur de k. La première contribution de cette thèse est de concevoir un modèle et une implémentation la plus efficace possible, en séparant soigneusement les parties statiques et dynamiques de l’analyse, pour permettre le passage à l’échelle. La seconde contribution de cette thèse est de proposer une nouvelle variante de CFA basée sur k-l-CFA, et appelée *-CFA, qui consiste à faire du paramètre k une propriété de chaque variante, de façon à ne l’augmenter que dans les contextes qui le justifient.Afin d’évaluer l’efficacité de notre implémentation de k-l-CFA, nous avons effectué une comparaison avec le framework Wala. Ensuite, nous validons l’analyse de taches et la détection de comportements avec le Benchmark DroidBench. Enfin, nous présentons les apports de l’algorithme *-CFA par rapport aux algorithmes standards de CFA dans le contexte d’analyse de taches et de détection de comportements. / Without executing an application, is it possible to predict the target method of a call site? Is it possible to know the types and values that an expression can contain? Is it possible to determine exhaustively the set of behaviors that an application can perform? In all three cases, the answer is yes, as long as a certain approximation is accepted.There is a class of algorithms - little known outside of academia - that can simulate and analyze a program to compute conservatively all information that can be conveyed in an expression. In this thesis, we present these algorithms called CFAs (Control flow analysis), and more specifically the multivariant k-l-CFA algorithm.We combine k-l-CFA algorithm with taint analysis, which consists in following tainted sensitive data inthe control flow to determine if it reaches a sink (an outgoing flow of the program).This combination with the integration of abstract interpretation for the values, aims to identify asexhaustively as possible all behaviors performed by an application.The problem with this approach is the high number of false positives, which requiresa human post-processing treatment.It is therefore essential to increase the accuracy of the analysis by increasing k.k-l-CFA is notoriously known as having a high combinatorial complexity, which is exponential commensurately with the value of k.The first contribution of this thesis is to design a model and most efficient implementationpossible, carefully separating the static and dynamic parts of the analysis, to allow scalability.The second contribution of this thesis is to propose a new CFA variant based on k-l-CFA algorithm -called *-CFA - , which consists in keeping locally for each variant the parameter k, and increasing this parameter in the contexts which justifies it.To evaluate the effectiveness of our implementation of k-l-CFA, we make a comparison with the Wala framework.Then, we do the same with the DroidBench benchmark to validate out taint analysis and behavior detection. Finally , we present the contributions of *-CFA algorithm compared to standard CFA algorithms in the context of taint analysis and behavior detection.

Actuellement, la restauration des oeuvres d’art, notamment des statues fracturées, repose sur des techniqueséprouvées, mais empiriques. Les statues endommagées comportent souvent des parties brisées. Leur restaurationconsiste la plupart du temps à les rassembler. Ainsi apparait la nécessité de prendre en compte lespropriétés mécaniques des interfaces entre les différentes parties brisées, ce qui permet de limiter l’ampleur desréparations et ainsi, de mieux conserver l’intégrité de l’oeuvre. Par ailleurs, les techniques numériques d’acquisition3D font leur entrée au service de la conservation du patrimoine. Cette thèse propose une méthodologiecapable d’utiliser des données issues d’une acquisition 3D pour simuler les opérations de restauration et leurseffets sur la structure de l’oeuvre. Les processus de restauration peuvent ainsi être testés et optimisés.Un scanner laser est utilisé pour l’acquisition de la géométrie des oeuvres, ce qui nous permet de reconstruireun modèle 3D pour la simulation numérique. Les calculs sont menés dans le cadre de la mécanique des milieuxcontinus déformables avec FLAC3D. Pour vérifier tous les points clés garantissant la stabilité mécanique, lecomportement des éléments de renforts et celui des interfaces entre les blocs ont été considérés. À partirdes résultats de ces études, une critique des stratégies de restauration mises en oeuvre ou envisageables estproposée.De plus, plusieurs méthodes de caractérisation visant à retrouver la provenance du matériau et/ou estimerles propriétés mécaniques de l’oeuvre sont proposées : caractérisations physico-chimiques et minéralogiques,essais non destructifs et destructifs. Une campagne expérimentale visant à caractériser le comportement desfractures en contact frottant avec acquisition de l’état de surface a été réalisée. Une analyse des corrélationsentre les propriétés mécaniques et morphologique des interfaces est ensuite élaborée. Enfin nous proposonsdes modèles prédictifs construits par régressions linéaires multiples et multivariées. Cette étude permet desimuler le comportement d’une oeuvre fracturée. / Currently, the artworks restoration, including broken statues, are based on proven but empirical techniques. Damaged statues often have broken parts. Restoration mainly consists in joining these parts. Thus appears the necessity of taking into account the interfaces mechanical properties between the different broken parts, reducing thereby the extent of repairs and thus better maintain the integrity of the work. Beside this, digital 3D acquisition techniques become more and more popular among the cultural heritage community. This thesis proposes a methodology able to use 3D acquisition datas to simulate the restoration operations and their effects on the structure. The restoration strategy can thus be tested and optimized. A laser scanner is used to acquire the statue geometry, allowing to reconstruct a 3D model for numerical simulation. Computations are carried out within the framework of deformable continuum mechanics using the FLAC3D software. In order to check all the key points ensuring mechanical stability, the behavior of reinforcing elements and those of the interfaces between blocks were considered. From the results of the present studies, a critical analysis of implemented or possible restoration strategy is proposed. In addition, several characterization methods to find the material origin and/or estimate the mechanical properties of the work are proposed : physico-chemical and mineralogical characterizations, non-destructive and destructive tests. An experimental campaign to characterize the behavior of fractures in contact with surface acquisition was performed. An analysis of correlations between mechanical and morphological interfaces properties is then developed. Finally, we propose a predictive modelling based on multiple linear and multivariate regressions. This study allow the simulation of fractured artworks behaviour.

Les systèmes critiques basés sur l’arithmétique flottante exigent un processus rigoureux de vérification et de validation pour augmenter notre confiance en leur sureté et leur fiabilité. Malheureusement, les techniques existentes fournissent souvent une surestimation d’erreurs d’arrondi. Nous citons Arian 5 et le missile Patriot comme fameux exemples de désastres causés par les erreurs de calculs. Ces dernières années, plusieurs techniques concernant la transformation d’expressions arithmétiques pour améliorer la précision numérique ont été proposées. Dans ce travail, nous allons une étape plus loin en transformant automatiquement non seulement des expressions arithmétiques mais des programmes complets contenant des affectations, des structures de contrôle et des fonctions. Nous définissons un ensemble de règles de transformation permettant la génération, sous certaines conditions et en un temps polynômial, des expressions pluslarges en appliquant des calculs formels limités, au sein de plusieurs itérations d’une boucle. Par la suite, ces larges expressions sont re-parenthésées pour trouver la meilleure expression améliorant ainsi la précision numérique des calculs de programmes. Notre approche se base sur les techniques d’analyse statique par interprétation abstraite pour sur-rapprocher les erreurs d’arrondi dans les programmes et au moment de la transformation des expressions. Cette approche est implémenté dans notre outil et des résultats expérimentaux sur des algorithmes numériques classiques et des programmes venant du monde d’embarqués sont présentés. / Critical software based on floating-point arithmetic requires rigorous verification and validation process to improve our confidence in their reliability and their safety. Unfortunately available techniques for this task often provide overestimates of the round-off errors. We can cite Arian 5, Patriot rocket as well-known examples of disasters. These last years, several techniques have been proposed concerning the transformation of arithmetic expressions in order to improve their numerical accuracy and, in this work, we go one step further by automatically transforming larger pieces of code containing assignments, control structures and functions. We define a set of transformation rules allowing the generation, under certain conditions and in polynomial time, of larger expressions by performing limited formal computations, possibly among several iterations of a loop. These larger expressions are better suited to improve, by re-parsing, the numerical accuracy of the program results. We use abstract interpretation based static analysis techniques to over-approximate the round-off errors in programs and during the transformation of expressions. A tool has been implemented and experimental results are presented concerning classical numerical algorithms and algorithms for embedded systems.

Les attaques par canaux cachés sont une forme d'attaque particulièrement dangereuse. Dans cette thèse, nous nous intéressons au canal caché temporel. Un programme est dit ''constant-time'' lorsqu'il n'est pas vulnérable aux attaques par canal caché temporel. Nous présentons dans ce manuscrit deux méthodes reposant sur l'analyse statique afin de s'assurer qu'un programme est constant-time. Ces méthodes se placent dans le cadre de vérification formelle afin d'obtenir le plus haut niveau d'assurance possible en s'appuyant sur une chaîne de compilation vérifiée composée du compilateur CompCert et de l'analyseur statique Verasco. Nous proposons aussi une méthode de preuve afin de s'assurer qu'un compilateur préserve la propriété de constant-time lors de la compilation d'un programme. / Side-channel attacks are an especially dangerous form of attack. In this thesis, we focus on the timing side-channel. A program is said to be constant-time if it is not vulnerable to timing attacks. We present in this thesis two methods relying on static analysis in order to ensure that a program is constant-time. These methods use formal verification in order to gain the highest possible level of assurance by relying on a verified compilation toolchain made up of the CompCert compiler and the Verasco static analyzer. We also propose a proof methodology in order to ensure that a compiler preserves constant-time security during compilation.

Il est important que les logiciels pilotant les systèmes critiques (avions, centrales nucléaires, etc.) fonctionnent correctement — alors que la plupart des systèmes informatisés de la vie courante (micro-ordinateur, distributeur de billets, téléphone portable) ont des dysfonctionnements visibles. Il ne s'agit pas là d'un simple problème d'ingéniérie : on sait depuis les travaux de Turing et de Cook que la preuve de propriétés de bon fonctionnement sur les programmes est un problème intrinsèquement difficile.<br /><br />Pour résoudre ce problème , il faut des méthodes à la fois efficaces (coûts en temps et en mémoire modérés), sûres (qui trouvent tous les problèmes possibles) et précises (qui fournissent peu d'avertissements pour des problèmes inexistants). La recherche de ce compromis nécessite des recherches faisant appel à des domaines aussi divers que la logique formelle, l'analyse numérique ou l'algorithmique « classique ».<br /><br />De 2002 à 2007 j'ai participé au développement de l'outil d'analyse statique Astrée. Ceci m'a suggéré quelques développements annexes, à la fois théoriques et pratiques (utilisation de techniques de preuve formelle, analyse de filtres numériques...). Plus récemment, je me suis intéressé à l'analyse modulaire de propriétés numériques et aux applications en analyse de programme de techniques de résolution sous contrainte (programmation semidéfinie, techniques SAT et SAT modulo théorie).

Les plates-formes dynamiques de services (SOP, pour ?service-oriented programming') sont des environnements d'exécution génériques qui définissent un modèle d'architecture logicielle structuré: les composants communiquent par le biais d'interfaces explicites, ce qui facilite la configuration et l'évolution de ces systèmes. Les plates-formes SOP utilisent leur envi- ronnement réseau pour réaliser des tâches fonctionnelles, mais également pour améliorer leur capacité de gestion et d'évolution. Elles sont exploitées dans des contextes variés, des serveurs d'application aux systèmes embarqués médicaux ou automobiles. La flexibilité apportée par les plates-formes SOP permet l'intégration de composants de plusieurs sources aussi bien lors de la conception qu'à l'exécution. Cette tendance induit cependant un risque important. Peu d'outils existent pour évaluer la qualité des systèmes résultants, et aucun ne garantit que les composants sélectionnés ne sont pas malicieux. Dans des contextes applicatifs tels que les systèmes e-Business ou les systèmes embarqués sensibles, l'existence d'attaques n'est pas à exclure. L'assurance de sécurité logicielle (Software Security Assurance) définit des méthodes pour le développement d'applications sûres, mais se concentre sur les systèmes monolithiques. Son principe est le suivant: les vulnérabilités doivent être identifiées et résolues tôt dans le cycle de vie pour éviter les attaques lors de l'exécution et limiter les coûts de réparation. Cepen- dant, cette approche ne peut s'appliquer directement aux applications à composants, où le développement n'est pas nécessairement contrôlé par l'intégrateur, et où l'intégration peut avoir lieu à l'exécution de manière automatisée. Nous proposons par conséquent de réaliser une analyse de sécurité pour une plate-forme SOP de référence, la plate-forme OSGi, et de fournir des mécanismes de protection adaptés aux besoins ainsi identifiés. L'analyse de sécurité de la plate-forme OSGi est réalisée par une méthode spécifique, SPIP , le Processus Spirale de Prévention d'Intrusion (Spiral Process for Intrusion Prevention). Elle permet l'évaluation des vulnérabilités du système cible et de la protection apportée par les mécanismes de sécurité associés. Le résultat de l'analyse est : les vulnérabilités de la plate-forme Java/OSGi, et les vulnérabilités des composants SOP Java. Plusieurs mécanismes de protection sont développés pour prévenir l'exploitation des vul- nérabilités identifiées. Ils sont implémentés dans la plate-forme elle-même et au niveau des composants. OSGi Robuste (Hardened OSGi) est un ensemble de recommandations pour la mise en oeuvre de plates-formes OSGi résistantes. CBAC, le contrôle d'accès basé composants (Component-based Access Control) est un mécanisme de contrôle d'accès qui vérifie lors de l'installation qu'un composant n'exécute que les appels explicitement autorisés. Son objectif est d'être plus flexible que le gestion de sécurité Java, de garantir que seuls les composants valides soient installés et de réduire autant que possible le coût de vérification en terme de performance. WCA, l'analyse de composants faibles (Weak Component Analysis), est un outil pour identifier les vulnérabilités exploitables dans les composants SOP selon l'exposition des classes: les objets partagés tels les services SOP, les classes partagées et les classes internes des composants ne sont pas concernés par les mêmes vulnérabilités. Nos propositions sont validées par leur intégration avec une JVM sécurisée dédiée aux applications OSGi, la JnJVM. Les propriétés de sécurité de l'environnement ainsi réalisé sont encourageantes.

Par "approche langage" on entend désigner une approche qui s'exprime, soit dans un langage de programmation, soit par un langage de programmation.<br />Les approches qui s'expriment dans le langage ne font appel à aucun formalisme éloigné (e.g. sémantique). Le langage de programmation est l'unique cadre de travail pour exprimer le problème, le résoudre et appliquer la solution. Nous montrons :<br /><br />- comment la compilation des langages fonctionnels peut s'exprimer dans le langage lui-même par transformation de programme. Ce cadre unifié permet de décrire, prouver, comparer et classifier la plupart des mises en œuvre de langages fonctionnels,<br /><br />- deux optimisations de l'implémentation des langages fonctionnels (une analyse de globalisation et un GC étendu) qui reposent sur la syntaxe et le type des expressions.<br /><br /><br /> Pour les approches qui s'expriment par un langage de programmation, il s'agit de prévenir le problème ou d'assurer une propriété via l'utilisation d'un langage (ou d'une discipline de programmation). Nous illustrons ce style d'approche par trois exemples :<br /><br /><br />- les types graphes qui permettent de définir et vérifier le partage des structures de données à pointeurs,<br /><br />- un langage dédié au parallélisme qui garantit une analyse de coût précise et un choix automatique de la meilleure distribution,<br /><br />- un style de programmation par aspects qui permet d'imposer automatiquement des propriétés aux programmes.

Les Réseaux de Régulation Biologique (RRB) sont communément utilisés en biologie systémique pour modéliser, comprendre et contrôler les dynamiques de production des protéines au sein des cellules. Bien qu'offrant une représentation très abstraite des systèmes biologiques, l'analyse formelle de tels modèles se heurte rapidement à l'explosion combinatoire des comportements engendrés. Cette thèse traite de la modélisation, de la simulation et de la vérification formelle des grands RRB à travers l'introduction d'un nouveau formalisme : les Frappes de Processus. La simplicité de ce formalisme permet notamment l'élaboration d'analyses statiques efficaces des systèmes complexes en général. Cette thèse aborde en premier lieu le raffinement du temps dans les modèles stochastiques via l'introduction d'un facteur d'absorption de stochasticité. Ceci apporte un compromis et une flexibilité entre des spécifications temporelles et stochastiques dans les modélisations hybrides. Une simulation générique (non-markovienne) des calculs de processus est alors proposée et appliquée aux Frappes de Processus. En outre de l'analyse statique des points fixes des Frappes de Processus, cette thèse développe une interprétation abstraite de ces Frappes de Processus permettant des approximations supérieures et inférieures très efficaces de propriétés d'atteignabilité discrète. Cette analyse permet également de faire émerger des composants requis pour la satisfaction de ces propriétés, guidant ainsi le contrôle du système. D'une complexité théorique limitée, cette approche promet de supporter l'analyse de très grands RRB et constitue une ainsi contribution qui ouvre sur de multiples perspectives.

Les tâches critiques en systèmes temps-réel sont soumises à des contraintes temporelles et de correction. La validation d'un tel système repose sur l'estimation du comportement temporel au pire cas de ses tâches. Le partage de ressources, inhérent aux architectures multi-cœurs, entrave le calcul de ces estimations. Le comportement temporel d'une tâche dépend de ses rivales du fait de l'arbitrage de l'accès aux ressources ou de modifications concurrentes de leur état. Cette étude vise à l'estimation de la contribution temporelle de la hiérarchie mémoire au pire temps d'exécution de tâches critiques. Les méthodes existantes, pour caches d'instructions, sont étendues afin de supporter caches de données privés et partagés, et permettre l'analyse de hiérarchies mémoires riches. Le court-circuitage de cache est ensuite utilisé pour réduire la pression sur les caches partagés. Nous proposons à cette fin différentes heuristiques basées sur la capture de la réutilisation de blocs de cache entre différents accès mémoire. Notre seconde proposition est la politique de partitionnement Preti qui permet l'allocation d'un espace sans conflits à une tâche. Preti favorise aussi les performances de tâches non critiques concurrentes aux temps-réel dans les systèmes de criticité hybride.