Stack size analysis for interrupt-driven programs

K. Chatterjee, D. Ma, R. Majumdar, T. Zhao, T.A. Henzinger, J. Palsberg, Information and Computation 194 (2004) 144–174.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ; ;
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.
Publishing Year
Date Published
2004-08-11
Journal Title
Information and Computation
Volume
194
Issue
2
Page
144 - 174
IST-REx-ID

Cite this

Chatterjee K, Ma D, Majumdar R, Zhao T, Henzinger TA, Palsberg J. Stack size analysis for interrupt-driven programs. Information and Computation. 2004;194(2):144-174. doi:10.1016/j.ic.2004.06.001
Chatterjee, K., Ma, D., Majumdar, R., Zhao, T., Henzinger, T. A., & Palsberg, J. (2004). Stack size analysis for interrupt-driven programs. Information and Computation, 194(2), 144–174. https://doi.org/10.1016/j.ic.2004.06.001
Chatterjee, Krishnendu, Di Ma, Ritankar Majumdar, Tian Zhao, Thomas A Henzinger, and Jens Palsberg. “Stack Size Analysis for Interrupt-Driven Programs.” Information and Computation 194, no. 2 (2004): 144–74. https://doi.org/10.1016/j.ic.2004.06.001.
K. Chatterjee, D. Ma, R. Majumdar, T. Zhao, T. A. Henzinger, and J. Palsberg, “Stack size analysis for interrupt-driven programs,” Information and Computation, vol. 194, no. 2, pp. 144–174, 2004.
Chatterjee K, Ma D, Majumdar R, Zhao T, Henzinger TA, Palsberg J. 2004. Stack size analysis for interrupt-driven programs. Information and Computation. 194(2), 144–174.
Chatterjee, Krishnendu, et al. “Stack Size Analysis for Interrupt-Driven Programs.” Information and Computation, vol. 194, no. 2, Elsevier, 2004, pp. 144–74, doi:10.1016/j.ic.2004.06.001.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar