Path Exploration Based on Monte Carlo Tree Search for Symbolic Execution

Chao Chun Yeh, Han Lin Lu, Jia Jun Yeh, Shih-Kun Huang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2017 Conference on Technologies and Applications of Artificial Intelligence, TAAI 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages33-37
Number of pages5
ISBN (Electronic)9781538642030
DOIs
StatePublished - 9 May 2018
Event2017 Conference on Technologies and Applications of Artificial Intelligence, TAAI 2017 - Taipei, Taiwan
Duration: 1 Dec 20173 Dec 2017

Publication series

NameProceedings - 2017 Conference on Technologies and Applications of Artificial Intelligence, TAAI 2017

Conference

Conference2017 Conference on Technologies and Applications of Artificial Intelligence, TAAI 2017
CountryTaiwan
CityTaipei
Period1/12/173/12/17

Keywords

  • Monte Carlo tree search
  • path exploration
  • software testing
  • symbolic execution
  • upper-confidence bounds for trees

Fingerprint Dive into the research topics of 'Path Exploration Based on Monte Carlo Tree Search for Symbolic Execution'. Together they form a unique fingerprint.

Cite this