The Experts below are selected from a list of 96 Experts worldwide ranked by ideXlab platform

Denis Poitrenaud - One of the best experts on this subject based on the ideXlab platform.

  • ICATPN - Designing a LTL model-checker based on unfolding graphs
    Lecture Notes in Computer Science, 2000
    Co-Authors: Jean-michel Couvreur, Sébastien Grivet, Denis Poitrenaud
    Abstract:

    International audienceIn this paper, we present new technique designing to solve the on-the-fly model checking problem for linear temporal logic using unfolding graphs [4] and the two key algorithms presented in [2]. Our study is based on the recognition of stuttering behavior in a formula automaton and on the on-the-fly construction of an unfolding graph. Moreover, the characterization of different kinds of behaviors allows us to design efficient algorithms for the detection of accepting paths. We have extended our study to the use of the Atomic Proposition dead which holds for terminal states. Partial order techniques are not adapted to deal with this global property in the context of a LTL model checking

  • Designing a LTL Model-Checker based on Unfolding Graphs
    2000
    Co-Authors: Jean-michel Couvreur, Sébastien Grivet, Denis Poitrenaud
    Abstract:

    In this paper, we present new technique designing to solve the on-the-fly model checking problem for linear temporal logic using unfolding graphs [4] and the two key algorithms presented in [2]. Our study is based on the recognition of stuttering behavior in a formula automaton and on the on-the-fly construction of an unfolding graph. Moreover, the characterization of different kinds of behaviors allows us to design efficient algorithms for the detection of accepting paths. We have extended our study to the use of the Atomic Proposition dead which holds for terminal states. Partial order techniques are not adapted to deal with this global property in the context of a LTL model checking.

Tayssir Touili - One of the best experts on this subject based on the ideXlab platform.

  • IFM - Branching Temporal Logic of Calls and Returns for Pushdown Systems
    Lecture Notes in Computer Science, 2018
    Co-Authors: Huu Vu Nguyen, Tayssir Touili
    Abstract:

    Pushdown Systems (PDSs) are a natural model for sequential programs with (recursive) procedure calls. In this work, we define the Branching temporal logic of CAlls and RETurns (BCARET) that allows to write branching temporal formulas while taking into account the matching between calls and returns. We consider the model-checking problem of PDSs against BCARET formulas with “standard” valuations (where an Atomic Proposition holds at a configuration c or not depends only on the control state of c, not on its stack) as well as regular valuations (where the set of configurations in which an Atomic Proposition holds is regular). We show that these problems can be effectively solved by a reduction to the emptiness problem of Alternating Buchi Pushdown Systems. We show that our results can be applied for malware detection.

  • Branching Temporal Logic of Calls and Returns for Pushdown Systems
    arXiv: Formal Languages and Automata Theory, 2018
    Co-Authors: Huu Vu Nguyen, Tayssir Touili
    Abstract:

    Pushdown Systems (PDSs) are a natural model for sequential programs with (recursive) procedure calls. In this work, we define the Branching temporal logic of CAlls and RETurns (BCARET) that allows to write branching temporal formulas while taking into account the matching between calls and returns. We consider the model-checking problem of PDSs against BCARET formulas with "standard" valuations (where an Atomic Proposition holds at a configuration c or not depends only on the control state of c, not on its stack) as well as regular valuations (where the set of configurations in which an Atomic Proposition holds is regular). We show that these problems can be effectively solved by a reduction to the emptiness problem of Alternating B\"uchi Pushdown Systems. We show that our results can be applied for malware detection.

  • Efficient CTL model-checking for pushdown systems
    Theoretical Computer Science, 2014
    Co-Authors: Fu Song, Tayssir Touili
    Abstract:

    Abstract Pushdown systems (PDS) are well adapted to model sequential programs with (possibly recursive) procedure calls. Therefore, it is important to have efficient model checking algorithms for PDSs. We consider in this paper CTL model checking for PDSs. We consider the “standard” CTL model checking problem where whether a configuration of a PDS satisfies an Atomic Proposition or not depends only on the control state of the configuration. We consider also CTL model checking with regular valuations, where the set of configurations in which an Atomic Proposition holds is a regular language. We reduce these problems to the emptiness problem in Alternating Buchi Pushdown Systems, and we give an algorithm to solve this emptiness problem. Our algorithms are more efficient than the other existing algorithms for CTL model checking for PDSs in the literature. We implemented our techniques in a tool, and we applied it to different case studies. Our results are encouraging. In particular, we were able to confirm the existence of known bugs in Linux source code.

  • CONCUR - Effcient CTL model-checking for pushdown systems
    CONCUR 2011 – Concurrency Theory, 2011
    Co-Authors: Fu Song, Tayssir Touili
    Abstract:

    Pushdown systems (PDS) are well adapted to model sequential programs with (possibly recursive) procedure calls. Therefore, it is important to have efficient model checking algorithms for PDSs. We consider in this paper CTL model checking for PDSs. We consider the "standard" CTL model checking problem where whether a configuration of a PDS satisfies an Atomic Proposition or not depends only on the control state of the configuration. We consider also CTL model checking with regular valuations, where the set of configurations in which an Atomic Proposition holds is a regular language. We reduce these problems to the emptiness problem in Alternating Buchi Pushdown Systems, and we give an algorithm to solve this emptiness problem. Our algorithms are more efficient than the other existing algorithms for CTL model checking for PDSs in the literature. We implemented our techniques in a tool, and we applied it to different case studies. Our results are encouraging. In particular, we were able to find bugs in linux source code.

Stefan Schwoon - One of the best experts on this subject based on the ideXlab platform.

  • Model checking LTL with regular valuations for pushdown systems
    Information and Computation, 2003
    Co-Authors: Javier Esparza, Antonı́n Kučera, Stefan Schwoon
    Abstract:

    AbstractRecent works have proposed pushdown systems as a tool for analyzing programs with (recursive) procedures, and the model-checking problem for LTL has received special attention. However, all these works impose a strong restriction on the possible valuations of Atomic Propositions: whether a configuration of the pushdown system satisfies an Atomic Proposition or not can only depend on the current control state of the pushdown automaton and on its topmost stack symbol. In this paper we consider LTL with regular valuations: the set of configurations satisfying an Atomic Proposition can be an arbitrary regular language. The model-checking problem is solved via two different techniques, with an eye on efficiency. The resulting algorithms are polynomial in certain measures of the problem which are usually small, but can be exponential in the size of the problem instance. However, we show that this exponential blowup is inevitable. The extension to regular valuations allows to model problems in different areas; for instance, we show an application to the analysis of systems with checkpoints. We claim that our model-checking algorithms provide a general, unifying and efficient framework for solving them

  • TACS - Model checking LTL with regular valuations for pushdown systems
    2001
    Co-Authors: Javier Esparza, Antonín Kučera, Stefan Schwoon
    Abstract:

    Recent works have proposed pushdown systems as a tool for analyzing programs with (recursive) procedures, and the model-checking problem for LTL has received special attention. However, all these works impose a strong restriction on the possible valuations of Atomic Propositions: whether a configuration of the pushdown system satisfies an Atomic Proposition or not can only depend on the current control state of the pushdown automaton and on its topmost stack symbol. In this paper we consider LTL with regular valuations: the set of configurations satisfying an Atomic Proposition can be an arbitrary regular language. The model-checking problem is solved via two different techniques, with an eye on efficiency. The resulting algorithms are polynomial in certain measures of the problem which are usually small, but can be exponential in the size of the problem instance. However, we show that this exponential blowup is inevitable. The extension to regular valuations allows to model problems in different areas; for instance, we show an application to the analysis of systems with checkpoints. We claim that our model-checking algorithms provide a general, unifying and efficient framework for solving them.

Jean-michel Couvreur - One of the best experts on this subject based on the ideXlab platform.

  • ICATPN - Designing a LTL model-checker based on unfolding graphs
    Lecture Notes in Computer Science, 2000
    Co-Authors: Jean-michel Couvreur, Sébastien Grivet, Denis Poitrenaud
    Abstract:

    International audienceIn this paper, we present new technique designing to solve the on-the-fly model checking problem for linear temporal logic using unfolding graphs [4] and the two key algorithms presented in [2]. Our study is based on the recognition of stuttering behavior in a formula automaton and on the on-the-fly construction of an unfolding graph. Moreover, the characterization of different kinds of behaviors allows us to design efficient algorithms for the detection of accepting paths. We have extended our study to the use of the Atomic Proposition dead which holds for terminal states. Partial order techniques are not adapted to deal with this global property in the context of a LTL model checking

  • Designing a LTL Model-Checker based on Unfolding Graphs
    2000
    Co-Authors: Jean-michel Couvreur, Sébastien Grivet, Denis Poitrenaud
    Abstract:

    In this paper, we present new technique designing to solve the on-the-fly model checking problem for linear temporal logic using unfolding graphs [4] and the two key algorithms presented in [2]. Our study is based on the recognition of stuttering behavior in a formula automaton and on the on-the-fly construction of an unfolding graph. Moreover, the characterization of different kinds of behaviors allows us to design efficient algorithms for the detection of accepting paths. We have extended our study to the use of the Atomic Proposition dead which holds for terminal states. Partial order techniques are not adapted to deal with this global property in the context of a LTL model checking.

Javier Esparza - One of the best experts on this subject based on the ideXlab platform.

  • Model checking LTL with regular valuations for pushdown systems
    Information and Computation, 2003
    Co-Authors: Javier Esparza, Antonı́n Kučera, Stefan Schwoon
    Abstract:

    AbstractRecent works have proposed pushdown systems as a tool for analyzing programs with (recursive) procedures, and the model-checking problem for LTL has received special attention. However, all these works impose a strong restriction on the possible valuations of Atomic Propositions: whether a configuration of the pushdown system satisfies an Atomic Proposition or not can only depend on the current control state of the pushdown automaton and on its topmost stack symbol. In this paper we consider LTL with regular valuations: the set of configurations satisfying an Atomic Proposition can be an arbitrary regular language. The model-checking problem is solved via two different techniques, with an eye on efficiency. The resulting algorithms are polynomial in certain measures of the problem which are usually small, but can be exponential in the size of the problem instance. However, we show that this exponential blowup is inevitable. The extension to regular valuations allows to model problems in different areas; for instance, we show an application to the analysis of systems with checkpoints. We claim that our model-checking algorithms provide a general, unifying and efficient framework for solving them

  • TACS - Model checking LTL with regular valuations for pushdown systems
    2001
    Co-Authors: Javier Esparza, Antonín Kučera, Stefan Schwoon
    Abstract:

    Recent works have proposed pushdown systems as a tool for analyzing programs with (recursive) procedures, and the model-checking problem for LTL has received special attention. However, all these works impose a strong restriction on the possible valuations of Atomic Propositions: whether a configuration of the pushdown system satisfies an Atomic Proposition or not can only depend on the current control state of the pushdown automaton and on its topmost stack symbol. In this paper we consider LTL with regular valuations: the set of configurations satisfying an Atomic Proposition can be an arbitrary regular language. The model-checking problem is solved via two different techniques, with an eye on efficiency. The resulting algorithms are polynomial in certain measures of the problem which are usually small, but can be exponential in the size of the problem instance. However, we show that this exponential blowup is inevitable. The extension to regular valuations allows to model problems in different areas; for instance, we show an application to the analysis of systems with checkpoints. We claim that our model-checking algorithms provide a general, unifying and efficient framework for solving them.