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

Che Sheng Lin; Gwan-Hwan Hwang

doi:10.1109/TASE.2009.23

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

Che Sheng Lin, Gwan-Hwan Hwang

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Proceedings - 2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009
Pages	291-292
Number of pages	2
DOIs	https://doi.org/10.1109/TASE.2009.23
Publication status	Published - 2009 Nov 16
Event	2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009 - Tianjin, China Duration: 2009 Jul 29 → 2009 Jul 31

Publication series

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

Other

Other	2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009
Country	China
City	Tianjin
Period	2009/07/29 → 2009/07/31

Keywords

Concurrent testing
Infinite loop
Livelock

ASJC Scopus subject areas

Computer Science Applications
Hardware and Architecture
Software

Access to Document

10.1109/TASE.2009.23

Fingerprint Dive into the research topics of 'Spontaneous detection of infinite loops and livelocks in dynamic testing of concurrent programs'. Together they form a unique fingerprint.

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 proceeding › Conference 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, 2009/07/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 = nov,

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",

note = "2009 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering, TASE 2009 ; Conference date: 29-07-2009 Through 31-07-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

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

Y2 - 29 July 2009 through 31 July 2009

ER -