Edward Liem: Towards Optimizing Feature Cause Computations

Event Details

Configurable systems enables customization of features to alter system functionalities. However, feature modifications have the potential to impact security, safety or usability of the configured system. In many cases, configuration spaces tend to be exponential w.r.t. the number of features, hampering detection and explanation of behaviors of interest. Recent works have introduced the notion of feature causality [1], aiming to identify features and interactions that contribute to particular system behaviors. Currently, feature causes are computed by filtering on prime implicants, which are found explicitly using Espresso [2], a multi-valued PLA minimization tool. We believe feature cause computation has room for improvement by taking advantage of implicit prime implicants represented as binary decision diagrams (BDDs). Inspired by an algorithm from Coudert et al. [3], we developed techniques and algorithms to filter these primes without explicit representations.

[1] C. Dubslaff, K. Weis, C. Baier, et al., “Feature causality”, Journal of Systems and Software, vol. 209, p. 111 915, 2024
[2] R. Rudell and A. Sangiovanni-Vincentelli, “Multiple-valued minimization for pla optimization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 6, no. 5, pp. 727–750, 1987
[3] O. Coudert and J. Madre, “Implicit and incremental computation of primes and essential primes of boolean functions.,”, Jan. 1992, pp. 36–39