Debugging and Testing Concurrent Programs with Efficient Test Case Generation

• 資料種別: 博士論文
• タイトル: Debugging and Testing Concurrent Programs with Efficient Test Case Generation
• 著者・編者: Setiadi, Theodorus Eric
• 著者標目: Setiadi, Theodorus Eric
• 出版事項: The University of Electro-Communications
• 出版年月日等: 2015-06-26
• 出版年（W3CDTF）: 2015-06-26
• 並列タイトル等: 効率良いテストケース生成による並行処理プログラムのデバッグとテスト
• タイトル（掲載誌）: 学位論文
• 授与機関名: 電気通信大学
• 授与年月日: 2015-06-26
• 授与年月日（W3CDTF）: 2015-06-26
• 報告番号: 乙第137号
• 学位: 博士（工学）
• 博論授与番号: 12612乙第137号
• 本文の言語コード: eng
• 対象利用者: 一般
• 一般注記: Debugging multi-threaded concurrent programs is more difficult than sequential programs because errors are not always reproducible. Re-executing or instrumenting a concurrent program for tracing might change the execution timing and might cause the concurrent program to take a different execution path. In other words, the exact timing that caused the error is unknown. In order to reproduce the error, one needs to execute the concurrent program with the same input values many times as test cases by changing interleavings, but it is not always feasible to test them all. This dissertation proposes a debugging/testing system that generates all possible executions as test cases based on the limited information obtained from an execution trace, and then detects potential race conditions caused by different schedules and interrupt timings on a concurrent multi-threaded program. There are a number of studies about test cases reduction using partial order reduction, but there are still redundancies for the purpose of checking race conditions. The objective is to efficiently reproduce concurrent errors, specifically race conditions, by proposing three methods. The first is to reduce the numbers of interleavings to be tested. This is achieved by reducing redundant test cases and eliminating infeasible ones. The originality of the proposed method is to exploit the nature of branch coverage and utilize data flows from the trace information to identify only those interleavings that affect branch outcomes, whereas existing methods try to identify all the interleavings which may affect shared variables. Since the execution paths with the same branch outcomes would have equivalent sequences of lock/unlock and read/write operations to shared variables, they can be grouped together in the same “race-equivalent” group. In order to reduce the task for reproducing race conditions, it is sufficient to check only one member of the group. In this way, the proposed method can significantly reduces the number of interleavings for testing while still capable of detecting the same race conditions. Furthermore, the proposed method extends the existing model of execution trace to identify and avoid generating infeasible interleavings due to dependency caused by lock/unlock and wait/notify mechanisms. Experimental results suggest that redundant interleavings can be identified and removed which leads to a significant reduction of test cases. We evaluated the proposed method against several concurrent Java programs. The experimental results for an open source program Apache Commons Pool show the number of test cases is reduced from 23, which is based on the existing Thread-Pair-Interleaving method (TPAIR), 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 numbers of test cases, while many existing methods generate an infinite number of test cases. The second is to reduce the memory space required for generating test cases. Redundant test cases were still generated by the existing reachability testing method even though there was no need to execute them. Here, we propose a new method by analyzing data dependency to generate only those test cases that might affect sequences of lock/unlock and read/write operations to shared variables. The experimental results for the Apache Commons Pool show that the size of the graph for creating the test cases is reduced from 990 nodes, as based on the reachability testing method used in our previous work, to only 4 nodes by our new method. The third improvement is to reduce the effort involved in checking race conditions by utilizing previous test results. Existing work requires checking race conditions in the whole execution trace for every new test case. The proposed method can identify only those parts of the execution trace in which the sequence of lock/unlock and read/write operations to shared variables might be affected by a new test case, thus necessitating that race conditions be rechecked only for those affected parts. From the new improvements introduced above, the proposed methods accomplish to significantly reduce the efforts for exhaustively checking all possible interleavings. The proposed methods provide programmers the information regarding whether there exist program errors caused by interleavings, the interleaving (path) when the errors occurred, and accesses to shared variables with inconsistent locking.; 2015
• 国立国会図書館永続的識別子: info:ndljp/pid/10120739; https://dl.ndl.go.jp/pid/10120739
• コレクション（共通）: 障害者向け資料
• コレクション（障害者向け資料：レベル1）: テキストデータ
• コレクション（個別）: 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• 収集根拠: 博士論文（自動収集）
• 受理日（W3CDTF）: 2016-07-07T04:28:02+09:00
• 記録形式（IMT）: application/pdf
• オンライン閲覧公開範囲: 国立国会図書館内限定公開
• デジタル化資料送信: 図書館・個人送信対象外
• 遠隔複写可否（NDL）: 可
• 掲載誌（URI）: http://id.nii.ac.jp/1438/00000798/
• 連携機関・データベース: 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp