Xavier Devroey, program co-chair du 13eme international Symposium on Search-Based Software Engineering

La 13eme édition du symposium sur le Search-Based Software Engineering (SSBSE ’21) s’est déroulée ces 11 et 12 octobre dernier en ligne. Ce symposium a lieu chaque année et regroupe les spécialistes du domaine en Evolutionary Computation appliqué au génie logiciel (SBSE). La professeure Una-May O’Reilly du MIT et Xavier Devroey, program co-chairs, étaient en charge du programme scientifique.

En tant que program co-chairs, leur tâche consistait principalement en la gestion de la bonne marche du processus de soumission, de revue par les pairs, de sélection des papiers présentés lors du symposium et de l’édition des actes de la conférence. La professeure Aldeida Aleti de l’Université de Monash (Australie) était également invitée à donner la présentation d’ouverture dans laquelle elle a exposé ses travaux sur l’analyse d’instances de problèmes d’optimisation et l’efficacité de différentes techniques de SBSE sur ceux-ci. 

Approches de Search-Based Software Engineering, késako ?

Le but des approches de SBSE est de trouver des solutions suffisamment satisfaisantes à des problèmes complexes, pour lesquels une solution exacte ou parfaite n’est pas calculable par un ordinateur dans un temps acceptable. Par exemple, la génération automatique de tests est l’une des grandes réussites de la recherche en SBSE et est en train de se déployer dans l’industrie. Les approches de SBSE s’inspirent notamment de la théorie de l’évolution : une population d’individus, représentant des solutions potentielles (mais probablement pas optimales) au problème traité, est générée aléatoirement et va évoluer sur plusieurs générations au travers de reproductions (sexuées ou non) successives.

Définir un ensemble minimal de tests satisfaisant un critère donné (tel qu’exécuter au moins une fois chaque ligne de code du programme) demanderait de pouvoir sélectionner l’ensemble minimum des exécutions possibles satisfaisant ce critère, ce qui est théoriquement (et, à fortiori, pratiquement) impossible. Pour pallier à ce problème, une approche SBSE va typiquement utiliser un algorithme génétique dans lequel un ensemble de taille fixe de suites de tests est généré aléatoirement pour former la population initiale. Cette population va ensuite évoluer au travers de reproductions (sexuées) successives où, en fonction de la stratégie choisie, deux suites de tests sont sélectionnées pour former un nouvel individu en utilisant des opérateurs (dits) génétiques de crossover et de mutation. Une fois un certain nombre de nouvelles suites générées, la nouvelle population est évaluée pour retirer les individus les moins intéressants (couvrant le moins de lignes de code) avant de subir une nouvelle évolution. Un algorithme génétique va itérer jusqu’à épuiser le budget qui lui est accordé (en général, il s’agit d’un temps maximum d’exécution). Le meilleur individu (la suite de test couvrant le plus de lignes de code) est alors sélectionné parmi la population finale.

Ces approches ont été appliquées pour la génération de tests unitaires pour des programmes Java et Python, de tests systèmes pour des applications Android, mais aussi pour des systèmes embarqués dans des véhicules autonomes en générant des scénarios simulant différentes conditions de conduite.

Dans sa recherche, Xavier Devroey applique des approches de génération automatique de tests permettant de reproduire un crash applicatif ou de mettre en évidence de mauvaises utilisations d’interfaces de programmation. 

Plus d’information à propos du symposium sont disponible sur le site https://conf.researchr.org/home/ssbse-2021.

Contact : Xavier Devroey - xavier.devroey@unamur.be