Stack size analysis for interrupt-driven programs Conference Paper


Author(s): Chatterjee, Krishnendu; Ma, Di; Majumdar, Ritankar S; Zhao, Tian; Henzinger, Thomas A; Palsberg, Jens
Title: Stack size analysis for interrupt-driven programs
Title Series: LNCS
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 axe 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 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.
Conference Title: SAS: Static Analysis Symposium
Volume: 2694
Conference Dates: June 11-13, 2003
Conference Location: San Diego, CA, USA
Publisher: Springer  
Location: Berlin, Heidelberg
Date Published: 2003-05-28
Start Page: 109
End Page: 126
DOI: 10.1007/3-540-44898-5_7
Notes: Jens Palsberg, Di Ma, and Tian Zhao were supported by the NSF ITR award 0112628. Thomas A. Henzinger, Krishnendu Chatterjee, and Rupak Majumdar were supported by the AFOSR grant F49620-00-1-0327, the DARPA grants F33615-C-98-3614 and F33615-00-C-1693, the MARCO grant 98-DT-660, and the NSF grants CCR-0208875 and CCR-0085949.
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work