The difference between Soundness and Completeness

Useful static analysis tools fall somewhere between sound and complete analyses.

So, let's go into what I mean by that.

Soundness is a property that states if an analysis says that x is true, then x is actually true. So what it's saying is that, when analysis says these are the things that I say, they're contained in the true things. And of course, this means that a trivially sound analysis is one that says nothing.

Completeness is such that if X is true, then the analysis says that X is true. So here are the things that I say, and true things are contained within them. So trivially complete analyses say everything.

A sound and complete analysis is such that the things I say are all of the true things. And of course what we have shown is that, for problems like the halting problem, such sound and complete analyses do not exist. You have to sacrifice either one or the other.

You can go one of two ways. You could have a sound analysis which says that if the program is claimed to be error-free, then it really is. Alarms do not imply erroneousness. A complete analysis is one that says if the program is claimed to erroneous, then it really is. Silence does not imply error freedom. So essentially, the most interesting analyses are neither sound nor complete, and not both, but they usually lead toward soundness or completeness.

Because the perfect static analysis is impossible in general, our goal is simply to make a tool that is useful. Doing so is as much art as it is science. In particular, there are many different elements of an analysis that trade off with one another.
A practical tool must decide which elements are most important.

[References]

• Software Security by University of Maryland, College Park