[{"title":"Stack size analysis for interrupt-driven programs","doi":"10.1007/3-540-44898-5_7","quality_controlled":"1","day":"13","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Ma, Di","first_name":"Di","last_name":"Ma"},{"last_name":"Majumdar","first_name":"Ritankar","full_name":"Majumdar, Ritankar"},{"last_name":"Zhao","full_name":"Zhao, Tian","first_name":"Tian"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"last_name":"Palsberg","first_name":"Jens","full_name":"Palsberg, Jens"}],"date_published":"2003-05-13T00:00:00Z","article_processing_charge":"No","publication_status":"published","year":"2003","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","status":"public","conference":{"location":"San Diego, CA, United States","end_date":"2003-06-13","start_date":"2003-06-11","name":"FCRC: Federated Computing Research Conference"},"_id":"3898","publist_id":"2260","abstract":[{"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.","lang":"eng"}],"type":"conference","language":[{"iso":"eng"}],"month":"05","page":"109 - 126","OA_type":"closed access","publisher":"Springer nature","publication":"10th International Static Analysis Symposium","intvolume":"      2694","date_created":"2018-12-11T12:05:46Z","citation":{"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.","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>.","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.","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>.","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."},"volume":2694,"publication_identifier":{"eisbn":["9783540448983"],"isbn":["9783540403258"]},"date_updated":"2026-05-06T09:39:35Z","oa_version":"None","extern":"1","alternative_title":["Lecture Notes in Computer Science"]}]