Uniform and Scalable SAT-Sampling for Configurable Systems

• Autores: Rubén Heradio Gil , David Jose Fernandez Amoros , José Galindo Gómez , David Benavides
• Localización: Actas de las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021): [Málaga, 22 al 24 de septiembre de 2021] / coord. por Rafael Capilla Sevilla , Maider Azanza Sese , Miguel Rodríguez Luaces , M. M. Roldán García , Dolores Burgueño Caballero, José Raúl Romero Salguero , José Antonio Parejo Maestre , José Francisco Chicano García , Marcela Genero , Óscar Díaz García , José González Enríquez , María Carmen Penades Gramage ; Silvia Mara Abrahao Gonzales (col.) , 2021
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • Several relevant analyses on configurable software systems remain intractable because they require examining vast and highly-constrained configuration spaces. Those analyses could be addressed through statistical inference, i.e., working with a much more tractable sample that later supports generalizing the results obtained to the entire configuration space. To make this possible, the laws of statistical inference impose an indispensable requirement: each member of the population must be equally likely to be included in the sample, i.e., the sampling process needs to be +AGAAYA-uniform''. Various SAT-samplers have been developed for generating uniform random samples at a reasonable computational cost. Unfortunately, there is a lack of experimental validation over large configuration models to show whether the samplers indeed produce genuine uniform samples or not. This paper (i) presents a new statistical test to verify to what extent samplers accomplish uniformity and (ii) reports the evaluation of four state-of-the-art samplers: Spur, QuickSampler, Unigen2, and Smarch. According to our experimental results, only Spur satisfies both scalability and uniformity.