Anyone who develops critical embedded software knows how softwarefaults ” also called run-time errors ” can be troublesome. An otherwisefully functional program plagued with run-time error will function asplanned, but will not be reliable. Impacts of run-time errors rangefrom false program results (and thus unpredictable behavior) to CPUcrash (usually taking down the whole system with it).
Run-time errors includes several types of bugs, ranging from illegalarithmetic operations (such as divisions by zero) to different kinds ofmemory corruption (such as out-of-bounds array accesses or illegallyde-referenced pointers), possible conflicting access on sharedvariables, and other improprieties of the code leading to unpredictableprogram behavior (such as reading an un-initialized variable). Theseerrors can be systematic (occur every time the program is executed) orintermittent (only occur under specific operating conditions). Run-timeerrors are in general difficult to detect, especially if they areintermittent.
In any case, the presence of run-time errors means poor softwarereliability that may jeopardize system integrity. Which is whyorganizations developing life, mission, business or safety-criticalsoftware (such as in Automotive, Defense, Aerospace, Medical Devicesand so on) spend a great deal of time and money to eliminate these bugsfrom their programs.
However, finding run-time errors is anything but easy. Dynamictesting, during which engineers develop test cases in order to “flushout” bugs, is very effective at finding functional bugs. However,run-time errors are often triggered by a small subset of possible inputvalues and operating conditions, which means that there is no way to besure that a program is run-time error-free unless each possible testcase is ran with every possible input values and operating conditions “which is all but impossible. Even in the case where a test case revealsthat there could be a run-time error, it really finds the consequence,not the source of that error. The error must then be identified at itssource through debugging ” usually a lengthy process.
On the other hand, manual code review, although an effectivetechnique, also faces the fundamental problem of detecting hard-to-findbugs that are triggered by specific and complex combinations of inputvalues. Furthermore, code review is a human-based activity that heavilyrelies on personal skills, which makes it difficult to reproduce.
Semantic analysis in a nutshell
For years, developers have struggled to find a way to detect run-timeerrors more efficiently. A number of organizations tried to useconventional static analyzers to detect run-time errors moreefficiently.
However, most static analyzers proved more effective at preventingthe introduction of run-time errors by enforcing coding rules than atdetecting run-time errors per se. These tools frequently return toomany false positives (indicating an operation has an error when thereis none), or they would return too many false negatives (omitting toflag an error where there is one). In most cases, these analyzerssuffer from both ailments, which severely limit their usefulness aserror detection solutions.
This is where semantic analysis comes in. The term semantic analysisrefers to a group of advanced static analysis techniques that enableusers to detect runtime and/or dynamic errors in software applications.
First used by modern compilers for code optimization, semanticanalysis address the problem of intermittent run-time errors byexhaustively analyzing the very dynamics the code ” including possibleranges of values different variables can take during execution ” beforecompilation actually takes place.
The result is that semantic analysis can certify that someoperations are run-time error-free under all operating conditions “thereby solving the false negative issue plaguing conventional staticanalyzers. It also delivers an analysis that is a lot more precise thanconventional static analyzers ” putting a serious dent in the number offalse positives. Finally, the technique can be completely automated ina software solution, which means that it does not add to the (alreadyheavy) burden of software engineers.
Four different types of diagnostics
In general, conventional static analyzers merely flag what they detectas being potential errors.Operations that are not flagged are not necessarily error-free – itsimply means that the tool was not able to determine if an error couldoccur or not. The user is thus left wondering how many other potentialbugs exist ” and where they are located.
On the other hand, semantic analysis provides four different typesof diagnostics on every operation that could in theory return arun-time error. In other words, semantic analysis is exhaustive in thesense each code section is verified and diagnosed against all possiblevalues of data.
Figure 1, below illustrates the four possible diagnostics, The first example (upper left quadrant ) isstraightforward ” the possible value and dangerous value zones areclearly distinct, with no overlap. Because the region of realisticvalue is the result of an abstraction which, by mathematicaldefinition, contains all values that can be experienced by the programduring execution, it is possible to conclude that there is no chancethat this particular operation returns a run-time error ” under anyoperating conditions.
|Figure1. The four types of diagnostic under semantic analysis|
In the upper right quadrant , theregion of realistic values is completely engulfed by the danger zone,which means that there will be anerror each and every time the operation is executed. On theother hand, the lower-leftquadrant is really leftto interpretation. The overlap between the two zones may indicate thepresence of a real intermittent error.
However, it is also possible that the region of possible values hasbeen abstracted in such a way that, in reality, no dangerous value willin fact occur. Given the potentially destructive nature of run-timeerrors, most of these diagnostics should be checked.
Semantic analysis can also locate unreachable code. This would bethe case when the region of possible values is empty, as illustrated bythe lower right quadrant in Figure 1, above .
Semantic Analysis In Action
The best way to understand how semantic analysis works is to walkthrough an example. Let us suppose that we must check for the presenceof run-time error in the following line of C code (for more details,please read Chris Hote's white paper):
y = 1 / (x-y);
If we assume that this line is part of a complex program and thatboth x and y are integers, we would have to check for at least threedifferent types of errors: (1) x or y could be not initialized at thispoint in time in the application, (2) there could be an overflow or anunderflow, and (3) there could be a division by zero.
If we were to check for the possible presence of a division by zero,we could represent the situation as follows (Figure 2 below ).
|Figure2. Possible division by zero|
In this graph we indicated all combinations of values of x and ythat can really occur duringexecution. These values would be the result obtained if someone were totest all possible test caseswith all possible inputvalues under all the possible combination of events ” something that isjust not possible.
We also drew a red line representing dangerous combinations of values “meaning combinations that would return a division by zero. Here, therelationship is linear, as a division by zero would occur whenever x isequal to y. Other types of errors or other code structures could have a”danger zone” that has a different shape (not a line).
Determining a set of dangerous values is relatively straightforward.But as we said before, knowing in advance and with precision thecombination of values that can bepotentially achieved is all but impossible. We could certainlywrite a lot of test cases to “flush out” as many possible combinationsof values as possible, but ultimately there would be no way to be surethat we found them all, which means we would not be sure that somepossible combinations of values are not, in fact, lying in the “dangerzone”.
The alternative is to determine a region of possible combination ofvalues in our graph just as we determine a region of dangerouscombinations of values. Thatabstraction should be made based on the semantic of the code.One very simple example would be based on the type information ofvariable x and y, namely their respective maximum and minimum values (Figure 3, below ).
|Figure3. A simple abstraction|
That type of abstraction (also known as type analysis) is relativelyeasy to implement. Unfortunately, its usefulness is limited. Theproblem stems from the fact that most of the region flagged ascontaining possible combinations of values does not, in fact, containany. The predictable result is a lot of false positives ” flaggingoperations as potentially error-ridden when they really are error-free.This is exactly the problem that is plaguing so many static analyzers.
The techniques at the heart of semantic analysis bring theabstraction process to the next level. Based on the internal dynamicsof the code, these techniques enable us to further refine the region ofpossible combination of values so as to dramatically reduce the numberof false positives. The result is a much more precise analysis.
|Figure4. Semantic analysis|
As seen in Figure4, above , semantic analysis ensures that each possiblecombination of values is still within the “possible” zone ” that is,the area containing combination of values that can actually occur atrun-time. However, that or these “zones” are much smaller in scope thanwhen using type analysis.
From that graphic, it can be concluded that a division by zero cannot mathematically occur atthis point in our program (in comparison, type analysis would havethrown a warning – so-called false positive).
Refining The Shapes
A number of techniques can be implemented in order to refine the shapeand size of the region containing possible combinations of values.These techniques are based on years of research in mathematics, and thedemonstration of the most advanced applications is clearly out of thescope of this article. The following is merely an overview of theirsimplest applications.
For example, in the following code excerpt, we can see how threedifferent techniques (conditional statement analysis, inter-proceduralanalysis and pointer arithmetic) can be used to further refine the zoneof possible values (Figure5, below ).
|Figure5. Small program|
Conditional statement analysis: A semantic analysis tool would have determined that pointer p at line 76 cannot point out of itsbounds. This diagnostic is based on the fact that the address that p points to is originally the firstelement of the array tab .Then, the for loop increments p untilit points out of bounds ” but then the loop is immediately terminated,without executing the operation at line 76. Thus, the range ofrealistic address values for p at line 76 would never point out of thebounds of the tab array.
The situation is different at line 81. If both the if statements at line 78 and 80 aretrue, then the value assignment through p is clearly writing out of bounds,based on the information propagated from the previous for loop. Sincethe pointer will be always out of the bounds of the array at this pointin the program, it has been flagged in red.
Interprocedural analysis: Semantic analysis can also determine the range of values that can beobtained from the call to functions. In this case, the tool determinedthat the call to function get_oil_pressure() at line 80 will always return a value superior to zero. Thus, the else statement at lines 82-83 willnever get executed. This code is flagged in gray. Although not arun-time error per se , deadcode can often point out to design flaws, logical errors, or redundantdefensive code.
Pointer arithmetic: Semanticanalysis also implements complex arithmetic calculations to determinerealistic value ranges. In our example, at line 87 the pointer mightpoint out of its bounds depending on the value taken by variable i, which is why it was flagged as an intermittent error (in orange).However, the assignment at line 91 clearly cannot be out-of-bounds,because the value of p has beenpreviously modified by i, and that thevalue of i has been restricted to somewhere above 0 but not larger than 100.
It should also be noted that depending on the values that arereturned by the function random_int() ,the assignment at line 87 could also cause an overflow or an underflow.Overall, the analysis flagged out two potentially dangerous pointeraccesses out of four, and certified that the two other accesses aresafe, thus enabling engineers to focus their code review efforts whereit really matters.
The authors would like to thankChris Hote for his help on this article.
Steve Barriaultmarketing manager is and Marc Lalo is a consultant at PolySpace Technologies.