uu.seUppsala universitets publikasjoner
Endre søk
Begrens søket
12 1 - 50 of 56
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.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Bui, Phi Diep
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holik, Lukas
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Trau: SMT solver for string constraints2018Inngår i: Proceedings of the 2018 18th Conference on Formal Methods in Computer Aided Design (FMCAD), IEEE, 2018Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Bui, Phi Diep
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Holık, Lukas
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Flatten and Conquer: A Framework for Efficient Analysis of String Constraints2017Inngår i: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 52, nr 6, s. 602-617Artikkel i tidsskrift (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Institute of Information Science, Academia Sinica .
    Holik, Lukas
    Brno University.
    Rezine, Ahmed
    Linköping University.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    String Constraints for Verification2014Inngår i: 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, s. 150-166Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Holík, Lukás
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Stenman, Jari
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Norn: An SMT solver for string constraints2015Inngår i: Computer Aided Verification: Part I, Springer, 2015, s. 462-469Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Schäf, Martin
    SRI International.
    Shankar, Natarajan
    SRI International.
    The Gradual Verifier2014Inngår i: NASA Formal Methods: 6th International Symposium, NFM 2014, Houston, TX, USA, April 29 – May 1, 2014. Proceedings, Switzerland, 2014, s. 313-327Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 6. Arlt, Stephan
    et al.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Schäf, Martin
    A theory for control-flow graph exploration2013Inngår i: Automated Technology for Verification and Analysis: ATVA 2013, Springer Berlin/Heidelberg, 2013, s. 506-515Konferansepaper (Fagfellevurdert)
  • 7.
    Backeman, Peter
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Efficient algorithms for bounded rigid E-unification2015Inngår i: Automated Reasoning with Analytic Tableaux and Related Methods, Springer, 2015, s. 70-85Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 8.
    Backeman, Peter
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Free variables and theories: Revisiting rigid E-unification2015Inngår i: Frontiers of Combining Systems, Springer, 2015, s. 3-13Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 9.
    Backeman, Peter
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Theorem proving with bounded rigid E-unification2015Inngår i: Automated Deduction – CADE-25, Springer, 2015, s. 572-587Konferansepaper (Fagfellevurdert)
  • 10.
    Backeman, Peter
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Zeljic, Aleksandar
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Bit-Vector Interpolation and Quantifier Elimination by Lazy Reduction2018Inngår i: Formal Methods in Computer-Aided Design / [ed] Nikolaj Bjørner, Arie Gurfinkel, IEEE, 2018, s. 50-59Konferansepaper (Fagfellevurdert)
    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

    Fulltekst (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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wahl, Thomas
    Northeastern Univ, Coll Comp & Informat Sci, Boston, MA 02115 USA.
    An automatable formal semantics for IEEE-754 floating-point arithmetic2015Inngår i: Proc. 22nd Symposium on Computer Arithmetic / [ed] Muller, JM; Tisserand, A; Villalba, J, IEEE Computer Society, 2015, s. 160-167Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wahl, Thomas
    An interpolating sequent calculus for quantifier-free Presburger arithmetic2011Inngår i: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 47, nr 4, s. 341-367Artikkel i tidsskrift (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wahl, Thomas
    Beyond quantifier-free interpolation in extensions of Presburger arithmetic2011Inngår i: Verification, Model Checking, and Abstract Interpretation: VMCAI 2011, Springer Berlin/Heidelberg, 2011, s. 88-102Konferansepaper (Fagfellevurdert)
  • 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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wu, Zhilin
    Institute of Software at Chinese Academy of Sciences, China.
    Decision procedures for path feasibility of string-manipulating programs with complex operations2019Inngår i: Proceedings of the ACM on Programming Languages, ISSN 2475-1421, Vol. 3, s. 49:1-49:30Artikkel i tidsskrift (Fagfellevurdert)
    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.

    Fulltekst (pdf)
    fulltext
  • 15. Chen, Yu-Fang
    et al.
    Hong, Chih-Duo
    Lin, Anthony W.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Learning to prove safety over parameterised concurrent systems2017Inngår i: Proceedings of the 17th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2017, s. 76-83Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 16. Cook, Byron
    et al.
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wintersteiger, Christoph M.
    Ranking function synthesis for bit-vector relations2013Inngår i: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 43, nr 1, s. 93-120Artikkel i tidsskrift (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Zuleger, Florian
    Vienna University of Technology.
    Systematic predicate abstraction using variable roles2017Inngår i: NASA Formal Methods, Springer, 2017, s. 265-281Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 18. Donaldson, Alastair F.
    et al.
    Haller, Leopold
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Software verification using k-induction2011Inngår i: Static Analysis: SAS 2011, Springer Berlin/Heidelberg, 2011, s. 351-368Konferansepaper (Fagfellevurdert)
  • 19. Donaldson, Alastair F.
    et al.
    He, Nannan
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Tightening test coverage metrics: A case study in equivalence checking using k-induction2011Inngår i: Formal Methods for Components and Objects: FMCO 2010, Springer Berlin/Heidelberg, 2011, s. 297-315Konferansepaper (Fagfellevurdert)
  • 20. Donaldson, Alastair F.
    et al.
    Kroening, Daniel
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    SCRATCH: a tool for automatic analysis of DMA races2011Inngår i: Proc. 16th ACM Symposium on Principles and Practice of Parallel Programming, New York: ACM Press, 2011, s. 311-312Konferansepaper (Fagfellevurdert)
  • 21. Felsing, Dennis
    et al.
    Grebing, Sarah
    Klebanov, Vladimir
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ulbrich, Mattias
    Automating regression verification2015Inngår i: Software Engineering & Management 2015, Germany: Gesellschaft für Informatik , 2015, s. 75-76Konferansepaper (Fagfellevurdert)
  • 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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ulbrich, Mattias
    Karlsruhe Institute of Technology, Karlsruhe, Germany.
    Automating regression verification2014Inngår i: ASE '14 Proceedings of the 29th ACM/IEEE international conference on Automated software engineering, New York: ACM Press, 2014, s. 349-360Konferansepaper (Fagfellevurdert)
  • 23.
    Gallagher, John
    et al.
    Roskilde Univ, Roskilde, Denmark.;IMDEA Software Inst, Madrid, Spain..
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Preface, Electronic Proceedings in Theoretical Computer Science. Vol 2192016Inngår i: Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180, E-ISSN 2075-2180, nr 219Artikkel i tidsskrift (Annet vitenskapelig)
  • 24.
    Griggio, Alberto
    et al.
    Fdn Bruno Kessler, Trento, Italy..
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Preface to special issue on satisfiability modulo theories2017Inngår i: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 51, nr 3, s. 431-432Artikkel i tidsskrift (Annet vitenskapelig)
  • 25. He, Nannan
    et al.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kroening, Daniel
    Test-case generation for embedded Simulink via formal concept analysis2011Inngår i: Proc. 48th Design Automation Conference, New York: ACM Press, 2011, s. 224-229Konferansepaper (Fagfellevurdert)
  • 26. Hojjat, H.
    et al.
    Iosif, R.
    Konečný, F.
    Kuncak, V.
    Rümmer, Phillipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Accelerating interpolants2012Inngår i: Automated Technology for Verification and Analysis: 10th International Symposium, ATVA 2012, Thiruvananthapuram, India, October 3-6, 2012. Proceedings, 2012, s. 187-202Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    A verification toolkit for numerical transition systems2012Inngår i: FM 2012: Formal Methods, Springer Berlin/Heidelberg, 2012, s. 247-251Konferansepaper (Fagfellevurdert)
  • 28.
    Hojjat, Hossein
    et al.
    Rochester Institute of Technology, University of Tehran.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    The ELDARICA Horn Solver2018Inngår i: Formal Methods in Computer Aided Design, IEEE, 2018, s. 158-164Konferansepaper (Fagfellevurdert)
    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.

    Fulltekst (pdf)
    fulltext
  • 29.
    Hojjat, Hossein
    et al.
    Cornell Univ, Ithaca, NY 14853 USA..
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    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 Repair2016Inngår i: Proceedings of the 2016 16Th Conference on Formal Methods In Computer-Aided Design (FMCAD 2016) / [ed] Piskac, R Talupur, M, IEEE , 2016, s. 73-80Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Shamakhi, Ali
    On Strings in Software Model Checking2019Inngår i: Programming Languages and Systems - 17th Asian Symposium, APLAS 2019, Nusa Dua, Bali, Indonesia, December 1-4, 2019, Proceedings, Cham, 2019, Vol. 11893, s. 19-30Konferansepaper (Annet vitenskapelig)
  • 31.
    Hojjat, Hossein
    et al.
    Cornell University, USA.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Subotic, Pavle
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wang, Yi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Horn Clauses for Communicating Timed Systems2014Inngår i: Proceedings First Workshop on Horn Clauses for Verification and Synthesis, 2014, s. 39-52Konferansepaper (Fagfellevurdert)
    Fulltekst (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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Vojnar, Tomas
    Brno University of Technology, Czech Republic.
    String constraints with concatenation and transducers solved efficiently2018Inngår i: Proceedings of the ACM on Programming Languages, E-ISSN 2475-1421, Vol. 2, s. 1-32, artikkel-id 4Artikkel i tidsskrift (Fagfellevurdert)
    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.

    Fulltekst (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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Probabilistic Bisimulation for Parameterized Systems: (with Applications to Verifying Anonymous Protocols)2019Inngår i: Computer Aided Verification. CAV 2019., Cham, 2019, Vol. 11561, s. 455-474Konferansepaper (Fagfellevurdert)
    Fulltekst (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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Schäf, Martin
    SRI International.
    Quantified heap invariants for object-oriented programs2017Inngår i: 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 2017, s. 368-384Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 35.
    Kahsai, Temesghen
    et al.
    Nasa Ames CMU, Moffett Field, CA USA.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    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 programs2016Inngår i: Computer Aided Verification: Part I, Springer, 2016, s. 352-358Konferansepaper (Fagfellevurdert)
    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.

    Fulltekst (pdf)
    fulltext
  • 36. Kahsai, Temesghen
    et al.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Schäf, Martin
    JayHorn: A Java Model Checker -: (Competition Contribution)2019Inngår i: Tools and Algorithms for the Construction and Analysis of Systems / [ed] Beyer D., Huisman M., Kordon F., Steffen B., Cham: Springer, 2019, Vol. 11429, s. 214-218Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 37.
    Klebanov, Vladimir
    et al.
    Karlsruhe Inst Technol, Inst Theoret Informat, Karlsruhe, Germany.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ulbrich, Mattias
    Karlsruhe Inst Technol, Inst Theoret Informat, Karlsruhe, Germany.
    Automating regression verification of pointer programs by predicate abstraction2018Inngår i: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 52, nr 3, s. 229-259Artikkel i tidsskrift (Fagfellevurdert)
    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.

    Fulltekst (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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Fair termination for parameterized probabilistic concurrent systems2017Inngår i: Tools and Algorithms for the Construction and Analysis of Systems: Part I, Springer, 2017, s. 499-517Konferansepaper (Fagfellevurdert)
    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.

    Fulltekst (pdf)
    fulltext
  • 39. Leroux, Jérôme
    et al.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Subotic, Pavle
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Guiding Craig interpolation with domain-specific abstractions2016Inngår i: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 53, nr 4, s. 387-424Artikkel i tidsskrift (Fagfellevurdert)
    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.

    Fulltekst (pdf)
    fulltext
  • 40. Lin, Anthony W.
    et al.
    Nguyen, Truong Khanh
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Sun, Jun
    Regular Symmetry Patterns2016Inngår i: Verification, Model Checking, and Abstract Interpretation, Springer Berlin/Heidelberg, 2016, s. 455-475Konferansepaper (Fagfellevurdert)
    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.

    Fulltekst (pdf)
    fulltext
  • 41.
    Lin, Anthony W.
    et al.
    Yale NUS Coll, Singapore, Singapore.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Liveness of randomised parameterised systems under arbitrary schedulers2016Inngår i: Computer Aided Verification: Part II, Springer, 2016, s. 112-133Konferansepaper (Fagfellevurdert)
    Fulltekst (pdf)
    fulltext
  • 42.
    McCarthy, Tim
    et al.
    SRI Int, 333 Ravenswood Ave, Menlo Pk, CA 94025 USA.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Schäf, Martin
    SRI Int, 333 Ravenswood Ave, Menlo Pk, CA 94025 USA.
    Bixie: Finding and understanding inconsistent code2015Inngår i: Proc. 37th IEEE/ACM International Conference on Software Engineering, Piscataway, NJ: IEEE , 2015, Vol. 2, s. 645-648Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Goveas, Neena
    BITS Pilani KK Birla Goa Campus, Dept Comp Sci & Informat Syst, Sancoale, Goa, India..
    A Comparative Study of GPUVerify and GKLEE2016Inngår i: 2016 Fourth International Conference On Parallel, Distributed And Grid Computing (PDGC) / [ed] Kumar, P Singh, AK, IEEE , 2016, s. 112-117Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Verified Software. Theories, Tools, and Experiments: Revised Selected Papers2018Konferanseproceedings (Fagfellevurdert)
  • 45.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    E-matching with free variables2012Inngår i: Logic for Programming, Artificial Intelligence, and Reasoning, Springer Berlin/Heidelberg, 2012, s. 359-374Konferansepaper (Fagfellevurdert)
  • 46.
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    JayHorn: A Java Model Checker2019Inngår i: PROCEEDINGS OF THE 21ST WORKSHOP ON FORMAL TECHNIQUES FOR JAVA-LIKE PROGRAMS (FTFJP 2019), ASSOC COMPUTING MACHINERY , 2019, artikkel-id 1Konferansepaper (Fagfellevurdert)
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Hojjat, Hossein
    Kuncak, Viktor
    Classifying and Solving Horn Clauses for Verification2013Inngår i: Fifth Working Conference on Verified Software: Theories, Tools and Experiments (VSTTE), 2013Konferansepaper (Fagfellevurdert)
  • 48.
    Rümmer, Philipp
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Hojjat, Hossein
    Kuncak, Viktor
    Disjunctive Interpolants for Horn-Clause Verification2013Inngår i: Computer Aided Verification: CAV 2013, Springer Berlin/Heidelberg, 2013, s. 347-363Konferansepaper (Fagfellevurdert)
  • 49.
    Rümmer, Philipp
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Hojjat, Hossein
    Kuncak, Viktor
    On recursion-free Horn clauses and Craig interpolation2015Inngår i: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 47, nr 1, s. 1-25Artikkel i tidsskrift (Fagfellevurdert)
  • 50.
    Rümmer, Philipp
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Subotic, Pavle
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Exploring Interpolants2013Inngår i: Formal Methods in Computer-Aided Design (FMCAD), 2013Konferansepaper (Fagfellevurdert)
12 1 - 50 of 56
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