Examinando por Autor "Benavides, David"

Mostrando 1 - 3 de 3
  • Miniatura
    Publicación
    A Monte Carlo tree search conceptual framework for feature model analyses
    (Elsevier, 2023-01) Horcas, José Miguel; Galindo, José A.; Benavides, David; Heradio Gil, Rubén; Fernández Amoros, David José
    Challenging domains of the future such as Smart Cities, Cloud Computing, or Industry 4.0 expose highly variable systems with colossal configuration spaces. The automated analysis of those systems’ variability has often relied on SAT solving and constraint programming. However, many of the analyses have to deal with the uncertainty introduced by the fact that undertaking an exhaustive exploration of the whole configuration space is usually intractable. In addition, not all analyses need to deal with the configuration space of the feature models, but with different search spaces where analyses are performed over the structure of the feature models, the constraints, or the implementation artifacts, instead of configurations. This paper proposes a conceptual framework that tackles various of those analyses using Monte Carlo tree search methods, which have proven to succeed in vast search spaces (e.g., game theory, scheduling tasks, security, program synthesis, etc.). Our general framework is formally described, and its flexibility to cope with a diversity of analysis problems is discussed. We provide a Python implementation of the framework that shows the feasibility of our proposal, identifying up to 11 lessons learned, and open challenges about the usage of the Monte Carlo methods in the software product line context. With this contribution, we envision that different problems can be addressed using Monte Carlo simulations and that our framework can be used to advance the state-of-the-art one step forward.
  • Miniatura
    Publicación
    Pragmatic Random Sampling of the Linux Kernel: Enhancing the Randomness and Correctness of the conf Tool
    (Association for Computing Machinery, New York, 2024-09-02) Fernández Amoros, David José; Heradio Gil, Rubén; Horcas Aguilera, Jose Miguel; Galindo, José A.; Benavides, David; Fuentes, Lidia; https://orcid.org/0000-0003-3758-0195; https://orcid.org/0000-0002-5677-7156; https://orcid.org/0000-0002-8449-3273; https://orcid.org/0000-0001-9293-9784
    The configuration space of some systems is so large that it cannot be computed. This is the case with the Linux Kernel, which provides almost 19,000 configurable options described across more than 1,600 files in the Kconfig language. As a result, many analyses of the Kernel rely on sampling its configuration space (e.g., debugging compilation errors, predicting configuration performance, finding the configuration that optimizes specific performance metrics, etc.). The Kernel can be sampled pragmatically, with its built-in tool conf, or idealistically, translating the Kconfig files into logic formulas. The pros of the idealistic approach are that it provides statistical guarantees for the sampled configurations, but the cons are that it sets out many challenging problems that have not been solved yet, such as scalability issues. This paper introduces a new version of conf called randconfig+, which incorporates a series of improvements that increase the randomness and correctness of pragmatic sampling and also help validate the Boolean translation required for the idealistic approach. randconfig+ has been tested on 20,000 configurations generated for 10 different Kernel versions from 2003 to the present day. The experimental results show that randconfig+ is compatible with all tested Kernel versions, guarantees the correctness of the generated configurations, and increases conf’s randomness for numeric and string options.
  • Miniatura
    Publicación
    Uniform and scalable sampling of highly configurable systems
    (Springer, 2022-01-21) Galindo, José A.; Benavides, David; Batory, Don; Heradio Gil, Rubén; Fernández Amoros, David José; Heradio Gil, Rubén; Fernández Amoros, David José
    Many analyses on configurable software systems are intractable when confronted with colossal and highly-constrained configuration spaces. These analyses could instead use statistical inference, where a tractable sample accurately predicts results for the entire space. To do so, the laws of statistical inference requires each member of the population to be equally likely to be included in the sample, i.e., the sampling process needs to be “uniform”. SAT-samplers have been developed to generate uniform random samples at a reasonable computational cost. However, there is a lack of experimental validation over colossal spaces to show whether the samplers indeed produce uniform samples or not. This paper (i) proposes a new sampler named BDDSampler, (ii) presents a new statistical test to verify sampler uniformity, and (iii) reports the evaluation of BDDSampler and five other state-of-the-art samplers: KUS, QuickSampler, Smarch, Spur, and Unigen2. Our experimental results show only BDDSampler satisfies both scalability and uniformity.