Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1998-07-17
2002-06-18
Frejd, Russell (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S022000, C716S030000
Reexamination Certificate
active
06408262
ABSTRACT:
FIELD OF THE ART
The invention relates to a method of analyzing a state based system model comprising a set of machines as stated in the independent claims
1
,
11
and
29
.
BACKGROUND OF THE INVENTION
When considering the fact that many product segments of the market tend to comprise an increasing amount of embedded software, and as the products within said segments tend to be differentiated more and more only by the performing differences of the embedded software rather than the utilized hardware, the future demands of software designs in general will vary greatly with respect to both the above-mentioned fault recognition and elimination and the short-term development deadlines.
One of many examples of relevance may be within the automotive industry. Even mass-produce cars tend to comprise an increasing number of dedicated microprocessors. The microprocessors may, e.g., be dedicated to control ABS, fuel injection, light control, different kinds of monitoring,, heat control, security systems, etc., and many of the different subsystems will often have to be controlled by a common protocol.
It is evident that the large, scale appearance of software-controlled units will cause increasing troubles to the system designers, as it may be difficult to overview every aspect of the possible state of each unit, and of course it may be even more complicated to keep track of the synergy between all the subsystems utilized. A further difficulty which should be mentioned is that most of the subsystems will be designed by different developers or groups of such, and that the interfaces between such subsystems may be difficult to control as no effective tools can be provided to the developers for the necessary analyses of such large-scale systems together or even in every single unit.
This may cause expensive and crucial delays with respect to the duration of the product development and releasing. It is even more crucial that some products may even be put on the market with inherent hidden errors which under certain unknown conditions, may be triggered and come to light.
This problem is of course really serious in safety critical systems where a defect or fault may even cause injury to persons affected by such a defect.
One way of testing such types of products is to check the logic design prior to the fabrication of a device through symbolic model checking. The technique has turned out to be very efficient for analyses and verification of hardware systems. However, it has not been clear whether model checking is an effective tool for other types of concurrent systems such as e.g. software systems.
One reason why symbolic model checking may not be as efficient is that software systems tend to be both larger and less regularly structured than hardware. For example, many of the results reported for verifying large hardware systems have been for linear structures like stacks or pipelines, for which it is known that the size of the transition relation when represented as a so-called ROBDD, Reduced Ordered Binary Decision Diagrams, grows linearly with the size of the system.
Another approach to this is described in U.S. Pat. No. 5,465,216 in which a method of automatic design verification is described. The described method basically accepts the fact that the formal verification suffers from a deficiency of “the state explosion problem”, and furthermore concludes that formal verification of very large systems are beyond the capabilities of the current formal verification techniques. Hence, the above-mentioned patent describes a way of decomposing and reducing the systeM model instead of dealing with the verification method. Consequently, a drawback of the described method is that the possibly obtainable results will only be partial and non-exhaustive.
A more promising technique, based on the above-mentioned ROBDDs, which also exploits the structure of the system is presented in W. Lee et al., Tearing based automatic abstraction for CTL model checking, 1996 IEEE/ACM International Conference on Computer-Aided Design, pages 76-81, San Jose, Calif., 1996 IEEE Comput. Soc. Press. This technique uses a partitioned transition relation, and a greedy heuristic is used to select subsets of the transition relation. For each chosen subset, a complete fixed point iteration is performed. If the formula cannot be proven after this iteration, a larger subset is chosen. In case of an invalid formula the alogrithm only terminates when the full transition relation has been constructed (or memory or time has been exhausted). A draw-back of the technique is that it uses a greedy strategy involving a fixed-point iteration for each of the remaining machines. If the system only has a single initial state, as is typical in embedded software systems. The greedy strategy reduces to selecting an arbitrary machine, thus involving extraneous fixed point iterations.
The present invention meets the requirement of both a formal verification and a use of an unreduced system model and provides the possibility of performing theoretical model “crash tests” in even very large-scale state based system models. Moreover, analyses and verification of the said models can be achieved in non-reduced models at a much higher rate than prior art analyses and verification tools.
SUMMARY OF THE INVENTION
When the method of analyzing a state based system model comprises a set of machines (M
1
, . . . ,Mn), said machines each comprising at least one: possible state (pS
1
Mi, . . . ,pSkMi) each machine being in one of its comprised states at any given time,
the dynamic behavior of said machines (M
1
, . . . ,Mn) being defined by predefined transitions between said states of each machine (M
1
, . . . ,Mn) and dependencies (D) between said machines (M
1
, . . . ,Mn),
initiating an initial set of at least one machine state (F) of said machines (M
1
, . . . ,Mn)
initiating a goal set of machine states (A) representing a condition on states of a subset of machines (MI), and repeating the following steps until the analyzing has terminated positively and/or if the subset of machines (MI) comprises all of said machines (M
1
, . . . ,Mn) expanding the goal set (A) with a set of states which via transitions can be brought into the previous goal set (A) independently of machines not included in (MI), if (A) comprises at least one of the set of states in the initial set of states (F) then terminating positively, otherwise expanding the subset of machines (MI) with at least a subset of the machines (M
1
, . . . ,Mn).
it is possible to obtain a very fast analysis of a state based system model.
Thus, according to the above, the invention deals with a dynamic expansion of a given investigated set of possible states A in a state based system model with the states within the currently investigated machine or set of machines. When the possible states A cannot be expanded any more, i.e. all states in the investigated machines are possible, or when the rest of the states are only possible if certain conditions in other machines is fulfilled, the number of investigated machines is increased and the set of possible states is expanded. This iterative process may continue until certain results are obtained. A desired result could for instance be a verification that a given machine state can be brought into the set of possible initial states A.
Specifically, the invention provides an accurate result when performing so-called reachability check, i.e. when verifying that a set of initial machine states can be brought into certain desired or undesired conditions.
Experimental results have shown that typical so-called reachability checks according to the invention can be performed considerably faster than prior art methods.
Moreover, according to the invention, it is now possible to analyze and verify system models comprising an extremely large number of machines, as no full calculation of all possible global state vectors has to be determined. This important aspect increases the possibility of creating very large state based systems, as a true model of the system can now be es
Andersen Henrik Reif
Behrmann Gerd
Hulgaard Henrik
Kristoffersen Kåre Jelling
Larsen Kim Guldstrand
Finnegan Henderson Farabow Garrett & Dunner LLP
Frejd Russell
IAR Systems A/S
LandOfFree
Method and an apparatus for analyzing a state based system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and an apparatus for analyzing a state based system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and an apparatus for analyzing a state based system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2979333