Towards Efficient Data-flow Test Data Generation

Ting Su, Chengyu Zhang, Yichen Yan, Lingling Fan, Geguang Pu, Yang Liu, Zhoulai Fu, Zhendong SuTheories of Programming and Formal Methods 2018 · OpenReview

Abstract

Data-flow testing (DFT) aims to detect potential data interaction anomalies by focusing on the points at which variables receive values and the points at which these values are used. Such test objectives are referred as def-use pairs. However, the complexity of DFT still overwhelms the testers in practice. To tackle this problem, we introduce a hybrid testing framework for data-flow based test generation: (1) The core of our framework is symbolic execution (SE), enhanced by a novel guided path exploration strategy to improve testing performance; and (2) we systematically cast DFT as reachability checking in software model checking (SMC) to complement SE, yielding practical DFT that combines the two techniques' strengths. Our evaluation on the 28,354 def-use pairs collected from 33 open-source and industrial program subjects shows (1) our SE-based approach can improve DFT performance by 15–48% in terms of testing time, compared with existing search strategies; and (2) our combined approach can further reduce testing time by 20.1–93.6%, and improve data-flow coverage by 27.8–45.2% by eliminating infeasible test objectives. Compared with the SMC-based approach alone, our combined approach can also reduce testing time by 19.9–23.8%, and improve data-flow coverage by 7–10%. This combined approach also enables the cross-checking of each component for reliable and robust testing results.

Introduction

While control-flow testing is widely used to ensure statement or branch coverage, data-flow testing (DFT) provides a more rigorous assessment by tracking "def-use pairs"—the relationship between where a variable is defined and where it is subsequently used. Despite its effectiveness, DFT faces significant practical challenges: the sheer number of def-use pairs, the "path explosion" problem in automated tools, and the prevalence of infeasible test objectives that waste computational resources.

The Hybrid Testing Framework

To address these challenges, we propose a hybrid framework that integrates Symbolic Execution (SE) and Software Model Checking (SMC). The architecture, illustrated in Figure 1, leverages the complementary strengths of these two techniques.

The hybrid testing framework architecture.

The process begins with static analysis to identify def-use pairs and "cut points"—mandatory intermediate locations in the code. The SE engine then attempts to find feasible paths. If the SE engine times out or fails to cover a pair, the task is handed over to the SMC component. SMC is particularly adept at proving the infeasibility of a path, allowing the framework to prune impossible objectives quickly.

Guided Path Exploration with Cut Points

A key innovation in our framework is the Cut-Point Guided Search (CPGS) strategy. By identifying "must-pass" nodes (dominators) in the control-flow graph, we can guide the symbolic execution engine toward the target "use" point more efficiently.

Example program and its control-flow graph used for identifying def-use pairs and cut points.

As shown in Figure 2, the program's structure is analyzed to determine the sequence of nodes that must be traversed to satisfy a def-use pair. CPGS prioritizes paths based on their distance to the next cut point and prunes paths that redefine the target variable prematurely, significantly narrowing the search space.

Evaluation and Results

We evaluated our framework using 33 program subjects, including industrial modules and open-source drivers, totaling over 28,000 def-use pairs.

The results demonstrate substantial improvements:

  • Efficiency: The CPGS strategy alone improved SE performance by 15–48%. The full hybrid approach reduced total testing time by up to 93.6% compared to SE alone.
  • Coverage: By effectively identifying and ignoring infeasible pairs, the hybrid approach increased data-flow coverage by 27.8–45.2%.
  • Robustness: The independent nature of SE and SMC allowed for cross-checking, which helped identify bugs in the underlying tools during development.

Conclusion

Our hybrid framework demonstrates that combining guided symbolic execution with software model checking can overcome the traditional bottlenecks of data-flow testing. By treating test generation as a reachability problem and utilizing cut points for guidance, we achieve higher coverage and greater efficiency than either technique could provide in isolation.

Summary updated

Abstract

Data-flow testing (DFT) aims to detect potential data interaction anomalies by focusing on the points at which variables receive values and the points at which these values are used. Such test objectives are referred as \emph{def-use pairs}. However, the complexity of DFT still overwhelms the testers in practice. To tackle this problem, we introduce a hybrid testing framework for data-flow based test generation: (1) The core of our framework is symbolic execution (SE), enhanced by a novel guided path exploration strategy to improve testing performance; and (2) we systematically cast DFT as reachability checking in software model checking (SMC) to complement SE, yielding practical DFT that combines the two techniques' strengths. We implemented our framework for C programs on top of the state-of-the-art symbolic execution engine KLEE and instantiated with three different software model checkers. Our evaluation on the 28,354 def-use pairs collected from 33 open-source and industrial program subjects shows (1) our SE-based approach can improve DFT performance by 15$\sim$48% in terms of testing time, compared with existing search strategies; and (2) our combined approach can further reduce testing time by 20.1$\sim$93.6%, and improve data-flow coverage by 27.8$\sim$45.2% by eliminating infeasible test objectives. Compared with the SMC-based approach alone, our combined approach can also reduce testing time by 19.9$\sim$23.8%, and improve data-flow coverage by 7$\sim$10%. This combined approach also enables the cross-checking of each component for reliable and robust testing results. We have made our testing framework and benchmarks publicly available to facilitate future research.
BibTeX
@inproceedings{su2018towards,
  author = {Ting Su and Chengyu Zhang and Yichen Yan and Lingling Fan and Geguang Pu and Yang Liu and Zhoulai Fu and Zhendong Su},
  title = {{Towards Efficient Data-flow Test Data Generation}},
  booktitle = {Theories of Programming and Formal Methods},
  year = {2018},
  url = {https://openreview.net/forum?id=gDMZGNcyfh3},
}
Figure