russell@unturf.com
fb1ff685c1
cmake-0005: cmQtAutoGen MergeOptions std::find over baseOpts in newOpts loop, O(N*M), 31.5x at N=M=50 cmake-0006: cmVisualStudio10TargetGenerator FinishWritingSource writtenSettings O(S^2), 15.3x at S=30 cmake-0007: cmGeneratorExpressionNode TargetRuntimeDllDirsNode dllDirs O(D^2), 10.3x at D=100 MPD: all 5 MOADs CLEAN; updated CLEAN.md with MOAD-0002 through MOAD-0005 analysis. Unit tests: 3/3 PASS.
1.9 KiB
cmake-0007 — TargetRuntimeDllDirsNode: O(D²) dllDirs dedup in genex evaluator
Target: CMake (Kitware/CMake)
Severity: MEDIUM
File: Source/cmGeneratorExpressionNode.cxx
Lines: 4496–4511 (TargetRuntimeDllDirsNode::Evaluate)
CWE: CWE-407 (Algorithmic Complexity)
Pattern
// Source/cmGeneratorExpressionNode.cxx:4501-4510
std::vector<std::string> dlls = CollectDlls(parameters, eval, content);
std::vector<std::string> dllDirs;
for (std::string const& dll : dlls) {
std::string directory = cmSystemTools::GetFilenamePath(dll);
if (std::find(dllDirs.begin(), dllDirs.end(), directory) == // O(D) scan
dllDirs.end()) {
dllDirs.push_back(directory);
}
}
For each DLL in dlls (size D), std::find scans dllDirs (up to D entries) linearly.
Total cost: O(D²) dedup.
This generator expression ($<TARGET_RUNTIME_DLL_DIRS:tgt>) is evaluated per
target and per configuration during the generator phase. In a Windows project
with many DLL dependencies (e.g. Qt, Boost, OpenCV combined: 100+ DLLs),
D grows large and D² becomes significant.
Exploit Scenario
A Windows application linking Qt6 + Boost + OpenCV: ~80 DLLs across ~20 distinct directories. Current cost: 80 × 80 = 6,400 comparisons per target per config. With a hash set: 80 lookups total — 80x speedup for dedup phase.
Fix
Replace the growing dllDirs vector with an insertion-ordered structure that
uses a parallel std::unordered_set<std::string> for O(1) membership testing.
std::vector<std::string> dllDirs;
std::unordered_set<std::string> dllDirsSet;
for (std::string const& dll : dlls) {
std::string directory = cmSystemTools::GetFilenamePath(dll);
if (dllDirsSet.insert(directory).second) { // O(1) insert+check
dllDirs.push_back(directory);
}
}
MOAD Classification
MOAD-0001 (CWE-407): std::find over growing dllDirs vector inside
for loop over dlls — classic O(N²) dedup.