QSF: Multi-objective Optimization Based Efficient Solving for Floating-Point Constraints
Proceedings of the ACM on Software Engineering · 19.06.2025 · 2 (FSE) · 511-532
DOI: 10.1145/3715739 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Software Engineering, online erschienen am 19.06.2025. Verfasst von Xu Yang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 68 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0). Gefördert von: National Key R&D Program of China, NSFC.
Abstract (Originalsprache)
Floating-point constraint solving is challenging due to the complex representation and non-linear computations. Search-based constraint solving provides an effective method for solving floating-point constraints. In this paper, we propose QSF to improve the efficiency of search-based solving for floating-point constraints. The key idea of QSF is to model the floating-point constraint solving problem as a multi-objective optimization problem. Specifically, QSF considers both the number of unsatisfied constraints and the sum of the violation degrees of unsatisfied constraints as the objectives for search-based optimization. Besides, we propose a new evolutionary algorithm in which the mutation operators are specially designed for floating-point numbers, aiming to solve the multi-objective problem more efficiently. We have implemented QSF and conducted extensive experiments on both the SMT-COMP benchmark and the benchmark from real-world floating-point programs. The results demonstrate that compared to SOTA floating-point solvers, QSF achieved an average speedup of 15.72X under a 60-second timeout and an impressive 87.48X under a 600-second timeout on the first benchmark. Similarly, on the second benchmark, QSF delivered an average speedup of 22.44X and 29.23X, respectively, under the two timeout configurations. Furthermore, QSF has also enhanced the performance of symbolic execution for floating-point programs.
Förderung
- National Key R&D Program of China
- NSFC
Zitieren
APA
Yang, X., Chen, Z., Dong, W., & Wang, J. (2025). QSF: Multi-objective Optimization Based Efficient Solving for Floating-Point Constraints. Proceedings of the ACM on Software Engineering, 2(FSE), 511-532. https://doi.org/10.1145/3715739
Vancouver
Yang X, Chen Z, Dong W, Wang J. QSF: Multi-objective Optimization Based Efficient Solving for Floating-Point Constraints. Proceedings of the ACM on Software Engineering. 2025;2(FSE):511-532. doi:10.1145/3715739
BibTeX
@article{Yang2025,
author = {Yang, Xu and Chen, Zhenbang and Dong, Wei and Wang, Ji},
title = {QSF: Multi-objective Optimization Based Efficient Solving for Floating-Point Constraints},
journal = {Proceedings of the ACM on Software Engineering},
year = {2025},
volume = {2},
number = {FSE},
pages = {511--532},
doi = {10.1145/3715739}
}
EUVIMED