Webinar: C++ semantics - 06.11
Hi! Though the 2019 conference season is not over yet, we'd like to talk about the bug-finding challenges we offered to visitors at our booth during the past conferences. Starting with the fall of 2019, we've been bringing a new set of challenges, so we can now reveal the solutions to the previous tasks of 2018 and the first half of 2019 – after all, many of them came from previously posted articles, and we had a link or QR code with information about the respective articles printed on our challenge leaflets.
If you attended events where we participated with a booth, you probably saw or even tried to solve some of our challenges. These are snippets of code from real open-source projects written in C, C++, C#, or Java. Each snippet contains a bug, and the guests are challenged to try to find it. A successful solution (or simply participation in the discussion of the bug) is rewarded with a prize: a spiral-bound desktop status, a keychain, and the like:
Want some too? Then welcome to drop by our booth at the upcoming events.
By the way, in the articles "Conference Time! Summing up 2018" and "Conferences. Sub-totals for the first half of 2019", we share our experience of participating in the events held earlier this year and in 2018.
Okay, let's play our "Find the bug" game. First we'll take a look at the earlier challenges of 2018, grouped by language.
Chromium bug
static const int kDaysInMonth[13] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
bool ValidateDateTime(const DateTime& time) {
if (time.year < 1 || time.year > 9999 ||
time.month < 1 || time.month > 12 ||
time.day < 1 || time.day > 31 ||
time.hour < 0 || time.hour > 23 ||
time.minute < 0 || time.minute > 59 ||
time.second < 0 || time.second > 59) {
return false;
}
if (time.month == 2 && IsLeapYear(time.year)) {
return time.month <= kDaysInMonth[time.month] + 1;
} else {
return time.month <= kDaysInMonth[time.month];
}
}
[Solution]
This bug found in Chromium was probably the most "long-running" challenge; we were offering it all the way through 2018 and included it in several presentations as well.
if (time.month == 2 && IsLeapYear(time.year)) {
return time.month <= kDaysInMonth[time.month] + 1; // <= day
} else {
return time.month <= kDaysInMonth[time.month]; // <= day
}
The body of the last If-else block contains typos in the return statements: time.month was accidentally written for a second time instead of time.day. This mistake makes the function return true all the time. The bug is discussed in detail in the article "February 31" and is a cool example of a bug that isn't easily spotted by code review. This case is also a good demonstration of how we use dataflow analysis.
Unreal Engine bug
bool VertInfluencedByActiveBone(
FParticleEmitterInstance* Owner,
USkeletalMeshComponent* InSkelMeshComponent,
int32 InVertexIndex,
int32* OutBoneIndex = NULL);
void UParticleModuleLocationSkelVertSurface::Spawn(....)
{
....
int32 BoneIndex1, BoneIndex2, BoneIndex3;
BoneIndex1 = BoneIndex2 = BoneIndex3 = INDEX_NONE;
if(!VertInfluencedByActiveBone(
Owner, SourceComponent, VertIndex[0], &BoneIndex1) &&
!VertInfluencedByActiveBone(
Owner, SourceComponent, VertIndex[1], &BoneIndex2) &&
!VertInfluencedByActiveBone(
Owner, SourceComponent, VertIndex[2]) &BoneIndex3)
{
....
}
[Solution]
The first thing to notice here is that the last argument of the VertInfluencedByActiveBone() function has a default value and is not required to be specified. Now look at the if block in a simplified form:
if (!foo(....) && !foo(....) && !foo(....) & arg)
The bug is now clearly visible. Because of the typo, the third call of the VertInfluencedByActiveBone() function is performed with three arguments instead of four, with the return value then participating in a & operation (bitwise AND: the left operand is the value of type bool returned by VertInfluencedByActiveBone(), and the right operand is the integer variable BoneIndex3). The code is still compilable. This is the fixed version (a comma added, the closing parenthesis moved to the end of the expression):
if(!VertInfluencedByActiveBone(
Owner, SourceComponent, VertIndex[0], &BoneIndex1) &&
!VertInfluencedByActiveBone(
Owner, SourceComponent, VertIndex[1], &BoneIndex2) &&
!VertInfluencedByActiveBone(
Owner, SourceComponent, VertIndex[2], &BoneIndex3))
This error was originally mentioned in the article "A long-awaited check of Unreal Engine 4", where it was titled "the nicest error", which I totally agree with.
Android bugs
void TagMonitor::parseTagsToMonitor(String8 tagNames) {
std::lock_guard<std::mutex> lock(mMonitorMutex);
// Expand shorthands
if (ssize_t idx = tagNames.find("3a") != -1) {
ssize_t end = tagNames.find(",", idx);
char* start = tagNames.lockBuffer(tagNames.size());
start[idx] = '\0';
....
}
....
}
[Solution]
The programmer had wrong assumptions about the precedence of operations in the condition of the if block. This code doesn't work as expected:
if (ssize_t idx = (tagNames.find("3a") != -1))
The idx variable will be assigned the value 0 or 1, and whether the condition is true or false will depend on this value, which is a mistake. This is the fixed version:
ssize_t idx = tagNames.find("3a");
if (idx != -1)
This bug was mentioned in the article "We checked the Android source code by PVS-Studio, or nothing is perfect".
Here's another non-trivial challenge with an Android bug:
typedef int32_t GGLfixed;
GGLfixed gglFastDivx(GGLfixed n, GGLfixed d)
{
if ((d>>24) && ((d>>24)+1)) {
n >>= 8;
d >>= 8;
}
return gglMulx(n, gglRecip(d));
}
[Solution]
The problem is in the (d >> 24) + 1 expression.
The programmer wanted to check that the 8 most significant bits of the d variable are set to 1 but not all of them at a time. In other words, they wanted to check that the most significant byte stores any value except 0x00 and 0xFF. First the programmer checks the most significant bits for null using the (d>>24) expression. Then they shift the eight most significant bits to the least significant byte, expecting the most significant sign bit to get duplicated in all the other bits. That is, if the d variable has the value 0b11111111'00000000'00000000'00000000, it will turn into 0b11111111'11111111'11111111'11111111 after the shift. By adding 1 to the int value 0xFFFFFFFF, the programmer is expecting to get 0 (-1+1=0). Thus, the ((d>>24)+1) expression is used to check that not all of the eight most significant bits are set to 1.
However, the most significant sign bit does not necessarily get "spread" when shifted. This is what the standard says: "The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined".
So, this is an example of implementation-defined behavior. How exactly this code will work depends on the CPU architecture and compiler implementation. The most significant bits may well end up as zeroes after the shift, and the ((d>>24)+1) expression would then always return a value other than 0, i.e. an always true value.
That, indeed, is a non-trivial challenge. Like the previous bug, this one was originally discussed in the article "We checked the Android source code by PVS-Studio, or nothing is perfect".
"It's all GCC's fault"
int foo(const unsigned char *s)
{
int r = 0;
while(*s) {
r += ((r * 20891 + *s *200) | *s ^ 4 | *s ^ 3) ^ (r >> 1);
s++;
}
return r & 0x7fffffff;
}
The programmer blames the GCC 8 compiler for the bug. Is it really GCC's fault?
[Solution]
The function returns negative values since the compiler doesn't generate code for the bitwise AND (&). The bug has to do with undefined behavior. The compiler notices that the r variable is used to calculate and store a sum, with only positive values involved. The r variable shouldn't overflow because that would be undefined behavior, which the compiler is not bound to reckon with at all. So it concludes that since r can't have a negative value at the end of the loop, the operation r & 0x7fffffff, which clears the sign bit, is unnecessary, so it simply tells the function to return the value of r.
This error was described in the article "PVS-Studio 6.26 released".
QT bug
static inline const QMetaObjectPrivate *priv(const uint* data)
{ return reinterpret_cast<const QMetaObjectPrivate*>(data); }
bool QMetaEnum::isFlag() const
{
const int offset = priv(mobj->d.data)->revision >= 8 ? 2 : 1;
return mobj && mobj->d.data[handle + offset] & EnumIsFlag;
}
[Solution]
The mobj pointer is handled in an unsafe way: first dereferenced, then checked. A classic.
The bug was mentioned in the article "A third check of Qt 5 with PVS-Studio".
Infer.NET bug
public static void
WriteAttribute(TextWriter writer,
string name,
object defaultValue,
object value,
Func<object, string> converter = null)
{
if ( defaultValue == null && value == null
|| value.Equals(defaultValue))
{
return;
}
string stringValue = converter == null ? value.ToString() :
converter(value);
writer.Write($"{name}=\"{stringValue}\" ");
}
[Solution]
Null dereference of the value variable may occur when evaluating the value.Equals(defaultValue) expression. This will happen when the variables' values are such that defaultValue != null and value == null.
This bug is from the article "What errors lurk in Infer.NET code?"
FastReport bug
public class FastString
{
private const int initCapacity = 32;
private void Init(int iniCapacity)
{ sb = new StringBuilder(iniCapacity); .... }
public FastString() { Init(initCapacity); }
public FastString(int iniCapacity) { Init(initCapacity); }
public StringBuilder StringBuilder => sb;
}
....
Console.WriteLine(new FastString(256).StringBuilder.Capacity);
What will the program output in the console? What's wrong with the FastString class?
[Solution]
The program will output the value 32. The reason is the misspelled name of the variable passed to the Init method in the constructor:
public FastString(int iniCapacity){ Init(initCapacity); }
The constructor parameter iniCapacity won't be used; what gets passed instead is the constant initCapacity.
The bug was discussed in the article "The fastest reports in the Wild West - and a handful of bugs..."
Roslyn bug
private SyntaxNode GetNode(SyntaxNode root)
{
var current = root;
....
while (current.FullSpan.Contains(....))
{
....
var nodeOrToken = current.ChildThatContainsPosition(....);
....
current = nodeOrToken.AsNode();
}
....
}
public SyntaxNode AsNode()
{
if (_token != null)
{
return null;
}
return _nodeOrParent;
}
[Solution]
Potential null dereference of current in the current.FullSpan.Contains(....) expression. The current variable can be assigned a null value as a result of invoking the nodeOrToken.AsNode() method.
This bug is from the article "Checking the Roslyn source code".
Unity bug
....
staticFields = packedSnapshot.typeDescriptions
.Where(t =>
t.staticFieldBytes != null &
t.staticFieldBytes.Length > 0)
.Select(t => UnpackStaticFields(t))
.ToArray()
....
[Solution]
A typo: the & operator is used instead of &&. This results in executing the t.staticFieldBytes.Length > 0 check all the time, even if the t.staticFieldBytes variable is null, which, in its turn, leads to a null dereference.
This bug was originally shown in the article "Discussing errors in Unity3D's open-source components".
IntelliJ IDEA bug
private static boolean checkSentenceCapitalization(@NotNull String value) {
List<String> words = StringUtil.split(value, " ");
....
int capitalized = 1;
....
return capitalized / words.size() < 0.2; // allow reasonable amount of
// capitalized words
}
Why does the program incorrectly calculate the number of capitalized words?
[Solution]
The function is expected to return true if the number of capitalized words is less than 20%. But the check doesn't work because of the integer division, which evaluates only to 0 or 1. The function will return false only if all the words are capitalized. Otherwise, the division will result in 0 and the function will return true.
This bug is from the article "PVS-Studio for Java".
SpotBugs bug
public static String getXMLType(@WillNotClose InputStream in) throws IOException
{
....
String s;
int count = 0;
while (count < 4) {
s = r.readLine();
if (s == null) {
break;
}
Matcher m = tag.matcher(s);
if (m.find()) {
return m.group(1);
}
}
throw new IOException("Didn't find xml tag");
....
}
What's wrong with the search of the xml tag?
[Solution]
The count < 4 condition will be always true since the variable count is not incremented inside the loop. The xml tag was meant to be searched for in the first four lines of the file, but because of the lacking increment, the program will be reading the entire file.
Like the previous bug, this one was described in the article "PVS-Studio for Java".
That's all for today. Come see us at the upcoming events – look for the unicorn. We'll be offering new interesting challenges and, of course, giving prizes. See you!
0