Slide Index

NPIC & HMIT (May 8, 1996):

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

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

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

Problems in Software Safety Evaluation ::::::::::::::::::::::::::::::::::::::::::::: 1.3Program 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.11

12 slides

April 11, 1996

1

UNIT 1

Unravel

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.0
Unravel

USING A PROGRAM SLICING CASE TOOL FOR

EVALUATING HIGH INTEGRITY SOFTWARE

SYSTEMS

Leo Beltracchi LXB@NRC.GOV

James R. Lyle JLYLE@NIST.GOV

Dolores R. Wallace DWALLACE@NIST.GOV

Nuclear Plant Instrumentation, Control, and

Human-Machine Interface Technologies

May 6-9, 1996 at The Nittany Lion Inn,

The Pennsylvania State University

Version 1.5

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.1
Talk Outline

 Problem Introduction Program Slicing Unravel Design Results Using Unravel

 Unravel Demonstration

 Functional Analysis Testing the Slice

 Conclusions

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.2
Problems in Software Safety Evaluation

 Need to nd software faults (bugs) quickly. Need to identify existence of common code. Need to identify impact of a code change. Need to connect inputs (e.g. a sensor signal) to outputs

(e.g. trip signal).

 Need to unravel code to conrm that dierent algorithms achieve the same function. All of the above are variations on the theme:

Need to understand an existing program.

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 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 still computing the same value for vat statement n.

 Data{
ow analysis is used to identify statements that

may be deleted without aecting the computation.

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 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 slice minus a backbone slice gives the statements

unique to a computation (program dice).

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 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

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 
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

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.7
Slices on Output 1 and Output 2

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.8
Combined Slices on Output 1 and Output 2

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.9
Using Unravel on Sample Code

Unravel was tried on sample safety system code, generated by an NRC sta person.

 Allowed auditor to extract a computation for manual

examination

 Found questionable sharing of code

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 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 (90 percent for the safetysystem example).

(5) Requested slices were computed is less than one minute.

NPIC & HMIT (May 8, 1996): Unravel (Created April 11, 1996) 1.11