Invalid read on a vector with size initialized by a variable using assert()-CodePudding

The simple function I've written catches a segfault on the test asserts that return 0 (false).

#include <vector>
#include <cassert>
using namespace std;

// checks whether the elements of a vector are some permutation of range [1..vector.size()]
int isPermutation(vector<int> &&A)
{
    int res = 1;
    int vecSize = A.size();

    // vector to store elements already found in vector A
    vector<int> B(vecSize, 0);
    
    for (auto& it : A)
    {
        if (B[it - 1] != 0 || it > vecSize)
        {
            res = 0;
            break;
        } // element already exists in B or is outside the permutation range
        else
        {
            B[it - 1] = 1;
        } // register element
    }
    return res;
}

int main()
{
    assert(isPermutation({4, 1, 3, 2}) == 1);
    assert(isPermutation({4, 1, 3, 2}) != 0);
    assert(isPermutation({1, 3}) == 0);
    assert(isPermutation({2}) == 0);
    assert(isPermutation({1}) == 1);
    assert(isPermutation({1, 2}) == 1);
    assert(isPermutation({4, 1, 3}) == 0);
    assert(isPermutation({4, 1, 2, 3, 6, 5, 8, 7}) == 1);

    return 0;
}

Valgrind points to the operator new[] which is used to manipulate the vector inside the function.

Error 1/3 (same on lines 34 and 37):

==212== Invalid read of size 4
==212==    at 0x109306: isPermutation(std::vector<int, std::allocator<int> >&&) (main.cpp:16)
==212==    by 0x109598: main (main.cpp:33)
==212==  Address 0x4dade18 is 0 bytes after a block of size 8 alloc'd
==212==    at 0x483BE63: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==212==    by 0x10A6B7: __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (new_allocator.h:114)
==212==    by 0x10A5CB: std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (alloc_traits.h:443)
==212==    by 0x10A427: std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (stl_vector.h:343)
==212==    by 0x10A2C0: std::_Vector_base<int, std::allocator<int> >::_M_create_storage(unsigned long) (stl_vector.h:358)
==212==    by 0x109F6A: std::_Vector_base<int, std::allocator<int> >::_Vector_base(unsigned long, std::allocator<int> const&) (stl_vector.h:302)
==212==    by 0x109BF2: std::vector<int, std::allocator<int> >::vector(unsigned long, int const&, std::allocator<int> const&) (stl_vector.h:521)
==212==    by 0x10928B: isPermutation(std::vector<int, std::allocator<int> >&&) (main.cpp:12)
==212==    by 0x109598: main (main.cpp:33)

Asserts that return 1 do not face this problem. Initializing the vector B using some constant instead of vecSize also clears the errors. Any ideas?

CodePudding user response：

There is a bug in

if (B[it - 1] != 0 || it > vecSize)

If it is larger than the size of the vector you first try to access an invalid element which causes UB.

You should switch this to

if (it > vecSize || B[it - 1] != 0)

so that you are sure that you only evaluate B[...] when the index is valid. (In addition you may want to check that it > 0)