Kunpeng Zhang (Shenzhen International Graduate School, Tsinghua University), Xiaogang Zhu (Swinburne University of Technology), Xi Xiao (Shenzhen International Graduate School, Tsinghua University), Minhui Xue (CSIRO's Data61), Chao Zhang (Tsinghua University), Sheng Wen (Swinburne University of Technology)

Mutation-based fuzzing is popular and effective in discovering unseen code and exposing bugs. However, only a few studies have concentrated on quantifying the importance of input bytes, which refers to the degree to which a byte contributes to the discovery of new code. They often focus on obtaining the relationship between input bytes and path constraints, ignoring the fact that not all constraint-related bytes can discover new code. In this paper, we conduct Shapely analysis to understand the effect of byte positions on fuzzing performance, and find that some byte positions contribute more than others and this property often holds across seeds. Based on this observation, we propose a novel fuzzing solution, ShapFuzz, to guide byte selection and mutation. Specifically, ShapFuzz updates Shapley values (importance) of bytes when each input is tested during fuzzing with a low overhead, and utilizes contextual multi-armed bandit to trade off between mutating high Shapley value bytes and low-frequently chosen bytes. We implement a prototype of this solution based on AFL++, i.e., ShapFuzz. We evaluate ShapFuzz against ten state-of-the-art fuzzers, including five byte schedule-reinforced fuzzers and five commonly used fuzzers. Compared with byte schedule-reinforced fuzzers, ShapFuzz discovers more edges and exposes more bugs than the best baseline on three different sets of initial seeds. Compared with commonly used fuzzers, ShapFuzz exposes 20 more bugs than the best comparison fuzzer, and discovers 6 more CVEs than the best baseline on MAGMA. Furthermore, ShapFuzz discovers 11 new bugs on the latest versions of programs, and 3 of them are confirmed by vendors.

View More Papers

Merge/Space: A Security Testbed for Satellite Systems

M. Patrick Collins (USC Information Sciences Institute), Alefiya Hussain (USC Information Sciences Institute), J.P. Walters (USC Information Sciences Institute), Calvin Ardi (USC Information Sciences Institute), Chris Tran (USC Information Sciences Institute), Stephen Schwab (USC Information Sciences Institute)

Read More

Don't Interrupt Me – A Large-Scale Study of On-Device...

Marian Harbach (Google), Igor Bilogrevic (Google), Enrico Bacis (Google), Serena Chen (Google), Ravjit Uppal (Google), Andy Paicu (Google), Elias Klim (Google), Meggyn Watkins (Google), Balazs Engedy (Google)

Read More

Leaking the Privacy of Groups and More: Understanding Privacy...

Jiangrong Wu (Sun Yat-sen University), Yuhong Nan (Sun Yat-sen University), Luyi Xing (Indiana University Bloomington), Jiatao Cheng (Sun Yat-sen University), Zimin Lin (Alibaba Group), Zibin Zheng (Sun Yat-sen University), Min Yang (Fudan University)

Read More

Towards Precise Reporting of Cryptographic Misuses

Yikang Chen (The Chinese University of Hong Kong), Yibo Liu (Arizona State University), Ka Lok Wu (The Chinese University of Hong Kong), Duc V Le (Visa Research), Sze Yiu Chau (The Chinese University of Hong Kong)

Read More