Software content has grown rapidly in all manner of safety-critical devices.
Meanwhile, society has become increasingly dependent upon their safe
operation. Unfortunately, our ability to develop safe and reliable
software has not improved at the same rate, resulting in increasing
reliability and safety vulnerabilities.
This increase in software vulnerability poses a serious threat to
human safety and demands new approaches to safe software development. Static analysis
has emerged as a
promising technology for improving the safety of software in safety critical
applications such
as medical devices and systems (See
Sidebar).
Beyond defect prevention, static analysis is also
finding a home in medical forensics labs, aiding scientists who must
locate the cause of failures in recalled medical devices.
Static analysis tools analyze software to find defects that may go
undetected using traditional techniques, such as compilers, human code
reviews, and testing.
A number of limitations, however, have prevented widespread adoption
in safety crtical applications such as medical device software
development. Static analysis tools often
take prohibitively long to execute and are not well integrated into the
software development environment. This article discusses a number of
techniques that address these barriers to adoption.
Metrics are provided to demonstrate how static analysis can be
incorporated as a practical and effective quality tool for everyday
medical device software development. In addition to traditional
analysis, the paper also discusses how static analysis technology can
be extended to enable detection of a new class of defects.
Static source code analyzers attempt to find code sequences that
when executed could result in buffer overflows, resource leaks, or many
other security and reliability problems. Static source
code analyzers are
effective at locating a significant class of flaws that are not
detected by compilers during standard builds and often go undetected
during run-time testing as well.
Earlier Is Better
A number of studies over the years have shown that the cost of
detecting and correcting a software flaw increases dramatically as a
project moves through the development, integration, quality assurance,
and deployment cycle [1], as
depicted in Figure 1 below.
Figure
1 - Cost of software flaws
This reality matches common sense: a software developer who finds
his own bug soon after adding it has recent context in which to quickly
understand and fix the problem. As a project enters integration and
test phases, a flaw is often discovered by someone other than the
developer who added it and often much later than the flaw was
introduced.
This, of course, makes it more difficult to trace the flaw back to its
source and for developers to infer the cause and determine the optimal
solution to the problem. Once a product has been deployed, the cost of
a serious flaw is bloated by customer service resource usage, patching
protocols, recalls, litigation, and other potential downstream effects.
From a cost-benefit perspective, static analysis is one of the most
powerful tools in the safety-critical device software developer's arsenal
because it enables defects to be cheaply discovered and fixed well
before even a single line of code is ever executed.
Software Complexity
Many of the problems relating to loss in quality and safety in software
can be attributed to the growth of complexity that cannot be
effectively managed [2]. For
instance, commodity operating system code bases have been increasing at
a staggering rate.
Microsoft Windows grew from six million lines of code in 1993, to 29
million in 2000, and 50 million in 2005. A Debian Linux distribution
increased even more rapidly: from over 55 million lines in 2000 to 104
million in 2002, and 215 million in 2005
[3]. In the medical device field, radiotherapy treatment
planning (RTP) systems have grown increasingly sophisticated, reaching
millions of lines of code [4].
Incidence of security vulnerabilities acts as a bellwether for
tracking the effects of software complexity. According to CERT
statistics, the number of documented vulnerabilities has been
increasing almost exponentially, from approximately 400 in 1999, to
more than 4000 in 2002, and more than 8000 in 2006 [5]. Over the past five years, the
CVE database [6] shows high
severity software vulnerabilities growing at a robust rate (Figure 2 below).
Figure
2 - High Severity Software Vulnerabilities (CVE)
Complexity strains traditional reliability techniques, such as code
reviews, and implies a growing necessity for automated static analysis
tools.
Common Features Of Static Analysis
Tools
Most source code analyzers perform a full program analysis, finding
bugs caused by complex interactions between pieces of code that may not
even 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 of
software objects could change across these paths. Based on this value
analysis, the analyzer can detect anomalous coding constructs, most of
which would normally compile without error or warning. The following is
a list of some of the more common errors that an analyzer will detect:
* Potential
NULL pointer dereferences * Access beyond an
allocated area (e.g. array or dynamically allocated buffer); otherwise
known as buffer overflow * Writes to
potentially read-only memory * Reads of
potentially uninitialized objects * Resource leaks
(e.g. memory leaks and file descriptor leaks) * Use of memory
that has already been deallocated * Out of scope
memory usage (e.g. returning the address of an automatic variable from
a subroutine) * Failure to set a
return value from a subroutine * Buffer and array
underflows
The analyzer often has knowledge about how many standard runtime
library functions behave. For example it knows that subroutines like
free should be passed pointers to memory allocated by subroutines like
malloc. The analyzer uses this information to detect errors in code
that calls or uses the result of a call to these functions.
Figure
3 - Web page flaw summary
Modern static analyzers are well known for their ability to reduce
the number of false positives. A false positive is a potential defect
identified by the analyzer that could not actually occur during program
execution. If an analyzer generates too many false positives, it will
become irrelevant because the output will be ignored by engineers.
However, since an analyzer is not able to understand complete
program semantics, it is not possible to totally eliminate false
positives. In some cases, a defect found by the analyzer may not result
in a fatal program fault, but could point to a questionable construct
that should be fixed to improve code clarity. A good example of this is
a write to a variable that is never subsequently read.
A common output format of a static analysis tool is a set of web
pages hosted by a web server. The web interface enables the user to
browse high level summaries of the defects found by the analyzer (Figure 3 above) and then click on
hyperlinks to investigate specific problems.
Within a specific problem display, the error is usually displayed in
context with the surrounding code, making it easy to understand (Figure 4 below). Function names and
other objects are hyperlinked for convenient browsing of the source
code. Since the web pages are running under a web server, the results
can easily be shared and browsed by any member of the development team.
Figure
4 - Context-sensitive display
Open Source
Static Analysis. Current generation open source static analysis
tools such as lint and splint suffer from high false positive rates,
making them impractical for use on complex software projects. The human
analysis time required to sift through the false positives often far
outweighs the cost of more accurate commercial static analysis tools.
Barriers To Widespread Adoption
A recent survey found that less than 5% of device software engineers
make regular use of static analysis tools [7]. Engineers cited the following
main technical barriers to adoption: poorintegrated
development environment (IDE) integration and prohibitive
execution time.
IDE Integration. Commercial
static analyzers often run as separate tools, distinct from the tool
chain used to develop and build application software. Thus, users must
separately install, license, and configure the analyzer. Configuration
can often be time consuming, requiring days of customization in order
to cajole the analyzer into processing the user's particular dialect of
source code.
An alternative approach performs static analysis within the same
compiler 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 need
to make guesses regarding the proper application of build options,
location of include header files and directories, or the definitions of
preprocessor macros. In fact, software projects are often built by
development teams in multiple configurations. By running within the
compiler, the analyzer sees each distinct configuration in its precise
deployed form.
Flaws discovered by the static analyzer can be interleaved with the
other standard diagnostics output by the compiler (Figure 5 below). Furthermore, common
IDE integrations between the project builder and the editor augment the
usability of the static analysis tool: when a static analysis flaw is
reported during the build process, the user can hyperlink from the
builder's output window back to the source code quickly, rectify the
error, and then return to building the program.
Figure
5 - Integration of static analysis with project builder
With proper project management integration, static analysis becomes
merely another option that any developer can easily enable or disable
from an options menu.
Execution Time.
Many commercial static analyzers require orders of magnitude more
execution time than a regular compile. Large software projects may
require hours, days, even weeks of analysis time. This execution cost
presents a barrier to adoption, causing static analysis, if used at
all, to be employed only periodically or during test phases.
Static analysis tools could enjoy improved adoption if execution
time can be reduced to a level that encourages constant use; developers
can detect flaws while software is first written and before it is ever
committed to a configuration management system.
Here again is where the integrated compiler approach proves
beneficial. The static analysis engine can take advantage of compiler
dataflow analysis, constant propagation, and path pruning algorithms,
developed and tuned over many years for execution time efficiency of
complex code optimizations, to improve run-time performance.
Secondly, the total time to build and analyze software would be
reduced since the compiler uses a single parsing pass of the code to
perform both compilation and analysis.
Integration with the compiler may also enable the analyzer to take
advantage of the IDE's existing distributed build mechanism. As a
result, the parsing pass for the project's source code can be
distributed 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 project
management system. The project manager typically uses dependency
analysis to monitor which code subroutines have changed since the most
recent build. In much the same way, static analysis can be limited to
the program subgraph affected by the last modification. This
optimization dramatically reduces analysis time when used throughout
the software development cycle.
Studies have shown that an application of static analysis that takes
advantage of compiler integration, change dependency analysis, and IDE
distributed processing yields analysis times comparable with
traditional compilation times, thereby removing an important barrier to
adoption.
Future directions for static
analysis
To meet the future requirements for the growing number of safety
critical embedded device designs, work needs to be done in two key
areas: finding new classes of defects and coding for safety.
New Classes Of
Defects. Traditional static analyzers are implemented in a high
level language code processor (or "front end"). Such a tool consumes
source code and produces defect diagnostics relating to the source code
itself and nothing else.
The integrated compiler approach consumes source code, produces
error diagnostics, and optionally generates the target object code for
the software (adding "back end" functionality). By incorporating
knowledge of the run-time object code characteristics of software,
static analysis is able to locate some classes of defects that
standalone analyzers simply cannot reach.
Stack overflow detectionis one
example. Multithreaded applications use concurrent threads to
accomplish their work. In many classes of medical devices, memory is
constrained, and the programmer must specify the size of run-time stack
for each thread to use.
When a thread uses more stack space than was allocated, a stack
overflow occurs. The result of a stack overflow varies. In some cases,
the overflow causes corruption of critical data located beyond the
stack segment, resulting in a downstream system failure.
During its target code generation phase, the static analyzer is able
to compute the run-time stack memory size requirements for each
subroutine. This information is combined with the analyzer's
intelligent inter-module path comprehension to compute worst case stack
size requirements for the entire application and warn the user when
these requirements exceed the specified per-thread allocations.
Thus, an insidious run-time defect is detected and prevented with
static analysis. This is one example where the soundness, or ability to
detect defects, needs to improve over time in static analysis tools.
It is conceivable that other types of defects and secure software
development features can be added to the static analysis tool. For
example, since the analyzer understands the complex pathways through
software and can generate code, unit testing software can be
automatically inserted to improve coverage. This is one of many
promising areas of research.
Coding For
Safety. Most safe and secure development processes espouse the
use of a coding standard that governs how developers write code [9]. The goal of the coding standard
is to increase reliability by promulgating intelligent coding
practices.
For example, a coding standard may contain rules that help
developers avoid dangerous language constructs, limit complexity of
functions, and use a consistent syntactical and commenting style.
These rules can reduce the occurrence of defects, make software
easier to test, and improve long term maintainability. There are some
tools that enable various parts of coding standards to be automatically
enforced.
Unless the developer is using SPARK Ada or other obscure
programming languages that incorporate DbC, the programmer must resort
to 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 of
test cases, most developers resort to traditional manual methods.
One vision for static analyzers is to incorporate all of the above
robustness techniques (and more) into a single tool that is fully
integrated, executes efficiently, and needs only to examine the source
code statically. This "uber-analyzer" can perform traditional static
analysis, enforce coding standards, generate test cases, enforce as
many DbC constructs as possible, and more.
Conclusion
Static analysis represents the next major ingredient to be added to
high quality coding standards for medical device software development.
A number of optimizations and integrations are possible to make it easy
and efficient to incorporate automated static source code checking into
the everyday safe software development process.
Furthermore, static analysis can be an important weapon in the
regulatory investigator's arsenal to quickly locate potential sources
of malfunction in complex device software.
David
Kleidermacher is chief technology officer at Green Hills
Software where he has been designing compilers, software
development environments, and real-time operating systems for the past
16 years. David frequently publishes articles in trade journals and
presents papers at conferences on topics relating to embedded systems.
He holds a BS in computer science from Cornell University, and can be
reached at davek@ghs.com.
