CWE Rule 674

Uncontrolled Recursion

Since R2024a

Description

Rule Definition

The product does not properly control the amount of recursion that takes place, consuming excessive resources, such as allocated memory or the program stack.

Polyspace Implementation

This rule checker checks for recursive functions that do not update their parameters.

Examples

Recursive Functions That Do Not Update Their Parameters

Issue

The issue occurs when a recursive function passes parameters to its recursive call without correctly updating those parameters, resulting in uncontrolled recursion. For example, in this code snippet, function myRecursiveFunction never reaches its base case (cond < 0) because the parameter cond is not updated in the recursive call inside the else branch.

void myRecursiveFunction(int cond)
{
    if (cond < 0)
    {
        // Base case, exit
        return;
    }
    else
    {
        // Recursive call using same value of
        // parameter cond
        myRecursiveFunction(cond);
        // A correct implementation would be
        // to call myRecursiveFunction(cond-1)
    }
}

Executing the previous code results in an infinite recursion.

Polyspace does not check indirect recursions or recursions that you implement with labels and goto statements.

Risk

Uncontrolled recursions lead to repeated function calls which consume stack memory and other resources, such as file descriptors if the function opens a file on each call. These repeated function calls can in turn lead to a stack overflow, a system crash, or even security vulnerabilities.

Fix

Check that your function has a reachable base case or that it exits with the appropriate error if the recursion reaches a certain depth.

Example — Recursive Function With Uncontrolled Recursion

int sumTriangular(int var) // Noncompliant
{ 
    if (var == 1)
    {
        // base case
        return 1;
    }
    // Parameter of sumTriangular() is not updated
    return var + sumTriangular(var);
}

In this example, the function sumTriangular is a recursive implementation of the triangular number sequence. Polyspace reports this function as noncompliant because the parameter var in the recursive call to sumTriangular is not updated, which results in an infinite recursion and a segmentation fault caused by a stack overflow.

Correction — Update Parameter of Recursive Function

int sumTriangular(int var) // Compliant
{ 
    if (var == 1)
    {
        // base case
        return 1;
    }
    return var + sumTriangular(var-1);
}

One possible correction is to update the parameter var by decrementing it so that the recursion reaches the base case and exits.

Check Information

Category: Others

Version History

Introduced in R2024a