In a conversation with Marshall Clow on the CppCast #300 ABI Stability podcast, we touched on the long-standing news of Visual Studio compiler support for AddressSanitizer (ASan). We've been implementing ASan in our testing system for some time now and want to share a couple of interesting bugs it helped us find.
The translation of the text translation of CppCast 300 is here .
AddressSanitizer is a dynamic analysis module from LLVM's compiler-rt. It's designed to catch memory errors such as out-of-bounds memory violations, use-after-frees, and double or incorrect memory frees. For obvious reasons, we primarily write about static analysis on the PVS-Studio blog, but the usefulness of dynamic analysis for program correctness shouldn't be ignored.
First, I'd like to say a few words about how we test the C++ analyzer. It goes through several stages of testing on the build server during the nightly run:
The developers also run the first four points locally on their machines.
We've been using dynamic analysis on the Linux platform for over five years. It was first added when we ported the analyzer to Linux. As the saying goes, you can never have too many tests. So we decided to try dynamic analysis on Windows as well, as the project code in our test databases varies significantly across different operating systems. The analyzer code also varies slightly across different systems.
There are no such things until proven otherwise. Just kidding. As doctors say, "There are no healthy people, only under-tested ones." It's the same with software development. Today, the tools you use cheerfully report that everything is fine. And tomorrow, you'll try something new or update an old one and wonder, "How did your code ever work?" Unfortunately, we're no exception, but that's the way it is, and that's okay.
More seriously, both dynamic and static code analysis have their strengths and weaknesses. There's no point in trying to choose just one over the other. Static and dynamic code analysis complement each other perfectly. As you can see, we use both static and dynamic analysis for our PVS-Studio code checks. And now we'll demonstrate the benefits of diversity in practice.
Before moving on to ASan itself, let's note one useful setting, which is actually a dynamic analysis mechanism and is already readily available (especially since without it, an ASan project won't build in Debug mode). These are the checks built into the compiler's standard library implementation. By default, MSVC's debug mode includes the following macros: _HAS_ITERATOR_DEBUGGING=1, _ITERATOR_DEBUG_LEVEL=2, and _SECURE_SCL=1, which activate runtime checks for improper handling of iterators and other standard library classes. These checks can catch a large number of trivial, inattentive errors.
However, multiple checks can be very disruptive, significantly slowing down the debugging process. Therefore, developers usually keep them disabled and enable them at night on the test server. Well, that's how it was on paper. In reality, at some point, this setting disappeared from the test run script on the Windows server... Consequently, when configuring the project for the sanitizer, a slew of accumulated surprises surfaced:
For example, those messages in MessageBoxes arose due to incorrect initialization of a variable of type std:
ptional :
If the StringToIntegral function fails to parse the number controlling the enabled diagnostic groups, it returns std::nullopt. The group must then be retrieved by converting the literal code. However, an extra asterisk was included in the reset expression for the groupIndicator value , resulting in undefined behavior due to an accessor call on an uninitialized std:ptional (analogous to a null pointer dereference).
Another problem with std:ptional was found in the incorrect logic for handling "virtual values" of array sizes:
Here, the virtual values obtained by combining the code execution paths are merged. In our terminology, a "virtual value" is a range of values that the variable's value will fall within at the corresponding point in the program. If the values on both execution paths can be determined (both values do not contain std::nullopt ), the Union method should be called . If the value on one of the execution paths is unknown, it should be set to the known value from the other path. However, the original algorithm wasn't designed for unknown values on both execution paths—the Union method will still be called for them , as if both values were known. This causes a problem similar to the previous example. The corrected code should do nothing when both values are unknown:
if (other.m_arraySizeInterval && m_arraySizeInterval)
{
res.m_arraySizeInterval = m_arraySizeInterval
->Union(*other.m_arraySizeInterval);
res.m_elementSize = m_elementSize;
}
else if (!other.m_arraySizeInterval && m_arraySizeInterval)
{
res.m_intervalSizeIsNotPrecise = false;
res.m_arraySizeInterval = m_arraySizeInterval;
res.m_elementSize = m_elementSize;
}
else if (!m_arraySizeInterval && other.m_arraySizeInterval)
{
res.m_intervalSizeIsNotPrecise = false;
res.m_arraySizeInterval = other.m_arraySizeInterval;
res.m_elementSize = other.m_elementSize;
}
The following failed test shows an example of the consequences of refactoring:
The str variable was once a simple pointer to a character array (naturally terminated by a null terminal), after which it was replaced by std::string_view , which does not include the null terminal. However, not all uses of this variable were converted to the methods of this class. In this code, the algorithm that processes the string's contents continues searching for its end, expecting a null terminal. There is no actual error (aside from an extra, useless iteration), since the null terminal exists in memory. But there is no guarantee that this will always be the case, so we limit the loop using the size method :
for (size_t i = 1; i < str.size(); ++i)
{
bool isUp = VivaCore::isUpperAlpha(name[i + pos]);
allOtherIsUpper &= isUp;
oneOtherIsUpper |= isUp;
}
Another example of a line break looks like incorrect behavior. It was found in diagnostic V624 , which checks the accuracy of certain constants and suggests replacing them with more accurate equivalents from the standard library:
From the sampleStr string, we obtain the character at index checkLen , which should be a digit from a numeric literal. However, in this case, the index points to the null terminal. The index is obtained as follows:
const size_t maxDigits = 19;
size_t n; // Numbers after dot to check
switch (literalType)
{
case ST_FLOAT:
n = 6;
break;
case ST_DOUBLE:
n = 14;
break;
default:
n = maxDigits;
}
const size_t checkLen = min(n, testStr.length()); // <=
size_t dist = GetEditDistance(testStr.substr(0, checkLen),
sampleStr.substr(0, checkLen));
The checkLen value is set based on the floating-point constant type and the length of the string containing the constant's reference entry. This does not take into account the length of the numeric literal of the constant being checked. As a result, the diagnostic may not work correctly on short numbers. Corrected code:
const size_t checkLen = min(n, min(sampleStr.size() - 1, testStr.size()));
The last error found in the standard library checks was diagnostic V1069 , which looks for a concatenation of different types of string literal pieces.
The compareWithPattern lambda compares the prefixes of string literal fragments using std::equal . The comparison is performed backwards (as required!), using reversed iterators. The problem is that the std::equal algorithm overload used compares the inclusion of elements of one container in another element-by-element, without checking the lengths of both containers in advance. It simply iterates until it hits the end iterator of the first container. If the first container is longer than the second (in this case, the substring "u8" in the prefix "u" was searched for), then the bounds of the second container are exceeded. To ensure that the bounds of both containers are not exceeded, you can use the correct overload, which checks the end iterators of both containers. But std::equal returns true even if the containers have different lengths and their elements are the same. Therefore, you need to use std::mismatch and check both resulting iterators:
StringLiteralType GetPattern(const SubstringView& element)
{
auto rElementItBegin = element.RBeginAsString();
auto rElementItEnd = element.REndAsString();
.... // 'rElementItBegin' modification
const auto compareWithPattern =
[&rElementItBegin, &rElementItEnd](const auto &el)
{
const auto &pattern = el.second;
auto [first, second] = std::mismatch(pattern.rbegin(), pattern.rend(),
rElementItBegin, rElementItEnd);
return first == pattern.rend() || second == rElementItEnd;
};
const auto type = std::find_if(Patterns.begin(), Patterns.end(),
compareWithPattern);
return type != Patterns.end() ? type->first : StringLiteralType::UNKNOWN;
}
This is where the errors detected by the asserters ended.
All previous tests were run with ASan enabled, but it didn't show any warnings. Oddly, the standard library checks didn't show any warnings when running on Linux.
To enable sanitizer in your project, you first need to install the corresponding component in Visual Studio.
In addition to the fact that standard library checks must be enabled in the Debug configuration (they are not needed in the Release configuration), the compilation flag /fsanitize=address must be added to the project properties.
Enabling it via a CMake script is also quite simple, you just need to remove the conflicting /RTC flags from the compiler:
if (PVS_STUDIO_ASAN)
if (MSVC)
add_compile_options(/fsanitize=address)
string(REGEX REPLACE "/RTC(su|[1su])" ""
CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG}")
endif ()
endif ()
Since the minor tests have already been fixed, it's time for the "heavy artillery." We build the kernel in Release mode with the sanitizer enabled and run SelfTester.
Okay, so the testing took 10 times longer than testing a regular kernel, and one project even timed out after 5 hours (it hadn't encountered any issues when run separately). You can't squeeze that into an overnight run, no matter how hard you try, but it's like, "Obviously, it's doing something!" As a result, two common errors were found across 6 different files.
ASan crashes the program when it detects an error, and before doing so, it prints the call stack so you can see where the error occurred:
In this case, a buffer overrun occurred somewhere in the V808 diagnostic , which warns that an object was created and then not used. We started kernel debugging with ASan enabled, passing the .cfg file where the crash occurred, and waited. Seeing this bug was quite unexpected.
The V808 diagnostic has an exception: it doesn't trigger on symbols passed to the __noop(....) function of the MSVC compiler. Processing this operation as a full function call was deemed a thankless task, so when parsing the source code, a leaf node of the tree (roughly speaking, std::string_view ) is simply formed from it. Within the V808 diagnostic, its contents have to be parsed separately. Due to an error within the parser, the algorithm that forms a leaf node for __noop incorrectly determined the end of the construct, thereby capturing excess code. Because this __noop was close to the end of the file, an ASan out-of-bounds error occurred when constructing a string from a pointer and the leaf length. A great catch! And, naturally, after fixing the parser, the analyzer began to show some additional warnings on code located after __noop s (we only found one such case in our test database).
The last error found using dynamic analysis was related to the use of freed memory:
One of the techniques we use to analyze programs is data-flow analysis.
During expression analysis, the data flow analyzer allocates special storage— Pools —to store virtual values. When a different context needs to be switched to evaluate a subexpression or another execution block, the previous Pool is saved and a new active Pool is created . Accordingly, when the current context is finished processing, its Pool is deallocated and the previous context is restored.
pair<optional<IntegerVirtualValue>, optional<IntegerVirtualValue>>
PreciseListVirtualValue::SizeFromCondition(
BinaryOperator op,
const IntegerVirtualValue& value,
const IntegerInterval &sizeInterval) const
{
Pool pool{};
pair<optional<IntegerVirtualValue>, optional<IntegerVirtualValue>> res;
auto length = GetLengthVirtual()
.value_or(IntegerVirtualValue(sizeInterval, false));
....
auto getResForCond = [](const VirtualValueOpt& value)
-> std:ptional<IntegerVirtualValue>
{
if (!value)
{
return nullopt;
}
if (const IntegerVirtualValue *val = get_if<IntegerVirtualValue>(&*value))
{
return *val; // <=
}
return nullopt;
};
....
switch (op)
{
case .... :
// for example
res.first = getResForCond(length.Intersection(pool, value));
res.second = getResForCond(length.Complement(pool, value));
....
}
return { res.first, res.second };
}
A wrapper around references to virtual values is created in the getResForCond lambda . They are then processed depending on the operation type in the switch statement. When the SizeFromCondition function exits , the wrapper is returned, but the references within it continue to hold on to the values in the pool deleted via RAII . To fix the code, you need to return copies of the objects, not references. In this case, it was fortunate that the cause of the error and its effect were close together; otherwise, it would have been a long and painful debug.
Dynamic analysis is a very powerful tool. Its main advantage is the fundamental absence of false positives. For example, if ASan shows a buffer overrun, that's what actually happened during execution with the given input data. Barring the butterfly effect (when a problem occurs early in program execution and manifests itself much later), debugging will provide sufficient information about what happened and where to fix the error.
Unfortunately, this also works the other way around. If a program allows for an error but successfully navigates the edge, no warning will occur. This means dynamic analysis is unable to identify potential errors. For some programs, it's possible to write tests that check for all edge cases, but for PVS-Studio, this means building a codebase that contains every possible program written in C++.
The translation of the text translation of CppCast 300 is here .
AddressSanitizer is a dynamic analysis module from LLVM's compiler-rt. It's designed to catch memory errors such as out-of-bounds memory violations, use-after-frees, and double or incorrect memory frees. For obvious reasons, we primarily write about static analysis on the PVS-Studio blog, but the usefulness of dynamic analysis for program correctness shouldn't be ignored.
Introduction
First, I'd like to say a few words about how we test the C++ analyzer. It goes through several stages of testing on the build server during the nightly run:
- Checking the buildability of the kernel (pvs-studio) and the pvs-studio-analyzer and plog-converter utilities using different compilers (MSVC, GCC, Clang) in various configurations (Debug, Release) for Windows, Linux, and macOS platforms.
- Running unit and integration tests to validate both test code fragments and utility usage scenarios. Written using the GoogleTest framework.
- C++ analyzer performance monitoring for open source projects on all supported platforms. We commonly call this program SelfTester. It runs the analyzer on a project and compares the results with benchmark results.
- Static "introspection" of a project using PVS-Studio. Incidentally, this is one of the most frequently asked questions we receive in articles and at conferences.
- Dynamic analysis running on unit and integration tests.
The developers also run the first four points locally on their machines.
We've been using dynamic analysis on the Linux platform for over five years. It was first added when we ported the analyzer to Linux. As the saying goes, you can never have too many tests. So we decided to try dynamic analysis on Windows as well, as the project code in our test databases varies significantly across different operating systems. The analyzer code also varies slightly across different systems.
Are there any bugs in PVS-Studio?
There are no such things until proven otherwise. Just kidding. As doctors say, "There are no healthy people, only under-tested ones." It's the same with software development. Today, the tools you use cheerfully report that everything is fine. And tomorrow, you'll try something new or update an old one and wonder, "How did your code ever work?" Unfortunately, we're no exception, but that's the way it is, and that's okay.
More seriously, both dynamic and static code analysis have their strengths and weaknesses. There's no point in trying to choose just one over the other. Static and dynamic code analysis complement each other perfectly. As you can see, we use both static and dynamic analysis for our PVS-Studio code checks. And now we'll demonstrate the benefits of diversity in practice.
Debugging tools from the standard library
Before moving on to ASan itself, let's note one useful setting, which is actually a dynamic analysis mechanism and is already readily available (especially since without it, an ASan project won't build in Debug mode). These are the checks built into the compiler's standard library implementation. By default, MSVC's debug mode includes the following macros: _HAS_ITERATOR_DEBUGGING=1, _ITERATOR_DEBUG_LEVEL=2, and _SECURE_SCL=1, which activate runtime checks for improper handling of iterators and other standard library classes. These checks can catch a large number of trivial, inattentive errors.
However, multiple checks can be very disruptive, significantly slowing down the debugging process. Therefore, developers usually keep them disabled and enable them at night on the test server. Well, that's how it was on paper. In reality, at some point, this setting disappeared from the test run script on the Windows server... Consequently, when configuring the project for the sanitizer, a slew of accumulated surprises surfaced:
For example, those messages in MessageBoxes arose due to incorrect initialization of a variable of type std:
ptional :
If the StringToIntegral function fails to parse the number controlling the enabled diagnostic groups, it returns std::nullopt. The group must then be retrieved by converting the literal code. However, an extra asterisk was included in the reset expression for the groupIndicator value , resulting in undefined behavior due to an accessor call on an uninitialized std:
ptional (analogous to a null pointer dereference).
Another problem with std:
ptional was found in the incorrect logic for handling "virtual values" of array sizes:
Here, the virtual values obtained by combining the code execution paths are merged. In our terminology, a "virtual value" is a range of values that the variable's value will fall within at the corresponding point in the program. If the values on both execution paths can be determined (both values do not contain std::nullopt ), the Union method should be called . If the value on one of the execution paths is unknown, it should be set to the known value from the other path. However, the original algorithm wasn't designed for unknown values on both execution paths—the Union method will still be called for them , as if both values were known. This causes a problem similar to the previous example. The corrected code should do nothing when both values are unknown:
if (other.m_arraySizeInterval && m_arraySizeInterval)
{
res.m_arraySizeInterval = m_arraySizeInterval
->Union(*other.m_arraySizeInterval);
res.m_elementSize = m_elementSize;
}
else if (!other.m_arraySizeInterval && m_arraySizeInterval)
{
res.m_intervalSizeIsNotPrecise = false;
res.m_arraySizeInterval = m_arraySizeInterval;
res.m_elementSize = m_elementSize;
}
else if (!m_arraySizeInterval && other.m_arraySizeInterval)
{
res.m_intervalSizeIsNotPrecise = false;
res.m_arraySizeInterval = other.m_arraySizeInterval;
res.m_elementSize = other.m_elementSize;
}
The following failed test shows an example of the consequences of refactoring:
The str variable was once a simple pointer to a character array (naturally terminated by a null terminal), after which it was replaced by std::string_view , which does not include the null terminal. However, not all uses of this variable were converted to the methods of this class. In this code, the algorithm that processes the string's contents continues searching for its end, expecting a null terminal. There is no actual error (aside from an extra, useless iteration), since the null terminal exists in memory. But there is no guarantee that this will always be the case, so we limit the loop using the size method :
for (size_t i = 1; i < str.size(); ++i)
{
bool isUp = VivaCore::isUpperAlpha(name[i + pos]);
allOtherIsUpper &= isUp;
oneOtherIsUpper |= isUp;
}
Another example of a line break looks like incorrect behavior. It was found in diagnostic V624 , which checks the accuracy of certain constants and suggests replacing them with more accurate equivalents from the standard library:
From the sampleStr string, we obtain the character at index checkLen , which should be a digit from a numeric literal. However, in this case, the index points to the null terminal. The index is obtained as follows:
const size_t maxDigits = 19;
size_t n; // Numbers after dot to check
switch (literalType)
{
case ST_FLOAT:
n = 6;
break;
case ST_DOUBLE:
n = 14;
break;
default:
n = maxDigits;
}
const size_t checkLen = min(n, testStr.length()); // <=
size_t dist = GetEditDistance(testStr.substr(0, checkLen),
sampleStr.substr(0, checkLen));
The checkLen value is set based on the floating-point constant type and the length of the string containing the constant's reference entry. This does not take into account the length of the numeric literal of the constant being checked. As a result, the diagnostic may not work correctly on short numbers. Corrected code:
const size_t checkLen = min(n, min(sampleStr.size() - 1, testStr.size()));
The last error found in the standard library checks was diagnostic V1069 , which looks for a concatenation of different types of string literal pieces.
The compareWithPattern lambda compares the prefixes of string literal fragments using std::equal . The comparison is performed backwards (as required!), using reversed iterators. The problem is that the std::equal algorithm overload used compares the inclusion of elements of one container in another element-by-element, without checking the lengths of both containers in advance. It simply iterates until it hits the end iterator of the first container. If the first container is longer than the second (in this case, the substring "u8" in the prefix "u" was searched for), then the bounds of the second container are exceeded. To ensure that the bounds of both containers are not exceeded, you can use the correct overload, which checks the end iterators of both containers. But std::equal returns true even if the containers have different lengths and their elements are the same. Therefore, you need to use std::mismatch and check both resulting iterators:
StringLiteralType GetPattern(const SubstringView& element)
{
auto rElementItBegin = element.RBeginAsString();
auto rElementItEnd = element.REndAsString();
.... // 'rElementItBegin' modification
const auto compareWithPattern =
[&rElementItBegin, &rElementItEnd](const auto &el)
{
const auto &pattern = el.second;
auto [first, second] = std::mismatch(pattern.rbegin(), pattern.rend(),
rElementItBegin, rElementItEnd);
return first == pattern.rend() || second == rElementItEnd;
};
const auto type = std::find_if(Patterns.begin(), Patterns.end(),
compareWithPattern);
return type != Patterns.end() ? type->first : StringLiteralType::UNKNOWN;
}
This is where the errors detected by the asserters ended.
Where is ASan?
All previous tests were run with ASan enabled, but it didn't show any warnings. Oddly, the standard library checks didn't show any warnings when running on Linux.
To enable sanitizer in your project, you first need to install the corresponding component in Visual Studio.
In addition to the fact that standard library checks must be enabled in the Debug configuration (they are not needed in the Release configuration), the compilation flag /fsanitize=address must be added to the project properties.
Enabling it via a CMake script is also quite simple, you just need to remove the conflicting /RTC flags from the compiler:
if (PVS_STUDIO_ASAN)
if (MSVC)
add_compile_options(/fsanitize=address)
string(REGEX REPLACE "/RTC(su|[1su])" ""
CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG}")
endif ()
endif ()
Since the minor tests have already been fixed, it's time for the "heavy artillery." We build the kernel in Release mode with the sanitizer enabled and run SelfTester.
Okay, so the testing took 10 times longer than testing a regular kernel, and one project even timed out after 5 hours (it hadn't encountered any issues when run separately). You can't squeeze that into an overnight run, no matter how hard you try, but it's like, "Obviously, it's doing something!"
As a result, two common errors were found across 6 different files.ASan crashes the program when it detects an error, and before doing so, it prints the call stack so you can see where the error occurred:
In this case, a buffer overrun occurred somewhere in the V808 diagnostic , which warns that an object was created and then not used. We started kernel debugging with ASan enabled, passing the .cfg file where the crash occurred, and waited. Seeing this bug was quite unexpected.
The V808 diagnostic has an exception: it doesn't trigger on symbols passed to the __noop(....) function of the MSVC compiler. Processing this operation as a full function call was deemed a thankless task, so when parsing the source code, a leaf node of the tree (roughly speaking, std::string_view ) is simply formed from it. Within the V808 diagnostic, its contents have to be parsed separately. Due to an error within the parser, the algorithm that forms a leaf node for __noop incorrectly determined the end of the construct, thereby capturing excess code. Because this __noop was close to the end of the file, an ASan out-of-bounds error occurred when constructing a string from a pointer and the leaf length. A great catch! And, naturally, after fixing the parser, the analyzer began to show some additional warnings on code located after __noop s (we only found one such case in our test database).
The last error found using dynamic analysis was related to the use of freed memory:
One of the techniques we use to analyze programs is data-flow analysis.
During expression analysis, the data flow analyzer allocates special storage— Pools —to store virtual values. When a different context needs to be switched to evaluate a subexpression or another execution block, the previous Pool is saved and a new active Pool is created . Accordingly, when the current context is finished processing, its Pool is deallocated and the previous context is restored.
pair<optional<IntegerVirtualValue>, optional<IntegerVirtualValue>>
PreciseListVirtualValue::SizeFromCondition(
BinaryOperator op,
const IntegerVirtualValue& value,
const IntegerInterval &sizeInterval) const
{
Pool pool{};
pair<optional<IntegerVirtualValue>, optional<IntegerVirtualValue>> res;
auto length = GetLengthVirtual()
.value_or(IntegerVirtualValue(sizeInterval, false));
....
auto getResForCond = [](const VirtualValueOpt& value)
-> std:
ptional<IntegerVirtualValue>{
if (!value)
{
return nullopt;
}
if (const IntegerVirtualValue *val = get_if<IntegerVirtualValue>(&*value))
{
return *val; // <=
}
return nullopt;
};
....
switch (op)
{
case .... :
// for example
res.first = getResForCond(length.Intersection(pool, value));
res.second = getResForCond(length.Complement(pool, value));
....
}
return { res.first, res.second };
}
A wrapper around references to virtual values is created in the getResForCond lambda . They are then processed depending on the operation type in the switch statement. When the SizeFromCondition function exits , the wrapper is returned, but the references within it continue to hold on to the values in the pool deleted via RAII . To fix the code, you need to return copies of the objects, not references. In this case, it was fortunate that the cause of the error and its effect were close together; otherwise, it would have been a long and painful debug.
Conclusion
Dynamic analysis is a very powerful tool. Its main advantage is the fundamental absence of false positives. For example, if ASan shows a buffer overrun, that's what actually happened during execution with the given input data. Barring the butterfly effect (when a problem occurs early in program execution and manifests itself much later), debugging will provide sufficient information about what happened and where to fix the error.
Unfortunately, this also works the other way around. If a program allows for an error but successfully navigates the edge, no warning will occur. This means dynamic analysis is unable to identify potential errors. For some programs, it's possible to write tests that check for all edge cases, but for PVS-Studio, this means building a codebase that contains every possible program written in C++.
