Soundness vs. Completeness
Intro
The complexity of modern programs is at the highest. No, it has been exponentially increasing.
Bill Gates said in 2007 that he spends more than 3 times of cost in testing than actual software development processes.
According to the report from Meddev, almost 90% of cost of the company goes to maintenance.
It is obvious because the complexity makes it not easy to understand the behavior of a program.
Many software companies are trying to solve this problem by program analysis.
These indice don’t look that intuitive.
Now, let’s think about Windows kernel.
It is a huge program with millions of lines of code.
One line edited in that massive lines of source code can possibly cause a bug.
Now, if that change is BIC (bug inducing commit), how can we find it?
What is making this difficult is that this change could affect thousands of lines of code.
I think that pretty much explain why program analysis is important.
When we talk about the program analysis, it can be divided into two categories:
- Dynamic Analysis
- Static Analysis
Completeness (dynamic analysis)
Completeness is one of corectness indexes for program analysis.
Let’s define a complete program.
A complete method is a method that can prove anything that’s right.
On the other hand, a complete method cannot prove that a program does not have defects.
For example, testing as one of the dynamic analysis methods is a complete method.
If a program passes all the tests, then we can say that that program satisfies the test conditions.
However, even if a program passes all test cases given, it is not necessarily bugless.
Soundness (static analysis)
Soundness is another one
A sound method is a method that cannot prove anything that’s wrong.
Meaning that it can only prove things that are right.
Which also means that if it says that a program has a bug, it can only be either false positive or true postive.
Most of the static analysis methods are sound, meaning that it can generate false alarms, yet it literally detects everything without a miss.
The following figure would explain more intuitively.
Soundness vs. Completeness
Nowadays, most of huge software companies divide up their limited resources to both static and dynamic analysis to find faults in a software.
This is because the both are uniquely different and strong in their own ways.
For example, static analysis has more scalability and obviously consumes incredibily small amount of resources compared to dynamic analysis.
On the other hand, dynamic analysis is more accurate and more intuitive, making it more trustable.
There are also cons for both. Static analysis cannot react to off-the-convention source code sturucture.
On the other hand, dynamic analysis has many undcidable NPs regarding the test cases.
Mathmatically,
If Σ is a set of hypotheses, Φ is a set of conclusions, Σ ⊨ Φ means Φ is true given Σ, and Σ ⊢ Φ means Σ can prove Φ.
Σ is sound if,
Σ ⊢ Φ –> Σ ⊨ Φ
Σ is complete if,
Σ ⊨ Φ –> Σ ⊢ Φ
Summary
Bugless software does not exist, maybe there are, but it is not possible to find them all according to the Halting Problem.
If there is an analysis method that is both sound and complete, then it would be the best.
There are other indexes such as automaticness, termination, and exactness for the reasoning method of the analysis methods
This is one of the most important problem in the software engineering field.
Like, this is literally Turing Award winning problem.