Coreboot 4.13 Dependency and Conflict Graphs Dataset

This dataset contains dependency and conflict graphs derived from the coreboot 4.13 firmware variability model using association rule mining. The graphs represent deterministic feature relationships discovered through empirical analysis of 1,000 randomly sampled valid configurations. Overview This dataset accompanies the paper: "Deriving Dependency and Conflict Graphs from Configurable Software via Association Rules" Ruben Heradio, David Fernandez-Amoros, Miguel Angel Olivero, Jose M. Sanchez The dataset provides a practical alternative to SAT-based analysis for understanding feature relationships in large-scale Kconfig-based systems, avoiding both the computational expense of repeated SAT solver calls and the incomplete Kconfig-to-Boolean translation problem. Dataset Contents 1. coreboot_association_rules.csv (299 MB) Description: Raw association rules discovered using the Apriori algorithm with parameters: - Support = 0.01 (minimum 1% occurrence in configurations) - Confidence = 1.0 (100% deterministic rules only) - Rule length = 2 (binary relationships) Format: CSV with columns: - rules: Association rule in format {antecedent} => {consequent} - support: Proportion of configurations containing both antecedent and consequent - confidence: Proportion of configurations with antecedent that also contain consequent (always 1.0) - coverage: Proportion of all transactions covered by the rule - lift: How much more likely consequent is when antecedent is present - count: Number of configurations where the rule holds Sample: "{BOARD_SAMSUNG_LUMPY=y} => {EC_SMSC_MEC1308=y}";0.01;1;0.01;100;10 This rule indicates that in all sampled configurations where BOARD_SAMSUNG_LUMPY is enabled, EC_SMSC_MEC1308 is also enabled (100% confidence). 2. coreboot__requires.net (776 KB) Description: Dependency graph representing requires relationships (directed arcs). Statistics: - Format: Pajek .net (network graph format) - Vertices: 1,918 features - Arcs: 79,464 directed dependencies - Interpretation: An arc from feature A to feature B means "A requires B" (if A is enabled, B must be enabled) Format: Pajek network format *Vertices 1918 1 "FEATURE_NAME_1" 2 "FEATURE_NAME_2" ... *Arcs 1 2 # Feature 1 requires Feature 2 Usage: Compatible with network analysis tools including: - Gephi (https://gephi.org/) - igraph (R/Python) - NetworkX (Python) - Pajek (http://mrvar.fdv.uni-lj.si/pajek/) 3. coreboot__excludes.net (10.8 MB) Description: Conflict graph representing excludes relationships (undirected edges). Statistics: - Format: Pajek .net (network graph format) - Vertices: Variable features (after removing core and dead) - Edges: 1,206,384 undirected conflicts - Interpretation: An edge between features A and B means they are mutually exclusive (cannot both be enabled) Format: Pajek network format with *Edges section instead of *Arcs to indicate undirected relationships. Usage: Same tools as requires graph. The large number of conflicts reflects hardware incompatibilities and mutually exclusive design choices inherent in firmware configuration. 4. coreboot__core.txt (96 bytes) Description: List of core features that appear enabled in all sampled configurations. Content: 6 features that are essential firmware components that cannot be disabled: COREBOOT_BUILD HAVE_BOOTBLOCK HAVE_RAMSTAGE HAVE_ROMSTAGE NO_EARLY_GFX_INIT Note: Core features were excluded from graph generation as they provide no variation information for dependency analysis. 5. coreboot__dead.txt (13 KB) Description: List of dead features that never appear enabled in any sampled configuration. Content: 596 features that may indicate: - Obsolete configuration options - Hardware-specific features not represented in the sample - Features with unmet dependencies Note: Dead features were excluded from graph generation as they exhibit zero variance and cannot participate in meaningful dependency relationships. Methodology Configuration Sampling Generated 1,000 valid configurations from coreboot 4.13 using randconfig+ Each configuration represents a valid firmware build with specific feature selections Configurations stored as feature vectors with states: =y (enabled), =n (disabled), =m (module) Association Rule Mining Applied Apriori algorithm to discover frequent itemsets Extracted rules with confidence = 1.0 (deterministic constraints only) Classified rules based on feature states: Requires: {A=y} => {B=y} (enabling A requires enabling B) Excludes: {A=y} => {B=n} (enabling A excludes B) Graph Generation Created directed graph for dependency relationships (requires) Created undirected graph for conflict relationships (excludes) Exported to Pajek format for compatibility with network analysis tools Use Cases Impact Analysis Identify hub features whose modifications affect large portions of the codebase by analyzing in-degree distributions in the dependency graph. Refactoring Guidance Detect tightly coupled feature clusters that may benefit from architectural restructuring by analyzing strongly connected components. Configuration Debugging Explain why certain feature combinations are incompatible by querying the conflict graph. Testing Prioritization Focus testing on limit configurations combining highly required features and high-conflict features that stress variability model boundaries. Architectural Analysis Study structural properties including: - Degree distributions (long-tail patterns) - Hub features (high in-degree nodes) - Structural robustness (correlation between in-degree and out-degree) System Information Coreboot Version: 4.13 Total Features: 7,413 configuration options Kconfig Files: 1,099 files Unique Symbols: 4,003 Feature Types: - Boolean: 56.9% (4,216 features) - String: 19.5% (1,442 features) - Hexadecimal: 12.1% (894 features) - Integer: 11.2% (827 features) - Unknown: 0.5% (34 features) Sample Size: 1,000 configurations Variable Features Analyzed: 6,811 (after removing 6 core and 596 dead features) File Sizes coreboot_association_rules.csv 299 MB (raw association rules) coreboot__excludes.net 10.8 MB (conflict graph) coreboot__requires.net 776 KB (dependency graph) coreboot__dead.txt 13 KB (596 dead features) coreboot__core.txt 96 bytes (6 core features) License This dataset is released under MIT License. Contact For questions or issues regarding this dataset, please contact Ruben Heradio: [e-mail].