System for determining a total error description of at least one part of a computer program

A section of a computer program is used to ascertain a control flow description and a data flow description, and program elements are selected from the section of the computer program. For each selected program element, a stored fault description associated with a respective reference element is used to ascertain an element fault description which describes possible faults in the respective program element. The element fault descriptions are used to ascertain the overall fault description, taking into account the control flow description and the data flow description.

CROSS REFERENCE TO RELATED APPLICATIONS

This application is based on and hereby claims priority to German Patent Application No. 19925239.4 filed on Jun. 2, 2001, the contents of which are hereby incorporated by reference.

REFERENCE TO COMPUTER PROGRAM LISTING, COMPACT DISC APPENDIX

A compact disc is included herewith and incorporated by reference herein having thereon a computer program listing appendix in the ASCII uncompressed text format with ASCII carriage return, ASCII line feed and all control codes defined in ASCII, having computer compatibility with IBM PC/XT/AT or compatibles, having operating system compatibility with MS-Windows and including file PROGRA˜6.TXT (Program-Listing.txt in Windows) of 130,121 bytes, created on Nov. 29, 2001.

BACKGROUND OF THE INVENTION

The invention relates to a method and a system for ascertaining an overall fault description for at least one section of a computer program, and also to a computer product and a computer-readable storage medium.

Such a method and such a system are known from N. Leveson, “Safety Verification of ADA Programs Using Software Fault Trees”, IEEE Software, July 1991, pages 48–59, which discloses the practice of using computers to ascertain an overall fault description in the form of an overall fault tree for a computer program. For the computer program, a control flow description is ascertained in the form of a control flow graph. For various program elements of the computer program, a stored fault description associated with a respective stored reference element is used to ascertain an element fault description. The fault description for a reference element describes possible faults in the respective reference element. The element fault descriptions in the form of element fault trees are used to ascertain the overall fault description, taking into account the control flow graph for the computer program.

The method and the system taught by Leveson have the following drawbacks, in particular. The overall fault tree ascertained is incomplete in terms of the faults examined and the causes thereof, and is therefore unreliable. Hence, this practice is not appropriate for use within the context of generating fault trees for a computer program for safety-critical applications. The individual fault trees associated with the reference elements are also incomplete and hence unreliable.

M. Weiser, “Program Slicing”, in IEEE Transaction on Software Engineering, Vol. 10, No. 4, July 1984, pp. 352–357 provides an overview of “slicing”. Slicing is the analysis carried out when searching for causes of incorrect action in a computer program. This procedure involves checking whether the incorrect action has been caused by an instruction currently under consideration. If this is not the case, the instructions which deliver data for or control the execution of the instruction are checked. This method is continued until no further operations exist, that is to say it gets to input data for the computer program. In slicing, “slices” are ascertained. A slice shows which instructions are affected in what way by a value under consideration. Below, the term slicing is always understood to mean backwardly directed slicing.

P. Liggesmeyer, Modultest und Modulverifikation—State of the Art, Mannheim, Vienna, Zurich: BI Wissenschaftsverlag, 1990 discloses the practice of ascertaining a control flow description and a data flow description for a computer program. In Liggesmeyer, this representation is used as an initial basis for “data-flow-oriented testing” of the computer program. The instructions (nodes) of the control flow graph are assigned data flow attributes (data flow description) which describe the nature of the data access operations contained in the instructions of the computer program. A distinction is drawn between write access operations and read access operations. Write access operations are referred to as definitions (def). Read access operations are referred to as a reference. If a read access operation takes place in a decision, this access operation is referred to as a predicative reference (p-use, predicate use). A read access operation during calculation of a value is referred to as a computational reference (c-use, computational use).

DIN 25424-1: Fehlerbaumanalysen; Methoden und Bildzeichen, September 1981, which has a title that can be translated “Fault Tree Analyses; Methods and Graphic Symbols”, discloses principles relating to a fault tree. A fault tree is to be understood, as described in DIN 25424-1, to mean a structure which describes logical relationships between input variables for the fault tree which lead to a prescribed undesirable event.

SUMMARY OF THE INVENTION

The invention is based on the problem of ascertaining an overall fault description which is more reliable than ascertaining an overall fault tree in the manner known on the basis of the method taught by Leveson.

In a method for ascertaining an overall fault description for at least one section of a computer program, using a computer, at least the section of the computer program is stored. A control flow description and a data flow description are ascertained for the section of the computer program, and program elements are selected from the section of the computer program. For each selected program element, a stored fault description is used to ascertain an element fault description. The fault description is associated with a respective reference element. The element fault description describes possible faults in the respective program element. A fault description for a reference element describes possible faults in the respective reference element. The element fault descriptions are used to ascertain the overall fault description, which takes into account the control flow description and the data flow description.

A system for ascertaining an overall fault description for at least one section of a computer program has a processor which is set up such that the following method steps can be carried out:at least the section of the computer program is stored,a control flow description and a data flow description are ascertained for the section of the computer program,program elements are selected from the section of the computer program,for each selected program element, a stored fault description associated with a respective reference element is used to ascertain an element fault description which describes possible faults in the respective program element,a fault description for a reference element describes possible faults in the respective reference element,the element fault descriptions are used to ascertain the overall fault description, taking into account the control flow description and the data flow description.

A computer program product comprises a computer-readable storage medium on which a program is stored which, when it has been loaded into a memory in a computer, allows the computer to carry out the following steps for ascertaining an overall fault description for at least one section of a computer program:at least the section of the computer program is stored,a control flow description and a data flow description are ascertained for the section of the computer program,program elements are selected from the section of the computer program,for each selected program element, a stored fault description associated with a respective reference element is used to ascertain an element fault description which describes possible faults in the respective program element,a fault description for a reference element describes possible faults in the respective reference element,the element fault descriptions are used to ascertain the overall fault description, taking into account the control flow description and the data flow description.

A computer-readable storage medium stores a program which, when it has been loaded into a memory in a computer, allows the computer to carry out the following steps for ascertaining an overall fault description for at least one section of a computer program:at least the section of the computer program is stored,a control flow description and a data flow description are ascertained for the section of the computer program,program elements are selected from the section of the computer program,for each selected program element, a stored fault description associated with a respective reference element is used to ascertain an element fault description which describes possible faults in the respective program element,a fault description for a reference element describes possible faults in the respective reference element,the element fault descriptions are used to ascertain the overall fault description, taking into account the control flow description and the data flow description.

The invention now makes it possible to ascertain a reliable overall fault description, which takes into account the peculiarities of a computer program, for a computer program or a section thereof. Since the overall fault description ascertained is much more reliable than the overall fault description which can be ascertained on the basis of the method taught by Leveson, the invention is also suitable for safety-critical applications, i.e. in particular for ascertaining an overall fault description for a safety-critical computer program.

The control flow description and/or the data flow description may be in the form of a control flow graph or of a data flow graph, respectively.

The fault description may be in the form of a stored fault tree, and the element fault description can be ascertained as an element fault tree. In this case, the overall fault description can be ascertained as an overall fault tree. This development permits standardized representation of a fault description, which makes it much simpler for a user of the fault description to analyze same.

In one development, the overall fault description can be used for fault analysis in the section of the computer program. This development has the advantage, in particular, that automated, reliable fault analysis becomes possible, and if the fault descriptions are in the form of fault trees the fault description can even be analyzed in a manner “normalized” in accordance with the fault tree analysis methods.

In another refinement, the overall fault description is ascertained as an overall fault tree, and the overall fault tree is altered in terms of prescribable boundary conditions. The alteration can be made by adding a complementary fault tree.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 1shows a computer100used to carry out the method described below. The computer100has a processor101which is connected to a memory102via a bus103. The bus103also has an input/output interface106connected to it.

The memory102stores a computer program104for which an overall fault description is ascertained in the manner described below. In addition, the memory102stores a program105which implements the method described below. The memory also stores fault descriptions115for different reference elements of a computer program. A fault description for a reference element describes possible faults in the respective reference element. Various reference elements and fault descriptions associated with the reference elements are explained in detail below.

The input/output interface106has a keyboard108connected to it via a first connection107. A second connection109is used to connect the input/output interface106to a computer mouse110, and a third connection111is used to connect the input/output interface106to a screen112on which the overall fault description ascertained for the computer program104is displayed. A fourth connection113is used to connect the input/output interface106to an external storage medium114.

FIG. 2shows a block diagram illustrating the procedure in accordance with the exemplary embodiment described below.

The stored computer program104is used to ascertain a control flow graph201and a data flow graph202for the computer program104.

Individual program elements are selected from the computer program (step203). For each program element selected, a stored fault description associated with a reference element corresponding to the selected program element is used to ascertain an element fault description (step204). The element fault description describes possible faults in the respective selected program element.

On the basis of a fault event in the computer program (undesirable event), which fault event is prescribed by a user and needs to be examined, in a final step (step205) an overall fault description for the computer program is ascertained, for the fault instance to be examined, from the element fault descriptions, taking into account the control flow graph and the data flow graph. The overall fault tree ascertained is displayed to the user on the screen112.

FIG. 3shows the basic procedure for creating a fault tree, as used in the initial example in order to form the fault trees described below for the reference elements.

For an event301selected by a user, it is necessary to ascertain how the selected incorrect event can arise. In a computer program, incorrect output of a variable, as a selected incorrect event (undesirable event)301, can be caused by a control flow fault303and/or a data fault304(INCLUSIVE-OR function302).

A control flow fault303is to be understood to mean incorrect control of the processing of the respective variable.

The data flow fault304is to be understood to mean a fault which arises during processing as a result of incorrect data. The data flow fault304may originate in the processing step currently under consideration (block306) and/or it may already have been present and may be maintained only by fault propagation (block307) (INCLUSIVE-OR function305).

On the basis of these considerations, the appropriate fault tree, a slice describing the instruction and a control flow graph are respectively illustrated below for the following elements of a computer program:an instruction sequence,a selection element,a loop element.

Instruction Sequence

The instruction sequence401comprises the three instructions shown inFIG. 4a. In a first instruction402, a first variable j is assigned the value 3 (j:=3). A second instruction403assigns a second variable k the value 2 (k:=2). A third instruction404forms a sum using the first variable and the second variable (i:=j+k).

In accordance with the practice disclosed in Weiser, a slice410is formed for this instruction sequence401, as shown inFIG. 4b. The first instruction402and the second instruction403both affect the third instruction404, which is illustrated by two arrows411,412in the slice410.

For the control flow graph401, the fault tree420shown inFIG. 4cis obtained for the following prescribed undesirable event421: “Variable i is incorrect after the third instruction”.

The incorrect event421may have been produced by a fault in the third instruction404under consideration itself, if the data up to this instruction step were correct (element422inFIG. 4c). The incorrect event421may also be caused by corrupt input data for the third instruction, however, i.e. as a result of INCLUSIVE-ORing424the events that the second variable k was incorrect after the second instruction (element425) and/or that the first variable j was incorrect after the first instruction402(element426). The result of the first INCLUSIVE-ORed function424is INCLUSIVE-ORed with the event that the third instruction is incorrect (INCLUSIVE-OR function423).

Selection Element

With a selection element as reference element, it is necessary to consider possibilities of fault in the data flows and in the control flows within the computer program.

FIGS. 5ato5cshow a control flow graph501(cf.FIG. 5a), a slice520(cf.FIG. 5b) and a fault tree540(cf.FIG. 5c) for an If-Then-Else instruction as a selection element. The control flow graph501comprises the following six instructions:a first instruction502, which assigns a first variable j the value 3 (j:=3),a second instruction503, which assigns a second variable k a prescribable value (k:= . . . ),a third instruction504, which checks whether the second variable k has a value greater than 0; if the value of the second variable is greater than 0, the instruction branches to a fourth instruction505, otherwise it branches to a fifth instruction506,the fourth instruction505, which assigns a third variable i the value of the second variable k (i:=k),a fifth instruction506, which assigns the third variable i the value of the second variable k with a negative arithmetic sign (i:=−k),a sixth instruction507, which processes the third variable i further in an arbitrary manner.

For the control flow graph501shown inFIG. 5a, the slice520shown inFIG. 5bis obtained for the selection element. Solid edges in the slice520show a data dependency between the different instructions. Dashed edges indicate control dependencies between the appropriate instructions.

The following definitions apply for the two edge types:dashed edges, referred to as control edges below, are directed from instructions which contain a predicative reference (failure constructs, loop control) to the directly controlled instructions, i.e. to those instructions which are executed only if the predicate has a particular value. Control edges are drawn only between the controlling instruction and directly interleaved instructions. If a controlled block contains a further interleaved control level, no control edges crossing more than one level are drawn. Since a control relationship is transitive, this indirect control can be inferred from the slice by utilizing the transitivity.solid edges, referred to as data flow edges below, are directed from instructions in which a variable is defined to instructions in which this variable is referenced. The variable under consideration cannot be defined again between the definition and the reference. This is referred to as a definition-free path for the variable under consideration.

The slice is ascertained by searching the control flow graph, counter to the edge direction, for a definition of the variable under consideration starting from the instruction containing the variable under consideration, for which the undesirable event is prescribed. If computational references exist for the definition, the method is continued recursively until no further additional nodes are found. The dependencies found in this way between instructions are data dependencies. If a node under consideration is contained in a block whose execution is controlled directly by a decision, this represents a control dependency. For the predicative references of the variables involved in the decision, nodes with appropriate definitions—that is to say data flow dependencies—are recursively sought which have other control dependencies.

FIG. 5bshows the failure element's associated slice520with corresponding control edges and data flow edges.

FIG. 5cshows the fault tree540for the prescribed event “the third variable i is incorrect before the 6th instruction”541.

The following events result in the incorrect event541when INCLUSIVE-ORed542:ANDing543the events that the decision in accordance with the third instruction504is true (element544) and a result of INCLUSIVE-ORing545the events that the fourth instruction505is incorrect (element546) and/or the first variable j is incorrect after the first instruction502(element547);ANDing550the events that the decision in accordance with the third instruction504is false (element551) and a result of INCLUSIVE-ORing552the events that the fifth instruction is incorrect (element553) and/or that the first variable j is incorrect after the first instruction502(element554);INCLUSIVE-ORing560the following events: the decision in accordance with the third instruction504is incorrect (element561) and/or the second variable k is incorrect after the second instruction503(element562).

Multiple Selection Element

A multiple selection element as reference element can be handled in accordance with the scheme described above by breaking down the multiple selection into a cascade of two-way selection elements processed in accordance with the procedure above, in order thus to ascertain a fault tree for a multiple selection element.

FIGS. 6ato6cshow a fault tree601(cf.FIG. 6a), the corresponding slice620(cf.FIG. 6b) and the associated fault tree640(cf.FIG. 6c) for the reference element of a loop. The control flow graph601for a loop element comprises the following seven instructions:a first instruction602, which assigns a first variable i the value 0 (i:=0),a second instruction603, which assigns a second variable j an unspecified value (j:= . . . ),a third instruction604, which prescribes a further unspecified value for a third variable k (k:= . . . ),a fourth instruction605, which, as a loop instruction, specifies a condition that a fifth instruction and a sixth instruction are executed until the value of the second variable is j>0 (WHILE j>0 DO),a fifth instruction606, which assigns the first variable i a value which is obtained from the sum of the previous value of the first variable and the product of the second variable and the third variable (i:=i+k*j),a sixth instruction607, which assigns the second variable j a value which is obtained by decreasing the original value of the second variable j by the value 1 (j:=j−1),a seventh instruction608, which processes the first variable i further in a prescribable manner ( . . . :=i . . . ).

FIG. 6bshows the corresponding slice620for the control flow graph601shown inFIG. 6awith associated control flow edges and data flow edges. The fault tree640shown inFIG. 6cis formed for the prescribed event641that the “first variable i is incorrect before the seventh instruction”.

The fault tree640is obtained by INCLUSIVE-ORing642the following four events:a first event643, which describes a situation in which the first variable i is incorrect after the first instruction602,ANDing644the events that the loop body has been passed through at least twice (element645) and the event that the sixth instruction607is incorrect (646),ANDing650the event that the loop body has been executed at least once (element651) and INCLUSIVE-ORing652of the following four events:a) the fifth instruction606is incorrect (element653),b) the first variable i is incorrect after the first instruction (element654),c) the second variable j is incorrect after the second instruction (element655),d) the third variable k is incorrect after the third instruction (element656),INCLUSIVE-ORing660the following three events:e) the decision in accordance with the fourth instruction605is incorrect (element661),f) the second variable j is incorrect after the second instruction603(element662),g) ANDing663the events that the sixth instruction is incorrect (element664) and the event that the loop body has been passed through at least once (element665).

The fault trees described above, which are associated with the individual reference elements, are stored in the memory102as fault trees115.

FIG. 7shows a control flow graph700for the following computer program:

For the control flow graph700comprising 13 instructions (reference symbols 1, 2, 3, . . . , 13) which is shown inFIG. 7,FIG. 8ashows the associated slice800for the variable max andFIG. 8bshows the associated slice810for the variable avr. The numbering of the individual instructions in the slices corresponds to the numbering of the individual instructions in the control flow graph700fromFIG. 7.

FIG. 9shows the slice900for the variable avr, as shown inFIG. 8b. The structure of the loop element contained in the program shown above is highlighted in bold. This structure corresponds to the slice shown inFIG. 6bfor a loop element.

An overall fault tree1000for the computer program shown above is shown inFIG. 10. The overall fault tree for the computer program is produced by instantiating the appropriate fault tree associated with the reference element which corresponds to the selected program element.

By starting from the prescribed undesirable event and working backward, the overall fault tree1000is thus ascertained using the fault trees associated with the reference elements.

FIG. 10contains the fault tree1000relating to the event that “the variable avr is incorrect before the thirteenth instruction” (element1001). The variable avr may be incorrect before the thirteenth instruction13on account of at least one of the following three events, as is also shown in the slice900shown inFIG. 9for the variable avr (INCLUSIVE-OR function1002):an input variable n is incorrect after the first instruction1(element1003),the eleventh instruction11is incorrect (element1004),the value of the variable sum is incorrect before the eleventh instruction11(element1005).

The variable sum is incorrect before the eleventh instruction11(element1005) if at least one of the following events is satisfied (INCLUSIVE-OR function1006):the variable sum is incorrect after the fourth instruction4(element1007),ANDing1008the event that the loop body has been executed at least twice (element1009) and the event that the tenth instruction10is incorrect (element1010),ANDing1011the event that the loop body has been executed at least once (element1012) and the result of INCLUSIVE-ORing1013the following four events:a) the ninth instruction9is incorrect (element1014),b) the variable sum is incorrect after the fourth instruction4(element1015),c) the variable i is incorrect after the fifth instruction5(element1016),d) the variable a is incorrect after the second instruction2(element1017),INCLUSIVE-ORing1018the following events:e) the decision in accordance with the sixth instruction is incorrect (element1019),f) the variable i is incorrect after the fifth instruction (element1020),g) the variable n is incorrect after the first instruction (element1021),h) ANDing1022the event that the 10th instruction is incorrect (element1023) and the event that the loop body has been executed at least once (element1024).

To provide for clearer illustration, the fault tree1000fromFIG. 10is altered such that events shown a plurality of times in the fault tree1000are combined to form one node of a cause-effect graph1100(cf.FIG. 11).

The fault tree1000shown inFIG. 10is subjected to a fault tree analysis method, as described in DIN 25424-2, which analyzes an analysis of the computer program for a prescribed undesirable event.

The text below illustrates alternatives and further opportunities for application of the exemplary embodiment described above.

The overall fault tree produced using the method described above can be used for various purposes:description of the fault generation or propagation of incorrect action by a section of a computer program within the context of safety analysis or reliability analysis for the computer program,analysis of software fault mechanisms, for example within the context of test case generation.

The invention has been described in detail with particular reference to preferred embodiments thereof and examples, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention.