Taxonomy of Infinite Loop

In this page, we introduce the taxonomy of infinite loop and corresponding examples. We show the hierarchical taxonomy of infinite loops including four levels of categories. Our taxonomy of infinite loops consists of 10 inner categories (marked in grey color) and 16 leaf categories (marked in white color). To measure the frequency of bugs appearing in each category, we counted the number of bugs in each category and the number of projects where the bugs are located, shown in the upper right corner of each category in Figure 1.

Figure 1: Taxonomy of Infinite Loop

Category 1: Logical Error

From the program-logic perspective, the behavior of a loop iteration depends on the loop condition, the loop iterator variables, and the control statements (eg, break). Specifically, the loop continues to iterate while the condition is true, a loop iterator variable (or loop iterator) serves as an index of the loop and may affect the value of loop conditions, and control statements may change the flow of loop execution. Logical errors are divided into three categories related to these three loop elements (ie, Category 1.1, 1.2, and 1.3). In total, there are 10 specific leaf categories under Category 1.

Category 1.1: Loop Iterator Error

During loop execution, loop variables are updated iteratively. A Loop Iterator Error refers to an incorrect update to loop iterators, making the loop condition to be always true. Updates to loop iterators usually involve only a few lines of code but are error-prone when their cascading effects span multiple iterations. We found 149 loop iterator bugs rooted in different causes.

Category 1.1.1: Misusing Same Loop Iterator in Nested Loops

We observed that, in nested loops, developers may confuse the loop iterators of the inner loops with those of the outer loops. There are six infinite loops (4.0%) which are caused by reusing the same iterator in nested loops. For example, if the inner loop incorrectly uses the loop iterator of the outer loop (eg, setting it to zero), the outer loop never terminates. Listing 1 shows an example of Missusing Same Loop Iterator from the project ``fontforge''.

url: https://github.com/fontforge/fontforge/commit/abfc4cd510940dee22cdd00bde086ef626f55beb

commit: abfc4cd510940dee22cdd00bde086ef626f55beb

In this case, the loop iterator i is reused in nested loop. In inner loop, the variable i is updated, which makes i satisfy i < index forever and causes infinite loop.

Category 1.1.2.1: Missing Iterator Update

To our surprise, there are 74 cases (59.7% of Category 1.1.2) that are due to missing iterator updates (Category 1.1.2.1). Our analysis shows that, the iterator updating statements are missed in 54 cases which are often due to careless mistakes of developers. The remaining 20 cases are because the iterator updates are placed incorrectly after the continue statements, not being executed as a result. Listing 2 shows an example of Missusing Same Loop Iterator from the project ``busybox''.

url: https://github.com/mirror/busybox/commit/8e8041115121524c3a3d6c06abea53fd1fcbbd62

commit: 8e8041115121524c3a3d6c06abea53fd1fcbbd62

In this case, because of missing iterator i update before “continue”, the loop falls into infinite loop and always execute only one path when if condition is satisfied.

Category 1.1.2.2: Adding/Subtracting Zero

Another group of errors (37.1%) are caused when the change made to the iterator value is effectively zero (Category 1.1.2.2). Listing 3 shows an example of Adding/Subtracting Zero from the project ``freetype ''.

url:https://github.com/freetype/freetype/commit/b80d85fe9ed3b0cf96d03dcfd7d1e1f149c2b718

commit: b80d85fe9ed3b0cf96d03dcfd7d1e1f149c2b718

In this case, the function read can return 0 forever when EOF is reached. Therefore, the variable total_read_count will be constant because it adds read_count (ie, 0).

Category 1.1.2.3: Incorrect Bit Calculation

Bit manipulations (Category 1.1.2.3), such as `&' (AND), `|' (OR), and `<<' (shift left), can also lead to such errors. We show an example of Bit Operation from the project ``brltty''.

url:https://github.com/brltty/brltty/commit/5bec3fff0bac50f4b4d4d3b02e70161a2bf38d0f

commit:5bec3fff0bac50f4b4d4d3b02e70161a2bf38d0f

In this case, the loop terminates only if wc becomes zero. However, since wc is an extended signed character type (ie, wchar_t), the loop makes no progress if wc is negative before entering the loop. Because of the shift-right operations, wc will eventually remain -1, causing a non-termination.

Category 1.1.3.1: Missing Initialization

Variable initialization is important but error-prone. We found 13 cases (8.7%) that are caused by the incorrect initialization of loop iterators, such as Missing Initialization (category 1.1.3.1) and Incorrect Initialization (category 1.1.3.2). Listing 4 shows an example of Missing Initialization from the project `` ffmpeg ''.

url: https://github.com/FFmpeg/FFmpeg/commit/407a3d94f566a68c7a862fcdac812bf53741af94

commit: 407a3d94f566a68c7a862fcdac812bf53741af94

In this case, the loop will be stuck between the outer loop and inner loop because of the missing initialization of res, which makes the inner loop never to be executed.

Category 1.1.3.2: Incorrect Initialization

Incorrect initialization can also affect the loop execution, which mainly include incorrect positions of initialization statements (eg, the initialization for the outer loop is incorrectly put in the inner loop) and incorrect initialization values (eg, the binary search may not terminate if the variables low and high}are not initialized properly). We show an infinite loop bug from "keepalived" project. Because the source program is too cumbersome, it is not shown here. Please see the url below.

url: https://github.com/acassen/keepalived/commit/d37b2f4794acf1b0b431110c5e1fb23d652c5962

commit: d37b2f4794acf1b0b431110c5e1fb23d652c5962

Category 1.1.4: Incorrect Update for Loop Iterators

Incorrect updates to loop iterators lead to non-termination. We identified six infinite loops that are caused by incorrectly updated loop iterators. Note that we distinguish this category from Category 1.1.2, because we would like to emphasize the different effects of no update and incorrect update. No update for loop iterator (ie, Category 1.1.2) causes the loop to get stuck in one state, while incorrect updates may cause the loop to get stuck in a recurrent set of states. We show an infinite loop from the asterisk project.

url: https://github.com/asterisk/asterisk/commit/3322180d4b452e11545b70abc9b2d5af3d241361

Commit: 3322180d4b452e11545b70abc9b2d5af3d241361.

In each loop iteration, l is decreased by 2, which results in an infinite execution if l is initialized to an odd number.

Category 1.2: Incorrect Control Statement

Control statements are used to direct the control flow of the loop execution. In our analysis, 14 of the logical errors (5.1%) are attributed to the incorrect control statements (ie, break, goto, and continue). For example, the continue and break statements can be misused; break statements can be placed at incorrect locations, resulting in incorrect termination condition; and goto statements may jump to incorrect program locations. We show an infinite loop example from "freeradius-server" project. commit:

url:https://github.com/FreeRADIUS/freeradius-server/commit/e6801c90311679fc0854af73da95fe58079c59f4

When *p is ':' (ie, line 6) and the if condition in not satisfy, the break will be executed, which makes p and stop stable.

Category 1.3: Loop Condition Error

Loop conditions determine whether the loop can start or terminate. A proper loop condition is critical for the correctness and termination of the loop. We observed that a large number of infinite loops (40.3%) are caused by the incorrect loop conditions

Category 1.3.1: Missing Corner-case Handling

The loop condition restricts the scope of states (ie, different values of variables) that can be reached. If the scope is not well designed, it may cause infinite execution. We observe 76 bugs caused by loose conditions that miss handling some corner-cases. 11 of them are caused by the general incorrect comparison operators (eg, use i ≤ 0 rather than i < 0 ). The incorrect comparison operators can miss some boundary checking. We show an infinite loop caused by the missing corner-case handling from "libssh".

url: https://github.com/substack/libssh/commit/1b15896e8b29561447fff9a7bcaa028179eab51b

commit: 1b15896e8b29561447fff9a7bcaa028179eab51b

The comparison operator is not correct, which makes that the loop condition always satisfied. channel_read function returns 0 if no more data can be read. The remaining 65 cases are caused by the loose conditions that are more related to the specific business logic of the programs.

Category 1.3.2: Using Erroneous Condition

It is worth noting that there are 34 bugs (30.9%) caused by the totally incorrect loop conditions. These conditions may use incorrect iterator variables, incorrect termination logic or TRUE condition (the value is always true), indicating the difficulty of setting correct termination conditions in some loops. We show an infinite loop from "binutils-gdb".

url: https://github.com/bminor/binutils-gdb/commit/8455d26243aef72f7b827ec0d8367b6b7816de07

commit:8455d26243aef72f7b827ec0d8367b6b7816de07

It is obvious that the loop condition can always be true when cached_frame->reg_count is not zero.

Category 2: General Programming Error

In addition to the logical errors about the loop design, we observe that general programming errors can also lead to infinite loops, which account for 14.2% infinite loops. Specifically, integer overflow, variable type casting and undefined behavior can affect the update of loop iterators, resulting in non-termination. These errors are not directly related to the loop logic. Hence, it is hard to detect them by existing termination tools that mainly focus on the logic errors.

Category 2.1: Overflow

Without good consideration for overflow, developers can misestimated the update of loop iterators during the loop execution. We observe 15 infinite loops (4.7%) that are caused by overflow including Unsigned Wraparound Error (Category 2.1.1) and Signed Overflow Error (Category 2.1.2).

Category 2.1.1: Unsigned Wraparound Error

For unsigned integer types, wraparound operations will be executed when the value of the variable is out of scope. For example, the result of expression ``UINT_MAX+1'' will be 0, which is well-defined. Due to the wraparound of unsigned numbers, the loop iterators can never break the loop condition, causing the infinite loops. We find 9 infinite loops due to wraparound of unsigned numbers, which account for 2.83% of all infinite loops. We show an example infinite loop from "mupdf".

url: https://github.com/ArtifexSoftware/mupdf/commit/ce9d4462423ac74a1dbbc4ce52c2c81cfcdda766

commit:ce9d4462423ac74a1dbbc4ce52c2c81cfcdda766

size_t is an unsigned type. If n is less than 16, n will be wrapped around to be another large positive value.

Category 2.1.2: Signed Overflow Error

It is well-defined that wraparound operation will be executed when overflow or underflow of unsigned integer occurs. But when overflow occurs, the results of signed integer types maybe various. In general, wraparound operation will be executed when overflow or underflow of signed integer occurs, ie, the result of expression INT_MAX+1 is INT_MIN. Similarly, Signed Overflow Error leads to the abnormal change of loop iterators, leading to infinite execution. We totally find 6 bugs, accounting for 1.89% of all loop bugs.

We show an example infinite loop from "git".

url: https://github.com/git/git/commit/d306f3d3513c62342fec4e31457766f2473f9e9a

commit: d306f3d3513c62342fec4e31457766f2473f9e9a

Because of signed overflow, i could be negative and finally i becomes 0.

Category 2.2: Incorrect Variable Type

The storage of different types of variables are different (ie, different ranges). Incorrect use of variable types can also cause infinite loops by changing the value of loop iterators abnormally. There are 24 bugs in this category including Type Conversion (Category 2.2.1) and Misuse Variable Type (Category 2.2.2).

Category 2.2.1.1: Type Conversion in Comparison

When the types of left values and right values do not match, the type conversion can happen in assignment statements and comparison statements, which can affect the value of loop iterators and loop conditions. There are a total number of 14 bugs caused by type conversion including 9 Type Conversion in Comparison bugs (Category 2.2.1.1) and 5 Type Conversion in Assignment bugs (Category 2.2.1.2). Listing 5 shows an infinite loop from “owntone-server”.

url:

https://github.com/owntone/owntone-server/commit/f9bfec180f91671d8ba72a01cab1781c1f5e9999

commit: 407a3d94f566a68c7a862fcdac812bf53741af94

This loop will get stuck when 𝑠𝑒𝑞𝑛𝑢𝑚+𝑙𝑒𝑛 is greater than UINT16_MAX. In this case, bit expansion will occur, the type of the right value in the loop condition will be a large 32-bit integer, i.e., it is greater than UINT16_MAX. The detail can be seen in IR. In line 24, before adding, len and seqnum are expanded into 32 bits by zero expansion, which makes len+seqnum greater than UINT16_MAX.

Category 2.2.1.2: Type Conversion in Assignment

url:

https://github.com/kmatheussen/das_watchdog/commit/57e7400d046f382ee94745791ccb0e1a06efb2e4

commit: 57e7400d046f382ee94745791ccb0e1a06efb2e4

The program in commit is char in line 2, but the commit message shows that the loop would go into an infinite loop when asked to find a variable that doesn't exist on a platform where char is unsigned (e.g. ARM): fgetc would return -1 (EOF), which would be stored as 255 in temp[i], which then wouldn't be equal to -1 when testing.

Category 2.2.2: Misusing Variable Type

The type of a variable determines the range of its values. The incorrect type may limit the range of the loop iterator, which can lead to an infinite loop. We totally find 10 bugs caused by misusing variables, which accounts for 3.14% of infinite loops. We show an infinite loop bug from "linux_media".

url:https://github.com/ljalves/linux_media/commit/090341b0a95d1f6d762915a75c13b393366f4ab3

commit:090341b0a95d1f6d762915a75c13b393366f4ab3

Because div1 and div2 are unsigned variable, they never become negative. Hence, the loop condition div1 ≥ 0 and div2 ≥ 0 will be always TRUE.

Category 2.3: Undefined Behavior

During our classification, we find some potential infinite bugs caused by undefined behavior and the termination of these programs may be different in different compilers and platforms. The best-known examples of undeﬁned behaviors in programming languages come from C and C++, which have hundreds of them, including simple local operations (overﬂowing signed integer arithmetic). Undefined Behavior could make unexpected consequences (eg, Silent Breakage, Time Bombs), which depends on different compilers and platforms.The unexpected consequences can affect the termination of loops. In our study, undefined behavior is a root cause of infinite loop, accounting for 1.9% of all loop bugs and involving 2.92% projects.

We show a potential non-termination loop bug from ``FFmpeg''.

url:https://github.com/FFmpeg/FFmpeg/commit/d597655f771979c70c08f8f8ed84c1319da121e8

commit:d597655f771979c70c08f8f8ed84c1319da121e8

When the value of bytes is 8, uint64_t >> 64 is an undefined operation leading to the undefined behavior. Its value varies in different compilers and platforms, ie, the loop can be infinitely executed if its value is parsed as non-zero. The confirmation of this category of bugs is difficult. We confirmed these bugs from: 1) the commit messages that clearly point out the non-termination and 2) we reproduce them by simplifying the program. For example, we compile the above loop with gcc (version 7.3.0) in Ubuntu SMP Tue. When the value of val was initialized to -1, this loop falls into infinite loop.

Page updated

Google Sites

Report abuse