The difference between Soundness and Completeness

in #software6 years ago (edited)

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.



Congratulations @cpuu! You received a personal award!

Happy Birthday! - You are on the Steem blockchain for 1 year!

You can view your badges on your Steem Board and compare to others on the Steem Ranking

Vote for @Steemitboard as a witness to get one more award and increased upvotes!

Coin Marketplace

STEEM 0.33
TRX 0.11
JST 0.034
BTC 66438.74
ETH 3268.32
USDT 1.00
SBD 4.39