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.
An interactive demo is available through the CHISSA
Demo Facility .
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
a list of people
interested in program slicing 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:
-
Are program slices smaller than the original program to an extent that
is useful to a software auditor evaluating a program?
-
Can program slices be computed quickly enough to be useful in an audit?
-
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 current unravel team members are:
Related NIST pages
Contact Information
Jim Lyle
National Institute of Standards and Technology
Information Technology Laboratory
NIST North / Room 526
Gaithersburg, MD 20899
(Voice) +1(301)975-3270
(Fax) +1(301)926-3696
(Internet) jlyle@nist.gov
This page ( http://hissa.ncsl.nist.gov/~jimmy/unravel-new.html ) was
last modified Friday, 27-Mar-98 14:30:40 EST.