Stack size analysis for interrupt-driven programs Journal Article


Author(s): Chatterjee, Krishnendu; Ma, Di; Majumdar, Ritankar S; Zhao, Tian; Henzinger, Thomas A; Palsberg, Jens
Article Title: Stack size analysis for interrupt-driven programs
Affiliation
Abstract: We study the problem of determining stack boundedness and the exact maximum stack size for three classes of interrupt-driven programs. Interrupt-driven programs are used in many real-time applications that require responsive interrupt handling. In order to ensure responsiveness, programmers often enable interrupt processing in the body of lower-priority interrupt handlers. In such programs a programming error can allow interrupt handlers to be interrupted in a cyclic fashion to lead to an unbounded stack, causing the system to crash. For a restricted class of interrupt-driven programs, we show that there is a polynomial-time procedure to check stack boundedness, while determining the exact maximum stack size is PSPACE-complete. For a larger class of programs, the two problems are both PSPACE-complete, and for the largest class of programs we consider, the two problems are PSPACE-hard and can be solved in exponential time. While the complexities are high, our algorithms are exponential only in the number of handlers, and polynomial in the size of the program.
Keywords: program analysis; stack bounds; interrupt programs
Journal Title: Information and Computation
Volume: 194
Issue 2
ISSN: 0890-5401
Publisher: Elsevier  
Date Published: 2004-08-11
Start Page: 144
End Page: 174
DOI: 10.1016/j.ic.2004.06.001
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work