A Testing and Debugging Tool for Arbitrary Interleaving on Multithreaded Programs Based on Debugger

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：24

、訪客IP：18.225.56.198

姓名

楊權(Chuan Yang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(A Testing and Debugging Tool for Arbitrary Interleaving on Multithreaded Programs Based on Debugger)

相關論文

★ 使用PolyTraceAid進行程式文件覆蓋率計算與分群	★ Support Visual Debugging in Electronic Design Automation Software by xDIVA
★ 設計與實作視覺化追蹤點以支援xDIVA進行程式動畫	★ Combine Internal Test Oracles and Capture/Replay GUI Testing for Precise Replay and Higher Validation Power
★ Dissimilarity of Polymorphic Execution Sequences	★ The Analysis of Capturing System Test Cases into Unit Test Cases
★ 動態延遲載入的測試覆蓋率	★ 建構於JMeter之自動化分散式壓力測試架構
★ 模組化因修改具耦合的程式碼所伴隨的成本漣漪	★ Design a Pluggable Architecture for Layout Algorithms in xDIVA
★ 重複性程式碼檢測之外掛模組設計	★ Visual Perception of Realistic Rendering in xDiva 3D Environment
★ Why and When GUI Test Automation Fails in Practice and Our Solutions to The Problem	★ Why and When GUI Test Automation Fails in Practice and Our Solutions to The Problem
★ Very High Precision Optical Character Recognition For Clean-Fixed-Sized True Type Characters	★ Enhance Korat by Branch Capability in Capture/Replay User Scenario to Industrial Test Case Automation

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

多執行緒程式在現今的軟體開發過程中幾乎難以避免，但如何設計出沒有錯誤的多執行緒程式，對開發者來說仍是一個困難的挑戰。因為多執行緒間的concurrency所引入的微妙錯誤往往需要特定的輸入及interleaving才能引發，這種nondeterminism讓引發與重現這種錯誤變得困難，進而導致了多執行緒程式不易測試與除錯的特性。
在除錯方面，儘管debugger是開發者用來除錯程式的主要工具，現有的debugger卻沒有針對重現interleaving的需求設計對應的功能。而測試concurrency error的研究雖然陸續有提出演算法及工具，來有效地探索interleaving空間以找出concurrency error，但其工具的使用往往受限於某些條件，例如相依於特定作業系統或高階語言虛擬機器，甚至必須動用昂貴的靜態分析技術。
本研究開發了一個具有彈性的多執行緒的interleaving的測試與除錯工具，並且只依賴debugger來提供所需的interleaving控制能力。在除錯上，本工具藉由提供可重現任意的interleaving的能力，來支援開發者進行除錯。在測試上，則可以系統性地探索interleaving空間，並可利用heuristic提高測試效率。此外，本工具也針對常見的兩種synchronization intention violation－atomicity violation、order violation－提供開發者設置assertion的功能，做為一種判斷程式如預期執行的測試準則(test oracle)，讓開發者能夠從更多的面向檢驗程式的行為，以增加提早發現concurrency error的機會，降低後續除錯的難度。最後，由於本工具是基於debugger framework進行設計，因此更容易移植到新的除錯器上以支援更多程式語言。

摘要(英)

Applying multithreading techniques is an inevitable trend in software development nowadays. However, writing correct multi-threaded programs remains a difficult challenge to most of developers in practice, due to the lack of debugging and testing support from tools. Such nondeterminism has seriously hindered the reproduction of concurrency errors, making debugging and testing a concurrent program a difficult task in practice.
Although the primary tool for fixing a bug is a debugger, debugging support for multi-threaded program is poorly provided by existing debuggers. On the other hand, solutions provided by previous researches often suffer from different kinds of assumptions and limitations. These limitations and assumptions are, O.S., high-level programming language, virtual machine dependency, or the programming language dependency for costly static analysis
In this paper, a flexible debugging and testing tool is proposed. First of all, This tool helps programmers on testing and debugging concurrency errors by providing the capability of reproducing and generating arbitrary interleavings. Where interleaving space can be reduced by heuristics, including bounding the locations of context switches and using thread pairwise testing. In addition, assertions for two common synchronization intentions, atomicity and order, are provided to help developers detecting concurrency errors from a different perspective, which offer an additional opportunity to make debugging easier by reducing the distance between the execution of the concurrency error and its manifestation. Finally, this approach is protentially easy to port to other debuggers to support more programming languages.

關鍵字(中)

★ 多執行緒
★ 並行錯誤
★ 除錯
★ 測試

關鍵字(英)

★ multi-thread
★ concurrency error
★ debugging
★ testing

論文目次

第1章、緒論 1
1-1 研究背景 1
1-2 研究動機 3
1-3 研究方法與貢獻 3
1-4 論文架構 4
第2章、研究背景與相關研究 5
2-1 軟體測試 5
2-2 軟體除錯 5
2-2-1 錯誤的可重現性 6
2-2-2 Debugger 7
2-3 Concurrency Error重現與對應 9
2-3-1 Interleaving 9
2-3-2 Race Condition 10
2-3-3 同步操作指令與忙碌等待 11
2-3-4 Deadlock 12
2-3-5 Atomicity Synchronization Intention 14
2-3-6 Order Synchronization Intention 15
2-4 Concurrency Error偵測與除錯 16
2-4-1 壓力測試的不足 16
2-4-2 Probe Effect 17
2-4-3 靜態分析的應用 17
2-4-4 動態分析的應用 18
第3章、 Interleaving控制功能之介紹 21
3-1 需求分析 21
3-2 功能與使用者介面 23
3-2-1 功能概觀 23
3-2-2 Breakpoint Panel 23
3-2-3 Interleaving Control Panel 24
3-3 ICP Setting 25
第4章、基於Debugger實現Interleaving之控制 27
4-1 以ICP及Virtual Scheduler監控執行緒 27
4-2 Interleaving Control Point之實作 28
4-2-1 主動脫離執行狀態之察覺 29
4-2-2 重現相同Interleaving之確保 30
第5章、 Concurrency Testing by Debugger 34
5-1 Iterative Context Bounding(IBC)演算法之應用 34
5-2 Synchronization Intention Assertion 36
5-2-1 Atomicity Synchronization Intention assertion 37
5-2-2 Order Synchronization Intention Assertion 39
5-3 Thread Pairwise Testing 41
第6章、討論與評估 43
6-1 可移植性之討論 43
6-2 錯誤偵測能力評估 43
6-2-1 鏈結串列 44
6-2-2 Modified Peterson’s algorithm 45
6-2-3 Bounded Producer/Consumer 47
6-2-4 Deadlock Example: AnagramPair 49
第7章、結論與未來研究方向 51
第8章、參考文獻 53

參考文獻

[1] S. Lu, S. Park, E. Seo, and Y. Zhou, "Learning from mistakes: a comprehensive study on real world concurrency bug characteristics," SIGARCH Comput. Archit. News, vol. 36, pp. 329-339, 2008.
[2] Java Path Finder (JPF). Available: http://babelfish.arc.nasa.gov/trac/jpf/wiki/projects/start
[3] "Checkthread - a static analysis tool for catching java concurrency bugs."
[4] S. Bindal, S. Bansal, and A. Lal, "Variable and thread bounding for systematic testing of multithreaded programs," presented at the Proceedings of the 2013 International Symposium on Software Testing and Analysis, Lugano, Switzerland, 2013.
[5] L. O. Andersen, "Program Analysis and Specialization for the C Programming Language," ed, 1994.
[6] J. Whaley and M. S. Lam, "Cloning-based context-sensitive pointer alias analysis using binary decision diagrams," SIGPLAN Not., vol. 39, pp. 131-144, 2004.
[7] 陳新志, "Korat: An O.S.-independent Capture/Replay Test Automation System," 碩士, 軟體工程研究所, 國立中央大學, 桃園縣, 2014.
[8] 劉冠吟, "建構於JMeter之自動化分散式壓力測試架構," 碩士, 資訊工程學系, 國立中央大學, 桃園縣, 2015.
[9] G. Denaro, A. Margara, M. Pezz, x00E, and M. Vivanti, "Dynamic Data Flow Testing of Object Oriented Systems," in 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, 2015, pp. 947-958.
[10] EclEmma, a free Java code coverage tool for Eclipse, brings code coverage analysis directly into the Eclipse workbench. Available: http://www.eclemma.org/
[11] 王浚懿, "Locating Interested Code by Program Execution Paths with Debugger," 碩士, 軟體工程研究所, 國立中央大學, 桃園縣, 2013.
[12] Valgrind. Available: http://valgrind.org/docs/pubs.html
[13] M. Musuvathi and S. Qadeer, "Iterative context bounding for systematic testing of multithreaded programs," SIGPLAN Not., vol. 42, pp. 446-455, 2007.
[14] J.-D. Choi and H. Srinivasan, "Deterministic replay of Java multithreaded applications," presented at the Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, Welches, Oregon, USA, 1998.
[15] O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur, "Multithreaded Java program test generation," IBM Systems Journal, vol. 41, pp. 111-125, 2002.
[16] S. Park, S. Lu, and Y. Zhou, "CTrigger: exposing atomicity violation bugs from their hiding places," SIGPLAN Not., vol. 44, pp. 25-36, 2009.
[17] S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson, "Eraser: a dynamic data race detector for multithreaded programs," ACM Trans. Comput. Syst., vol. 15, pp. 391-411, 1997.
[18] A. Bron, E. Farchi, Y. Magid, Y. Nir, and S. Ur, "Applications of synchronization coverage," presented at the Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, Chicago, IL, USA, 2005.
[19] W. Pugh and N. Ayewah, "Unit testing concurrent software," presented at the Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, Atlanta, Georgia, USA, 2007.

指導教授

鄭永斌(Yung-Pin Cheng)

審核日期

2016-7-1

推文