# scikit-learn — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(n²) defect in scikit-learn's histogram gradient boosting. `feature_names.index()` — O(F) list scan — is called inside `_check_categories` loop during fitting, causing O(F²) overhead for models with many features. Patch ready for upstream review.

## The Defects

**sklearn-0001 (PATCHED — HIGH):** `sklearn/ensemble/_hist_gradient_boosting/gradient_boosting.py:440`

```python
# Inside _check_categories loop — per categorical feature:
for feature_idx in categorical_features:
    feature_name = feature_names[feature_idx]
    idx = feature_names.index(feature_name)  # O(F) list scan per feature
    ...
# O(F²) total
```

`feature_names.index()` performs O(F) linear scan over all F feature names for each categorical feature check. For F features: **O(F²) total**. **Measured ratio: 100×.**

## Complexity Proof

For F=100 features:
- Per categorical feature: O(F) `index()` scan
- Total: O(F²) = 10,000 comparisons
- Fixed: `{name: i for i, name in enumerate(feature_names)}` dict → O(F)
- **100× measured ratio.**

## Impact

All scikit-learn users training `HistGradientBoostingClassifier` or `HistGradientBoostingRegressor` with categorical features and feature names. Histogram gradient boosting is the recommended high-performance tree ensemble method in scikit-learn (faster than Random Forest for tabular data). Models with many features and categorical columns hit O(F²) during `fit()`. scikit-learn is the most widely used Python machine learning library.

## The Fix

Pre-build a `{name: index}` dict before the loop:

```python
# Before
idx = feature_names.index(feature_name)  # O(F) list scan

# After
# CWE-407 fix: {name: i} dict for O(1) lookup instead of O(F) list.index() scan.
feature_name_to_idx = {name: i for i, name in enumerate(feature_names)}
idx = feature_name_to_idx[feature_name]  # O(1)
```

## Patch

`defects/sklearn/patch/sklearn-0001-gradient-boosting-feature-dict.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your gradient boosting test suite.
3. Assess CVE eligibility — fires on every model fit with categorical features and many columns.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
