Using static analysis to diagnose & prevent failures in safety-critical device designs

Software content has grown rapidly in all manner of safety-critical devices.Meanwhile, society has become increasingly dependent upon their safeoperation. Unfortunately, our ability to develop safe and reliablesoftware has not improved at the same rate, resulting in increasingreliability and safety vulnerabilities.

This increase in software vulnerability poses a serious threat tohuman safety and demands new approaches to safe software development. Static analysishas emerged as apromising technology for improving the safety of software in safety criticalapplications suchas medical devices and systems (SeeSidebar ).Beyond defect prevention, static analysis is alsofinding a home in medical forensics labs, aiding scientists who mustlocate the cause of failures in recalled medical devices.

Static analysis tools analyze software to find defects that may goundetected using traditional techniques, such as compilers, human codereviews, and testing.

A number of limitations, however, have prevented widespread adoptionin safety crtical applications such as medical device softwaredevelopment. Static analysis tools oftentake prohibitively long to execute and are not well integrated into thesoftware development environment. This article discusses a number oftechniques that address these barriers to adoption.

Metrics are provided to demonstrate how static analysis can beincorporated as a practical and effective quality tool for everydaymedical device software development. In addition to traditionalanalysis, the paper also discusses how static analysis technology canbe extended to enable detection of a new class of defects.

Static source code analyzers attempt to find code sequences thatwhen executed could result in buffer overflows, resource leaks, or manyother security and reliability problems. Static sourcecode analyzers areeffective at locating a significant class of flaws that are notdetected by compilers during standard builds and often go undetectedduring run-time testing as well.

Earlier Is Better
A number of studies over the years have shown that the cost ofdetecting and correcting a software flaw increases dramatically as aproject moves through the development, integration, quality assurance,and deployment cycle [1] , asdepicted in Figure 1 below .

Figure1 – Cost of software flaws

This reality matches common sense: a software developer who findshis own bug soon after adding it has recent context in which to quicklyunderstand and fix the problem. As a project enters integration andtest phases, a flaw is often discovered by someone other than thedeveloper who added it and often much later than the flaw wasintroduced.

This, of course, makes it more difficult to trace the flaw back to itssource and for developers to infer the cause and determine the optimalsolution to the problem. Once a product has been deployed, the cost ofa serious flaw is bloated by customer service resource usage, patchingprotocols, recalls, litigation, and other potential downstream effects.

From a cost-benefit perspective, static analysis is one of the mostpowerful tools in the safety-critical device software developer's arsenalbecause it enables defects to be cheaply discovered and fixed wellbefore even a single line of code is ever executed.

Software Complexity
Many of the problems relating to loss in quality and safety in softwarecan be attributed to the growth of complexity that cannot beeffectively managed [2] . Forinstance, commodity operating system code bases have been increasing ata staggering rate.

Microsoft Windows grew from six million lines of code in 1993, to 29million in 2000, and 50 million in 2005. A Debian Linux distributionincreased even more rapidly: from over 55 million lines in 2000 to 104million in 2002, and 215 million in 2005[3]. In the medical device field, radiotherapy treatmentplanning (RTP) systems have grown increasingly sophisticated, reachingmillions of lines of code [4].

Incidence of security vulnerabilities acts as a bellwether fortracking the effects of software complexity. According to CERTstatistics, the number of documented vulnerabilities has beenincreasing almost exponentially, from approximately 400 in 1999, tomore than 4000 in 2002, and more than 8000 in 2006 [5]. Over the past five years, theCVE database [6] shows highseverity software vulnerabilities growing at a robust rate (Figure 2 below ).

Figure2 – High Severity Software Vulnerabilities (CVE)

Complexity strains traditional reliability techniques, such as codereviews, and implies a growing necessity for automated static analysistools.

Common Features Of Static AnalysisTools
Most source code analyzers perform a full program analysis, findingbugs caused by complex interactions between pieces of code that may noteven be in the same source file.

The analyzer determines potential execution paths through code,including paths into and across subroutine calls, and how the values ofsoftware objects could change across these paths. Based on this valueanalysis, the analyzer can detect anomalous coding constructs, most ofwhich would normally compile without error or warning. The following isa list of some of the more common errors that an analyzer will detect:

* PotentialNULL pointer dereferences
* Access beyond anallocated area (e.g. array or dynamically allocated buffer); otherwiseknown as buffer overflow
* Writes topotentially read-only memory
* Reads ofpotentially uninitialized objects
* Resource leaks(e.g. memory leaks and file descriptor leaks)
* Use of memorythat has already been deallocated
* Out of scopememory usage (e.g. returning the address of an automatic variable froma subroutine)
* Failure to set areturn value from a subroutine
* Buffer and arrayunderflows

The analyzer often has knowledge about how many standard runtimelibrary functions behave. For example it knows that subroutines likefree should be passed pointers to memory allocated by subroutines likemalloc. The analyzer uses this information to detect errors in codethat calls or uses the result of a call to these functions.

Figure3 – Web page flaw summary

Modern static analyzers are well known for their ability to reducethe number of false positives. A false positive is a potential defectidentified by the analyzer that could not actually occur during programexecution. If an analyzer generates too many false positives, it willbecome irrelevant because the output will be ignored by engineers.

However, since an analyzer is not able to understand completeprogram semantics, it is not possible to totally eliminate falsepositives. In some cases, a defect found by the analyzer may not resultin a fatal program fault, but could point to a questionable constructthat should be fixed to improve code clarity. A good example of this isa write to a variable that is never subsequently read.

A common output format of a static analysis tool is a set of webpages hosted by a web server. The web interface enables the user tobrowse high level summaries of the defects found by the analyzer (Figure 3 above) and then click onhyperlinks to investigate specific problems.

Within a specific problem display, the error is usually displayed incontext with the surrounding code, making it easy to understand (Figure 4 below ). Function names andother objects are hyperlinked for convenient browsing of the sourcecode. Since the web pages are running under a web server, the resultscan easily be shared and browsed by any member of the development team.

Figure4 – Context-sensitive display

Open SourceStatic Analysis. Current generation open source static analysistools such as lint and splint suffer from high false positive rates,making them impractical for use on complex software projects. The humananalysis time required to sift through the false positives often faroutweighs the cost of more accurate commercial static analysis tools.

Barriers To Widespread Adoption
A recent survey found that less than 5% of device software engineersmake regular use of static analysis tools [7] . Engineers cited the followingmain technical barriers to adoption: poor integrateddevelopment environment (IDE) integration and prohibitiveexecution time.

IDE Integration . Commercialstatic analyzers often run as separate tools, distinct from the toolchain used to develop and build application software. Thus, users mustseparately install, license, and configure the analyzer. Configurationcan often be time consuming, requiring days of customization in orderto cajole the analyzer into processing the user's particular dialect ofsource code.

An alternative approach performs static analysis within the samecompiler used to build software. This provides several advantages,including the obvious benefit of reducing the time to effective usage.

Since static analysis is performed by the compiler, it doesn't needto make guesses regarding the proper application of build options,location of include header files and directories, or the definitions ofpreprocessor macros. In fact, software projects are often built bydevelopment teams in multiple configurations. By running within thecompiler, the analyzer sees each distinct configuration in its precisedeployed form.

Flaws discovered by the static analyzer can be interleaved with theother standard diagnostics output by the compiler (Figure 5 below ). Furthermore, commonIDE integrations between the project builder and the editor augment theusability of the static analysis tool: when a static analysis flaw isreported during the build process, the user can hyperlink from thebuilder's output window back to the source code quickly, rectify theerror, and then return to building the program.

Figure5 – Integration of static analysis with project builder

With proper project management integration, static analysis becomesmerely another option that any developer can easily enable or disablefrom an options menu.

Execution Time. Many commercial static analyzers require orders of magnitude moreexecution time than a regular compile. Large software projects mayrequire hours, days, even weeks of analysis time. This execution costpresents a barrier to adoption, causing static analysis, if used atall, to be employed only periodically or during test phases.

Static analysis tools could enjoy improved adoption if executiontime can be reduced to a level that encourages constant use; developerscan detect flaws while software is first written and before it is evercommitted to a configuration management system.

Here again is where the integrated compiler approach provesbeneficial. The static analysis engine can take advantage of compilerdataflow analysis, constant propagation, and path pruning algorithms,developed and tuned over many years for execution time efficiency ofcomplex code optimizations, to improve run-time performance.

Secondly, the total time to build and analyze software would bereduced since the compiler uses a single parsing pass of the code toperform both compilation and analysis.

Integration with the compiler may also enable the analyzer to takeadvantage of the IDE's existing distributed build mechanism. As aresult, the parsing pass for the project's source code can bedistributed across idle workstation assets on a user's network,dramatically reducing the total analysis time.

Static analyzers could also be integrated with the IDE's projectmanagement system. The project manager typically uses dependencyanalysis to monitor which code subroutines have changed since the mostrecent build. In much the same way, static analysis can be limited tothe program subgraph affected by the last modification. Thisoptimization dramatically reduces analysis time when used throughoutthe software development cycle.

Studies have shown that an application of static analysis that takesadvantage of compiler integration, change dependency analysis, and IDEdistributed processing yields analysis times comparable withtraditional compilation times, thereby removing an important barrier toadoption.

Future directions for staticanalysis
To meet the future requirements for the growing number of safetycritical embedded device designs, work needs to be done in two keyareas: finding new classes of defects and coding for safety.

New Classes OfDefects. Traditional static analyzers are implemented in a highlevel language code processor (or “front end”). Such a tool consumessource code and produces defect diagnostics relating to the source codeitself and nothing else.

The integrated compiler approach consumes source code, produceserror diagnostics, and optionally generates the target object code forthe software (adding “back end” functionality). By incorporatingknowledge of the run-time object code characteristics of software,static analysis is able to locate some classes of defects thatstandalone analyzers simply cannot reach.

Stack overflow detection is oneexample. Multithreaded applications use concurrent threads toaccomplish their work. In many classes of medical devices, memory isconstrained, and the programmer must specify the size of run-time stackfor each thread to use.

When a thread uses more stack space than was allocated, a stackoverflow occurs. The result of a stack overflow varies. In some cases,the overflow causes corruption of critical data located beyond thestack segment, resulting in a downstream system failure.

During its target code generation phase, the static analyzer is ableto compute the run-time stack memory size requirements for eachsubroutine. This information is combined with the analyzer'sintelligent inter-module path comprehension to compute worst case stacksize requirements for the entire application and warn the user whenthese requirements exceed the specified per-thread allocations.

Thus, an insidious run-time defect is detected and prevented withstatic analysis. This is one example where the soundness, or ability todetect defects, needs to improve over time in static analysis tools.

It is conceivable that other types of defects and secure softwaredevelopment features can be added to the static analysis tool. Forexample, since the analyzer understands the complex pathways throughsoftware and can generate code, unit testing software can beautomatically inserted to improve coverage. This is one of manypromising areas of research.

Coding ForSafety. Most safe and secure development processes espouse theuse of a coding standard that governs how developers write code [9]. The goal of the coding standardis to increase reliability by promulgating intelligent codingpractices.

For example, a coding standard may contain rules that helpdevelopers avoid dangerous language constructs, limit complexity offunctions, and use a consistent syntactical and commenting style.

These rules can reduce the occurrence of defects, make softwareeasier to test, and improve long term maintainability. There are sometools that enable various parts of coding standards to be automaticallyenforced.

Good software practices also espouse design by contract” (DbC) methodology.With DbC, the software developer uses language features or extensionsto check subroutine preconditions and postconditions, correctnessassertions, and other designinvariants.

Unless the developer is using SPARK Ada or other obscureprogramming languages that incorporate DbC, the programmer must resortto run-time verification of these design contracts.

Of course thorough testing is also critical to software robustness.Although there are some tools for semi-automating the generation oftest cases, most developers resort to traditional manual methods.

One vision for static analyzers is to incorporate all of the aboverobustness techniques (and more) into a single tool that is fullyintegrated, executes efficiently, and needs only to examine the sourcecode statically. This “uber-analyzer” can perform traditional staticanalysis, enforce coding standards, generate test cases, enforce asmany DbC constructs as possible, and more.

Conclusion
Static analysis represents the next major ingredient to be added tohigh quality coding standards for medical device software development.A number of optimizations and integrations are possible to make it easyand efficient to incorporate automated static source code checking intothe everyday safe software development process.

Furthermore, static analysis can be an important weapon in theregulatory investigator's arsenal to quickly locate potential sourcesof malfunction in complex device software.

DavidKleidermacher is chief technology officer at Green HillsSoftware where he has been designing compilers, softwaredevelopment environments, and real-time operating systems for the past16 years. David frequently publishes articles in trade journals andpresents papers at conferences on topics relating to embedded systems.He holds a BS in computer science from Cornell University, and can bereached at davek@ghs.com.

References
[1] TheEconomic Impacts ofInadequate Infrastructure for Software Testing; NIST; May 2002, p.1-13.
[2] Are VendorsDoing Enough To Improve Software?; Robert Parker; OptimizeMagazine;
[3] Debian-counting.Communication Systems Group of the University Rey Juan Carlos, MadridSpain;
[4] American Association ofPhysicists in Medicine Radiation Therapy Committee Task Group 53: Quality assurancefor clinical radiotherapy treatment planning; Benedick Fraass, etal.; 1998;
[5] CERTStatistics
[6] CommonVulnerabilities and Exposures (CVE)
[7] Survey of engineers atEmbedded World 2006; Nuremberg, Germany
[8] TimeMachines:the futureof debuggers; Mike Lindahl; RTC Magazine; October 2006
[9] DO-178B,SoftwareConsiderations in Airborne Systems and Equipment Certification; at RTCA.Inc.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.