Telephonic communications – Diagnostic testing – malfunction indication – or electrical...
Reexamination Certificate
2000-07-13
2002-10-15
Tieu, Binh (Department: 2643)
Telephonic communications
Diagnostic testing, malfunction indication, or electrical...
C379S010030, C379S016000, C379S022000, C379S030000, C370S241000, C370S247000, C370S248000
Reexamination Certificate
active
06466646
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of verification of systems.
The systems to which the invention can be applied can be of very diverse kinds. They include in particular sequential or parallel data processing software, communication protocols, control and command systems, distributed systems, electronic components, etc. As a general rule, the invention is applicable to any physical system whose operation can be modelled in the form of communicating automata.
By “model” is meant an abstraction of the system enabling its operation to be parameterised. In the present instance, it is the translation of the system into the form of automata. The translation must of course preserve the properties of the system as much as possible, whilst allowing flexibility in respect of the verification methods employed.
The term “automaton” means a parametric representation of a part of the system, formed of states and transitions (i.e. of labelled points and arcs) enabling its operation to be described. An automaton can be described in various forms: graphically, textually, in the form of a data processing process, etc. A communicating automaton is an automaton which can exchange information with other automata in the form of sending of messages, synchronisations, etc.
In the context of the present invention, verification consists of demonstrating that the properties of the system as represented by automata are true or false, by exhibiting a path or by proving that a path cannot exist, a path being a succession (obviously a possible succession) of global states of the model. The path gives the ordered sequence of each state of each element of the model. In the present instance, this will be the ordered sequence of states of each automaton constituting the model.
It should be noted that as a general rule the verification is performed on a model and not on the system itself. In this respect it differs from testing, which is more directly related to the finished product. Testing consists of causing the real system to operate (for example the software to execute) to study its behaviour, attempting to cover its operation to the maximum. Many verification workshops enable the real system (the software) to be generated automatically from the model or its specifications to be defined. There is a relatively large number of modelling and verification aid tools (see, for example, A. A. Loureiro et al.: “Fdt tools for protocol development”, in FORTE'92, 1992).
In the field of verification. three types of methods are most often employed:
1. Simulation. Most existing tools enable simulation. It corresponds to running through the states of the model one after the other in accordance with a more or less sophisticated strategy, in order to look for pertinent paths. This method has the advantage that it can be used at any level of abstraction of the system (provided that the abstraction incorporates the path concept) and of being very flexible in use. It has two drawbacks: it runs up against the combinatorial explosion of the number of states of the system (the deeper the search, the greater the number of paths), and it does not prove anything (not finding any path at depth n does not prove that there is none at depth n+1).
2. “Model-checking” (see A. Kerbrat: “Méthodes symboliques pour la vérification de processus communicants: étude et mise en oeuvre” [“Symbolic methods for verifying communicating processes: design and implementation”], PhD thesis, University Joseph Fourier, Grenoble, 1994, or K. L. McMillan: “Symbolic Model Checking”, Kluwer Academic Publishers, 1993). “Model-checking” methods require modelling of the system in the form of automata. The automata of such modelling are fused into a single automaton in which each state corresponds to a global state of the model. It is then possible to verify properties described in temporal logic on the global automaton. The advantage of this method lies in the richness of the temporal software, which enables a very large number of types of requests to be specified. It also facilitates simulation. However, it has the limitation of very quickly generating a global automat of gigantic size which as a general rule can therefore not be constructed, despite a number of techniques for reducing the size of the automaton (use of global automaton coding techniques, fabrication of a model of the global automaton with weaker properties, etc.).
3. Proof by theorems (see J.-R. Abrial: “The B-book”, Cambridge University Press, 1995, or B. Chetali: “Formal verification of concurrent programs: How to specify UNITY using the Larch Prover”, Technical report, INRIA, France, 1995). Here the model consists of a set of logic formulae which describe its basic properties. A new property to be verified being given in the form of a logical formula, a proof will consist of successive steps enabling the new logic formula to be obtained from logical formulae of the model and inference rules. This method has the advantage of producing true formal proofs. However, there are no good inference strategies at present and the computer is almost always reduced merely to solving the simple steps of the proof and leaving the hard parts to the human logicist.
In the field of Petri networks, it is known in the art to use optimisation methods employing linear programming to verify systems. However, linear programming is used only on very highly constrained models which therefore cannot be used to model real systems (see J. Esparza et al.: “A polynomial-time algorithm to decide liveness of bounded free choice nets”, Theoretical Computer Science, 102: 185-205, 1992), or to generate the set of invariants of the model studied (in particular the Fourier-Motzkin algorithm), which set is constructed without discernment and rapidly becomes of gigantic size.
More recently, the direct use of integer programming on a communicating automata model has been studied (see J. C. Corbett: “Automated Formal Analysis Methods for Concurrent and Real-Time Software”, PhD thesis, Department of Computer Science, University of Massachusetts, USA, 1992). However, using integer programming does not provide sufficient algorithms and most importantly cannot perform proofs on the model. This research team studied the power of expressivity of the request system in depth and deduced that it was very close to temporal logic.
Another use of linear programming in the field of verification is described by J. L. Lambert (“Présentation du projet validation de protocoles par programmation linéaire” [“Description of the protocol validation by linear programming project”], Technical Report 27, Greyc, University of Caen, 1994). This approach does not involve any concept of ordering messages, which constitutes a limitation on the operating conditions of the system which can be analysed.
The object of the present invention is to enrich verification techniques by proposing a method that is capable of proving properties of the system studied and whose complexity does not increase too dramatically with the size of the system.
SUMMARY OF THE INVENTION
The invention therefore proposes a method of verifying the operation of a system modelled by a system of automata synchronised by a set of messages, including the following operations:
breaking down the system into N subsystems numbered from n=1 to n=N;
providing parameters describing each subsystem n (1≦n≦N) in the form of a respective automaton composed of a set E
n
of states e
n
i
of the subsystem n with a set A
n
of transitions a
n
j
between pairs of states of the set E
n
, each transition a of the set A
n
j
being associated with a subset M
n
j
of the set of synchronisation messages to translate the fact that each message of the subset M
n
j
arises when the subsystem described changes state in accordance with the transition a
n
j
;
constructing a system of linear equations including, for 1≦t≦T and 1≦n≦N, on the one hand flow equations of the form:
e
n
i
(
t
-
1
)
=
∑
j
&Elemen
Broult Christophe
Dellacherie Samuel
Devulder Samuel
Lambert Jean-Luc
Marshall Gerstein & Borun.
Tieu Binh
Valiosys
LandOfFree
Method for verifying the proper functioning of a 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 for verifying the proper functioning of a system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for verifying the proper functioning of a system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2946717