Skip to content

dubslaff/FeatCause

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Feature Causality

This is the repository of FeatCause, a prototypical implementation of the algorithms described in the ICSE'22 paper

Causality in Configurable Software Systems by Clemens Dubslaff, Kallistos Weis, Christel Baier, and Sven Apel.

The preprint of this paper is available at ArXiv.

Compared to the version used in this paper, the implementation has been extended with methods to reason about uncertainties in effect sets.

Directory structure

The supplementary material to reproduce our findings from the evaluation is organized in the following three main directories:

tool

In this directory, we provide the prototype of FeatCause, our algorithm to compute feature causes.

  • main.py contains the major part of the implementation
  • fm_parser.py, causality.py, utils.py contain helping functionality for FeatCause
  • espresso, espresso-macos-x86, espresso-macos-arm are precompiled binaries of the two-level minimizer espresso for Linux and macOS operating systems

Since main.py invokes "./espresso", please ensure that espresso is in the folder where you run the tool from (e.g., "tool"). If on macOS and you want to use the precompiled espresso binary, please rename "espresso-osx" to "espresso" first. On Windows systems, please compile espresso by your own.

main.py

To run our prototype the first argument needs to be the path to the experiment + experiment name, e.g., 'python3 main.py experiment/expFolder/expName ... '.

One can choose between different options to run our prototype:

  • -s [number] the number of the single effect experiment to be considered, default is set to -1, which includes all effect experiments

  • -fmt [DNF, CNF] determins the format of the feature model and effect set, default is set to DNF

  • -n switches the effect set and its negation

  • -na disables feature cause computation (only compute cause-effect covers)

  • -d minimize causes with the distributive law simplification

  • -m computes most general feature causes

  • -e [standard, fast] adds the output minimal cause-effect covers generated by espresso

  • -b [pfblame, fblame, cblame, all] determins which blame shall be computed, pfblame for the blame of partial configurations, fblame for the blame of single features, and cblame for the blame of causes

  • -w computes the weights of causes

  • -i enables computation of minimal t-way interaction witnesses

  • -inc enables the incremental computation of uncertain effect sets (in combination with -m)

  • -sani performs sanity checks during computation

  • -v is the verbose flag, leading to more output information about each experiment

  • -p to print all feature cause results on std::out

  • -stat writes statistics for the descriptive statistics table

  • -tstat adds the time to compute feature causes to existing statistic files

scripts

  • profeat_extract.py is a script to extract the experiments from the ProFeat model checking results.
  • provelines_extract.py is a script to extract the experiments from the ProVeLines model checking results.
  • buildEvaluationTable.py is a script to create a table for descriptive statistics of all experiments (as presented in the paper)

benchmark

Contains a script (evaluation_runner.py) to execute all experiments as well as an archive of examples (examples.zip) which contains all data that are used in the paper to evaluate our approach.

Flags for evaluation_runner.py:

  • -c to check if all experiments are found.
  • -r to run all experiments
  • -t to get run time measurements for all experiments, can only be used after running all experiments once
  • -m to run multiple experiments in parallel, one for each thread of the system
  • -f to run fscore computations for uncertain effect sets

To execute the runner, espresso has to be located in the same directory as the evaluation_runner.py. Make sure to unzip examples.zip before you run the evaluation_runner.py.

Requirements

espresso

We provide binaries of espresso compiled for macOS and Linux, compiled from the following sources

Python

To run our prototype the following dependencies need to be provided, which are installable in the standard way via pip:

  • pyEDA
  • pandas

Creating own Case-Studies

To compute causes, responsibility and blame for your own case study, you need to provide the following files:

  • study.fs contains all features of the case study, each feature in an own line
  • study.fm contains a feature model (formula of all valid configurations) in DNF or CNF format, where each line represents one clause
  • study.0 contains the set of configurations, for which a certain effect property can be observed, also in DNF or CNF format, where each line represents one clause

Note: All files have to be stored in the same directory, with the same file name and their respective, correct file extension. If you want conduct more than one experiment for a system, you can add more than one effect set, by increasing the file extension, e.g., study.1 would be the second effect set for this system. If you use CNF format, you have to specify the option -fmt CNF, you have to use the same format for all effect sets and the feature model of one case study.

Experiment Results

The results of our tool will be written in a new directory, i.e., tmp, in the same directory as the tool. Causes and blame are stored in subdirectories of tmp, for which their experiment name is used as name. All statistical output, i.e., produced with the flags -stat and -tstat, will be in a subdirectory of tmp, i.e., statistic_files.

Examples

Executing the command python main.py ../benchmark/examples/ProVeLines/minepump/minepump -v -i -s 12 -m -d leads to the output:

Console Output
--- FeatCause ---
Feature model of examples/ProVeLines/minepump/minepump.fm: 128 configurations
	PID: 45334
	Number of Features: 11
--- Time to read feature model:     0.0235s
--- start iteration 12 ---
--- Time to build effect BDD:     0.0142s
28 effects
--- Time to build BDD for valid non-effects:     0.0014 seconds
100 valid non-effects
Compute causes via prime implicants...
O	Compute primes...
O       Time for BDD PLA export:     0.0055s                
O	Time for Espresso primes:     0.0083s
O Atomic feature causes computed (7)                                            
	And(High, Start, MethaneAlarm)
	And(High, Command, ~Stop, MethaneSensor, ~MethaneQuery)
	And(High, Start, Stop)
	And(High, Start, MethaneSensor, ~MethaneQuery)
	And(High, Low, Command, ~Stop)
	And(High, Low, Start)
	And(High, Command, ~Stop, MethaneAlarm)
X	DLS [34 -> 21]: And(High, Or(And(Command, ~Stop, Or(Low, MethaneAlarm, And(MethaneSensor, ~MethaneQuery))), And(Start, Or(Low, Stop, MethaneAlarm, And(MethaneSensor, ~MethaneQuery)))))
X Most general causes (3)
X	And(High, Low, Start)
X	And(High, Start, Stop)
X	And(High, Start, MethaneAlarm)
X	DLS [13 -> 7]: And(High, Start, Or(Low, Stop, MethaneAlarm))
--- Time for atomic and most general causes:     0.0461s
I 3-way interaction witnesses computed (3)
	And(High, Start, MethaneAlarm)
	And(High, Low, Start)
	And(High, Start, Stop)
------------- end iterations
Total time for computation:     0.0882s

Executing the command python main.py ../benchmark/examples/RWSPL/lrzip/lrzipPaper -s 1 -i -b all -m -d -sani -p -w leads to the output:

Console Output
--- FeatCause ---
Feature model of examples/RWSPL/lrzip/lrzipPaper.fm: 432 configurations
	PID: 36880
	Number of Features: 20
--- Time to read feature model:     1.9924s
--- start iteration 1 ---
--- Time to build effect BDD:     0.4272s
120 effects
effect feats-univ: set(), univ-feats: set()
--- Time to build BDD for valid non-effects:     0.0044 seconds
312 valid non-effects
valid non-effects ... feats-univ: set() univ-feats: set()
sanity check: 120 valid effects
sanity check (b_ne & b_e is zero): True
Compute causes via prime implicants...
O	Compute primes...
O       Time for BDD PLA export:     0.0302s
O	Time for Espresso primes:     0.0166s
Compute partial blame of causes...
Compute weight of causes...
O Atomic feature causes computed (16)
	b: 0.0333 w: 2.0000 w*b: 0.0667 And(compressionLrzip, level8)
	b: 0.0667 w: 4.0000 w*b: 0.2667 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, level8)
	b: 0.0333 w: 2.0000 w*b: 0.0667 And(compressionLrzip, level5)
	b: 0.0667 w: 4.0000 w*b: 0.2667 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, level5)
	b: 0.3000 w: 24.0000 w*b: 7.2000 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, ~compressionLrzip)
	b: 0.0333 w: 2.0000 w*b: 0.0667 And(compressionLrzip, level7)
	b: 0.0667 w: 4.0000 w*b: 0.2667 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, level4)
	b: 0.0667 w: 4.0000 w*b: 0.2667 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, level6)
	b: 0.0667 w: 4.0000 w*b: 0.2667 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, level7)
	b: 0.0667 w: 4.0000 w*b: 0.2667 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, level9)
	b: 0.3000 w: 24.0000 w*b: 7.2000 compressionZpaq
	b: 0.0333 w: 2.0000 w*b: 0.0667 And(compressionLrzip, level6)
	b: 0.2000 w: 12.0000 w*b: 2.4000 And(compressionLrzip, ~level1, ~level2, ~level3)
	b: 0.4000 w: 24.0000 w*b: 9.6000 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, ~level1, ~level2, ~level3)
	b: 0.0333 w: 2.0000 w*b: 0.0667 And(compressionLrzip, level4)
	b: 0.0333 w: 2.0000 w*b: 0.0667 And(compressionLrzip, level9)
X	DLS [75 -> 32]: Or(compressionZpaq, And(compressionLrzip, Or(level4, level5, level6, level7, level8, level9, And(~level1, ~level2, ~level3))), And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, Or(~compressionLrzip, level4, level5, level6, level7, level8, level9, And(~level1, ~level2, ~level3))))
X Most general causes (2)
Compute partial blame of most general causes...
X       b: 0.3000 compressionZpaq | And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, ~compressionLrzip)
X	b: 0.4000 And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, ~level1, ~level2, ~level3)
X	DLS [16 -> 13]: Or(compressionZpaq, And(compression, ~compressionBzip2, ~compressionGzip, ~compressionLzo, Or(~compressionLrzip, And(~level1, ~level2, ~level3))))
sanity check (reduced expression semantically equivalent?): True
--- Time for atomic and most general causes:     0.9343s
I 1-way interaction witnesses computed (1)
	compressionZpaq
R Partial blame computations ...
R compressionBzip2,level1: 	 0.0000
R compressionBzip2,level2: 	 0.0000
R compressionBzip2,level3: 	 0.0000
R compressionBzip2,level4: 	 0.0000
R compressionBzip2,level5: 	 0.0000
R compressionBzip2,level6: 	 0.0000
R compressionBzip2,level7: 	 0.0000
R compressionBzip2,level8: 	 0.0000
R compressionBzip2,level9: 	 0.0000
R compressionGzip,level1: 	 0.0000
R compressionGzip,level2: 	 0.0000
R compressionGzip,level3: 	 0.0000
R compressionGzip,level4: 	 0.0000
R compressionGzip,level5: 	 0.0000
R compressionGzip,level6: 	 0.0000
R compressionGzip,level7: 	 0.0000
R compressionGzip,level8: 	 0.0000
R compressionGzip,level9: 	 0.0000
R compressionLzo,level1: 	 0.0000
R compressionLzo,level2: 	 0.0000
R compressionLzo,level3: 	 0.0000
R compressionLzo,level4: 	 0.0000
R compressionLzo,level5: 	 0.0000
R compressionLzo,level6: 	 0.0000
R compressionLzo,level7: 	 0.0000
R compressionLzo,level8: 	 0.0000
R compressionLzo,level9: 	 0.0000
R compressionZpaq,level1: 	 0.0000
R compressionZpaq,level2: 	 0.0000
R compressionZpaq,level3: 	 0.0000
R compressionZpaq,level4: 	 0.0000
R compressionZpaq,level5: 	 0.0000
R compressionZpaq,level6: 	 0.0000
R compressionZpaq,level7: 	 0.0000
R compressionZpaq,level8: 	 0.0000
R compressionZpaq,level9: 	 0.0000
R compressionLrzip,level1: 	 0.0000
R compressionLrzip,level2: 	 0.0000
R compressionLrzip,level3: 	 0.0000
R compressionLrzip,level4: 	 0.0333
R compressionLrzip,level5: 	 0.0333
R compressionLrzip,level6: 	 0.0333
R compressionLrzip,level7: 	 0.0333
R compressionLrzip,level8: 	 0.0333
R compressionLrzip,level9: 	 0.0333
R Blame computations for each feature
R       [0.0000,0.5000] compression
R       [0.5000,0.0000] compressionBzip2
R       [0.5000,0.0000] compressionGzip
R       [0.2000,0.2000] compressionLrzip
R       [0.5000,0.0000] compressionLzo
R       [0.0000,0.3000] compressionZpaq
R	[0.0000,0.0000] disableCompressibilityTesting
R	[0.0000,0.0000] encryption
R	[0.0000,0.0000] level
R       [0.3333,0.0000] level1
R       [0.3333,0.0000] level2
R       [0.3333,0.0000] level3
R       [0.0000,0.0500] level4
R       [0.0000,0.0500] level5
R       [0.0000,0.0500] level6
R       [0.0000,0.0500] level7
R       [0.0000,0.0500] level8
R       [0.0000,0.0500] level9
R	[0.0000,0.0000] root
R	[0.0000,0.0000] unlimitedWindowSize
--- Time for blame computation:     1.7120s
------------- end iterations
Total time for computation:     5.0778s

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages