\n
\n\n \n \n \n \n \n \n Verification of Concurrent Programs Using Trace Abstraction Refinement.\n \n \n \n \n\n\n \n Cassez, F.; and Ziegler, F.\n\n\n \n\n\n\n In Davis, M.; Fehnker, A.; McIver, A.; and Voronkov, A., editor(s),
Logic for Programming, Artificial Intelligence, and Reasoning - 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings, volume 9450, of
Lecture Notes in Computer Science, pages 233–248, 2015. Springer\n
LPAR Best paper award\n\n
\n\n
\n\n
\n\n \n \n Paper\n \n \n \n Slides\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{cassez-lpar-2015,\n author = {Franck Cassez and\n Frowin Ziegler},\n editor = {Martin Davis and\n Ansgar Fehnker and\n Annabelle McIver and\n Andrei Voronkov},\n title = {Verification of Concurrent Programs Using Trace Abstraction Refinement},\n booktitle = {Logic for Programming, Artificial Intelligence, and Reasoning - 20th\n International Conference, {LPAR-20} 2015, Suva, Fiji, November 24-28,\n 2015, Proceedings},\n pages = {233--248},\n year = {2015},\n series = {Lecture Notes in Computer Science},\n volume = {9450},\n publisher = {Springer},\n year = {2015},\n url = {http://dx.doi.org/10.1007/978-3-662-48899-7_17},\n mywebpage = {soft-verif},\n category = {soft-verif},\n isbn = {978-3-662-48898-0},\n doi = {10.1007/978-3-662-48899-7_17},\n show = {},\n note = {LPAR Best paper award},\n urlpaper = {papers/lpar-2015.pdf},\n urlslides = {papers/slides-lpar-2015.pdf},\n abstract = {Verifying concurrent programs is notoriously hard due to the state explosion problem: (1) the data state space can be very large as the variables can range over very large sets, and (2) the control state space is the Cartesian product of the control state space of the concurrent com- ponents and thus grows exponentially in the number of components. On the one hand, the most successful approaches to address the control state explosion problem are based on assume-guarantee reasoning or model-checking coupled with partial order reduction. On the other hand, the most successful techniques to address the data space explosion problem for sequential programs verification are based on the abstraction/refine- ment paradigm which consists in refining an abstract over-approximation of a program via predicate refinement. In this paper, we show that we can combine partial order reduction techniques with trace abstraction refinement. We apply our approach to standard benchmarks and show that it matches current state-of-the-art analysis techniques.},\n Type = {B - International Conferences},\n}\n\n
\n
\n\n\n
\n Verifying concurrent programs is notoriously hard due to the state explosion problem: (1) the data state space can be very large as the variables can range over very large sets, and (2) the control state space is the Cartesian product of the control state space of the concurrent com- ponents and thus grows exponentially in the number of components. On the one hand, the most successful approaches to address the control state explosion problem are based on assume-guarantee reasoning or model-checking coupled with partial order reduction. On the other hand, the most successful techniques to address the data space explosion problem for sequential programs verification are based on the abstraction/refine- ment paradigm which consists in refining an abstract over-approximation of a program via predicate refinement. In this paper, we show that we can combine partial order reduction techniques with trace abstraction refinement. We apply our approach to standard benchmarks and show that it matches current state-of-the-art analysis techniques.\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Perentie: Modular Trace Refinement and Selective Value Tracking - (Competition Contribution).\n \n \n \n \n\n\n \n Cassez, F.; Matsuoka, T.; Pierzchalski, E.; and Smyth, N.\n\n\n \n\n\n\n In
Tools and Algorithms for the Construction and Analysis of Systems - 21st International Conference, TACAS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015. Proceedings, volume 9035, of
LNCS, pages 439–442, 2015. Springer\n
\n\n
\n\n
\n\n
\n\n \n \n Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n\n\n\n
\n
@inproceedings{tacas-15,\nauthor = {Franck Cassez and\n Takashi Matsuoka and\n Edward Pierzchalski and\n Nathan Smyth},\n title = {Perentie: Modular Trace Refinement and Selective Value Tracking -\n (Competition Contribution)},\n booktitle = {Tools and Algorithms for the Construction and Analysis of Systems\n - 21st International Conference, {TACAS} 2015, Held as Part of the\n European Joint Conferences on Theory and Practice of Software, {ETAPS}\n 2015, London, UK, April 11-18, 2015. Proceedings},\n pages = {439--442},\n year = {2015},\n url = {http://dx.doi.org/10.1007/978-3-662-46681-0_39},\n doi = {10.1007/978-3-662-46681-0_39},\n publisher = springv,\n volume = 9035,\n series = lncs,\n mywebpage = {soft-verif},\n keywords = {refinement, software verification},\n category = {soft-verif},\n show = {},\n urlpaper = {papers/sv-comp-2015.pdf},\n abstract = {Perentie is a software analysis tool based on iterative refinement of trace abstraction:\n if the refinement process terminates, the program is either declared correct or a counterexample is\n provided and the program is incorrect.},\n Type = {B - International Conferences},\n\n}\n\n\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n%%% 2014\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n\n
\n
\n\n\n
\n Perentie is a software analysis tool based on iterative refinement of trace abstraction: if the refinement process terminates, the program is either declared correct or a counterexample is provided and the program is incorrect.\n
\n\n\n