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

Direct link
Ranking function synthesis for bit-vector relations
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2013 (English)In: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 43, no 1, 93-120 p.Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
2013. Vol. 43, no 1, 93-120 p.
Keyword [en]
Software verification, Ranking functions, Termination, Bit-vectors
National Category
Computer and Information Science
URN: urn:nbn:se:uu:diva-204769DOI: 10.1007/s10703-013-0186-4ISI: 000321223500004OAI: oai:DiVA.org:uu-204769DiVA: diva2:641145
Available from: 2013-08-15 Created: 2013-08-12 Last updated: 2013-08-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Rümmer, Philipp
By organisation
Computer Systems
In the same journal
Formal methods in system design
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 141 hits
ReferencesLink to record
Permanent link

Direct link