DOI: 10.5281/zenodo.18134414
title: Coreboot 4.13 Dependency and Conflict Graphs Dataset

description: 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: rheradio@issi.uned.es.