在資訊服務多元的時代，軟體架構越來越複雜，必須仰賴自動測試技術，以找出系統可能存在的問題。現行自動測試的方法之一是使用符號執行。符號執行是一種軟體測試與分析的技術，能模擬程式執行的路徑，針對程式產生相對應的符號執行樹狀結構圖，再進行樹狀結構的探索，以找尋有問題的程式節點。
論文中，我們探討以機器學習方法，基於Monte Carlo Tree Search (MCTS)搜尋，進行動態路徑探索，改良傳統搜尋(如DFS或BFS)只能固定搜尋方式的問題，結合靜態模擬與限制式求解的狀況，動態調整搜尋的順序。實驗結果顯示，在固定的時間下，探討測試程式覆蓋率，我們改善程式覆蓋區塊的數量，比DFS 增加0.69到3.4倍的涵蓋範圍。

With the diversity of information services, software architecture is becoming complicated, and the software system must rely on automatic testing to identify potential problems. One of the automated testing methods is symbolic execution. Symbol execution is a dynamic analysis method to emulate the program execution by assuming inputs as symbolic values.
In this thesis, we use Monte Carlo Tree Search (MCTS) method to dynamically explore the execution tree of symbolic execution and improve traditional methods such as DFS or BFS. The experimental results reveal that we can improve the program coverage at a fixed time, and we increase the coverage of the program by 0.69 to 3.4 times compared with the DFS.

摘要 I
Abstract II
致謝 III
List of Contents IV
List of Figures V
List of Tables VI
1. Introduction 1
2. Background 3
2.1 Symbolic Execution 3
2.2 Multi-armed bandit problem 4
2.3 Monte Carlo Tree Search 5
3. Method 7
3.1 Overview 7
3.2 Proposed Algorithm with penalty 8
4. Implementation 15
4.1 Introduction to Angr 15
4.2 Exploration techniques 15
5. Result 17
5.1 Environment 17
5.2 Evaluation Result 18
5.3 Discussions 24
6. Conclusion 25
7. Future work 26
8. References 27

[1] Chipounov, V., V. Kuznetsov, and G. Candea, S2E: A platform for in-vivo multi-path analysis of software systems. ACM SIGPLAN Notices, 2011. 46(3): p. 265-278.
[2] Kaelbling, L.P., Multi-armed bandit.
[3] Bradberry, J. Introduction to Monte Carlo Tree Search. 2015; Available from: https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/.
[4] Browne, C.B., et al., A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 2012. 4(1): p. 1-43.
[5] Silver, D. and D. Hassabis, Alphago: Mastering the ancient game of go with machine learning. Research Blog, 2016.
[6] Yeh, J.-J., Monte Carlo Tree Search-based Path Exploration for Symbolic Execution.
[7] Hauser, C., Y. Shoshitaishvili, and R. Wang, Poster: Challenges and next steps in binary program analysis with angr.