Correctness Checking using
Formal Verification
This
is an
ongoing project which tries to equip Ptolemy II with abilities to test
the correctness
of a system using formal verification. Currently we develop a code
generator to
convert Ptolemy II models into files accepted by model checker SMV (also acceptable
by NuSMV).
- Open
$PTII/ptolemy/verification/demo/TrafficLight/SimpleTrafficLight.xml
- Double click
on the MathematicalModelConverter
(Pink color).
- A dialog box
will appear, ask you to input temporal formula. Type ! EF (CarLightNormal.state
= Cgrn & PedestrianLightNormal.state
= Pgreen).
You may want to copy the above line; it would be a lot faster.
- Press OK.
The code accepted by NuSMV
will be generated. You can thus save the file (use .smv as
extension). Also you can only check the
generated .smv format by selecting "Open
Generated Format" in step 3.
- Invoke NuSMV or SMV to see if the
property is hold. If you have installed NuSMV and set up the path
environment variable (how?),
you may also check the result of verification by selecting "Invoke
NuSMV" options in step 3.
- Now
modify the model by opening the PedestrianLightNormal actor,
redirect the transition from Pgreen to Pred by creating a self loop in
Pgreen (you can move the arrow pointed to Pred back to Pgreen). In this
way, the model is no longer correct. Perform verification again, and
the result would be false with a counter example.
Demo 2: Generate the specification directly from the graph
In
this demo, we are experimenting methods to alleviate designers' burden
on writing the specification themselves. A simple solution is to
generate the specification graphically. For reachability properties,
this can be done easily by annotating properties on states.
- Open
$PTII/ptolemy/verification/demo/TrafficLight/SimpleTrafficLightGraphicalSpec.xml
- You
can open the actors freely. Note that now the in FMVCarlightNormal, the
state Cgrn is red, and so is the state Pgreen in
FMVPedestrianLightNormal.
- Double click
on the MathematicalModelConverter
(Pink color).
- A dialog box
will appear, ask you to input temporal formula. This time, for the formula type, choose Risk,
and you don't need to type the formula. The specification will be
annotated automatically in the file based on red-labeled states.
- To
generate an automaton with the ability to annotate risk/reachability
properties, you can open an FMVAutomaton editor from File -- New --Fmv
Automaton editor, or you can drag an instance in the graph editor (More
Libraries -- CodeGenerators -- Verification -- FmvAutomaton).
Demo 3: SMVLegacyCodeActor
The SMVLegacyCodeActor can be viewed as a preliminary version of
code-generation helpers. The user can specify functionalities written
in SMV, and the MathematicalModelConverter would append it to the
generated file. In fact, a code-generation
helper for a particular actor can be viewed as a template; the
information for the actor and relevent ports is annotated to the
template as the converted result.
- Open
$PTII/ptolemy/verification/demo/TrafficLight/SimpleTrafficLightSMVModule.xml
- You can open the PedestrianLightSMV actor, and you can find some code written in formats acceptable by SMV.
- Double click
on the MathematicalModelConverter
(Pink color). Type ! EF (CarLightNormal.state = Cgrn & PedestrianLightSMV.state = Pgreen).
You may want to copy the above line; it would be a lot faster. Perform the verification.
A larger example in robotic controller design (reactive control)
A relatively larger example can be found in $PTII/ptolemy/verification/demo/iRobotHillClimbing/iRobotCreateVerification.xml
Install
NuSMV and set up environment variables
In
our current Java implementation, we simply invoke a process to execute
existing NuSMV and redirect the console into the Ptolemy window. Thus
if you expect to use NuSMV in Ptolemy rather than generating codes only,
please follow instructions listed below (instructions are for
Microsoft Windows OS; for linux users, please apply similar
approaches).
Install
NuSMV by downloading from its website.
- Assume
the installed NuSMV directory in your system is C:\Program
Files\NuSMV\2.4.3,
then set up the the environment variable "Path" by attaching "C:\Program
Files\NuSMV\2.4.3\bin" (Control Panel >> System
>> Advanced >>
Environment Variable). Save your changes.
- That's all
you need to do! Now you can invoke NuSMV within Ptolemy II
software!
To
perform full integration of verification process, we also experiment
how to embed verification engines into the Ptolemy II architecture.
Currently we are able to integrate NuSMV into Ptolemy II, where code
modification is minor (<100 lines + 1 file renaming). The core
technique is to use EmbeddedCActor instead of using Java Native
Interface directly (it is relatively complicated for C++
programmers to learn Java and JNI). Therefore, for researchers
willing to use Ptolemy II as their front-end, this offers excellent
guidance.
- This is a highly
preliminary code generator facility, with many limitations. It is best
viewed
as a concept demonstration. Currently it
may analyze a single FSMActor, and a system consisting of multiple
FSMActors or ModalModels (with state or SR refinement )
interacting with SMVLegacyCodeActors in the SR domain. For models in
the DE domain, we are also performing preliminary experiments. We will
expand
existing functionalities soon.
- We find some examples having problem executing under NuSMV while they are
executable under SMV. Examples in the demo folder includes iRobotCreateVerification.xml and HierarchicalTrafficLight.xml. Our preminiary diagnosis is that there are small syntatic differences between SMV and NuSMV.