russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
87 lines
2.3 KiB
ReStructuredText
87 lines
2.3 KiB
ReStructuredText
CMake — CWE-407 Analysis
|
|
=========================
|
|
|
|
.. contents:: :local:
|
|
|
|
Overview
|
|
--------
|
|
|
|
CMake is the most widely used C/C++ build system generator, processing ``CMakeLists.txt`` files
|
|
into native build system files (Makefiles, Ninja, Visual Studio projects). It performs link
|
|
dependency analysis to determine transitive link libraries. One CWE-407 defect site was found
|
|
in the link dependency computation. It is unpatched.
|
|
|
|
Defect Sites
|
|
------------
|
|
|
|
cmake-0001
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``Source/cmComputeLinkDepends.cxx:1167,521,1363``
|
|
|
|
**Pattern:**
|
|
|
|
.. code-block:: cpp
|
|
|
|
// Link dependency group membership — std::find on group vectors
|
|
std::vector<int> groupMembers;
|
|
// ...
|
|
bool IsInGroup(int componentIndex) {
|
|
return std::find(groupMembers.begin(),
|
|
groupMembers.end(),
|
|
componentIndex) != groupMembers.end();
|
|
// O(|groupMembers|) per call
|
|
}
|
|
|
|
// Called during link order traversal for each target
|
|
void ProcessGroup(...) {
|
|
for (auto& dep : dependencies) {
|
|
if (IsInGroup(dep.componentIndex)) { // O(V) per edge
|
|
// merge groups
|
|
}
|
|
}
|
|
}
|
|
|
|
**Why this is O(n):** ``std::find`` on a ``std::vector`` is O(n); called once per dependency
|
|
edge during link group traversal.
|
|
|
|
**Complexity:** ``O(n)`` per group membership test; ``O(V²)`` for full link order computation
|
|
in worst case (dense dependency graph)
|
|
|
|
**Patch:**
|
|
|
|
.. code-block:: cpp
|
|
|
|
std::unordered_set<int> groupMemberSet;
|
|
std::vector<int> groupMembers; // keep for ordering
|
|
|
|
bool IsInGroup(int componentIndex) {
|
|
return groupMemberSet.count(componentIndex) > 0; // O(1)
|
|
}
|
|
|
|
void AddToGroup(int componentIndex) {
|
|
if (groupMemberSet.insert(componentIndex).second) {
|
|
groupMembers.push_back(componentIndex);
|
|
}
|
|
}
|
|
|
|
**Data structure change:** ``std::vector<int>`` + ``std::find`` → ``std::unordered_set<int>`` + ``count()``
|
|
|
|
**Status:** Unpatched
|
|
|
|
Benchmark Results
|
|
-----------------
|
|
|
|
.. TODO: benchmark pending patch
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Let V = number of link-order components. ``std::find`` on a vector of up to V elements: O(V)
|
|
per call. With O(V) calls during traversal: O(V²). ``unordered_set::count`` is O(1) amortized:
|
|
O(V) total. QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/cmake-0001.md``
|