[BUG] Report on Stack Overflow Vulnerability in C/sorting/binary_insertion_sort.c

[N1nEmAn]

Title: Report on Stack Overflow Vulnerability in C/sorting/binary_insertion_sort.c

Abstract:
This report highlights a stack overflow vulnerability in the binary_insertion_sort.c file within the C/sorting directory. The vulnerability leads to a segmentation fault when executing the program with certain input sizes. Additionally, it is observed that when compiled with O2/O3 optimization flags, the program runs indefinitely without terminating.

1. Introduction:
The binary_insertion_sort.c file contains an implementation of the binary insertion sort algorithm in the C programming language. However, it has been discovered that the program encounters a segmentation fault and an infinite loop in specific scenarios, indicating potential stack overflow vulnerabilities and optimization-related issues.

2. Vulnerability Description:
The stack overflow vulnerability arises due to insufficient stack space allocation during the sorting process. As the binary insertion sort algorithm recursively calls itself, it relies on the stack to store intermediate values and function calls. If the size of the input array is large or the recursion depth becomes significant, the stack may overflow, resulting in a segmentation fault.

3. Reproduction Steps:
To reproduce the issue, follow these steps:
a. Compile the binary_insertion_sort.c file using the GCC compiler:

gcc binary_insertion_sort.c

b. Execute the compiled program:

./a.out

c. When prompted, enter the size of the array and provide the corresponding elements.

Enter size of array:
50
Enter the elements of the array
10 81 36 5 96 13 61 56 83 20 63 91 37 56 64 92 20 88 13 27 96 74 69 81 39 72 48 57 35 3 59 32 58 9 18 34 1 64 72 32 95 86 38 31 60 79 99 59 45 76
Original array: 10 81 36 5 96 13 61 56 83 20 63 91 37 56 64 92 20 88 13 27 96 74 69 81 39 72 48 57 35 3 59 32 58 9 18 34 1 64 72 32 95 86 38 31 60 79 99 59 45 76
zsh: segmentation fault (core dumped)  ./a.out

d. Observe the segmentation fault error message indicating a program crash.

And, if compile with O2/O3, it runs without stop.

4. Impact:
The stack overflow vulnerability has the following potential impact:

• Program crash: The vulnerability leads to a segmentation fault, causing the program to terminate abruptly.
• Denial of Service: An attacker may exploit this vulnerability to repeatedly crash the program, resulting in a denial of service condition.

5. Mitigation:
To address the stack overflow vulnerability, the following steps are recommended:
a. Increase stack size: Allocate a larger stack size to handle larger input arrays and deeper recursion levels. This can be achieved by adjusting compiler or linker options or using platform-specific techniques.
b. Implement iterative sorting: Consider modifying the algorithm to use an iterative approach instead of recursion, eliminating the reliance on the stack.
c. Input validation: Implement proper input validation to ensure that the input array size is within acceptable limits.
d. Error handling: Enhance error handling mechanisms to handle exceptional conditions gracefully and prevent crashes.

6. Optimization-related Issue:
The observed behavior of the program running indefinitely when compiled with O2/O3 optimization flags suggests a potential issue with the optimization process. Further investigation and analysis are required to understand the root cause and implement necessary fixes.

7. Conclusion:
The stack overflow vulnerability identified in the binary_insertion_sort.c file can lead to program crashes and potential denial of service conditions. Additionally, the observed optimization-related issue requires attention to ensure the program terminates correctly. By implementing the recommended mitigation measures and addressing the optimization-related issue, developers can enhance the stability, security, and performance of the code.

Expected behavior

Program crash: The vulnerability leads to a segmentation fault, causing the program to terminate abruptly. Denial of Service: An attacker may exploit this vulnerability to repeatedly crash the program, resulting in a denial of service condition.

Actual behavior

Program crash: The vulnerability leads to a segmentation fault, causing the program to terminate abruptly. Denial of Service: An attacker may exploit this vulnerability to repeatedly crash the program, resulting in a denial of service condition.

Possible fix

change the logic of program

Steps to reproduce

To reproduce the issue, follow these steps:
a. Compile the binary_insertion_sort.c file using the GCC compiler:

gcc binary_insertion_sort.c

b. Execute the compiled program:

./a.out

c. When prompted, enter the size of the array and provide the corresponding elements.

Enter size of array:
50
Enter the elements of the array
10 81 36 5 96 13 61 56 83 20 63 91 37 56 64 92 20 88 13 27 96 74 69 81 39 72 48 57 35 3 59 32 58 9 18 34 1 64 72 32 95 86 38 31 60 79 99 59 45 76
Original array: 10 81 36 5 96 13 61 56 83 20 63 91 37 56 64 92 20 88 13 27 96 74 69 81 39 72 48 57 35 3 59 32 58 9 18 34 1 64 72 32 95 86 38 31 60 79 99 59 45 76
zsh: segmentation fault (core dumped)  ./a.out

d. Observe the segmentation fault error message indicating a program crash.

And, if compile with O2/O3, it runs without stop.

Context

• This project is a standard algorithm library, which could potentially expose users employing these algorithms to attacks.

Additional information

No response

[hasan-alkama]

@N1nEmAn
Implement iterative sorting: Consider modifying the algorithm to use an iterative approach instead of recursion, eliminating the reliance on the stack.
Given the nature of the vulnerability, where deep recursion levels contribute to stack overflow, an iterative approach that does not consume stack space with function calls seems like the most appropriate solution.
can i create a PR which solves this issue by writing the same logic in iterative way? if yes can you assigned this issue to me?
thanks

[N1nEmAn]

@hasan-alkama Sure, please go ahead and create a PR to solve this issue by implementing the iterative approach. I will assign the issue to you. Thanks!

The new code can be referred to as follows:

/* Sorting of array list using binary insertion sort
 * Using binary search to find the proper location for
 * inserting the selected item at each iteration. */

#include <stdio.h>
#include <stdlib.h>

/* Displays the array passed to this method */
void display(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

/* Performs binary search to find the proper index for inserting the key */
int binarySearch(int *arr, int key, int low, int high)
{
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key)
            return mid; // Key found, return its index
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low; // Key not found, return the index where it should be inserted
}

/* This is where the sorting of the array takes place
 * arr[] --- Array to be sorted
 * size --- Array Size
 */
void insertionSort(int *arr, int size)
{
    int i, j;
    for (i = 1; i < size; i++)
    {
        int key = arr[i];
        j = i - 1;

        /* Find the proper index for inserting the key */
        int index = binarySearch(arr, key, 0, j);

        /* Move all elements greater than key from [index...j]
         * to one position */
        while (j >= index)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        /* Insert key value in the correct position */
        arr[j + 1] = key;
    }
}

int main(int argc, const char *argv[])
{
    int n;
    printf("Enter size of array:\n");
    scanf("%d", &n); // E.g. 8

    printf("Enter the elements of the array\n");
    int i;
    int *arr = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    printf("Original array: ");
    display(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: ");
    display(arr, n);

    free(arr);
    return 0;
}

In this version, we have modified the binarySearch function to its iterative form while retaining the original comments and variable names.

[N1nEmAn]

@hasan-alkama Apologies, I don't have the authority to assign issues. We'll need @Panquesito7 @tjgurwara99 @alexpantyukhin to handle the assignment. Thanks for your understanding and patience!

[github-actions]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions]

Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!