TL;DR
This paper introduces LEO, a novel machine learning-based approach to accelerate symbolic execution by intelligently tuning compiler optimizations for specific code segments (functions and libraries). By learning optimal optimization settings, LEO significantly boosts symbolic execution efficiency, achieving higher code coverage than default configurations.
What Problem Does This Paper Address?
Symbolic execution is a powerful technique for automated test generation and program analysis, but its practical application is severely limited by its high computational cost. This inefficiency stems from the exponential growth of program paths and the complexity of solving the associated constraints. While various techniques have been proposed to improve symbolic execution efficiency, the problem persists. This paper tackles this challenge by exploring an orthogonal approach: transforming the program under test itself to make it easier for symbolic execution to analyze. Specifically, they focus on leveraging compiler optimizations, which are known to improve concrete execution speed, but whose impact on symbolic execution is unpredictable and can even be detrimental if not applied carefully. The core problem is that there's no one-size-fits-all set of compiler optimizations that benefits symbolic execution across all programs.
Methods
The authors propose LEO (Learning to Accelerate Symbolic Execution), a machine learning-based framework that learns to tune compiler optimizations for individual code portions of a program.
Here's a breakdown of their approach:
- Code Transformation via Compiler Optimization: Instead of refining symbolic execution algorithms, LEO modifies the target program. It uses compiler optimizations, which are standard techniques for transforming code to be more efficient (e.g., faster execution).
- Function-Level and Library-Level Optimization: LEO recognizes that different parts of a program behave differently. It splits programs into source-code functions and libraries, learning optimization settings separately for each.
- Function Optimization: For each function, LEO extracts features (e.g., program structure, complexity metrics) and uses these to train a predictive model (initially SVM-based) to determine whether a specific compiler optimization should be enabled or disabled for that function.
- Library Optimization: Due to the size of libraries, LEO treats them as a whole. It uses features related to which library functions are called by a program to predict optimization settings for libraries.
- Program-Splitter and Local-Optimizer: To apply these fine-grained optimization settings, LEO implements:
- Program-Splitter: Divides the program into individual function-level files.
- Local-Optimizer: Applies the learned compiler optimization settings to each function-level file and libraries.
- Machine Learning for Prediction: LEO uses machine learning models to predict the optimal compiler optimization settings. It trains these models on data collected from symbolic execution runs of existing programs. The "label" for training is whether a particular compiler optimization setting improves symbolic execution efficiency (measured by line coverage).
- Imbalanced Instance Processing: The authors address the common issue of imbalanced datasets in machine learning by using the SMOTE (Synthetic Minority Over-sampling Technique) algorithm to balance the training data.
Datasets
The primary dataset used for training and evaluation consists of GNU Coreutils programs. These are a collection of standard Unix command-line utilities. The authors use 76 GNU Coreutils programs for their experiments, with a total of 39,752 lines of source code (SLOC) plus internal and external library code. For mutation score evaluation, they use 40 of these programs.
Key Insights and Ideas
- Compiler Optimizations are Program-Specific for Symbolic Execution: The most striking insight is that compiler optimizations, while beneficial for concrete execution, have unpredictable and program-specific effects on symbolic execution. What speeds up one program might slow down another. This necessitates a tailored approach rather than a blanket application.
- Fine-Grained Optimization is Key: Applying compiler optimizations at a coarse, program-wide level is insufficient. LEO's success hinges on its ability to tune optimizations at the function and library level, recognizing that different code segments have different optimization needs for symbolic execution.
- Machine Learning as an Enabler: Machine learning provides a practical way to learn these complex, program-specific optimization strategies. By analyzing features of code and the performance of symbolic execution, LEO can predict effective optimization settings.
- Library Optimization is Crucial: The study highlights that optimizing libraries is particularly impactful, likely because GNU Coreutils programs heavily rely on them. This suggests that future work should focus more on sophisticated library optimization strategies.
- Code Transformation is Orthogonal to Symbolic Execution Improvements: LEO's approach of transforming the program is orthogonal to other symbolic execution acceleration techniques (like incremental or parallel execution). This means LEO can potentially be combined with these existing methods for even greater gains.
Key Results
- Significant Acceleration: LEO significantly accelerates symbolic execution.
- Higher Line Coverage: On the GNU Coreutils benchmark, LEO achieved the highest line coverage in 50 out of 68 programs compared to default KLEE configurations (all optimizations on/off).
- Average Improvement Rates:
- Compared to turning off all compiler optimizations (NO), LEO achieved an average line coverage improvement of 88.92%.
- Compared to turning on all compiler optimizations (ALL), LEO achieved an average line coverage improvement of 46.48%.
- Robustness Across Time Limits: LEO consistently outperforms ALL and NO across various testing time limits, demonstrating its effectiveness regardless of the allocated time.
- Impact of Training Time: LEO's performance improves when the training time limit is closer to the testing time limit, suggesting that more training data can lead to better optimization predictions.
- Contribution of Components: Both function and library optimization contribute to LEO's effectiveness, with library optimization showing a more pronounced impact.
- Machine Learning Algorithm Performance: LEO performs well with various machine learning algorithms, with SMO showing a slight edge.
Limitations and Future Work
- Inter-Procedural Optimizations: LEO currently predicts optimizations for individual functions. It acknowledges that inter-procedural compiler optimizations (those that consider multiple functions together) might be missed. Future work could involve predicting optimizations for subsets of functions.
- Coupling Effects of Optimizations: The authors note that some compiler optimizations have coupling effects, meaning their impact can depend on other optimizations. LEO currently learns models for each optimization independently. Future work could explore learning models that account for these dependencies.
- New Code Transformations: While LEO leverages existing compiler optimizations, the authors suggest that designing new code transformations specifically for symbolic execution would be a valuable future direction.
- Broader Subject Set: The study uses GNU Coreutils. Future work should involve a wider range of programs to ensure generalizability.
- Library Optimization Granularity: LEO currently treats libraries as a whole. Future work could explore finer-grained library optimization, perhaps by splitting libraries into sets of functions or analyzing open-source repositories.
- Combining with Other Techniques: The authors suggest combining code transformation with other symbolic execution acceleration techniques (e.g., parallel, incremental) for further gains.
Summary updated