Vulnerability benchmark generation algorithm based on finite state machines

XIE Yuandong; YAN Xuexiong; ZHAO Guangsheng; ZHAO Xu; QIU Han

doi:10.11959/j.issn.2096-109x.2025036

您当前的位置：

首页 >

文章列表页 >

Vulnerability benchmark generation algorithm based on finite state machines

Papers | 更新时间：2025-06-30

- Vulnerability benchmark generation algorithm based on finite state machines
- Chinese Journal of Network and Information Security Vol. 11, Issue 3, Pages: 150-162(2025)
- 作者机构：
  
  网络空间安全教育部重点实验室，河南郑州 450001
- 作者简介：
- 基金信息：
  
  The Natural Science Foundation of Henan Province of China(242300421415)
- DOI：10.11959/j.issn.2096-109x.2025036
  CLC： TP311
- Received：31 October 2024，
  
  Revised：2025-03-31，
  
  Published：25 June 2025
- 稿件说明：
移动端阅览
谢元栋, 颜学雄, 赵光胜, 等. 基于有限状态机的漏洞基准测试集生成算法[J]. 网络与信息安全学报, 2025, 11(3): 150-162.

Format: XIE Y D, YAN X X, ZHAO G S, et al. Vulnerability benchmark generation algorithm based on finite state machines[J]. Chinese Journal of Network and Information Security, 2025, 11(3): 150-162.
谢元栋, 颜学雄, 赵光胜, 等. 基于有限状态机的漏洞基准测试集生成算法[J]. 网络与信息安全学报, 2025, 11(3): 150-162. DOI： 10.11959/j.issn.2096-109x.2025036.

Format: XIE Y D, YAN X X, ZHAO G S, et al. Vulnerability benchmark generation algorithm based on finite state machines[J]. Chinese Journal of Network and Information Security, 2025, 11(3): 150-162. DOI： 10.11959/j.issn.2096-109x.2025036.

摘要

随着各类源代码漏洞挖掘技术的出现与发展，如何评估各种工具的漏洞挖掘能力是一个重要问题。源代码漏洞基准测试集是用于评估面向源代码的漏洞挖掘工具能力的源代码程序集，是开展评估工作的重要基础。已有的源代码漏洞基准测试集大多数对模拟真实程序代码的复杂性和多样性重视不足，导致漏洞挖掘工具在基准测试集与真实程序代码中的表现差异很大。并且，现有源代码基准测试集未提供对漏洞辨别率的测试支撑，使得工具评估缺失一个重要维度。针对上述问题，对漏洞抽象三元组及可利用漏洞链进行了研究，提出了一种基于有限状态机的源代码漏洞基准测试集生成算法。首先建立源代码基准测试集有限状态机模型，构建基本代码路径；其次利用条件编辑距离选择辨别率指标专用路径；最后使用代码圈复杂度包装器对路径元素进行包装，以模拟现实代码的复杂结构。实验结果表明，该算法生成的漏洞基准测试集与真实软件复杂性更加接近，能够发现漏洞挖掘工具在代码路径上存在的偏向性和不足，证明了其有效性和实用性。

Abstract

The emergence and development of various source code vulnerability detection techniques led to the evaluation of these tools’ effectiveness becoming a critical issue. Source code vulnerability benchmarks were regarded as a basic basis for such evaluations. However

most of the existing benchmarks were found to inadequately simulate the complexity and diversity of real-world code

leading to significant discrepancies between benchmark testing and actual program analysis. Furthermore

current source code benchmarks were observed to lack support for testing vulnerability discriminability

resulting in an incomplete evaluation dimension. To address these limitations

vulnerability abstract triples and exploitable vulnerability chains were investigated

and a finite-state-machine-based algorithm for generating source code vulnerability benchmarks was proposed. The approach consisted of three steps. First

a finite - state machine model was established to construct basic code paths. Second

conditional edit distance was employed to select discriminability-specific paths. Third

cyclomatic complexity wrappers were used to encapsulate path elements

thereby simulating the intricate structures of real-world code. Experimental results demonstrate that the generated benchmarks more closely resemble the complexity of real software

effectively exposing biases and deficiencies in vulnerability detection tools across different code paths. This study validates the algorithm’s effectiveness and practical utility

confirming that it provides a more comprehensive and realistic benchmark for evaluating vulnerability detection tools.

关键词

Keywords

references

OKUN V , GAUCHER R , BLACK P E . The static analysis tool exposition (SATE) 2008: NIST SP 500-279 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2009 .

OKUN V , BLACK P E , DELAITRE A M . The second static analysis tool exposition (SATE) 2009: NIST SP 500-287 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2010 .

OKUN V , BLACK P E , DELAITRE A M . Report on the third static analysis tool exposition (SATE 2010): NIST SP 500-283 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2011 .

OKUN V , DELAITRE A M , BLACK P E . Report on the static analysis tool exposition (SATE) IV: NIST SP 500-297 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2013 .

DELAITRE A M , STIVALET B C , BLACK P E , et al . SATE V report: ten years of static analysis tool expositions: NIST SP 500-326 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2018 .

DELAITRE A , BLACK P E , CUPIF D , et al . SATE VI report: bug injection and collection: NIST SP 500-341 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2023 .

MBURANO B , SI W . Evaluation of web vulnerability scanners based on OWASP benchmark [C ] // 2018 26th International Conference on Systems Engineering . Piscataway : IEEE Press , 2018 : 1 - 6 .

BLACK P E , MENTZER W , FONG E , et al . Vulnerability test suite generator (VTSG) version 3: NIST IR 8493 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2023 .

SCHUCKERT F , LANGWEG H , KATT B . Systematic generation of XSS and SQLi vulnerabilities in PHP as test cases for static code analysis [C ] // Proceedings of 2022 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW) . 2022 : 261 - 268 .

OLIVEIRA C . Real world software assurance test suite: STONESOUP (presentation) [C ] // Proceedings of IEEE 27th Software Technology Conference (STC’ 2015). 2015 .

DE OLIVEIRA C , FONG E , BLACK P . Impact of code complexity on software analysis: NIST internal or interagency report (NISTIR) 8165 [R ] . Gaithersburg, MD : National Institute of Standards and Technology , 2017 .

DOLAN-GAVITT B , HULIN P , KIRDA E , et al . LAVA: large-scale automated vulnerability addition [C ] // Proceedings of 2016 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2016 : 110 - 121 .

PEWNY J , HOLZ T . EvilCoder: automated bug insertion [C ] // Proceedings of the 32nd Annual Conference on Computer Security Applications . New York : ACM Press , 2016 : 214 - 225 .

KASHYAP V , RUCHTI J , KOT L , et al . Automated customized bug-benchmark generation [C ] // Proceedings of the 19th International Working Conference on Source Code Analysis and Manipulation (SCAM) . Piscataway : IEEE Press , 2019 : 103 - 114 .

HAZIMEH A , HERRERA A , PAYER M . Magma: a ground-truth fuzzing benchmark [J ] . Proceedings of the ACM on Measurement and Analysis of Computing Systems , 2020 , 4 ( 3 ): 1 - 29 .

ZHANG Z , PATTERSON Z , HICKS M , et al . FixReverter: a realistic bug injection methodology for benchmarking fuzz testing [C ] // Proceedings of 31st USENIX Security Symposium (USENIX Security 22) . Berkeley : USENIX Association , 2022 : 3699 - 3715 .

JIANG Z , LI R , TANG C . BugAnaBench: benchmark for software vulnerability analysis and its construction method [C ] // Proceedings of International Symposium on Computer Technology and Information Science (ISCTIS 2022) . Guilin : SPIE , 2022 .

STIVALET B , FONG E . Large scale generation of complex and faulty PHP test cases [C ] // Proceedings of 2016 IEEE International Conference on Software Testing, Verification and Validation (ICST) . Piscataway : IEEE Press , 2016 : 409 - 415 .

SESTILI C D , SNAVELY W S , VANHOUDNOS N M . Towards security defect prediction with AI [J ] . arXiv Preprint , arXiv: 1808.09897 , 2018 .

LEE H , KIM S , CHA S K . Fuzzle: making a puzzle for fuzzers [C ] // Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering . New York : ACM Press , 2022 .

FELICI R , POZZI L , FURIA C A . HyperPUT: generating synthetic faulty programs to challenge bug-finding tools [J ] . Empirical Software Engineering , 2024 , 29 ( 2 ): 38 .

MCCABE T J . A complexity measure [J ] . IEEE Transactions on Software Engineering , 1976 , SE-2( 4 ): 308 - 320 .

PAGE M J , MCKENZIE J E , BOSSUYT P M , et al . The PRISMA 2020 statement: an updated guideline for reporting systematic reviews [J ] . Systematic Reviews , 2021 , 10 ( 1 ): 89 .

CHOWDHURY I , ZULKERNINE M . Using complexity, coupling, and cohesion metrics as early indicators of vulnerabilities [J ] . Journal of Systems Architecture , 2011 , 57 ( 3 ): 294 - 313 .

MEDEIROS N , IVAKI N , COSTA P , et al . Software metrics as indicators of security vulnerabilities [J ] . IEEE International Symposium on Software Reliability Engineering , 2017 .

马总帅 , 武泽慧 , 燕宸毓 , 等 . 漏洞基准测试集构建技术综述 [J ] . 计算机科学 , 2024 , 51 ( 1 ): 316 - 326 .

MA Z S , WU Z H , YAN C Y , et al . Survey of vulnerability benchmark construction technique [J ] . Computer Science , 2024 , 51 ( 1 ): 316 - 326 .

黄诚 , 孙明旭 , 段仁语 , 等 . 面向项目版本差异性的漏洞识别技术研究 [J ] . 网络与信息安全学报 , 2022 , 8 ( 1 ): 52 - 62 .

HUANG C , SUN M X , DUAN R Y , et al . Vulnerability identification technology research based on project version difference [J ] . Chinese Journal of Network and Information Security , 2022 , 8 ( 1 ): 52 - 62 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰