uu.seUppsala University Publications
Change search
Refine search result
12 1 - 50 of 56
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Chen, Yu-Fang
    Bui, Phi Diep
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Holik, Lukas
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Trau: SMT solver for string constraints2018In: Proceedings of the 2018 18th Conference on Formal Methods in Computer Aided Design (FMCAD), IEEE, 2018Conference paper (Refereed)
    Abstract [en]

    We introduce TRAU, an SMT solver for an expressive constraint language, including word equations, length constraints, context-free membership queries, and transducer constraints. The satisfiability problem for such a class of constraints is in general undecidable. The key idea behind TRAU is a technique called flattening, which searches for satisfying assignments that follow simple patterns. TRAU implements a Counter-Example Guided Abstraction Refinement (CEGAR) framework which contains both an under- and an over-approximation module. The approximations are refined in an automatic manner by information flow between the two modules. The technique implemented by TRAU can handle a rich class of string constraints and has better performance than state-of-the-art string solvers.

  • 2.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Chen, Yu-Fang
    Bui, Phi Diep
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Holık, Lukas
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Flatten and Conquer: A Framework for Efficient Analysis of String Constraints2017In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 52, no 6, p. 602-617Article in journal (Refereed)
    Abstract [en]

    We describe a uniform and efficient framework for checking the satisfiability of a large class of string constraints. The framework is based on the observation that both satisfiability and unsatisfiability of common constraints can be demonstrated through witnesses with simple patterns. These patterns are captured using flat automata each of which consists of a sequence of simple loops. We build a Counter-Example Guided Abstraction Refinement (CEGAR) framework which contains both an under-and an over-approximation module. The flow of information between the modules allows to increase the precision in an automatic manner. We have implemented the framework as a tool and performed extensive experimentation that demonstrates both the generality and efficiency of our method.

  • 3.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Chen, Yu-Fang
    Institute of Information Science, Academia Sinica .
    Holik, Lukas
    Brno University.
    Rezine, Ahmed
    Linköping University.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    String Constraints for Verification2014In: Computer Aided Verification - 26th International Conference, {CAV} 2014, Held as Part of the Vienna Summer of Logic, {VSL} 2014, Vienna, Austria, July 18-22, 2014. Proceedings, Springer, 2014, p. 150-166Conference paper (Refereed)
    Abstract [en]

    We present a decision procedure for a logic that combines (i) word equations over string variables denoting words of arbitrary lengths, together with (ii) constraints on the length of words, and on (iii) the regular languages to which words belong. Decidability of this general logic is still open. Our procedure is sound for the general logic, and a decision procedure for a particularly rich fragment that restricts the form in which word equations are written. In contrast to many existing procedures, our method does not make assumptions about the maximum length of words. We have developed a prototypical implementation of our decision procedure, and integrated it into a CEGAR-based model checker for the analysis of programs encoded as Horn clauses. Our tool is able to automatically establish the correctness of several programs that are beyond the reach of existing methods.

  • 4.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Chen, Yu-Fang
    Holík, Lukás
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stenman, Jari
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Norn: An SMT solver for string constraints2015In: Computer Aided Verification: Part I, Springer, 2015, p. 462-469Conference paper (Refereed)
    Abstract [en]

    We present version 1.0 of the Norn SMT solver for string constraints. Norn is a solver for an expressive constraint language, including word equations, length constraints, and regular membership queries. As a feature distinguishing Norn from other SMT solvers, Norn is a decision procedure under the assumption of a set of acyclicity conditions on word equations, without any restrictions on the use of regular membership.

  • 5.
    Arlt, Stephan
    et al.
    Universite du Luxembourg.
    Rubio-Gonzalez, Cindy
    University of California, Berkeley.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schäf, Martin
    SRI International.
    Shankar, Natarajan
    SRI International.
    The Gradual Verifier2014In: NASA Formal Methods: 6th International Symposium, NFM 2014, Houston, TX, USA, April 29 – May 1, 2014. Proceedings, Switzerland, 2014, p. 313-327Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 6. Arlt, Stephan
    et al.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schäf, Martin
    A theory for control-flow graph exploration2013In: Automated Technology for Verification and Analysis: ATVA 2013, Springer Berlin/Heidelberg, 2013, p. 506-515Conference paper (Refereed)
  • 7.
    Backeman, Peter
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Efficient algorithms for bounded rigid E-unification2015In: Automated Reasoning with Analytic Tableaux and Related Methods, Springer, 2015, p. 70-85Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 8.
    Backeman, Peter
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Free variables and theories: Revisiting rigid E-unification2015In: Frontiers of Combining Systems, Springer, 2015, p. 3-13Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 9.
    Backeman, Peter
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Theorem proving with bounded rigid E-unification2015In: Automated Deduction – CADE-25, Springer, 2015, p. 572-587Conference paper (Refereed)
  • 10.
    Backeman, Peter
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Zeljic, Aleksandar
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Bit-Vector Interpolation and Quantifier Elimination by Lazy Reduction2018In: Formal Methods in Computer-Aided Design / [ed] Nikolaj Bjørner, Arie Gurfinkel, IEEE, 2018, p. 50-59Conference paper (Refereed)
    Abstract [en]

    The inference of program invariants over machine arithmetic, commonly called bit-vector arithmetic, is an important problem in verification. Techniques that have been successful for unbounded arithmetic, in particular Craig interpolation, have turned out to be difficult to generalise to machine arithmetic: existing bit-vector interpolation approaches are based either on eager translation from bit-vectors to unbounded arithmetic, resulting in complicated constraints that are hard to solve and interpolate, or on bit-blasting to propositional logic, in the process losing all arithmetic structure. We present a new approach to bitvector interpolation, as well as bit-vector quantifier elimination (QE), that works by lazy translation of bit-vector constraints to unbounded arithmetic. Laziness enables us to fully utilise the information available during proof search (implied by decisions and propagation) in the encoding, and this way produce constraints that can be handled relatively easily by existing interpolation and QE procedures for Presburger arithmetic. The lazy encoding is complemented with a set of native proof rules for bit-vector equations and non-linear (polynomial) constraints, this way minimising the number of cases a solver has to consider

    Download full text (pdf)
    fulltext
  • 11.
    Brain, Martin
    et al.
    Univ Oxford, Dept Comp Sci, Oxford, England.
    Tinelli, Cesare
    Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wahl, Thomas
    Northeastern Univ, Coll Comp & Informat Sci, Boston, MA 02115 USA.
    An automatable formal semantics for IEEE-754 floating-point arithmetic2015In: Proc. 22nd Symposium on Computer Arithmetic / [ed] Muller, JM; Tisserand, A; Villalba, J, IEEE Computer Society, 2015, p. 160-167Conference paper (Refereed)
    Abstract [en]

    Automated reasoning tools often provide little or no support to reason accurately and efficiently about floating-point arithmetic. As a consequence, software verification systems that use these tools are unable to reason reliably about programs containing floating-point calculations or may give unsound results. These deficiencies are in stark contrast to the increasing awareness that the improper use of floating-point arithmetic in programs can lead to unintuitive and harmful defects in software. To promote coordinated efforts towards building efficient and accurate floating-point reasoning engines, this paper presents a formalization of the IEEE-754 standard for floating-point arithmetic as a theory in many-sorted first-order logic. Benefits include a standardized syntax and unambiguous semantics, allowing tool interoperability and sharing of benchmarks, and providing a basis for automated, formal analysis of programs that process floating-point data.

  • 12. Brillout, Angelo
    et al.
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wahl, Thomas
    An interpolating sequent calculus for quantifier-free Presburger arithmetic2011In: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 47, no 4, p. 341-367Article in journal (Refereed)
    Abstract [en]

    Craig interpolation has become a versatile tool in formal verification, used for instance to generate program assertions that serve as candidates for loop invariants. In this paper, we consider Craig interpolation for quantifier-free Presburger arithmetic (QFPA). Until recently, quantifier elimination was the only available interpolation method for this theory, which is, however, known to be potentially costly and inflexible. We introduce an interpolation approach based on a sequent calculus for QFPA that determines interpolants by annotating the steps of an unsatisfiability proof with partial interpolants. We prove our calculus to be sound and complete. We have extended the Princess theorem prover to generate interpolating proofs, and applied it to a large number of publicly available Presburger arithmetic benchmarks. The results document the robustness and efficiency of our interpolation procedure. Finally, we compare the procedure against alternative interpolation methods, both for QFPA and linear rational arithmetic.

  • 13. Brillout, Angelo
    et al.
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wahl, Thomas
    Beyond quantifier-free interpolation in extensions of Presburger arithmetic2011In: Verification, Model Checking, and Abstract Interpretation: VMCAI 2011, Springer Berlin/Heidelberg, 2011, p. 88-102Conference paper (Refereed)
  • 14.
    Chen, Taolue
    et al.
    Birkbeck University of London, UK.
    Hague, Matthew
    Royal Holloway University of London, UK.
    Lin, Anthony W.
    University of Oxford, UK.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wu, Zhilin
    Institute of Software at Chinese Academy of Sciences, China.
    Decision procedures for path feasibility of string-manipulating programs with complex operations2019In: Proceedings of the ACM on Programming Languages, ISSN 2475-1421, Vol. 3, p. 49:1-49:30Article in journal (Refereed)
    Abstract [en]

    The design and implementation of decision procedures for checking path feasibility in string-manipulating programs is an important problem, with such applications as symbolic execution of programs with strings and automated detection of cross-site scripting (XSS) vulnerabilities in web applications. A (symbolic) path is given as a finite sequence of assignments and assertions (i.e. without loops), and checking its feasibility amounts to determining the existence of inputs that yield a successful execution. Modern programming languages (e.g. JavaScript, PHP, and Python) support many complex string operations, and strings are also often implicitly modified during a computation in some intricate fashion (e.g. by some autoescaping mechanisms).

    In this paper we provide two general semantic conditions which together ensure the decidability of path feasibility: (1) each assertion admits regular monadic decomposition (i.e. is an effectively recognisable relation), and (2) each assignment uses a (possibly nondeterministic) function whose inverse relation preserves regularity. We show that the semantic conditions are expressive since they are satisfied by a multitude of string operations including concatenation, one-way and two-way finite-state transducers, replaceall functions (where the replacement string could contain variables), string-reverse functions, regular-expression matching, and some (restricted) forms of letter-counting/length functions. The semantic conditions also strictly subsume existing decidable string theories (e.g. straight-line fragments, and acyclic logics), and most existing benchmarks (e.g. most of Kaluza’s, and all of SLOG’s, Stranger’s, and SLOTH’s benchmarks). Our semantic conditions also yield a conceptually simple decision procedure, as well as an extensible architecture of a string solver in that a user may easily incorporate his/her own string functions into the solver by simply providing code for the pre-image computation without worrying about other parts of the solver. Despite these, the semantic conditions are unfortunately too general to provide a fast and complete decision procedure. We provide strong theoretical evidence for this in the form of complexity results. To rectify this problem, we propose two solutions. Our main solution is to allow only partial string functions (i.e., prohibit nondeterminism) in condition (2). This restriction is satisfied in many cases in practice, and yields decision procedures that are effective in both theory and practice. Whenever nondeterministic functions are still needed (e.g. the string function split), our second solution is to provide a syntactic fragment that provides a support of nondeterministic functions, and operations like one-way transducers, replaceall (with constant replacement string), the string-reverse function, concatenation, and regular-expression matching. We show that this fragment can be reduced to an existing solver SLOTH that exploits fast model checking algorithms like IC3.

    We provide an efficient implementation of our decision procedure (assuming our first solution above, i.e., deterministic partial string functions) in a new string solver OSTRICH. Our implementation provides built-in support for concatenation, reverse, functional transducers (FFT), and replaceall and provides a framework for extensibility to support further string functions. We demonstrate the efficacy of our new solver against other competitive solvers.

    Download full text (pdf)
    fulltext
  • 15. Chen, Yu-Fang
    et al.
    Hong, Chih-Duo
    Lin, Anthony W.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Learning to prove safety over parameterised concurrent systems2017In: Proceedings of the 17th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2017, p. 76-83Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 16. Cook, Byron
    et al.
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wintersteiger, Christoph M.
    Ranking function synthesis for bit-vector relations2013In: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 43, no 1, p. 93-120Article in journal (Refereed)
    Abstract [en]

    Ranking function synthesis is a key component of modern termination provers for imperative programs. While it is well-known how to generate linear ranking functions for relations over (mathematical) integers or rationals, efficient synthesis of ranking functions for machine-level integers (bit-vectors) is an open problem. This is particularly relevant for the verification of low-level code. We propose several novel algorithms to generate ranking functions for relations over machine integers: a complete method based on a reduction to Presburger arithmetic, and a template-matching approach for predefined classes of ranking functions based on reduction to SAT- and QBF-solving. The utility of our algorithms is demonstrated on examples drawn from Windows device drivers.

  • 17.
    Demyanova, Yulia
    et al.
    Vienna University of Technology.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Zuleger, Florian
    Vienna University of Technology.
    Systematic predicate abstraction using variable roles2017In: NASA Formal Methods, Springer, 2017, p. 265-281Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 18. Donaldson, Alastair F.
    et al.
    Haller, Leopold
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Software verification using k-induction2011In: Static Analysis: SAS 2011, Springer Berlin/Heidelberg, 2011, p. 351-368Conference paper (Refereed)
  • 19. Donaldson, Alastair F.
    et al.
    He, Nannan
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Tightening test coverage metrics: A case study in equivalence checking using k-induction2011In: Formal Methods for Components and Objects: FMCO 2010, Springer Berlin/Heidelberg, 2011, p. 297-315Conference paper (Refereed)
  • 20. Donaldson, Alastair F.
    et al.
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    SCRATCH: a tool for automatic analysis of DMA races2011In: Proc. 16th ACM Symposium on Principles and Practice of Parallel Programming, New York: ACM Press, 2011, p. 311-312Conference paper (Refereed)
  • 21. Felsing, Dennis
    et al.
    Grebing, Sarah
    Klebanov, Vladimir
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ulbrich, Mattias
    Automating regression verification2015In: Software Engineering & Management 2015, Germany: Gesellschaft für Informatik , 2015, p. 75-76Conference paper (Refereed)
  • 22.
    Felsing, Dennis
    et al.
    Karlsruhe Institute of Technology, Karlsruhe, Germany.
    Grebing, Sarah
    Karlsruhe Institute of Technology, Karlsruhe, Germany.
    Klebanov, Vladimir
    Karlsruhe Institute of Technology, Karlsruhe, Germany.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ulbrich, Mattias
    Karlsruhe Institute of Technology, Karlsruhe, Germany.
    Automating regression verification2014In: ASE '14 Proceedings of the 29th ACM/IEEE international conference on Automated software engineering, New York: ACM Press, 2014, p. 349-360Conference paper (Refereed)
  • 23.
    Gallagher, John
    et al.
    Roskilde Univ, Roskilde, Denmark.;IMDEA Software Inst, Madrid, Spain..
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Preface, Electronic Proceedings in Theoretical Computer Science. Vol 2192016In: Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180, E-ISSN 2075-2180, no 219Article in journal (Other academic)
  • 24.
    Griggio, Alberto
    et al.
    Fdn Bruno Kessler, Trento, Italy..
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Preface to special issue on satisfiability modulo theories2017In: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 51, no 3, p. 431-432Article in journal (Other academic)
  • 25. He, Nannan
    et al.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Kroening, Daniel
    Test-case generation for embedded Simulink via formal concept analysis2011In: Proc. 48th Design Automation Conference, New York: ACM Press, 2011, p. 224-229Conference paper (Refereed)
  • 26. Hojjat, H.
    et al.
    Iosif, R.
    Konečný, F.
    Kuncak, V.
    Rümmer, Phillipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Accelerating interpolants2012In: Automated Technology for Verification and Analysis: 10th International Symposium, ATVA 2012, Thiruvananthapuram, India, October 3-6, 2012. Proceedings, 2012, p. 187-202Conference paper (Refereed)
    Abstract [en]

    We present Counterexample-Guided Accelerated Abstraction Refinement (CEGAAR), a new algorithm for verifying infinite-state transition systems. CEGAAR combines interpolation-based predicate discovery in counterexample-guided predicate abstraction with acceleration technique for computing the transitive closure of loops. CEGAAR applies acceleration to dynamically discovered looping patterns in the unfolding of the transition system, and combines overapproximation with underapproximation. It constructs inductive invariants that rule out an infinite family of spurious counterexamples, alleviating the problem of divergence in predicate abstraction without losing its adaptive nature. We present theoretical and experimental justification for the effectiveness of CEGAAR, showing that inductive interpolants can be computed from classical Craig interpolants and transitive closures of loops. We present an implementation of CEGAAR that verifies integer transition systems. We show that the resulting implementation robustly handles a number of difficult transition systems that cannot be handled using interpolation-based predicate abstraction or acceleration alone.

  • 27. Hojjat, Hossein
    et al.
    Konecný, Filip
    Garnier, Florent
    Iosif, Radu
    Kuncak, Viktor
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    A verification toolkit for numerical transition systems2012In: FM 2012: Formal Methods, Springer Berlin/Heidelberg, 2012, p. 247-251Conference paper (Refereed)
  • 28.
    Hojjat, Hossein
    et al.
    Rochester Institute of Technology, University of Tehran.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    The ELDARICA Horn Solver2018In: Formal Methods in Computer Aided Design, IEEE, 2018, p. 158-164Conference paper (Refereed)
    Abstract [en]

    This paper presents the ELDARICA version 2 model checker. Over the last years we have been developing and maintaining ELDARICA as a state-of-the-art solver for Horn clauses over integer arithmetic. In the version 2, we have extended the solver to support also algebraic data types and bit-vectors, theories that are commonly applied in verification, but currently unsupported by most Horn solvers. This paper describes the high-level structure of the tool and the interface that it provides to other applications. We also report on an evaluation of the tool. While some of the techniques in ELDARICA have been documented in research papers over the last years, this is the first tool paper describing ELDARICA in its entirety.

    Download full text (pdf)
    fulltext
  • 29.
    Hojjat, Hossein
    et al.
    Cornell Univ, Ithaca, NY 14853 USA..
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    McClurg, Jedidiah
    CU Boulder, Boulder, CO USA..
    Cerny, Pavol
    CU Boulder, Boulder, CO USA..
    Foster, Nate
    Cornell Univ, Ithaca, NY 14853 USA..
    Optimizing Horn Solvers for Network Repair2016In: Proceedings of the 2016 16Th Conference on Formal Methods In Computer-Aided Design (FMCAD 2016) / [ed] Piskac, R Talupur, M, IEEE , 2016, p. 73-80Conference paper (Refereed)
    Abstract [en]

    Automatic program repair modifies a faulty program to make it correct with respect to a specification. Previous approaches have typically been restricted to specific programming languages and a fixed set of syntactical mutation techniques-e.g., changing the conditions of if statements. We present a more general technique based on repairing sets of unsolvable Horn clauses. Working with Horn clauses enables repairing programs from many different source languages, but also introduces challenges, such as navigating the large space of possible repairs. We propose a conservative semantic repair technique that only removes incorrect behaviors and does not introduce new behaviors. Our proposed framework allows the user to request the best repairs-it constructs an optimization lattice representing the space of possible repairs, and uses a novel local search technique that exploits heuristics to avoid searching through sub-lattices with no feasible repairs. To illustrate the applicability of our approach, we apply it to problems in software-defined networking (SDN), and illustrate how it is able to help network operators fix buggy configurations by properly filtering undesired traffic. We show that interval and Boolean lattices are effective choices of optimization lattices in this domain, and we enable optimization objectives such as modifying the minimal number of switches. We have implemented a prototype repair tool, and present preliminary experimental results on several benchmarks using real topologies and realistic repair scenarios in data centers and congested networks.

  • 30. Hojjat, Hossein
    et al.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Shamakhi, Ali
    On Strings in Software Model Checking2019In: Programming Languages and Systems - 17th Asian Symposium, APLAS 2019, Nusa Dua, Bali, Indonesia, December 1-4, 2019, Proceedings, Cham, 2019, Vol. 11893, p. 19-30Conference paper (Other academic)
  • 31.
    Hojjat, Hossein
    et al.
    Cornell University, USA.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Subotic, Pavle
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wang, Yi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Horn Clauses for Communicating Timed Systems2014In: Proceedings First Workshop on Horn Clauses for Verification and Synthesis, 2014, p. 39-52Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 32.
    Holik, Lukas
    et al.
    Brno University of Technology, Czech Republic.
    Janku, Petr
    Brno University of Technology, Czech Republic.
    Lin, Anthony W.
    University of Oxford, United Kingdom.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Vojnar, Tomas
    Brno University of Technology, Czech Republic.
    String constraints with concatenation and transducers solved efficiently2018In: Proceedings of the ACM on Programming Languages, E-ISSN 2475-1421, Vol. 2, p. 1-32, article id 4Article in journal (Refereed)
    Abstract [en]

    String analysis is the problem of reasoning about how strings are manipulated by a program. It has numerous applications including automatic detection of cross-site scripting, and automatic test-case generation. A popular string analysis technique includes symbolic executions, which at their core use constraint solvers over the string domain, a.k.a. string solvers. Such solvers typically reason about constraints expressed in theories over strings with the concatenation operator as an atomic constraint. In recent years, researchers started to recognise the importance of incorporating the replace-all operator (i.e. replace all occurrences of a string by another string) and, more generally, finite-state transductions in the theories of strings with concatenation. Such string operations are typically crucial for reasoning about XSS vulnerabilities in web applications, especially for modelling sanitisation functions and implicit browser transductions (e.g. innerHTML). Although this results in an undecidable theory in general, it was recently shown that the straight-line fragment of the theory is decidable, and is sufficiently expressive in practice. In this paper, we provide the first string solver that can reason about constraints involving both concatenation and finite-state transductions. Moreover, it has a completeness and termination guarantee for several important fragments (e.g. straight-line fragment). The main challenge addressed in the paper is the prohibitive worst-case complexity of the theory (double-exponential time), which is exponentially harder than the case without finite-state transductions. To this end, we propose a method that exploits succinct alternating finite-state automata as concise symbolic representations of string constraints. In contrast to previous approaches using nondeterministic automata, alternation offers not only exponential savings in space when representing Boolean combinations of transducers, but also a possibility of succinct representation of otherwise costly combinations of transducers and concatenation. Reasoning about the emptiness of the AFA language requires a state-space exploration in an exponential-sized graph, for which we use model checking algorithms (e.g. IC3). We have implemented our algorithm and demonstrated its efficacy on benchmarks that are derived from cross-site scripting analysis and other examples in the literature.

    Download full text (pdf)
    fulltext
  • 33.
    Hong, Chih-Duo
    et al.
    Univ Oxford, Oxford, England.
    Lin, Anthony W.
    TU Kaiserslautern, Kaiserslautern, Germany.
    Majumdar, Rupak
    Max Planck Inst Software Syst, Kaiserslautern, Germany.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Probabilistic Bisimulation for Parameterized Systems: (with Applications to Verifying Anonymous Protocols)2019In: Computer Aided Verification. CAV 2019., Cham, 2019, Vol. 11561, p. 455-474Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 34.
    Kahsai, Temesghen
    et al.
    Carnegie Mellon University, Silicon Valley; NASA Ames.
    Kersten, Rody
    Carnegie Mellon University, Silicon Valley.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schäf, Martin
    SRI International.
    Quantified heap invariants for object-oriented programs2017In: 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 2017, p. 368-384Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 35.
    Kahsai, Temesghen
    et al.
    Nasa Ames CMU, Moffett Field, CA USA.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Sanchez, Huascar
    SRI Int, 333 Ravenswood Ave, Menlo Pk, CA 94025 USA.
    Schäf, Martin
    SRI Int, 333 Ravenswood Ave, Menlo Pk, CA 94025 USA.
    JayHorn: A framework for verifying Java programs2016In: Computer Aided Verification: Part I, Springer, 2016, p. 352-358Conference paper (Refereed)
    Abstract [en]

    Building a competitive program verifiers is becoming cheaper. On the front-end side, openly available compiler infrastructure and optimization frameworks take care of hairy problems such as alias analysis, and break down the subtleties of modern languages into a handful of simple instructions that need to be handled. On the back-end side, theorem provers start providing full-fledged model checking algorithms, such as PDR, that take care looping control-flow. In this spirit, we developed JayHorn, a verification framework for Java with the goal of having as few moving parts as possible. Most steps of the translation from Java into logic are implemented as bytecode transformations, with the implication that their soundness can be tested easily. From the transformed bytecode, we generate a set of constrained Horn clauses that are verified using state-of-the-art Horn solvers. We report on our implementation experience and evaluate JayHorn on benchmarks.

    Download full text (pdf)
    fulltext
  • 36. Kahsai, Temesghen
    et al.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schäf, Martin
    JayHorn: A Java Model Checker -: (Competition Contribution)2019In: Tools and Algorithms for the Construction and Analysis of Systems / [ed] Beyer D., Huisman M., Kordon F., Steffen B., Cham: Springer, 2019, Vol. 11429, p. 214-218Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 37.
    Klebanov, Vladimir
    et al.
    Karlsruhe Inst Technol, Inst Theoret Informat, Karlsruhe, Germany.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ulbrich, Mattias
    Karlsruhe Inst Technol, Inst Theoret Informat, Karlsruhe, Germany.
    Automating regression verification of pointer programs by predicate abstraction2018In: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 52, no 3, p. 229-259Article in journal (Refereed)
    Abstract [en]

    Regression verification is an approach complementing regression testing with formal verification. The goal is to formally prove that two versions of a program behave either equally or differently in a precisely specified way. In this paper, we present a novel automated approach for regression verification that reduces the equivalence of two related imperative pointer programs to constrained Horn clauses over uninterpreted predicates. Subsequently, state-of-the-art SMT solvers are used to solve the clauses. We have implemented the approach, and our experiments show that non-trivial programs with integer and pointer arithmetic can now be proved equivalent without further user input.

    Download full text (pdf)
    fulltext
  • 38.
    Lengál, Ondrej
    et al.
    FIT, Brno University of Technology, Czech Republic.
    Lin, Anthony W.
    Department of Computer Science, University of Oxford, UK.
    Majumdar, Rupak
    MPI-SWS Kaiserslautern, Germany.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Fair termination for parameterized probabilistic concurrent systems2017In: Tools and Algorithms for the Construction and Analysis of Systems: Part I, Springer, 2017, p. 499-517Conference paper (Refereed)
    Abstract [en]

    We consider the problem of automatically verifying that a parameterized family of probabilistic concurrent systems terminates with probability one for all instances against adversarial schedulers. A parameterized family defines an infinite-state system: for each number n, the family consists of an instance with n finite-state processes. In contrast to safety, the parameterized verification of liveness is currently still considered extremely challenging especially in the presence of probabilities in the model. One major challenge is to provide a sufficiently powerful symbolic framework. One well-known symbolic framework for the parameterized verification of non-probabilistic concurrent systems is regular model checking. Although the framework was recently extended to probabilistic systems, incorporating fairness in the framework-often crucial for verifying termination-has been especially difficult due to the presence of an infinite number of fairness constraints (one for each process). Our main contribution is a systematic, regularity-preserving, encoding of finitary fairness (a realistic notion of fairness proposed by Alur and Henzinger) in the framework of regular model checking for probabilistic parameterized systems. Our encoding reduces termination with finitary fairness to verifying parameterized termination without fairness over probabilistic systems in regular model checking (for which a verification framework already exists). We show that our algorithm could verify termination for many interesting examples from distributed algorithms (Herman's protocol) and evolutionary biology (Moran process, cell cycle switch), which do not hold under the standard notion of fairness. To the best of our knowledge, our algorithm is the first fully-automatic method that can prove termination for these examples.

    Download full text (pdf)
    fulltext
  • 39. Leroux, Jérôme
    et al.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Subotic, Pavle
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guiding Craig interpolation with domain-specific abstractions2016In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 53, no 4, p. 387-424Article in journal (Refereed)
    Abstract [en]

    Craig interpolation is a standard method to construct and refine abstractions in model checking. To obtain abstractions that are suitable for the verification of software programs or hardware designs, model checkers rely on theorem provers to find the right interpolants, or interpolants containing the right predicates, in a generally infinite lattice of interpolants for any given interpolation problem. We present a semantic and solver-independent framework for systematically exploring interpolant lattices, based on the notion of interpolation abstraction. We discuss how interpolation abstractions can be constructed for a variety of logics, and how they can be applied in the context of software model checking.

    Download full text (pdf)
    fulltext
  • 40. Lin, Anthony W.
    et al.
    Nguyen, Truong Khanh
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Sun, Jun
    Regular Symmetry Patterns2016In: Verification, Model Checking, and Abstract Interpretation, Springer Berlin/Heidelberg, 2016, p. 455-475Conference paper (Refereed)
    Abstract [en]

    Symmetry reduction is a well-known approach for alleviating the state explosion problem in model checking. Automatically identifying symmetries in concurrent systems, however, is computationally expensive. We propose a symbolic framework for capturing symmetry patterns in parameterised systems (i.e. an infinite family of finite-state systems): two regular word transducers to represent, respectively, parameterised systems and symmetry patterns. The framework subsumes various types of "symmetry relations" ranging from weaker notions (e.g. simulation preorders) to the strongest notion (i.e. isomorphisms). Our framework enjoys two algorithmic properties: (1) symmetry verification: given a transducer, we can automatically check whether it is a symmetry pattern of a given system, and (2) symmetry synthesis: we can automatically generate a symmetry pattern for a given system in the form of a transducer. Furthermore, our symbolic language allows additional constraints that the symmetry patterns need to satisfy to be easily incorporated in the verification/synthesis. We show how these properties can help identify symmetry patterns in examples like dining philosopher protocols, self-stabilising protocols, and prioritised resource-allocator protocol. In some cases (e.g. Gries's coffee can problem), our technique automatically synthesises a safety-preserving finite approximant, which can then be verified for safety solely using a finite-state model checker.

    Download full text (pdf)
    fulltext
  • 41.
    Lin, Anthony W.
    et al.
    Yale NUS Coll, Singapore, Singapore.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Liveness of randomised parameterised systems under arbitrary schedulers2016In: Computer Aided Verification: Part II, Springer, 2016, p. 112-133Conference paper (Refereed)
    Download full text (pdf)
    fulltext
  • 42.
    McCarthy, Tim
    et al.
    SRI Int, 333 Ravenswood Ave, Menlo Pk, CA 94025 USA.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schäf, Martin
    SRI Int, 333 Ravenswood Ave, Menlo Pk, CA 94025 USA.
    Bixie: Finding and understanding inconsistent code2015In: Proc. 37th IEEE/ACM International Conference on Software Engineering, Piscataway, NJ: IEEE , 2015, Vol. 2, p. 645-648Conference paper (Refereed)
    Abstract [en]

    We present Bixie, a tool to detect inconsistencies in Java code. Bixie detects inconsistent code at a higher precision than previous tools and provides novel fault localization techniques to explain why code is inconsistent. We demonstrate the usefulness of Bixie on over one million lines of code, show that it can detect inconsistencies at a low false alarm rate, and fix a number of inconsistencies in popular open-source projects. Watch our Demo at http://youtu.be/QpsoUBJMxhk.

  • 43.
    Panda, Anmol
    et al.
    BITS Pilani KK Birla Goa Campus, Dept Comp Sci & Informat Syst, Sancoale, Goa, India..
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Goveas, Neena
    BITS Pilani KK Birla Goa Campus, Dept Comp Sci & Informat Syst, Sancoale, Goa, India..
    A Comparative Study of GPUVerify and GKLEE2016In: 2016 Fourth International Conference On Parallel, Distributed And Grid Computing (PDGC) / [ed] Kumar, P Singh, AK, IEEE , 2016, p. 112-117Conference paper (Refereed)
    Abstract [en]

    Use of Graphics Processing Unit (CPU) software is increasing due to the need for data intensive operations and availability of GPUs. This has led to a need for effective GPU software verification tools. These tools have to satisfy requirements such as accuracy, reliability and ease of use. In this work, we have considered two such tools: GPUVerify and GKLEE. Our objectives were to learn about the common challenges developers faced in GPU programming, to understand the specific bugs that these two tools report and compare their scope and scalability aspects. We have also considered usability and learnability aspects. In order to test the software, twenty-six benchmarks were selected from open-source applications. These benchmarks were then verified using the tools and the results documented and analysed. The conclusions have been included in the final section.

  • 44. Piskac, Ruzica
    et al.
    Rümmer, PhilippUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Verified Software. Theories, Tools, and Experiments: Revised Selected Papers2018Conference proceedings (editor) (Refereed)
  • 45.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    E-matching with free variables2012In: Logic for Programming, Artificial Intelligence, and Reasoning, Springer Berlin/Heidelberg, 2012, p. 359-374Conference paper (Refereed)
  • 46.
    Rümmer, Philipp
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    JayHorn: A Java Model Checker2019In: PROCEEDINGS OF THE 21ST WORKSHOP ON FORMAL TECHNIQUES FOR JAVA-LIKE PROGRAMS (FTFJP 2019), ASSOC COMPUTING MACHINERY , 2019, article id 1Conference paper (Refereed)
    Abstract [en]

    This talk will give an overview of the JayHorn verification tool, a model checker for sequential Java programs annotated with assertions expressing safety conditions. JayHorn is fully automatic and based to a large degree on standard infrastructure for compilation and verification: it uses the Soot library as front-end to read Java bytecode and translate it to the Jimple three-address format, and the state-of-the-art Horn solvers SPACER and Eldarica as back-ends that infer loop invariants, object and class invariants, and method contracts. Since JayHorn uses an invariant-based representation of heap data-structures, it is particularly useful for analysing programs with unbounded data-structures and unbounded run-time, while at the same time avoiding the use of logical theories, like the theory of arrays, often considered hard for Horn solvers. The development of JayHorn is ongoing, and the talk will also cover some of the future features of JayHorn, in particular the handling of strings.

  • 47.
    Rümmer, Philipp
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Hojjat, Hossein
    Kuncak, Viktor
    Classifying and Solving Horn Clauses for Verification2013In: Fifth Working Conference on Verified Software: Theories, Tools and Experiments (VSTTE), 2013Conference paper (Refereed)
  • 48.
    Rümmer, Philipp
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Hojjat, Hossein
    Kuncak, Viktor
    Disjunctive Interpolants for Horn-Clause Verification2013In: Computer Aided Verification: CAV 2013, Springer Berlin/Heidelberg, 2013, p. 347-363Conference paper (Refereed)
  • 49.
    Rümmer, Philipp
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Hojjat, Hossein
    Kuncak, Viktor
    On recursion-free Horn clauses and Craig interpolation2015In: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 47, no 1, p. 1-25Article in journal (Refereed)
  • 50.
    Rümmer, Philipp
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Subotic, Pavle
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Exploring Interpolants2013In: Formal Methods in Computer-Aided Design (FMCAD), 2013Conference paper (Refereed)
12 1 - 50 of 56
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf