基于决策树的选择符号执行和Fuzzing测试方法.pdf

eeSelMeasurement&Detecting Technology测量与检测技术电气自动化2 0 2 3年第45卷第4期基于决策树的选择符号号执行和Fuzzing测试方法加依达尔金格斯，舒斐，李永光”，朱亚运”，李中伟（1.乌鲁木国网新疆电力有限公司电力科学研究院，新疆乌鲁木齐830011;2.国网新疆电力有限公司，新疆乌鲁木齐830011;3.中国电力科学研究院有限公司，北京100192;4.中国科学院沈阳计算技术研究所有限公司，辽宁沈阳110168)摘要：为实现漏洞快速检测，提出了一种基于决策树的选择符号执行和Fuzzing测试方法。在漏洞检测开始之前就判定适合模糊测试（或符号执行）的路径集，从而制导模糊测试（或符号执行）到达适合它们的区域。通过在固定的时间窗口，采集反映模糊测试、符号执行的各项指标，作为生成决策树的输人，以决策树的分类结果，实现对漏洞挖掘中模糊测试、符号测试的自动化调度。同时，还提出路径化简去重算法提升漏洞挖掘的效率。试验结果表明，所提方法相对于单独符号执行或模糊测试，不仅提高了语句和分支覆盖率，还增加了路径数目关键词：Fuzzing测试；符号执行；决策树；路径优化；漏洞检测D0I:10.3969/j.issn.1000-3886.2023.04.031中图分类号TP301文献标志码A文章编号10 0 0-38 8 6（2 0 2 3)0 4-0 0 9 8-0 4ection Symbolic Execution and Fuzzing Test Method Based on Decision TrJaydar Jingus,Shu Fei,Li Yongguang,Zhu Yayun,Li Zhongwei4(1.Electric Power Research Institute,State Grid Xinjiang Electric Power Co.,Ltd.,Urumqi Xinjiang 830011,China;2.State Grid Xinjiang Electric Power Co.,Ltd.,Urumqi Xinjiang 83001l,China;3.China Electric Power Research Institute Co.,Ltd.,Beijing,100192,China;4.Shenyang Institute ofComputing Technology Co.,Ltd.,Chinese Academy of Sciences,Shenyang Liaoning 110168,China)Abstract:In order to achieve rapid vulnerability detection,a decision tree-based selective symbolic execution and Fuzzing test method wasproposed.Before vulnerability detection began,a set of paths suitable for fuzzing(or symbolic execution)were determined,therebyguiding fuzzing(or symbolic execution)to areas suitable for them.By collecting various indicators reflecting fuzz testing and symbolicexecution in a fixed time window,as the input to generate a decision tree,the classification results of the decision tree were used torealize automatic scheduling of fuzz testing and symbolic testing in vulnerability mining.At the same time,a path simplification anddeduplication algorithm were also proposed to improve the efficiency of vulnerability mining.Experimental results show that theproposed method not only improves statement and branch coverage,but also increases the number of paths compared to singlesymbolic execution or fuzzing.Keywords:Fuzzing test;symbolic execution;decision tree;path optimization;vulnerability detection0引言目前，各种各样的安全事件层出不穷，频发的网络安全事件使得人们认识到网络安全漏洞检测的重要性。程序漏洞检测的主要技术手段为模糊测试技术和选择符号执行。近些年来，前人在模糊测试和符号执行结合的基础上，提出了很多方法。Ste-phens等结合Fuzzing工具AFL和符号执行工具Angr来实现漏洞检测，当模糊测试无法继续探索时，启用二进制混合测试模块。该模块可以约束求解生成，突破这些限制的新输入，并将输入返回给模糊测试作为种子，使得模糊测试可以快速突破条件判断语句继续执行。Zhao等2 提出应用蒙托卡罗概率模型对模糊测试中执行到的路径进行优先级计算，将困难路径交给混合执行来求解。Cha等3 利用符号执行，分析模糊测试的两个输人种子的符号执行轨迹，得到输人位之间的依赖关系，并基于该依赖关系，计算种子的最佳突变率，最后将新生成的种子输人模糊测试继续检定稿日期：2 0 2 2-0 4-0 298ElectricalAutomation测。文献4 提出结合混合符号执行的导向式灰盒模糊测试方法。通过跟踪种子的执行路径，使用约束求解器对种子的遗传变异加以辅助，生成能够通过检查语句的测试用例，从而对目标区域进行测试。文献5 通过导向式模糊测试技术对程序路径进行过滤，利用选择符号执行技术对可能触发漏洞的路径进行求解。综上所述，针对符号执行和模糊测试技术，许多研究者提出了多种两者相结合的优化方法。但是，由于两者的优劣各有不同，上述方法只能在模糊测试（或符号执行）运行时判定是否应该借助符号执行（或模糊测试），无法同时利用两者的优势，导致漏洞检测受限。因此，本文提出一种基于决策树的选择符号执行和Fuzzing测试方法，该方法根据在固定的时间窗口，采集反映得到的模糊测试、符号执行的各项指标，作为生成决策树的输入，以决策树的分类结果，实现对漏洞挖掘中模糊测试和符号测试的自动化调度。同时，还提出路径化简去重算法提升漏洞检测的效率。ElectricalAutomation99Measurement&Detecting Technology测量与检测技术电气自动化2 0 2 3年第45卷第4期1基本概念1.1模糊概述模糊测试是一种非常有效软件安全漏洞挖掘技术，目前已经被广泛地应用在软件安全漏洞的检测上。该技术于2 0 世纪9 0 年代提出并应用在测试Unix程序稳定性上，其主要思想是：将自动化生成的测试用例不断输人到目标程序中，监视程序的异常执行状态；发现程序中的崩溃之后，保存测试用例用以后续分析，以判定该崩溃是否能够重现和利用。模糊测试流程应用广泛，测试对象种类繁多，但是模糊的整个测试流程是一致的，流程如图1所示。1.2符号执行技术符号执行技术使用符号变元代替程序的具体输入，并监控程序控制流并记录程序执行轨迹。其在程序中的每一个分支节点，收集符号变元的路径约束，每执行完一条路径，系统恢复到上一个分支节点并开始探索新的路径。该技术利用全路径分析的方式定位程序漏洞位置，求解程序人口到程序漏洞的路径约束来得到触发漏洞的测试用例。2 0 0 9年选择符号执行技术应运而生，一定程度上解决了路径状态空间爆炸的问题。选择符号执行技术的主要思想是将具体执行与符号执行相结合，对程序核心函数进行符号执行，而对核心函数或系统函数调用不进行具体执行。这不仅有效降低了系统运行开支，还降低了约束求解器的求解难度。2路径化简去重算法由于漏洞点所在基本块的可达路径可能有多条，每条代码路径触发漏洞的难易程度不一样，如果对所有的代码路径随机选择并进行漏洞挖掘，则可能需要经过很长时间才能挖掘到漏洞，同时，对于二进制程序而言，同一个漏洞点的多条可达路径的漏洞成因类似，在修复了漏洞点处的漏洞后，其他路径的漏洞也会同时消除。因此，需要对疑似漏洞的代码路径进行优先度排序，优先挖掘容易触发漏洞、危害更大、漏洞存在概率更大的路径，更快地发现漏洞。本文提出一种路径化简去重算法，结合基本块的复杂度计算、代码片段复杂度计算、代码路径的复杂度计算、漏洞风险及漏洞概率因素的影响等要素，对所有疑似漏洞点的代码路径进行优先度排序，将优先度越高的代码路径越早进行挖掘。具体的生成步骤如下：步骤一：对待挖掘漏洞的二进制程序通过IDA软件进行逆向编译成可读形式，划分出基本块和片段。步骤二：通过指令数量和指令类型计算基本块的复杂度，即每个基本块的复杂度由其指令数量和指令类型来衡量，包含的指开始确定测试对象确定输入向量生成测试数据执行测试数据目标程序异常？是工保存输入数据与异常信息数据分析图1模糊测试流程权重值与指令的时间复杂度的对应关系如表1所示表1中：的值等于1+指令类型数量-1，编号1 7 是对应的7 种时间复杂度，涵盖了代码中可能出现的时间复杂度情况。步骤三：根据片段中各基本块的复杂度以及基本块的数量，按照层级加权求和计算片段的复杂度，并设计每种代码令数量越多、内存读写指令越多，则基本块的复杂度越高。通过这两项指标，计算出每个基本块的复杂度。基本块的复杂度的计算公式为：En.Roca)+ZNC(1)num式中：C,为基本块的复杂度；n为对应指令类型的指令数量；Ro(n)为该指令类型的指令的权重值；为影响系数，取值为0.010.1之间；N%为基本块中涉及到的每一次栈操作时，栈顶到栈底的距离；num为基本块中总的指令数量。指令类型的指令的权重值Ro(n)参考指令的时间复杂度o(n)获得。所述指令的表1指令权重值与时间复杂度的对应表序号时间复杂度指令权重10(1)120(n)a30(n)24o(log n)1og a5o(nlog n)alog(a)60(n)70(2)2片段类型的复杂度计算方法。片段的复杂度计算公式为：C,=0,(Cb+Ch2+.)+02(Ci+C2+.)+0.(Ci+Ci2+.)(2)式中：0 为对应的片段中处于不同层级的基本块的权重；Ch为不同层级中第一个基本块的复杂度；Ch2为不同层级中第二个基本块的复杂度步骤四：通过路径经过的片段的复杂度和基本块的复杂度来计算路径的复杂度，对于路径上的条件分支类型的代码片段，给予更大的权重，一条路径经过的数据完整性验证点越多，越难构造出相应的输人来抵达漏洞点，即这条路径的复杂度越高。路径的复杂度的计算公式为：C,=V(G)(Cn+C,+.)(3)V(G)=e-n+2(4)式中：V(G)为一条路径的圈复杂度；C,为路径中涉及到的所有片段的复杂度；e为一条路径中边的数量；n为控制流图中的节点数量。步骤五：根据步骤四计算的路径复杂度，结合漏洞存在因素计算路径的优先度，所述漏洞存在因素包括不同漏洞类型的漏洞对应代码出现频率和对应代码复杂度。疑似漏洞点所在路径的优先度的计算公式为：S=xZ PvC.:+P（5）Zc.式中：P为对应代码出现频率；P。为对应代码复杂度；C，为一条路径的复杂度;为系数，+=1。步骤六：对所有疑似漏洞点所在路径的优先度进行排序100ElectricalAutomationMeasurement&DetectingTechnology测量与检测技术电气自动化2 0 2 3年第45卷第4期3基于决策树的自动调度方法模糊测试和选择性符号执行是漏洞检测的两个核心技术。通过决策树预测路径是适合符号执行还是适合模糊测试，对于适合符号执行的路径集，则引导符号执行优先执行该路径集；对于适合模糊测试的路径集，则引导模糊测试优先执行该路径集。通过二者的有机结合，对当前的状态进行更为深入的路径搜索以提高代码覆盖率，最终提高程序测试的效率。3.1决策树分类法决策树是对数据进行分类的一种常用方法，它采用自顶向下的递归方式：首先从根节点开始在每个节点上按照给定的度量方式选择属性；然后根据相应属性的可能取值向下建立分支，直到训练集没有剩余属性进一步划分样本为止。从根节点到叶节点的一条路径对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。本文应用C4.5算法自动化对模糊测试、符号执行进行自动化调度，C4.5算法使用信息增益来选择属性分裂，在构造树的过程中进行剪枝操作优化，流程如图2 所示。开始创建节点是训练集为空？返回节点N否是样本都属于类别A?返回节点N，为叶节点并标记为类A工是属性为连续性？离散化属性计算信息增益率选择最大增益率属性标记N用后剪枝方法进行剪枝结束图2决策树分类执行流程图首先创建节点N，按信息的计算公式为：H(X)=-Zp(x)logap(x)(6)XEX得出样本中的类别信息熵Info（C），然后对于每一属性，将属性作为条件，按照如下公式计算：H(Y|X)=Zp(x)H(Y|X=x)=EXp(x)Zp(y/x)log p(yl)=XEXYEYZZp(x,y)log p(y/x)-Elog p(Y|x)(7)计算该条件下的条件嫡，得到各属性的熵值为Info（A,），.,Info(A,)。C4.5算法采用信息增益率作为依据选择属性，对样本集进行划分。计算信息增益率，同时要计算得到每一种属性的内部信息，同样按照信息嫡的计算方法得到H（A,），,H（A,）。即计算每一种属性的信息增益率，并取最大值属性作为划分属性，标记节点N。如果属性A的取值为连续型，还要对齐进行离散化处理，最后应用PEP剪枝算法对决策树进行剪枝优化。3.2决策树的生成优化依据本文提出的路径化简去重算法，人工调用模糊测试和符号执行进行漏洞检测。在进行模糊测试和符号测试的过程中，对测试状态和二进制程序状态进行监控。在固定的时间窗口采集相关数据，获得描述模糊测试、符号执行漏洞检测效率和系统开销的各项指标，作为生成决策树的输入。根据调度结果对每条测试数据设置类别标签，生成决策树调度的训练样本，设定决策数的属性集合A=（代码覆盖率，危险代码块可达率，新增代码块数量，新增危险指令数量，测试用例迭代变化率，系统开销，测试时间，其类别标签L=1符号执行开始，符号执行结束，漏洞挖掘终止1，再应用C4.5算法，生成模糊测试、符号测试的自动化调度决策树，以决策树的分类结果，实现对模糊测试和符号测试的自动化调度。根据调度结果与路径化简去重算法的符合程度，调整对系统的指标数据采集。和原始决策树生成时的属性集合，动态对决策树的结构进行调整。实现实际调度结果对决策树生成的反馈，以改善决策树动态调度过程，提升漏洞检测的效率。4试验分析本文选用LAVA-M数据集为测试对象。通过使用LAVA技术在uniq、w h o、m d 5s u m 和base64四个程序上进行bug插人而形成LAVA-M测试集。本次使用LAVA-M测试集中的base64,将单模糊测试、单符号执行和基于决策树的混合模糊测试方法分别进行测试，对比三者完成情况，具体试验结果见表2。表2三种方法的测试结果基于决策树的项目单模糊测试单符号执行混合模糊测试方法语句覆盖率/（%）41.240.141.2分支覆盖率/（%）35.730.436.8路径数目/个32309358由上述试验结果可知，相比单独模糊测试和符号执行技术，本文提出的方法可以实现对漏洞函数的快速覆盖，路径数目增多且检测出了更多缺陷5结束语本文对模糊测试技术与符号执行技术进行研究，评估现有检测方法的优势与不足，提出了一种基于决策树的选择符号执行和Fuzzing测试方法。该方法依据路径简化去重算法，人工调用模糊测试、符号测试进行漏洞检测，在固定的时间窗口，采集反映模糊测试、符号执行的各项指标作为生成决策树的输入，以决策树的分类结果，实现对漏洞挖掘中模糊测试、符号测试的自动化调度。通过对LAVA-M程序集中的base64程序进行测试，试验结果表明，本文提出的方法不仅能够提升对代码的覆盖率，且漏洞检测时间也得到提升。(下转第10 4页）104ElectricalAutomation上接第10 0 页）Intelligent Control Technology电气自动化2 0 2 3年第45卷第4期智能控制技术观操作失误等。其被理解为推理方式，由结果推出原因。建立系统的故障树是防止事件发生和产生预防方案。4保护设备在线状态评估系统设计系统采用分布式部署及应用模式，涵盖10 大应用场景，分别为：变电站、地市级集控中心、地市级调度端、地市级检修机构、省级集控中心、省级调度端、省级检修机构、总部技术支持机构、总部调度分支机构和总部调度端。调度端的应用主要面向调度人员和保护专责，集控中心端的应用主要面向运维人员，检修机构的应用主要面向检修人员，总部技术支持机构的应用主要面向科研人员和技术服务人员。图10 为系统的应用模式及应用场景演示图。总部技术支总部级总部分支机构撑机构7省部级分支机构省部级省部级生产机构智能变电站智能变电站智能变电站服务器保护装置服务器保护装置服务器保护装置?5地市级分支机构地市级地市级生产机构智能变电站智能变电站服务器保护装置服务器保护装置图10系统的应用模式及应用场景为实现系统在10 大应用场景中的应用，设计系统管理类，图形及模型管理类，数据信息管理及传输类，业务功能类，以及算法类模块共五大类功能模块。五大类功能模块相互配合完成系统的整体功能如表4所示5结束语从技术感知势态分析到结合智能变电站的在线状态运行评估方法，本文完成了对模型的分析以及完整的一套运行信息应用参考文献：1 STEPHENS N,CROSEN J,SALLS C,et al.Diller:augmentingfuzzing through selective symbolic execution C/Network andDistributed System Security Symposium,San Diego,USA:2016.2 ZHAO L,DUAN Y,YIN H,et al.Send hardest problems my way:probabilistic path prioritization for hybrid fuzzing C/Network andDistributed System Security Symposium,San Diego,USA:2019.3 CHA SK,WOO M,BRUMLEY D.Program-adaptive mutational表4系统功能模块划分模块种类功能模块名称系统管理类用户及角色管理模块、系统功能配置管理、参数管理图形及模型SCD文件解析模块、保护模型、运行数据匹配管理模管理类块、物理连接图和虚端子连接图管理模块数据采集模块、故障信息管理模块、运行信息管理模数据信息管块、历史运行信息管理、信息调阅及数据传输模块、Web理及传输类发布模块及与外系统接口在线监视模块、动作分析模块、故障诊断模块、状态评业务功能类估模块、检修管理模块、安措管理模块、定值管理模块、报表及报告管理模块算法训练编辑模块、算法接口调用模块和算法执行算法类模块状态数据。综合利用保护设备的在线数据、离线数据和保护设备信息模型，结合态势感知技术完成了对保护设备的综合评估和态势预测。本文研究了保护设备的状态评价内容及状态评价量，并提出了保护设备运行评价的具体指标体系，同时介绍了在线运行状态评估方法及内容和系统的场景应用参考文献：1唐葆生伦敦南部地区大停电及其教训J电网技术，2 0 0 3，2 7(11):1 5;12.2 叶远波，陈晓东，项忠华，等继电保护在线状态检修的应用和探讨J.电力系统保护与控制，2 0 17，45（2 2）：132-138.【3熊小伏，陈星田，郑昌圣，等.继电保护系统状态评价研究综述J.电力系统保护与控制，2 0 14，42（5）：51-58.【4刘琨，黄明辉，李一泉，等智能变电站继电保护在线运检方法研究J电力系统保护与控制，2 0 2 0，48（7）：58-6 5.【5刘，李川基于多层次架构的继电保护在线状态评价方法J.电力系统保护与控制，2 0 17，45（8）：113-12 0.【6】王俊芳面向状态检修的继电保护系统可靠性评估D北京：北京交通大学，2 0 18.【7 杨亮智能变电站二次系统的集成设计优化D陕西：西安理工大学，2 0 2 0.【作者简介】周杰（1990 一），男，新疆吐鲁番人，大学本科，中级工程师，专业方向为电力系统继电保护与控制。张良武（198 6 一），男，黑龙江人，大学本科，中级工程师，专业方向为电力系统及自动化。谭金龙（198 9一），男，新疆昌吉人，大学本科，中级工程师，专业方向为电力系统继电保护与控制。张烈（198 4一），女，北京人，硕士研究生，高级工程师，专业方向为电力系统继电保护与控制。杨利民（198 5一），男，湖北孝感人，大学本科，高级工程师，专业方向为电力系统及自动化。fuzzing C/IEEE Symposium on Security&Privacy.San Jose,USA:2015:725-741.【4戴渭，陆余良，朱凯龙。结合混合符号执行的导向式灰盒模糊测试技术J.计算机工程，2 0 2 0，46（8）：190-196.【5李明磊，黄晖，陆余良，等.SymFuzz：一种复杂路径条件下的漏洞检测技术J计算机科学，2 0 2 1，48（5）：2 5-31.【作者简介】加依达尔金格斯（1993一），女，哈萨克族，新疆人，大学本科、工程师，主要研究方向：电力系统自动化和网络安全。