检索结果-内蒙古大学图书馆

软件学报 2015年第10期26卷 2485-2503页

作者：周筱羽顾斌赵建华杨孟飞计算机软件新技术国家重点实验室(南京大学) 江苏南京210023 南京大学软件学院江苏南京210093 西北工业大学计算机学院陕西西安710072 南京大学计算机科学与技术系江苏南京210023 中国空间技术研究院北京100094

针对一类中断驱动的航天控制系统,给出了有界模型检验的算法.这类系统由中断处理程序和操作系统调度的任务组成.当中断发生时,对应的中断处理程序响应中断事件,并可以修改控制变量值,以便在系统任务中完成后续工作.操作系统周期性地调... 详细信息

针对一类中断驱动的航天控制系统,给出了有界模型检验的算法.这类系统由中断处理程序和操作系统调度的任务组成.当中断发生时,对应的中断处理程序响应中断事件,并可以修改控制变量值,以便在系统任务中完成后续工作.操作系统周期性地调度任务序列处理日常事务以及中断事件的后续工作.使用了带中断标记的时间自动机对中断事件和任务调度事件进行建模,并使用中断向量表和中断处理程序的伪代码模型共同描述中断的处理过程.控制变量将中断处理过程和系统任务相关联,中断处理程序可以设定某个控制变量,而系统任务则通过检查该控制变量来确定是否需要进行后续处理.对于这样的形式化模型,给出了检验关键时序性质的有界模型检验算法.该算法使用深度优先的方式遍历所有长度小于等于K的可行路径,并使用SMT Z3实现了对时间约束和规约的处理.

关键词：中断驱动系统有界模型检验超时检测

来源：评论

学校读者我要写书评

暂无评论

有界模型检验与时序深度计算算法研究

有界模型检验与时序深度计算算法研究

引用

作者：张忠林复旦大学

学位级别：硕士

随着集成电路技术的飞速发展，电路的规模不断增大。电路验证领域正面临前所未有的挑战，如何快速并且完备地完成超大规模集成电路的设计验证，已经成为当前的研究热点。与传统的基于模拟的验证方法相比，形式化验证方法中的模型验证方... 详细信息

随着集成电路技术的飞速发展，电路的规模不断增大。电路验证领域正面临前所未有的挑战，如何快速并且完备地完成超大规模集成电路的设计验证，已经成为当前的研究热点。与传统的基于模拟的验证方法相比，形式化验证方法中的模型验证方法由于具有完备性的优点被广泛使用。为了扩大模型检验的验证范围，被称为有界模型检验的验证方法被提出。然而，有界模型检验算法最主要的缺点是验证的不完备性，即我们不知道验证所需的深度。为了克服有界模型检验算法的这个缺点，本文提出的时序深度计算的算法。该算法创新之处分为两点：(1)基于可满足算法引擎的后续状态的计算。由于本文在后续状态的计算中使用了可满足算法引擎，大大提高了后续状态的计算速度和计算的能力。并且我们计算的规模较小，每次运算后可满足问题的子句数目变化很小，因此一直可以保持比较快速和高效的计算。(2)基于高度平衡二叉搜索树的历史状态的存储方法。由于本文所提的算法需要大量的查找历史状态的操作，因此如何得到一个稳定的平均查找时间就成为了本算法的一个要点。因此本文使用了高度平衡二叉搜索树的算法，该算法在大量结点插入运算后，可以保持良好的搜索高度，使得搜索时间稳定在O(log2n)量级。此外，我们的提出的算法具有很强的灵活性。对于内部，程序可以调用不同的SATSolver来完成；对于外部，可以作为独立的软件使用，也可以作为一个模块被其他算法调用，比如用于时序电路的等价验证。

关键词：有界模型检验时序深度形式化验证可满足性问题

来源：评论

学校读者我要写书评

暂无评论

一种改进的有界模型检验子句规则

引用

微电子学与计算机 2007年第11期24卷 103-106,109页

作者：尹文波荆明娥周电周晓方复旦大学专用集成电路与系统国家重点实验室上海201203

为有界模型检验提出了改进的子句规则。在节点分类的基础上,首先对精简布尔电路表示进行逻辑化简,去掉功能冗余节点;然后识别、记录和处理多元运算的操作数,把多元运算作为单个节点直接生成子句;最后合并相邻节点,根据合并后的逻辑关系... 详细信息

为有界模型检验提出了改进的子句规则。在节点分类的基础上,首先对精简布尔电路表示进行逻辑化简,去掉功能冗余节点;然后识别、记录和处理多元运算的操作数,把多元运算作为单个节点直接生成子句;最后合并相邻节点,根据合并后的逻辑关系生成变量和子句。实验结果表明,改进的子句规则普遍减少了可满足性问题的变量、子句数目和运行时间。

关键词：可满足性问题有界模型检验子句规则精简布尔电路

来源：评论

学校读者我要写书评

暂无评论

基于有界模型检验的硬件木马检测方法

基于有界模型检验的硬件木马检测方法

引用

作者：于露同济大学

学位级别：硕士

随着集成电路的广泛应用，植入集成电路的硬件木马严重地损害了广大使用方利益。硬件木马是指在集成电路芯片上植入的具有恶意功能的冗余电路，用于篡改电路数据、修改或破坏电路功能、修改电路参数和拒绝服务等。由于硬件木马在大多数... 详细信息

随着集成电路的广泛应用，植入集成电路的硬件木马严重地损害了广大使用方利益。硬件木马是指在集成电路芯片上植入的具有恶意功能的冗余电路，用于篡改电路数据、修改或破坏电路功能、修改电路参数和拒绝服务等。由于硬件木马在大多数情况下处于潜伏状态，只有罕见条件才能将其触发，故难以有效检测，危害极大。　　对于使用方，如何快速有效地检测出集成电路中的硬件木马已成为亟待解决的问题。针对这些问题，本文提出了一个基于有界模型检验的逻辑木马检测方法，并通过分析得到的反例构建测试序列数据库，从而进一步确定硬件木马的存在。　　针对时序逻辑电路的时序特征，本文结合有界模型检验的原理，设计并实现了可有效检测植入时序逻辑电路中的硬件木马的检测方法。对于时序深度很深的时序逻辑电路，本木马检测方法依然有效。　　针对规模较小的微型木马，本文在实验中设计了多种不同类型的微型木马，证明了本文的木马检测方法对微型木马有较强的识别能力。　　根据对木马检测所提出的功能需求、性能需求，制定了详细的测试计划及方案，分别进行了功率消耗测试、时间延迟测试、测试成本分析，并对实验结果进行分析。

关键词：硬件木马木马检测有界模型检验时序逻辑木马微型木马

来源：评论

学校读者我要写书评

暂无评论

面向路径代码有界模型检验的系统优化技术研究

面向路径代码有界模型检验的系统优化技术研究

引用

作者：闾乐成南京大学

学位级别：硕士

随着社会信息化程度的不断提高,计算机在各行各业扮演的角色越来越重要,软件系统的安全问题也因此愈发受到重视。而C语言在航空航天、地铁运输、国防安全等关键领域使用广泛,因此保障C代码的正确性非常重要,研究人员基于传统模型检验技... 详细信息

随着社会信息化程度的不断提高,计算机在各行各业扮演的角色越来越重要,软件系统的安全问题也因此愈发受到重视。而C语言在航空航天、地铁运输、国防安全等关键领域使用广泛,因此保障C代码的正确性非常重要,研究人员基于传统模型检验技术研发了多款面向C代码的模型检验工具如CBMC、CPAChecker等等。但以上方法和工具都是针对代码转化得到的整体问题进行验证,随着代码规模的不断扩大会导致状态空间爆炸的问题,使得问题规模超出底层求解器支持,验证效率低下。为此,在之前的工作中,我们已经提出了一种面向路径的有界模型检验算法SAT-LP-IIS,该算法将单次验证对象限制为一条程序执行路径,能够一定程度上控制验证复杂度,并以此为基础实现了一个简单工具原型。然而在我们将该方法实际应用于C代码的模型检验时,仍有很多挑战需要面对,首先是该方法在处理规模较大的代码时,需要遍历验证的路径数量很大,可能存在路径爆炸的问题,因此需要更加高效的路径遍历方法;同时,当输入的代码中包含迭代次数较大的循环结构时,路径的长度可能很大,导致单次验证的难度提升,因此需要有效处理循环的方法和框架。为解决上述问题,同时将方法实际应用于C代码上的有界模型检验,本文主要做了如下工作:针对目前存在的路径爆炸的问题,本文提出了一种新型的路径遍历方法。该方法基于并行计算技术,通过并行验证多条路径加快验证,同时使用共享不可行路径池,同步反馈各路径验证结果以避免不必要的计算,从而提高整体的验证效率。针对目前无法有效处理迭代次数较大的循环结构的问题,本文提出了一种针对循环结构的集成处理框架。该框架利用循环总结技术和循环抽象技术,在验证之前对循环进行预处理,从而提高系统对循环结构的处理能力。为了将上述方法落实到实际C代码的有界模型检验上,同时为了评估本文工作的效果,我们按照优化后的算法和框架实现了一个面向C代码的有界模型验证工具BRICK,并添加了多种通用技术进行整体支持。我们为优化前后的BRICK与一些具有代表性的同类工具设计了实验并将结果进行对比,结果显示基于本文方案的BRICK有着良好的性能优势。

关键词：形式化验证有界模型检验面向路径并行计算循环预处理

来源：评论

学校读者我要写书评

暂无评论

中断驱动系统有界模型检验的偏序优化技术研究

中断驱动系统有界模型检验的偏序优化技术研究

引用

作者：蔡增科南京大学

学位级别：硕士

中断驱动系统(Interrupt-driven System)被广泛应用于安全关键系统中,因而中断驱动系统的正确性保障尤为重要。此类系统通常使用操作系统任务调度加中断处理程序的软件体系结构。系统中的中断事件的发生时间及顺序具有极大的不确定性,... 详细信息

中断驱动系统(Interrupt-driven System)被广泛应用于安全关键系统中,因而中断驱动系统的正确性保障尤为重要。此类系统通常使用操作系统任务调度加中断处理程序的软件体系结构。系统中的中断事件的发生时间及顺序具有极大的不确定性,不同的中断发生时间和顺序将导致不同的系统行为,而系统中的许多设计错误只有在特定的处理顺序下才会显现出来。因此在中断驱动系统的设计和开发过程中,测试工作开销极大且效率低下,需投入很大的精力用于错误的重现与定位,大量的测试工作只能定位少数错误,系统的正确性得不到保障。模型检验(Model Checking)技术的出现使得全面分析和验证中断驱动系统的系统行为成为可能。其基本思想是对待验证系统进行形式化建模,用模型的运行来模拟系统运行,然后利用计算机的快速计算能力,穷举被验证系统的状态空间中的每一个状态来验证该系统是否满足特定的形式规约。在过去的工作中,我们提出了中断驱动系统的有界模型检验方法,其核心是以时间自动机+伪代码建立中断驱动系统的形式化模型,然后用深度优先的方式进行状态空间遍历。实践证明,该方法能够切实有效地检测出中断驱动系统中的错误。但随着中断驱动系统中中断数量的增长,模型状态空间呈指数级增长,使得检验过程的时间花费极高。偏序约减(Partial Order Reduction)技术通过消除并发系统中由于迁移交错执行而产生的冗余的遍历路径来达到约减状态空间的目的,是一种常用的提高模型检验算法效率的方法。本文通过对中断驱动系统所具有的特性的分析,在原有有界模型检验算法的基础上,提出了基于偏序约减技术的优化算法。实验证明,该优化算法能够大幅提高中断驱动系统模型检验的效率。本文的主要工作如下:1.实现了中断驱动系统的有界模型检方法。本文采用时间自动机+伪代码的建模方式对中断驱动系统建模,并将系统中的时间约束和系统规约编码为线性不等式组,调用SMT(Satisfiability Modulo Theories)求解器Z3求解。实践证明该方法能够应用于实际中断驱动系统的模型检验,并能有效检测出系统中的错误。2.提出了一套完整的、切实可行的基于偏序约减技术的优化方案。我们首先对模型的运行方式进行了重新定义,将中断的触发、响应与执行整合为一个事件,确定偏序关系的粒度。在进行验证前,首先通过静态分析,得到中断处理程序间的依赖关系。在状态遍历过程中,将多个同时满足触发条件的中断根据相互之间的依赖关系生成偏序路径,然后按照偏序路径执行到达新的状态。由于偏序路径排除了其它等价的路径,所以此优化算法能够消除冗余的遍历路径,达到约减状态空间的目的。3.将优化方案应用到模型检验工具中并进行了实例研究。实验结果表明,本文提出的优化算法能够有效约减状态空间、减少验证时间。而且,随着系统中中断数量的增加,优化算法的效果更加明显。

关键词：中断驱动系统有界模型检验偏序约减

来源：评论

学校读者我要写书评

暂无评论

基于有界模型检验的传感网软件验证方法研究

基于有界模型检验的传感网软件验证方法研究

引用

作者：岳书珍南京邮电大学

学位级别：硕士

传感网是一种由具有感知、处理和无线通信能力的传感器节点通过自组织方式形成的一种多跳网络。随着传感网的迅速发展，传感网软件的规模逐渐变大，这使得不同的应用领域对传感网软件的性能都有着越来越高的要求。软件验证技术是保证软... 详细信息

传感网是一种由具有感知、处理和无线通信能力的传感器节点通过自组织方式形成的一种多跳网络。随着传感网的迅速发展，传感网软件的规模逐渐变大，这使得不同的应用领域对传感网软件的性能都有着越来越高的要求。软件验证技术是保证软件性能的一项重要技术。模型检验是软件验证技术的一种，它为传感网软件验证提供了新的技术手段。在基于模型检验的软件验证领域中，状态空间爆炸问题是其发展的瓶颈。有界模型检验技术是模型检验领域新的研究方向，它通过限制建立模型时状态展开的次数来实现，主要用于缓解状态空间爆炸问题。本文主要对基于有界模型检验的传感网软件验证方法进行研究，该研究是面向源代码的，其实现主要分为两个工作： 1）提出一种基于有界模型检验的传感网软件代码验证方法。该方法首先通过对传感网软件建立软件模型，实现对传感网软件的静态结构和动态行为的抽象；然后定义模型转换规则，将软件模型转化C语言代码；最后使用CBMC对转化后的代码进行有界模型检验。 2）提出一种基于POR（偏序简约）的有界模型检验优化算法，该算法通过分段的方法来避免重复路径的搜索，较少状态遍历时间，

关键词：传感网软件验证状态空间爆炸有界模型检验 CBMC

来源：评论

学校读者我要写书评

暂无评论

基于可满足性问题解算器的有界模型检验——子句规则和冲突分析研究

基于可满足性问题解算器的有界模型检验——子句规则和冲突分析研...

引用

作者：尹文波复旦大学

学位级别：硕士

随着集成电路设计和制造技术的不断进步，电路的规模也在不断增大，电路验证和测试领域面临着前所未有的挑战。传统的基于模拟的验证方法不能满足电路复杂度增大的需要，具有完备性特点的形式化验证方法开始得到人们的关注，成为当前的... 详细信息

随着集成电路设计和制造技术的不断进步，电路的规模也在不断增大，电路验证和测试领域面临着前所未有的挑战。传统的基于模拟的验证方法不能满足电路复杂度增大的需要，具有完备性特点的形式化验证方法开始得到人们的关注，成为当前的研究热点。\n 本文研究工作是针对时序电路的有界模型检验进行展开的。由于近些年来，对可满足性问题(SAT)的研究取得了重大进展，有效的SAT解算器诸如zChaff、BerkMin和MiniSat等已经可以在一定时间内解决数十万变量规模的SAT问题，并且作为一个优秀的计算引擎在集成电路验证领域有着广泛的应用。本文分析了有界模型检验在子句规则和冲突分析上的优缺点，并提出了改进的方法，能够加速有界模型检验的执行。\n 本文主要的创新之处在于：(1)对重命名子旬规则进行了改进，引入了逻辑化简、处理多元运算、合并相邻结点等方法，减小了输入到SAT解算器的问题规模，有效的提高了有界模型检验的执行效率。(2)分析了有界模型检验问题冲突蕴涵图的特征，引入辅助学习子句的概念，根据蕴涵图的结构和形状生成辅助学习子句，阻止类似的冲突再次发生，有效的减少了蕴涵图的深度和冲突次数，提高有界模型检验的执行效率。对大量测试电路进行实验的结果表明了这些改进策略的有效性。

关键词：有界模型检验子句规则冲突分析集成电路设计时序电路 SAT解算器

来源：评论

学校读者我要写书评

暂无评论

有界模型检验综述

引用

电脑知识与技术（过刊） 2017年第12X期23卷 70-71页

作者：于露同济大学上海201800

无论是计算机系统硬件设计还是软件设计,随着设计规模越来越复杂和庞大,会产生越来越多的设计缺陷。传统检测方法代价高,并且难以检测这些设计缺陷。有界模型检验是一种重要的形式化验证方法,可以大大提高检测、验证的效率。作为一种形... 详细信息

无论是计算机系统硬件设计还是软件设计,随着设计规模越来越复杂和庞大,会产生越来越多的设计缺陷。传统检测方法代价高,并且难以检测这些设计缺陷。有界模型检验是一种重要的形式化验证方法,可以大大提高检测、验证的效率。作为一种形式化方法构造系统的模拟运行过程,有界模型检验通过把有限状态机和线性时序逻辑验证规范否定形式编码成布尔可满足性实例,再由各种布尔可满足性工具来求解,以获得反例。由于有界模型检验使用深度优先搜索,它可以很快找到路径最短的反例。

关键词：有界模型检验模型检验 SAT

来源：评论

学校读者我要写书评

暂无评论

基于有界模型检验的Web服务组合

基于有界模型检验的Web服务组合

引用

第一届全国服务计算学术会议

作者：方志廖乐健陈若愚北京理工大学计算机学院，北京市 100081

随着SOA在众多应用领域中得到认同以及可用的Web服务数量的快速增长，如何有效地组合Web服务来满足用户需求成为一个备受关注的问题。本文提出一种基于有界模型检验的Web服务组合方法．其中，Web服务被建模为有限状态自动机，众多Web服... 详细信息

随着SOA在众多应用领域中得到认同以及可用的Web服务数量的快速增长，如何有效地组合Web服务来满足用户需求成为一个备受关注的问题。本文提出一种基于有界模型检验的Web服务组合方法．其中，Web服务被建模为有限状态自动机，众多Web服务构成服务社区，Web服务组合需求由线性时态逻辑公式描述，通过有界模型检验器的系统化搜索，该方法能够从服务社区中自动地构建满足需求的Web服务组合．实验表明，该方法能够适应较大规模的Web服务组合场景．

关键词：有界模型检验 Web服务组合线性时态逻辑

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：