標題: Path Exploration Based on Monte Carlo Tree Search for Symbolic Execution
作者: Yeh, Chao-Chun
Lu, Han-Lin
Yeh, Jia-Jun
Huang, Shih-Kun
資訊工程學系
資訊技術服務中心
Department of Computer Science
Information Technology Services Center
關鍵字: Monte Carlo tree search;upper-confidence bounds for trees;symbolic execution;path exploration;software testing
公開日期: 1-Jan-2017
摘要: Symbolic Execution is a widely used technique for program testing and analysis. When a program executes a trace symbolically, it simulates all possible paths. This results in an exponential growth of the number of states within the problem, which is commonly referred to as "path explosion." We therefore propose novel strategies that only require limited resources to give priority to more valuable paths. In this paper, we utilize a method based on the Monte Carlo tree search (MCTS) strategy to resolve the problem. We then compare the proposed MCTS-based strategy with other methods such as depth-first search (DFS) and breadth-first search (BFS). We also perform different scales of experiments based on time and space resource constraints. For smaller test cases, we found that MCTS performs on average 1.4 times better than BFS and DFS in terms of the block discovery rate. In addition, for larger test cases, MCTS performs on average 2.8 times better than DFS and BFS in terms of the block discovery rate.
URI: http://hdl.handle.net/11536/146163
ISSN: 2376-6816
期刊: 2017 CONFERENCE ON TECHNOLOGIES AND APPLICATIONS OF ARTIFICIAL INTELLIGENCE (TAAI)
起始頁: 33
結束頁: 37
Appears in Collections:Conferences Paper