Out-of-bounds debugging lab

Why this matters

An array is a row of boxes that each hold one value. Each box has a number called its index. The first box has index 0. A row with 5 boxes has indexes 0, 1, 2, 3 and 4. A program that asks for index 5 is asking for a box that does not exist. This is called going out of bounds, and it is one of the most common bugs in C++ programs.

The bug is hard to catch for two reasons. In C++, the language does not stop you when you do it on most plain array and vector reads. The program may crash, print a wrong number, or print a right-looking number by luck. The C++ standard calls this undefined behaviour. It means the language makes no promise about what happens. The compiler is allowed to assume your program never does it, so the result can be anything.

This lesson is a lab. You will meet three broken programs, read the messages they print, find the index that goes too far, and fix it. You will also see the tools that show you the exact line. The array basics are in the lessons on arrays and vectors. The fixed-size and variable-size sliding window lessons use the same index arithmetic, so the habits you learn here carry over to them.

The idea: valid indexes run from 0 to size minus 1

Take five test scores:

index:   0    1    2    3    4
score:  70   85   90   60   75

The valid indexes are 0 through 4. The size() function of a vector returns the number of elements, which is 5 here. The last valid index is always size() - 1, which is 4.

So the rule is short:

• The first valid index is 0.
• The last valid index is size() - 1.
• Any index less than 0, or equal to or greater than size(), is out of bounds.

Most out-of-bounds bugs come from one of three places. A loop condition uses <= where it should use <. A calculation subtracts 1 from an unsigned number that is already 0. A loop looks at a neighbour, such as the value before or after the current one, and does not handle the first or last position.

The next three sections show each of these with real output from a real compiler. The compiler used here is g++ 15 on Ubuntu, with the flags the course uses.

Worked example 1: the loop that goes one too far

Here is a short program that adds up five scores. It has a bug in the loop condition.

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> scores = {70, 85, 90, 60, 75};
    int total = 0;
    for (size_t i = 0; i <= scores.size(); ++i) {
        total += scores[i];
    }
    cout << "total " << total << "\n";
}

The loop should stop before index 5. The condition i <= scores.size() lets i reach 5, which is one past the last valid index. Compile it and run it:

g++ -std=c++20 -Wall -o scores scores.cpp && ./scores

On the Ubuntu g++ 15 install used to test this lesson, the program stops with this message and exit code 134:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The part that matters is Assertion '__n < this->size()' failed. The C++ library checks the index inside [] and found that the index is not less than the size. The name __n is the library's name for the index. The long text before it names the file and the function where the check sits, which is inside the C++ library and not in your code. The message does not say which line of your program caused it.

This check is not part of the C++ standard. It is turned on by default in this Ubuntu install of g++ 15. Other compilers and other installs may not check. On those, the same program reads memory past the end of the vector and keeps going.

Both outcomes are the same bug. You should treat any run that prints an assertion or a crash as a bug in your code, not as a problem with the compiler.

Using at() to get a clear error

A vector also has an at() function. It does the same job as [] but checks the index every time and throws an exception when the index is wrong. An exception is an error that the program can catch and handle, or let stop the program. Here is the same loop using at(), with a try block that catches the error:

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;
 
int main() {
    vector<int> scores = {70, 85, 90, 60, 75};
    int total = 0;
    try {
        for (size_t i = 0; i <= scores.size(); ++i) {
            total += scores.at(i);
        }
    } catch (const out_of_range& e) {
        cout << "caught: " << e.what() << "\n";
    }
    cout << "total so far " << total << "\n";
}

Run it:

caught: vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)
total so far 380

The message says the index was 5 and the size was 5. The total is 380, which is 70 + 85 + 90 + 60 + 75. The loop reached index 5 and threw before it added anything extra. The try block stopped the loop, so the total is the sum of the five real scores.

at() costs a little speed because it checks every time. Many programs use [] in hot loops and check the bounds themselves. For learning and for debugging, at() is the safer choice, because a wrong index gives an error you can read.

The trap: the wrong answer that looks right

Now remove the check and read the memory directly with data(), which returns the raw pointer to the first element of the vector. This skips the library check on [], so you can see the plain behaviour.

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> scores = {70, 85, 90, 60, 75};
    int total = 0;
    for (size_t i = 0; i <= scores.size(); ++i) {
        total += scores.data()[i];
    }
    cout << "total " << total << "\n";
}

g++ -std=c++20 -Wall -o scores_raw scores_raw.cpp && ./scores_raw

total 380

The program prints a plausible total, exits with code 0, and shows no error. The read at index 5 went to the memory just after the five numbers. In this run that memory held 0, so adding it changed nothing. Another compiler, another run, or a different machine could read a different value there. The total would then be wrong, and nothing in the output would say so.

This is the trap. A program with an out-of-bounds read can produce the right answer and still be broken. The check is never "the output looks right." The check is "the tool reports no error."

Using a sanitizer to find the line

A sanitizer is a tool built into g++ and clang++ that checks the program while it runs. The one that matters here is AddressSanitizer, usually called ASan. It watches every memory access and reports the first bad one, with the line number of your code. Turn it on with -fsanitize=address and add -g, which keeps the line numbers in the program.

g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o scores_raw_asan scores_raw.cpp && ./scores_raw_asan

The first lines of the report look like this. The rest is a long list of the memory allocation and the call stack, and the first lines are the part to read. This report is from scores_raw.cpp, and line 10 is the total += scores.data()[i]; line shown above. The process number and addresses differ on each run:

=================================================================
==152470==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6e33c93e0054 at pc 0x6424d22aa680 bp 0x7ffd61799320 sp 0x7ffd61799310
READ of size 4 at 0x6e33c93e0054 thread T0
    #0 0x6424d22aa67f in main scores_raw.cpp:10
...
0x6e33c93e0054 is located 0 bytes after 20-byte region [0x6e33c93e0040,0x6e33c93e0054)

Three parts of this report answer the question.

• heap-buffer-overflow says the bad read was in memory that was allocated on the heap, which is where a vector keeps its elements. The 20-byte region is five int values, each 4 bytes.
• READ of size 4 says the program read 4 bytes, one int.
• #0 ... bug1_data.cpp:10 gives the file and line of the bad read.

The line located 0 bytes after 20-byte region also tells you the index. The read was just past the end of the region, so it was index 5.

The same kind of report appears for a plain C array, which is the older kind of array with a fixed size written as int marks[5]. Here is a loop that reads one index too far:

#include <iostream>
 
int main() {
    int marks[5] = {70, 85, 90, 60, 75};
    int total = 0;
    for (int i = 0; i <= 5; ++i) {
        total += marks[i];
    }
    std::cout << "total " << total << "\n";
}

g++ -std=c++20 -Wall -g -fsanitize=address -o marks_asan marks.cpp && ./marks_asan

The report now says the bad read was on the stack, which is the memory the function uses for its local variables. The file is marks.cpp, and its line 7 is the total += marks[i]; line:

=================================================================
==152525==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x77825d1f0034 at pc 0x5b99bd5c5497 bp 0x7fff463e4810 sp 0x7fff463e4800
READ of size 4 at 0x77825d1f0034 thread T0
    #0 0x5b99bd5c5496 in main marks.cpp:7
...
    [32, 52) 'marks' (line 4) <== Memory access at offset 52 overflows this variable

The last line names the variable. marks is 20 bytes, and the read was at offset 52 from the start of the frame, which is past the end of it.

Plain builds without a sanitizer ran the C array loop too. In the test run it printed total 380 with exit code 0, the same silent result as before.

Worked example 2: a subtraction that wraps around

The second common bug is a subtraction that goes below zero. In C++, the type size_t is an unsigned integer. It cannot hold a negative number. When you subtract past zero, the value wraps around to a very large number instead. On a 64-bit machine, 0 - 1 becomes 18446744073709551615.

Here is a program that prints this:

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> temps = {18, 21, 19, 24};
    size_t day = 0;
    cout << "day " << day << " minus one = " << day - 1 << "\n";
    cout << "size of temps = " << temps.size() << "\n";
    cout << "day - 1 < size? " << boolalpha << (day - 1 < temps.size()) << "\n";
}

g++ -std=c++20 -Wall -o wrap wrap.cpp && ./wrap

day 0 minus one = 18446744073709551615
size of temps = 4
day - 1 < size? false

The value day - 1 is not -1. It is a huge positive number, so the check day - 1 < temps.size() is false. If you write temps[day - 1] without this check, the program reads far outside the vector.

This bug shows up in loops that count backwards or look at the value before the current one. Here is the typical case: the first day has no previous day, so the code asks for day - 1. Test the first position with an if before the subtraction, or use a signed type such as int for the index and check it against 0.

The safest habit for a loop that looks back is to write the condition so that the subtraction never happens when the result would be negative. The lab in the next section shows this.

Worked example 3: the lab

This is the lab itself. The program below is meant to smooth a list of meter readings. Each new value is the average of the reading, the reading before it, and the reading after it. The first and last readings have only one neighbour, so the code needs to handle them.

The code has a bug. Read it first and try to find it before you run it.

#include <iostream>
#include <vector>
using namespace std;
 
// Average each reading with its left and right neighbour.
vector<int> smooth(const vector<int>& readings) {
    vector<int> out(readings.size());
    for (int i = 0; i < static_cast<int>(readings.size()); ++i) {
        int left = readings[i - 1];
        int right = readings[i + 1];
        out[i] = (left + readings[i] + right) / 3;
    }
    return out;
}
 
int main() {
    vector<int> readings = {10, 20, 30, 40, 50};
    for (int v : smooth(readings)) {
        cout << v << " ";
    }
    cout << "\n";
}

Save the program as lab_bug.cpp, then compile and run it:

g++ -std=c++20 -Wall -g -o lab_bug lab_bug.cpp && ./lab_bug

On this machine the program stops with the same library assertion as before:

/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The assertion does not show the line number of your code, so it is not enough on its own. Here are the steps to find the bug.

Step 1: find the index

The message says an index was not less than the size. It does not say which index. To get that, replace the raw [] reads with a small checked function. The function prints the index, the valid range and the line of the caller. It uses std::source_location, a C++20 feature that records where a function was called.

#include <cstdlib>
#include <iostream>
#include <source_location>
#include <vector>
using namespace std;
 
int checked(const vector<int>& v, long long i, source_location where = source_location::current()) {
    if (i < 0 || i >= static_cast<long long>(v.size())) {
        cerr << where.file_name() << ":" << where.line() << ": index " << i
             << " is outside 0 to " << static_cast<long long>(v.size()) - 1 << "\n";
        exit(1);
    }
    return v[static_cast<size_t>(i)];
}
 
vector<int> smooth(const vector<int>& readings) {
    vector<int> out(readings.size());
    for (long long i = 0; i < static_cast<long long>(readings.size()); ++i) {
        int left = checked(readings, i - 1);
        int right = checked(readings, i + 1);
        out[i] = (left + checked(readings, i) + right) / 3;
    }
    return out;
}
 
int main() {
    vector<int> readings = {10, 20, 30, 40, 50};
    for (int v : smooth(readings)) {
        cout << v << " ";
    }
    cout << "\n";
}

g++ -std=c++20 -Wall -g -o lab_helper lab_helper.cpp && ./lab_helper

lab_helper.cpp:19: index -1 is outside 0 to 4

Now the message is clear. Line 19 is the call checked(readings, i - 1), and the index was -1. The valid range is 0 to 4. The helper does not change the values, so the program returns the same answer for any input that passes the check.

The helper is a debugging tool. Once the bug is fixed, you can remove it, or keep it only in test builds.

Step 2: find out why

The index was -1 at the first position, where i is 0. The loop starts at 0 and calls readings[i - 1], so it reads one box before the start. The same thing happens at the end. When i is 4, the code reads readings[5], which is past the last box.

The loop runs over every position, so both ends break. The code needs a rule for the first and last readings. The simplest rule is to treat a missing neighbour as the reading itself. So the first reading uses itself as its left neighbour, and the last reading uses itself as its right neighbour.

Step 3: check the ASan line on the raw code

The sanitizer gives the same information for the raw code, if you read the data through data() so that the library check does not stop the program first. This is the variant of the lab that the sanitizer can report on:

sed 's/readings\[i - 1\]/readings.data()[i - 1]/; s/readings\[i + 1\]/readings.data()[i + 1]/' lab_bug.cpp > lab_data.cpp && g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o lab_data_asan lab_data.cpp && ./lab_data_asan

=================================================================
==153137==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6c6d7efe003c at pc 0x5a20c22d06e8 bp 0x7ffedccffd10 sp 0x7ffedccffd00
READ of size 4 at 0x6c6d7efe003c thread T0
    #0 0x5a20c22d06e7 in smooth(std::vector<int, std::allocator<int> > const&) /home/chiranjeet/dev/anisha/scratch-offtmp/arrays-lessons-writer/lab/lab_data.cpp:9
    #1 0x5a20c22d0bb8 in main /home/chiranjeet/dev/anisha/scratch-offtmp/arrays-lessons-writer/lab/lab_data.cpp:18
...
0x6c6d7efe003c is located 4 bytes before 20-byte region [0x6c6d7efe0040,0x6c6d7efe0054)

The report points to line 9, which is the readings[i - 1] read, in the function smooth. located 4 bytes before means the read was one int before the start of the array, so the index was -1.

Step 4: fix it

The fix handles the ends with a conditional. A conditional is an expression with ? and : that picks one of two values. Here i > 0 ? i - 1 : 0 means "use i - 1 if i is greater than 0, otherwise use 0." The subtraction only happens when it is safe.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> smooth(const vector<int>& readings) {
    vector<int> out(readings.size());
    int last = static_cast<int>(readings.size()) - 1;
    for (int i = 0; i <= last; ++i) {
        int left = readings[i > 0 ? i - 1 : 0];
        int right = readings[i < last ? i + 1 : last];
        out[i] = (left + readings[i] + right) / 3;
    }
    return out;
}
 
int main() {
    vector<int> readings = {10, 20, 30, 40, 50};
    for (int v : smooth(readings)) {
        cout << v << " ";
    }
    cout << "\n";
}

g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o lab_fixed lab_fixed.cpp && ./lab_fixed

13 20 30 40 46

Check the numbers by hand. The first reading uses 10, 10 and 20, so the average is 40 / 3, which is 13 with integer division. The middle readings are plain averages, so 10, 20, 30 gives 20. The last reading uses 40, 50 and 50, so the average is 140 / 3, which is 46. The sanitizer ran with no report, so the program has no bad read.

Note that the loop now uses i <= last, with last set to the last valid index. This is the same rule as the first example: the valid range ends at size() - 1.

Common mistakes

Using <= where you mean <. The loop for (size_t i = 0; i <= v.size(); ++i) reads index v.size(), which is one past the end. Write i < v.size(). The loop body should never reach v.size() itself.

Subtracting from size() on an empty vector. For an empty vector, v.size() - 1 is 18446744073709551615, not -1. A loop such as for (size_t i = 0; i < v.size() - 1; ++i) then runs, and reads v[0] from a vector with no elements. Write i + 1 < v.size() instead, which never subtracts.

Assuming the program will crash. The [] version stopped with an assertion, and the data() version printed 380 and exited with code 0. Undefined behaviour does not promise a crash. If a program reads past the end and you do not see a message, that does not mean the read was safe.

Trusting a correct-looking output. The total 380 run was correct by luck. Check bounds with at(), or run the program under -fsanitize=address,undefined, before you trust the output.

Expecting -Wall to catch it. None of the programs in this lesson produced a warning under -Wall, even the ones with the bug. The compiler does not check the indexes in loops. Use the sanitizer and at() to find these bugs.

Mixing a signed index with size_t. An int index that is -1 converts to a very large size_t when it is passed to []. So an index of -1 becomes 18446744073709551615. Keep the index in one type, or use long long as the lab does, and check the range before you read.

Practice

1. The loop below sums the four values in v. The program stops with an exception. Which index is the first bad one, and what does the message say?

vector<int> v = {4, 8, 15, 16};
int total = 0;
for (size_t i = 1; i <= v.size(); ++i) {
    total += v.at(i);
}

Show the answer

The first bad index is 4, because v.size() is 4 and the last valid index is 3. The loop reaches i equal to 4 and at(4) throws std::out_of_range. Run as a full program with no try block, the output is terminate called after throwing an instance of 'std::out_of_range' followed by what(): vector::_M_range_check: __n (which is 4) >= this->size() (which is 4). The fix is i < v.size().

2. The loop below is meant to visit the values from last to first. Find the bug. Then write a loop that visits every index from v.size() - 1 down to 0 without going out of bounds.

for (size_t i = v.size() - 1; i >= 0; --i) {
    cout << v[i] << " ";
}

Show the answer

The condition i >= 0 is always true for an unsigned type, so the loop never ends by itself. When i is 0 and --i runs, i wraps to 18446744073709551615, and v[i] reads far outside the vector. One correct form is for (size_t i = v.size(); i-- > 0;) { cout << v[i] << " "; }. The i-- > 0 test compares the old value of i with 0, then subtracts one. It stops after index 0 without a subtraction that goes below zero. With v = {4, 8, 15, 16} this prints 16 15 8 4.

3. What does this program print on a 64-bit machine?

size_t n = 0;
cout << n - 1 << "\n";

Show the answer

It prints 18446744073709551615. The type size_t is unsigned, so 0 - 1 wraps to the largest value the type can hold, which is 2 to the power of 64 minus 1 on a 64-bit machine. This is not an error, and no warning is printed, but any index computed this way is out of bounds.

4. A program has vector<int> v; with no elements, then runs for (size_t i = 0; i < v.size() - 1; ++i) { total += v[i]; }. Does the loop body run? Write a loop that does the same job without the bad subtraction.

Show the answer

Yes. For an empty vector, v.size() - 1 wraps to 18446744073709551615, so 0 < 18446744073709551615 is true and the body runs with i equal to 0. The read v[0] is out of bounds. A loop with no subtraction is for (size_t i = 0; i + 1 < v.size(); ++i). For an empty vector the condition is 1 < 0, which is false, so the body never runs. For a single-element vector such as {7} the condition is 1 < 1, which is false, so nothing is added. That matches the loop's intent, which adds every value except the last.

5. The program in the trap section prints total 380 with exit code 0, using scores.data()[i] with i <= scores.size(). A classmate says the program is correct because the answer is right. Is the classmate right? Say what you would run to check.

Show the answer

No. The read at index 5 is undefined behaviour. The value 0 that was read at that index is a coincidence of this run. To check, compile with g++ -std=c++20 -Wall -g -fsanitize=address,undefined and run the program. AddressSanitizer reports a heap-buffer-overflow at the line of the bad read. Fix the loop to use i < scores.size(), run it again, and confirm the sanitizer reports nothing.

Summary

• The valid indexes of an array or vector run from 0 to size() - 1.
• Using [] with a bad index is undefined behaviour. The program may crash, print a wrong value, or print a correct value by luck.
• at() checks the index and throws an exception that names the index and the size.
• AddressSanitizer, turned on with -fsanitize=address -g, reports the file and line of the first bad read.
• An unsigned subtraction below zero wraps to a huge number, so a check such as i - 1 >= 0 is always true for size_t.
• A checked helper that prints the index and the caller's line makes a bad index easy to find.