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.
2 KiB
cmake-0006 — FinishWritingSource: O(S²) writtenSettings dedup in VS generator
Target: CMake (Kitware/CMake)
Severity: MEDIUM
File: Source/cmVisualStudio10TargetGenerator.cxx
Lines: 2775–2799 (FinishWritingSource)
CWE: CWE-407 (Algorithmic Complexity)
Pattern
// Source/cmVisualStudio10TargetGenerator.cxx:2778-2795
std::vector<std::string> writtenSettings;
for (auto const& configSettings : toolSettings) {
for (auto const& setting : configSettings.second) {
if (std::find(writtenSettings.begin(), writtenSettings.end(),
setting.first) != writtenSettings.end()) { // O(S) scan
continue;
}
...
writtenSettings.push_back(setting.first);
}
}
For each source file, FinishWritingSource iterates over all configs (outer loop)
and all settings per config (inner loop). For each setting it does std::find
over writtenSettings — a vector that grows with each unique setting written.
Cost per source file: O(C × S × S) = O(C × S²) where C = config count, S = setting count. For a target with many sources and many per-source compiler settings, this is O(F × S²).
Exploit Scenario
A Visual Studio project with 200 source files, 4 configs, 30 settings each:
200 × 4 × 30 × 30 = 720,000 comparisons.
With an unordered_set: 200 × 4 × 30 = 24,000 lookups — 30x speedup.
Fix
Replace writtenSettings vector with an std::unordered_set<std::string>.
Change push_back to insert, and the std::find check to count().
std::unordered_set<std::string> writtenSettings;
for (auto const& configSettings : toolSettings) {
for (auto const& setting : configSettings.second) {
if (writtenSettings.count(setting.first)) { // O(1)
continue;
}
...
writtenSettings.insert(setting.first);
}
}
MOAD Classification
MOAD-0001 (CWE-407): std::find over growing writtenSettings vector inside
nested loop over toolSettings (configs × settings per config).