Sunday, December 25, 2016

Major Update Released (0.4)

New Version Released (0.4)
Actions in a colored Kripke Structure
Global Model Check
Refinements
Synchronization Skeletons Editor
Scripting REPL



New Features:

 - Action Synchronization: You can now synchronize transition shared between multiple processes using action names. You can choose whether to use synchronization by process indices, by action names, or both when repairing the structure. Actions are supported by all the other features (abstractions, transforming to synchronization skeletons, etc ...).

 - Global Model Checking: Eshmun can check whether any user-provided CTL formula holds at state. States that satisfy the formula will be shaded in grey, other states will be displayed as usual. This process is similar to model checking the structure many times, each time using one of the states as a start state.

 - Unsat Core: If the structure is unrepairable, you can use a minimal unsat core to determine a small subset of states and transitions that are causing the structure to be unrepairable. At least one start state will be part of this set. Eshmun will communicate with the Unsat core solver and highlight the subset graphically. This feature requires you to get MUSer2. When using this feature Eshmun will look for MUSer2 in the same directory, if it fails to find it, it will prompt a dialog box asking for its location. You can get MUSer2 from http://logos.ucd.ie/web/doku.php?id=muser .

- Synchronization Skeletons Editor: Eshmun's Synchronization Skeletons editor is now enhanced, it is easier to input/modify the guards, as well as add additional states and transitions to the skeletons. The guards can refer to action names.

- Scripting: Eshmun provides a built in small scripting language for creating structures quickly. You can use the scripting language to quickly replicate an existing structure, modify existing ones, or create them from scratch. The scripting language contains loops and conditionals that can be used to determine which pairs of processes to create. It also contains constructs to import/load structures from Eshmun. The scripts can be written in a file or directly into a REPL Terminal inside Eshmun.

- Refinements: Repair of big or complicated structures is often an iterative process, that includes modifying the structure and specifications, iteratively repairing the structure against different specifications, and using other helpful features of Eshmun (transforming to skeletons, abstractions, etc..). Eshmun supports recording these different steps to track the different stages of repair. The resulting sequences of steps (a refinement) can be saved, loaded, and modified.

- Visual Aids: Additional visual aids have been added to Eshmun. This facilitates navigating and understanding big structures. These aids include custom coloring of actions, labels, and transitions based on the process they belong to or the action name they synchronize by, determining which process to show and which hide, as well as displaying different statistics about the size of the structures, repairs, and internal SAT formulae.

User Help: Please refer to the user manual inside Eshmun (in the help menu) for a detailed user manual. The manual covers all the existing features, and provides helpful tips on how to use Eshmun in general.




Backwards Compatibility:

 - Saved structures from older versions may not work. Depending on what features are used in these saved structures, the new version may fail to open them. This issue can be solved by using an older version of Eshmun to export these structures into text format, then importing the text format into the new version of Eshmun. The imported structures will be automatically "upgraded", and can be dealt with as if structures produced by the new version.


Downloads:

 - The new version of the tool (version 0.4) can be downloaded here. It is a runnable jar file, it is recommended to use Java 8, but java 7 is also supported. Please notice that the tool is still under development and is not a final-release.


Bug reports: 
If a bug was encountered, please submit a bug report to the following email eshmuntool@gmail.com, please attach with it a saved copy of the structure causing the bug, or details on how to reproduce the bug on our machines to study it. Your feedback is highly appreciated and will help us deliver a better tool. 

Tuesday, September 22, 2015

Update Released (0.3)

New Version Released (0.3)

Synchronization Skeleton for Mutex of 3 processes with shared variables to keep track of priority.

New Features:

 - Decision Procedure: The tool provides an Implementation of the Decision Procedure [Emerson and Clark 82]. The decision procedure is accessed from the tools menu, it can be used to determine the satiability or validity of boolean formulae, the tableau (before deletions) can also be displayed.

 - Concurrent Abstraction: Concurrent Kripke Structures can be abstracted efficiently (By labels or sub-formulae). The concertized repair is model checked against the original specifications, as well as checked for synchronization between the pairs.

 - Synchronization Skeleton: Kripke Structures (single and concurrent) can now be transformed to a synchronization skeleton. Synchronization Skeleton can be edited by adding or removing states and transitions. Synchronization Skeletons can be transformed back to Kripke Structures.

Downloads:

 - The new version of the tool (version 0.3) can be downloaded here. It is a runnable jar file, it required java 7. Please notice that the tool is still under development and is not a final-release.

Tableau for determining satisfiability of [ AX(P) & P => AG(P) ]
Bug reports: 
If a bug was encountered, please submit a bug report to the following email eshmuntool@gmail.com, please attach with it a saved copy of the structure causing the bug, or details on how to reproduce the bug on our machines to study it. Your feedback is highly appreciated and will help us deliver a better tool. 

Monday, August 3, 2015

Minor Update Release (0.2.1)

New Version Released (0.2.1)





New Features:

 - Transitions Coloring: The tool can automatically detect the process making a transition, then color all the transitions of a process with the same color. The name of the process making the transition is also displayed in the information bar when the transition is selected. Details on how to activate the feature are present in the user manual inside Eshmun (F1).

 - Process-Indexed Next time CTL Operators: By indexing AX and EX operators with a process name you can restrict the operator. Instead of considering all the children states, only the children reached by a transition belonging to the indexed process are considered. Additional information on the usage and syntax are available in the user manual.

Change Notice: Retained States and Transitions now appear in bold instead of being colored red. The color red could be used as a process color.

Downloads:

 - The new version of the tool (version 0.2.1) can be downloaded here. It is a runnable jar file, it required java 7. Please notice that the tool is still under development and is not a final-release.

Bug reports: 
If a bug was encountered, please submit a bug report to the following email eshmuntool@gmail.com, please attach with it a saved copy of the structure causing the bug, or details on how to reproduce the bug on our machines to study it. Your feedback is highly appreciated and will help us deliver a better tool. 


Sunday, June 21, 2015

Model and Program Repair via SAT Solving

Eshmun Tool

Barrier Synchronization with 4 Barriers.
Click on the picture to view all the pictures in high quality.
4 Barriers Synchronization: Abstracted by Formula.
Click on the picture to view all the pictures in high quality.
Barrier Synchronization: 2 Barriers, 2 Processes (Full Paper).
Click on the picture to view all the pictures in high quality.
Dining Philosopher for 2 Philosophers.
Click on the picture to view all the pictures in high quality.
Eventually Serialized Data Service: Replica-Replica Pair Repaired.
Click on the picture to view all the pictures in high quality.
2 Process Mutual Exclusion with Liveness (Full Paper).
Click on the picture to view all the pictures in high quality.
5 Processes Mutual Exclusion Abstracted By Label
Click on the picture to view all the pictures in high quality.
5 Processes Mutual Exclusion
Click on the picture to view all the pictures in high quality.
Two Rounds Phone call Repaired (Full Paper).
Click on the picture to view all the pictures in high quality.
Concurrent Mutual Exclusion for 3 Pairs
Click on the picture to view all the pictures in high quality.


Abstract:

We consider the model repair problem: given a finite Kripke structure M and a CTL formula η, determine if M contains a substructure M that satisfies η. Thus, M can be “repaired” to satisfy η by deleting some transitions. We map an instance (M, η) of model repair to a boolean formula repair (M, η) such that (M, η) has a solution iff repair (M, η) is satisfiable. Furthermore, a satisfying assignment determines which states and transitions must be removed from M to generate a model M of η. Thus, we can use any SAT solver to repair Kripke structures. Using a complete SAT solver yields a complete algorithm: it always finds a repair if one exists. We also show that CTL model repair is NP-complete. We extend the basic repair method in three directions: (1) the use of abstraction mappings, i.e., repair a structure abstracted from M and then concretize the resulting repair to obtain a  repair of M , and (2) repair concurrent Kripke structures and concurrent programs: we use the pairwise method of Attie and Emerson to represent and repair the behavior of a concurrent program, as a set of “concurrent Kripke structures”, with only a quadratic increase in the size of the repair formula. (3) repair hierarchical Kripke structures: we use a CTL formula to summarize the behavior of each “box”, and CTL deduction to relate the box formula with the overall specification.

We successfully repaired the following (some of which is shown above in the pictures):
  1. Mutual Exclusion.
  2. Barrier Synchronization.
  3. Dining Philosophers.
  4. Eventually Serializable Data Service.
  5. One and Two rounds Phone call.

Downloads:

 - The tool (version 0.2) can be downloaded here. It is a runnable jar file, it required java 7. Please notice that the tool is still under development and is not a final-release.

 - You can access the tool user-manual here. The tool user-manual is also available inside the tool, under the Help Menu (or by pressing F1).

 - The full paper can be accessed here.

 - The examples used in the paper, and benchmarks are available in the following zip archive. The archive contains two folders:
    1. single: contains examples on single Kripke structures divided into folders: phone call, mutual exclusion, a simple dining philosophers (2 philosophers), and barrier synchronization.
    2. concurrent: contains examples on concurrent Kripke structures and programs: ESDS, mutual exclusion, dining philosophers.
    3. Every file is named with a number, representing the number of processes in the structure.
Technical References:
  1. Synthesis of Large Dynamic Concurrent Programs from Dynamic Specifications, P. C. Attie.
  2. Synthesis of Concurrent Systems with Many Similar Processes, P. C. Attie and E. A. Emerson.
    
    
  3. Synthesis of Large Concurrent Programs via Pairwise Composition, P. C. Attie.
Currently Under Implementation:
The following are under implementation:
  1. Decision Procedure, the form included in the jar is a placeholder.
  2. Abstracting concurrent structures: currently it abstracts, but repair is not possible.
  3. Making the repair traverse buttons more efficient: currently old repairs might reappear, sometimes the repair itself remains visible for few trials. This is due to having extra variables in the repair formula that don't immediately impact the visible repair.
Bug reports:
 
If a bug was encountered, please submit a bug report to the following email eshmuntool@gmail.com, please attach with it a saved copy of the structure causing the bug, or details on how to reproduce the bug on our machines to study it. Your feedback is highly appreciated and will help us deliver a better tool.