A Python library for the analysis of highly configurable systems.
bdd4va supports the analysis of variability models specified with the SPLOT format. To do so, it first creates a Binary Decision Diagram (BDD) that is later explored. In particular, bdd4va supports the following operations:
-
BDD Synthesis: bdd4va wraps the Logic2BDD tool to build BDDs, which was presented in D. Fernandez-Amoros, S. Bra, E. Aranda-Escolastico, and R. Heradio, "Using Extended Logical Primitives for Efficient BDD Building," Mathematics, vol. 8, no. 8, p. 1253, 2020.
-
Counting the total number of valid configurations
-
Uniform Random Sampling: bdd4va generates configuration samples with and without replacement. To do so, it wraps BDDSampler, which was presented in R. Heradio, D. Fernandez-Amoros, J. Galindo, D. Benavides, and D. Batory, "Uniform and Scalable Sampling of Highly Configurable Systems", Empirical Software Engineering, vol. 27, no. 44, 2022.
-
Computing Feature Probabilities: bdd4va gets the probability each model feature has to be included in a valid product. That is, for every feature it returns the number of valid products with the feature activated divided by the total number of valid products (a product is valid if it satisfies all model constraints). For that, it wraps the tool probability, which was described in Heradio, R., Fernandez-Amoros, D., Mayr-Dorn, C., Egyed, A.: "Supporting the statistical analysis of variability models". 41st International Conference on Software Engineering (ICSE), pp. 843–853. Montreal, Canada (2019)..
-
Computing Product Distribution: bdd4va gets the distribution of the number of activated features per product. That is,
+ How many products have 0 features activated? + How many products have 1 feature activated? + ... + How many products have all features activated?To do so, bdd4va wraps the tool histogram, which was described in Heradio, R., Fernandez-Amoros, D., Mayr-Dorn, C., Egyed, A.: "Supporting the statistical analysis of variability models". In: 41st International Conference on Software Engineering (ICSE), pp. 843–853. Montreal, Canada (2019)..
bdd4va has been tested on Linux and Windows with Python 3.8.10. For Windows, it requires installing the Windows Subsystem for Linux (WSL).
Imagine bdd4va has been downloaded into the directory my_folder. Go to that directory:
cd my_folder
and run
pip install ./bdd4va
The following code:
- Imports bdd4va.
- Imports the library pprint for pretty-printing the results.
- Creates a BDD for the Dell laptop configurator variability model included in the test folder.
- Counts the total number of valid configurations when there is no feature assignment
- Counts the total number of valid configurations for a partial feature assignment
- Generates a sample with 10 configurations and then prints the result.
- Computes the feature probabilities and then prints the result.
- Computes the product distribution and then prints the result.
- Shows how to use a previously synthesized BDD file
from bdd4va.bdd4va import BDD
import pprint
pp = pprint.PrettyPrinter(indent=4)
# Synthesize a BDD for model DellSPLOT
my_bdd = BDD("test/model_examples/DellSPLOT/DellSPLOT.xml")
# Count the total number of valid configurations
confs = my_bdd.count()
print(confs)
# Count the number of valid configurations
# * With features Vostro_1510 and Hardware_Raid not activated
# * With feature Latitude_D630N activated
confs = my_bdd.count(['not Vostro_1510', 'Latitude_D630N', 'not Hardware_Raid'])
print(confs)
# Generate a sample with 10 configurations
configurations = my_bdd.sample(10)
pp.pprint(configurations)
# Compute the feature probabilities
probabilities = my_bdd.feature_probabilities()
pp.pprint(probabilities)
# Compute the product distribution
distribution = my_bdd.product_distribution()
pp.pprint(distribution)
# When a BDD is synthesized, it is automatically stored in a dddmp file.
# Accordingly and to save time, if the BDD hasn't changed, you don't need to synthesize it again!!
# For example, we can create a new BDD object reusing our previously
# synthesized bdd. To do so,
# 1) The model_file param is the dddmp file
# 2) The synthesize_bdd param of BDD is set to False
# Reuse a previously synthesized BDD
my_restored_bdd = BDD("test/model_examples/DellSPLOT/DellSPLOT.dddmp", False)
configurations = my_restored_bdd.sample(10)
pp.pprint(configurations)
The code execution would print the following text:
Preprocessing test/model_examples/DellSPLOT/DellSPLOT.xml to get its BDD...
Synthesizing the BDD (this may take a while)...
Counting the number of valid configurations (this may take a while)...
1128674
Counting the number of valid configurations (this may take a while)...
5760
Getting a sample with 10 configurations (this may take a while)...
[ [ 'Dell_XML',
'not Vostro_1510',
...,
'not integrated_Modem'
],
...
]
Getting the feature probabilities (this may take a while)...
{ 'Beetwen_5_and_7_lbs_Light': 0.869268,
'Between_1000_1300': 0.181764,
...
'w80211n': 0.0803492
}
Getting the product distribution (this may take a while)...
[ 0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
22108,
103540,
223702,
...
]
For more examples, see the bdd4va test.
bdd4va ships with several precompiled binaries, which require a 64-bit Linux system and certain shared libraries.
On systems that don't fulfill these requirements (such as macOS), running inside a virtualized Docker environment with the --platform flag is a viable alternative.
Here is an example to get started (executing the code in example.py):
docker build . --platform linux/amd64 -t bdd4va
docker run --rm --platform linux/amd64 -v "$PWD":/mount bdd4va
Builds a BDD for a configuration model
:param model_file: A file specifying a configuration model with the SPLOT format.
:param synthesize_bdd: do you like to synthesize the BDD or to restore a previously synthesized one?
:return: A dddmp file containing the BDD encoding of the model is generated in the same folder where model_file is located.
Computes the number of valid configurations.
:param feature_assignment: a list with a partial or a complete features' assignment
(e.g., ["f1", "not f3", "f5"])
:return The number of valid configurations
Generates a uniform random sample of size "config_number" from "bdd_file".
:param config_number: Number of configurations to be generated.
:param with_replacement: If it is True, every configuration is generated from scratch, independently
of the prior generated configurations. Accordingly, a configuration may be repeated in the sample. If
with_replacement is False then the sample is generated without replacement and there won't be any
repeated configurations (for a more detailed explanation, check https://en.wikipedia.org/wiki/Simple_random_sample).
:return: A list with the generated configurations. Each element in that list is a configuration, and
each configuration is in turn a list of strings encoding the feature values.
Computes the probability each model feature has to be included in a valid product.
That is, for every feature it returns the number of valid products with the feature activated
divided by the total number of valid products (a product is valid if it satisfies all model constraints).
For detailed information, see the paper: Heradio, R., Fernandez-Amoros, D., Mayr-Dorn, C., Egyed, A.:
Supporting the statistical analysis of variability models. In: 41st International Conference on Software
Engineering (ICSE), pp. 843–853. Montreal, Canada (2019).
:param feature_assignment: a list with a partial or a complete features' assignment
(e.g., ["f1", "not f3", "f5"])
:return: A dictionary with the format {feature_1: feature_1_probability, feature_2: feature_2_probability, ...}
Computes the distribution of the number of activated features per product.
:return: A list that stores:
+ In index 0, the number of products with 0 features activated.
+ In index 1, the number of products with 1 feature activated.
...
+ In index n, the number of products with n features activated.
bdd4va is intended to be part of Flama, which is a Python-based framework for the Automated Analysis of Feature Models (AAFM). It takes into consideration previous AAFM tool designs and enables multi-solver and multi-metamodel support for the integration of AAFM tooling on the Python ecosystem.
The main features of the framework are:
- Easy to extend by enabling the creation of new plugins following a semi-automatic generator approach.
- Support multiple variability models. Currently, it provides support for cardinality-based feature models. However, it is easy to integrate others such as attributed feature models.
- Support multiple solvers. Currently, it provides support for the PySAT metasolver, which enables more than ten different solvers.
- Support multiple operations. It is developed, having in mind multi-model operations such as those depicted by Familiar and single-model operations.