Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

The complexity of our software is greater than ever. Previously, a programmer could know all the instructions of his processor by heart and he created his own applications and games. Now programmers can use multi-language technologies, transcompilers, scripts, native code, and a lot more. Parallel and distributed code also adds a new layer of complexity. And this software, this code, is everywhere in our lives. It’s in our planes, our cars, our thermal power plants, our computers, our phones and so many other places. In order for our lives to unfold as planned, all this programming must therefore be reliable. In the old days, the problems of small programs could be solved by their creator, with a sheet of paper and concentration. Today we use computers, to test computers. All of this brings us to software tests. Directly testing software is the most popular method to gain confidence in its behavior. Combinatorial tests are particularly interesting because it has been observed that in practice, tests of a certain interaction strength are as effective in finding bugs as a brute-force approach which enumerates all the possibilities. Our thesis therefore focuses on combinatorial tests. In particular, we propose a generalization of t-way testing in Φ-way testing, which gives us a better system to add constraints to our tests. Then, by reducing to a graph coloring or hypergraph vertex covering problem, we can take advantage of existing algorithms and methods to solve the problem. Subsequently, we looked at the problem of scalability, because graphs and hypergraphs are memory and cpu intensive. We used the Apache Spark technology, a technology typically used for Big Data processing, to implement distributed algorithms for graphs and hypergraphs. We have made original contributions in the development of these algorithms. We have also created a hybrid algorithm called "Distributed IPOG". We tested these algorithms on a cluster of computers provided by Compute Canada, an organization for Canadian researchers. We compared the results with those calculated by existing tools, to see that our algorithms produce competitive test suites, and can adapt to large sizes of problems. However, these algorithms are slower to execute than non-distributed solutions, which is explained by network latency and the different needs of this technology. In the future, with improvements to distributed technologies and improvements in hardware, we predict that distributed approaches will become even more interesting. Our algorithms, as well as the execution script for the Compute Canada cluster are open-source and available on GitHub with the TSPARK project.

Meme si l’informatique est encore une discipline assez jeune, la complexite de nos logiciels est à present plus grande que jamais. Auparavant, un programmeur pouvait connaitre toutes les instructions de son processeur par coeur et il creait lui-meme ses applications et ses jeux. Maintenant les programmeurs peuvent utiliser des technologies multi-langages, des transcompilateurs, des scripts, du code natif et beaucoup d’autres choses. Le code parallele et distribue ajoute egalement une nouvelle couche de complexite. Et ces logiciels, ce code, est omnipresent dans nos vies. Il est dans nos avions, nos voitures, nos centrales thermiques, nos ordinateurs, nos telephones et dans tellement d’autres endroits. Pour que nos vies puissent se derouler comme prevu, il faut donc que toute cette programmation soit fiable. Autrefois, les problemes des petits programmes pouvaient etre resolus par leur createur, avec une feuille de papier et de la concentration. De nos jours nous devons utiliser des ordinateurs pour tester des ordinateurs. Tout ceci nous amene aux tests. Tester directement un logiciel est la methode la plus repandue pour valider le comportement de celui-ci. Les tests combinatoires sont notamment interessants car il a ete observe qu’en pratique, les tests combinatoires non-exhaustifs sont aussi efficaces pour trouver les bugs qu’une approche de force brute qui enumere toutes les possibilites. Notre these porte donc sur les tests combinatoires. Notamment, nous proposons une generalisation du t-way testing en Φ-way testing, ce qui nous permet d’avoir un meilleur systeme pour ajouter des contraintes aux parametres qu’on teste. Ensuite, en transformant ce probleme NPComplet en un probleme de coloriage de graphe, et en probleme de couverture par ensembles, nous pouvons prendre avantage des methodes existantes pour resoudre ces problemes. Par la suite, nous nous sommes interesses au probleme de la scalabilite, car les graphes et hypergraphes sont gourmands en memoire. Nous avons utilise la technologie Apache Spark, une technologie typiquement utilisee par les entreprises pour faire du traitement de donnees massives, pour implementer des algorithmes distribues pour les graphes et hypergraphes. Nous avons fait des contributions originales dans l’elaboration de ces algorithmes. Nous avons egalement cree un algorithme hybride appele “Distributed IPOG”. Nous avons teste ces algorithmes sur un cluster d’ordinateurs fourni par Calcul Canada, un organisme pour les chercheurs canadiens. Nous avons compare les resultats avec ceux calcules par des outils existants, pour constater que nos algorithmes calculent des solutions de qualite, et peuvent s’adapter a des grandes tailles de problemes. Cependant, ces algorithmes sont plus lents a executer que les solutions non-distribuees, ce qui s’explique par les temps de transport et les besoins differents de cette technologie. Dans le futur, avec les ameliorations aux technologies distribuees et les ameliorations materielles, nous predisons que les approches distribuees deviendront encore plus interessantes. Nos algorithmes, ainsi que le script d’execution pour le cluster de Calcul Canada sont open-source et disponibles sur GitHub avec le projet TSPARK.