Difference between revisions of "Flata"
Radu iosif (Talk | contribs) |
Radu iosif (Talk | contribs) |
||
| Line 32: | Line 32: | ||
=== Reachability Analysis === | === Reachability Analysis === | ||
| − | The reachability analysis semi-algorithm implemented in FLATA is based on computatation of procedure summaries. The core of the method is an algorithm for computing transitive closures of octagonal relations <ref name="cav10">[http://nts.imag.fr/images/d/d5/Cav10.pdf "Fast Acceleration of Ultimately Periodic Relations."] M. Bozga, R. Iosif, and F. Konecny. In Proc. of CAV'10, volume 6174 of LNCS, pages 227-242, 2010. Springer-Verlag. </ref><ref name="cav10-TR">[http://www-verimag.imag.fr/TR/TR-2012-10.pdf "Relational Analysis of Integer Programs"] M. Bozga, R. Iosif, and F. Konecny. VERIMAG technical report, TR-2012-10, 2012. </ref> | + | The reachability analysis semi-algorithm implemented in FLATA is based on computatation of procedure summaries. The core of the method is an algorithm for computing transitive closures of octagonal relations <ref name="cav10">[http://nts.imag.fr/images/d/d5/Cav10.pdf "Fast Acceleration of Ultimately Periodic Relations."] M. Bozga, R. Iosif, and F. Konecny. In Proc. of CAV'10, volume 6174 of LNCS, pages 227-242, 2010. Springer-Verlag. </ref><ref name="cav10-TR">[http://www-verimag.imag.fr/TR/TR-2012-10.pdf "Relational Analysis of Integer Programs"] M. Bozga, R. Iosif, and F. Konecny. VERIMAG technical report, TR-2012-10, 2012. </ref>. |
| − | ''' | + | '''Examples''' |
| − | * | + | * <tt>./flata-reachability.sh benchmarks-reach/VHDL/synlifo.correct.nts</tt> (a correct program) |
| − | + | * <tt>./flata-reachability.sh benchmarks-reach/L2CA/listcounter.error.nts</tt> (program with a counterexample trace) | |
=== Termination Analysis === | === Termination Analysis === | ||
| Line 42: | Line 42: | ||
The semi-algorithm implemented in FLATA first attempts to compute a transition invariant as a disjunction of octagonal relations (by adapting the procedure summary algorithm) and then computes a termination precondition by applying an algorithm that computes the weakest termination precondition of octagonal relations <ref name="tacas12"> Deciding Conditional Termination. M. Bozga, R. Iosif, and F. Konecny. In Proc. of TACAS'12, volume 7214 of LNCS, pages 252-266, 2012. Springer-Verlag. ([http://arxiv.org/pdf/1210.42.pdf Extended journal submission.]) </ref>. The semi-algorithm is guaranteed to terminate for ''flat integer programs''. | The semi-algorithm implemented in FLATA first attempts to compute a transition invariant as a disjunction of octagonal relations (by adapting the procedure summary algorithm) and then computes a termination precondition by applying an algorithm that computes the weakest termination precondition of octagonal relations <ref name="tacas12"> Deciding Conditional Termination. M. Bozga, R. Iosif, and F. Konecny. In Proc. of TACAS'12, volume 7214 of LNCS, pages 252-266, 2012. Springer-Verlag. ([http://arxiv.org/pdf/1210.42.pdf Extended journal submission.]) </ref>. The semi-algorithm is guaranteed to terminate for ''flat integer programs''. | ||
| − | '''Example | + | '''Example''' |
* <tt>./flata-termination.sh benchmarks-term/anubhav.correct.nts</tt> | * <tt>./flata-termination.sh benchmarks-term/anubhav.correct.nts</tt> | ||
| Line 49: | Line 49: | ||
Given a recursive program, FLATA attempts to compute its summary by computing increasingly precise underapproximations of the program <ref name="tacas13">[http://arxiv.org/pdf/1210.4289.pdf "Underapproximation of Procedure Summaries for Integer Programs."] P. Ganty, R. Iosif and F. Konecny. In Proc. of TACAS'13. To appear. </ref>. Note that error control states are ignored and that a reachability relation between initial and final control states is computed. The semi-algorithm is guaranteed to terminate for ''bounded periodic integer programs''. | Given a recursive program, FLATA attempts to compute its summary by computing increasingly precise underapproximations of the program <ref name="tacas13">[http://arxiv.org/pdf/1210.4289.pdf "Underapproximation of Procedure Summaries for Integer Programs."] P. Ganty, R. Iosif and F. Konecny. In Proc. of TACAS'13. To appear. </ref>. Note that error control states are ignored and that a reachability relation between initial and final control states is computed. The semi-algorithm is guaranteed to terminate for ''bounded periodic integer programs''. | ||
| − | '''Example | + | '''Example''' |
* <tt>./flata-reachability.sh benchmarks-recur/mccarthy.nts</tt> | * <tt>./flata-reachability.sh benchmarks-recur/mccarthy.nts</tt> | ||
| Line 57: | Line 57: | ||
* [http://www-verimag.imag.fr/%7Ebozga Marius Bozga] (VERIMAG, Grenoble, France) | * [http://www-verimag.imag.fr/%7Ebozga Marius Bozga] (VERIMAG, Grenoble, France) | ||
* [http://www-verimag.imag.fr/%7Eiosif Radu Iosif] (VERIMAG, Grenoble, France) | * [http://www-verimag.imag.fr/%7Eiosif Radu Iosif] (VERIMAG, Grenoble, France) | ||
| − | * [http://www-verimag.imag.fr/~konecny/ Filip Konecny] ( | + | * [http://www-verimag.imag.fr/~konecny/ Filip Konecny] (EPFL, Lausanne, Switzerland) |
* [http://www.fit.vutbr.cz/~vojnar/ Tomas Vojnar] (Brno University of Technology, Czech Republic) | * [http://www.fit.vutbr.cz/~vojnar/ Tomas Vojnar] (Brno University of Technology, Czech Republic) | ||
Revision as of 11:15, 5 February 2013
FLATA <ref name="fm12">"A Verification Toolkit for Numerical Transition Systems." H. Hojjat, R. Iosif, F. Konecny, V. Kuncak, and P. Rummer. In Proc. of FM'12, volume 7436 of LNCS, pages 247-251, 2012. Springer-Verlag. </ref> is a toolset for the manipulation and the analysis of non-deterministic integer programs (also known as counter automata). The main functionalities of FLATA are:
- reachability analysis of non-recursive programs - checking if an error control state is reachable
- termination analysis of non-recursive programs - computation of termination preconditions
- computation of summaries of recursive programs
Contents
Download
FLATA is a free software under LGPL license. The current distribution of FLATA is available here: flata.tar.gz
Prerequisites:
- JAVA version 1.6.0 or later
- YICES has to be installed in your executable path
- GLPK Java has to be installed in LD_LIBRARY_PATH (required for termination analysis only)
Run
The input to the tool is a textual description of a counter automaton, essentially a control flow graph with edges labeled with arithmetic relations. A good way to get started using FLATA is to go through some of the examples (a subset of NTS benchmarks that FLATA can verify) contained in the distribution and run FLATA as e.g.:
- reachability analysis ./flata-reachability.sh benchmarks-reach/VHDL/synlifo.correct.nts
- termination analysis ./flata-termination.sh benchmarks-term/anubhav.correct.nts
Reachability Analysis
The reachability analysis semi-algorithm implemented in FLATA is based on computatation of procedure summaries. The core of the method is an algorithm for computing transitive closures of octagonal relations <ref name="cav10">"Fast Acceleration of Ultimately Periodic Relations." M. Bozga, R. Iosif, and F. Konecny. In Proc. of CAV'10, volume 6174 of LNCS, pages 227-242, 2010. Springer-Verlag. </ref><ref name="cav10-TR">"Relational Analysis of Integer Programs" M. Bozga, R. Iosif, and F. Konecny. VERIMAG technical report, TR-2012-10, 2012. </ref>.
Examples
- ./flata-reachability.sh benchmarks-reach/VHDL/synlifo.correct.nts (a correct program)
- ./flata-reachability.sh benchmarks-reach/L2CA/listcounter.error.nts (program with a counterexample trace)
Termination Analysis
The semi-algorithm implemented in FLATA first attempts to compute a transition invariant as a disjunction of octagonal relations (by adapting the procedure summary algorithm) and then computes a termination precondition by applying an algorithm that computes the weakest termination precondition of octagonal relations <ref name="tacas12"> Deciding Conditional Termination. M. Bozga, R. Iosif, and F. Konecny. In Proc. of TACAS'12, volume 7214 of LNCS, pages 252-266, 2012. Springer-Verlag. (Extended journal submission.) </ref>. The semi-algorithm is guaranteed to terminate for flat integer programs.
Example
- ./flata-termination.sh benchmarks-term/anubhav.correct.nts
Verification of Recursive Programs
Given a recursive program, FLATA attempts to compute its summary by computing increasingly precise underapproximations of the program <ref name="tacas13">"Underapproximation of Procedure Summaries for Integer Programs." P. Ganty, R. Iosif and F. Konecny. In Proc. of TACAS'13. To appear. </ref>. Note that error control states are ignored and that a reachability relation between initial and final control states is computed. The semi-algorithm is guaranteed to terminate for bounded periodic integer programs.
Example
- ./flata-reachability.sh benchmarks-recur/mccarthy.nts
Contributors
- Marius Bozga (VERIMAG, Grenoble, France)
- Radu Iosif (VERIMAG, Grenoble, France)
- Filip Konecny (EPFL, Lausanne, Switzerland)
- Tomas Vojnar (Brno University of Technology, Czech Republic)
Acknowledgements
This work was supported by the French national project ANR-09-SEGI-016 VERIDYC, by the Czech Science Foundation (projects P103/10/0306 and 102/09/H042), the Czech Ministry of Education (projects COST OC10009 and MSM 0021630528), and the internal FIT BUT grant FIT-S-10-1.
References
<references />
