Description

Currently we have some heuristic based selectors. But our coverage sometimes is not 100%, so we want to increase our coverage and one approach is improvement of path selection.

Context

Path selector is a object that have poll(): ExecutionState and offer(ExecutionState) with semantics "give me the next state for traverse" and "take this state as potential candidate for future poll" respectively. During symbolic execution we may have thousands of potential next states: some of them can lead in cycles or bad branch of if or some other place of code, visiting which doesn't increase our coverage, so strategy of path selection have a significant impact on final coverage.

Expected behavior

Increasing in coverage compared with current selector or speeding up of test generation.

Idea

We want to implement new path selector inspired by this paper. Briefly,

• selectors based on different heuristics visit different parts of code
• enter reward for execution state, in which we want more coverage with less executing time
• we can consider this heuristics as features of execution state and reward as target function of execution, collect data after test generation with different selectors and then train our model on this data
• it can summarize information from all heurestics and cover more code in less time

Implementation

We should develop:

• calculation of heuristics for execution state
• several new path selectors based on heuristics
• feature processing part
• predictor, which calculates reward for execution state using python models and selector which uses this predictor

Environment

No specific environment is required for testing, but some specific environment is required for learning and it will be described in next feature request, which will involve scripts for education.

Potential alternatives

Not applicable