Extended combinatorial testing using graph algorithms and Apache Spark
Bibliographic record
Abstract
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. \n \nMeme 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.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.004 | 0.016 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.003 |
| Bibliometrics | 0.002 | 0.003 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.003 | 0.005 |
| Open science | 0.005 | 0.004 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.007 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".