Our website uses cookies to enhance your browsing experience.
No one disputes the value of static or dynamic code analysis. However, some developers see that value as rather abstract and stop at writing unit tests. I recently came across an example from the C world that nicely illustrates how unit tests can sometimes fail to catch even the most common types of errors.
I've already discussed the bug I'm about to show you in the article "A beautiful error in the implementation of the string concatenation function." I'll briefly recap it, and then we'll look at it from the perspective of early detection.
The LFortran project had the following function for concatenating two strings into a new buffer:
void _lfortran_strcat(char** s1, char** s2, char** dest)
{
int cntr = 0;
char trmn = '\0';
int s1_len = strlen(*s1);
int s2_len = strlen(*s2);
int trmn_size = strlen(&trmn);
char* dest_char = (char*)malloc(s1_len+s2_len+trmn_size);
for (int i = 0; i < s1_len; i++) {
dest_char[cntr] = (*s1)[i];
cntr++;
}
for (int i = 0; i < s2_len; i++) {
dest_char[cntr] = (*s2)[i];
cntr++;
}
dest_char[cntr] = trmn;
*dest = &(dest_char[0]);
}This is a classic error where the allocated buffer is one byte smaller than required. The terminal null isn't taken into account; or rather, it is, but its size is calculated incorrectly.
char trmn = '\0';
int trmn_size = strlen(&trmn);The trmn character here gets interpreted as an empty string, whose length is zero. As a result, the trmn_size variable, whose name suggests that it stores the size of the terminal null, always equals 0. So, the terminal null is written past the end of the allocated buffer.
This is how we can fix the code (by adding +1 when calculating the argument of the malloc function):
void _lfortran_strcat(char** s1, char** s2, char** dest)
{
if (s1 == NULL || *s1 == NULL ||
s2 == NULL || *s2 == NULL || dest == NULL)
{
// Some error handling appropriate for this project.
....
}
int s1_len = strlen(*s1);
int s2_len = strlen(*s2);
char* dest_char = (char*)malloc(s1_len + s2_len + 1);
if (dest_char == NULL)
{
// Some error handling appropriate for this project.
....
}
memcpy(dest_char, *s1, s1_len);
memcpy(dest_char + s1_len, *s2, s2_len);
dest_char[s1_len + s2_len] = '\0';
*dest = &(dest_char[0]);
}The error is simple and straightforward. Buffer overflows are a common issue in C programs. What else is there to discuss? The bug has been found; case closed.
What got me thinking was a reader's comment about how tricky this error can be because of the granularity of memory allocation.
The malloc function doesn't actually allocate exactly as much memory as requested. It obtains large blocks from the OS and splits them into smaller chunks, adding some metadata along the way. The exact block size depends on the implementation.
Even if we call malloc(1), the allocator may still return a pointer to a block that is, say, 32 bytes in size (minus the metadata fields, leaving 24 usable bytes). This helps maintain memory alignment, typically the 16-byte one, and simplifies memory management.
The returned pointer must be properly aligned. Since malloc doesn't know what types we'll store in the allocated memory, it has to account for the strictest alignment requirement that might arise. In reality, on x86-64, malloc allocates addresses that are multiples of 16. That's why the allocator always rounds the requested block size up to the next alignment boundary.
I described the process very roughly and simplified some details. The important point is that, in reality, the code we looked at usually allocates more memory than it actually needs. If the blocks are multiples of 16 bytes, writing the terminal null into the next block will happen only when the resulting string size is also a multiple of 16. In other words, the bug has a 1-in-16 chance of actually happening (or perhaps not 16, that's just one possible value).
Now, I'd like to mention undefined behavior. Technically, the code is incorrect because it accesses memory outside the array bounds. We can't reliably predict how it will work, how the bug will behave, etc.
However, undefined behavior can also mean that incorrect code happens to work as expected. In this case, the memory manager may allocate more memory than the code requests, making it appear as if everything is working correctly.
We can write unit tests like these:
void Test1()
{
char *a = "a";
char *b = "";
char *q;
_lfortran_strcat(&a, &b, &q);
int ok = strcmp(q, "a") == 0;
printf("%s+%s=%s %s\n", a, b, q, ok ? "ok" : "err");
free(q);
}
void Test2()
{
char *a = "12";
char *b = "345";
char *q;
_lfortran_strcat(&a, &b, &q);
int ok = strcmp(q, "12345") == 0;
printf("%s+%s=%s %s\n", a, b, q, ok ? "ok" : "err");
free(q);
}And still miss the issue. The tests pass successfully:
a+=a ok
12+345=12345 okTests with short strings won't reveal the problem. Some developers might not even think to try working with long strings. Why would they? At first glance, such tests don't seem to add much value. Those devs will probably create tests for edge cases, such as empty strings, but they aren't relevant to finding the bug we're discussing.
Even with long strings, the chance of spilling into the neighboring block is only 1 in N (where N might be 16, for example). They could concatenate two huge strings, each containing 111111 characters, and everything would still work fine because the resulting 222222-character string doesn't end on a 16-byte block boundary.
Don't get me wrong: I'm not criticizing unit tests. They're a great tool! However, some errors can easily hide from them, and this is exactly such a case.
The issue is that it's easy to miss where the code crosses the invisible boundary of an allocated memory block. The following test creates reasonably long strings, 37 characters each. Do you think this test will cause the program to crash or create another visible problem?
void Test3()
{
char *a = "123";
for (unsigned i = 1; i != 35; ++i)
{
char *b = (char *)malloc(i + 1);
memset(b, 'a', i);
b[i] = '\0';
char *q;
_lfortran_strcat(&a, &b, &q);
int ok = strlen(q) == 3 + i;
printf("%u %s %s\n", i, q, ok ? "ok" : "err");
free(b);
free(q);
}
}It's impossible to say whether it will or not because we're dealing with undefined behavior. In reality, I compiled it with gcc using the -O2 optimization level and didn't notice any visible symptoms of the error, even though the memory blocks should have been corrupted. Yet the tests still make everything look fine:
1 123a ok
2 123aa ok
3 123aaa ok
4 123aaaa ok
5 123aaaaa ok
6 123aaaaaa ok
7 123aaaaaaa ok
8 123aaaaaaaa ok
9 123aaaaaaaaa ok
10 123aaaaaaaaaa ok
11 123aaaaaaaaaaa ok
12 123aaaaaaaaaaaa ok
13 123aaaaaaaaaaaaa ok
14 123aaaaaaaaaaaaaa ok
15 123aaaaaaaaaaaaaaa ok
16 123aaaaaaaaaaaaaaaa ok
17 123aaaaaaaaaaaaaaaaa ok
18 123aaaaaaaaaaaaaaaaaa ok
19 123aaaaaaaaaaaaaaaaaaa ok
20 123aaaaaaaaaaaaaaaaaaaa ok
21 123aaaaaaaaaaaaaaaaaaaaa ok
22 123aaaaaaaaaaaaaaaaaaaaaa ok
23 123aaaaaaaaaaaaaaaaaaaaaaa ok
24 123aaaaaaaaaaaaaaaaaaaaaaaa ok
25 123aaaaaaaaaaaaaaaaaaaaaaaaa ok
26 123aaaaaaaaaaaaaaaaaaaaaaaaaa ok
27 123aaaaaaaaaaaaaaaaaaaaaaaaaaa ok
28 123aaaaaaaaaaaaaaaaaaaaaaaaaaaa ok
29 123aaaaaaaaaaaaaaaaaaaaaaaaaaaaa ok
30 123aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ok
31 123aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ok
32 123aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ok
33 123aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ok
34 123aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa okThe program will crash when i reaches 38 in the for (unsigned i = 1; i != 38; ++i) loop:
free(): invalid pointer
Program terminated with signal: SIGSEGVDon't look for any special meaning in the number 38; it's just how it turned out. The most interesting thing here is how long the error was hiding from unit tests!
Such an error can be detected immediately using static or dynamic analysis.
Picrute 1—Early error detection using dynamic analysis (AddressSanitizer) or static analysis (PVS-Studio).
PVS-Studio static analyzer immediately issues a warning about an anomaly in the code: V742 Function receives an address of a 'char' type variable instead of pointer to a buffer. Inspect the first argument.
Or you can use a dynamic analysis tool, such as AddressSanitizer (gcc key:fsanitize=address). The simplest test, Test1, will immediately expose the issue.
Unit tests and dynamic analysis work hand in hand. The sanitizer detects an issue while the unit test runs. Without the test, the error may not surface until much later.
Static and dynamic analysis complement unit tests and other bug-finding techniques well. There's no single best method or tool, though. Static and dynamic analyzers have their own limitations and complement each other. And unit tests can uncover logic errors that analyzers are unlikely to catch.
Use them all. Although it'll require some investment at first, it'll pay off over time by catching a large percentage of bugs at an early stage in the development process. The earlier you find a bug, the easier and cheaper it is to fix (the shift-left testing approach).
0
0
0
0