基于PAR 的排序算法自动生成研究

排序是计算机学科中的一类特殊问题,其算法设计策略的灵活性使得求解算法更具多样性.基于形式化方法PAR(partition-and-recur),研究了排序算法的自动生成问题.刻画了排序问题的代数性质,形式化构建了排序算法领域的泛型类型构件和算法构件,建立了排序领域特定语言和算法生成形式化模型,以参数替换的方式自动生成了一组排序算法,包括快速排序、堆排序、Shell排序等典型的已知算法以及增量选择排序等若干未见于现有文献的算法,并在程序生成系统中予以了实现.通过上层框架研究和底层构件支持,显著提高了特定领域算法的开发效率和可靠性.     

网构软件的资源自适应性的形式化分析与验证

针对基于构件的网构软件系统对环境资源变化的自适应性特征的可信分析与验证展开研究.具体工作包括:在网构软件的系统模型层次,使用带资源语义信息的接口自动机对软件构件的行为进行形式化建模,其包含了构件在完成特定功能的过程中对环境资源的使用特征;使用资源接口自动机网络来描述构件组装实体的组合行为;使用基于场景的UML顺序图模型来描述具有多功能的组合系统规约;分别研究了检验组合系统的所有行为是否都满足给定的资源约束以及检验指定的系统行为是否满足资源约束这两个具体问题:通过对资源自动机网络状态空间的分析,构造其相应的可达图,在此基础上给出了相应的检验资源可满足性、最小资源需求量以及检验指定功能合法性等算法.     

基于自动机的构件实时交互行为的形式化模型

采用形式化方法对复杂实时构件系统交互行为进行描述和验证,对于提高系统的正确性、可靠性等可信性质具有重要意义.分析了基于进程代数和自动机的构件交互行为形式化建模方法各自的优缺点,在此基础上提出了基于时间构件交互自动机的建模方法,给出了时间构件交互自动机的相关定义、组合和验证算法.时间构件交互自动机引入了时间限制、时间代价、时间代价计算半环、构件组合层次等概念,既能够描述构件交互情况,又能够清楚地表示出构件系统的体系结构信息和实时信息,便于对系统进行描述和验证.最后,结合具体应用给出了应用示例.     

Mediator的概率扩展

Mediator是一种基于组件的形式化建模语言,它提供了分层的模块化结构,从而可以方便地对复杂系统进行建模。它以自动机为其底层单位,自动机连接成的系统作为高级结构,能在对模型进行形式化描述的同时让其本身简单易用。为了使Mediator具有更强的表达能力,可对具有概率行为的系统进行形式化建模,对Mediator做了概率方面的扩展,并对扩展后的语言给出了基于马尔可夫决策过程的语义。同时还介绍了由Mediator模型自动生成PRISM代码的方法,能够使用PRISM工具对Mediator模型的相关性质进行验证。     

基于场景的联锁软件形式化模型生成方法

为保证列车运行安全和旅客生命财产安全,对车站联锁控制系统进行有效的分析、验证和测试是必不可少的,而形式化模型是联锁系统分析、验证和测试的基础.以计算机联锁软件的UML半形式化模型为基础,以事件确定有限自动机模型作为描述系统的形式化模型,研究UML2.0顺序图转换为事件确定有限自动机模型的方法.首先选取一组与交互行为相关的全局变量作为状态向量来分析和消解顺序图各个场景的消息以及不同场景间的同一消息的前后置状态向量值是否存在矛盾,从而得到一致性的需求场景;然后提取各对象的事件序列生成对应的事件确定有限自动机;最后通过组合系统中对象的自动机模型得到系统的事件确定有限自动机模型.该方法改善了安全苛求软件的设计与开发,为软件质量评估提供了技术支撑.     

基于SysML的复杂机电系统设计模型形式化扩展与验证

形式化系统验证是保证系统设计正确性的一种重要手段.如何针对复杂机电系统物理与软件相融合的特征,对系统设计的动态特征进行验证,是系统验证研究领域亟待解决的问题.针对这一问题,对系统工程标准建模语言SysML进行扩展,提出了一套形式化系统模型验证方法.首先,以计算树逻辑和基于流的功能表示为形式化基础,形成基于SysML的系统功能建模方法;然后,以混合自动机为基础,建立基于SysML的系统行为建模方法;最后,针对物理与软件子系统的不同动态特征,借助NuSMV模型校验器,以层次化方式实现系统模型的自动验证.以移动机器人系统为例,展示了复杂机电系统设计模型的自动验证过程.     

基于统计模型检测的Tc CBTC移动授权建模与分析

基于通信的列车运行控制(communication based train control, CBTC)系统采用车地通信方式使得地面设备极其复杂。随着通信技术的快速发展,以车载为核心的列车运行控制(train-centric communication based train control, TcCBTC)系统采用车车通信方式减少了控制信息的传递环节,将成为城市轨道交通领域的发展方向。移动授权(movementauthority,MA)是决定列车能否以安全间隔运行的直接因素,因此对MA生成过程进行形式化建模与分析,对避免列车碰撞具有重要意义。根据TcCBTC系统架构分析MA生成流程,确定参与功能实现的子系统,并计算出不确定性参数;通过UPPAAL-SMC建立对应的随机混成自动机网络模型;最后采用统计模型检测方法对模型进行定量分析。分析结果表明：置信度为99.95%的情况下,系统在300 ms内成功计算出MA的概率为0.997 412 474 8,为后续TcCBTC系统开发设计提供理论参考。     

面向汉语建模的自适应词表生成算法

词表的质量直接影响汉语语言模型的性能, 而当前汉语词典编撰工作同语言建模工作相脱离, 一方面使得现有的汉语语言模型受词表规模所限, 性能不能发挥到最优, 另一方面因为缺乏专业领域的词表, 难以建立面向特定领域的语言模型. 本文旨在通过建立优化词表的方式来提高现有汉语语言模型的性能, 并使其自动适应训练语料的领域. 本文首先将词表自动生成工作同汉语语言建模工作相结合, 构建一体化迭代算法框架, 在自动生成优化词表的同时能够获得高性能的汉语语言模型. 在该框架下, 本文提出汉字构词强度的概念来描述汉语的词法信息, 并将其作为词法特征与统计特征相结合, 构造一种基于多特征的汉语词表自动生成算法. 最后, 本文提出两种启发式方法, 自动根据训练语料的特点调整系统中的各项参数, 使系统能够自动适应训练语料的领域. 实验表明, 本文的方法能够在生成高质量词表的同时获得高性能的语言模型, 并且能够有效自动适应训练语料的领域.     

构件式实时系统建模与验证研究

在复杂的实时系统开发中使用构件式设计方法已成为目前软件开发领域中的研究热点,如何有效地验证实时软件的设计是否满足给定的时间需求并降低验证过程的复杂度,是实时计算领域中的主要挑战之一.文中对构件接口模型进行时间扩展,提出了时间接口模型,并将其用于构件接口交互行为的形式化建模.在接口自动机理论的的基础上进一步提出了时间接口自动机模型用于描述时间接口交互下构件的行为及组合方法,通过消除错误状态产生组合模型来约减构件时间接口自动机模型的积,并在约减的模型上进行性质检验,降低了分析复杂度,有效地应对状态空间爆炸问题.为了说明论文建议的方法,详细讨论了一个简单的、贯穿整篇论文的示例系统.     

基于梯形逻辑的联锁系统形式化验证方法

铁路联锁系统设计通常采用梯形逻辑进行建模。为了实现对铁路联锁系统进行形式化验证的目的,根据梯形逻辑的状态变迁语义,将梯形逻辑表示的联锁系统模型转换成模型检测工具NuSMV的语言,并将铁路联锁系统的安全需求表示为计算树逻辑(CTL),最后实现基于NuSMV的铁路联锁系统设计模型的形式化验证。     

基于场景分析的系统形式化模型生成方法

采用形式化方法对系统的安全性进行分析与验证,是构造可靠安全软件系统的一个重要途径。当前的形式化安全分析方法,面临着系统的形式化建模难的问题。以铁路车站联锁系统中基本进路建立为例,提出基于场景分析的系统形式化模型生成方法。该方法首先采用OCL前/后置条件分析法对UML时序场景作一致性分析,然后将UML时序图中对象交互的行为序列转换成FSP进程代数模型,进而得到系统的形式化模型。该方法为系统的形式化建模提供了新思路,从安全质量方面改善了安全苛求软件的设计与开发,丰厚了基于模型的软件形式化开发方法。     

联锁软件的统一建模语言和Petri网建模

使用统一建模语言(unified modeling language,UML)为联锁软件建立平台无关的模型(platform independent model．PIM),可以实现在异种平台间的移植和复用,并有助于自动生成测试案例和测试脚本。UML建模包括静态结构分析和动态行为分析。Petri网可对联锁软件与安全性相关的动态行为精确和严格地进行形式化描述。     

基于MTRDL的自动飞行系统模式需求建模与验证方法[1]

在民机自动飞行过程中,自动飞行系统模式转换是影响安全的重要因素,随着现代民机机载系统的功能与复杂度的快速增长,在需求阶段对自动飞行系统模式转换的安全性分析和验证成为重要的挑战.飞行模式转换的复杂性不仅体现在自动飞行过程中必需的多重飞行模式之间的交互关系,还体现在模式转换与外部环境之间复杂的数据与控制交联关系,这些交联关系同时隐含了飞行模式转换的安全性质,这些特征提高了形式化方法的应用难度.本文工作提出一种领域特定的建模验证框架:首先,提出面向自动飞行系统模式转换的领域需求建模语言MTRDL,和基于该语言扩展于SysML上的建模方法;其次,提出基于安全需求模板的安全性质辅助规约方法;最后,通过对某机型的若干条目化需求的实例研究,证明了本文方法在自动飞行系统模式转换需求验证中的有效性.     

一种可定制参考过程模型的自动构建方法

过程模型在企事业单位中的应用日益普遍.由于企业为每个特定业务需求单独开发过程模型是复杂并且高成本的工作,因此企业通常使用参考过程模型作为过程模型开发的基础,以有效降低成本并提高开发效率和质量.由于参考模型需要领域专家大量的领域分析和抽象建模工作,如何基于领域内已有的过程模型变体自动创建出初步的参考模型以辅助领域专家的工作成为有意义的研究问题.现有的参考模型构建方法存在输出模型复杂度较高或难以全面表达领域内多样推荐实践等问题.为了创建代表性和可读性更强的参考模型,基于相似过程片段聚合技术,提出了一种支持层次化子过程结构的可定制参考过程模型的自动构建方法,全面支持可定制参考模型中基础过程、变更可选项以及约束关系的自动构建.案例研究结果表明:该方法生成的参考模型具有良好的领域代表性和模型复杂度.     

基于MBSE的鱼雷全电子安全系统安全性与任务可靠性分析

随着武器装备研究的深入推进,传统方法难以满足复杂系统安全性与可靠性分析的需求。为提升系统研发与评估效率,以形式化的系统建模语言分析鱼雷全电子安全系统的安全性、可靠性成为必然趋势。本文在传统安全性与可靠性分析的基础上,基于系统工程开展安全系统建模过程,以功能需求、系统架构、活动视图以及时序逻辑控制作为安全性与作用可靠性分析的构成元素,对系统功能模型进行故障传播建模;最后以安全建模语言构建事故树模型得出安全性与可靠性的影响因素,为引信系统的安全性与可靠性分析工作提供一定参考价值。     

Formal Modeling and Verification of Safety-Critical Software

Rigorous quality demonstration is important when developing safety-critical software such as a reactor protection system (RPS) for a nuclear power plant. Although using formal methods such as formal modeling and verification is strongly recommended, domain experts often reject formal methods for four reasons: there are too many candidate techniques, the notations appear complex, the tools often work only in isolation, and output is often too difficult for domain experts to understand. A formal-methods-based process that supports development, verification and validation, and safety analysis can help domain experts overcome these obstacles. Nuclear engineers can also use CASE tools to apply formal methods without having to know details of the underlying formalism. The authors spent more than seven years working with nuclear engineers in developing RPS software and applying formal methods. The engineers and regulatory personnel found the process effective and easy to apply with the integrated tool support.     

基于项重写系统的联锁系统模型检测方法研究

模型检测方法对安全苛求系统建模的完整性需要一套严谨的方法论与技术,对于验证系统的正确性,具有传统方法无法比拟的优势。提出利用项重写系统建立安全苛求系统模型与验证方法,采用基于项重写系统原理的Maude工具语言,对铁路联锁系统的站场进行形式化建模,通过其语法和语义定义各类约束和离散事件,构架联锁系统属性和行为。在模型建立的基础上,对联锁站场的静态属性和安全属性进行形式化模型验证。结果表明,基于项重写系统的模型检测方法可以较好地应用于实际联锁系统软件的开发,对开发安全苛求系统和模型检测方法的实际应用提供借鉴。