Slide Index

Software Quality Week (May 28, 1997):

UNIT 1 Unravel ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.0

Unravel :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.1

Talk Outline ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.2

Evaluating High Integrity Software ::::::::::::::::::::::::::::::::::::::::::::::::: 1.3

Program Slicing :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.4

Combining Slices ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.5Programmer's View After a Slice ::::::::::::::::::::::::::::::::::::::::::::::::::: 1.6Computing a Program Slice :::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.7Slices on Output 1 and Output 2 ::::::::::::::::::::::::::::::::::::::::::::::::::: 1.8Combined Slices on Output 1 and Output 2 ::::::::::::::::::::::::::::::::::::::::: 1.9Using Unravel on Sample Code :::::::::::::::::::::::::::::::::::::::::::::::::::: 1.10Unravel Performance ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.11Current Work ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.12Call Tree Example 1 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.13Call Tree Example 2 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.14Call Tree Example 3 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.15Basic Unravel Design ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.16

Future Work :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.17

C++ Parsing :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.18Conclusions ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 1.19

1
20 slides

April 18, 1997

2

UNIT 1

Unravel

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.0
Unravel

USING THE UNRAVEL PROGRAM SLICING TOOL

TO EVALUATE HIGH INTEGRITY SOFTWARE

James R. Lyle JLYLE@NIST.GOV

Dolores R. Wallace DWALLACE@NIST.GOV

SOFTWARE QUALITY WEEK

San Francisco

May 27-30, 1997

Version

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.1
Talk Outline

 Evaluating High Integrity Software

 Program Slicing Results Using Unravel

 Current Work Future Work

 Conclusions

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.2
Evaluating High Integrity Software

 Failure of High Integrity Software ) serious accident or

severe nancial loss ) software needs careful evaluation& review.

 Simpler to compare spec of computation to code if code

of other computations are removed.

 Dierent algorithms used to compute consistency check

) possible point of common failure.

 Need to nd software faults (bugs) quickly. All of the above are variations on the theme:

Need to understand an existing program.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.3
Program Slicing

 Program Slice: All program statements relevant to a

given computation.

 Slicing Criterion: Species the slice (computation) for

a variable, v, at a statement, n.

 Program slices for a given slicing criterion are obtained

from a given program, P, by deleting zero or more statements from P, but the slice still computes the same valuefor v at statement n.

 Data{
ow analysis is used to identify statements that

may be deleted without aecting the computation.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.4
Combining Slices

Program slices can be combined to nd or exclude common

code.

 The intersection of two slices (backbone slice) is the

set of statements common to the two computations (A

ma jor concern in high integrity software).

 A slice minus a backbone slice gives the statements

unique to a computation (program dice).

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.5
Programmer's View After a Slice

ρ1 ρ2

β ω

ω

σ

Output 1 Output 2 Output 3

Input 3

Input 1 Input 2

Output 1 Output 2

Input 3

Input 1 Input 2

Output 3 Output 1 Output 2

Inp

Input 1 Input 2

Out

Initial View After Slice on Output 3 Relations Between Two Slices

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 
Computing a Program Slice

To locate the statements that in
uence variable v just

before execution reaches statement m we would compute aprogram slice for the criterion < m; v >.

1. Start with program 
ow-graph

2. Annotate with variables referenced and assigned to

3. the defs(n) set and the slicing criterion determine inclusion

4. the refs(n) set gives new criterion

S<m;v> =

8>>>><>>>>: S<n;v> if v 62 defs(n) fng [ S<n;x>8x 2 refs(n) otherwise

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.7
Slices on Output 1 and Output 2

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.8
Combined Slices on Output 1 and Output 2

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.9
Using Unravel on Sample Code

Unravela was tried on sample high integrity code, generated by a software reviewer.

 Allowed auditor to extract a computation for manual

examination

 Found questionable sharing of code

aDevelopment of unravel was supported under interagency agreement DNRO46115 between the Department of Defense and NIST. Currently

unravel is supported by NIST and the NRC. Development of the unravel tool is being supported under interagency agreement RES-92-005

between the U.S. Nuclear Regulatory Commission and NIST. The opinions, ndings, conclusions and recommendations expressed herein are those

of the author(s) and do not necessarily re
ect the views of the NRC.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.10
Unravel Performance

(1) Unravel signicantly enhances ability to analyze code.(2) Unravel is easy to operate.

(3) Unravel can disclose subtle relationships in code that

would require a C expert to discover.

(4) The ma jority of the slices were less than 25 percent of

the size of the original program (some as small as 10

percent of the original).

(5) Requested slices were computed in less than one

minute.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.11
Current Work

 Make unravel run faster. Current version uses simple

algorithms that can be easily improved.

 Cosmetic user interface changes. E.g., Selecting variables: now global variables presented by le and locals

presented by procedure. Add list of all variables.

 Parsing C dialects complicated by new keywords or syntax.

 No semantic knowledge for libraries. Add display of call tree with slice information.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.12
Call Tree Example 1

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.13
Call Tree Example 2

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.14
Call Tree Example 3

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.15
Basic Unravel Design

Analyzer:

scanner &

parser

.LIF

.T/.H

Linker Map &

Slicer and

Interface

.K

.LOG

.T/.H

SYSTEM .LINK

.C.C .LIF

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 
Future Work

 Unravel is based on a FORTRAN slicing tool. We have

been requested to update the FORTRAN component

and integrate it into unravel.

 Add Java and C++.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.17
C++ Parsing

C++ is hard for many reasons, some that stand out to us:

 Exceptions are hard to slice and used more often in

C++ than signals in ANSI C.

 Templates must be expanded. In C we used the cpp to

expand macros.

 Pointer usage is much richer in C++ than C, e.g., pointers to functions more common.

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.18
Conclusions

In an initial evaluation an independent software reviewer

found:

 Unravel easy to use with little training.

 Simplied the task of extracting a computation for evaluation. Slices were much smaller than the original program. Slices were found quickly.

Down load by anonymous ftp from:

HISSA.NCSL.NIST.GOV

Web page: HTTP:HISSA.NCSL.NIST.GOV/UNRAVEL

Software Quality Week (May 28, 1997): Unravel (Created April 18, 1997) 1.19