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.
79 lines
2.2 KiB
ReStructuredText
79 lines
2.2 KiB
ReStructuredText
LLVM/Clang — CWE-407 Analysis
|
||
==============================
|
||
|
||
.. contents:: :local:
|
||
|
||
Overview
|
||
--------
|
||
|
||
LLVM is a widely used compiler infrastructure project; Clang is the C/C++/Objective-C frontend
|
||
built on top of it. During Link Time Optimization (LTO), LLVM's ``GlobalsModRef`` pass builds
|
||
a call graph to determine which globals are modified by each function. One CWE-407 defect site
|
||
was found in the LTO call-graph traversal. It is unpatched.
|
||
|
||
Defect Sites
|
||
------------
|
||
|
||
llvm-0001
|
||
~~~~~~~~~
|
||
|
||
**File:** ``llvm/lib/Analysis/GlobalsModRef.cpp:570``
|
||
|
||
**Pattern:**
|
||
|
||
.. code-block:: cpp
|
||
|
||
// LTO call graph traversal — is_contained on vector of call graph nodes
|
||
SmallVector<CallGraphNode *, 8> visiting;
|
||
// ...
|
||
void analyzeCallGraph(CallGraphNode *node) {
|
||
if (is_contained(visiting, node)) return; // O(V) — is_contained is std::find
|
||
visiting.push_back(node);
|
||
for (auto &edge : *node) {
|
||
analyzeCallGraph(edge.second);
|
||
}
|
||
visiting.pop_back();
|
||
}
|
||
|
||
**Why this is O(n):** ``is_contained`` (an LLVM ADT helper) calls ``std::find`` on the
|
||
``SmallVector``, which is a linear scan. Called once per node per DFS frame.
|
||
|
||
**Complexity:** ``O(V×E)`` where V = call graph nodes, E = call edges (during LTO)
|
||
|
||
**Patch:**
|
||
|
||
.. code-block:: cpp
|
||
|
||
SmallPtrSet<CallGraphNode *, 8> visitingSet;
|
||
SmallVector<CallGraphNode *, 8> visiting; // keep for stack ordering
|
||
|
||
void analyzeCallGraph(CallGraphNode *node) {
|
||
if (!visitingSet.insert(node).second) return; // O(1) hash set
|
||
visiting.push_back(node);
|
||
for (auto &edge : *node) {
|
||
analyzeCallGraph(edge.second);
|
||
}
|
||
visiting.pop_back();
|
||
visitingSet.erase(node);
|
||
}
|
||
|
||
**Data structure change:** ``SmallVector<CGN*>`` + ``is_contained`` → ``SmallPtrSet<CGN*>`` + ``insert()``
|
||
|
||
**Status:** Unpatched
|
||
|
||
Benchmark Results
|
||
-----------------
|
||
|
||
.. TODO: benchmark pending patch
|
||
|
||
Complexity Proof
|
||
----------------
|
||
|
||
Let V = call graph nodes. ``is_contained`` scans a vector of up to V elements: O(V) per call.
|
||
With V calls during DFS: O(V²). ``SmallPtrSet::insert()`` returns a pair indicating whether
|
||
the element was newly inserted — O(1) amortized. Total: O(V). QED.
|
||
|
||
References
|
||
----------
|
||
|
||
* Defect ticket: ``tools/tickets/defects/llvm-0001.md``
|