高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

模糊测试中的位置自适应变异调度策略

杨智 徐航 桑伟泉 孙浩东 金舒原

杨智, 徐航, 桑伟泉, 孙浩东, 金舒原. 模糊测试中的位置自适应变异调度策略[J]. 电子与信息学报, 2024, 46(9): 3797-3806. doi: 10.11999/JEIT240060
引用本文: 杨智, 徐航, 桑伟泉, 孙浩东, 金舒原. 模糊测试中的位置自适应变异调度策略[J]. 电子与信息学报, 2024, 46(9): 3797-3806. doi: 10.11999/JEIT240060
YANG Zhi, XU Hang, SANG Weiquan, SUN Haodong, JIN Shuyuan. Position-Adaptive Mutation Scheduling Strategy in Fuzzing[J]. Journal of Electronics & Information Technology, 2024, 46(9): 3797-3806. doi: 10.11999/JEIT240060
Citation: YANG Zhi, XU Hang, SANG Weiquan, SUN Haodong, JIN Shuyuan. Position-Adaptive Mutation Scheduling Strategy in Fuzzing[J]. Journal of Electronics & Information Technology, 2024, 46(9): 3797-3806. doi: 10.11999/JEIT240060

模糊测试中的位置自适应变异调度策略

doi: 10.11999/JEIT240060
基金项目: 国家自然科学基金(62176265)
详细信息
    作者简介:

    杨智:男,教授,研究方向为操作系统安全、云计算安全和隐私保护

    徐航:男,硕士生,研究方向为软件安全性分析

    桑伟泉:男,硕士,研究方向为网络安全与人工智能

    孙浩东:男,硕士生,研究方向为软件安全性分析

    金舒原:女,教授,研究方向为漏洞挖掘、网络攻防、人工智能安全和操作系统安全

    通讯作者:

    徐航 1174290091@qq.com

  • 中图分类号: TN915.08; TP393.08

Position-Adaptive Mutation Scheduling Strategy in Fuzzing

Funds: The National Natural Science Foundation of China (62176265)
  • 摘要: 种子自适应变异调度策略是基于变异的模糊测试中最新的技术,该技术能够根据种子的语法和语义特征自适应地调整变异算子的概率分布,然而其存在两个问题:(1)无法根据变异位置自适应地调整概率分布;(2)使用的汤普森采样算法在模糊测试场景中容易导致学习到的概率分布接近平均分布,进而导致变异调度策略失效。针对上述问题,该文提出一种位置自适应变异调度策略,通过一种自定义的双层多臂老虎机模型为变异位置和变异算子建立联系,并且采用置信区间上界算法选择变异算子,实现位置自适应的同时避免了出现平均分布的问题。基于American Fuzzy Lop(AFL)实现了位置自适应的模糊测试器 (PAMSSAFL),实验结果表明位置自适应的变异调度策略能明显提升模糊测试器的bug发现能力和覆盖能力。
  • 图  1  种子自适应变异调度策略流程

    图  2  示例种子

    图  3  双层多臂老虎机示例

    图  4  PAMSSAFL系统流程

    图  5  位置自适应变异调度策略流程

    图  6  触发漏洞的测试用例

    图  7  路径数量对比

    图  8  SeamFuzz测试objdump和who时学习到的概率分布

    表  1  变异算子类型

    类型 释义
    Flip(k) 翻转第k个比特,0翻转为1,1翻转为0
    Overwrite(s, e, v) 将第s个字节至第e个字节的内容复写为v
    Arithmetic(s, e, v) 将第s个字节至第e个字节的内容与
    v进行算术运算
    Delete(s, l) 从第s个字节开始删除长度l的内容
    Insert(s, v) 在第s个字节之后插入v
    下载: 导出CSV

    表  2  示例代码段

     1. function example() {
     2.   number = getNumber();
     3.   if(number == 10) bug1();
     4.   content = getContent();
     5.   length = strlen(content);
     6.   if(length > 8) bug2();
     7. }
    下载: 导出CSV

    表  3  MAGMA测试结果

    模糊测试器libpnglibtifflibxml2luaopenssl总计
    AFL覆盖6681425
    触发241119
    DARWIN覆盖6681425
    触发131117
    PAMSSAFL覆盖6881427
    触发1521110
    SeamFuzz覆盖6681424
    触发131117
    AFL++覆盖6881427
    触发2441112
    PAMSSAFL++覆盖6881427
    触发2541214
    下载: 导出CSV

    表  4  LAVA-M测试结果

    模糊测试器base64md5sumuniqwho总计
    AFL07007
    DARWIN071412
    PAMSSAFL074516
    SeamFuzz07108
    下载: 导出CSV

    表  5  真实应用中的漏洞挖掘情况

    程序版本所在文件漏洞类型AFLDARWINPAMSSAFLSeamFuzz
    binutils2.28libbfd.c缓冲区溢出0 h 55 min1 h 11 min0 h 27 min0 h 48 min
    binutils2.30dwarf1.c整数溢出1 h 36 min1 h 3 min2 h 1 min
    cflow1.6parser.c释放后使用15 h 9 min10 h 33 min6 h 36 min6 h 57 min
    cflow1.6parser.c跨界读取5 h 51 min10 h 22 min
    libexif0.6.14exif-entry.c缓冲区溢出0 h 18 min0 h 10 min0 h 6 min0 h 5 min
    libexif0.6.14exif-data.c跨界读取0 h 21 min0 h 24 min0 h 31 min0 h 27 min
    libtiff4.0.4tif_print.c跨界读取1 h 25 min0 h 18 min0 h 6 min0 h 53 min
    libxml22.9.4valid.c缓冲区溢出6 h 8 min
    tcpdump4.9.0print-sl.c缓冲区溢出0 h 49 min0 h 47 min0 h 4 min0 h 3 min
    tcpdump4.9.2print-bootp.c跨界读取0 h 6 min0 h 7 min0 h 9 min0 h 9 min
    xpdf3.02parser.cc无限递归19 h 46 min3 h 21 min0 h 51 min2 h 39 min
    平均时长10 h 4 min6 h 2 min1 h 59 min4 h 24 min
    下载: 导出CSV

    表  6  漏洞所在代码段

     1. static u_int lastlen[2][256];
     2. static void sliplink_print() {
     3.  int dir = p[SLX_DIR];
     4.  compressed_sl_print(dir);
     5. }
     6. static void compressed_sl_print(int dir) {
     7.  lastlen[dir][lastconn] = length - (hlen << 2);
     8. }
    下载: 导出CSV

    表  7  路径数量和边数量统计

    目标程序版本输入参数AFLDARWINPAMSSAFLSeamFuzz
    路径路径路径路径
    cflow1.7@@15882251144922191644224716402230
    objdump2.41-d @@20206462217464412222659020506467
    tcpdump4.99.4-nr @@460311441470911790519812414486411401
    tiffinfo4.6.0@@29914391287944242959435629984394
    增幅(%)00+0.08+1.34+7.33+4.33+3.12–0.22
    下载: 导出CSV
  • [1] ZALEWSKI M. American Fuzzy Lop (AFL) fuzzer[EB/OL]. https://lcamtuf.coredump.cx/afl/, 2023.
    [2] Honggfuzz: A security oriented, feedback-driven, evolutionary, easy-to-use fuzzer[EB/OL]. https://github.com/google/honggfuzz, 2023.
    [3] LLWM. LibFuzzer—A library for coverage-guided fuzz testing[EB/OL]. http://llvm.org/docs/LibFuzzer.html, 2023.
    [4] LEE M, CHA S, and OH H. Learning seed-adaptive mutation strategies for greybox fuzzing[C]. 2023 IEEE/ACM 45th International Conference on Software Engineering, Melbourne, Australia, 2023: 384–396. doi: 10.1109/ICSE48619.2023.00043.
    [5] AGRAWAL S and GOYAL N. Analysis of thompson sampling for the multi-armed bandit problem[C]. The 25th Annual Conference on Learning Theory, Edinburgh, UK, 2012: 39.
    [6] AUER P, CESA-BIANCHI N, and FISCHER P. Finite-time analysis of the Multiarmed bandit problem[J]. Machine Learning, 2002, 47(2/3): 235–256. doi: 10.1023/A:1013689704352.
    [7] JAUERNIG P, JAKOBOVIC D, PICEK S, et al. DARWIN: Survival of the fittest fuzzing mutators[C]. The 30th Annual Network and Distributed System Security Symposium, San Diego, USA, 2023. doi: 10.14722/ndss.2023.23159.
    [8] LEMIEUX C and SEN K. FairFuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage[C]. The 33rd IEEE/ACM International Conference on Automated Software Engineering, Montpellier, France, 2018: 475–485. doi: 10.1145/3238147.3238176.
    [9] SHE Dongdong, SHAH A, and JANA S. Effective seed scheduling for fuzzing with graph centrality analysis[C]. The 43rd IEEE Symposium on Security and Privacy, San Francisco, USA, 2022: 2194–2211. doi: 10.1109/SP46214.2022.9833761.
    [10] SAHA S, SARKER L, SHAFIUZZAMAN M, et al. Rare path guided fuzzing[C]. The 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis, Seattle, USA, 2023: 1295–1306. doi: 10.1145/3597926.3598136.
    [11] LÜ Chenyang, JI Shouling, ZHANG Chao, et al. MOPT: Optimized mutation scheduling for fuzzers[C]. The 28th USENIX Security Symposium, Santa Clara, USA, 2019: 1949–1966.
    [12] WU Mingyuan, JIANG Ling, XIANG Jiahong, et al. One fuzzing strategy to rule them all[C]. The 44th International Conference on Software Engineering, Pittsburgh, USA, 2022: 1634–1645. doi: 10.1145/3510003.3510174.
    [13] SUTTON R S and BARTO A G. Reinforcement Learning: An Introduction[M]. 2nd ed. Cambridge: The MIT Press, 2018: 31–47.
    [14] 李明磊, 陆余良, 黄晖, 等. 模糊测试变异算子调度优化模型[J]. 小型微型计算机系统, 2021, 42(10): 2190–2195. doi: 10.3969/j.issn.1000-1220.2021.10.029.

    LI Minglei, LU Yuliang, HUANG Hui, et al. Fuzzy tester mutation operator scheduling optimization algorithm[J]. Journal of Chinese Computer Systems, 2021, 42(10): 2190–2195. doi: 10.3969/j.issn.1000-1220.2021.10.029.
    [15] FIORALDI A, MAIER D C, EIßFELDT H, et al. AFL++: Combining incremental steps of fuzzing research[C]. The 14th USENIX Conference on Offensive Technologies, Berkeley, USA, 2020: 10.
    [16] HAZIMEH A, HERRERA A, and PAYER M. Magma: A ground-truth fuzzing benchmark[J]. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2020, 4(3): 49. doi: 10.1145/3428334.
    [17] DOLAN-GAVITT B, HULIN P, KIRDA E, et al. LAVA: Large-scale automated vulnerability addition[C]. 2016 IEEE Symposium on Security and Privacy, San Jose, USA, 2016: 110–121. doi: 10.1109/SP.2016.15.
  • 加载中
图(8) / 表(7)
计量
  • 文章访问数:  50
  • HTML全文浏览量:  24
  • PDF下载量:  2
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-01-26
  • 修回日期:  2024-07-13
  • 网络出版日期:  2024-08-02
  • 刊出日期:  2024-09-26

目录

    /

    返回文章
    返回