Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs

Che Sheng Lin, Gwan-Hwan Hwang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Concurrent programs that contain busy-waiting loops or iterative statements might not stop when they are tested dynamically due to some processes getting stuck in infinite loops or the execution of several loops forming a livelock. The traditional way of handling this problem in dynamic testing - interrupting the execution of the concurrent program when a predefined maximum execution time is exceeded. In this paper, we propose a dynamic decision scheme that spontaneously stops the execution of tested processes when they get stuck in an infinite loop or form a livelock. Since the halting problem is proven to be undecidable, we propose heuristic algorithms to cope with this. We apply the proposed scheme to a dynamic testing methodology called dynamic effective testing, which can perform state- and transition-cover testing for concurrent programs with busy-waiting loops. The implementation and experimental results demonstrate the feasibility of the proposed scheme.

Original languageEnglish
Title of host publicationProceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009
Pages291-292
Number of pages2
DOIs
Publication statusPublished - 2009 Nov 16
Event2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009 - Tianjin, China
Duration: 2009 Jul 292009 Jul 31

Publication series

NameProceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009

Other

Other2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009
CountryChina
CityTianjin
Period09/7/2909/7/31

Fingerprint

Testing
Heuristic algorithms

Keywords

  • Concurrent testing
  • Infinite loop
  • Livelock

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture
  • Software

Cite this

Lin, C. S., & Hwang, G-H. (2009). Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs. In Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009 (pp. 291-292). [5198516] (Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009). https://doi.org/10.1109/TASE.2009.23

Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs. / Lin, Che Sheng; Hwang, Gwan-Hwan.

Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009. 2009. p. 291-292 5198516 (Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lin, CS & Hwang, G-H 2009, Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs. in Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009., 5198516, Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009, pp. 291-292, 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009, Tianjin, China, 09/7/29. https://doi.org/10.1109/TASE.2009.23
Lin CS, Hwang G-H. Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs. In Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009. 2009. p. 291-292. 5198516. (Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009). https://doi.org/10.1109/TASE.2009.23
Lin, Che Sheng ; Hwang, Gwan-Hwan. / Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs. Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009. 2009. pp. 291-292 (Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009).
@inproceedings{301e3d977673413f9d5682e077a3172f,
title = "Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs",
abstract = "Concurrent programs that contain busy-waiting loops or iterative statements might not stop when they are tested dynamically due to some processes getting stuck in infinite loops or the execution of several loops forming a livelock. The traditional way of handling this problem in dynamic testing - interrupting the execution of the concurrent program when a predefined maximum execution time is exceeded. In this paper, we propose a dynamic decision scheme that spontaneously stops the execution of tested processes when they get stuck in an infinite loop or form a livelock. Since the halting problem is proven to be undecidable, we propose heuristic algorithms to cope with this. We apply the proposed scheme to a dynamic testing methodology called dynamic effective testing, which can perform state- and transition-cover testing for concurrent programs with busy-waiting loops. The implementation and experimental results demonstrate the feasibility of the proposed scheme.",
keywords = "Concurrent testing, Infinite loop, Livelock",
author = "Lin, {Che Sheng} and Gwan-Hwan Hwang",
year = "2009",
month = "11",
day = "16",
doi = "10.1109/TASE.2009.23",
language = "English",
isbn = "9780769537573",
series = "Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009",
pages = "291--292",
booktitle = "Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009",

}

TY - GEN

T1 - Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs

AU - Lin, Che Sheng

AU - Hwang, Gwan-Hwan

PY - 2009/11/16

Y1 - 2009/11/16

N2 - Concurrent programs that contain busy-waiting loops or iterative statements might not stop when they are tested dynamically due to some processes getting stuck in infinite loops or the execution of several loops forming a livelock. The traditional way of handling this problem in dynamic testing - interrupting the execution of the concurrent program when a predefined maximum execution time is exceeded. In this paper, we propose a dynamic decision scheme that spontaneously stops the execution of tested processes when they get stuck in an infinite loop or form a livelock. Since the halting problem is proven to be undecidable, we propose heuristic algorithms to cope with this. We apply the proposed scheme to a dynamic testing methodology called dynamic effective testing, which can perform state- and transition-cover testing for concurrent programs with busy-waiting loops. The implementation and experimental results demonstrate the feasibility of the proposed scheme.

AB - Concurrent programs that contain busy-waiting loops or iterative statements might not stop when they are tested dynamically due to some processes getting stuck in infinite loops or the execution of several loops forming a livelock. The traditional way of handling this problem in dynamic testing - interrupting the execution of the concurrent program when a predefined maximum execution time is exceeded. In this paper, we propose a dynamic decision scheme that spontaneously stops the execution of tested processes when they get stuck in an infinite loop or form a livelock. Since the halting problem is proven to be undecidable, we propose heuristic algorithms to cope with this. We apply the proposed scheme to a dynamic testing methodology called dynamic effective testing, which can perform state- and transition-cover testing for concurrent programs with busy-waiting loops. The implementation and experimental results demonstrate the feasibility of the proposed scheme.

KW - Concurrent testing

KW - Infinite loop

KW - Livelock

UR - http://www.scopus.com/inward/record.url?scp=71049174815&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71049174815&partnerID=8YFLogxK

U2 - 10.1109/TASE.2009.23

DO - 10.1109/TASE.2009.23

M3 - Conference contribution

AN - SCOPUS:71049174815

SN - 9780769537573

T3 - Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009

SP - 291

EP - 292

BT - Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009

ER -