Les Components-Off-The-Shelf (COTS) sont utilisés pour le développement rapide et efficace de logiciels tout en limitant le coût. Il est important de tester le fonctionnement des composants dans le nouvel environnement. Pour les logiciels tiers,le code source des composants, les spécifications et les modèles complets ne sont pas disponibles. Dans la littérature de tels systèmes sont appelés composants “boîte noire”. Nous pouvons vérifier leur fonctionnement avec des tests en boîte noire tels que le test de non-régression, le test aléatoire ou le test à partir de modèles. Pour ce dernier, un modèle qui représente le comportement attendu du système sous test(SUT) est nécessaire. Ce modèle contient un ensemble d’entrées, le comportement du SUT après stimulation par ces entrées et l’état dans lequel le système se trouve.Pour les systèmes en boîte noire, les modèles peuvent être extraits à partir des traces d’exécutions, des caractéristiques disponibles ou encore des connaissances des experts. Ces modèles permettent ensuite d’orienter le test de ces systèmes.Les techniques d’inférence de modèles permettent d’extraire une information structurelle et comportementale d’une application et de la présenter sous forme d’un modèle formel. Le modèle abstrait appris est donc cohérent avec le comportement du logiciel. Cependant, les modèles appris sont rarement complets et il est difficile de calculer le nombre de tests nécessaires pour apprendre de façon complète et précise un modèle.Cette thèse propose une analyse et des améliorations de la version Mealy de l’algorithme d’inférence L* [Angluin 87]. Elle vise à réduire le nombre de tests nécessaires pour apprendre des modèles. La version Mealy de L* nécessite d’utiliser deux types de test. Le premier type consiste à construire les modèles à partir des sorties du système, tandis que le second est utilisé pour tester l’exactitude des modèles obtenus. L’algorithme utilise ce que l’on appelle une table d’observation pour enregistrer les réponses du système.Le traitement d’un contre-exemple peut exiger d’envoyer un nombre conséquent de requêtes au système. Cette thèse aborde ce problème et propose une technique qui traite les contre-exemples de façon efficace. Nous observons aussi que l’apprentissage d’un modèle ne nécessite pas de devoir remplir complètement ces tables. Nous proposons donc un algorithme d’apprentissage qui évite de demander ces requêtes superflues.Dans certains cas, pour apprendre un modèle, la recherche de contre-exemples peut coûter cher. Nous proposons une méthode qui apprend des modèles sans demander et traiter des contre-exemples. Cela peut ajouter de nombreuses colonnes à la table d’observation mais au final, nous n’avons pas besoin d’envoyer toutes les requêtes. Cette technique ne demande que les requêtes nécessaires.Ces contributions réduisent le nombre de tests nécessaires pour apprendre des modèles de logiciels, améliorant ainsi la complexité dans le pire cas. Nous présentons les extensions que nous avons apportées à l’outil RALT pour mettre en oeuvre ces algorithmes. Elles sont ensuite validées avec des exemples tels que les tampons, les distributeurs automatiques, les protocoles d’exclusion mutuelle et les planificateurs. / Components-Off-The-Shelf (COTS) are used for rapid and cost effective developmentof software systems. It is important to test the correct functioning of COTS in new environment. For third party software components source code, completes pecifications and models are not available. In literature such systems are referred as black box software components. Their proper functioning in new environment can be tested with black box testing techniques like, comparison testing, fuzz testing, Model based testing. For Model based software testing, software models are required, which represent the desired behavior of a system under test (SUT). A software model shows that a certain set of inputs are applicable to the SUT and how it behaves when these inputs are applied under different circumstances. For software black box systems, models can be learned from behavioral traces, available specifications, knowledge of experts and other such sources. The software models steer the testing of software systems. The model inference algorithms extractstructural and design information of a software system and present it as a formal model. The learned abstract software model is consistent with the behavior of the particular software system. However, the learned models are rarely complete and it is difficult to calculate the number of tests required to learn precise and complete model of a software system. The thesis provides analysis and improvements on the Mealy adaptation of the model inference algorithm L* [Angluin 87]. It targets at reducing the number oftests required to learn models of software systems. The Mealy adaptation of thealgorithm L* requires learning models by asking two types of tests. First type oftests are asked to construct models i.e. output queries, whereas the second type is used to test the correctness of these models i.e. counterexamples. The algorithm uses an observation table to record the answers of output queries. Processing a counterexample may require a lot of output queries. The thesis addresses this problem and proposes a technique which processes the counterexamples efficiently. We observe that while learning the models of software systems asking output queries for all of the observation table rows and columns is not required. We propose a learning algorithm that avoids asking output queries for such observationtable rows and columns. In some cases to learn a software model, searching for counterexamples may govery expensive. We have presented a technique which learns the software models without asking and processing counterexamples. But this may add many columns to the observation table and in reality we may not require to ask output queries for all of the table cells. This technique asks output queries by targeting to avoid asking output queries for such cells. These contributions reduce the number of tests required to learn software models, thus improving the worst case learning complexity. We present the tool RALT which implements our techniques and the techniques are validated by inferring the examples like buffers, vending machines, mutual exclusion protocols and schedulers.

Les Components-Off-The-Shelf (COTS) sont utilisés pour le développement rapide et efficace de logiciels tout en limitant le coût. Il est important de tester le fonctionnement des composants dans le nouvel environnement. Pour les logiciels tiers,le code source des composants, les spécifications et les modèles complets ne sont pas disponibles. Dans la littérature de tels systèmes sont appelés composants "boîte noire". Nous pouvons vérifier leur fonctionnement avec des tests en boîte noire tels que le test de non-régression, le test aléatoire ou le test à partir de modèles. Pour ce dernier, un modèle qui représente le comportement attendu du système sous test(SUT) est nécessaire. Ce modèle contient un ensemble d'entrées, le comportement du SUT après stimulation par ces entrées et l'état dans lequel le système se trouve.Pour les systèmes en boîte noire, les modèles peuvent être extraits à partir des traces d'exécutions, des caractéristiques disponibles ou encore des connaissances des experts. Ces modèles permettent ensuite d'orienter le test de ces systèmes.Les techniques d'inférence de modèles permettent d'extraire une information structurelle et comportementale d'une application et de la présenter sous forme d'un modèle formel. Le modèle abstrait appris est donc cohérent avec le comportement du logiciel. Cependant, les modèles appris sont rarement complets et il est difficile de calculer le nombre de tests nécessaires pour apprendre de façon complète et précise un modèle.Cette thèse propose une analyse et des améliorations de la version Mealy de l'algorithme d'inférence L* [Angluin 87]. Elle vise à réduire le nombre de tests nécessaires pour apprendre des modèles. La version Mealy de L* nécessite d'utiliser deux types de test. Le premier type consiste à construire les modèles à partir des sorties du système, tandis que le second est utilisé pour tester l'exactitude des modèles obtenus. L'algorithme utilise ce que l'on appelle une table d'observation pour enregistrer les réponses du système.Le traitement d'un contre-exemple peut exiger d'envoyer un nombre conséquent de requêtes au système. Cette thèse aborde ce problème et propose une technique qui traite les contre-exemples de façon efficace. Nous observons aussi que l'apprentissage d'un modèle ne nécessite pas de devoir remplir complètement ces tables. Nous proposons donc un algorithme d'apprentissage qui évite de demander ces requêtes superflues.Dans certains cas, pour apprendre un modèle, la recherche de contre-exemples peut coûter cher. Nous proposons une méthode qui apprend des modèles sans demander et traiter des contre-exemples. Cela peut ajouter de nombreuses colonnes à la table d'observation mais au final, nous n'avons pas besoin d'envoyer toutes les requêtes. Cette technique ne demande que les requêtes nécessaires.Ces contributions réduisent le nombre de tests nécessaires pour apprendre des modèles de logiciels, améliorant ainsi la complexité dans le pire cas. Nous présentons les extensions que nous avons apportées à l'outil RALT pour mettre en oeuvre ces algorithmes. Elles sont ensuite validées avec des exemples tels que les tampons, les distributeurs automatiques, les protocoles d'exclusion mutuelle et les planificateurs.

Le test est une approche efficace pour détecter des bogues d'implémentation ayant un impact sur la sécurité, c.a.d. des vulnérabilités. Lorsque le code source n'est pas disponible, il est nécessaire d'utiliser des techniques de test en boîte noire. Nous nous intéressons au problème de détection automatique d'une classe de vulnérabilités (Cross Site Scripting alias XSS) dans les applications web dans un contexte de test en boîte noire. Nous proposons une approche pour inférer des modèles de telles applications et frelatons des séquences d'entrées générées à partir de ces modèles et d'une grammaire d'attaque. Nous inférons des automates de contrôle et de teinte, dont nous extrayons des sous-modèles afin de réduire l'espace de recherche de l'étape de frelatage. Nous utilisons des algorithmes génétiques pour guider la production d'entrées malicieuses envoyées à l'application. Nous produisons un verdict de test grâce à une double inférence de teinte sur l'arbre d'analyse grammaticale d'un navigateur et à l'utilisation de motifs de vulnérabilités comportant des annotations de teinte. Nos implémentations LigRE et KameleonFuzz obtiennent de meilleurs résultats que les scanneurs boîte noire open-source. Nous avons découvert des XSS ``0-day'' (c.a.d. des vulnérabilités jusque lors inconnues publiquement) dans des applications web utilisées par des millions d'utilisateurs. / Testing is a viable approach for detecting implementation bugs which have a security impact, a.k.a. vulnerabilities. When the source code is not available, it is necessary to use black-box testing techniques. We address the problem of automatically detecting a certain class of vulnerabilities (Cross Site Scripting a.k.a. XSS) in web applications in a black-box test context. We propose an approach for inferring models of web applications and fuzzing from such models and an attack grammar. We infer control plus taint flow automata, from which we produce slices, which narrow the fuzzing search space. Genetic algorithms are then used to schedule the malicious inputs which are sent to the application. We incorporate a test verdict by performing a double taint inference on the browser parse tree and combining this with taint aware vulnerability patterns. Our implementations LigRE and KameleonFuzz outperform current open-source black-box scanners. We discovered 0-day XSS (i.e., previously unknown vulnerabilities) in web applications used by millions of users.

Les abeilles sont des pollinisateurs essentiels pour les cultures et les plantes sauvages, mais l'intensification des pratiques agricoles a engendré une baisse importante de leur abondance et diversité. Afin de protéger efficacement les abeilles dans les paysages agricoles, il est nécessaire d'avoir une meilleure connaissance de leurs patrons de diversité. L'objectif général de cette thèse était de déterminer les patrons spatio-temporels de la diversité des abeilles et l'utilisation des ressource fleuries dans un système agricole intensif. L'échantillonnage spatialement extensif de l'activité de butinage des abeilles sauvages et domestiques nous a permis de recenser 45040 individus (29314 abeilles domestiques et 15726 sauvages), appartenant à 192 espèces recensées à l'échelle territoriale. Cette diversité représente près de 20% de la richesse des espèces apiformes connues à l'échelle nationale. Cette communauté est caractérisée par une forte proportion d'espèces rares (28,8%) et de fortes variations temporelles et spatiales, en particulier de l'échelle locale jusqu'à 10-20 km2. L'importance des habitats semi-naturels pour soutenir les populations d'abeilles sauvages a été confirmée dans cette étude. Durant les périodes de floraison des cultures oléagineuses, les abeilles sauvages étaient étroitement associées aux habitats semi-naturels alors que les abeilles domestiques ont montré une nette préférence pour les cultures à floraison massive. La diversité des abeilles sauvages dans les habitats semi- naturels était 3-4 fois supérieure à celle observée dans le colza ou le tournesol. L'importance de certains facteurs écologiques clefs pour la diversité des abeilles, comme la richesse floristique locale et la quantité d'habitats semi-naturels dans le paysage, a été confirmée et quantifiée. Il a également été démontré que ces effets varient en fonction de la saison et de l'échelle spatiale. Ces résultats mettent en évidence les processus écologiques responsables des partons de diversité des abeilles à différentes échelles spatiales, et peuvent contribuer à optimiser la conception des mesures de conservation visant à promouvoir la diversité des abeilles dans les agrosystèmes intensifs. / Bees are essential pollinators for crops and wild plants, but theintensification of agricultural practices have contributed to a significantdecline in their abundance and diversity. To effectively protect andpromote the bee fauna in agroecosystems, a better knowledge of theirdiversity patterns is required. The over-arching objective of this thesiswas to determine the spatial and temporal patterns of bee diversity andfloral resource use in an intensive agricultural system in western France.A spatially extensive survey of foraging wild bees and honey bees returned45.040 individual records at the territorial scale (29.314 honey bees and15.726 wild bees), representing 192 species, i.e. nearly 20% of the speciesrichness reported at the national scale. The bee community wascharacterised by a large proportion of uncommon species (28.8 %) and bysignificant temporal and spatial variations of the diversity, especially atlocal scales up to 10-20 km2. The importance of semi-natural habitats forsustaining wild bee populations was highlighted in this study. Duringoleaginous crop flowering periods, wild bees were tightly associated withsemi-natural habitats while honey bees have shown a clear preference formass-flowering crops. The diversity of foraging wild bees was 3-4 timesgreater in semi-natural habitats than in oilseed rape or sunflower fields.The importance of some keystone ecological correlates of bee diversity,such as the local floral richness and the amount of semi-natural habitatsin the vicinity, has been confirmed and quantified. It was also evidencedthat their effect varies among seasons and spatial scales. These resultshighlight the ecological processes underlying bee diversity patterns atdifferent spatial scales, and further help to optimise the efficiency ofconservation measures intended to promote bee diversity in intensiveagrosystems.

Les abeilles sont des pollinisateurs essentiels pour les cultures et les plantes sauvages, mais l'intensification des pratiques agricoles a engendré une baisse importante de leur abondance et diversité. Afin de protéger efficacement les abeilles dans les paysages agricoles, il est nécessaire d'avoir une meilleure connaissance de leurs patrons de diversité. L'objectif général de cette thèse était de déterminer les patrons spatio-temporels de la diversité des abeilles et l'utilisation des ressource fleuries dans un système agricole intensif. L'échantillonnage spatialement extensif de l'activité de butinage des abeilles sauvages et domestiques nous a permis de recenser 45040 individus (29314 abeilles domestiques et 15726 sauvages), appartenant à 192 espèces recensées à l'échelle territoriale. Cette diversité représente près de 20% de la richesse des espèces apiformes connues à l'échelle nationale. Cette communauté est caractérisée par une forte proportion d'espèces rares (28,8%) et de fortes variations temporelles et spatiales, en particulier de l'échelle locale jusqu'à 10-20 km2. L'importance des habitats semi-naturels pour soutenir les populations d'abeilles sauvages a été confirmée dans cette étude. Durant les périodes de floraison des cultures oléagineuses, les abeilles sauvages étaient étroitement associées aux habitats semi-naturels alors que les abeilles domestiques ont montré une nette préférence pour les cultures à floraison massive. La diversité des abeilles sauvages dans les habitats semi- naturels était 3-4 fois supérieure à celle observée dans le colza ou le tournesol. L'importance de certains facteurs écologiques clefs pour la diversité des abeilles, comme la richesse floristique locale et la quantité d'habitats semi-naturels dans le paysage, a été confirmée et quantifiée. Il a également été démontré que ces effets varient en fonction de la saison et de l'échelle spatiale. Ces résultats mettent en évidence les processus écologiques responsables des partons de diversité des abeilles à différentes échelles spatiales, et peuvent contribuer à optimiser la conception des mesures de conservation visant à promouvoir la diversité des abeilles dans les agrosystèmes intensifs.