hgoes / gtl Goto Github PK
View Code? Open in Web Editor NEWThe GALS Transformation Language
License: Other
The GALS Transformation Language
License: Other
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.
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.
When all states are final in both büchi automaton, a simpler product automaton can be constructed by using the classical NFA product construction.
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.
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)]
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?
This is self-explanatory. Fix it!
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.
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
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.
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.
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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.