• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Discovering invariants in the analysis and verification of finite state transition systems.
【24h】

Discovering invariants in the analysis and verification of finite state transition systems.

机译：在有限状态转换系统的分析和验证中发现不变式。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Hardware and software systems are evolving at a fascinating speed, thanks to the refinements of semiconductor technologies. However, verifying their correctness becomes a daunting task because of the state explosion problem. Because simulation can only validate a modern design for a fairly small portion of functional coverage, formal methods become indispensable tools in certifying design correctness. Although significant progresses have been achieved in this area, the state of the art is still far behind what is required and there is plenty room for improvement. This thesis addresses some issues in formal analysis and verification of finite state transition systems.; Through identifying some invariants, we study four subjects in the analysis and verification of finite state transition systems. First, we establish the most general definition of combinationality in designs with cyclic definitions, which occur naturally in systems specified in high-level description languages due to resource sharing, module composition, etc. This is further extended to determine the sequential determinism of systems with state holding elements. Second, we study the transformation invariants under retiming and resynthesis operations, which are the most practical techniques in the optimization of synchronous hardware systems. We characterize the optimization power of these operations and demonstrate the verification complexity of checking retiming and resynthesis equivalence. We give the rectification of initialization sequences invalidated due to these transformations. Third, we revisit equivalence checking of two finite state transition systems, which is one of the most important problems in design verification. Demonstrated is how the verification task can be fulfilled with symbolic computations in the disjoint union state space, rather than in the traditional product state space, of the two systems. Finally, because abstraction is one of the most promising techniques to leverage the state explosion problem, we investigate a reachability-preserving abstraction technique based on functional dependency. By extending combinational to sequential dependency, the detection of functional dependency can be isolated from reachability analysis. Also, our computation can be integrated into reachability analysis as an on-the-fly reduction.
机译：得益于半导体技术的完善，硬件和软件系统的发展速度令人着迷。但是，由于状态爆炸问题，验证其正确性成为一项艰巨的任务。由于仿真只能验证功能覆盖范围很小的现代设计，因此形式化方法成为验证设计正确性必不可少的工具。尽管在该领域已取得了重大进展，但现有技术水平仍远远落后于要求的水平，并且仍有很大的改进空间。本文解决了有限状态转换系统形式化分析和验证中的一些问题。通过确定一些不变性，我们在有限状态转换系统的分析和验证中研究了四个主题。首先，我们在具有循环定义的设计中建立组合性的最一般定义，由于资源共享，模块组成等原因，这些定义自然出现在高级描述语言中指定的系统中。这进一步扩展为确定具有以下条件的系统的顺序确定性：国家控股元素。其次，我们研究了重定时和重新合成操作下的变换不变量，这是优化同步硬件系统中最实用的技术。我们表征了这些操作的优化能力，并演示了检查重定时和重新合成等效性的验证复杂性。我们给出由于这些转换而无效的初始化序列的校正。第三，我们重新研究两个有限状态转换系统的等效性检查，这是设计验证中最重要的问题之一。演示了如何在两个系统的不相交联合状态空间而不是传统乘积状态空间中通过符号计算来完成验证任务。最后，由于抽象是利用状态爆炸问题的最有前途的技术之一，因此我们研究了一种基于功能依赖关系的可保存性抽象技术。通过将组合依赖扩展到顺序依赖，可以将功能依赖的检测与可达性分析隔离。同样，我们的计算可以作为实时减少而集成到可达性分析中。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号