uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Haziza, Frédéric
Publications (10 of 13) Show all publications
Abdulla, P., Haziza, F., Holík, L., Jonsson, B. & Rezine, A. (2017). An integrated specification and verification technique for highly concurrent data structures for highly concurrent data structures. International Journal on Software Tools for Technology Transfer (STTT), 19(5), 549-563
Open this publication in new window or tab >>An integrated specification and verification technique for highly concurrent data structures for highly concurrent data structures
Show others...
2017 (English)In: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 19, no 5, p. 549-563Article in journal (Refereed) Published
Abstract [en]

We present a technique for automatically verifying safety properties of concurrent programs, in particular programs that rely on subtle dependencies of local states of different threads, such as lock-free implementations of stacks and queues in an environment without garbage collection. Our technique addresses the joint challenges of infinite-state specifications, an unbounded number of threads, and an unbounded heap managed by explicit memory allocation. Our technique builds on the automata-theoretic approach to model checking, in which a specification is given by an automaton that observes the execution of a program and accepts executions that violate the intended specification. We extend this approach by allowing specifications to be given by a class of infinite-state automata. We show how such automata can be used to specify queues, stacks, and other data structures, by extending a data-independence argument. For verification, we develop a shape analysis, which tracks correlations between pairs of threads, and a novel abstraction to make the analysis practical. We have implemented our method and used it to verify programs, some of which have not been verified by any other automatic method before.

Place, publisher, year, edition, pages
SPRINGER HEIDELBERG, 2017
Keywords
Verification, Pointer programs, Explicit memory allocation, Queue, Stack, Unbounded, Concurrency, Specification, Linearizability
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:uu:diva-334744 (URN)10.1007/s10009-016-0415-4 (DOI)000409295800004 ()
Available from: 2017-11-29 Created: 2017-11-29 Last updated: 2018-01-13Bibliographically approved
Abdulla, P. A., Haziza, F. & Holík, L. (2016). Parameterized verification through view abstraction. International Journal on Software Tools for Technology Transfer (STTT), 18(5), 495-516
Open this publication in new window or tab >>Parameterized verification through view abstraction
2016 (English)In: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 18, no 5, p. 495-516Article in journal (Refereed) Published
Abstract [en]

We present a simple and efficient framework for automatic verification of systems with a parametric number of communicating processes. The processes may be organized in various topologies such as words, multisets, rings, or trees. Our method needs to inspect only a small number of processes in order to show correctness of the whole system. It relies on an abstraction function that views the system from the perspective of a fixed number of processes. The abstraction is used during the verification procedure in order to dynamically detect cut-off points beyond which the search of the state space need not continue. We show that the method is complete for a large class of well quasi-ordered systems including Petri nets. Our experimentation on a variety of benchmarks demonstrate that the method is highly efficient and that it works well even for classes of systems with undecidable verification problems. In particular, the method handles the fine-grained and full version of Szymanski's mutual exclusion protocol, whose correctness, to the best of our knowledge, has not been proven automatically by any other existing methods.

Keywords
Parameterized systems; Safety; Small model properties; View abstraction
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-260089 (URN)10.1007/s10009-015-0406-x (DOI)000382011100003 ()
Projects
UPMARC
Available from: 2015-11-23 Created: 2015-08-15 Last updated: 2017-12-04Bibliographically approved
Haziza, F., Holík, L., Meyer, R. & Wolff, S. (2016). Pointer Race Freedom. In: Verification, Model Checking, And Abstract Interpretation, VMCAI 2016: . Paper presented at 17th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI), JAN 17-19, 2016, St Petersburg, FL (pp. 393-412). Springer
Open this publication in new window or tab >>Pointer Race Freedom
2016 (English)In: Verification, Model Checking, And Abstract Interpretation, VMCAI 2016, Springer, 2016, p. 393-412Conference paper, Published paper (Refereed)
Abstract [en]

We propose a novel notion of pointer race for concurrent programs manipulating a shared heap. A pointer race is an access to a memory address which was freed, and it is out of the accessor's control whether or not the cell has been re-allocated. We establish two results. (1) Under the assumption of pointer race freedom, it is sound to verify a program running under explicit memory management as if it was running with garbage collection. (2) Even the requirement of pointer race freedom itself can be verified under the garbage-collected semantics. We then prove analogues of the theorems for a stronger notion of pointer race needed to cope with performance-critical code purposely using racy comparisons and even racy dereferences of pointers. As a practical contribution, we apply our results to optimize a thread-modular analysis under explicit memory management. Our experiments confirm a speedup of up to two orders of magnitude.

Place, publisher, year, edition, pages
Springer, 2016
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9583
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-299664 (URN)10.1007/978-3-662-49122-5_19 (DOI)000375148800019 ()9783662491225; 9783662491218 (ISBN)
Conference
17th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI), JAN 17-19, 2016, St Petersburg, FL
Available from: 2016-07-25 Created: 2016-07-25 Last updated: 2018-01-10Bibliographically approved
Dahlö, M., Haziza, F., Kallio, A., Korpelainen, E., Bongcam-Rudloff, E. & Spjuth, O. (2015). BioImg.org: A catalog of virtual machine images for the life sciences. Bioinformatics and Biology Insights, 9, 125-128
Open this publication in new window or tab >>BioImg.org: A catalog of virtual machine images for the life sciences
Show others...
2015 (English)In: Bioinformatics and Biology Insights, ISSN 1177-9322, E-ISSN 1177-9322, Vol. 9, p. 125-128Article in journal (Refereed) Published
Abstract [en]

Virtualization is becoming increasingly important in bioscience, enabling assembly and provisioning of complete computer setups, including operating system, data, software, and services packaged as virtual machine images (VMIs). We present an open catalog of VMIs for the life sciences, where scientists can share information about images and optionally upload them to a server equipped with a large file system and fast Internet connection. Other scientists can then search for and download images that can be run on the local computer or in a cloud computing environment, providing easy access to bioinformatics environments. We also describe applications where VMIs aid life science research, including distributing tools and data, supporting reproducible analysis, and facilitating education.

Keywords
catalogue; virtual machine image; virtual appliance; container; software repository; cloud computing
National Category
Bioinformatics (Computational Biology)
Identifiers
urn:nbn:se:uu:diva-262376 (URN)10.4137/BBI.S28636 (DOI)000365108200001 ()26401099 (PubMedID)
Funder
Science for Life Laboratory - a national resource center for high-throughput molecular bioscienceeSSENCE - An eScience CollaborationEU, FP7, Seventh Framework Programme, Bm1006EU, FP7, Seventh Framework Programme, allBioSwedish National Infrastructure for Computing (SNIC)
Available from: 2015-09-10 Created: 2015-09-14 Last updated: 2018-01-11Bibliographically approved
Haziza, F. (2015). Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis. (Doctoral dissertation). Uppsala: Acta Universitatis Upsaliensis
Open this publication in new window or tab >>Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This doctoral thesis considers the automatic verification of parameterized systems, i.e. systems with an arbitrary number of communicating components, such as mutual exclusion protocols, cache coherence protocols or heap manipulating programs. The components may be organized in various topologies such as words, multisets, rings, or trees.

The task is to show correctness regardless of the size of the system and we consider two methods to prove safety:(i) a backward reachability analysis, using the well-quasi ordered framework and monotonic abstraction, and (ii) a forward analysis which only needs to inspect a small number of components in order to show correctness of the whole system. The latter relies on an abstraction function that views the system from the perspective of a fixed number of components. The abstraction is used during the verification procedure in order to dynamically detect cut-off points beyond which the search of the state-space need not continue.

Our experimentation on a variety of benchmarks demonstrate that the method is highly efficient and that it works well even for classes of systems with undecidable property. It has been, for example, successfully applied to verify a fine-grained model of Szymanski's mutual exclusion protocol. Finally, we applied the methods to solve the complex problem of verifying highly concurrent data-structures, in a challenging setting: We do not a priori bound the number of threads, the size of the data-structure, the domain of the data to store nor do we require the presence of a garbage collector. We successfully verified the concurrent Treiber's stack and Michael & Scott's queue, in the aforementioned setting.

To the best of our knowledge, these verification problems have been considered challenging in the parameterized verification community and could not be carried out automatically by other existing methods.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2015. p. 123
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1302
Keywords
program verification, model checking, parameterized systems, infinite-state systems, reachability, approximation, safety, tree systems, shape analysis, small model properties, view abstraction, monotonic abstraction
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-264171 (URN)978-91-554-9366-0 (ISBN)
Public defence
2015-11-18, ITC 2446, Lägerhyddsvägen 2, Uppsala, 13:00 (English)
Opponent
Supervisors
Projects
UPMARC
Available from: 2015-10-28 Created: 2015-10-06 Last updated: 2019-02-25
Abdulla, P. A., Haziza, F. & Holík, L. (2014). Block me if you can!: Context-sensitive parameterized verification. In: Static Analysis: SAS 2014. Paper presented at 21st International Symposium, SAS 2014, September 11–13, Munich, Germany (pp. 1-17). Springer
Open this publication in new window or tab >>Block me if you can!: Context-sensitive parameterized verification
2014 (English)In: Static Analysis: SAS 2014, Springer, 2014, p. 1-17Conference paper, Published paper (Refereed)
Abstract [en]

We present a method for automatic verification of systems with a parameterized number of communicating processes, such as mutual exclusion protocols or agreement protocols. To that end, we present a powerful abstraction framework that uses an efficient and precise symbolic encoding of (infinite) sets of configurations. In particular, it generalizes downward-closed sets that have successfully been used in earlier approaches to parameterized verification. We show experimentally the efficiency of the method, on various examples, including a fine-grained model of Szymanski’s mutual exclusion protocol, whose correctness, to the best of our knowledge, has not been proven automatically by any other existing methods.

Place, publisher, year, edition, pages
Springer, 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8723
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-260087 (URN)10.1007/978-3-319-10936-7_1 (DOI)000360204700001 ()978-3-319-10935-0 (ISBN)
Conference
21st International Symposium, SAS 2014, September 11–13, Munich, Germany
Projects
UPMARC
Available from: 2014-09-13 Created: 2015-08-15 Last updated: 2015-12-16Bibliographically approved
Abdulla, P. A., Haziza, F. & Holík, L. (2013). All for the price of few: (Parameterized verification through view abstraction). In: Verification, Model Checking, and Abstract Interpretation: . Paper presented at VMCAI 2013, January 20-22, Rome, Italy (pp. 476-495). Springer Berlin/Heidelberg
Open this publication in new window or tab >>All for the price of few: (Parameterized verification through view abstraction)
2013 (English)In: Verification, Model Checking, and Abstract Interpretation, Springer Berlin/Heidelberg, 2013, p. 476-495Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science ; 7737
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-190003 (URN)10.1007/978-3-642-35873-9_28 (DOI)978-3-642-35872-2 (ISBN)
Conference
VMCAI 2013, January 20-22, Rome, Italy
Projects
UPMARC
Available from: 2013-01-09 Created: 2013-01-07 Last updated: 2015-11-10Bibliographically approved
Abdulla, P. A., Haziza, F., Holik, L., Jonsson, B. & Rezine, A. (2013). An Integrated Specification and Verification Technique for Highly Concurrent Data Structures. In: Tools and Algorithms for the Construction and Analysis of Systems. Paper presented at 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 16-24 March, 2013, Rome, ITALY.
Open this publication in new window or tab >>An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
Show others...
2013 (English)In: Tools and Algorithms for the Construction and Analysis of Systems, 2013Conference paper, Published paper (Refereed)
Abstract [en]

We present a technique for automatically verifying safety properties of concurrent programs, in particular programs which rely on subtle dependen- cies of local states of different threads, such as lock-free implementations of stacks and queues in an environment without garbage collection. Our technique addresses the joint challenges of infinite-state specifications, an unbounded num- ber of threads, and an unbounded heap managed by explicit memory allocation. Our technique builds on the automata-theoretic approach to model checking, in which a specification is given by an automaton that observes the execution of a program and accepts executions that violate the intended specification. We extend this approach by allowing specifications to be given by a class of infinite-state au- tomata. We show how such automata can be used to specify queues, stacks, and other data structures, by extending a data-independence argument. For verifica- tion, we develop a shape analysis, which tracks correlations between pairs of threads, and a novel abstraction to make the analysis practical. We have imple- mented our method and used it to verify programs, some of which have not been verified by any other automatic method before.

Keywords
verification, pointer program, queue, stack, unbounded concurrency, specification, linearizability
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-191330 (URN)
Conference
19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 16-24 March, 2013, Rome, ITALY
Projects
UPMARC
Available from: 2013-01-16 Created: 2013-01-10 Last updated: 2018-01-11Bibliographically approved
Abdulla, P. A., Chen, Y.-F., Delzanno, G., Haziza, F., Hong, C.-D. & Rezine, A. (2010). Constrained monotonic abstraction: A CEGAR for parameterized verification. In: CONCUR 2010 – Concurrency Theory. Paper presented at 21st International Conference, CONCUR 2010, Paris, France, August 31-September 3, 2010 (pp. 86-101). Berlin: Springer-Verlag
Open this publication in new window or tab >>Constrained monotonic abstraction: A CEGAR for parameterized verification
Show others...
2010 (English)In: CONCUR 2010 – Concurrency Theory, Berlin: Springer-Verlag , 2010, p. 86-101Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we develop a counterexample-guided abstraction refinement (CEGAR) framework for monotonic abstraction, an approach that is particularly useful in automatic verification of safety properties for parameterized systems The main drawback of verification using monotonic abstraction is that it sometimes generates spurious counterexamples Our CEGAR algorithm automatically extracts from each spurious counterexample a set of configurations called a "Safety Zone" and uses it to refine the abstract transition system of the next iteration We have developed a prototype based on this idea, and our experimentation shows that the approach allows to verify many of the examples that cannot be handled by the original monotonic abstraction approach.

Place, publisher, year, edition, pages
Berlin: Springer-Verlag, 2010
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6269
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-130923 (URN)10.1007/978-3-642-15375-4_7 (DOI)000285373500007 ()978-3-642-15374-7 (ISBN)
Conference
21st International Conference, CONCUR 2010, Paris, France, August 31-September 3, 2010
Projects
UPMARCautomated verification of highly concurrent algorithms
Available from: 2010-09-17 Created: 2010-09-17 Last updated: 2018-01-12Bibliographically approved
Abdulla, P. A., Haziza, F. & Kindahl, M. (2008). Model checking race-freeness. SIGARCH Computer Architecture News, 36(5), 72-79
Open this publication in new window or tab >>Model checking race-freeness
2008 (English)In: SIGARCH Computer Architecture News, ISSN 0163-5964, E-ISSN 1943-5851, Vol. 36, no 5, p. 72-79Article in journal (Refereed) Published
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-142914 (URN)10.1145/1556444.1556454 (DOI)
Available from: 2011-01-17 Created: 2011-01-17 Last updated: 2018-01-12Bibliographically approved
Organisations

Search in DiVA

Show all publications