以 GDB 實作 XThreadDebugger-Linux(XTD-Linux)提供 Linux 平台之多執行緒除錯

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：16

、訪客IP：18.190.217.134

姓名

陳之寬(Chih-Kuan Chen) 查詢紙本館藏

畢業系所

軟體工程研究所

論文名稱

以 GDB 實作 XThreadDebugger-Linux(XTD-Linux)提供 Linux 平台之多執行緒除錯

相關論文

★ CRUnit - Capture / Replay Based Unit Testing	★ Locating Interested Code by Program Execution Paths with Debugger
★ An OpenStack Based Testing as a Service Platform	★ Visualize Ripple Effect with Analyzing Object-Oriented Design Relationship
★ Change History Tracing Tool for Arbitrary Programming Language	★ Virtual Objects for Program Visualization in xDIVA
★ Enhance Stress Testing Power by Synchronizing JMeter Test Scripts	★ 支援版本控制系統之文件撰寫工具
★ Korat: An O.S.-independent Capture/Replay Test Automation System	★ GUI Component Detection for Cross-Platform Applications–Using Input Device and Image Change Synergistic Detection Method
★ 應用設計模式於 RPA 軟體實作低維護成本的屬性面板自動修正功能	★ 使用靜態分析偵測 JavaScript 應用程式中的 Race Condition
★ 基於物件導向與 Clean Code 概念進行 xDiva 重構與優化	★ 基於xDIVA之利用關鍵影格將3D物件動畫化與即時保存的視覺化工具
★ CoolPCB：以控制點為主的電路板切割成形繪製自動化方法	★ 利用軟體 UI 實現擴充功能突破原始碼限制的工具

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

多執行緒程式在當前的多核世代中扮演著越來越重要的角色，其提供的方便性以及效能在軟體開發中已經成為不可或缺的一部分。然而雖然多執行緒程式有著大量優點，但它也容易發生並行性錯誤(concurrency error)，這些錯誤特別難以避免，發現和修復，因為它們的發生取決於特定的執行緒交錯(interleaving)。並且由於參與其中的執行緒調度通常數量龐大，所以測試所有可能的交錯實務上是不可行的。同時，由於多執行緒程式固有的非確定性，引發並行錯誤和除錯這些多執行緒程序變得非常具有挑戰性。雖然在重現並行錯誤的領域Windows上已有諸多研究提供了他們各自的工具，然而在Linux平台上，卻少有研究提出此類工具。本實驗室已經實作一套運作於Windows下之多執行緒程式除錯與測試輔助工具，提供使用者對於交錯產生的控制能力以手動引發並行錯誤，並提供記錄和重放產生該並行錯誤之交錯的功能。此外，該工具也提供以窮舉測試方式替開發人員自動搜尋並記錄並行錯誤。本論文將移植該工具至Linux平台以提供對其多執行緒開發人員之支援，並實作測試來驗證該工具符合本論文所訂定之需求，同時作為未來擴充該工具時作為基本運行測試之一環。

摘要(英)

Multi-threaded programs play an increasingly important role in the current multi-core generation. The convenience and performance multi-threaded programs provided have become integral for modern software development. However, although multi-threaded programs have a number of advantages, they are also prone to concurrency errors. These errors are particularly difficult to avoid, find and fix, because their occurrence depends on specific interleaving. And because of the large number of thread involved, it is not feasible to test all possible interleaving in practices. At the same time, due to the inherent non-determinism of multi-threaded programs, reproduce these concurrency errors and debugging multi-threaded programs becomes very challenging. Although many researches have provided their own tools in the field of reproducing concurrency error, there are few studies on such tools under Linux. Our colleagues have implemented a tool for debugging and testing multi-threaded programs under Windows, providing ability for user to control interleave and manually trigger concurrency errors, and record and/or replay the buggy interleaving to re-generate those concurrency errors. In addition, the tool also provides an exhaustive test module for developers to automatically search for and record buggy interleaving. This paper ports the tool to Linux to provide support for its multi-threaded developers, verifies that the tool meets the requirements through a series of tests and as a basic operating test for future expansion of this tool at the same time.

關鍵字(中)

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

關鍵字(英)

★ multi-thread
★ debugging
★ concurrency error
★ testing

論文目次

圖目 5
表目 6
摘要 7
Abstract 8
一、緒論 9
1-1 研究背景 9
1-2 研究動機 12
1-3 研究方法與貢獻 13
1-4 論文架構 13
二、相關背景研究 15
2-1 軟體測試與除錯 15
2-2 錯誤重現 16
2-3 Debugger 17
2-3-1 The GNU Debugger(GDB) 18
2-4 重現與處理concurrency errors 18
2-4-1 交錯 19
2-4-2 Race condition 21
2-4-3 同步操作與忙碌等待 21
2-4-4 Deadlock 22
2-5 除錯多執行緒程式 23
2-5-1 Probe effect 24
2-5-2 靜態分析 25
2-5-3 動態分析 26
三、 XThreadDebugger簡介 27
3-1 壓力測試與其缺點 27
3-2 窮舉測試：必要之惡 28
3-3 XThredDebugger(XTD) 29
3-4 與現有工具之比較：為何我們製作XTD-Linux 30
四、 XTD-Linux設計與實作 33
4-1 GDB上之多執行緒控制 33
4-1-1 使用GDB除錯Deadlock之困難 33
4-2 架構設計 37
4-2-1 架構說明 37
4-2-2 與XTD之比較 39
4-3 功能實作 40
4-3-1 Context switch point 41
4-3-2 Blocking assertion point 41
4-3-3 Naming point 43
4-3-4 Thread registration point 44
4-3-5 Breakpoint dictionary 45
4-3-6 Virtual scheduler 46
4-3-7 交錯之錄製與重現 47
五、 Exhaustive Testing設計與實作 48
5-1 Iterative context bounding演算法 48
六、測試與結果探討 51
6-1 Mutual Exclusion Problem 51
6-2 Dining philosophers problem - deadlock dection 54
6-3 其他語言之支援，以C++為例 56
七、結論與未來方向 59
參考文獻 61

參考文獻

[1] S. Lu, S. Park, E. Seo, and Y. Zhou, "Learning from mistakes: a comprehensive study on real world concurrency bug characteristics," ACM SIGOPS Operating Systems Review, vol. 42, pp. 329-339, 2008.
[2] A. Zeller, Why programs fail: a guide to systematic debugging: Elsevier, 2009.
[3] (2009-02-15, 2018-06). Should we always reproduce the bugs to verify the fixes? Available: https://stackoverflow.com/questions/550242/should-we-always-reproduce-the-bugs-to-verify-the-fixes
[4] M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu, "Finding and Reproducing Heisenbugs in Concurrent Programs," in OSDI, 2008, pp. 267-280.
[5] J. Micco. (May 27, 2016, 2018-06). Flaky Tests at Google and How We Mitigate Them. Available: https://testing.googleblog.com/2016/05/flaky-tests-at-google-and-how-we.html
[6] (2018-06). GDB Online Document. Available: https://sourceware.org/gdb/current/onlinedocs/gdb/index.html#SEC_Contents
[7] (2018-06). Stopping and Starting Multi-thread Programs. Available: https://sourceware.org/gdb/current/onlinedocs/gdb/Thread-Stops.html#Thread-Stops
[8] X. Yuan, C. Wu, Z. Wang, J. Li, P.-C. Yew, J. Huang, et al., "ReCBuLC: reproducing concurrency bugs using local clocks," in Proceedings of the 37th International Conference on Software Engineering-Volume 1, 2015, pp. 824-834.
[9] N. Rungta, E. G. Mercer, and W. Visser, "Efficient testing of concurrent programs with abstraction-guided symbolic execution," in International SPIN Workshop on Model Checking of Software, 2009, pp. 174-191.
[10] L. M. Carril and W. F. Tichy, "Interleaving generation for data race and deadlock reproduction," in Proceedings of the 2nd International Workshop on Software Engineering for Parallel Systems, 2015, pp. 26-34.
[11] P. Anderson, "The use and limitations of static-analysis tools to improve software quality," CrossTalk: The Journal of Defense Software Engineering, vol. 21, pp. 18-21, 2008.
[12] D. Hutchins, A. Ballman, and D. Sutherland, "C/C++ thread safety analysis," in Source Code Analysis and Manipulation (SCAM), 2014 IEEE 14th International Working Conference on, 2014, pp. 41-46.
[13] C. Flanagan and P. Godefroid, "Dynamic partial-order reduction for model checking software," in ACM Sigplan Notices, 2005, pp. 110-121.
[14] P. Fonseca, C. Li, and R. Rodrigues, "Finding complex concurrency bugs in large multi-threaded applications," in Proceedings of the sixth conference on Computer systems, 2011, pp. 215-228.
[15] B. Kasikci, W. Cui, X. Ge, and B. Niu, "Lazy Diagnosis of In-Production Concurrency Bugs," in Proceedings of the 26th Symposium on Operating Systems Principles, 2017, pp. 582-598.
[16] M. Musuvathi and S. Qadeer, "Iterative context bounding for systematic testing of multithreaded programs," in ACM Sigplan Notices, 2007, pp. 446-455.
[17] C. Wang, M. Said, and A. Gupta, "Coverage guided systematic concurrency testing," in Proceedings of the 33rd International Conference on Software Engineering, 2011, pp. 221-230.
[18] P. Godefroid, "Model checking for programming languages using VeriSoft," in Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1997, pp. 174-186.
[19] J. Neystadt. (February 2008, 2018-06). Automated Penetration Testing with White-Box Fuzzing. Available: https://msdn.microsoft.com/en-us/library/cc162782.aspx
[20] S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte, "A randomized scheduler with probabilistic guarantees of finding bugs," in ACM Sigplan Notices, 2010, pp. 167-178.
[21] 楊權 and C. Yang, "A Testing and Debugging Tool for Arbitrary Interleaving on Multithreaded Programs Based on Debugger," 國立中央大學.
[22] (2018-06). Undo. Available: https://undo.io/
[23] N. Chatterjee, S. Majumdar, S. R. Sahoo, and P. P. Das, "Debugging multi-threaded applications using pin-augmented gdb (pgdb)," in Proceedings of the International Conference on Software Engineering Research and Practice (SERP), 2015, p. 109.
[24] Y. Eytani, K. Havelund, S. D. Stoller, and S. Ur, "Towards a framework and a benchmark for testing tools for multi‐threaded programs," Concurrency and Computation: Practice and Experience, vol. 19, pp. 267-279, 2007.

指導教授

鄭永斌

審核日期

2018-7-3

推文