自动选择软件验证算法,无需标签也能准确匹配最佳工具。
MFH: A Multi-faceted Heuristic Algorithm Selection Approach for Software Verification
- 基于代码属性图和间接启发式,自动推断可用算法。
- 91.47%准确率,无标签训练下仍表现优异。
- 支持新工具快速扩展,适合工业级验证系统集成。
当前众多验证算法可用于提升软件可靠性,但选择合适算法需领域知识与大量人力。现有自动化选择方法或依赖带标签的高质量样本,或依赖人工设计启发式,存在数据依赖性强、可扩展性差的问题。本文提出MFH方法,通过分析能正确输出结果的验证器所采用的算法,间接推断潜在适用算法。该方法将代码属性图(CPG)嵌入模型以增强鲁棒性,将选择任务分解为预测可用算法与匹配最优验证器两步,并引入错误预测反馈机制持续优化。在20个验证器及超过1.5万个验证任务上评估,结果显示:即使训练时无真实算法标签,仍达到91.47%的预测准确率;新增10个验证器后准确率仅下降0.84%,证明其强可扩展性。
原文摘要 · Abstract (English)
Currently, many verification algorithms are available to improve the reliability of software systems. Selecting the appropriate verification algorithm typically demands domain expertise and non-trivial manpower. An automated algorithm selector is thus desired. However, existing selectors, either depend on machine-learned strategies or manually designed heuristics, encounter issues such as reliance on high-quality samples with algorithm labels and limited scalability. In this paper, an automated algorithm selection approach, namely MFH, is proposed for software verification. Our approach leverages the heuristics that verifiers producing correct results typically implement certain appropriate algorithms, and the supported algorithms by these verifiers indirectly reflect which ones are potentially applicable. Specifically, MFH embeds the code property graph (CPG) of a semantic-preserving transformed program to enhance the robustness of the prediction model. Furthermore, our approach decomposes the selection task into the sub-tasks of predicting potentially applicable algorithms and matching the most appropriate verifiers. Additionally, MFH also introduces a feedback loop on incorrect predictions to improve model prediction accuracy. We evaluate MFH on 20 verifiers and over 15,000 verification tasks. Experimental results demonstrate the effectiveness of MFH, achieving a prediction accuracy of 91.47% even without ground truth algorithm labels provided during the training phase. Moreover, the prediction accuracy decreases only by 0.84% when introducing 10 new verifiers, indicating the strong scalability of the proposed approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。