With the software size growth, it becomes more important to have some helping tools, which can aid the software development. There are two kinds of tools: static checking tools analyze the syntax of source code and discover errors at compiling time; dynamic checking tools use test cases to run programs and detect runtime errors and invariants.

The paper "The use of Program Dependence Graphs in Software Engineering" describes a language-independent program representation – the program dependence graph – and discusses how program dependence graphs can form the basis for powerful programming tools. Horwitz and Reps use program slicing to understand what an existing program does and how it works. Differencing is used to understand the differences between several versions of a program. Program integration is a way to create new programs by combining pieces of old programs.

All of the methods talked above are based on the program dependence graphs. Program dependence graph is used to present single procedure program, system dependence graph is used to present programs with multiple procedures and functions. Program dependence graph presents control and data dependence graph among program points (statements). The algorithm can efficiently compute the slicing, differencing and integration problems. It is based on a simple restricted language.

Since the dependence graph is statement-based, it is not very helpful for large-scale programs. For instance, one single statement may have a very large backward slicing set. By simply looking at the backward slicing, it doesn’t help locate the bug. Usually debugging the program is easier to find the error.

I don’t see the big advantage of integration method in the paper either. The integration method can automatically merge two different versions to one program, which is a good thing. But it doesn’t have much more power than existing commercial text-based merge utilities, such as SourceSafe or ClearCase.

This paper, Dynamically Discovering Likely Program Invariants to Support Program Evolution, describes techniques for dynamically discovering invariants, along with an instrumentation and inference engine that embodies these techniques. It also reports on the application of the engine to two sets of target programs and usefulness of these invariants in the software evolution.

Dynamically discovering invariants are pretty useful for middle or large-scale programs, I think. In order to discover invariants, we need to provide a set of test cases. For small programs, reading the source code will take less time and provide sufficient information for developers. But for large-scale programs, knowing the invariants and relationship between data will help developers understand the whole application in a short time.

A good feature of the inference engine is that it can be directly sped up by checking for fewer invarinants. I think this feature is pretty important in industry. For instance, when upgrading a project, it is very often that only a part of the program, specially several core functions, needs to be upgraded. Checking the necessary invariants not only speeds up the performance but also simplify the test cases and analyses.

Declaring invariants in the program helps others understand the specification and reduce bugs. More and more people realize it and add this feature to some languages. Better than C, C++ adds the key word "const" to indicate an invariant. IDL (Interface Description Language) is used to specify an interface, which can be used to generate C++ header file in COM. It has two specific key words "IN" and "OUT" for parameters in a function. An "IN" parameter can’t be changed inside the function, so it is an invariant. An "OUT" parameter doesn’t need to be initialized. Its value is usually set by the function. Thus it is easy to verify an IDL interface declaration from the specification.

There is one thing I get confused while reading this paper: How can you come up with a set of test cases and how can you guarantee that it covers the most cases? The test case is based on the program. Without knowing much about the program in advance, how can people build up the test cases?

Different from the dynamically discovering techniques, the paper "Lackwit: A Program Understanding Tool Based on Type Interface" presents an efficient method to determine the structure of a program statically. Lackwit can identify abstract data types, detect abstraction violations, find unused variables, functions, and fields of data structures, detect simple errors in operations on abstract data types, locate sites of possible references to a value, and display communication relationships between program modules.

As a static analysis tool, it is great that Lackwit can handle pointer aliasing issue. The analysis assigns extended types to variables and the types encode information about representation. Lackwit can track the contents of variables and extract information about the behavior of the functions and how they are connected. Another important feature is that Lackwit can analyze the memory allocation. Since the architecture of its type inference procedure is pretty open, we can simply use it and attach additional parameters to the type constructors to record the memory status. It is very useful to detect the data that is never read and find the memory leaks.

All the analysis Lackwit does is based on the static text of a program. It can’t provide the dynamic execution information of a program. For instance, Lackwit can detect memory leaks. Sometimes we run the program and find a large memory leak. Lackwit can’t tell us exactly what causes the memory leak if there are more than one memory leak it detects.

The given sample Morphin has 17,000 lines. Lackwit built the constraint database with the 15MB size. And it only analyzes the global variables. I think the database must contain some redundant or unnecessary information. Comparing 17,000-line source, 15 MB is really a big space. The authors don’t mention any disadvantage of Lackwit in the paper. I am wondering how it is applied in the industry.

The LCLint checking tool has been used effectively in both industry and academia to detect errors in programs and facilitate enhancements to legacy code. In the paper "Static Detection of Dynamic Memory Errors", David Evan extends LCLint to detect a broad class of important errors. By introducing annotations to make certain assumptions explicit at interface points, the static checking tool exploits these annotations and detects problems including misuses of null pointers, uses of dead storage, memory leaks, and dangerous aliasing.

Annotations are the key of the extended LCLint. Actually annotations are kind of program document. Adding annotations to the functions helps developers make their assumptions clear and find their errors in the early stage. It also helps other developers, who take over the program later, read and understand the source code easier. On other hand, it requires much more work. In order to get rid of those messages, almost each parameter of each function needs to be added an annotation. This is really time-consuming. In some cases, we need to take over other’s code to fix several bugs. We may be not quite clear with the assumptions about some functions and have no idea how to add correct annotations for them. In my opinion, LCLint is more useful when writing new code since it documents the specification and assumption. It is not an efficient way to add annotations for an existing large project for software evolution purpose.

My husband, who works at Microsoft, uses PCLint in his work. While reading the paper, I asked him whether he often used PCLint. His answer is no and the reason is "PCLint usually generates hundreds of warnings for a program". Some of the warnings even belong to the header files of the windows operation system, which he doesn’t care at all. PCLint is configurable (that’s good). So he can turn off some warnings. But even after that, there are still too many messages left. He basically just goes through these warnings and ignores most of them. PCLint did help him find one bug once.

To solve this problem, ideally LCLint should have some kind of intelligence. Instead of only checking the syntax of source code, it should have some knowledge of the program it is checking. Its users should be able to specify what kind of error they are interested. LCLint could be smart enough to point out the important errors and skip the others, such as the errors of the operating system.

I think that runtime checking is more powerful to detect memory leaks. It will be a little difficult for static checking tools to detect such a problem. Each time the memory gets allocated at run time, we can attach addition information to record it. Thus we can trace all the memory allocation. MFC (Microsoft Foundation Library) does a good job in this area already. For COM, a component may be referenced by multiple pointers. It has a counter to record the reference number. The counter increases by one when a new pointer references it and decreases by one when a pointer dereferences. If the reference number becomes zero, it will deallocate itself automatically. This is how COM smart pointer works. This mechanism avoids memory leaks. But whether runtime checking is useful is update to its test cases sometimes. For certain problems, it may be difficult to choose a good test case. This is a big problem for dynamic checking tools.