Using static analysis to evaluate software in medical devices
The Center for Devices and Radiological Health (CDRH) at the FDA is responsible for post-market surveillance of medical devices. If a device failure resulting in actual or potential serious injury or death is reported, the manufacturer of the medical device is required to investigate, determine the root cause and contributory factors, develop appropriate corrective actions, and report their findings to CDRH.
In cases where the adequacy of the manufacturer's investigation or corrective action is in question, CDRH may conduct an independent investigation. Commensurate with the threat to public health, CDRH can unilaterally take a range of actions, including issuing public health notifications or mandating a product recall.
Performing a post-market investigation, however, is not an easy task. This is particularly true in the case of software, where the execution is often user-driven and system-specific. To further complicate matters, device software is usually event-driven, resulting in failures that are often unpredictable and may not be easily reproducible. In such cases, the only way to trace the software flaws has historically been to manually review the source code itself. Given the complexity of modern medical-device software, this is a very difficult and time-consuming task for a third-party investigator with no prior knowledge of the software.
Recently the CDRH's Office of Science and Engineering Laboratories (OSEL) has been investigating the use of static analysis technology to assist in this task. This article gives a brief introduction to static analysis and explains how we used this technique to detect flaws.
Historically, static analysis has been used mainly to enforce syntax checks and coding standards in software. Over the last few years, a new breed of static analysis tools, based on light-weight formal methods, has emerged that can be used to detect potentially fatal flaws in the software.
The flaws detected by these static analysis tools include runtime errors, such as buffer overruns, null pointer dereferences, race conditions, resource or memory leaks, and dangerous casts. Some advanced tools also incorporate a facility to detect inconsistencies in the code, such as redundant conditions or erroneous assumptions that may indicate programmer misunderstandings. Typically, when a potential flaw is found in the software, the tool generates a warning that allows the user to see not only where the flaw occurs, but the conditions that must hold in order for it to occur.
An advanced static analysis tool typically operates by performing an abstract or symbolic execution of the program. During this execution, program variables containing actual concrete values are replaced by corresponding symbolic values. The analysis proceeds by using these symbolic values to follow all possible paths through the code. Along each path, all possible symbolic values are recorded. As this execution proceeds, the analysis may learn facts about the variables and how they relate to each other. It uses these facts to refine associated symbolic values and check for potential errors. If any of the values is determined to result in an error at any point along the path, a corresponding warning is issued.
As an example, consider the code snippet shown in Listing 1. When analyzing this code, the static analysis tool computes symbolic values for the variables x, p, and q along all possible paths in the program. As it navigates through these paths, the tool learns facts about the variables and uses them to refine their corresponding symbolic values. Along the path comprising lines 29 through 35 for instance, the tool learns that x can only hold values between 0 and 100. Therefore, it refines the symbolic value associated with x to the range [0..100]. Further, it learns that when x is equal to 10, the pointer q is assigned the value NULL. Thus, the tool associates the symbolic value NULL with q, provided the predicate (x == 10) is true.
Finally, on line 34, when q is dereferenced, the tool determines that a possible symbolic value for q may be NULL and issues a corresponding 'NULL Pointer Dereference' warning to indicate the same.
A common problem with static analysis tools is the generation of false positives--warnings reported by the tool that are not genuine errors. False positives are generally caused due to a lack of domain-specific knowledge about the code. Typically, this involves variables that can only hold specific values and can never be assigned the erroneous symbolic values as computed through static analysis. A high false-positive rate is undesirable as it could result in needless effort for the user and may result in true positives (errors) being overlooked.
While completely eliminating false positives is not possible, most static analysis tools deal with this problem by providing users with configuration parameters to control the analysis. For example, the maximum number of paths explored per procedure may be specified to increase or limit the search-space for the tool. These configuration parameters help provide the tool with the missing domain-specific knowledge required for accurate analysis, while allowing users to select the level of analysis most appropriate for their application.