russell@unturf.com
78f834e1e7
InFlightMetadataCollectorImpl.buildRecursiveOrderedFkSecondPasses() lacks a visited-table set — only guards against direct self-cycles (startTable check). On diamond FK dependency graphs (A references B and C, both B and C reference D), node D is visited 2^depth times. At depth=10: 25.9x overhead; at depth=13: 124x. Fix: add Set<String> visitedTables parameter; skip re-entry with visited.add(). Unit test: HibernateFkDiamondRecursionTest.java — confirms exponential growth and correctness (both algorithms produce identical FK sets). 4/4 assertions PASS. Separate from hibernate-0004 (which addressed the O(N^2) ArrayList.contains() in the same method); that patch uses LinkedHashSet to deduplicate output but does not prevent exponential recursive traversal of intermediate diamond nodes. spring and ant: diamond recursion scan CLEAN markers added.
25 lines
1.9 KiB
Markdown
25 lines
1.9 KiB
Markdown
# Spring Framework — Diamond Recursion (CWE-407 O(2^D)) Scan: CLEAN
|
|
|
|
**Pattern:** Recursive cycle-detection / dependency traversal without a visited set
|
|
(exponential re-visitation on diamond-shaped DAGs)
|
|
**Scan date:** 2026-03-29
|
|
**Scope:** `spring-beans`, `spring-context`, `spring-core`, `spring-aop`, `spring-web`
|
|
|
|
## Methods Checked
|
|
|
|
| Method | Location | Guard | Result |
|
|
|--------|----------|-------|--------|
|
|
| `DefaultSingletonBeanRegistry.isDependent` | `spring-beans/.../support/DefaultSingletonBeanRegistry.java:630` | `Set<String> alreadySeen` parameter — O(1) HashSet | CLEAN |
|
|
| `DefaultLifecycleProcessor.doStart` | `spring-context/.../support/DefaultLifecycleProcessor.java:395` | `lifecycleBeans.remove(beanName)` — once removed, bean skipped on re-entry | CLEAN |
|
|
| `DefaultLifecycleProcessor.doStop` | `spring-context/.../support/DefaultLifecycleProcessor.java:458` | Same `lifecycleBeans.remove` guard | CLEAN |
|
|
| `DefaultListableBeanFactory.hasPrimaryConflict` | `spring-beans/.../support/DefaultListableBeanFactory.java:2272` | Traverses parent bean factory chain (linear, not DAG) | CLEAN |
|
|
| `DefaultListableBeanFactory.checkBeanNotOfRequiredType` | `spring-beans/.../support/DefaultListableBeanFactory.java:2304` | Traverses parent chain (linear) | CLEAN |
|
|
| `ConfigurationClassParser.collectImports` | `spring-context/.../annotation/ConfigurationClassParser.java:562` | `Set<SourceClass> visited` parameter | CLEAN |
|
|
| `AnnotationTypeMapping.computeSynthesizableFlag` | `spring-core/.../annotation/AnnotationTypeMapping.java:261` | `Set<Class<?>> visitedAnnotationTypes` passed through | CLEAN |
|
|
|
|
## Conclusion
|
|
|
|
No diamond recursion defect found in Spring Framework. All recursive graph-traversal
|
|
methods have proper visited-set guards. The `isDependent` method (the most critical
|
|
path for circular bean dependency detection) was fixed in a prior version to add
|
|
`alreadySeen` — the fix predates this scan.
|