{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:14:15Z","timestamp":1775873655424,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"FSE","funder":[{"name":"European Research Council","award":["850868"],"award-info":[{"award-number":["850868"]}]},{"name":"ERC","award":["CoG Project AT_SCALE (101179366)"],"award-info":[{"award-number":["CoG Project AT_SCALE (101179366)"]}]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["PCEGP2 186974"],"award-info":[{"award-number":["PCEGP2 186974"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"State of Upper Austria","award":["888338"],"award-info":[{"award-number":["888338"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2025,6,19]]},"abstract":"<jats:p>\n            Can a fuzzer cover more code with minimal corruption of the initial seed?        Before a seed is fuzzed, the early greybox fuzzers first systematically enumerated slightly         corrupted inputs by applying every mutation operator to every part of the seed, once per generated         input. The hope of this so-called\n            <jats:italic toggle=\"yes\">\u201cdeterministic\u201d stage<\/jats:italic>\n            was that simple changes to the         seed would be less likely to break the complex file format; the resulting inputs would find bugs         in the program logic well beyond the program\u2019s parser. However, when experiments showed that         disabling the deterministic stage achieves more coverage, applying multiple mutation         operators at the same time to a single input, most fuzzers disabled the         deterministic stage by default.                Instead of ignoring the deterministic stage, we analyze its potential and substantially improve         deterministic exploration. Our deterministic stage is now the default in AFL++, reverting the         earlier decision of dropping deterministic exploration.        We start by investigating the overhead and the contribution         of the deterministic stage to the discovery of coverage-increasing inputs. While the sheer number         of generated inputs explains the overhead, we find that only a few critical seeds (20%), and only         a few critical bytes in a seed (0.5%) are responsible for the vast majority of the         coverage-increasing inputs (83% and 84%, respectively). Hence, we develop an efficient         technique, called , to identify these critical seeds \/ bytes so as to prune a large number         of unnecessary inputs. retains the benefits of the classic deterministic stage by         only enumerating a tiny part of the total deterministic state space.                We evaluate implementation on two benchmarking frameworks,         FuzzBench and Magma. Our evaluation shows that outperforms state-of-the-art fuzzers         with and without the (old) deterministic stage enabled, both in terms of coverage and bug finding.         also discovered 8 new CVEs on exhaustively fuzzed security-critical applications.         Finally, has been independently evaluated and integrated into AFL++ as default option.\n          <\/jats:p>","DOI":"10.1145\/3715713","type":"journal-article","created":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T15:16:02Z","timestamp":1750346162000},"page":"44-64","source":"Crossref","is-referenced-by-count":3,"title":["MendelFuzz: The Return of the Deterministic Stage"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5689-3075","authenticated-orcid":false,"given":"Han","family":"Zheng","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7114-5640","authenticated-orcid":false,"given":"Flavio","family":"Toffalini","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"},{"name":"Ruhr-Universit\u00e4t, Bochum, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4470-1824","authenticated-orcid":false,"given":"Marcel","family":"B\u00f6hme","sequence":"additional","affiliation":[{"name":"MPI for Security and Privacy, Bochum, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5054-7547","authenticated-orcid":false,"given":"Mathias","family":"Payer","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,19]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"AFL. 2019. technical_details.txt. https:\/\/github.com\/google\/AFL\/blob\/master\/docs\/perf_tips.txt"},{"key":"e_1_2_1_2_1","unstructured":"AFLplusplus. 2025. AFLplusplus: edge coverage and collision-free coverage. https:\/\/github.com\/AFLplusplus\/AFLplusplus\/blob\/stable\/instrumentation\/README.llvm.md"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"REDQUEEN: Fuzzing with Input-to-State Correspondence","volume":"19","author":"Aschermann Cornelius","year":"2019","unstructured":"Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and Thorsten Holz. 2019. REDQUEEN: Fuzzing with Input-to-State Correspondence.. In NDSS. 19, 1\u201315.","journal-title":"NDSS."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 28th ACM joint meeting on European software engineering conference and symposium on the foundations of software engineering. 713\u2013724","author":"B\u00f6hme Marcel","year":"2020","unstructured":"Marcel B\u00f6hme and Brandon Falk. 2020. Fuzzing: On the exponential cost of vulnerability discovery. In Proceedings of the 28th ACM joint meeting on European software engineering conference and symposium on the foundations of software engineering. 713\u2013724."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 678\u2013689","author":"B\u00f6hme Marcel","year":"2020","unstructured":"Marcel B\u00f6hme, Valentin JM Man\u00e8s, and Sang Kil Cha. 2020. Boosting fuzzer efficiency: An information theoretic perspective. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 678\u2013689."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 1032\u20131043","author":"B\u00f6hme Marcel","year":"2016","unstructured":"Marcel B\u00f6hme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage-based greybox fuzzing as markov chain. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 1032\u20131043."},{"key":"e_1_2_1_7_1","unstructured":"centipede. 2023. centipede. https:\/\/github.com\/google\/centipede"},{"key":"e_1_2_1_8_1","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Chen Ju","year":"2022","unstructured":"Ju Chen, Wookhyun Han, Mingjun Yin, Haochen Zeng, Chengyu Song, Byoungyoung Lee, Heng Yin, and Insik Shin. 2022. $SYMSAN$: Time and Space Efficient Concolic Execution via Dynamic Data-flow Analysis. In 31st USENIX Security Symposium (USENIX Security 22). 2531\u20132548."},{"key":"e_1_2_1_9_1","volume-title":"2018 IEEE Symposium on Security and Privacy (SP). 711\u2013725","author":"Chen Peng","year":"2018","unstructured":"Peng Chen and Hao Chen. 2018. Angora: Efficient fuzzing by principled search. In 2018 IEEE Symposium on Security and Privacy (SP). 711\u2013725."},{"key":"e_1_2_1_10_1","volume-title":"2020 IEEE Symposium on Security and Privacy (SP). 1580\u20131596","author":"Chen Yaohui","year":"2020","unstructured":"Yaohui Chen, Peng Li, Jun Xu, Shengjian Guo, Rundong Zhou, Yulong Zhang, Tao Wei, and Long Lu. 2020. Savior: Towards bug-driven hybrid testing. In 2020 IEEE Symposium on Security and Privacy (SP). 1580\u20131596."},{"key":"e_1_2_1_11_1","volume-title":"2019 IEEE\/ACM 41st International Conference on Software Engineering (ICSE). 736\u2013747","author":"Choi Jaeseung","year":"2019","unstructured":"Jaeseung Choi, Joonun Jang, Choongwoo Han, and Sang Kil Cha. 2019. Grey-box concolic testing on binary code. In 2019 IEEE\/ACM 41st International Conference on Software Engineering (ICSE). 736\u2013747."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis. 1\u201313","author":"Fioraldi Andrea","year":"2020","unstructured":"Andrea Fioraldi, Daniele Cono D\u2019Elia, and Emilio Coppa. 2020. WEIZZ: Automatic grey-box fuzzing for structured binary formats. In Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis. 1\u201313."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 14th USENIX Conference on Offensive Technologies. 10\u201310","author":"Fioraldi Andrea","year":"2020","unstructured":"Andrea Fioraldi, Dominik Maier, Heiko Ei\u00df feldt, and Marc Heuse. 2020. AFL++ combining incremental steps of fuzzing research. In Proceedings of the 14th USENIX Conference on Offensive Technologies. 10\u201310."},{"key":"e_1_2_1_14_1","unstructured":"FuzzBench. 2020. FuzzBench: 2020-03-11 report. https:\/\/www.fuzzbench.com\/reports\/paper\/AFL-Deterministic-Experiment\/index.html"},{"key":"e_1_2_1_15_1","unstructured":"FuzzBench. 2020. FuzzBench: 2021-04-23-paper report. https:\/\/www.fuzzbench.com\/reports\/paper\/Main-Experiment\/index.html"},{"key":"e_1_2_1_16_1","volume-title":"29th USENIX security symposium (USENIX Security 20). 2577\u20132594.","author":"Gan Shuitao","unstructured":"Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, and Zuoning Chen. 2020. $GREYONE$: Data flow sensitive fuzzing. In 29th USENIX security symposium (USENIX Security 20). 2577\u20132594."},{"key":"e_1_2_1_17_1","volume-title":"2018 IEEE Symposium on Security and Privacy (SP). 679\u2013696","author":"Gan Shuitao","year":"2018","unstructured":"Shuitao Gan, Chao Zhang, Xiaojun Qin, Xuwen Tu, Kang Li, Zhongyu Pei, and Zuoning Chen. 2018. Collafl: Path sensitive fuzzing. In 2018 IEEE Symposium on Security and Privacy (SP). 679\u2013696."},{"key":"e_1_2_1_18_1","unstructured":"Google. 2023. FuzzBench Evaluation Report. https:\/\/fuzzbench.com\/reports\/experimental\/2023-04-27-main\/index.html"},{"key":"e_1_2_1_19_1","volume-title":"oss-fuzz progress","year":"2023","unstructured":"google. 2023. oss-fuzz progress in 2023.txt. https:\/\/security.googleblog.com\/2023\/02\/taking-next-step-oss-fuzz-in-2023.html"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3428334","article-title":"Magma: A ground-truth fuzzing benchmark","volume":"4","author":"Hazimeh Ahmad","year":"2020","unstructured":"Ahmad Hazimeh, Adrian Herrera, and Mathias Payer. 2020. Magma: A ground-truth fuzzing benchmark. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4, 3 (2020), 1\u201329.","journal-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems"},{"key":"e_1_2_1_21_1","unstructured":"Marc Heuse. 2023. magma is using outdated afl++. https:\/\/github.com\/HexHive\/magma\/pull\/142"},{"key":"e_1_2_1_22_1","unstructured":"honggfuzz. 2019. honggfuzz. https:\/\/github.com\/google\/honggfuzz"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering. 475\u2013485","author":"Lemieux Caroline","year":"2018","unstructured":"Caroline Lemieux and Koushik Sen. 2018. Fairfuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage. In Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering. 475\u2013485."},{"key":"e_1_2_1_24_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Li Yuwei","year":"2021","unstructured":"Yuwei Li, Shouling Ji, Yuan Chen, Sizhuang Liang, Wei-Han Lee, Yueyao Chen, Chenyang Lyu, Chunming Wu, Raheem Beyah, and Peng Cheng. 2021. $UNIFUZZ$: A Holistic and Pragmatic $Metrics-Driven$ Platform for Evaluating Fuzzers. In 30th USENIX Security Symposium (USENIX Security 21). 2777\u20132794."},{"key":"e_1_2_1_25_1","unstructured":"libfuzzer. 2023. libfuzzer. https:\/\/llvm.org\/docs\/LibFuzzer.html"},{"key":"e_1_2_1_26_1","volume-title":"USENIX Security Symposium. 1949\u20131966","author":"Lyu Chenyang","year":"2019","unstructured":"Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, and Raheem Beyah. 2019. MOPT: Optimized Mutation Scheduling for Fuzzers.. In USENIX Security Symposium. 1949\u20131966."},{"key":"e_1_2_1_27_1","volume-title":"29th Annual Network and Distributed System Security Symposium. https:\/\/dx. doi. org\/10","author":"Lyu Chenyang","year":"2022","unstructured":"Chenyang Lyu, Shouling Ji, Xuhong Zhang, Hong Liang, Binbin Zhao, Kangjie Lu, and Raheem Beyah. 2022. Ems: History-driven mutation for coverage-based fuzzing. In 29th Annual Network and Distributed System Security Symposium. https:\/\/dx. doi. org\/10.14722\/ndss. 10."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 29th ACM joint meeting on European software engineering conference and symposium on the foundations of software engineering. 1393\u20131403","author":"Metzman Jonathan","year":"2021","unstructured":"Jonathan Metzman, L\u00e1szl\u00f3 Szekeres, Laurent Simon, Read Sprabery, and Abhishek Arya. 2021. Fuzzbench: an open fuzzer benchmarking platform and service. In Proceedings of the 29th ACM joint meeting on European software engineering conference and symposium on the foundations of software engineering. 1393\u20131403."},{"key":"e_1_2_1_29_1","first-page":"1980","article-title":"Smart greybox fuzzing","volume":"47","author":"Pham Van-Thuan","year":"2019","unstructured":"Van-Thuan Pham, Marcel B\u00f6hme, Andrew E Santosa, Alexandru R\u0103zvan C\u0103ciulescu, and Abhik Roychoudhury. 2019. Smart greybox fuzzing. IEEE Transactions on Software Engineering, 47, 9 (2019), 1980\u20131997.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_2_1_30_1","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Poeplau Sebastian","year":"2020","unstructured":"Sebastian Poeplau and Aur\u00e9lien Francillon. 2020. Symbolic execution with $SymCC$: Don\u2019t interpret, compile!. In 29th USENIX Security Symposium (USENIX Security 20). 181\u2013198."},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"VUzzer: Application-aware evolutionary fuzzing","volume":"17","author":"Rawat Sanjay","year":"2017","unstructured":"Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. 2017. VUzzer: Application-aware evolutionary fuzzing.. In NDSS. 17, 1\u201314.","journal-title":"NDSS."},{"key":"e_1_2_1_32_1","volume-title":"2024 IEEE Symposium on Security and Privacy (SP). 1974\u20131993","author":"Schloegel Moritz","year":"2024","unstructured":"Moritz Schloegel, Nils Bars, Nico Schiller, Lukas Bernhard, Tobias Scharnowski, Addison Crump, Arash Ale-Ebrahim, Nicolai Bissantz, Marius Muench, and Thorsten Holz. 2024. Sok: Prudent evaluation practices for fuzzing. In 2024 IEEE Symposium on Security and Privacy (SP). 1974\u20131993."},{"key":"e_1_2_1_33_1","volume-title":"2022 IEEE Symposium on Security and Privacy (SP). 2194\u20132211","author":"She Dongdong","year":"2022","unstructured":"Dongdong She, Abhishek Shah, and Suman Jana. 2022. Effective seed scheduling for fuzzing with graph centrality analysis. In 2022 IEEE Symposium on Security and Privacy (SP). 2194\u20132211."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 44th International Conference on Software Engineering. 1634\u20131645","author":"Wu Mingyuan","year":"2022","unstructured":"Mingyuan Wu, Ling Jiang, Jiahong Xiang, Yanwei Huang, Heming Cui, Lingming Zhang, and Yuqun Zhang. 2022. One fuzzing strategy to rule them all. In Proceedings of the 44th International Conference on Software Engineering. 1634\u20131645."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 29th USENIX Conference on Security Symposium. 2307\u20132324","author":"Yue Tai","year":"2020","unstructured":"Tai Yue, Pengfei Wang, Yong Tang, Enze Wang, Bo Yu, Kai Lu, and Xu Zhou. 2020. Ecofuzz: Adaptive energy-saving greybox fuzzing as a variant of the adversarial multi-armed bandit. In Proceedings of the 29th USENIX Conference on Security Symposium. 2307\u20132324."},{"key":"e_1_2_1_36_1","volume-title":"27th USENIX Security Symposium (USENIX Security 18)","author":"Yun Insu","year":"2018","unstructured":"Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, and Taesoo Kim. 2018. $QSYM$: A practical concolic execution engine tailored for hybrid fuzzing. In 27th USENIX Security Symposium (USENIX Security 18). 745\u2013761."},{"key":"e_1_2_1_37_1","unstructured":"Michal Zalewski. 2013. american fuzzy lop. https:\/\/lcamtuf.coredump.cx\/afl\/"},{"key":"e_1_2_1_38_1","volume-title":"SHAPFUZZ: Efficient Fuzzing via Shapley-Guided Byte Selection. arXiv preprint arXiv:2308.09239.","author":"Zhang Kunpeng","year":"2023","unstructured":"Kunpeng Zhang, Xiaogang Zhu, Xiao Xi, Minhui Xue, Chao Zhang, and Sheng Wen. 2023. SHAPFUZZ: Efficient Fuzzing via Shapley-Guided Byte Selection. arXiv preprint arXiv:2308.09239."},{"key":"e_1_2_1_39_1","volume-title":"32nd USENIX Security Symposium (USENIX Security 23)","author":"Zheng Han","year":"2023","unstructured":"Han Zheng, Jiayuan Zhang, Yuhang Huang, Zezhong Ren, He Wang, Chunjie Cao, Yuqing Zhang, Flavio Toffalini, and Mathias Payer. 2023. $FISHFUZZ$: Catch Deeper Bugs by Throwing Larger Nets. In 32nd USENIX Security Symposium (USENIX Security 23). 1343\u20131360."}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3715713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T15:16:36Z","timestamp":1750346196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,19]]},"references-count":39,"journal-issue":{"issue":"FSE","published-print":{"date-parts":[[2025,6,19]]}},"alternative-id":["10.1145\/3715713"],"URL":"https:\/\/doi.org\/10.1145\/3715713","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,19]]}}}