Kevin is a software architect for Nortel Networks and can be reached at kwsmith@ nortelnetworks.com.
Congratulations, you have just been handed several million lines of complex C++ code. This code might be an internally developed product, commercial C++ library, or some open-source code you downloaded from the Internet and are considering adding to your next product release. Although the software basically works, at least as demonstrated in your testing, you are concerned that there are a large number of latent defects lurking in the software. But how can you find them before the ship date? In this article, I describe three techniques that will let you quickly identify latent defects without extensive testing or simulation. Instead, these three techniques complement your normal testing efforts. I recently used these techniques to quickly identify and correct several thousand latent defects in a very complex software system containing several million lines of C++ code.
Latent Defects
What is a latent defect? It is a defect that exists in your software, but has not been discovered by your testing process. For example, in a very large software system, it is not possible to test all possible execution paths through the source code (you would need billions of test cases to cover every combination of conditional branches in a very large software system). Some of these untested execution paths may contain serious coding errors. The challenge is to find these latent defects before your customers find them. A large percentage of the defects I uncovered were in various error paths that had not received proper test coverage during previous test cycles. Obviously, correcting defects early in the design cycle will save time and money, so identifying as many defects as possible before your software is shipped in volume is critical. The latent defects that I identified in this exercise fell into eight broad categories.
- Pointer/array violations. Dereferencing null pointers, accessing array elements outside the dimensions of the array, or copying memory/strings into buffers that are too small.
- Uninitialized variables. Using a variable before it has been initialized with a value, or dereferencing a pointer after it has been deleted.
- Improper return values. Returning void from a nonvoid function, or returning a pointer to a variable with local scope.
- Memory leaks. Exiting a procedure (possibly through an error path) and failing to release memory that was allocated and stored in a local variable. This occurs frequently when a procedure has multiple exit points.
- Common C mistakes. Placing a ; after an if statement, using an = in an if statement (instead of ==), operator precedence errors, or case blocks missing breaks.
- Common C++ mistakes. Using delete when delete[] is required, calling a virtual function within an object's constructor, or not providing a copy constructor when one is needed.
- Size errors. Shifting a 16-bit integer by 24 bits, or initializing a 16-bit integer with a 32-bit value.
- Logic errors. Algorithms implemented incorrectly or incompletely.
Code Complexity Analysis
Traditional code inspections work well to identify latent defects. The principle difficulty here is that code inspecting millions of lines of code takes too much time. The obvious answer is to inspect the source files that contain the highest percentage of the defects since this will offer the greatest return on your time investment. If you are not familiar with the software or if the software is relatively new, identifying the most problematic source files can be difficult.
I began with a simple assumption: The more complex code gets, the more defects it will contain. I verified this assumption by comparing subsystem complexity with incoming defects over the past few years. The subsystem complexity was a much better predictor of the defect rate than subsystem size in lines of noncomment code. This analysis was easy to do using the statistical correlation coefficient functions in Excel 2000. So how is complexity measured for software?
We applied a series of well-known software engineering metrics to the source code and computed a complexity number for each source file. The complexity number for a given source file was calculated by summing the results of each software engineering metric on that file. I chose eight basic software engineering metrics that closely reflect my beliefs about complex code.
- Lines of code. The number of noncomment, nonblank lines of code in a source-code file. In general, files with thousands of lines are more complex than files with only a few hundred lines.
- Variable density. The ratio of operands to the number of lines of code with an extra emphasis on large module sizes. When a source module manipulates many variables (especially in a large source file), the code becomes very difficult to understand.
- Unique operands. The number of unique operands in a source-code file. For example, defining and using hundreds of variables in a file will increase that file's complexity.
- Maximum conditional span. The maximum number of control blocks located within a conditional branch in a source-code file. For example, functions with deeply nested if/else clauses are more difficult to understand than functions with only a few unnested conditional branches.
- Average conditional complexity. Arithmetic mean of the complexity computed for each conditional block in a source-code file. This metric measures how complex the nested blocks are within if/else expressions.
- Global variable references. The number of unique, externally defined global variables referenced by this file. Files that reference many global variables from other parts of the software are more complex than files that reference only a few global variables.
- Control statements. The number of control statements in a source-code file. As the number of control statements increases, the software becomes harder to understand.
- Average control comments. Arithmetic mean of all commented control structure blocks in a source-code file. This metric determines if a control statement contains some type of comment, hopefully explaining what the control block is doing.
We selected the top 5 percent of the most complex source files in the entire system for code inspection. We also selected source files where the complexity had increased by more than 25 percent since the last software release. The hand inspection took several weeks and yielded 1384 latent defects. Another approach, which I did not try, is to inspect the most complex subsystems rather than the most complex files that are spread across many subsystems. One of the reasons not to inspect a single subsystem (even the most complex subsystem) in its entirety is that you would inspect many low-risk files along with the high-risk files.
In general, computing these metrics for your source code is fairly simple. There are a number of tools that you can purchase that will automatically compute these (and many other) metrics on your source code. Many of these tools have reached a level of sophistication where they produce valuable metrics reports with very little configuration effort on your part. A list of some of these tools is available in Table 1.
I recommend tracking these metrics over each software release. When a source file's complexity increases by more than 25 percent in a few months, there is a very good chance that latent defects have been created in that module. Note that code can be added into a module without significantly altering that module's complexity metric, as long as the new code is simple. Architecturally, you should decide if a module's sudden complexity increase was appropriate for the development occurring during the release, or if the complexity was accidentally introduced into your software. Even if the increase in complexity is warranted, you should inspect the changes carefully for latent defects.
Compiler Warning Analysis
Compiling several million lines of code generated 67,124 warnings. Personally, I dislike code to generate any compiler warnings; however, not all programmers share my views and complain that many compiler warnings are not really defects. All the same, I was willing to bet that some of these 67,124 warnings reflected real defects. A few lines of Perl sorted the warnings by type, and I investigated the most suspicious ones carefully. After a few days of effort, I identified 158 defects. Some of these suspicious warnings reflected obvious defects, so how did the original developers miss them? One explanation is that with over 67,000 warnings, no one noticed when a few new (and serious) warnings were introduced into the software. This experience has further convinced me that code shouldn't produce any warnings, if only because those benign warnings can hide serious problems.
One caution is that some compilers can be configured to suppress certain warnings. Make sure your compilers are configured to display all warnings before starting this analysis. During my work, I discovered several subsystems with makefiles that disabled critical compiler warnings, including a warning about returning void from a nonvoid function. This subsystem appeared to work normally under most circumstances, but started failing in random ways after a compiler upgrade. Fixing compiler warnings before they cause problems will save you time in the long run.
Linker warnings are also worth investigating. When our C++ linker encountered global symbols with the same name, only the first symbol encountered was linked into the load, and a warning was generated for any subsequent symbol definitions. While investigating the linker logs, I discovered 435 warnings of this type in our software load. All of these warnings reflected either global variables or global functions with names that are not unique. Since we do not use C++ namespaces in this project, we rely on subsystem naming conventions to guarantee unique names for global symbols; unfortunately, naming conventions are not always followed, and these 435 symbol conflicts were serious errors in our software.
Static Code Analysis
Static source-code analysis tools explore your source code, hunting for bugs, somewhat like an automated code inspection. Lint is one of the oldest and most valuable static source-code analysis tools for C software. The principle difficulty here is that lint churns out volumes of output, and only a small subset of this output reflects real errors. To combat this verbosity, I purchased Flexelint from Gimpel software (http://www.gimpel.com/lintinfo.htm) because this version of lint can suppress specific warnings and operates well on C++ source code. After a few weeks of experimenting, I crafted a set of lint rules with an extremely good signal-to-noise ratio. Running lint in this fashion quickly yielded 1843 defects. The first lint configuration file (available electronically; see "Resource Center," page 5) presents a list of lint rules that are good at identifying real defects.
This configuration file is intended to help with manual code inspections by identifying common C++ coding errors, potential memory leaks, and common coding standards violations. The second lint configuration file (Listing One) is a subset of the previous file; this file checks for blatant and serious errors. The second lint configuration file should produce a clean run on any code that is submitted into the source-code repository. These configuration files do not use the full power of lint since some legitimate errors are suppressed in favor of producing a high signal-to-noise output. This technique works by asking lint to suppress all warnings, then only turning on the select few that you are scanning for.
I also recommend linting all third-party source code in your software (unless you are willing to trust your reputation to someone else's source code). There are a number of commercial products available that perform static analysis on C++ source code. A few good tools (such as Splint) work well on C source code and are available for free. Table 1 lists some common static analysis tools. Many of these tools enforce the C++ coding guidelines that Scott Meyers published in his Effective C++ series of books and CD-ROMs, as described in "Examining C++ Program Analyzers," (DDJ, February 1997).
Next Steps
Once you have gathered information about the subsystems in your software, keep note of which subsystems contained serious compiler warnings or a large number of severe lint errors. These metrics can point to potential problems in your overall software organization. For example, are your staffing and C++ training levels appropriate for the complexity and number of defects identified in each subsystem? On the other hand, maybe you'll decide to switch suppliers for your third-party software libraries!
Conclusion
These three techniques will identify latent defects in your software and can be implemented quickly at little expense. If you are really pressed for time and can only execute one of these three techniques, I recommend performing a selective static analysis (using a properly configured lint or equivalent) since it offers the biggest bang in the shortest time period. However, for a large software system, it is hard to argue why you wouldn't use all three of these techniques before every software release. Although these three defect identification techniques are not radically new, how confident are you that your software would not benefit from this targeted analysis? How many latent defects are lurking in your software?
DDJ
Listing One
// ------------------------------------------------------------------------
// This file contains specific lint checks that are MANDATORY before
// submitting software into the source code library system.
// ------------------------------------------------------------------------
// ------------------------------------------------------------------------
// Use warning level 1 and continue when an error is encountered
// ------------------------------------------------------------------------
-w1
+fce
// ------------------------------------------------------------------------
// These checks usually find errors...
// ------------------------------------------------------------------------
// non-void function not returning anything
+e533
// returning address of a local (stack) variable
+e604
// using delete when you should use delete[] or free when you want delete
+e424
// use of null pointers
+e413
// out-of-bounds pointers such as "int a[10]; a[10] = 0;"
+e415
+e416
// subtract a value from a pointer returned from malloc (or an auto array)
+e428
// boolean argument to relational, such as "if (a < b < c)"
+e503
// using = when you meant == such as "if (x = 10)"
+e720
// semi-colon after an if such as "if (x == y);"
+e548
// order of evaluation dependency such as "x = i + i++;"
+e564
// classic problems with "%" args in printf-style commands
+e417
+e557
+e558
+e560
+e561
+e566
+e567
+e622
+e627
// non-ANSI escape sequence such as "printf("\i");"
+e606
// constant out of range for operator such as "if (byte < 65537)"
+e650
// signed-unsigned mix with divide such as "x = uint / int;"
+e573
// passing a null pointer to function such as "strcpy(null, null);"
+e418
// data overrun for function such as "char x[1]; strcpy(x, "abc");"
+e419
// access beyond array for function
+e420
// passing a negative value to function such as "x = malloc(-1);"
+e422
// malloc size issues
+e432
+e433
// unused label (usually finds problems with case labels)
+e563
// ------------------------------------------------------------------------
// These checks reflect poor programming style with bad consequences
// ------------------------------------------------------------------------
// started a comment or struct but didn't finish it before end of file
+e404
+e405
+e406
// don't call virtual functions from within constructor or destructor
+e1506
// flag header files that aren't used by the module that includes them
+e766
// don't use gets() because it is dangerous (possible buffer overflows)
+e421
// #define re-defines something that was already #define'd
+e547
// created a #define with same name as a variable
+e652
// really long constant that doesn't fit into a long int
+e417
// mixing int and enum in a case statement
+e408
// ------------------------------------------------------------------------
// Exceptions
// ------------------------------------------------------------------------
// allow macro re-definitions from library headers like stdio.h.
-elib(652)
-elib(547)
// ------------------------------------------------------------------------
// Suppress all syntax errors from warning level 1
// ------------------------------------------------------------------------
-e1 -e2 -e3 -e4 -e5 -e6 -e7 -e8 -e9 -e10
-e11 -e12 -e13 -e14 -e15 -e16 -e17 -e18 -e19 -e20
-e21 -e22 -e23 -e24 -e25 -e26 -e27 -e28 -e29 -e30
-e31 -e32 -e33 -e34 -e35 -e36 -e37 -e38 -e39 -e40
-e41 -e42 -e43 -e44 -e45 -e46 -e47 -e48 -e49 -e50
-e51 -e52 -e53 -e54 -e55 -e56 -e57 -e58 -e59 -e60
-e61 -e62 -e63 -e64 -e65 -e66 -e67 -e68 -e69 -e70
-e71 -e72 -e73 -e74 -e75 -e76 -e77 -e78 -e79 -e80
-e81 -e82 -e83 -e84 -e85 -e86 -e87 -e88 -e89 -e90
-e91 -e92 -e93 -e94 -e95 -e96 -e97 -e98 -e99 -e100
-e101 -e102 -e103 -e104 -e105 -e106 -e107 -e108 -e109 -e110
-e111 -e112 -e113 -e114 -e115 -e116 -e117 -e118 -e119 -e120
-e121 -e122 -e123 -e124 -e125 -e126 -e127 -e128 -e129 -e130
-e131 -e132 -e133 -e134 -e135 -e136 -e137 -e138 -e139 -e140
-e141 -e142 -e143 -e144 -e145 -e146 -e147 -e148 -e149 -e150
-e151 -e152 -e153 -e154 -e155 -e156 -e157 -e158 -e159 -e160
-e161 -e162 -e163 -e164 -e165 -e166 -e167 -e168 -e169 -e170
-e171 -e172 -e173 -e174 -e175 -e176 -e177 -e178 -e179 -e180
-e181 -e182 -e183 -e184 -e185 -e186 -e187 -e188 -e189 -e190
-e191 -e192 -e193 -e194 -e195 -e196 -e197 -e198 -e199
-e1001 -e1002 -e1003 -e1004 -e1005 -e1006 -e1007 -e1008 -e1009 -e1010
-e1011 -e1012 -e1013 -e1014 -e1015 -e1016 -e1017 -e1018 -e1019 -e1020
-e1021 -e1022 -e1023 -e1024 -e1025 -e1026 -e1027 -e1028 -e1029 -e1030
-e1031 -e1032 -e1033 -e1034 -e1035 -e1036 -e1037 -e1038 -e1039 -e1040
-e1041 -e1042 -e1043 -e1044 -e1045 -e1046 -e1047 -e1048 -e1049 -e1050
-e1051 -e1052 -e1053 -e1054 -e1055 -e1056 -e1057 -e1058 -e1059 -e1060
-e1061 -e1062 -e1063 -e1064 -e1065 -e1066 -e1067 -e1068 -e1069 -e1070
-e1071 -e1072 -e1073 -e1074 -e1075 -e1076 -e1077 -e1078 -e1079 -e1080
-e1081 -e1082 -e1083 -e1084 -e1085 -e1086 -e1087 -e1088 -e1089 -e1090
-e1091 -e1092 -e1093 -e1094 -e1095 -e1096 -e1097 -e1098 -e1099 -e1100
-e1101 -e1102 -e1103 -e1104 -e1105 -e1106 -e1107 -e1108 -e1109 -e1110
-e1111 -e1112 -e1113 -e1114 -e1115 -e1116 -e1117 -e1118 -e1119 -e1120
-e1121 -e1122 -e1123 -e1124 -e1125 -e1126 -e1127 -e1128 -e1129 -e1130
-e1131 -e1132 -e1133 -e1134 -e1135 -e1136 -e1137 -e1138 -e1139 -e1140
-e1141 -e1142 -e1143 -e1144 -e1145 -e1146 -e1147 -e1148 -e1149 -e1150
-e1151 -e1152 -e1153 -e1154 -e1155 -e1156 -e1157 -e1158 -e1159 -e1160
-e1161 -e1162 -e1163 -e1164 -e1165 -e1166 -e1167 -e1168 -e1169 -e1170
-e1171 -e1172 -e1173 -e1174 -e1175 -e1176 -e1177 -e1178 -e1179 -e1180
-e1181 -e1182 -e1183 -e1184 -e1185 -e1186 -e1187 -e1188 -e1189 -e1190
-e1191 -e1192 -e1193 -e1194 -e1195 -e1196 -e1197 -e1198
