Learning to Accelerate Symbolic Execution via Code Transformation

Junjie Chen, Wenxiang Hu, Lingming Zhang, Dan Hao, Sarfraz Khurshid, Lu ZhangECOOP 2018 · OpenReview

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

Abstract

Symbolic execution is an effective but expensive technique for automated test generation. Over the years, a large number of refined symbolic execution techniques have been proposed to improve its efficiency. However, the symbolic execution efficiency problem remains, and largely limits the application of symbolic execution in practice. Orthogonal to refined symbolic execution, in this paper we propose to accelerate symbolic execution through semantic-preserving code transformation on the target programs. During the initial stage of this direction, we adopt a particular code transformation, compiler optimization, which is initially proposed to accelerate program concrete execution by transforming the source program into another semantic-preserving target program with increased efficiency (e.g., faster or smaller). However, compiler optimizations are mostly designed to accelerate program concrete execution rather than symbolic execution. Recent work also reported that unified settings on compiler optimizations that can accelerate symbolic execution for any program do not exist at all. Therefore, in this work we propose a machine-learning based approach to tuning compiler optimizations to accelerate symbolic execution, whose results may also aid further design of specific code transformations for symbolic execution. In particular, the proposed approach LEO separates source-code functions and libraries through our program-splitter, and predicts individual compiler optimization (i.e., whether a type of code transformation is chosen) separately through analyzing the performance of existing symbolic execution. Finally, LEO applies symbolic execution on the code transformed by compiler optimization (through our local-optimizer). We conduct an empirical study on GNU Coreutils programs using the KLEE symbolic execution engine. The results show that LEO significantly accelerates symbolic execution, outperforming the default KLEE configurations (i.e., turning on/off all compiler optimizations) in various settings, e.g., with the default training/testing time, LEO achieves the highest line coverage in 50/68 programs, and its average improvement rate on all programs is 46.48%/88.92% in terms of line coverage compared with turning on/off all compiler optimizations.
BibTeX
@inproceedings{chen2018learning,
  author = {Junjie Chen and Wenxiang Hu and Lingming Zhang and Dan Hao and Sarfraz Khurshid and Lu Zhang},
  title = {{Learning to Accelerate Symbolic Execution via Code Transformation}},
  booktitle = {ECOOP},
  year = {2018},
  url = {https://openreview.net/forum?id=MxHxDl-eHq},
}
Figure