基于Petri网展开的多线程程序数据竞争检测与重演

数据竞争是多线程程序的常见漏洞之一,传统的数据竞争分析方法在查全率和准确率方面难以两全,而且所生成检测报告难以定位漏洞的根源.鉴于Petri网在并发系统建模和分析方面具有行为描述精确、分析工具丰富的优点,提出一种基于Petri网展开的新型数据竞争检测方法.首先,对程序的某一运行轨迹进行分析和挖掘,构建程序的一个Petri网模型,它由单一轨迹挖掘得到,却可隐含程序的多个不同运行轨迹,由此可在保证效率的同时降低传统动态分析方法的漏报率;其次,提出基于Petri网展开的潜在数据竞争检测方法,相比静态分析方法在有效性上有较大提升,而且能明确给出数据竞争的产生路径;最后,对上一阶段检测到的潜在数据竞争,给出基于CalFuzzer平台的潜在死锁重演调度方法,可剔除误报,保证数据竞争检测结果的真实性.开发相应的原型系统,结合公开的程序实例验证了所提方法的有效性.     

基于矩阵运算的Petri网反向推理算法

通过对加权模糊Petri网模型和反向推理算法的研究,建立了加权模糊Petri网的关联Petri网推理模型。在此基础上,提出了基于矩阵运算的反向推理算法。通过实例对算法进行了检验,结果表明该算法具有解决复杂问题的并行推理能力、推理效率高、推理过程简单、容易实现。     

非交互式Petri网可覆盖性验证的高效实现

近年来,基于Petri网可覆盖性的验证技术已经成功地应用于并发程序的验证与分析中.然而,由于Petri网的可覆盖性问题复杂度太高,这类技术在应用时有较大的局限性,对于输入规模较大的问题常常会出现超时的情况.而Petri网的一个子系统——非交互式Petri网,其可覆盖性和可达性复杂性均是NP完备的,同时表达力又可以作为某类并发程序的验证模型.设计并实现了可以高效验证非交互式Petri网可覆盖性的工具CFPCV.采用基于约束的方法,从模型中提取约束,并使用Z3 SMT求解器对约束进行求解,同时,通过子网可标记方法对候选解进行验证,从而保证每组解都是正确解.通过实验分析了该工具的成功率、迭代次数以及运行效率,发现该算法不仅验证成功率高,而且性能非常优异.     

基于Petri网的协同三维建模工作流模型研究*

通过分析大规模三维场景单机建模所面临的局限性问题,对三维场景协同建模理论进行了描述。结合workflow net的定义以及建立工作流模型的方法,采用基于Petri网扩展的、用于复杂工作流模型设计的建模方法建立协同三维建模的工作流模型,并通过Petri网相关理论分析得出所建模型具有可达性、有界性、活性,并且是安全可靠的,同时对系统中必须加以解决的并发问题进行了相关的探讨。     

Petri网展开图法的分析和应用

Petri网的展开图是一种特殊的并发系统状态空间搜索方法，它不需要重复考虑并发事件的所有可能的交集，从而大大缩减状态空间爆炸给验证分析带来的空间复杂度和时间复杂度。使用展开图分析Petri网的行为属性与传统的Petri网分析方法相比，具有自己的特点。该文首先介绍了Petri网展开图的构造算法，在此基础上使用展开图分析方法对一个典型Petri网的活性，有界性和可逆性等行为属性进行了分析，并与传统的Petri网分析方法作比较。     

共享竞争择一资源Petri网的形式化设计方法

自动制造系统中有许多共享资源，例如，机器人、数控加工中心、无人导引自动小车等，竞争择一是其共享方式之一。以往，自动制造系统的Ｐｅｔｒｉ网控制系统器设计几乎都是试凑，而且一些性质不能得到满足，如无死锁。这主要是对共享资源的不适当设计造成的。对于多个子系统，为了使之能很好地工作，必须研究一种设计有界、无死锁的Ｐｅｔｒｉ网控制器的方法。本文在以往工作的基础上，提出了有界、无死锁、安全Ｐｅｔｒｉ网控制器…     

基于通信Petri网的异步通信程序验证模型

由于多栈的模型图灵等价,因此通用的异步通讯程序模型的验证问题不可判定.为此,基于Petri网,提出了一个新的模型通讯——通讯Petri网对异步通讯程序进行刻画,通过对输入通讯进行k-型限制,以及对每个栈进行基于正则语言泵引理的抽象,通过将这样限制下的模型编码到数据Petri网,证明了限制下的新模型可覆盖性可判定.     

基于Petri网的程序缓冲区溢出检测方法

由于软件的安全性问题的很大一部分是由于缓冲区溢出而引起的。因此，为了减少软件的安全漏洞，本文提出了一种利用着色Petri网的理论来检测原代码缓冲区溢出方法，并用CPNTools进行仿真证明了该方法的正确性和简便性。这为软件的缓冲区溢出检测增添了一种新的方法。     

基于面向对象Petri网的设备采购管理系统建模及性能分析

传统的设备采购系统不能随外界环境的变化而进行相应的重组。为此,本文提出了一种基于面向对象Petri网的设备采购系统的工作流模型。该模型将各个对象的内部结构进行封装,避免了相互之间的库所与变迁的定义干涉。模型具有模块化、图形化、结构化的特性,提高了设备采购系统的可重用性和可扩展性。以审批部门的OOPN模型为例,求其关联矩阵、可覆盖性树和P不变量,并进行相关性分析,证明了构建的模型具有良好的性能并满足系统变化和重组的要求。     

用Petri网分析循环程序的并行性

为分析循环程序的并行性,最重要且最基本的工作是数据相关性分析,而数据相关性分析最主要的内容之一是循环程序中数组元素间的数据相关性分析。传统的分析方法是通过数组的下标进行分析计算,但这种计算每次只能对两个语句间的相关性作出结论,而无法知道是否有第三个或更多的语句在这同一数据处相关,从而很难确定这两个语句是否可以并行。将Petri网用于数据相关性分析理论中,可以从全局的观点分析出同一数据处所有语句的相关性,从而可以提出将循环程序转换为并行程序的有效方法。     

目标导向的多线程程序UAF漏洞预测方法

Use-After-Free （UAF）漏洞是多线程程序的常见并发缺陷.预测性UAF漏洞检测方法因兼顾误报率和漏报率而备受关注.然而,已有的预测性UAF检测方法未结合待检测目标作针对性优化,当程序规模大或行为复杂时会导致检测效率低下.为解决上述问题,本文提出一种目标导向的多线程程序UAF漏洞检测方法.首先,由程序运行轨迹挖掘程序的Petri网模型;之后,针对每一个潜在可构成UAF漏洞的内存Free/Use操作对,以触发该漏洞为目标导向,在程序的Petri网模型中添加保持操作间因果约束和数据一致性的行为控制结构,在此基础上设计一种基于Petri网反向展开的UAF漏洞检测方法.该方法每次只针对一个潜在的UAF漏洞有针对性地验证其真实性,从而保证检测的效率.与此同时,为减少待检测的潜在UAF漏洞数量,提出一种新型向量时钟进行Free操作与Use操作间的因果关系自动识别,据此对潜在的UAF漏洞进行筛选.结合多个程序实例对所提方法进行了实验评估.实验结果表明,所提方法在检测的效率和准确性方面较主流方法有所提高.     

一类资源组合问题的扩展参数Petri网建模与优化研究

现代企业重组及ＣＩＭＳ资源调度问题是一类典型资源组合优化问题。文中针对这类资源组合优化问题。提出一种新的建模方法－－扩展参数Ｐｅｔｒｉ网。该网通过着色Ｐｅｔｒｉ网和时间Ｐｅｔｒｉ网中引入扩展参数使之对任务执行过程具有很强的模型描述与性能评价能力。另外,在该网中扩展的控制决策层Ｐｅｔｒｉ网模型不仅实现了对资源组合方案选择与评价并且可以方便地与不同的优化策略与优化算法进行集成,使问题的求解更加灵活、高     

基于Petri网工作流模型展开树的路径序列相似性算法

在实际的数据迁移项目中,为了解决数据映射的问题,需要确定两个工作流模型之间的相似度。从工作流模型的相似性方面进行分析阐述,提出了基于Petri网的工作流模型展开树的路径序列相似性算法。首先采用深度优先搜索算法和动态规划算法对模型进行搜索;其次通过提出的算法获取展开树的所有路径序列;最后利用编辑距离算法计算两个模型序列之间的两两相似度,进而完成模型相似性计算;相较于其他的主流相似度算法,主要优点在于可以精确计算得到模型部分结构和行为相似度,可以更好地确定流程间映射,从而找到数据映射的解决方法。实验结果表明,该方法较主流的基于模型结构和行为相似性的算法,计算合理性和准确性有很大提升。     

基于数据影响的多对象交互流程偏差检测方法

现有的大多数偏差检测方法能够识别来自流程活动及部分数据属性的偏差,但是无法处理流程执行过程中数据变化对流程的影响问题,尤其是在涉及多对象交互的情况下。针对这一问题,提出了一种多对象交互情况下基于数据影响的业务流程偏差检测方法。首先,基于控制流与数据信息识别可能的偏差活动;然后,根据数据变化对活动的影响定义影响集;接着,将以对象为中心的概念引入偏差检测过程,形式化以对象为中心的Petri网模型,在此基础上,通过分析对象是否对其修改的数据具有执行权限,分类并定义了四种数据影响类型及其计算标准,据此得到基于数据影响的偏差检测结果;最后,与其他偏差检测方法对比验证,结果表明,应用该方法得到的偏差检测结果值得到提升,并且能够处理多对象交互的流程偏差。该方法能够有效捕获多对象交互流程中数据变化影响的流程活动,提高偏差检测的合理性与准确性。     

基于Petri网的入侵模式的自动化建库

详细介绍了目前正在研究开发的基于Petri网的入侵检测系统的模式库的构建方法。该方法采用统一化方法表示攻击行为,具有跟踪检测的特性,并可以有效地分析DDOS等分布式入侵行为。