NIST logo
*

The Unravel Project

Unravel is a prototype program slicing tool that can be used to statically evaluate ANSI C source code using program slicing (general references and some of our papers). Development of unravel was funded by both the United States Nuclear Regulatory Commission (NRC) and the National Communications System (NCS) under contracts RES-92-005, FIN #L24803, and DNRO46115, respectively. Under the terms of those contracts, the National Institute of Standards and Technology (NIST) supplied the prototype to both funding parties. The tool was developed in C with a user interface written using the MIT Athena Widgets and the X Window System.

Program Slicing

Program slicing is a static analysis technique that extracts all statements relevant to the computation of a given variable. Program slicing is useful in program debugging, software maintenance and program understanding. Program slices can be used to reduce the effort in examining software by allowing a software auditor to focus attention on one computation at a time.

Mark Harmon (UK) has some interesting slicing links and Jens Krinke has a list of slicing projects and other resources.

Using Program Slicing to Evaluate High Integrity Software

By combining program slices with logical set operations, unravel can identify code that is executed in more than one computation. This information is immediately useful for addressing issues of high integrity software, since a failure involving this code may lead to a malfunction of more than one logical software component. In the case of safety systems, which commonly use several computations for protection, common code among them can provide a single point of failure. In the case of security, what may have been perceived as a secure path may be penetrated by an otherwise unsuspected approach. The identification of common code enables the developer to consider redesign or to emphasize verification and validation activities in those regions to provide assurance of the program.

Evaluating Unravel

Unravel was evaluated in the context of auditing safety system software for quality as is done by the NRC. The evaluation considered the size of slices produced, time to compute slices and usability by a novice user. The objectives of the evaluation were to determine the following:

  1. Are program slices smaller than the original program to an extent that is useful to a software auditor evaluating a program?  
  2. Can program slices be computed quickly enough to be useful in an audit?  
  3. Is unravel usable by a novice user?

 

Two examples of typical safety system code were used to test and refine unravel. Demonstration of unravel using these and other examples were given to NRC auditors and to NCS. The demonstrations resulted in improvements to the user interface and in the identification of features to be explained in more depth in the user manual or to be included in a later version of unravel.

A manual software audit is slow, tedious, and prone to human errors. With unravel, once an NRC auditor has identified a variable for further investigation, the auditor directs unravel to compute a program slice on the variable. Instead of examining the entire program, only the statements in the slice need to be examined by the auditor. By speeding up the process of locating relevant code for examination by the auditor, a larger sample of the software can be inspected with greater confidence that some relevant section of source code has not been missed.

Without any tool, an NRC auditor evaluates the software for common code shared between two computations until it is determined that there is no common code, or that the common code present will not compromise the mission of the safety critical software. With unravel, once two computations that could be vulnerable to common mode failure have been identified, program slices can be computed to find statements relevant to each computation. Source program statements that have potential to cause common mode failure would be present in the intersection of the program slices.

Unravel consists of three main components, called the analyzer, linker and slicer. The analyzer and linker components can process source code of up to 100,000 lines of code in less than 10 minutes. The linear behavior of the analyzer and linker leads to stable run time performance. The slicer component does not use a linear algorithm, but rather uses a quadratic algorithm that can have significant run time variability. The slicer performed well on programs provided by the NRC. It should be noted that there is potential for significant algorithm improvement. For example, after one small change in the slicer code that controls the order of visiting nodes during the slice computation, the longest time to compute a slice on code from an example of an actual safety system dropped from 10 hours to 3 hours. Other areas that can be improved include loop analysis and procedure calls.

Obtaining the Unravel source code

Download Unravel source code as a compresed (.Z) file. 

Publications About Unravel

The unravel tool is described in a two volume technical report (NISTIR 5691) is available by anonymous ftp. The first volume covers the requirements, design and evaluation of unravel while the second volume is an unravel user manual.

Click on your choice to transfer the document:

 

Unravel Team

The unravel team consisted of:

Jim Lyle
Dolores R. Wallace
David W. Binkley