kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Hoare-Style Logic for Unstructured Programs
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS. Saab AB.ORCID iD: 0000-0001-9921-3257
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0002-8069-6495
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0001-5311-1781
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0001-5432-6442
2020 (English)In: Software Engineering and Formal Methods / [ed] Frank de Boer, Antonio Cerone, Cham: Springer Nature , 2020, p. 193-213Conference paper, Published paper (Refereed)
Abstract [en]

Enabling Hoare-style reasoning for low-level code is attractive since it opens the way to regain structure and modularity in a domain where structure is essentially absent. The field, however, has not yet arrived at a fully satisfactory solution, in the sense of avoiding restrictions on control flow (important for compiler optimization), controlling access to intermediate program points (important for modularity), and supporting total correctness. Proposals in the literature support some of these properties, but a solution that meets them all is yet to be found. We introduce the novel Hoare-style program logic , which interprets postconditions relative to program points when these are first encountered. The logic can support both partial and total correctness, derive contracts for arbitrary control flow, and allows one to freely choose decomposition strategy during verification while avoiding step-indexed approximations and global invariants. The logic can be instantiated for a variety of concrete instruction set architectures and intermediate languages. The rules of  have been verified in the interactive theorem prover HOL4 and integrated with the toolbox HolBA for semi-automated program verification, making it applicable to the ARMv6 and ARMv8 instruction sets.

Place, publisher, year, edition, pages
Cham: Springer Nature , 2020. p. 193-213
Series
LNCS, ISSN 0302-9743, E-ISSN 1611-3349 ; 12310
Keywords [en]
Program logics, Formal verification, Theorem proving, Binary analysis, Hoare Logic
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-281691DOI: 10.1007/978-3-030-58768-0_11ISI: 000722446400011Scopus ID: 2-s2.0-85091597792OAI: oai:DiVA.org:kth-281691DiVA, id: diva2:1469213
Conference
18th International Conference, SEFM 2020, Amsterdam, The Netherlands, September 14–18, 2020
Projects
TrustFullCERCES
Funder
Swedish Foundation for Strategic ResearchSwedish Civil Contingencies Agency
Note

QC 20200921

Available from: 2020-09-21 Created: 2020-09-21 Last updated: 2023-03-30Bibliographically approved

Open Access in DiVA

fulltext(719 kB)822 downloads
File information
File name FULLTEXT01.pdfFile size 719 kBChecksum SHA-512
a18d592808f2ba91b2864f033e8cca7c2778f790a86813a51ca965f583e3bb02b9a57363ff35a490314b8fa02fc99bfe03c9c5b961ad3b5bed8ce6c5bac78659
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Lundberg, DidrikGuanciale, RobertoLindner, AndreasDam, Mads

Search in DiVA

By author/editor
Lundberg, DidrikGuanciale, RobertoLindner, AndreasDam, Mads
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 829 downloads
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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 568 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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