Skip to main content
Kent Academic Repository

Abstract Interpretation of Microcontroller Code: Intervals meet Congruences

Brauer, Jorg, King, Andy, Kowalewski, Stefan (2013) Abstract Interpretation of Microcontroller Code: Intervals meet Congruences. Science of Computer Programming, 78 (7). pp. 862-883. ISSN 0167-6423. (doi:10.1016/j.scico.2012.06.001) (KAR id:30802)


Bitwise instructions, loops and indirect data access present challenges to the verification of microcontroller programs. In particular, since registers are often memory mapped, it is necessary to show that an indirect store operation does not accidently mutate a register. To prove this and related properties, this article advocates using the domain of bit-wise linear congruences in conjunction with intervals to derive accurate range information. The paper argues that these two domains complement one another when reasoning about microcontroller code. The paper also explains how SAT solving, which applied with dichotomic search, can be used to recover branching conditions from binary code which, in turn, further improves interval analysis.

Item Type: Article
DOI/Identification number: 10.1016/j.scico.2012.06.001
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 21 Sep 2012 09:49 UTC
Last Modified: 16 Nov 2021 10:08 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.