Test case prioritization in highly-configurable systems

Abstract

Highly-configurable software systems (HCSs) provide a common core functionality and a set of optional features, where a feature represents an increment in system functionality. Development tools as Eclipse (with more than 3,000 plug-ins) or operating systems as Debian Wheezy (with more than 37,000 packages) have been reported as examples of HCSs. The large number of features that can be combined leading to thousands or even millions of individual software systems (a.k.a. configurations) makes the testing of HCSs a challenge. That is, testing every single configuration is too expensive in general. To overcome this problem, researchers have proposed numerous techniques mainly focused on reducing the space of testing to a manageable but representative subset of configurations to be tested. Nevertheless, even after reduce the test space, the number of configurations under test may still be large and expensive to run. In this dissertation, we address the testing of HCSs using test case prioritization, which schedules test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal, typically detect faults as quickly as possible. Test case prioritization approaches help to improve the effectiveness of testing allowing faster feedback to software testers and ensuring that test cases with the highest fault detection ability will have been executed if testing is stopped by any circumstance. Test case prioritization in HCSs can be driven by different functional and non–functional objectives, being an objective the order criterion used to accelerate the detection of faults. Functional prioritization objectives are based on the functional features of the system and their interactions. Non–functional prioritization objectives consider extra–functional information such as user preferences or cost. In this thesis we present thirteen objectives, techniques and tools for test case prioritization in HCSs. In particular, we define six objectives based on functional properties and seven objectives based on non–functional properties of the HCS under test. These objectives are evaluated using real data extracted from HCS Git repositories and bug tracking systems, which reinforces the validity of our conclusions. Regarding test case prioritization techniques, we present single–objective and multi-objective approaches based on evolutionary algorithms. Additionally, we report a comparison of 63 different com binations of up to three objectives to determine which combinations perform better in accelerating the detection of faults in an HCS. Furthermore, we propose an industrystrength HCS case study with more than 2 billions of configurations to be used as a realistic subject for further and reproducible validation of variability testing techniques. These contributions have been evaluated using extensive and rigorous experiments that reveal the efficacy and efficiency of our approach. Part of our contributions have been integrated into a tool called SmarTest for testing Drupal, a well-known web content management framework. SmarTest is a testing module that supports the analysis of the Drupal system to provide useful information to guide the testing. Also, it allows applying different prioritization testing techniques to reveals bugs faster in Drupal.

Los sistemas software altamente configurables proporcionan una funcionalidad básica común y un conjunto de características opcionales para adaptar todas las variantes de un sistema de acuerdo a un conjunto determinado de requisitos. Sistemas operativos como Linux (con más de 37,000 paquetes) o herramientas de desarrollo como Eclipse (con más de 3,000 plugins) han sido presentados como ejemplos de sistemas altamente configurables. Las pruebas en sistemas software altamente configurables suponen un gran reto debido al elevado número de configuraciones que deben probarse. Por ejemplo, linux con más de 37,000 paquetes puede dar lugar a miles de millones de configuraciones diferentes. Esto hace que probar cada configuración individual de un sistema altamente configurable sea demasiado costoso. Para paliar este problema, se han propuesto numerosos trabajos de investigación para reducir el espacio de pruebas a un subconjunto razonable y representativo de configuraciones a probar. Sin embargo, incluso reduciendo el espacio de pruebas, el número de configurationes resultante puede seguir siendo demasiado grande y costoso para llevar a cabo las pruebas. En esta tesis, se aborda el problema anteriormente mencionado utilizando priorización de casos de prueba para sistemas altamente configurables. Las técnicas de priorización de casos de prueba ordenan las pruebas de manera que se ejecuten primero aquellas que permitan maximizar un determinado objetivo de rendimiento, normalmente, detectar errores lo antes posible. La priorización de casos de prueba ayuda a mejorar la efectividad del proceso de pruebas permitiendo un feedback más rápido a los ingenieros del software y asegurando que las pruebas con mayor capacidad de detectar errores habrán sido ejecutadas si el proceso se parase por alguna circunstancia. La priorización de pruebas en sistemas software altamente configurables puede guiarse por diferentes objetivos funcionales y no funcionales, entendiéndose un objetivo como el criterio de ordenación elegido para acelerar la detectión de errores. Los objetivos de priorización funcionales son aquellos basados en características funcionales del sistema y sus interacciones. Los objetivos no funcionales consideran información extra-funcional tales como las preferencias de usuario. En esta tesis se presentan un conjunto de objetivos, técnicas y herramientas para la priorización de casos de prueba en sistemas altamente configurables. En concreto, se definen 6 objetivos basados en propiedades funcionales y 7 objetivos basados en propiedades no funcionales del sistema para guiar el proceso de pruebas. Estos objetivos se evalúan utilizando datos reales extraídos de los repositiorios Git y sistemas de gestión de errores de sistemas altamente configurables, reforzándo así la validez de nuestras conclusiones. Con respecto a las técnicas de priorización de pruebas, se presentan propuestas basadas en un sólo objetivo y basadas en múltiples objetivos utilizando algoritmos evolutivos. Adicionalmente, se presenta una comparación de 63 combinaciones diferentes de 1, 2 y 3 objetivos con la intención de encontrar las mejores combinaciones para accelerar la detección de errores en un sistema altamente configurable. Además, proponemos un caso de estudio basado en un sistema real altamente configurable con más de 2,000 millones de configuraciones para evaluar y validar las técnicas de pruebas. Estas contribuciones han sido evaluadas realizando rigurosos experimentos que han revalado la eficacia y efficiancia de nuestra propuesta. Parte de nuestras contribuciones se han integrado en una herramienta denominada SmarTest para llevar acabo las pruebas en Drupal. Drupal es un sistema de gestión de contenidos web y framework ampliamente conocido. SmarTest es un módulo de pruebas para Drupal que permite analizar el sistema y proporcionar al ingeniero de calidad información relevante de Drupal que le permita guiar mejor el proceso de pruebas. Además, SmarTest también permite aplicar diferentes técnicas de priorización para detectar antes los errores en Drupal.