Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 1 of 1
-
ItemSoftware testing with Monte Carlo tree search( 2022)Achieving high code coverage in modern software is an essential yet challenging task. The size and complexity of programs give rise to the exploitation-exploration dilemma for testers: How to balance the consideration between investigating a) the parts of the program that appears to be interesting based on the existing information (exploitation) vs b) other parts that are less well-understood (exploration)? The Monte Carlo tree search (MCTS) is an artificial intelligence (AI) search algorithm that offers a principled solution to balancing these two concerns and has demonstrated its efficiency in large search spaces. This thesis contributes to tailoring MCTS to automate test generation for coverage-based testing. First, we propose Legion to assist coverage-based whitebox testing with our variation of MCTS. Legion’s APPFuzzing generalises concoilc testing and fuzzing to cover more program states with amortised computation cost: It selectively solves the path constraints of intermediate program states for seed inputs and mutates them to cover the descendants of the selected states. Legion’s variation of MCTS uses the best-first search strategy to learn the most productive program states to apply APPFuzzing, thus mitigating path explosion in symbolic execution. We compare Legion’s performance with KLEE, a famous coverage-based concoilc testing tool developed, maintained, and used by a large community across academia and industry. Legion outperformed KLEE in 7 out of 11 benchmark suites in a worldwide competition and achieved 90% of the best score in 5 suites. Then we extend Legion’s algorithm to seed selection in greybox fuzzing. This algorithm searches for stateful protocol servers’ most progressive seed input sequence. We analyse the impact of multiple server models and selection algorithms with repeated experiments. This study shows that although our algorithm has a limited impact on the overall coverage performance, it vastly increases the probability of covering some representative code blocks in servers. It highlights the bottleneck of overall coverage performance in input generation quality and fuzzing throughput. Finally, we design a contextual MCTS algorithm to reify and transfer the knowledge of past program state evaluations. Most software testing algorithms estimate a state’s productivity only with the state-specific statistics and neglect the knowledge from other states. To use the statistics more efficiently, we identify two contextual features of each program state and quantified their effect state’s productivity as feature coefficients. We then train a regression model to dynamically update the value of the coefficients to evaluate other program states based on the states’ feature values. By analysing our experiment results and reviewing others’ work, we point out the current weaknesses and corresponding future works regarding this topic.