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
