约束求解

摘要： 程序缺陷自动修复是指针对程序中存在的缺陷,自动生成相应的程序补丁,进而使程序恢复正常运行.首先,根据补丁生成方式的不同,将程序缺陷自动修复方法划分为4类,分别为基于搜索的、基于语义的、基于机器学习的以及基于错误报告驱动的程序缺陷自动修复方法.基于搜索的程序缺陷自动修复方法运用启发式算法在搜索空间内通过搜索生成程序补丁;基于语义的程序缺陷自动修复方法将修复约束作为合成程序补丁的规约,最后通过约束求解器生成程序补丁;基于机器学习的程序缺陷自动修复方法使用数据集训练并生成修复模型,通过修复模型生成程序补丁;基于错误报告驱动的程序缺陷自动修复方法通过利用程序执行以及用户反馈的错误信息生成程序补丁.本文对以上4类程序缺陷自动修复方法进行了详细阐述;其次,总结了检验程序缺陷自动修复方法及工具修复效果所用到的缺陷库;最后,分析了程序缺陷自动修复在工业界的应用现状并总结了该领域面临的关键问题及未来研究的方向.

摘要： 针对可执行程序中难以发现的内存脆弱性,提出了一种基于内存访问轨迹的程序脆弱性检测方法.应用有限状态机模型,将内存访问的轨迹看作各状态之间的转化,基于其中不合法的转化定义了几种内存脆弱性及约束条件:内存泄漏、未初始化读、双重释放、释放后读写、死写以及重复频繁读.借助二进制插桩工具Intel-Pin获取可执行程序的内存访问轨迹,结合自定义的内存脆弱性约束,通过约束求解器混合求解,从而确定程序的内存脆弱性类别和位置.结果 表明:本文方法可以检测出一些可执行程序中普遍存在的内存脆弱性以及低效代码,同时也能检测出近几年曝出的危害极大的内存漏洞及其变种.

摘要： 动态符号执行是一种有效的软件测试方法,但由于受到约束求解器求解能力的限制,在面对较为复杂的程序和路径条件时,动态符号执行的路径覆盖率还有待提升.针对上述问题,提出了一种遗传算法辅助的动态符号执行测试方法,并基于此方法实现了原型工具JDart-Ga.该方法结合遗传算法的优势,生成约束求解器无法求解的约束条件对应测试输入,从而提升动态符号执行的路径覆盖率.实验结果表明,在测试存在动态符号执行无法覆盖路径的3个实验对象时,所提出方法的路径覆盖率与JDart相比分别提升了16％至23％.

摘要： 针对基于PHP语言开发的Web应用系统,提出了一种基于图遍历算法的服务端请求伪造漏洞检测和利用方法.通过构建抽象语法树,获取每个文件的数据流信息,进而利用数据流中的传递依赖关系构造全局的代码属性图,使用图遍历算法对生成的代码属性图进行污点分析,得到污点变量的代码传递依赖路径图,最后使用约束求解的方法对路径图中的经过函数信息进行漏洞检测并生成可利用的攻击向量.实验结果表明,这种检测方式相较于传统的静态审计方法能够很好地发现服务端请求伪造漏洞,并能够自动化生成可绕过的攻击向量.

摘要： 处理器研制过程中需要对指令算术数据路径进行覆盖验证.针对现有模拟验证方法存在的不足,提出了一种基于可满足模理论(satisfiability modulo theory,SMT)的指令约束求解方法:利用可满足模理论求解器将指令级功能验证任务转化成数据约束求解满足问题.在结果操作数约束、操作数间约束、指令内部约束以及浮点操作数约束4个方面分别给出示例,并分别给出了利用SMT求解器进行约束建模的关键过程以及可以用于指令级功能验证的元组数据.为提高求解模型效率,提出了2种解决方法:首先利用时间阈值实现问题求解超时即终止的策略;其次是结合进程管理与线程管理技术,实现了指令功能约束并行求解框架,将串行求解任务分派给可并行执行的多个线程,提高了求解速度.该技术已成功应用于系统级验证中,有效提升了测试覆盖与质量,取得了很好的效益.

摘要： 随着移动计算、物联网、云计算、人工智能等领域的飞速发展,也涌现出了很多新的编程语言和编译器,但是C/C++语言依旧是最受欢迎的编程语言之一,而数组是C语言最重要的数据结构之一.当在程序中通过数组下标访问数组元素时,必须确保该下标在该数组的边界之内,否则就会导致数组越界.程序中的数组越界缺陷会使得程序在运行时导致系统崩溃,甚至使攻击者可以截取控制流以执行任意恶意代码.当前针对数组越界的静态检查方法无法达到高精度的分析,尤其是无法处理复杂约束和表达式,过多的误报额外增加了开发者的负担.因此,提出了一种基于污点分析的数组越界的静态检测方法.首先,提出流敏感、上下文敏感的按需指针分析方法,实现数组长度区间分析.然后,提出按需污点分析方法,实现数组下标和数组长度污染情况的计算.最后,定义数组越界缺陷判定规则,提出使用后向数据流分析方法,检测数组下标是否越界.在进行数组越界检测的过程中,为了处理程序中的复杂约束和表达式,在分析过程中将调用约束求解器来判断约束的可满足性.如果没有发现相应的语句,则报告数组越界缺陷警报.同时,实现了自动静态分析工具Carraybound,并通过实验展示了方法的有效性.

摘要： 根据空间众包任务类型的多样化特点,构建空间众包任务分配模型并提出基于预测算法的在线任务分配策略.在批处理模式下,将最大分数任务分配问题转化为寻找二分图最大权匹配问题,通过匈牙利算法对其进行求解得到每个时间片的最大分数,并利用预测算法使得工人在完成该任务后尽可能处于任务密集区域,避免出现工人没有合适任务可执行的情况发生,实现模型的最优在线任务分配.在滴滴快车数据集上的实验结果表明,与BASIC、LLEP和CDP策略相比,该策略在整个时间段内的总任务分配数量最多能提高10％,具有更高的任务分配效率与质量.

摘要： 在漏洞挖掘中,符号执行技术是一种常用的测试用例生成技术.但当软件中包含加解密、校验和检验等复杂数学运算函数时,使用符号执行技术生成测试用例存在无法有效求解约束表达式的问题,导致漏洞挖掘效率低下.针对该问题,文章结合分治算法的思想提出基于符号分治区的测试用例生成技术.首先通过静态分析技术识别软件中的加解密、校验和检验等函数;然后以程序中的加解密、校验和检验函数为分界点对软件进行分区,符号执行引擎每执行到软件的一个分治区,就在本区引入一个新的符号变元进行约束构建,在约束求解时从软件最后一个分治区开始递归求解.基于该方法,文章在符号执行平台S2E上实现了漏洞挖掘原型系统Divide,并与现有的符号执行生成测试用例技术进行对比实验.实验结果表明,文章方法能够快速、有效地生成测试用例,提高漏洞挖掘的效率.

摘要： 近年来符号执行技术研究取得了很大的进展,但受限于程序内部本身复杂的执行环境和SMT理论的研究进展,这项技术仍然面临着可扩展性差的问题.在符号执行中,约束求解主要负责对路径可达性进行判定以及测试输入生成的工作,但路径爆炸问题带来的频繁调用,以及SMT求解器本身的能力和效率的不足,使得约束求解占用了符号执行中主要的性能开销,约束求解问题也成为符号执行中面临的主要瓶颈问题之一.本文首先介绍了符号执行和约束求解的基本概念,并分析了符号执行中约束求解问题的由来,然后对近年来的约束求解问题研究进展进行了归类,最后对这方面的研究进行了展望和总结.

摘要： 针对多核硬件结构出现后时间耗费型的约束求解问题具有并行求解能力的问题,分析回溯搜索算法和相容技术,提出并行相容和并行搜索结合的约束求解方法.在并行相容技术上,提出基于集中式存储的全局约束并行相容模型,以高效压缩搜索空间,优化搜索过程;研究搜索空间分裂方法,通过对搜索空间划分与调度确保并行搜索的不相交和完整性.实验验证方法的可行性并能够获得更高的加速比.

摘要： 静态程序分析具有良好的覆盖率,但是它不可避免地会导致一些误报。对一个流行的程序分析工具CQual进行了改进,添加了对结构成员之间关系的建模,扩充了类型推断规则和约束求解规则,并使用改进后的CQual对一些实用程序中存在的格式串缺陷进行了分析，与原始CQual的分析结果相比,它消除了一类误报,从而减小了分析人员排错的负担。

摘要： 针对符号执行建立的路径条件求解困难的问题，结合混合约束求解的最新研究成果，提出了一个多策略的路径条件求解算法。分析了路径条件的具体特征，通过路径条件的变换及时消除不可行路径，在路径条件的求解中，首先求解线性约束，并利用这些初步解，结合启发式方法进一步求解非线性约束。实现了一个针对C程序的多策略路径条件求解原型MPCS1．0，初步实验表明该方法的可行性。

摘要： 在模具的虚拟设计中，模具的装配设计阶段是一个十分重要的阶段，对后续工作影响很大。模具的装配设计的实质是参与装配的各个部件按照装配关系进行装配约束求解的过程，采用传统的数值法进行约束求解，需要大规模求解非线形方程组，计算效率缓慢，有可能不收敛。本文设计了的适合模具的装配模型和装配约束，采用自由度分析算法进行装配约束求解，能够正确、有效地求解装配约束，无需建立和求解大型分线性方程组;同时较好的解决装配中的欠约束和过约束问题，更易实现装配设计过程的智能化、自动化。

摘要： 动态符号执行是对程序进行安全性分析的重要技术。在动态符号执行过程中，存在着符号地址，系统调用，路径选择等问题。针对符号地址导致的别名分析问题，本文提出了一种基于约束的指针分析方法，对程序进行过程内的指向分析，并对指针分析过程引入约束条件，产生可以进行路径选择的测试用例，以提高指针分析的精度。在国内首款某型号商用编译器的开发过程中实现了该方法，实验结果表明，该方法可以准确地分析C语言测试用例，缩短用例测试的时间。

摘要： 动态符号执行是对程序进行安全性分析的重要技术。在动态符号执行过程中，存在着符号地址，系统调用，路径选择等问题。针对符号地址导致的别名分析问题，本文提出了一种基于约束的指针分析方法，对程序进行过程内的指向分析，并对指针分析过程引入约束条件，产生可以进行路径选择的测试用例，以提高指针分析的精度。在国内首款某型号商用编译器的开发过程中实现了该方法，实验结果表明，该方法可以准确地分析C语言测试用例，缩短用例测试的时间。

摘要： 动态符号执行是对程序进行安全性分析的重要技术。在动态符号执行过程中，存在着符号地址，系统调用，路径选择等问题。针对符号地址导致的别名分析问题，本文提出了一种基于约束的指针分析方法，对程序进行过程内的指向分析，并对指针分析过程引入约束条件，产生可以进行路径选择的测试用例，以提高指针分析的精度。在国内首款某型号商用编译器的开发过程中实现了该方法，实验结果表明，该方法可以准确地分析C语言测试用例，缩短用例测试的时间。

摘要： 动态符号执行是对程序进行安全性分析的重要技术。在动态符号执行过程中，存在着符号地址，系统调用，路径选择等问题。针对符号地址导致的别名分析问题，本文提出了一种基于约束的指针分析方法，对程序进行过程内的指向分析，并对指针分析过程引入约束条件，产生可以进行路径选择的测试用例，以提高指针分析的精度。在国内首款某型号商用编译器的开发过程中实现了该方法，实验结果表明，该方法可以准确地分析C语言测试用例，缩短用例测试的时间。

摘要： 动态符号执行是对程序进行安全性分析的重要技术。在动态符号执行过程中，存在着符号地址，系统调用，路径选择等问题。针对符号地址导致的别名分析问题，本文提出了一种基于约束的指针分析方法，对程序进行过程内的指向分析，并对指针分析过程引入约束条件，产生可以进行路径选择的测试用例，以提高指针分析的精度。在国内首款某型号商用编译器的开发过程中实现了该方法，实验结果表明，该方法可以准确地分析C语言测试用例，缩短用例测试的时间。

摘要： 本发明提出了一种基于改进约束序优化的带安全约束的不确定性机组组合问题求解方法，首先在粗糙模型中融入离散变量识别策略，并构造基于约束条件的序优化粗糙模型；然后在精确模型中引入非有效安全约束削减策略，并构造针对连续变量的序优化精确模型。相比于传统针对SCUC模型的约束序优化方法，本发明提出的改进策略有效提升了序优化算法的紧凑性，降低了计算冗余度，因而具有更高的求解效率。

摘要： 本发明公开了一种求解约束优化问题的量子近似算法，属于量子计算技术领域。本发明将二次无约束的二元优化方法和量子交替算符拟设方法融合在同一量子近似优化算法框架中，利用经典的贪心算法，对带约束的优化问题进行求解，得到的近似最优解作为一个约束条件，根据约束条件重新设计编码演化算符，使得表征解的量子态演化限制在可行解范围内，并且，将约束优化问题通过添加惩罚项转化为无约束优化问题，当有解违反约束时，在目标函数中添加惩罚项，使不满足约束条件的解的期望值比满足约束条件的解要差，通过本发明方法能高效的求解约束优化问题。

摘要： 描述了一种评估并减少对象检测结果与识别结果中的感知误差的系统。所述系统包括感知模块，其从移动平台附近的环境接收(对象的)感知数据。生成感知探针，所述感知探针描述对象的一个或更多个特性。将感知探针转换为基于概率信号时间逻辑(PSTL)的约束，其提供具有感知探针的统计分析的公理。对公理进行评估，以将感知探针分类为有效的或有误差的。通过基于公理求解优化问题来生成最优感知参数，这允许所述系统基于最优感知参数来调整感知模块。

摘要： 本发明提出了一种动态神经网络(Dynamic neural network，DNN)来求解时变跳数约束最短路径问题(Time‑varying shortest path problem with hop‑constraint，HC‑TSPP)。HC‑TSPP的目的是寻找一条传输时间最短且弧数受限的路径。提出的DNN是一种基于动态神经元的新型神经网络。DNN上的所有神经元都是并行计算的，每个动态神经元由七个部分组成：输入、波接收器、滤波器、状态存储器、波产生器、波发送器和输出。波是神经元通信的载体，每一条波由三部分组成。最短路径的报告是基于到达目的节点并满足跳数约束的第一个波。实验结果表明本发明提出的方法能够求得问题的全局最优解。

摘要： 本公开涉及一种驱动量子计算网络的方法，所述方法用于确定二次无约束二值优化问题的解的代价函数的极值，所述方法包括：初始化量子比特；将量子门层顺序地应用于所述量子比特，其中，每一层包括作用于多个量子比特的多量子比特量子门以及具有两个特征值和对所述量子比特的可变作用的多个变分量子门，其中，所述量子门层的变分量子门的可变作用形成变分参数的集合；以及确定所述量子计算网络的输出状态以获得与所述变分参数的集合相关联的解，其中，所述二次无约束二值优化问题的每个二值变量都与所述寄存器量子比特的计算基态相关联，并且所述解是通过评估测量到与所述二值变量相对应的计算基态的概率而获得的，并且其中，所述解通过以下操作迭代地改进：确定经变更的变分参数的输出状态以评估关于所述变分参数的子集的偏导数，从而基于所述经变更的变分参数的输出状态确定所述代价函数的梯度；以及基于所述代价函数的梯度上的移动平均值与所述代价函数的平方梯度上的移动平均值的更新函数来更新所述变分参数。

摘要： 本发明公开了一种用于求解电力调度问题的联合机会约束优化方法及装置，包括：建立含新能源出力的联合机会约束；其中，所述新能源出力为多维随机变量；通过预先设置的风险水平的权重，将联合机会约束拆分成多个单一机会约束；其中，单一机会约束与随机变量一一对应；通过预设的散度函数和散度容差，修正每个所述单一机会约束的风险水平；根据每个随机变量的历史数据样本和区间自适应带宽的核密度估计，得到每个随机变量的累积分布函数；通过每个随机变量的累积分布函数，将与该随机变量对应的单一机会约束转化为确定性约束；将每个确定性约束输入至求解器中进行求解，得到电力优化调度结果，能够有效提高电力优化调度结果的准确性且操作简单。

摘要： 本发明涉及一种求解复杂约束优化问题的多策略混合麻雀搜索方法。通过在初始化阶段引入基于对位学习策略，获得更优的初始种群；在更新种群阶段结合差分进化算法扩展算法探索和开发能力；最后，引入基于社区学习策略对种群进行精炼，进一步平衡局部搜索和全局搜索能力，并保持种群的多样性。本发明方法对比其他先进优化算法是非常具有竞争力。

摘要： 一种基于时间波延时神经网络的约束时变最短路径求解方法，该方法通过构造时间波延时神经网络(time wave delay neural network，简称TWDNN)来求解约束时变最短路径(constrained time‑varying shortest path problem，简称CTSPP)；设计的TWDNN是一种基于时间波延迟神经元的新型神经网络，与传统的神经网络不同的是，TWDNN不需要任何训练，TWDNN的设计包括神经元结构设计和神经网络结构设计，时间波延时神经网络上的每个神经元由输入、波接收器、神经元状态、波发生器、波发送器和输出六个部分组成；波是神经元之间交换信息的媒介，波在神经元之间的传播时延相当于数据包在网络上的传输时延，最短路径的输出是基于目的神经元接收到的时间波。实验结果表明，所提出的方法优于现有的方法。

摘要： 本发明提供了一种基于约束求解引擎的带约束随机数生成方法，包括以下步骤：1）编译用户在EDA数字仿真器中输入的仿真代码，获取随机变量、约束、求解次数，其中，所述求解次数记作N；2）对所述随机变量进行比特提取，将提取的随机变量的每一个比特作为独立的随机变量；3）利用表达随机的约束，生成随机属性约束：对于第一次求解，利用随机函数为随机变量每一个比特随机生成0或1的值，获得随机属性约束；对于第2次到第N次求解，对上一次的求解结果，随机选择选定个数的比特，进行比特值的翻转，获得随机属性约束；4）将所有约束送入约束求解引擎进行求解。本发明能够在保证随机性的前提下，很大程度上提升效率。

摘要： 本发明公开一种基于数据路径约束求解的随机指令测试程序生成方法，包括以下步骤：S1、循环读取基于约束求解的随机指令序列文件，每次读取一行，若为空则跳转至S7；S2、根据S1中读取的内容，解析指令格式，获取指令名称以及指令格式中每一个操作数的类型；S3、随机读取与S2中解析的指令对应的数据路径约束求解结果文件，获取一组基于数据路径约束的验证元组数据；S4、将S3中获取的验证元组数据按照对界要求预先存储到局存空间中；S5、根据S1中自随机指令序列文件读取的当前随机指令；S6、跳转至S1继续读取指令序列进行解析；S7、生成结果校验代码。本发明可以提升随机指令测试的有效性。