hgoes / gtl Goto Github PK

View Code? Open in Web Editor NEW

2.0 3.0 1.0 1.21 MB

The GALS Transformation Language

License: Other

Haskell 99.23% Emacs Lisp 0.77%

gtl's People

Contributors

Stargazers

Watchers

Forkers

tpolzer

gtl's Issues

Bounded model checking is broken.

The following example verifies correctly with -m native:

model[none] client() {
  input bool proceed;
  output enum { nc, acq, cs, rel } st;
  init st 'nc;
  // Basic behaviour
  automaton {
    init final state nc {
      st = 'nc;
      transition[proceed] cs;
      transition[!proceed] nc;
    }
    state cs {
      st = 'cs;
      transition rel;
      transition cs;
    }
    final state rel {
      st = 'rel;
      transition nc;
    }
  };
  // Constrained behaviour
  always (st = 'cs => next st = 'rel);
}

model[none] server() {
  input enum { nc, acq, cs, rel } procstate;
  output bool procout;
  init procout false;
}

instance client c0;

instance server s;

connect c0.st s.procstate;

connect s.procout c0.proceed;

verify {
  always (c0.st = 'cs => finally c0.st = 'rel);
}

$ gtl -m native min.gtl
--- Output ---
warning: for p.o. reduction to be valid the never claim must be stutter-invariant
(never claims generated from LTL formulae are stutter-invariant)

(Spin Version 6.2.5 -- 3 May 2013)
        + Partial Order Reduction

Full statespace search for:
        never claim             + (never_0)
        assertion violations    + (if within scope of claim)
        acceptance   cycles     + (fairness disabled)
        invalid end states      - (disabled by never claim)

State-vector 60 byte, depth reached 72, errors: 0
       47 states, stored (59 visited)
       60 states, matched
      119 transitions (= visited+matched)
      358 atomic steps
hash conflicts:         0 (resolved)

Stats on memory usage (in Megabytes):
    0.004       equivalent memory usage for states (stored*(State-vector + overhead))
    0.272       actual memory usage for states
  128.000       memory used for hash table (-w24)
    0.534       memory used for DFS stack (-m10000)
  128.730       total actual memory usage


unreached in proctype c0
        min.pr:220, state 190, "-end-"
        (1 of 190 states)
unreached in proctype s
        min.pr:273, state 49, "-end-"
        (1 of 49 states)
unreached in init
        (0 of 5 states)
unreached in claim never_0
        min.pr:309, state 20, "-end-"
        (1 of 20 states)

pan: elapsed time 0 seconds

No errors found.

But it fails to verify with bmc:

$ gtl -m smt_bmc min.gtl
fixme:heap:HeapSetInformation (nil) 1 (nil) 0
Depth: 1 (0.266067s)
Depth: 2 (0.267505s)
Depth: 3 (0.268852s)
Step 1 none
| c0.proceed = False
| c0.st = nc
| s.procout = False
| s.procstate = nc
| c0.automaton0 = nc
Step 2 none
| c0.proceed = True
| s.procout = True
Step 3 none
| c0.st = cs
| s.procstate = cs
| c0.automaton0 = cs
Step 4 (loop starts here) none

where obviously the step from 3 to 1 is invalid because it changes from cs to nc without rel

Adding time concepts

Verifying temporal formulas can be very useful when designing real-world GALS systems. It should be possible to declare a cycle time for models and use temporal constructs like "after 50ms, variable x has the value 50".
This would include implementing a scheduler that governs the execution of cycles of components.

Büchi determinization bug

The contract

always (x < y => always x < y)

produces a DFA which has too many transitions:

state fromList [0,1]
["x" < "y"] -> fromList [0,1]
["x" >= "y"] -> fromList [1]
initial state fromList [1]
["x" < "y"] -> fromList [0,1]
["x" >= "y"] -> fromList [1]

This doesn't happen if "x<y" is replaced by a boolean variable.

SPIN verification breaks when narrowing implementation contract

The following verifies fine with -m native:

model[NuSMV] client("impl.smv","client") {
  input bool proceed;
  output enum { nc, cs } st; 
  init st 'nc;
  // Basic behaviour
  automaton {
    init final state nc {
      st = 'nc;
      transition[proceed] cs; 
      transition nc; 
    }   
    final state cs {
      st = 'cs;
      transition nc; 
      transition cs; 
    }   
  };  
  // Constrained behaviour
  always (st = 'cs => (st = 'cs until[4cy] st = 'nc));
}

model[NuSMV] server("impl.smv","server") {
  input enum { nc, cs }^2 procstates;
  output bool^2 procouts;
  init procouts [false,false];
  always (procstates[1] != 'cs and procouts = [true,false])
         or (procouts = [false,false]);
}

instance client c0; 
instance client c1; 

instance server s;

connect c0.st s.procstates[0];
connect c1.st s.procstates[1];

connect s.procouts[0] c0.proceed;
connect s.procouts[1] c1.proceed;

verify {
  //liveness
  always (c0.st = 'cs => finally c0.st = 'nc);
}

while this fails:

model[NuSMV] client("impl.smv","client") {
  input bool proceed;
  output enum { nc, cs } st; 
  init st 'nc;
  // Basic behaviour
  automaton {
    init final state nc {
      st = 'nc;
      transition[proceed] cs; 
      transition nc; 
    }   
    final state cs {
      st = 'cs;
      transition nc; 
      transition cs; 
    }   
  };  
  // Constrained behaviour
  always (st = 'cs => (st = 'cs until[4cy] st = 'nc));
  always (st = 'nc) => ((next st = 'cs) => next next st = 'cs);
}

model[NuSMV] server("impl.smv","server") {
  input enum { nc, cs }^2 procstates;
  output bool^2 procouts;
  init procouts [false,false];
  always (procstates[1] != 'cs and procouts = [true,false])
         or (procouts = [false,false]);
}

instance client c0; 
instance client c1; 

instance server s;

connect c0.st s.procstates[0];
connect c1.st s.procstates[1];

connect s.procouts[0] c0.proceed;
connect s.procouts[1] c1.proceed;

verify {
  //liveness
  always (c0.st = 'cs => finally c0.st = 'nc);
}

Where the only difference is this line in the client contract:

always (st = 'nc) => ((next st = 'cs) => next next st = 'cs);

Since this only narrows down the number of valid traces for the client it cannot possibly invalidate the global goal.

Create UPPAAL verification target

As UPPAAL provides a state-based verification approach as well as temporal constructs, it would be interesting to see how it performs when compared to SPIN. This includes writing a code-generator for UPPAAL and translating GTL specifications to it.

BDD verification doesn't work with arrays and enums

This is self-explanatory. Fix it!

Verify each property in Scade on its own

Don't generate one big automaton which contains all properties for one model. Because we have to generate deterministic automata this may lead to massive blow-ups which no longer can be handled.

Improving the LTL to Büchi translation

The current LTL to Büchi-Automaton translation performs poorly when compared to the algorithms used for example in SPIN. It would benefit the verification performance tremendously if the algorithm would produce even just a few less states.
This could either mean improving the translation algorithm or using techniques to optimize the resulting Büchi automaton.

determinizeBA produces invalid output in some cases

determinizeBA $ let {trans = M.fromList [(1,[(M.fromList [],2),(M.fromList [(1,True)],1)]),(2,[(M.fromList [(2,True)],2)])] :: M.Map Int [(M.Map Int Bool,Int)]; inits = S.fromList [1]; finals = S.fromList [1,2];} in BA trans inits finals

produces:

Just initial state fromList [1]
  fromList [] -> fromList [1,2]
state fromList [1,2]
  fromList [] -> fromList [1,2]
  fromList [(2,True)] -> fromList [2]
state fromList [2]
  fromList [(2,True)] -> fromList [2]

which is obviously not deterministic.

I think that in order to fix this it would be necessary to extend AtomContainer. The correct result would look like this:

Just initial state fromList [1]
  fromList [(1,True)] -> fromList [1,2]
  fromList [(1,False)] -> fromList [2]
state fromList [1,2]
  fromList [(1,True)] -> fromList [1,2]
  fromList [(1,False)] -> fromList [2]
state fromList [2]
  fromList [(2,True)] -> fromList [2]

however AtomContainer does not have any way to express fromList [(1,False)] in terms of fromList [(1,True)] and [(M.fromList [(2,True)]

Create special case for büchi product construction

When all states are final in both büchi automaton, a simpler product automaton can be constructed by using the classical NFA product construction.

backendVerify has no way to access input/output declarations

Since NuSMV has no type declarations for the inputs of a component, it would be very convenient if I could access the input declaration of the gtl file in backendVerify.

If I did not overlook anything, what would be "the" way to expose those declarations?

LTL capturing past variables is broken

exists x = st : finally[4cy] x = st;

at the moment translates to

"st" = "st" or (X "st" = "st" or (X "st" = "st" or (X "st" = "st")))

this translation is obviously wrong.

gtl does not build with newest smtlib

Make verification seamless

Currently most verification targets just output a Promela/SCADE file for the user to compile. This means that the user must have at least some knowledge about the workings of those tools in order to be able to use the GTL tool. It would be beneficial if the GTL tool would call the SPIN/SCADE tools in order to directly verify the generated source files. It could also parse the output of those tools and provide the user with more meaningful informations about why the verification failed.