uu.seUppsala universitets publikasjoner
Endre søk
Begrens søket
1 - 13 of 13
RefereraExporteraLink til resultatlisten
Permanent link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Treff pr side
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Forfatter A-Ø
  • Forfatter Ø-A
  • Tittel A-Ø
  • Tittel Ø-A
  • Type publikasjon A-Ø
  • Type publikasjon Ø-A
  • Eldste først
  • Nyeste først
  • Skapad (Eldste først)
  • Skapad (Nyeste først)
  • Senast uppdaterad (Eldste først)
  • Senast uppdaterad (Nyeste først)
  • Disputationsdatum (tidligste først)
  • Disputationsdatum (siste først)
  • Standard (Relevans)
  • Forfatter A-Ø
  • Forfatter Ø-A
  • Tittel A-Ø
  • Tittel Ø-A
  • Type publikasjon A-Ø
  • Type publikasjon Ø-A
  • Eldste først
  • Nyeste først
  • Skapad (Eldste først)
  • Skapad (Nyeste først)
  • Senast uppdaterad (Eldste først)
  • Senast uppdaterad (Nyeste først)
  • Disputationsdatum (tidligste først)
  • Disputationsdatum (siste først)
Merk
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ben Henda, Noomene
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Delzanno, Giorgio
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Parameterized tree systems2008Inngår i: Formal Techniques for Networked and Distributed Systems: FORTE 2008 / [ed] Suzuki K, Berlin: Springer-Verlag , 2008, s. 69-83Konferansepaper (Fagfellevurdert)
    Abstract [en]

    Several recent works have considered parameterized verification, i.e. automatic verification of systems consisting of an arbitrary number of finite-state processes organized in a linear array. The aim of this paper is to extend these works by giving a simple and efficient method to prove safety properties for systems with tree-like architectures. A process in the system is a finite-state automaton and a transition is performed jointly by a process and its parent and children processes. The method derives an over-approximation of the induced transition system, which allows the use of finite trees as symbolic representations of infinite sets of configurations. Compared to traditional methods for parameterized verification of systems with tree topologies, our method does not require the manipulation of tree transducers, hence its simplicity and efficiency. We have implemented a prototype which works well on several nontrivial tree-based protocols.

  • 2.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Bouajjani, Ahmed
    Cederberg, Jonathan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Monotonic abstraction for programs with dynamic memory heaps2008Inngår i: Computer Aided Verification / [ed] Gupta A, Malik S, Berlin: Springer-Verlag , 2008, s. 341-354Konferansepaper (Fagfellevurdert)
    Abstract [en]

    We propose a new approach for automatic verification of programs with dynamic heap manipulation. The method is based on symbolic (backward) reachability analysis using upward-closed sets of heaps w.r.t. an appropriate preorder on graphs. These sets are represented by a finite set of minimal graph patterns corresponding to a set of bad configurations. We define an abstract semantics for the programs which is monotonic w.r.t. the preorder. Moreover, we prove that our analysis always terminates by showing that the preorder is a well-quasi ordering. Our results are presented for the case of programs with 1-next selector. We provide experimental results showing the effectiveness of our approach.

  • 3.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Delzanno, Giorgio
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Hong, Chih-Duo
    Rezine, Ahmed
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Constrained monotonic abstraction: A CEGAR for parameterized verification2010Inngår i: CONCUR 2010 – Concurrency Theory, Berlin: Springer-Verlag , 2010, s. 86-101Konferansepaper (Fagfellevurdert)
    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.

  • 4.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holik, Lukas
    Brno University.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Linköping University, Department of Computer and Information Science.
    An Integrated Specification and Verification Technique for Highly Concurrent Data Structures2013Inngår i: Tools and Algorithms for the Construction and Analysis of Systems, 2013Konferansepaper (Fagfellevurdert)
    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.

  • 5.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holík, Lukás
    Block me if you can!: Context-sensitive parameterized verification2014Inngår i: Static Analysis: SAS 2014, Springer, 2014, s. 1-17Konferansepaper (Fagfellevurdert)
    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.

  • 6.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holík, Lukás
    Brno Univ Technol, Brno, Czech Republic.
    Parameterized verification through view abstraction2016Inngår i: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 18, nr 5, s. 495-516Artikkel i tidsskrift (Fagfellevurdert)
    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.

  • 7.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holík, Lukáš
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    All for the price of few: (Parameterized verification through view abstraction)2013Inngår i: Verification, Model Checking, and Abstract Interpretation, Springer Berlin/Heidelberg, 2013, s. 476-495Konferansepaper (Fagfellevurdert)
  • 8.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kindahl, Mats
    Model checking race-freeness2008Inngår i: SIGARCH Computer Architecture News, ISSN 0163-5964, E-ISSN 1943-5851, Vol. 36, nr 5, s. 72-79Artikkel i tidsskrift (Fagfellevurdert)
  • 9.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kindahl, Mats
    Model Checking Race-Freeness2008Inngår i: Proc. 1st Swedish Workshop on Multi-Core Computing, 2008, s. 89-96Konferansepaper (Annet vitenskapelig)
  • 10.
    Abdulla, Parosh
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holík, Lukás
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Brno Univ Technol, Brno, Czech Republic..
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Linköping Univ, Linköping, Sweden..
    An integrated specification and verification technique for highly concurrent data structures for highly concurrent data structures2017Inngår i: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 19, nr 5, s. 549-563Artikkel i tidsskrift (Fagfellevurdert)
    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.

  • 11.
    Dahlö, Martin
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Uppsala universitet, Science for Life Laboratory, SciLifeLab.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    Kallio, Aleksi
    Korpelainen, Eija
    Bongcam-Rudloff, Erik
    Spjuth, Ola
    Uppsala universitet, Medicinska och farmaceutiska vetenskapsområdet, Farmaceutiska fakulteten, Institutionen för farmaceutisk biovetenskap. Uppsala universitet, Science for Life Laboratory, SciLifeLab.
    BioImg.org: A catalog of virtual machine images for the life sciences2015Inngår i: Bioinformatics and Biology Insights, ISSN 1177-9322, E-ISSN 1177-9322, Vol. 9, s. 125-128Artikkel i tidsskrift (Fagfellevurdert)
    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.

  • 12.
    Haziza, Frédéric
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datorteknik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis2015Doktoravhandling, med artikler (Annet vitenskapelig)
    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.

    Delarbeid
    1. All for the price of few: (Parameterized verification through view abstraction)
    Åpne denne publikasjonen i ny fane eller vindu >>All for the price of few: (Parameterized verification through view abstraction)
    2013 (engelsk)Inngår i: Verification, Model Checking, and Abstract Interpretation, Springer Berlin/Heidelberg, 2013, s. 476-495Konferansepaper, Publicerat paper (Fagfellevurdert)
    sted, utgiver, år, opplag, sider
    Springer Berlin/Heidelberg, 2013
    Serie
    Lecture Notes in Computer Science ; 7737
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-190003 (URN)10.1007/978-3-642-35873-9_28 (DOI)978-3-642-35872-2 (ISBN)
    Konferanse
    VMCAI 2013, January 20-22, Rome, Italy
    Prosjekter
    UPMARC
    Tilgjengelig fra: 2013-01-09 Laget: 2013-01-07 Sist oppdatert: 2015-11-10bibliografisk kontrollert
    2. An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
    Åpne denne publikasjonen i ny fane eller vindu >>An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
    Vise andre…
    2013 (engelsk)Inngår i: Tools and Algorithms for the Construction and Analysis of Systems, 2013Konferansepaper, Publicerat paper (Fagfellevurdert)
    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.

    Emneord
    verification, pointer program, queue, stack, unbounded concurrency, specification, linearizability
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-191330 (URN)
    Konferanse
    19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 16-24 March, 2013, Rome, ITALY
    Prosjekter
    UPMARC
    Tilgjengelig fra: 2013-01-16 Laget: 2013-01-10 Sist oppdatert: 2018-01-11bibliografisk kontrollert
    3. Block me if you can!: Context-sensitive parameterized verification
    Åpne denne publikasjonen i ny fane eller vindu >>Block me if you can!: Context-sensitive parameterized verification
    2014 (engelsk)Inngår i: Static Analysis: SAS 2014, Springer, 2014, s. 1-17Konferansepaper, Publicerat paper (Fagfellevurdert)
    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.

    sted, utgiver, år, opplag, sider
    Springer, 2014
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 8723
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-260087 (URN)10.1007/978-3-319-10936-7_1 (DOI)000360204700001 ()978-3-319-10935-0 (ISBN)
    Konferanse
    21st International Symposium, SAS 2014, September 11–13, Munich, Germany
    Prosjekter
    UPMARC
    Tilgjengelig fra: 2014-09-13 Laget: 2015-08-15 Sist oppdatert: 2015-12-16bibliografisk kontrollert
    4. Monotonic abstraction for programs with dynamic memory heaps
    Åpne denne publikasjonen i ny fane eller vindu >>Monotonic abstraction for programs with dynamic memory heaps
    Vise andre…
    2008 (engelsk)Inngår i: Computer Aided Verification / [ed] Gupta A, Malik S, Berlin: Springer-Verlag , 2008, s. 341-354Konferansepaper, Publicerat paper (Fagfellevurdert)
    Abstract [en]

    We propose a new approach for automatic verification of programs with dynamic heap manipulation. The method is based on symbolic (backward) reachability analysis using upward-closed sets of heaps w.r.t. an appropriate preorder on graphs. These sets are represented by a finite set of minimal graph patterns corresponding to a set of bad configurations. We define an abstract semantics for the programs which is monotonic w.r.t. the preorder. Moreover, we prove that our analysis always terminates by showing that the preorder is a well-quasi ordering. Our results are presented for the case of programs with 1-next selector. We provide experimental results showing the effectiveness of our approach.

    sted, utgiver, år, opplag, sider
    Berlin: Springer-Verlag, 2008
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 5123
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-106059 (URN)10.1007/978-3-540-70545-1_33 (DOI)000257539900033 ()
    Konferanse
    20th International Conference on Computer Aided Verification Princeton, NJ, JUL 07, 2008
    Tilgjengelig fra: 2009-06-13 Laget: 2009-06-13 Sist oppdatert: 2018-01-13bibliografisk kontrollert
    5. Parameterized tree systems
    Åpne denne publikasjonen i ny fane eller vindu >>Parameterized tree systems
    Vise andre…
    2008 (engelsk)Inngår i: Formal Techniques for Networked and Distributed Systems: FORTE 2008 / [ed] Suzuki K, Berlin: Springer-Verlag , 2008, s. 69-83Konferansepaper, Publicerat paper (Fagfellevurdert)
    Abstract [en]

    Several recent works have considered parameterized verification, i.e. automatic verification of systems consisting of an arbitrary number of finite-state processes organized in a linear array. The aim of this paper is to extend these works by giving a simple and efficient method to prove safety properties for systems with tree-like architectures. A process in the system is a finite-state automaton and a transition is performed jointly by a process and its parent and children processes. The method derives an over-approximation of the induced transition system, which allows the use of finite trees as symbolic representations of infinite sets of configurations. Compared to traditional methods for parameterized verification of systems with tree topologies, our method does not require the manipulation of tree transducers, hence its simplicity and efficiency. We have implemented a prototype which works well on several nontrivial tree-based protocols.

    sted, utgiver, år, opplag, sider
    Berlin: Springer-Verlag, 2008
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 5048
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-106058 (URN)10.1007/978-3-540-68855-6_5 (DOI)000256666500005 ()978-3-540-68854-9 (ISBN)
    Konferanse
    28th International Conference on Formal Techniques for Networked and Distributed Systems Tokyo, JAPAN, JUN 10-13, 2008
    Tilgjengelig fra: 2009-06-13 Laget: 2009-06-13 Sist oppdatert: 2018-01-13bibliografisk kontrollert
    6. Model checking race-freeness
    Åpne denne publikasjonen i ny fane eller vindu >>Model checking race-freeness
    2008 (engelsk)Inngår i: SIGARCH Computer Architecture News, ISSN 0163-5964, E-ISSN 1943-5851, Vol. 36, nr 5, s. 72-79Artikkel i tidsskrift (Fagfellevurdert) Published
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-142914 (URN)10.1145/1556444.1556454 (DOI)
    Tilgjengelig fra: 2011-01-17 Laget: 2011-01-17 Sist oppdatert: 2018-01-12bibliografisk kontrollert
    7. Parameterized verification through view abstraction
    Åpne denne publikasjonen i ny fane eller vindu >>Parameterized verification through view abstraction
    2016 (engelsk)Inngår i: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 18, nr 5, s. 495-516Artikkel i tidsskrift (Fagfellevurdert) 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.

    Emneord
    Parameterized systems; Safety; Small model properties; View abstraction
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-260089 (URN)10.1007/s10009-015-0406-x (DOI)000382011100003 ()
    Prosjekter
    UPMARC
    Tilgjengelig fra: 2015-11-23 Laget: 2015-08-15 Sist oppdatert: 2017-12-04bibliografisk kontrollert
  • 13.
    Haziza, Frédéric
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Biologiska sektionen, Institutionen för cell- och molekylärbiologi, Beräkningsbiologi och bioinformatik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    Holík, Lukás
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Brno Univ Technol, CS-61090 Brno, Czech Republic..
    Meyer, Roland
    Univ Kaiserslautern, D-67663 Kaiserslautern, Germany..
    Wolff, Sebastian
    Univ Kaiserslautern, D-67663 Kaiserslautern, Germany..
    Pointer Race Freedom2016Inngår i: Verification, Model Checking, And Abstract Interpretation, VMCAI 2016, Springer, 2016, s. 393-412Konferansepaper (Fagfellevurdert)
    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.

1 - 13 of 13
RefereraExporteraLink til resultatlisten
Permanent link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf