russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
82 lines
2.8 KiB
Markdown
82 lines
2.8 KiB
Markdown
---
|
||
id: solc-0001
|
||
repo: ethereum/solidity
|
||
file: libyul/optimiser/CallGraphGenerator.cpp
|
||
line: 49
|
||
status: unpatched
|
||
severity: HIGH
|
||
complexity: O(F × D²) — F functions, D max call depth
|
||
pattern: std::find on std::vector<FunctionHandle> currentPath in DFS cycle detector
|
||
---
|
||
|
||
## Description
|
||
|
||
`CallGraphCycleFinder::visit()` maintains `currentPath` as a `std::vector<FunctionHandle>`
|
||
representing the current DFS stack. On every node visited, it calls:
|
||
|
||
```cpp
|
||
auto it = find(currentPath.begin(), currentPath.end(), _function); // O(|path|)
|
||
```
|
||
|
||
This is an O(|path|) linear scan to check whether `_function` is already on the current
|
||
DFS path (i.e., whether we've found a cycle back to it). For a call graph with F functions
|
||
and maximum call depth D, the total cost is O(F × D²).
|
||
|
||
The developer left a comment at line 36: `// TODO: This algorithm is non-optimal.`
|
||
|
||
## Context
|
||
|
||
`CallGraph::recursiveFunctions()` is called during Yul optimizer passes to identify which
|
||
functions are recursive (so they can be handled differently during inlining and optimization).
|
||
It is invoked on every contract compiled through the Yul IR pipeline, which includes all
|
||
contracts compiled with `--via-ir` or `--optimize` on modern solc.
|
||
|
||
## Fix
|
||
|
||
Maintain a parallel `std::set<FunctionHandle>` (or `std::unordered_set` if hash is available)
|
||
alongside `currentPath`:
|
||
|
||
```cpp
|
||
struct CallGraphCycleFinder {
|
||
CallGraph const& callGraph;
|
||
std::set<FunctionHandle> containedInCycle{};
|
||
std::set<FunctionHandle> visited{};
|
||
std::vector<FunctionHandle> currentPath{};
|
||
std::set<FunctionHandle> currentPathSet{}; // CWE-407 fix
|
||
|
||
void visit(FunctionHandle const& _function) {
|
||
if (visited.count(_function))
|
||
return;
|
||
if (currentPathSet.count(_function)) // O(log n) instead of O(|path|)
|
||
{
|
||
// Cycle confirmed — find position for range insert (rare, O(|path|) ok)
|
||
auto it = find(currentPath.begin(), currentPath.end(), _function);
|
||
containedInCycle.insert(it, currentPath.end());
|
||
}
|
||
else {
|
||
currentPathSet.insert(_function);
|
||
currentPath.emplace_back(_function);
|
||
if (callGraph.functionCalls.count(_function))
|
||
for (auto const& child: callGraph.functionCalls.at(_function))
|
||
visit(child);
|
||
currentPath.pop_back();
|
||
currentPathSet.erase(_function);
|
||
visited.insert(_function);
|
||
}
|
||
}
|
||
};
|
||
```
|
||
|
||
The fallback `find` inside the cycle-detected branch runs only when a cycle is actually
|
||
found — rare in practice. The hot path (no cycle) is now O(log D) per node instead of O(D).
|
||
|
||
## Complexity after fix
|
||
|
||
O(F × D × log D) instead of O(F × D²).
|
||
|
||
## Work items
|
||
|
||
- [ ] patch
|
||
- [ ] unit test (operation count: comparisons before and after at F=100, D=50)
|
||
- [ ] integration test (contracts with recursive Yul functions)
|
||
- [ ] benchmark
|