Abstract:
A method for storing and propagating error information in computer programs, in which a globally valid error variable is used for storing and propagating the error information, wherein for each recognized error a nonzero value for the error is added to the error variable as error information with a respective stipulated arithmetic sign, and wherein the value is formed from a discrepancy in the content of a coded variable from an expected value. This combination and integration of a separate global propagation variable with values derived from an error, particularly by virtue of detected discrepancies in the known error recognition and propagation paths using operations and operands in “coded processing”, achieves an increased propagation certainty.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The invention relates to a method for storing and propagating error information in computer programs. 
         [0003]    2. Description of the Related Art 
         [0004]    In safety-oriented programs for industrial applications, that are typically executed on embedded hardware, such as programmable logic controllers (PLCs) including a processor or other type of computational unit, it is necessary to ensure that the error information spotted during program execution is safely retained up to the end of the program run or up to the end of a cycle so that the routines for error reactions that are executed at the end of the program run or cycle are initiated with certainty. The storage and retention of the error information up to the end of the program is referred to generally as error propagation. 
         [0005]    Important variables are processed in coded form in the safety-oriented programs, where this process is also called “coded processing”. To this end, values (xf) are coded in variables via AN, ANB (AN+B), ANBD codes or by related codes (hybrid method). In this case, all numerical variables are coded on the basis of a rule in the form 
         [0000]      Eq. (1) 
         [0000]        x   c   =A *xf+ B _x+ D,    
         [0006]    and the arithmetic operations (+, *, /, etc.) are customized such that the processing in the coded range (xc) delivers consistent results for the Ur range (xf) (in this case, it is entirely possible for B_x or D also to have the value zero). 
         [0007]    The coded variable can be used to detect errors arise as a result of a random change or corruption of individual bits, for example. This means that the values to be coded are mapped onto coded values such that a discrepancy in individual bits can be recognized by virtue of errors in individual bits allowing the production of invalid values in the coded space, for example, on account of the Hamming distance between admissible coded values. Here, it is also possible for double storage and processing of the values, i.e., once in coded form and once in uncoded form, to occur, with the respective verification involving the value being extracted from the coded variable and being compared with the value managed in uncoded form. 
         [0008]    A program run is verified in the conventional systems by using run variables, known as “tracers”, the content of which can be used to log and hence check the program path taken. 
         [0009]    Thus, while numerous known approaches exist for the recognition of errors, the failsafe formation of an error variable and the propagation thereof are not trivial. By way of example, there is no possibility of adding a constant to an error variable, etc., for every error or alternatively in every case of nonerror because such standard steps can be optimized, i.e., combined, for example, by compilers, which reduces the certainty. 
       SUMMARY OF THE INVENTION 
       [0010]    It is therefore an object of the present invention to provide a method for failsafe propagation of errors in computer programs. 
         [0011]    This and other objects and advantages are achieved in accordance with the invention by a method for storing and propagating error information in computer programs, in which a globally valid error variable is used for storing and propagating the error information, where for each recognized error a nonzero value for the error is added to the error variable as error information with a respective stipulated arithmetic sign, and where the value is formed from a discrepancy in the content of a coded variable from an expected value. This combination and integration of a separate global propagation variable with values derived from an error, particularly by virtue of detected discrepancies in the known error recognition and propagation paths using operations and operands in “coded processing”, achieves increased propagation certainty. 
         [0012]    It is an essential concept of the way in which the invention achieves the object that a container used for the error propagation is an error variable, the content of which is formed such that corruption can be recognized and that the effect of different independent errors cannot result in reciprocal compensation. The invention achieves this by virtue of the error information with a stipulated arithmetic sign being propagated in the error variable. A further protection, particularly against systematic errors and against untransparent and unwanted optimizations in a compiler, etc., is achieved by virtue of the invention deriving the value that enters the propagation variable from the error, i.e., the absolute value discrepancy from a target condition. 
         [0013]    Errors become easily recognizable, for example, in the case of the “random” corruption of variables, when the coded variable is coded by AN or AN+B or ANBD coding or by a hybrid form comprising these codings. 
         [0014]    Besides the propagation of errors in variables and values, the method can advantageously also be used for verifying a program run or the like by virtue of the error variable being divided into at least an upper bit range and a lower bit range, where the value is summed in the lower bit range each time, and where a check value is summed in the upper bit range. In this case, advantageously the check value used is the expected value or the check value is at least formed from the expected value. 
         [0015]    Further protection against systematic errors is obtained particularly for failsafe programs in industrial automation engineering when the computer program comprises at least one cyclically executed procedure, where the error variable is initialized with a starting value at the beginning of a cycle, and where different starting values are used for different cycles. In this case, the aim in one advantageous embodiment is for the stipulated arithmetic sign not to be changed at least for the duration of one cycle. 
         [0016]    The error variable is evaluated and hence an error event is recognized by advantageously comparing the content of the error variable with an expected value for the content of the error variable. 
         [0017]    Fast and arithmetically simple processing is obtained when the value is formed by logically combining the discrepancy in the content of the coded variable with the expected value via an XOR function. 
         [0018]    The method can advantageously be used to verify a program run by virtue of a signature being calculated and being added to the coded variable or being subtracted therefrom each time at least in an essential program portion when the essential program portion is executed, and by virtue of an expected value for the signature as intended for a proper program run being subtracted from the coded variable or added thereto, with the calculated signature and the expected value canceling one another out in the error-free case. Alternatively, the error can be propagated by using the addition (subtraction) of the calculated signature, and the expected value for the signature can be subtracted (added) also by using the error variable (propagation variable). 
         [0019]    It is also possible for simple errors recognized in the program itself to be propagated using the method by virtue of such errors being propagated by adding a constant, for example, and nonzero value to the error variable or subtracting it therefrom each time. 
         [0020]    Other objects and features of the present invention will become apparent from the following detailed description considered in conjunction with the accompanying drawings. It is to be understood, however, that the drawings are designed solely for purposes of illustration and not as a definition of the limits of the invention, for which reference should be made to the appended claims. It should be further understood that the drawings are not necessarily drawn to scale and that, unless otherwise indicated, they are merely intended to conceptually illustrate the structures and procedures described herein. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0021]    An exemplary embodiment of the method according to the invention will be explained below; the variants discussed in this context can also be implemented in combination with one another. 
           [0022]    The FIGURE is a flowchart of the method in according with the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0023]    A propagation variable is intended to be considered as a coded variable P which is initialized in a suitable manner at the beginning of a program run and which is used to hold the results of consistency checks on a coded useful variable x c  during the program execution: 
         [0000]      Eq. (1) 
         [0000]      x c   =A *xf+ B _x+ D    
         [0024]    In this case, A, B_x and D are constants at least for one program cycle. For A, a high prime number is advantageously used, because this allows the use of the modulo operation for recognizing errors. 
         [0025]    An error is thus present in recognizable form (in simplified terms) when the content of the variable x c  is discernibly different from the form (1), i.e., when the following applies: 
         [0000]        X   F =( x   c   −D ) modulo  A≠B _x 
         [0026]    Without loss of generality, x F ≧0 applies (e.g., as a result of the use of the relevant modulo command from the arithmetic and logic unit). 
         [0027]    In this case, B_x is the expected value, i.e., the value of the modulo operation in the error-free case. Discrepancies from B_x can therefore be considered to be errors. 
         [0028]    In a program run or in a cycle of a program, the error is then frequently present both in positive and negative form and in many ways in alienated form. The mere addition (alternatively: mere subtraction) of the error-containing values could therefore often result in loss of the recognizability of errors. The method prevents this loss by stipulating in advance the direction (positive or negative) in which and with how many bits an error is permitted to have an effect. 
         [0029]    The first value for the recognizability is a random value x F  between 0 and A. x F −B_x may therefore be either positive or negative. Since only the recognizability of an error is of interest, however, the XOR function is simply used instead of the subtraction: 
         [0030]    xF=B_x: xF XOR B_x=0 applies (error-free case) 
         [0031]    xF≠B_x: xF XOR B_x&gt;0 applies (since xF≧0 and B_x&gt;0) 
         [0032]    and 
         [0033]    xF XOR B_x&lt;2̂n applies when A&lt;2̂n 
         [0034]    If an error is now propagated both in its positive form and in its negative form, two positive values are added. The sum of two positive values is always not equal to zero. A compensation can therefore be provided only by an overflow in the numerical ring of the arithmetic and logic unit. There should therefore be sufficient upper bits available. 
         [0035]    The results of such consistency checks using the described “modulo” operation are in this case meant to be transferred at regular check points (e.g., after every coded operation) such that unintentional compensation for error information that is already present is avoided. This is achieved by the described additive (alternative: subtractive) cumulation of error information with a positive arithmetic sign. 
         [0036]    The following describes an example of the propagation in a 32-bit value P with the use of 16-bit signatures: 
         [0000]      Eq. (2) 
         [0000]        x   F =( x   c   −D ) mod  A    
         [0037]    The expected value for x F  is B x . The error information corresponds to the difference between x F  and B x . 
         [0000]      Eq. (3) 
         [0000]        x   P =( x   F  &amp; 2 16 −1) XOR ( B   x ·(2 16 +1))
 
         [0038]    In this case, the later addition (alternatively: subtraction) involves the value B x  being shifted to the upper 16 bits as a check value; this can be used to verify the program run, for example, by verifying whether the number of check processes corresponds to an expected value. 
         [0039]    In principle, it is necessary to ensure that the error information (the difference between the expected value for x F  and x F ) always enters the propagation in positive form (or alternatively always in negative form) so that compensation effects are precluded. 
         [0040]    Coding rule (1) means that the following applies in the error-free case: 
         [0000]      Eq. (4) 
         [0000]        x   P   =B   x ·2 16  
 
         [0041]    For every operation, the error information (3) is formed and is added to the propagation variable P, with the result that 
         [0000]    
       
         
           
             
               
                 
                   P 
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       OpNumber 
                     
                      
                     
                       x 
                       
                         P 
                         , 
                         i 
                       
                     
                   
                 
               
               
                 
                   Eq 
                   . 
                   
                       
                   
                    
                   
                     ( 
                     5 
                     ) 
                   
                 
               
             
           
         
       
     
         [0042]    At the end of the program cycle, the propagation variable P end  must correspond to a value Pe that is to be expected: 
         [0000]      Eq. (6) 
         [0000]      P end =P e    
         [0043]    The value to be expected can be ascertained by an encoder or compiler at the translation time and can therefore be checked in a final consistency check in the form (6). Hence, an additional propagation path over the already known propagation path to the coded output values is created. Furthermore, this mechanism reveals missing updates for the propagation variable P, as a result of which it is possible to implement program run verification. 
         [0044]    In one advantageous embodiment of the invention, error information x F  is propagated not upon every operation but rather only before operations that necessitate an increase propagation loss risk (such as multiplication, division). Chains of propagation-safe operations, such as addition, have sufficiently good propagation properties for most purposes, which means that it is possible to dispense with steps (3) and (5) until a propagation-critical operation is effected. This form results in improved performance in comparison with update of the propagation variable upon every operation. 
         [0045]    The propagation can advantageously be constantly corrected in the case of alternative procedures in a path. To this end, the difference in the expected values for the propagation variable at the end of the alternative path is added to the propagation variable. 
         [0046]    In one embodiment of the invention, the propagation variable is initialized dynamically at the beginning of each cycle, e.g. by virtue of initialization with the dynamic signature D. 
         [0047]    In a further embodiment of the invention, the arithmetic sign of the error information x P  is altered dynamically. The arithmetic sign can be altered only when the cycle changes (i.e., may be the same within each cycle), or alternatively can also be altered within a cycle, the latter case requiring precautions to be taken to ensure that unwanted compensation cannot occur, for example, as a result of interim evaluation of the propagation variable P as per Eq. (6). 
         [0048]    In advantageous embodiment, methods for error recognition can be combined with the previously described embodiments of the method for error propagation. In this regard, one advantageous embodiment allows the propagation of a calculated signature S in a suitable coded variable x c , with an explicit expected value Se existing for S: 
         [0000]    
       
      
       x 
       c 
       =x 
       c 
       −S 
       e 
       +S  
      
     
         [0049]    The presently contemplated embodiment can be used particularly advantageously for the program run protection, for example, by virtue of the signature S used being a program run variable (“tracer”) which, in the case of correct execution, is always assigned an explicit value for each basic block of a program. Combining the program run variable with the method for error propagation increases the effectiveness of the program run protection and simultaneously improves the system independence (compiler, operation system, hardware). 
         [0050]    Alternatively, it is possible for the calculated signature S or the program run variable to be propagated directly by means of the propagation variable P, with an explicit expected value S e  existing for S: 
         [0000]        P=P +(( S  mod A) XOR (( S   e  mod  A )*(2 16 −1))
 
         [0051]    Note: if the numerical range of S is greater than the desired numerical range for propagation, the numerical range can easily be reduced in size, e.g. as follows: 
         [0000]      S′=(S XOR X/2 16 ) AND (2 16 −1)
 
         [0052]    Finally, it is also possible for the propagation variable P to be influenced directly in order to “report” an error: 
         [0053]    IF (error) 
         [0054]    THEN 
         [0000]      P=P+1 
         [0055]    Instead of the addition, subtraction is then used for “negative error logic”. Instead of the constant “1”, it is also possible to add or subtract other values which then advantageously change a plurality of bits of the propagation variable. 
         [0056]    The Figure is a flowchart of a computer implemented method for storing and propagating error information in computer programs. The method comprises storing and propagating the error information via a globally valid error variable, as indicated in step  110 . Next, for each recognized error, a nonzero value for an error is added by the processor of the computer to the error variable as the error information with a respective stipulated arithmetic sign, as indicated in step  120 . Here, the nonzero value is formed from a discrepancy in a content of a coded variable from an expected value. 
         [0057]    While there have been shown, described and pointed out fundamental novel features of the invention as applied to a preferred embodiment thereof, it will be understood that various omissions and substitutions and changes in the form and details of the methods described and the devices illustrated, and in their operation, may be made by those skilled in the art without departing from the spirit of the invention. For example, it is expressly intended that all combinations of those method steps which perform substantially the same function in substantially the same way to achieve the same results are within the scope of the invention. Moreover, it should be recognized that method steps shown and/or described in connection with any disclosed form or embodiment of the invention may be incorporated in any other disclosed or described or suggested form or embodiment as a general matter of design choice. It is the intention, therefore, to be limited only as indicated by the scope of the claims appended hereto.