Analyse et optimisation d'algorithmes pour l'inférence de modèles de composants logiciels

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