CODEWITHSUNDEEP
calgorithm
PointerTo
PointerTo

Reputation: 57

Leetcode 506:A Problem with heap-buffer-overflow in C

The link to the question:https://leetcode.com/problems/relative-ranks/;

This is my solution:Using a two-dimensional array nums[2][scoreSize]:nums[0][scoreSize] to record score[scoreSzie].nums[1][scoreSize] to record the index of every element in score[scoreSzie].Then QuickSort for nums[2][scoreSize].So the output is:the element in nums[0][scoreSize] arranges from big to small order,and nums[1][scoreSize] records corresponding index of the element in score[scoreSize].At last, using ret[nums[1][i]] to record the rank and return.Here is the code:

void quicksort(int left,int right,int row,int col,int nums[row][col]);
char **findRelativeRanks(int* score, int scoreSize, int* returnSize)
{
    char **ret=(char **)malloc(sizeof(char *)*scoreSize);
    *returnSize=scoreSize;
    int i;
    int nums[2][scoreSize];                               //to record score[scoreSzie] and index
    for(i=0;i<scoreSize;i++)
    {
        nums[0][i]=score[i];
    }
    for(i=0;i<scoreSize;i++)
    {
        nums[1][i]=i;
    }
    quicksort(0,scoreSize-1,2,scoreSize,nums);            //Quicksort for nums[2][scoreSize]
    for(i=0;i<scoreSize;i++)                              //record rank by ret[scoreSize]
    {
        if(i<3)
        {
            switch(i)
            {
                case 0:ret[nums[1][0]]=(char*)malloc(sizeof(char)*15);
                       strcpy(ret[nums[1][0]],"Gold Medal");
                        break;
                case 1:ret[nums[1][1]]=(char*)malloc(sizeof(char)*15);
                        strcpy(ret[nums[1][1]],"Sliver Medal");
                        break;
                case 2:ret[nums[1][2]]=(char*)malloc(sizeof(char)*15);
                        strcpy(ret[nums[1][2]],"Bronze Medal");
                        break;
                default:break;
            }
        }else
        {
            ret[nums[1][i]]=(char*)malloc(sizeof(char)*1);
            ret[nums[1][i]][0]='1'+i;
        }
    }
    return ret;
}
void quicksort(int left,int right,int row,int col,int nums[row][col])
{
    if(left<right)
    {
        int l=left,r=right;
        int pivot=nums[0][left];
        int temp=nums[1][left];
        while(l<r)
        {
            while(r>l&&nums[0][r]<=pivot) r--;
            if(r>l)
            {
                nums[1][l]=nums[1][r];
                nums[0][l++]=nums[0][r];
            }
            while(r>l&&nums[0][l]>pivot) l++;
            if(r>l)
            {
                nums[1][r]=nums[1][l];
                nums[0][r--]=nums[0][l];
            }
        }
        nums[0][l]=pivot;
        nums[1][l]=temp;
        quicksort(left,l-1,row,col,nums);
        quicksort(l+1,right,row,col,nums);
    }else
    {
        return;
    }
}

The error is

=================================================================
==42==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000072 at pc 0x564293732f0b bp 0x7fffde673830 sp 0x7fffde673820
READ of size 1 at 0x602000000072 thread T0
    #3 0x7fbdea9b60b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000072 is located 0 bytes to the right of 2-byte region [0x602000000070,0x602000000072)
allocated by thread T0 here:
    #0 0x7fbdeb5fbbc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #3 0x7fbdea9b60b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa 00 07 fa fa 00 07 fa fa 00 07 fa fa[02]fa
  0x0c047fff8010: fa fa 02 fa fa fa fd fa fa fa fd fd fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==42==ABORTING

As a new programmer,i try my best to figure out where the problem is,but i failed.I really need help.Thank you very much.

Upvotes: 0

Views: 284

Answers (1)

Rohan Kumar
Rohan Kumar

Reputation: 5872

As pointed out by people in comments, you should try to debug what's going on in your program by either using gdb or by adding some print statements. Also, if you're still not so comfortable with C, maybe it's good to read some book first.

I had a look at the problem and I don't think you need to implement your own version of QuickSort just for this problem. You can simply use C library's qsort method which is well tested and more reliable.

  1. I noticed, this section here which is handling (rank > 3) cases:
ret[nums[1][i]]=(char*)malloc(sizeof(char)*1);
ret[nums[1][i]][0]='1'+i;

You're allocating string array of size 1. Even if we consider ranks will be single digit only, this is wrong since even for a single digit string you need two characters: one for original string and one for \0.

If you carefully read problem constraints, you'll see that array size can be up to 10000. So maybe using sprintf would be better here:

rankStr = malloc(6 * sizeof(char));
sprintf(rankStr, "%d", rank + 1);
  1. I find your approach of using int nums[2][scoreSize] for storing both score and original index before sorting and then sorting a bit too complex. I would suggest creating a struct for pair like this:
typedef struct ValueToIndexPair {
    int value;
    int index;
} ValueToIndexPair;

You can easily use qsort providing a custom comparator function to compare with value:

int cmpfunc (const void * a, const void * b) {
   const ValueToIndexPair* i1 = (ValueToIndexPair*) a;
   const ValueToIndexPair* i2 = (ValueToIndexPair*) b; 

   return (i2->value - i1->value );
}

char **findRelativeRanks(int* score, int scoreSize, int* returnSize) {
  // ...
  qsort(scoreToIndexList, scoreSize, sizeof(ValueToIndexPair), cmpfunc);
}

With slightly cleaned up version of your code, I was able to get this solution accepted:

typedef struct ValueToIndexPair {
    int value;
    int index;
} ValueToIndexPair;

int cmpfunc (const void * a, const void * b) {
   const ValueToIndexPair* i1 = (ValueToIndexPair*) a;
   const ValueToIndexPair* i2 = (ValueToIndexPair*) b; 

   return (i2->value - i1->value );
}

char **findRelativeRanks(int* score, int scoreSize, int* returnSize) {
  char **ranks = malloc(scoreSize * sizeof(char*));
  *returnSize = scoreSize;
  ValueToIndexPair scoreToIndexList[scoreSize];  
  for (int i = 0; i < scoreSize; i++) {
      scoreToIndexList[i].value = score[i];
      scoreToIndexList[i].index = i;
  }

  qsort(scoreToIndexList, scoreSize, sizeof(ValueToIndexPair), cmpfunc);
  
  for (int i = 0; i < scoreSize; i++) {
      char *rankStr = createRankString(i);
      int currentScoreOrignalIndex = scoreToIndexList[i].index;
      ranks[currentScoreOrignalIndex] = rankStr;
  }

  return ranks;
}

char *createRankString(int rank) {
  char firstRankStr[12] = "Gold Medal";
  char secondRankStr[13] = "Silver Medal";
  char thirdRankStr[15] = "Bronze Medal";

  char *rankStr;
  if (rank == 0) {
      rankStr = malloc(12 * sizeof(char));
      strcpy(rankStr, firstRankStr);
  } else if (rank == 1) {
      rankStr = malloc(13 * sizeof(char));
      strcpy(rankStr, secondRankStr);
  } else if (rank == 2) {
      rankStr = malloc(15 * sizeof(char));
      strcpy(rankStr, thirdRankStr);
  } else {
      rankStr = malloc(6 * sizeof(char));
      sprintf(rankStr, "%d", rank + 1);
  }
  return rankStr;
}

Upvotes: 1

Related Questions