-The automated analysis of variability models in general and feature models in particular is a thriving research topic. There have been numerous contributions along the last twenty years in this area including both, research papers and tools. However, the lack of realistic variability models to evaluate those techniques and tools is recognized as a major problem by the community. To address this issue, we looked for largescale variability models in the open source community. We found that the Debian package dependency language can be interpreted as software product line variability model. Moreover, we found that those models can be automatically analysed in a software product line variability model-like style. In this paper, we take a first step towards the automated analysis of Debian package dependency language. We provide a mapping from these models to propositional formulas. We also show how this could allow us to perform analysis operations on the repositories like the detection of anomalies (e.g. packages that cannot be installed).
realistic models are highly desirable in order to assess the scalability of analysis tools.
In order to look for realistic and large–scale variability
models, we decided to look into the open source community. We
found that Debian based linux distributions have a language
to describe dependencies in software packages repositories.
They are used in Debian individual installations in order to
add, remove or update packages and manage their possible
conflicts and dependencies [
This section describes the main elements of the Debian package dependency language. A Debian–based installation is associated with a set of package repositories. A package is a unit of software that can be installed and configured. Each package repository is associated with a configuration file written in the Debian package dependency language including information about the software packages and their relationships/dependencies.
Figure 1 shows a fragment of a repository configuration file. For each package in the file, a set of properties are presented. A property is composed of a name and one or more values associated with it. Properties may be divided into those providing basic information about the package (e.g. name, version) and those describing the relationships with other packages. These relationships can be divided into: Depends. Package A depends on package B if B must be installed for A to work properly. Sometimes, A depends not only on B, but on a specific version of it. For instance, in Figure 1, line 6, describes that package openoffice.orggnome depends on package libc6 with version greater or equal to 2.1.3. If the relationship requires package B to be properly configured for the installation of A, the relationship is referred to as Pre-Depends. Note that a installed package could not be properly configured. Suggests. Package A suggests package B if B contains files that are related to (and usually enhance) the functionality of A. In Figure 1, line 8, package openoffice.orggnome suggests package openoffice.org-evolution. When the suggestion of the package is strong and it is intended to be accepted by most of the users this relationship is usually referred to as Recommends. Note that is a human who determines if a the relation should be suggests or recommends.
Conflicts. Package A conflicts with package B when A will not operate if B is installed on the system. In most cases, conflicts are cases where A contains files which are an improvement of those in B. For example, in Figure 1, line 9, package openoffice.org-gnome conflicts with package openoffice.org2-gnome in versions prior to 1:2.4.0-3ubuntu6.
Replaces. Package A replaces package B when files installed by B are removed and in some cases over-written by files in A. In Figure 1, line 4, package openoffice.orggnome replaces package openoffice.org-common in versions prior to 2.0.4 rc1-0. When this relationship affects only a part of the functionality of the package it is named Provides.
DEPENDENCIES
In order to improve the understandability and readability
of the paper we propose a simplified graphical notation [
Figure 3 shows an example using this notation. As illustrated, the repository is represented as a graph in which nodes represent packages and edges the relationships among packages. Each package is represented as a rectangle labelled with the name and version of the package. In this particular example, we also include a capital letter to simplify later references to the packages in the paper.
The model in Figure 3 represents the following products : 1) f g 2) fDg. 3) fCg. 4) fB, Cg. 5) fB, Dg 6) fA, B, Dg
Notice that the empty product is allowed in this variability model as it represents a Linux distribution without installed packages. Although this could be controversial, a distribution completely void, even without the Linux Kernel, could be considered valid as even the kernel can be installed or uninstalled.
There are also other potential products, that are invalid, for example the product fAg is not valid because the depends relationship with B package is not satisfied.
An example of how the automated analysis could help in
this circumstance is shown if we apply the valid product
operation [
Another analysis operation of feature models that can be used in the Debian community is the so–called dead features. A feature is dead when the feature does not appear in any valid configuration. In the context of Debian, we can define a dead package as the one that is present in a repository but can never be installed because of the violation of dependencies.
In our preliminary tests using Ubuntu 8.04 [
V. MAPPING DEBIANVML TO PROPOSITIONAL FORMULA
To enable the automated analysis of DebianVML we must
define the mapping from DebianVML to constraints into an
specific off–the–shelf solver such as Sat4j [
In this Section we do not refer to all the relationships as some of them have a very similar meaning and are treated in the same way as the relationships we describe here. Also there are some relationships that do no affect to the variability in the model and does not need to be added to the solver as constraints more exactly suggests and recommends relationships.
The algorithm we followed to translate DebianVML to constraints has the following general form: Each package name make up the set of variables then, each relationship is processed to make up the set of constraints (or propositional clauses) of the problem.
The first relationship to be processed is Replaces. This is a special case of relationship as it is needed to generate a set of tuples containing the replaced packages and their replacements to be ready to process the depends relationships. This is needed because, after performing a general mapping from Debian dependencies to propositional clauses, we have to change the output clauses according to the replacements that are stored in the tuples. For instance, in the example of Figure 3, we have the tuple (C,D) meaning that D is a replacement of C. Of course, in a real big example, we can have more than a tuple referring to the same package (e.g. (C,X1), (C,X2),... ,(C,Xn) means that C is replaced by X1, X2, ..., Xn).
After processing the Replaces relationship we can process the other relationships following the general rules presented
Propositional formula
A ) (B) A ) (B_ C _ D _ :::)
A ) (:B) Used to generate
the tuples
Table I DEBIAN RELATIONS TO PROPOSITIONAL FORMULA
There are other contributions interested in solving the
existing lack of realistic variability models in the SPL context.
Czarnecki et al.[
A similar contribution to the problem of the analysis of
Debian repositories is presented by some of the results of
the EDOS project [
VII. CONCLUSIONS, FUTURE WORK AND DISCUSSIONS In this paper, we propose using Debian repositories as a good source of realistic and complex variability models. These can be used as motivations inputs problems for those tools dealing with the automation of variability models. At the same time, we consider the Debian community could benefit of this automation to perform several analysis operations like the detection of inconsistencies in repositories, a work that is currently done by hand (e.g. When an error is detected, it is correctly manually).
In our ongoing research, we are working to enable the analysis of DebianVML in FaMa, making FaMa, our tool to analyse feature model, capable to perform this analysis and helping the community of Debian based distributions, applying the knowledge about feature models under Debian VM.
FaMa [
These are the main directions of our future work: Address new operations. Using our experience on feature models (e.g. Development of analysis tools, benchmarking, detection of errors ...) we need to be able to detect anomalies in Debian models such as conditionally dead packages or redundancies, probably the operations with more than one variability model can be very useful to Debian community improving the usability of packaging systems. Also the explanations of the errors to help Debian community on its daily work could help to improve the end user experience.
Benchmarking and optimization. In our preliminary tests we have detected that the Debian based models automated analysis are computationally very expensive, more than 6 hours in a laptop machine with main, multiverse, restricted and universe repositories of Ubuntu 8.04 enabled (24780 packages). We will work on the of the codding to improve those results.
We consider that this work could foster discussion about the following topics:
Can open source models be considered as SPL models?
Can the OS community benefit from the knowledge
acquired by the SPL analysis community in the last 20
years [
We would like to thank the friends and co-worker’s that encouraged us in this research and the anonymous reviewers for their helpful comments.
This work has been partially supported by the European Commission (FEDER) and Spanish Government under CICYT projects SETI (TIN2009-07366) and by the Andalusian Government under ISABEL project (TIC-2533).