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).

Demo 1 :Traffic light example

  1. Open $PTII/ptolemy/verification/demo/TrafficLight/SimpleTrafficLight.xml
  2. Double click on the MathematicalModelConverter (Pink color).
  3. 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. 
  4. 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.
  5. 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. 
  6. 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. 

  1. Open $PTII/ptolemy/verification/demo/TrafficLight/SimpleTrafficLightGraphicalSpec.xml
  2. 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. 
  3. Double click on the MathematicalModelConverter (Pink color).
  4. 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.
  5. 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.

  1. Open $PTII/ptolemy/verification/demo/TrafficLight/SimpleTrafficLightSMVModule.xml
  2. You can open the PedestrianLightSMV actor, and you can find some code written in formats acceptable by SMV. 
  3. 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). 

  1. Install NuSMV by downloading from its website. 
  2. 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.
  3. That's all you need to do! Now you can invoke NuSMV within Ptolemy II software! 

Integrating verification engines using the EmbeddedCActor 

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. 

Limitations

  1. 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. 
  2. 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.