一种基于部分解caching与重用的符号执行优化方法
技术领域
1.本发明涉及软件自动测试中符号执行技术领域，尤其涉及一种基于部分解caching与重用的符号执行优化方法。
背景技术：2.软件测试通过尽可能多地构造测试用例来发现软件中的漏洞，是现代软件开发过程中不可或缺的一环。目前，大多数软件的规模相当庞大，仅靠人来手动构造测试用例几乎是不可能的，因此，如何自动地生成测试用例是软件测试中很重要的一个问题。符号执行就是可以自动生成测试用例的一种技术手段。符号执行通过将输入符号化，在执行程序的同时收集路径条件，当一条路径被探索完时，收集到的路径条件将会交由约束求解器进行求解，若路径条件是可满足的，则约束求解的结果即为测试用例。符号执行通过不断地探索程序路径并求解路径约束，最终可以生成大量有效的测试用例。
3.在生成测试用例的符号执行过程中，由于真实程序中往往有大量的路径，因此在符号执行的过程中，需要频繁地调用约束求解器。约束求解过程中，约束求解器会不断地对约束中的变量进行赋值并验证，通常情况下，求解一个约束需要多次赋值和验证，求解过程中未能通过验证的赋值被称为部分解。约束求解本质上是对输入空间进行搜索，是一个非常耗时的过程，符号执行的效率严重依赖于约束求解的效率，因而符号执行中约束求解的效率会直接影响测试用例生成的效率。
4.目前有多种手段可以提高符号执行的效率，如约束简化、解的caching与重用等等。caching机制能够减少对求解器的调用，是一种有效且应用较多的优化手段。caching的基本流程为：将约束进行标准化，将约束及约束求解结果存储起来，以便以后在遇到相同或者相似的约束时能够重用。通常情况下，标准化的约束和约束求解结果会作为键值对存入cache中。上述caching机制中一个约束只能存储一个解，但是实际上，一个约束可能有多个解，因此，在传统的caching机制中，解无法有效地存储和利用，造成cache命中率偏低。因此，提升cache的命中率是提高符号执行效率的一个重要手段。
5.有从业者提出在caching机制下对特定形式的公式(或程序)提高cache的命中率，该类方法通常是针对有符号化地址的公式，将结构相似的公式进行合并，从而使得该类公式在进行cache查询时更容易命中。但是该类方案仅能够提高有符号化地址的公式或者程序的cache命中率，通用性差，导致软件自动测试过程中整体的符号执行效率仍然不高。因此，如何能够通用性的提升各类型程序在软件自动测试的符号执行过程中cache的命中率，从而提高测试用例生成时符号执行的效率仍然是一个亟待解决的问题。
技术实现要素：6.本发明要解决的技术问题就在于：针对符号执行效率低的问题，能够通用地、有效地提升cache命中率，从而提高测试用例生成过程中符号执行的效率，本发明提供一种基于部分解caching与重用的符号执行优化方法。
7.为解决上述技术问题，本发明提出的技术方案为：
8.一种基于部分解caching与重用的符号执行优化方法，包括步骤：
9.步骤s1.使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中的路径约束；
10.步骤s2.判断收集的路径约束是否能够命中当前cache，如果命中则返回执行步骤s1，如果未命中则转入执行步骤s3；
11.步骤s3.由约束求解器对未命中的所述路径约束进行求解，记录求解得到的部分解及最终解；
12.步骤s4.将所述路径约束与记录的所述最终解存入cache，并根据所述部分解与所述路径约束的原子约束之间的匹配关系，将所述部分解与约束对应存入当前cache以更新当前cache，使得在符号执行过程中遇到相同或者相似的约束时重用对应的所述部分解，返回执行步骤s1。
13.进一步的，所述步骤s2中判断是否能够命中cache的方法为：
14.如果cache中存在一个第一键值对[c,r]，则判定cache命中，其中c为当前需要求解的约束，r为cache中对应c的解；
[0015]
或者如果cache中存在一个第二键值对[c1,r]，其中c1是当前需要求解的约束c的子集，r为cache中对应c1的解，当r满足c时，则判定cache命中；
[0016]
或者如果cache中存在一个第三键值对[c2,r]，其中c2是当前需要求解的约束c的超集，r为cache中对应c2的解，则判定cache命中。
[0017]
进一步的，步骤s3中使用smt求解器对未命中的所述路径约束进行求解。
[0018]
进一步的，所述步骤s3中，由约束求解器对未命中的所述路径约束进行求解时，通过多次进行赋值以及验证判断当前赋值是部分解还是最终解，如果当前赋值通过验证则判断当前赋值为最终解，否则判断当前赋值为部分解。
[0019]
进一步的，所述步骤s4中的具体步骤为：对于每一个所述路径约的原子约束以及每一个部分解，判断部分解是否满足所述原子约束，根据是否满足的判断结果将部分解与对应的约束存入cache。
[0020]
进一步的，所述根据是否满足的判断结果将部分解与对应的约束存入cache包括：如部分解满足所述原子约束，则将所述部分解与原子约束对应存入cache，如部分解不满足所述原子约束，则对原子约束的条件取反后生成新的约束，并将新的约束与部分解对应存入cache。
[0021]
一种基于部分解caching与重用的符号执行优化装置，包括：
[0022]
约束收集模块，用于使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中的路径约束；
[0023]
命中判断模块，用于判断收集的路径约束是否能够命中当前cache，如果命中则返回执行约束收集模块，如果未命中则转入执行约束求解模块；
[0024]
约束求解模块，用于由约束求解器对未命中的所述路径约束进行求解，记录求解得到的部分解及最终解；
[0025]
cache更新模块，用于将所述路径约束与记录的所述最终解存入cache，并根据所述部分解与所述路径约束的原子约束之间的匹配关系，将所述部分解与约束对应存入当前
cache以更新当前cache，使得在符号执行过程中遇到相同或者相似的约束时重用对应的所述部分解，返回执行约束收集模块。
[0026]
一种基于部分解caching与重用的符号执行优化装置，包括处理器以及存储器，所述存储器用于存储计算机程序，所述处理器用于执行所述计算机程序，所述处理器用于执行所述计算机程序以执行上述方法。
[0027]
一种计算机可读存储介质，该计算机可读存储介质中存储有用于被计算机设备执行以实施上述方法的计算机程序。
[0028]
与现有技术发明相比，本发明的优点在于：
[0029]
1、本发明针对软件自动测试过程中使用符号执行对被测程序进行分析，以生成测试用例时，通过收集符号执行过程中路径约束，对各约束进行cache是否命中判断，如果未命中则使用约束求解器进行求解，记录最终解的同时，一并将部分解与对应约束记录下来存入cache中，使得利用符号执行的搜索结果对cache进行快速、准确的持续更新与扩充，在后续符号执行过程中，当遇到相同或者相似的约束时可以重复使用先前存入cache的部分解，即实现部分解的重用，从而能够充分利用部分解来不断扩充cache，有效提升cache命中率，进而提高测试用例生成过程中符号执行的效率。
[0030]
2、本发明可以适用于各类程序的自动测试，不针对某种特定形式的公式或程序，也不受限于某种特定的搜索策略，可以通用地提升各类程序测试用例生成过程中符号执行的cache命中率，从而提高软件测试时整体的符号执行效率。
附图说明
[0031]
图1是本实施例基于部分解caching与重用的符号执行优化方法的实现流程示意图。
[0032]
图2是在具体应用实施例中判断约束能否cache命中的效果示意图。
[0033]
图3是在具体应用实施例中记录部分解及最终解的效果示意图。
[0034]
图4是在具体应用实施例中根据部分解及最终解更新cache的效果示意图。
[0035]
图5是在具体应用实施例中部分解被重用的效果示意图。
具体实施方式
[0036]
以下结合说明书附图和具体优选的实施例对本发明作进一步描述，但并不因此而限制本发明的保护范围。
[0037]
如图1所示，本实施例提供基于部分解caching与重用的符号执行优化方法，包括步骤：
[0038]
步骤s1.使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中的路径约束；
[0039]
步骤s2.判断收集的路径约束是否能够命中当前cache，如果命中则返回执行步骤s1，如果未命中则转入执行步骤s3；
[0040]
步骤s3.由约束求解器对未命中的路径约束进行求解，记录求解得到的部分解及最终解，转入步骤s4；
[0041]
步骤s4.将路径约束与记录的最终解存入cache，并根据部分解与所述路径约束的
原子约束之间的匹配关系，将部分解与约束对应存入当前cache以更新当前cache，使得在符号执行过程中遇到相同或者相似的约束时重用对应的部分解，返回执行步骤s1。
[0042]
本实施例针对软件自动测试过程中使用符号执行对被测程序进行分析，以生成测试用例时，通过收集符号执行过程中路径约束，对各约束进行cache是否命中判断，如果未命中则使用约束求解器进行求解，记录最终解的同时，一并将部分解与对应约束记录下来存入cache中，使得利用符号执行的搜索结果对cache进行快速、准确的持续更新与扩充，在后续符号执行过程中，当遇到相同或者相似的约束时可以重复使用先前存入cache的部分解，即实现部分解的重用，从而能够充分利用部分解来不断扩充cache，有效提升cache命中率，进而提高测试用例生成过程中整体的符号执行效率。
[0043]
本实施例上述方法可以适用于各类程序的自动测试，不针对某种特定形式的公式或程序，也不受限于某种特定的搜索策略，可以通用地提升各类程序测试用例生成过程中符号执行的cache命中率，从而提高软件测试时符号执行效率。
[0044]
假设当前需要求解的约束为c，本实施例步骤s2中判断是否能够命中cache可以采用以下三种机制：
[0045]
机制1：如果cache中存在一个键值对[c,r]，则cache命中，其中c为当前需要求解的约束，r为cache中对应c的解；
[0046]
机制2：如果cache中存在一个键值对[c1,r]，其中c1是当前需要求解的约束c的子集，r为cache中对应c1的解，当r满足c时，则cache命中；
[0047]
机制3：如果cache中存在一个键值对[c2,r]，其中c2是当前需要求解的约束c的超集，r为cache中对应c2的解，则cache命中。
[0048]
上述三种机制可以根据实际需求选取其中任意一种，也可以为各机制设置选择条件，在满足预设条件时使用对应的机制。
[0049]
本实施例步骤s3中，由约束求解器对未命中的路径约束进行求解时，通过多次进行赋值以及验证判断当前赋值是部分解还是最终解，如果当前赋值通过验证则判断当前赋值为最终解，否则判断当前赋值为部分解。每次赋值验证时，具体由约束求解器提取路径约束中的所有变量，通过预设策略对每一个变量进行赋值，如果当前所有变量的赋值能够满足路径条件，则判断当前赋值为最终解，否则，判断当前赋值为部分解并对变量重新进行赋值。
[0050]
本实施例中，步骤s3中具体使用smt求解器对未命中的路径约束进行求解，即约束求解器为smt求解器。
[0051]
本实施例中，步骤s4的具体步骤为：对于每一个原子约束以及每一个部分解，判断部分解是否满足原子约束，根据是否满足的判断结果将部分解与对应的约束存入cache以对cache进行扩充。具体如部分解满足原子约束，则将部分解与原子约束对应存入cache，如不满足，则表明部分解一定满足原子约束的非，因此对原子约束的条件取反后生成新的约束，并将新的约束与部分解对应存入cache。即如果部分解满足原子约束，则直接将部分解与该原子约束一起对应存入cache，如果部分解不满足原子约束，则将原子约束取反后再与部分解对应一起存入cache。例如，对于路径约束c1的每一个原子约束ci以及c1的每一个部分解si，判断si是否满足ci，如果si满足ci，将{ci，si}存入cache，否则，将存入cache。
[0052]
以如图2所示的程序分析为示例对本发明上述方法进行进一步说明，其中x和y都为8位的有符号整数，cache中已有约束c(x+y》10)以及解r({x:10,y:0})。本实施例程序分析示例的基于部分解caching与重用的符号执行优化方法的过程如下：
[0053]
步骤s1.使用符号执行对程序进行分析后，当前需要求解的约束为c1，c为c1的子集，但r不满足c1，所以cache未命中；
[0054]
步骤s2.如图3所示，将路径约束c1交由约束求解器进行求解，当赋值为{x:0,y:0}以及{x:58,y:81}时，都验证失败，则这两次赋值被记录为部分解，通过验证的赋值{x:26,y:17}则被记录为最终解；
[0055]
步骤s3.如图4所示，首先，将路径约束c1与最终解r存入cache，然后，对于路径约束c1的每一个原子约束ci以及c1的每一个部分解si，判断si是否满足ci，如果si满足ci，将{ci，si}存入cache，否则，将存入cache，在后续符号执行过程中即可重用cache中已存入的部分解以提高cache命中率。
[0056]
例如，当本实施例程序分析示例后续需要求解如图5所示约束c2时，利用cache中预先存入的部分解，c2能够cache命中，从而提高cache命中率，减少调用求解器的次数。
[0057]
本实施例通过上述方法，能够快速、准确地扩充cache，从而有效地利用部分解，提升cache命中率，进而提高测试用例生成过程中符号执行的效率，从而有效提高测试用例的生成效率，并且本实施例不针对某种特定形式的公式或程序，也不受限于某种特定的搜索策略，可以通用地适用于各类程序实现cache命中率提升，从而有效提高软件自动测试中整体符号执行效率。
[0058]
本实施例基于部分解caching与重用的符号执行优化装置，包括：
[0059]
约束收集模块，用于使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中的路径约束；
[0060]
命中判断模块，用于判断收集的路径约束是否能够命中当前cache，如果命中则返回执行约束收集模块，如果未命中则转入执行约束求解模块；
[0061]
约束求解模块，用于由约束求解器对未命中的所述路径约束进行求解，记录求解得到的部分解及最终解；
[0062]
cache更新模块，用于将路径约束与记录的所述最终解存入cache，并根据部分解与路径约束的原子约束之间的匹配关系，将所述部分解与约束对应存入当前cache以更新当前cache，使得在符号执行过程中遇到相同或者相似的约束时重用对应的所述部分解，返回执行约束收集模块。
[0063]
本实施例基于部分解caching与重用的符号执行优化装置还可以由如下两部分构成：处理器以及存储器，存储器用于存储计算机程序，处理器用于执行计算机程序以执行上述方法。
[0064]
本实施例还提供计算机可读存储介质，该计算机可读存储介质中存储有用于被计算机设备执行以实施上述方法的计算机程序。
[0065]
上述只是本发明的较佳实施例，并非对本发明作任何形式上的限制。虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明。因此，凡是未脱离本发明技术方案的内容，依据本发明技术实质对以上实施例所做的任何简单修改、等同变化及修饰，均应落在本发明技术方案保护的范围内。
技术特征：1.一种基于部分解caching与重用的符号执行优化方法，其特征在于，包括步骤：步骤s1.使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中的路径约束；步骤s2.判断收集的路径约束是否能够命中当前cache，如果命中则返回执行步骤s1，如果未命中则转入执行步骤s3；步骤s3.由约束求解器对未命中的所述路径约束进行求解，记录求解得到的部分解及最终解；步骤s4.将所述路径约束与记录的所述最终解存入cache，并根据所述部分解与所述路径约束的原子约束之间的匹配关系，将所述部分解与约束对应存入当前cache以更新当前cache，使得在符号执行过程中遇到相同或者相似的约束时重用对应的所述部分解，返回执行步骤s1。2.根据权利要求1所述的基于部分解caching与重用的符号执行优化方法，其特征在于，所述步骤s2中判断是否能够命中cache的方法为：如果cache中存在一个第一键值对[c,r]，则判定cache命中，其中c为当前需要求解的约束，r为cache中对应c的解；或者如果cache中存在一个第二键值对[c1,r]，其中c1是当前需要求解的约束c的子集，r为cache中对应c1的解，当r满足c时，则判定cache命中；或者如果cache中存在一个第三键值对[c2,r]，其中c2是当前需要求解的约束c的超集，r为cache中对应c2的解，则判定cache命中。3.根据权利要求1所述的基于部分解caching与重用的符号执行优化方法，其特征在于，步骤s3中使用smt求解器对未命中的所述路径约束进行求解。4.根据权利要求1所述的基于部分解caching与重用的符号执行优化方法，其特征在于，所述步骤s3中，由约束求解器对未命中的所述路径约束进行求解时，通过多次进行赋值以及验证判断当前赋值是部分解还是最终解，如果当前赋值通过验证则判断当前赋值为最终解，否则判断当前赋值为部分解。5.根据权利要求1～4中任意一项所述的基于部分解caching与重用的符号执行优化方法，其特征在于，所述步骤s4中的具体步骤为：对于每一个所述路径约的原子约束以及每一个部分解，判断部分解是否满足所述原子约束，根据是否满足的判断结果将部分解与对应的约束存入cache。6.根据权利要求5所述的基于部分解caching与重用的符号执行优化方法，其特征在于，所述根据是否满足的判断结果将部分解与对应的约束存入cache包括：如部分解满足所述原子约束，则将所述部分解与原子约束对应存入cache，如部分解不满足所述原子约束，则对原子约束的条件取反后生成新的约束，并将新的约束与部分解对应存入cache。7.一种基于部分解caching与重用的符号执行优化装置，其特征在于，包括：约束收集模块，用于使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中的路径约束；命中判断模块，用于判断收集的路径约束是否能够命中当前cache，如果命中则返回执行约束收集模块，如果未命中则转入执行约束求解模块；约束求解模块，用于由约束求解器对未命中的所述路径约束进行求解，记录求解得到
的部分解及最终解；cache更新模块，用于将所述路径约束与记录的所述最终解存入cache，并根据所述部分解与所述路径约束的原子约束之间的匹配关系，将所述部分解与约束对应存入当前cache以更新当前cache，使得在符号执行过程中遇到相同或者相似的约束时重用对应的所述部分解，返回执行约束收集模块。8.一种基于部分解caching与重用的符号执行优化装置，包括处理器以及存储器，所述存储器用于存储计算机程序，所述处理器用于执行所述计算机程序，其特征在于，所述处理器用于执行所述计算机程序以执行权利要求1～6中任意一项所述方法。9.一种计算机可读存储介质，其特征在于，该计算机可读存储介质中存储有用于被计算机设备执行以实施权利要求1～6中任意一项所述方法的计算机程序。
技术总结本发明公开一种基于部分解Caching与重用的符号执行优化方法，包括步骤：S1：使用符号执行对被测程序进行分析以生成测试用例时，收集符号执行过程中路径约束；S2.判断收集的路径约束是否能够命中当前Cache，如果命中则返回步骤S1；如果未命中则转入步骤S3；S3.由约束求解器对未命中的路径约束进行求解，记录求解得到的部分解及最终解；S4.将路径约束与最终解存入Cache，并根据部分解与原子约束之间的匹配关系，将部分解与约束对应存入当前Cache，返回步骤S1。本发明能够充分利用部分解提升Cache命中率，有效提高测试用例生成过程中符号执行的效率且通用性强。号执行的效率且通用性强。号执行的效率且通用性强。
技术研发人员：陈振邦 王戟 马科林 刘坤林 帅子琦 毛晓光 董威 李姗姗 文艳军 陈立前 刘万伟 尹良泽
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2022.03.16
技术公布日：2022/7/5
