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.
112 lines
4.3 KiB
ReStructuredText
112 lines
4.3 KiB
ReStructuredText
FRRouting — CWE-407 Analysis
|
||
==============================
|
||
|
||
.. contents:: :local:
|
||
|
||
Overview
|
||
--------
|
||
|
||
FRRouting (FRR) is a widely deployed open-source routing protocol suite, implementing OSPF,
|
||
BGP, IS-IS, RIP, and other protocols on Linux and other Unix-like operating systems. It is used
|
||
in production by major cloud providers, ISPs, and network appliance vendors as both a software
|
||
router and a control-plane daemon on physical switching hardware.
|
||
|
||
Status: **CONFIRMED DEFECT — frrouting-0001** (scanned 2026-03-23)
|
||
--------------------------------------------------------------------
|
||
|
||
One confirmed CWE-407 defect in the TI-LFA fast-reroute extension. OSPF SPF (main path),
|
||
BGP, IS-IS, and LDP are clean.
|
||
|
||
Confirmed Defect
|
||
----------------
|
||
|
||
**frrouting-0001** — ``ospfd/ospf_ti_lfa.c``
|
||
|
||
The TI-LFA (Topology-Independent Loop-Free Alternate) fast-reroute implementation calls
|
||
``listnode_lookup()`` — FRR's O(n) linked-list linear search — at 5 call sites within
|
||
path-computation loops that iterate over all protected segments:
|
||
|
||
.. code-block:: c
|
||
|
||
/* ospfd/ospf_ti_lfa.c */
|
||
listnode_lookup(p->hops, node) /* line 72 */
|
||
listnode_lookup(p->hops, node) /* line 114 */
|
||
listnode_lookup(p->hops, node) /* line 227 */
|
||
listnode_lookup(p->hops, node) /* line 278 */
|
||
listnode_lookup(p->hops, node) /* line 285 */
|
||
|
||
``listnode_lookup`` is defined in ``lib/linklist.c`` as a linear scan over FRR's
|
||
doubly-linked list. TI-LFA checks whether a candidate path hop is already in the path for
|
||
each of N protected elements, each with P candidate paths of length H:
|
||
total cost **O(N × P × H)** — cubic in the common case.
|
||
|
||
Complexity Analysis
|
||
^^^^^^^^^^^^^^^^^^^
|
||
|
||
+----------------------------+----------------------------------+
|
||
| Metric | Expression |
|
||
+============================+==================================+
|
||
| Correct complexity | O(N × P) with O(1) membership |
|
||
+----------------------------+----------------------------------+
|
||
| Defective complexity | O(N × P × H) — H path length |
|
||
+----------------------------+----------------------------------+
|
||
| Example: 100 nodes, 3 paths, 20 hops | 6000 ops vs 300 |
|
||
+----------------------------+----------------------------------+
|
||
|
||
Threat Model
|
||
^^^^^^^^^^^^
|
||
|
||
TI-LFA computes backup paths triggered by any OSPF topology change (link or node failure).
|
||
In large topologies, failure events cause simultaneous TI-LFA recomputation on all routers
|
||
that protect the failed element. A crafted LSA injection or link-flap attack against a large
|
||
OSPF domain triggers O(n³) work per router per event. With N routers each doing O(n³) work
|
||
on a fault, the total convergence load scales as O(n⁴) across the domain.
|
||
|
||
OSPF SPF (Main Path) — CLEAN
|
||
------------------------------
|
||
|
||
``ospfd/ospf_spf.c`` is clean: it uses the ``LSA_SPF_IN_SPFTREE`` boolean flag set directly
|
||
on each LSA struct for O(1) visited tracking, plus a skip-list priority queue for the
|
||
candidate list. The main OSPF Dijkstra convergence path is not affected.
|
||
|
||
BGP, IS-IS, LDP — CLEAN
|
||
------------------------
|
||
|
||
No candidates found in ``bgpd``, ``isisd``, or ``ldpd``. BGP AS-path loop detection
|
||
(``aspath_loop_check``) iterates a path bounded by BGP's 255-hop maximum — O(n) but not
|
||
inside a topology loop, and the bound is tight. Not a defect.
|
||
|
||
Fix
|
||
---
|
||
|
||
Replace ``listnode_lookup()`` at all 5 sites with a boolean ``ti_lfa_visited`` flag on the
|
||
node struct (FRR node structs are already extended for SPF state):
|
||
|
||
.. code-block:: c
|
||
|
||
/* Before */
|
||
if (listnode_lookup(p->hops, node) == NULL)
|
||
listpath_add_node(p, node);
|
||
|
||
/* After */
|
||
if (!node->ti_lfa_visited) {
|
||
node->ti_lfa_visited = true;
|
||
listpath_add_node(p, node);
|
||
}
|
||
/* Reset flags after TI-LFA computation for this protected element */
|
||
|
||
Work Checklist
|
||
--------------
|
||
|
||
- [ ] Patch ``ospf_ti_lfa.c`` × 5 call sites with node flag
|
||
- [ ] Unit test: path membership correct, verify O(1) per check
|
||
- [ ] Integration test: TI-LFA backup path correct for sample topology
|
||
- [ ] Benchmark: TI-LFA recomputation time before/after on 100-node topology
|
||
- [ ] Disclose to FRR security contact before public announcement
|
||
|
||
References
|
||
----------
|
||
|
||
* Defect ticket: ``tools/tickets/defects/frrouting-0001.md``
|
||
* Scan result: ``tools/scan-results/frrouting.txt``
|
||
* FRR security contact: https://frrouting.org/community/security
|