Introduction
Software testing is a critical yet resource-intensive phase of development, often accounting for over 50% of total costs. Automated test data generation aims to alleviate this burden, but traditional methods often fall short. Evolutionary Algorithms (EA), such as Genetic Algorithms (GA), are flexible but can struggle with vast input spaces. Conversely, Symbolic Execution (SE) offers mathematical precision but is hindered by "path explosion" and complex code structures. This paper proposes a hybrid framework that integrates the global search capabilities of GAs with the precision of SE to optimize test coverage.
Methodology
The proposed framework utilizes a three-pronged strategy to enhance test data generation:
- Smart Seeding: Instead of random initialization, the system uses SE to generate high-quality initial test cases based on potentially feasible paths identified via the Y&M method.
- Dynamic Domain Reduction (DDR): The search space is pruned by identifying constraints for uncovered branches, focusing the GA on relevant input ranges.
- Evolutionary Search Variations: The framework supports three GA types: Standard GA (decision-focused), Differential GA (contribution-focused), and a Hybrid GA (two-stage refinement).
Experimental Evaluation
The framework was evaluated using 13 benchmark programs written in Java and C, ranging from classic logic problems to structural benchmarks.
These test objects provide a diverse set of challenges, with code sizes up to 86 lines and branch counts reaching 78, as seen in the "Dbll" program in Table 1.
Results and Impact
The hybrid approach demonstrated significant improvements in branch coverage within a 30-second execution window. By "warm starting" the evolution with SE-derived seeds and pruning irrelevant variables, the system achieved much higher efficiency than pure evolutionary methods.
Key findings include:
- Substantial Coverage Gains: The hybrid method outperformed pure GAs by an average of 16.36% for Approach 1, 13.93% for Approach 2, and 12.78% for Approach 3.
- Full Coverage Milestones: For several benchmarks, including "Triangle," "Binary search," and "Bubble sort," the hybrid method reached 100% branch coverage, a feat pure EAs often failed to achieve.
- Component Contribution: Analysis showed that seeding alone contributed an 8-10% improvement, while domain reduction added a further 1.5-2.5% boost.
Conclusion and Future Work
The integration of Symbolic Execution as a guide for Evolutionary Algorithms effectively addresses the limitations of both techniques. While the current study focused on smaller benchmarks, the results provide a strong proof-of-concept for hybrid test generation. Future work will focus on scaling the framework for enterprise-level software, improving the handling of complex pointers, and optimizing the balance between symbolic and evolutionary search phases.
Summary updated