CODEWITHSUNDEEP
c++dictionaryruntime-error
mecdeality
mecdeality

Reputation: 455

AddressSanitizer: heap-buffer-overflow on address

Im trying to write a function to determine if the input string is valid.

This task is from leetcode, 20th task. So its given like that.

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
*Open brackets must be closed by the same type of brackets.
*Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

My code: 

bool isValid(string s) {
        vector<char> str;
        map<char, char> mp;
        mp['{']='}';
        mp['(']=')';
        mp['[']=']';
        for(int i = 0; i < s.length(); i++){
            str.push_back(s[i]);
        }int c = 0;
        while(!str.empty()){
            c++;
            for(int i = 0; i < str.size(); i++){
                if(str[i+1]==mp[i]){
                    int x = i+1;
                    str.erase(str.begin()+x);
                    str.erase(str.begin()+i);
                    }
            }if(c>str.size()) break;
        }
        if(str.empty()) return true;
        else return false;
    }

But every time I get this error:

=================================================================
==32==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000032 at pc 0x00000038767f bp 0x7ffffae90390 sp 0x7ffffae90388
READ of size 1 at 0x602000000032 thread T0
    #2 0x7fd5e106882f  (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
0x602000000032 is located 0 bytes to the right of 2-byte region [0x602000000030,0x602000000032)
allocated by thread T0 here:
    #4 0x7fd5e106882f  (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
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 fd fa fa fa[02]fa fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa 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
==32==ABORTING


Can you explain, whats wrong here, does my solution correct or not?

Upvotes: 2

Views: 8105

Answers (1)

molbdnilo
molbdnilo

Reputation: 66459

Comparing to mp[i] does not make any sense.

Since mp does not initially contain 0,1,2,3,... but three brackets, mp[i] will be zero until your index happens to be the encoding of one of the opening bracket characters (the first one is very likely 40, '(' in ASCII).

What will happen if you don't have that many characters is that you reach the last iteration, when i == size() - 1.
Then accessing str[i+1] has undefined behaviour and anything can happen.

There is no simple way to repair your program because your approach is flawed to begin with, so I would recommend that you delete all of that and start over.
(At a minimum, you need a way to keep track of all the opening brackets you've encountered so far. Major hint: read about std::stack)

Upvotes: 1

Related Questions