Path Exploration Based on Monte Carlo Tree Search for Symbolic Execution

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."...

Full description

Saved in:
Bibliographic Details
Main Authors: Yeh, Chao-Chun, Lu, Han-Lin, Yeh, Jia-Jun, Huang, Shih-Kun
Format: Conference Proceeding
Language:English
Subjects:
Computational intelligence
Conferences
Information technology
Monte Carlo tree search
path exploration
Privacy
Security
Software algorithms
Software engineering
software testing
symbolic execution
upper-confidence bounds for trees
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2376-6824
DOI:10.1109/TAAI.2017.26