Added a DFS strategy (Implementation is based on the legacy's module algorithm) and some tweaking to improve the general DSE exploration algorithm.
Changes
DSE Module
Removed default exploration algorithm that was not being used.
Added DFS exploration strategy based on the legacy exploration algorithm using generational search expansion as a baseline for expanding path conditions.
Reorganized DSE strategies naming among others.
Exploration Algorithm
Added a pruning stage for skipping path conditions already seen instead of just reusing their cached solutions. Previously, the Generational Search algorithm built the PCs in such a way that there were not repeated elements but this may not be the case for other path expansion strategies.
Abstracted the scoring function so that each exploration algorithm implements its own.
Generalized the tests worklist, now each algorithm defines it's own queue.
Added general logs
IMPORTANT: Reordered when a test is added, now tests are added when created instead of when explored. A lot of test cases were added to the worklist but added to the test suite only when explored, which resulted in a lot of wasted time in the solver side. In addition, there were a lot of tests that didn't end up in the test suite. We prefer to loose time minimizing the test suite later than missing already created tests.
Stopping conditions
Added MaxTestsStoppingCondition which mirrors the genetic algorithm's analogous class.
Added user selected stopping condition.
Fixes
Legacy DSE Module
fixed arrays case when creating bound in symbolic variables query
Path Divergences
Fixed comparison between branch conditions when checking for a divergence, now we check the constraints directly as branch conditions classes can be changed for a generic Branch
class when negating it.
Experiments
Compared it against the legacy module. Even though the implementation should be the same, there's a significant difference in performance. For some reason path conditions are larger, cache hit rate is 0 which results in less coverage in the same amount of time.
The legacy module was adding the test cases to the resulting test suite as soon as it created them. The new module was storing them in a worklist instead, and adding them to the test suite only when they were retrieved for exploration. This resulted in a lot of test cases stored in the worklist that didn't end up in the resulting test suite.
gofraser
commented
3 years ago
Details
Added a DFS strategy (Implementation is based on the legacy's module algorithm) and some tweaking to improve the general DSE exploration algorithm.
Changes
DSE Module
Exploration Algorithm
Stopping conditions
Fixes
Legacy DSE Module
Path Divergences
Experiments
Compared it against the legacy module. Even though the implementation should be the same, there's a significant difference in performance. For some reason path conditions are larger, cache hit rate is 0 which results in less coverage in the same amount of time.
(UPDATE) fixed experiments
The legacy module was adding the test cases to the resulting test suite as soon as it created them. The new module was storing them in a worklist instead, and adding them to the test suite only when they were retrieved for exploration. This resulted in a lot of test cases stored in the worklist that didn't end up in the resulting test suite.