Taxonomy of Infinite Recursion

Recursion is another repeated structure that one of the steps of the function reenters the function itself. Figure 2 illustrates the hierarchical taxonomy of infinite recursion bugs in real-world C and C++ projects. Generally speaking, our taxonomy of infinite recursion bugs consists of 4 inner categories (in grey) and 8 leaf categories (in white). Because recursion in real-world projects involves a lot of code, the examples we provide are relatively simplified.

Figure 2: Taxonomy of Infinite Recursion

Category 1: Incorrect Recursion Design

Category 1.1: Incorrect Arguments

Category 1.2: Incorrect Return

Category 1.3: Deep Recursion

Category 2: Unexpected Recursion

Category 2.1: Incorrect Self-invoking

Category 2.2: Incorrect Cyclic Invoking

Category 1: Incorrect Recursion Design

The termination of recursion mainly depends on the argument that will be sent to the parameters of the recursive function and the return that can determine the exit of the current iteration. In general, the incorrect recursion is mainly caused by Incorrect Arguments (Category 1.1), Incorrect Return (Category 1.2) and Deep Recursion (Category 1.3).

Category 1.1: Incorrect Arguments

We observe 7 infinite recursions (10.8%) in Incorrect Recursion that are caused by using the unchanged arguments. Similar with loop, the arguments determine the number of iterations. If the arguments keep unchanged, the recursion gets stuck to a state (ie, the values of arguments do not change) leading to the infinite execution. We show an infinite recursion from commit 084a7f4a5a5c859ab24e727ef92f9b2ed8611acf. We can see that gaim_xfer_cancel can call gaim_xfer_destroy, but when xfer->bytes_remaining > 0 , gaim_xfer_destroy can call gaim_xfer_cancel, which makes recursion. Without the gree line, before calling gaim_xfer_destroy, xfer->bytes_remaining never be changed to 0, which makes the recursion become infinite.

// commit 084a7f4a5a5c859ab24e727ef92f9b2ed8611acf

typedef struct gaim_xfer{

int watcher;

int fd;

int bytes_remaining;

}gaim_xfer;

void gaim_xfer_cancel(struct gaim_xfer *xfer){

if (xfer == 0)

return;

if (xfer->watcher != 0) {

xfer->watcher = 0;

}

if (xfer->fd != 0)

xfer->fd = 0;

+ + xfer->bytes_remaining = 0;

/* Delete the transfer. */

gaim_xfer_destroy(xfer);

}

void gaim_xfer_destroy(struct gaim_xfer *xfer){

if (xfer == 0)

return;

if (xfer->bytes_remaining > 0) {

gaim_xfer_cancel(xfer);

return;

}

free(xfer);

}

Category 1.2: Incorrect Return

Most (38.5%) of the incorrect recursions are caused by the incorrect return. Without loss of generality, a recursive function that does not return anything can be considered to return null. It is usually because of the incomplete condition for return. For example, the current iteration should exit, but couldn't because of incorrect return condition. We want to show an infinite recursion from commit ec79a06d084e7f7508fcfad583258163d8066e7b. But it is too long to show here. We extract it as benchmark and the detail can be seen in our benchmark.

Category 1.3: Deep Recursion

We also find a large part of recursion bugs (50.7%) in Incorrect Recursion that can cause stack overflow rather than non-termination bugs. When recursion is executed, the variables and some information need to be saved into the stack. As the recursion can be excessively deep, it causes the call stack buffer overflow. The Deep Recursion bugs are usually related to complex data structures (\eg, binary tree traversal, compilation process and database operations).

Category 2: Unexpected Recursion

Programming errors can lead to unexpected recursion that does not terminate. Specifically, our study shows that Unexpected Recursion involves 62 infinite recursion bugs that cover 61.4% (43/70) projects. The major reasons include Incorrect Self-invoking (Category 2.1) and Cyclic Invoking (Category 2.2).

Category 2.1: Incorrect Self-invoking

There are 38 infinite recursions (29.9%) caused by that the function invokes itself incorrectly and unintentionally. Specifically, 12 of them are due to Misusing Namespace (Category 2.1.1). The function M::f intends to invoke another function N::f where M and N are different namespaces. However, developers forget to use N causing it to call itself. 6 of them are due to the Miscalling Inherited Method (Category 2.1.2). In C++ inheritance, the method m in a child class A intends to invoke the method m in another child class B, However, developers forget to use the class name B (ie, B::m), thus A::m calls itself. 15 of them are due to Misusing Method Overloading (Category 2.1.3). It happens when the method m intends to invoke another overloaded function m but it incorrectly invokes itself (ie, using the same arguments). 5 of them are caused by Missing undef Instruction (Category 2.1.4). For this category, developers first use define to define an identifier A as function B. However, in the function B, it invokes A (ie, itself) again before undef A.

friend flags operator ~(flags x){

- - return static_cast<flags>(static_cast<unsigned int>(~x));

+ + return static_cast<flags>(~static_cast<unsigned int>(x));

}

The above example shows an infinite recursion due to Misusing Method Overloading (Category 2.1.3) from commit 9e757605709cace0fc048ad284b2d6aa3ae784ac. This function overrides the operator ~, but in its function body, it uses operator ~ again. This operator ~ in function body will call the override function ~, which makes infinite recursion.

#define pthread_mutex_trylock my_pthread_mutex_trylock

+ + #undef pthread_mutex_trylock

int my_pthread_mutex_trylock(pthread_mutex_t *mutex)

{

int error=pthread_mutex_trylock(mutex);

if (error == 1) /* Safety if the lib is fixed */

return 0; /* Mutex was locked */

return error;

};

The above example shows an infinite recursion due to Missing undef Instruction (Category 2.1.4) from commit b546212a16a6ac3e9f40f332644345ceec96a0e7. By #define, pthread_mutex_trylock will be replaced by my_pthread_mutex_trylock , which makes function my_pthread_mutex_trylock call itself. This is unexpected recursion. By adding #undef, the recursion is fixed.

Category 2.2: Incorrect Cyclic Invoking

Compared to Category 2.1 that involves a self-invoking, there are 24 of infinite recursions (18.9%) that are caused by cyclic calling. Given two functions A and B, if A calls B and B also calls A, then the unexpected cyclic calling is formed, causing an infinite execution.