Efficient Execution Path Exploration for Detecting Races in Concurrent Programs.
Saved in:
| Title: | Efficient Execution Path Exploration for Detecting Races in Concurrent Programs. |
|---|---|
| Authors: | Setiadi, Theodorus E.1 eric@maekawa.is.uec.ac.jp, Ohsuga, Akihiko1,2,3,4,5,6 akihiko@ohsuga.is.uec.ac.jp, Maekawa, Mamoru1,7,8,9 maekawa@maekawa.is.uec.ac.jp |
| Source: | IAENG International Journal of Computer Science. 2013, Vol. 40 Issue 3, p15-34. 21p. |
| Subjects: | Computers testing, Computer programming, Debugging, Computer programmers, Precision (Information retrieval), Information storage & retrieval systems |
| Abstract: | Concurrent programs are more difficult to test or debug than sequential programs because their non-deterministic behaviors can produce errors that depend on timing and interleaving of threads. A different interleaving might affect branch outcomes that can lead the execution path into one different from that in which the error was detected. In order to detect concurrent errors, a programmer needs to re-execute the concurrent program many times by changing the interleaving, but it is not always feasible to conduct all the tests due to a large number of possible different interleavings. This paper proposes an efficient method to minimize the number of test cases for detecting errors in a concurrent program. This method generates test cases with different interleavings based on the execution trace. The method reduces redundant test cases without sacrificing the precision of error detection. The method is novel because it exploits the branch structure and utilizes data flows from trace information to identify only those interleavings that affect branch outcomes, whereas existing methods try to identify all interleavings that seem to affect shared variables. In order to reduce the number of test cases, those execution paths with equivalent lock sequences and accesses to shared variables are grouped together into the same "race-equivalent" group and only one member of the group is tested. We evaluated the proposed method against several concurrent Java programs. The experimental results for a Java program for telnet show the number of test cases is reduced from 147, which is based on the existing TPAIR method, to only 2 by the proposed method. Moreover, for concurrent programs that contain infinite loops, the proposed method generates only a finite and very few number of test cases, while many existing methods generate an infinite number of test cases. [ABSTRACT FROM AUTHOR] |
| Copyright of IAENG International Journal of Computer Science is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 90109752 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Efficient Execution Path Exploration for Detecting Races in Concurrent Programs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Setiadi%2C+Theodorus+E%2E%22">Setiadi, Theodorus E.</searchLink><relatesTo>1</relatesTo><i> eric@maekawa.is.uec.ac.jp</i><br /><searchLink fieldCode="AR" term="%22Ohsuga%2C+Akihiko%22">Ohsuga, Akihiko</searchLink><relatesTo>1,2,3,4,5,6</relatesTo><i> akihiko@ohsuga.is.uec.ac.jp</i><br /><searchLink fieldCode="AR" term="%22Maekawa%2C+Mamoru%22">Maekawa, Mamoru</searchLink><relatesTo>1,7,8,9</relatesTo><i> maekawa@maekawa.is.uec.ac.jp</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IAENG+International+Journal+of+Computer+Science%22">IAENG International Journal of Computer Science</searchLink>. 2013, Vol. 40 Issue 3, p15-34. 21p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computers+testing%22">Computers testing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programming%22">Computer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Debugging%22">Debugging</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programmers%22">Computer programmers</searchLink><br /><searchLink fieldCode="DE" term="%22Precision+%28Information+retrieval%29%22">Precision (Information retrieval)</searchLink><br /><searchLink fieldCode="DE" term="%22Information+storage+%26+retrieval+systems%22">Information storage & retrieval systems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Concurrent programs are more difficult to test or debug than sequential programs because their non-deterministic behaviors can produce errors that depend on timing and interleaving of threads. A different interleaving might affect branch outcomes that can lead the execution path into one different from that in which the error was detected. In order to detect concurrent errors, a programmer needs to re-execute the concurrent program many times by changing the interleaving, but it is not always feasible to conduct all the tests due to a large number of possible different interleavings. This paper proposes an efficient method to minimize the number of test cases for detecting errors in a concurrent program. This method generates test cases with different interleavings based on the execution trace. The method reduces redundant test cases without sacrificing the precision of error detection. The method is novel because it exploits the branch structure and utilizes data flows from trace information to identify only those interleavings that affect branch outcomes, whereas existing methods try to identify all interleavings that seem to affect shared variables. In order to reduce the number of test cases, those execution paths with equivalent lock sequences and accesses to shared variables are grouped together into the same "race-equivalent" group and only one member of the group is tested. We evaluated the proposed method against several concurrent Java programs. The experimental results for a Java program for telnet show the number of test cases is reduced from 147, which is based on the existing TPAIR method, to only 2 by the proposed method. Moreover, for concurrent programs that contain infinite loops, the proposed method generates only a finite and very few number of test cases, while many existing methods generate an infinite number of test cases. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IAENG International Journal of Computer Science is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=90109752 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 21 StartPage: 15 Subjects: – SubjectFull: Computers testing Type: general – SubjectFull: Computer programming Type: general – SubjectFull: Debugging Type: general – SubjectFull: Computer programmers Type: general – SubjectFull: Precision (Information retrieval) Type: general – SubjectFull: Information storage & retrieval systems Type: general Titles: – TitleFull: Efficient Execution Path Exploration for Detecting Races in Concurrent Programs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Setiadi, Theodorus E. – PersonEntity: Name: NameFull: Ohsuga, Akihiko – PersonEntity: Name: NameFull: Maekawa, Mamoru IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: 2013 Type: published Y: 2013 Identifiers: – Type: issn-print Value: 1819656X Numbering: – Type: volume Value: 40 – Type: issue Value: 3 Titles: – TitleFull: IAENG International Journal of Computer Science Type: main |
| ResultId | 1 |
