UNDF: UNDF-2026-000000526

ros2-0002: NodeParameters::list_parameters() — O(P²) std::find on result.prefixes inside parameter loop

Location

rclcpp/src/rclcpp/node_interfaces/node_parameters.cpp lines 1098–1133 Repository: https://github.com/ros2/rclcpp

Severity

MEDIUM — Called when listing parameters, e.g. during node startup introspection, parameter dump, or ros2 param list. With P parameters and up to P unique prefixes, the deduplication loop is O(P²). Large ROS2 nodes (nav2 has 100+ parameters) call this during lifecycle transitions.

Complexity

Before: O(P²) — std::find on result.prefixes (grows to P) inside outer loop over parameters_ (size P)
After: O(P) — unordered_set tracks seen prefixes in O(1)

Defective Code

// node_parameters.cpp:1098-1133
for (const std::pair<const std::string, ParameterInfo> & kv : parameters_) {
    // ... prefix matching logic ...

    result.names.push_back(kv.first);
    size_t last_separator = kv.first.find_last_of(separator);
    if (std::string::npos != last_separator) {
        std::string prefix = kv.first.substr(0, last_separator);
        if (
            std::find(result.prefixes.cbegin(), result.prefixes.cend(), prefix) ==  // O(P) per iteration
            result.prefixes.cend())
        {
            result.prefixes.push_back(prefix);
        }
    }
}

Problem: std::find on result.prefixes is O(|result.prefixes|) which grows up to P as parameters are processed. This makes the entire loop O(P²).

Fixed Code

std::unordered_set<std::string> seen_prefixes;
for (const std::pair<const std::string, ParameterInfo> & kv : parameters_) {
    // ... prefix matching logic (unchanged) ...

    result.names.push_back(kv.first);
    size_t last_separator = kv.first.find_last_of(separator);
    if (std::string::npos != last_separator) {
        std::string prefix = kv.first.substr(0, last_separator);
        if (seen_prefixes.insert(prefix).second) {  // O(1) insert+dedup
            result.prefixes.push_back(prefix);
        }
    }
}

CWE

CWE-407: Inefficient Algorithmic Complexity — O(P²) → O(P)

2.1 KiB Raw Permalink Blame History Unescape Escape