Illegal Memory Access and Segmentation Fault

Introduction

In computer programming, when we use pointers for accessing memory without proper bounds checking, it can lead to illegal memory access. With the presence of illegal memory access, sometimes the computer program may encounter a segmentation fault, but sometimes it may not.

In this blog post, I would like to quickly discuss why illegal memory access sometimes may not cause a segmentation fault.

Illegal Memory Access and Segmentation Fault

Memory Access Boundary Checking

Frequent memory access boundary checking in software implementations can be expensive, especially in performance-critical applications. Without proper boundary checking, however, might result in undefined behavior if the program accesses memory outside the allocated bounds.

Sometimes, such undefined behavior results in a segmentation fault. This is because the operating system detects that the computer program is trying to access memory that it does not own, and will terminate program execution to prevent the program from corrupting the other software running. That’s why we could usually write buggy programs without damaging the operating system. Unlike the memory access boundary checking implemented in the software, the memory access boundary checking implemented in the operating system is more efficient and is accelerated by the hardware, such as the memory management unit (MMU) in the CPU.

How the operating system detects such illegal memory access is implementation-dependent. But the simplest way is to check the address of the memory access against the address range of the allocated memory for the computer program. If the address is outside the allocated memory range, then the operating system will terminate the program, resulting in a segmentation fault. However, if the address is within the allocated memory range, even if the address is intended to be out of bounds, the operating system will not terminate the program.

Example

The following C++ program demonstrates how illegal memory access can lead to a segmentation fault or not, depending on the offset used for accessing the out-of-bounds element.

oob.cpp

#include <vector>
#include <iostream>

void access_out_of_bounds_element(std::vector<int> const& v, size_t oob_offset)
{
    // Accessing out-of-bounds element
    std::cout << "Accessing Out-Of-Bounds Element At Index: "
              << v.size() - 1 + oob_offset << std::endl;
    // This line has higher chance of causing a segmentation fault if oob_offset is large.
    int out_of_bounds_element = v[v.size() - 1 + oob_offset];
}

int main()
{
    constexpr size_t vector_size{32U};
    std::vector<int> const v(vector_size, 0);

    std::cout << "Vector Size: " << v.size() << std::endl;
    access_out_of_bounds_element(v, 1);
    access_out_of_bounds_element(v, 10);
    access_out_of_bounds_element(v, 100);
    access_out_of_bounds_element(v, 1000);
    access_out_of_bounds_element(v, 10000);
    access_out_of_bounds_element(v, 100000);
}

On my computer, the output of the program is as follows.

$ g++ oob.cpp -o oob
$ ./oob
Vector Size: 32
Accessing Out-Of-Bounds Element At Index: 32
Accessing Out-Of-Bounds Element At Index: 41
Accessing Out-Of-Bounds Element At Index: 131
Accessing Out-Of-Bounds Element At Index: 1031
Accessing Out-Of-Bounds Element At Index: 10031
Accessing Out-Of-Bounds Element At Index: 100031
Segmentation fault (core dumped)

We could see when we tried to access the index of 32, 41, 131, 1031, and 10031 in the vector of size 32, the program did not crash with a segmentation fault. However, when we tried to access the index of 100031, the program crashed with a segmentation fault.

Using Valgrind, we could know the size of memory allocated for the computer program.

$ valgrind --tool=memcheck ./oob
==60== Memcheck, a memory error detector
==60== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==60== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==60== Command: ./oob
==60==
Vector Size: 32
Accessing Out-Of-Bounds Element At Index: 32
==60== Invalid read of size 4
==60==    at 0x108BD4: access_out_of_bounds_element(std::vector<int, std::allocator<int> > const&, unsigned long) (in /mnt/oob)
==60==    by 0x108C8B: main (in /mnt/oob)
==60==  Address 0x5b7fd00 is 0 bytes after a block of size 128 alloc'd
==60==    at 0x4C3217F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==60==    by 0x1092F1: __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (in /mnt/oob)
==60==    by 0x10925E: std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (in /mnt/oob)
==60==    by 0x1091AF: std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (in /mnt/oob)
==60==    by 0x10909C: std::_Vector_base<int, std::allocator<int> >::_M_create_storage(unsigned long) (in /mnt/oob)
==60==    by 0x108F3C: std::_Vector_base<int, std::allocator<int> >::_Vector_base(unsigned long, std::allocator<int> const&) (in /mnt/oob)
==60==    by 0x108E4F: std::vector<int, std::allocator<int> >::vector(unsigned long, int const&, std::allocator<int> const&) (in /mnt/oob)
==60==    by 0x108C2C: main (in /mnt/oob)
==60==
Accessing Out-Of-Bounds Element At Index: 41
==60== Invalid read of size 4
==60==    at 0x108BD4: access_out_of_bounds_element(std::vector<int, std::allocator<int> > const&, unsigned long) (in /mnt/oob)
==60==    by 0x108C9C: main (in /mnt/oob)
==60==  Address 0x5b7fd24 is 28 bytes before a block of size 1,024 in arena "client"
==60==
Accessing Out-Of-Bounds Element At Index: 131
Accessing Out-Of-Bounds Element At Index: 1031
==60== Invalid read of size 4
==60==    at 0x108BD4: access_out_of_bounds_element(std::vector<int, std::allocator<int> > const&, unsigned long) (in /mnt/oob)
==60==    by 0x108CBE: main (in /mnt/oob)
==60==  Address 0x5b80c9c is 2,844 bytes inside an unallocated block of size 4,120,160 in arena "client"
==60==
Accessing Out-Of-Bounds Element At Index: 10031
==60== Invalid read of size 4
==60==    at 0x108BD4: access_out_of_bounds_element(std::vector<int, std::allocator<int> > const&, unsigned long) (in /mnt/oob)
==60==    by 0x108CCF: main (in /mnt/oob)
==60==  Address 0x5b8993c is 38,844 bytes inside an unallocated block of size 4,120,160 in arena "client"
==60==
Accessing Out-Of-Bounds Element At Index: 100031
==60== Invalid read of size 4
==60==    at 0x108BD4: access_out_of_bounds_element(std::vector<int, std::allocator<int> > const&, unsigned long) (in /mnt/oob)
==60==    by 0x108CE0: main (in /mnt/oob)
==60==  Address 0x5be177c is 398,844 bytes inside an unallocated block of size 4,120,160 in arena "client"
==60==
==60==
==60== HEAP SUMMARY:
==60==     in use at exit: 0 bytes in 0 blocks
==60==   total heap usage: 3 allocs, 3 frees, 73,856 bytes allocated
==60==
==60== All heap blocks were freed -- no leaks are possible
==60==
==60== For counts of detected and suppressed errors, rerun with: -v
==60== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 0 from 0)

In our case, we have total heap usage: 3 allocs, 3 frees, 73,856 bytes allocated. So the memory allocated for the computer program is 73,856 bytes, which can be translated to a vector of 18,464 integers (assuming each integer is 4 bytes). Therefore, the out-of-bounds access at index 100031 is definitely outside the allocated memory range, which results in a segmentation fault, whereas the out-of-bounds access at index 32, 41, 131, 1031, and 10031 are still within the allocated memory range by chance, which does not result in a segmentation fault.

Interestingly, Valgrind detects the out-of-bounds access not only at index 100031 but also all the other out-of-bounds accesses at index 32, 41, 131, 1031, and 10031. This is because Valgrind runs a virtual memory manager that keeps track of all memory allocations and deallocations, allowing it to detect illegal memory accesses more easily. In our case, Valgrind knows that the vector v corresponds to a block of size 128 allocated bytes. When Valgrind sees an instruction corresponding to v[32], it knows this is an out-of-bounds access by checking the allocated block size of v. We might try some trick to fool Valgrind, such as float const* ptr{&v[31]}; ptr[1]; which is equivalent as v[32]. But it will not work, because Valgrind tracks the provenance of pointers, not just their final memory address. That is also to say, Valgrind will translate float const* ptr{&v[31]}; ptr[1]; to v[32] and know this is an out-of-bounds access.

In short, the operating system books keeping the memory addresses at the program level, while Valgrind books keeping the memory addresses at the more fine-grained object level. Therefore, Valgrind can detect the out-of-bounds access more accurately.

Conclusions

The illegal memory access may not always result in a segmentation fault from the operating system, depending on whether the illegal access is still within the allocated memory for the computer program. If the illegal memory access is outside the allocated memory range, it will result in a segmentation fault and the developer will be alarmed. However, if the illegal memory access is still within the allocated memory range, it will not result in a segmentation fault but the computer program behavior becomes undefined, which can be hard to debug.