1
\$\begingroup\$

Below is the code of Merge Sort for sorting an integer array in ascending order of values written by me. By looking at the code, I am thinking I can make the code more compact and secure, but not getting any ideas.

By secure, I mean, taking care of memory management, loopholes etc.

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
void mergesort(int*,int,int);
void mergeSequence(int*,int,int,int); //Merge the two arrays
void displaySequence(int*);
int n;
int main()
{
    int t,test;
    int*num=NULL;
    int i;
    printf("Enter the number of test cases\n", test);
    scanf("%d", &test);
    assert(test>0);
    for(t=0;t<test;t++)
    {
        printf("Enter the size of the sequence\n", n);
        scanf("%d", &n);
        assert(n>0);
        num=calloc(sizeof(int),n);
        assert(num);
        printf("Enter the sequence\n");
        for(i=0;i<n;i++)
            scanf("%d", (num+i));
        printf("Sequence before sorting\n");
        displaySequence(num);
        mergeSort(num,0,(n-1));
        printf("Sequence after sorting\n");
        display(num);
        free(num);
    }
    return 0;
}
void displaySequence(int*num)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ", num[i]);
    printf("\n");
}
void mergeSort(int*num,int start,int end)
{
    int mid;
    mid=start+((end-start)/2);
    printf("Mid->%d\n", mid);
    if(start<end)
    {
        mergeSort(num,start,mid);
        mergeSort(num,(mid+1),end);
        mergeSequence(num,start,mid,end);
    }

}
void mergeSequence(int*num,int start,int mid,int end)
{
    int n1,n2;
    int i,j,k;
    n1=(mid-start)+1;
    n2=(end-mid);
    printf("N1->%d\nN2->%d\n", n1,n2);
    int left[n1];
    int right[n2];
    for(i=0;i<n1;i++)
        left[i]=num[start+i];
    for(i=0;i<n1;i++)
        printf("%d ", left[i]);
    printf("\n");
    for(j=0;j<n2;j++)
        right[j]=num[(mid+1)+j];
    for(j=0;j<n2;j++)
        printf("%d ", right[j]);
    printf("\n");
    //Now I have two arrays, and I can now merge them
    k=start;
    i=0;
    j=0;
    while((k<=end))
    {
        if(i==n1)
        {
            num[k]=right[j];
            j++;
        }
        else if(j==n2)
        {
            num[k]=left[i];
            i++;
        }
        else if(left[i]<=right[j])
        {
            num[k]=right[j];
            j=j+1;
        }
        else
        {
            num[k]=left[i];
            i=i+1;
        }
        k++;
    }
    displaySequence(num);
}
\$\endgroup\$
2
\$\begingroup\$

Always check the result of scanf()

This code optimistically assumes that numeric inputs are successfully parsed. We need to check that the result of scanf() (the number of conversions successfully parsed and assigned) matches our expectations before using any of the values.

Don't use assert() for testing input validity

When reading user input, if we wish to check that we have more than 0 tests and more than 0 entries in each test, then assert() is the wrong tool. Remember that it can be disabled by defining NDEBUG, and it commonly is, for optimized builds.

Consider also using unsigned types for values that can't be negative.

Always check the result of memory allocation

Allocation functions such as calloc() can always fail. Again, assert() is not a robust means to check these.

Unexpected output in the bagging area

It looks like these statements were accidentally left in after a debugging session, and should be removed:

printf("Mid->%d\n", mid);
printf("N1->%d\nN2->%d\n", n1,n2);

No need to compute mid-point at end of recursion

Here, we only need mid if start<end:

void mergeSort(int*num,int start,int end)
{
    int mid;
    mid=start+((end-start)/2);
    if(start<end)
    {
        mergeSort(num,start,mid);
        mergeSort(num,(mid+1),end);
        mergeSequence(num,start,mid,end);
    }
}

We can re-write it as

void mergeSort(int *num, int start, int end)
{
    if (start < end) {
        const int mid = start + (end-start)/2;
        mergeSort(num, start, mid);
        mergeSort(num, mid+1, end);
        mergeSequence(num, start, mid, end);
    }
    /* else, start==end, and no work to do */
}
\$\endgroup\$
  • \$\begingroup\$ Concerning "Don't use assert() for testing input validity". How do you use assert()? \$\endgroup\$ – chux - Reinstate Monica Oct 29 '18 at 22:23
  • \$\begingroup\$ @chux Assertions are for enforcing facts that must be true according to the program logic. They are not meant for validating constraints on user input that you hope to be true. \$\endgroup\$ – 200_success Oct 30 '18 at 3:17
  • \$\begingroup\$ Still wondering of an example of how you use assert(). \$\endgroup\$ – chux - Reinstate Monica Oct 30 '18 at 3:27
  • \$\begingroup\$ You don't use assert() at all for tests on user input or other external conditions; you use a definite test that won't be compiled out. Use assert() only to document things that cannot be false unless there's a program bug. \$\endgroup\$ – Toby Speight Oct 30 '18 at 8:30
  • \$\begingroup\$ Trivial example: if (a < 100) return; double b = sqrt(a); assert (b >= 10); Obviously, it takes more complex code for the assertion to be useful. \$\endgroup\$ – Toby Speight Oct 30 '18 at 8:32
2
\$\begingroup\$

make the code more compact and secure

Separate sort code from test code

To well address security issues, OP needs to present a clear distinction between what is the sort code and what is not. Put all sort code in a separate .c file.

int vs. size_t

C employs size_t as the type that is neither to narrow nor too wide for array indexing and sizing.

Although int is commonly sufficient, to make more secure and work with large data, use size_t.

Aside from changing int --> size_t and "%d" --> "%zu", a singular challenge is to remember size_t is some unsigned type and code needs to consider that. (size_t)x < 0 is never true.

Beware large VLAs

Security risk: int left[n1]; is subject to stack overflow. Consider *alloc() instead. Insufficient memory can be detected that way.

Avoid exposing helper functions

mergeSequence() is not meant to be used outside of mergesort(). To prevent other code from using this functions, make it static. Further, put it and mergesort() in their own .c file.

This increases security as mergeSequence() then not need to handle all sorts of arguments, just the ones mergesort() generates.

All warnings enabled?

Save time, enable all warnings.

I'd expect mergeSort(num,0,(n-1)); (upper case S) to warn about function usage before declaration.

void mergesort(int*,int,int); (lower case S) is declared but not used.

Avoid generic names when a specific type is required

mergeSort() sorts int. With a name like mergeSort, I expected something like qsort() with its size-of-element parameter and compare function.

Of re-architect your merge sort code to take a generic object type.

void SS_mergeSort(void *base, size_t nmemb, size_t size, 
    int (*compar)(const void *, const void *));`

Compact by eliminating print out

It is unexpected that a sort routine would do any printing. Remove printf() and displaySequence() from merge...() functions.

Compact left,right code

int left[n1]; int right[n2]; can be int left_right[n1+n2]; and then the copying facilitated with the fast lib function memcpy().

memcpy(left_right, num, sizeof left_right);
int *left = left_right;
int *right = left_right + n1;
...
\$\endgroup\$
  • \$\begingroup\$ Are there platforms where overflowing program stack is a security bug? On most platforms, it's trapped and merely results in program termination. \$\endgroup\$ – Toby Speight Oct 30 '18 at 8:36
  • \$\begingroup\$ @TobySpeight Any form of exception is a crack in security. Most platforms in 2018 are embedded processors (billions per year) and which may terminate the program - only to restart it. \$\endgroup\$ – chux - Reinstate Monica Oct 31 '18 at 13:09
  • \$\begingroup\$ Stack overflow usually results in a signal, rather than an exception, but that aside, if terminating the program is a security risk, then that speaks more to whatever's running it that the program itself. I still agree that it's something worth avoiding, of course, but disagree on the motivation. \$\endgroup\$ – Toby Speight Oct 31 '18 at 13:15
  • \$\begingroup\$ Actually, it seems that the question uses the term "security" to refer to what I'd call robustness - i.e. functional correctness in the face of difficult (or even hostile) input, rather than what I'd call security - resistant to attempts to perform unauthorised actions. \$\endgroup\$ – Toby Speight Oct 31 '18 at 13:18
  • \$\begingroup\$ @TobySpeight A crack in "functional correctness in the face of difficult (or even hostile) input" is often a first step to defeating "resistant to attempts to perform unauthorised actions". \$\endgroup\$ – chux - Reinstate Monica Oct 31 '18 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.