Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LTL, CTL or TLA for modelling for my model (detailed description inside)?

I am currently writing my master thesis and am confronted with specifying and verifying my approach in a temporal logic.

Which temporal logic would be the best to use in my circumstances? I would really like some feedback on my approach and how to proceed

My model consists of participants, which will be executed concurrently. For each participant, one can register rules. They look something like this:

conditions -> action

e.g.

received(a, c) ^ received(b,c) -> allowed(c,d) 

which means that c has to have received a message from b and one from c in order to be allowed to send a message to d.

Before one of the participants sends or receives a message, my prototype checks if the participant is allowed to perform that action. So far, I want to verify that the algorithm does the following:

  1. If no rule exists whose conditions hold: forbid the action

  2. If a rule exists whose the conditions hold and it forbids the action: forbid the action

  3. If a rule exists whose conditions hold, it allows the action and no other rule exists whose condition holds and that forbids the action: allow the action

like image 715
nanoquack Avatar asked Mar 03 '14 12:03

nanoquack


People also ask

What is LTL and CTL?

CTL* is a superset of computational tree logic (CTL) and linear temporal logic (LTL). It freely combines path quantifiers and temporal operators. Like CTL, CTL* is a branching-time logic. The formal semantics of CTL* formulae are defined with respect to a given Kripke structure.

What is the difference between LTL and CTL in terms of modeling of time?

It would be more precise to say that LTL deals with linear-time, whereas CTL deals with branching time. Saying, in LTL you consider one future is like saying in CTL you consider one state. Satisfiability is defined this way. It's not about how many futures, but the structure of the future.

Can any LTL formula be specified by CTL?

No formula in LTL can define the language that is defined by the CTL formulas AG( p → (EXq ∧ EX¬q) ) or AG(EF(p)).

What are the various operators in model checking?

For simplicity, we use ∨, ∧, 〈R〉, [R], μ and v and as basic operators and assume that negations only occur in literals. Furthermore, we assume that in the formula to be checked each μ and υ quantification binds a different proposition variable.


2 Answers

It looks like that you want to find out if some properties of your specification are invariants. That is, if during the execution of the program the properties are always true.

The concept of invariant can be expressed in all the temporal logic formalisms. However, I would use TLA+ because there is a model checker, a proof system available, an active community, and a couple of excellent books for writing specifications.

But... be aware, Temporal Logic is not a piece of cake, and you will need to spend some quality time reading and thinking carefully.

like image 75
marcmagransdeabril Avatar answered Dec 26 '22 00:12

marcmagransdeabril


There is a misconception in comparing these three logics. The temporal logic in both TLA+ and LTL is linear. TLA+ includes set theory, and the axioms of TLA+ are based on Zermelo-Fraenkel set theory. TLA+ syntactically enforces stutter-invariance (for ensuring that refinement is practical). LTL is a propositional logic.

CTL is drastically different from LTL, because CTL is a branching time logic, whereas LTL a linear time logic. A single sequence is a model for a linear-time formula. In contrast, a tree is a model for a branching-time formula. A sequence represents a single execution, whereas a tree represents many executions, that start at some state.

Path quantification is available in CTL, whereas absent from LTL. There's a common subset of LTL and CTL, but they are incomparable (= some properties are expressible in LTL only, others in CTL only). CTL* is their common superset.

For the application that you sketch, linear-time semantics appears more suitable. I would recommend using TLA+, because it offers a good discipline for describing systems, and is temporally sufficiently expressive that you probably won't need LTL (the other way around: if you can't specify the system with a stutter-invariant formula in TLA+, then it's more likely that the system needs revision, rather than the full expressive power of LTL being necessary).

The TLA+ book is a very readable introduction.

like image 20
Ioannis Filippidis Avatar answered Dec 25 '22 22:12

Ioannis Filippidis