---
OA_type: closed access
_id: '3898'
abstract:
- lang: eng
  text: 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.
alternative_title:
- Lecture Notes in Computer Science
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Di
  full_name: Ma, Di
  last_name: Ma
- first_name: Ritankar
  full_name: Majumdar, Ritankar
  last_name: Majumdar
- first_name: Tian
  full_name: Zhao, Tian
  last_name: Zhao
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Jens
  full_name: Palsberg, Jens
  last_name: Palsberg
citation:
  ama: 'Chatterjee K, Ma D, Majumdar R, Zhao T, Henzinger TA, Palsberg J. Stack size
    analysis for interrupt-driven programs. In: <i>10th International Static Analysis
    Symposium</i>. Vol 2694. Springer nature; 2003:109-126. doi:<a href="https://doi.org/10.1007/3-540-44898-5_7">10.1007/3-540-44898-5_7</a>'
  apa: 'Chatterjee, K., Ma, D., Majumdar, R., Zhao, T., Henzinger, T. A., &#38; Palsberg,
    J. (2003). Stack size analysis for interrupt-driven programs. In <i>10th International
    Static Analysis Symposium</i> (Vol. 2694, pp. 109–126). San Diego, CA, United
    States: Springer nature. <a href="https://doi.org/10.1007/3-540-44898-5_7">https://doi.org/10.1007/3-540-44898-5_7</a>'
  chicago: Chatterjee, Krishnendu, Di Ma, Ritankar Majumdar, Tian Zhao, Thomas A Henzinger,
    and Jens Palsberg. “Stack Size Analysis for Interrupt-Driven Programs.” In <i>10th
    International Static Analysis Symposium</i>, 2694:109–26. Springer nature, 2003.
    <a href="https://doi.org/10.1007/3-540-44898-5_7">https://doi.org/10.1007/3-540-44898-5_7</a>.
  ieee: K. Chatterjee, D. Ma, R. Majumdar, T. Zhao, T. A. Henzinger, and J. Palsberg,
    “Stack size analysis for interrupt-driven programs,” in <i>10th International
    Static Analysis Symposium</i>, San Diego, CA, United States, 2003, vol. 2694,
    pp. 109–126.
  ista: 'Chatterjee K, Ma D, Majumdar R, Zhao T, Henzinger TA, Palsberg J. 2003. Stack
    size analysis for interrupt-driven programs. 10th International Static Analysis
    Symposium. FCRC: Federated Computing Research Conference, Lecture Notes in Computer
    Science, vol. 2694, 109–126.'
  mla: Chatterjee, Krishnendu, et al. “Stack Size Analysis for Interrupt-Driven Programs.”
    <i>10th International Static Analysis Symposium</i>, vol. 2694, Springer nature,
    2003, pp. 109–26, doi:<a href="https://doi.org/10.1007/3-540-44898-5_7">10.1007/3-540-44898-5_7</a>.
  short: K. Chatterjee, D. Ma, R. Majumdar, T. Zhao, T.A. Henzinger, J. Palsberg,
    in:, 10th International Static Analysis Symposium, Springer nature, 2003, pp.
    109–126.
conference:
  end_date: 2003-06-13
  location: San Diego, CA, United States
  name: 'FCRC: Federated Computing Research Conference'
  start_date: 2003-06-11
date_created: 2018-12-11T12:05:46Z
date_published: 2003-05-13T00:00:00Z
date_updated: 2026-05-06T09:39:35Z
day: '13'
doi: 10.1007/3-540-44898-5_7
extern: '1'
fulldoi: https://doi.org/10.1007/3-540-44898-5_7
intvolume: '      2694'
language:
- iso: eng
month: '05'
oa_version: None
page: 109 - 126
publication: 10th International Static Analysis Symposium
publication_identifier:
  eisbn:
  - '9783540448983'
  isbn:
  - '9783540403258'
publication_status: published
publisher: Springer nature
publist_id: '2260'
quality_controlled: '1'
status: public
title: Stack size analysis for interrupt-driven programs
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 2694
year: '2003'
...
