一、非确定并发系统的基于说明的测试推导（论文文献综述）
吴成伟[1]（2021）在《基于大数据的道路交通拥堵预测研究》文中指出交通强国的建设有利于居民出行以及促进社会经济繁荣发展。基于人工智能算法的未来城市交通道路拥堵预测,可以帮助交通决策部门提前进行交通流规划,避免交通拥堵的发生;基于大数据技术的实时城市道路拥堵情况统计,能够动态反映当前交通流拥堵的规律,便于采取增设潮汐车道等措施疏堵,同时能够及时响应因临时修路、交通事故等潜在突发情况造成的交通拥堵。这些对道路交通拥堵预测具有重要的现实意义。本文主要研究未来城市道路拥堵预测和城市道路实时统计,根据梯度提升算法进行未来道路旅行时间预测、基于实时数据流利用大数据实时计算引擎进行城市道路预测统计,来解决道路交通拥堵。本文主要工作如下:1)针对未来旅行时间预测的自回归问题,提出了多种算法融合的缺失值插补处理方法以及基于特征影响力的特征构建的XGBoost时间序列预测算法,该算法动态分裂计算残差,寻找最大增益提高算法精度,融合预训练模拟、线性回归、中位数拟合等来优化缺失值处理过程,进行分权重的特征提取,使用贝叶斯优化、交叉验证进行参数优化设计,避免了过拟合,降低模型复杂度,提高了模型的稳定性。实验结果表明,该算法能够快速收敛,达到训练时间短、泛化能力强的目的,对于未来旅行时间预测的自回归问题,预测效果良好。2)针对实时城市海量车辆分布去重问题,提出了动态扩容的多重位分配海量数据去重算法。该算法接收整个城市各道路区域的车辆信息,经过多重分配将海量车辆数据均匀分配到N维矩阵中,来实时确认车辆所处道路区域,经过累加,得到各道路区域车流密度,并利用位图实现动态扩容。实验结果表明,该算法在允许极低误差的前提下,能够解决海量车辆数据分布去重问题。3)针对导致道路拥堵问题原因分析,设计并实现了基于Flink的多维度实时城市交通拥堵预测统计模型。该模型抽象出三个维度,根据城市每条道路上实时车辆数据信息,经kafka消费,利用非确定有限状态自动机来自定义复杂事件,模式匹配超速车辆,输出危险驾驶车辆信息并报警,避免因交通事故造成的交通拥堵;利用窗口函数计算,得到城市道路的拥堵情况;并为了实时统计整个城市中所有路段最拥堵的道路,引入自定义TopN函数。同时解决了由于网络延迟等问题导致的交通事件时间乱序问题。实验结果表明,利用水位线能够最大限度的解决事件时间乱序问题,反馈真实的道路交通情况;同样Flink能够在兼顾实时性和吞吐量的前提下,完成城市车辆超速驾驶引发交通事故造成的交通拥堵以及最拥堵道路统计的问题。
向霜晴[2]（2020）在《软件定义网络的形式化建模与验证》文中研究表明软件定义网络（Software-Defined Networking,SDN）是一种新兴的网络架构,能够解决传统网络层级复杂,以至难以管理和创新的问题。该架构将控制逻辑从转发设备上分离出来,形成逻辑上集中的中心控制器,并提供网络可编程性。SDN的出现不仅推动了网络架构的更迭,更带来了网络开发方法的变革,可以预见在未来的网络开发流程之中,形式化方法必定处于极其重要的地位。本文通过形式化方法建模SDN并验证相关性质。对于与数据转发逻辑有关的性质,扩展了知名的软件定义网络编程语言NetKAT,提出了能描述虚拟局域网（VLAN）、拥有更强表达能力并且支持模型检测的语言PDNet,研究了PDNet的操作语义,并基于操作语义证明了PDNet和NetKAT在表达能力上的联系与差别。对于与SDN模块或应用的设计、功能和安全有关的性质,基于图灵奖得主C.A.R.Hoare教授提出的通信顺序进程（CSP）设计了系统建模框架,并在模型检测工具PAT（Process Analysis Toolkit）中进行了实现。基于该框架,本文建模并验证了开源控制器Floodlight的基础模块以及安全控制器TopoGuard的防御策略,以展示该框架的使用方法和实际价值。本文的主要内容和贡献包括以下三点:·提出了基于克莱尼代数（KA）的网络编程语言PDNet,来刻画数据层的转发逻辑。该语言对高级网络编程语言NetKAT（由康奈尔大学等研究机构提出）进行了扩展,从而能描述SDN的重要应用场景VLAN。同时,本文基于下推系统研究了PDNet的操作语义,并定义了语法导出规则。此外本文基于操作语义证明了PDNet的表达能力强于NetKAT。·总结归类了SDN三层架构以及外部环境中的软硬件设备,分析了各类对象在模型中的行为,提出了基于CSP的SDN系统建模框架。同时,本文建立了可实例化的数据层模型和四类主机模型,并为九种可能的攻击提供了建模方案,此外,为两种已知的,危害范围极广的攻击建立了攻击者模型。·基于系统建模框架,建模验证了开源控制器Floodlight的六个基本模块和安全控制器TopoGuard的攻击防御机制。对于Floodlight,我们验证了其基本模块的设计、功能与安全相关的性质。验证结果显示其拓扑发现和设备管理模块会受到链路攻击和主机攻击的危害,因此一大批与Floodlight使用类似的拓扑发现和设备管理方案的开源控制器都被这两种攻击影响。基于此,本文验证了为防御这两种攻击而设计的安全控制器TopoGuard,发现了两个严重问题,并提出了解决方案。
杨凯[3]（2019）在《基于MSVL的动静结合程序验证和自动规划》文中研究指明作为一种规范语言,时序逻辑已经被广泛用于计算机程序、数字电路和通信协议的验证以及人工智能的时序推理中。此外,时序逻辑也被用作程序设计语言来编写程序。一个时序逻辑程序设计语言编写的程序称作是一个时序逻辑程序,其本质上是一个时序逻辑公式。跟传统的非形式化编程语言（如Pascal,C等）不同,时序逻辑程序的执行过程是根据给定的规则对公式进行化简的过程。通常时序逻辑程序的执行过程更加复杂,执行效率已经成为影响时序逻辑程序能否应用于实际大型复杂系统的一个关键因素。为此,本文以建模、仿真和验证语言MSVL（Modeling,Simulation and Verification Language）为研究对象,提出了一种MSVL程序的编译执行方法并实现了一个MSVL编译器。在此基础上,研究了基于MSVL和MSVL编译器的C程序验证方法以及自动规划方法。此外,为了支持对C程序的时序性质验证,研究了时序性质自动挖掘方法从程序中挖掘PPTL（Propositional Projection Temporal Logic）性质。本文主要工作概括如下:第一,为了高效执行MSVL程序,提出了一种MSVL程序的编译执行方法并基于该方法实现了一个MSVL语言的编译器,包括词法和语法分析、预处理、语义分析、中间代码生成以及运行时系统实现等。其中针对MSVL中的时序操作符的预处理和并发语句的运行时系统实现是MSVL编译器实现的重点。MSVL编译器可以将一个形式良好的MSVL程序编译为平台对应的可执行码,从而对其进行执行。实验结果表明,对于大型复杂的MSVL程序,编译器的效率要明显高于现有的解释器的效率。基于MSVL编译器,我们实现了对MSVL程序的仿真、建模和验证。最重要的是,编译器的实现为其它工作,例如MSVL的高效运行时验证和MSVL统一动态验证等提供了坚实的基础,反过来,这些工作又为本文中的C程序验证方法提供了基础。第二,提出了一种基于MSVL的动静结合方法来验证C程序的时序性质。该方法采用具有完全正则表达能力的PPTL公式描述期望的性质,从而可以验证一些现有的工具无法验证的性质。此外,在静态分析阶段采用了抽象技术,可以在一定程度上缓解验证过程中的状态空间爆炸问题。最后也是很重要的一点,因为采用了静态的方法查找可能的反例,因此不会产生假阴性（漏报）,又因为采用了动态的方法检查虚假反例,因此也不会产生假阳性（误报）。我们基于该方法实现了一个工具SDMC并做实验和现有的相关工具进行了对比。实验结果表明,SDMC在验证一些简单的安全性和活性性质时,比现有的工具效率更高,且可以应用于实际大规模程序的验证,同时SDMC可以验证区间相关和周期重复的性质。第三,性质获取是目前程序验证领域面临的一个难题。为了支持对C程序的性质验证,本文提出了一种动态性质挖掘方法从C程序中自动挖掘时序性质。和现有方法不同的是,该方法采用具有完全正则表达能力的PPTL公式作为性质描述语言,因此可以支持更加复杂的性质,如区间相关性质和周期重复性质。此外,该方法采用了不变式探索工具Daikon挖掘程序中的不变式,因此可以支持挖掘数据相关的时序性质。由于该方法从程序的执行轨迹中挖掘时序性质,而不依赖源程序,因此可以用于其它语言（如JAVA,C++等）程序的性质挖掘。理论上该方法可以挖掘任意长度和复杂度的PPTL性质。为了提高挖掘效率,提出了一种分布式并行性质挖掘方法。第四,将MSVL应用于自动规划领域,提出了一种基于MSVL程序的自动规划方法。该方法同时用MSVL程序描述规划问题和搜索控制知识（Search Control Knowledge,简称SCK）,并可以通过对程序编译执行的方式进行规划求解。为了方便用MSVL程序对规划问题进行描述,实现了一种从标准规划域描述语言（Planning Domain Description Language,简称PDDL）到MSVL程序的自动转换方法。我们选取国际规划竞赛中具有代表性的标准规划问题进行了实验,实验表明,在一些依赖SCK的规划问题中,基于MSVL的自动规划方法比现有的大多数规划器所采用的方法效率更高。
于斌[4]（2019）在《MSVL程序的高效运行时验证方法研究》文中研究表明建模仿真验证语言（Modeling,Simulation and Verification Language,简称MSVL）是一种时序逻辑程序设计语言,是投影时序逻辑（Projection Temporal Logic,简称PTL）的可执行子集,其包含丰富的数据结构、函数调用以及同步和异步通信机制,已成功应用于并发系统、反应式系统和嵌入式实时系统的模型描述、路径仿真和形式化验证。作为PTL的命题形式,命题投影时序逻辑（Propositional PTL,简称PPTL）具有完全正则表达能力,能够方便地对顺序、并行、区间相关和周期重复的性质进行描述。基于统一的PTL逻辑框架,现有的方法已经实现了对MSVL程序的运行时验证,用于检测程序的动态执行轨迹是否满足期望的PPTL性质。然而,目前的验证方法存在一些不足:首先,针对单条执行路径的时序逻辑性质验证,没有充分利用当前已经广泛普及的多核设备和分布式网络,导致验证效率不高;其次,针对程序执行中分配的内存区域,没有进行动态追踪,使得程序中存在的内存泄漏问题无法被及时发现;最后,针对含有分支路径的时序逻辑性质验证,不能保证发现的反例是所有路径中最短的,导致验证过程需要探索更多的状态空间。为了解决以上问题,本文围绕MSVL程序的高效运行时验证展开,主要工作概括如下:首先,提出了基于单机多核系统的MSVL程序并行运行时验证方法。该方法将程序执行生成的状态序列分为若干个被同时验证的片段,每个片段由一个线程池负责,线程池中的多个线程同时对一个片段进行验证,当一定数目的片段被验证后,这些片段的验证结果会被及时汇总以检测能否得到最终的验证结果。基于LLVM平台,开发了验证器PPTLCheck,实验结果表明相较于目前的验证工具,PPTLCheck的验证效率更高,并适用于大规模程序的完全正则性质的验证。作为验证实例,研究了多线程程序中多个子线程是否正确交替执行的验证问题,在对问题进行建模和性质描述后,使用PPTLCheck工具对多线程程序的动态执行进行验证。然后,提出了基于分布式网络的MSVL程序并行运行时验证方法。该方法利用分布式网络中性能各异的多核机器对程序执行产生的状态序列片段同时进行验证,在每台机器中,一个片段进而又被分为若干个能够被并行验证的子片段。为了多台机器高效合作,建立了用于消息传递的通信机制和任务分配的调度机制,并给出了一种自适应算法以自动调节不同机器中验证线程的数量。开发了基于局域网的PPTLCheck+工具,实验结果表明,PPTLCheck+比PPTLCheck具有更高的验证效率。作为验证实例,研究了SQLite3数据库提供的API在调用过程中是否符合规范的验证问题,为此,开发了SQLite3Check工具,其通过分析网页上描述的API调用规范,得到相应的PPTL公式描述后,使用PPTLCheck+对调用SQLite3数据库API的程序进行检测。进而,提出了针对MSVL程序内存泄漏的运行时检测方法。该方法采用动态符号执行技术尽可能多地运行程序的不同路径,在每条路径的执行过程中,后端检测器跟踪每个被访问的动态分配的内存块,计算指向每个内存块的指针数量,判断其是否发生泄露,并记录内存泄露位置和指向每个泄露内存块的变量变化情况,在程序执行后,将相应的内存释放语句添加到代码合适位置。基于KLEE工具和MSVL编译器,开发了DEF LEAK工具,实验结果表明,DEF LEAK能够发现更多的内存泄露,并更有效地帮助开发人员理解泄露发生的原因以安全修复内存泄露。最后,提出了含有非确定选择语句的MSVL程序的统一限界运行时验证方法。该方法基于MSVL的统一运行时验证方法和PPTL限界语义,构造深度递增的有界带标记的范式图（Bounded Labeled Normal Form Graph,简称BLNFG）,以发现所有分支上违反性质的最短前缀,在资源有限或者不要求整个路径满足性质的情况下,该方法可用于说明在一定的搜索深度内,程序中不存在反例路径。以经典的互斥问题、哲学家就餐问题和银行家算法为案例,说明了所提验证方法对实际问题的有效性。
于恒彪[5]（2018）在《符号化验证关键技术研究》文中进行了进一步梳理随着软件规模和复杂度的不断提高,软件缺陷问题不断出现。如何提高软件的可靠性已经成为软件工程领域的一个重要研究问题。程序验证技术被广泛应用于提高软件可靠性。当前的程序验证技术主要分为静态验证和动态验证两类。静态验证对程序进行抽象建模,然后验证模型是否满足给定性质,能够确保程序的覆盖率,但是受限于分析误报、自动化程度低或可扩展性差等问题。动态验证实际执行程序,基于程序的运行时信息来检查程序的正确性,能够确保分析的精确性,但是会漏掉输入相关的错误。基于符号执行的程序验证能在静态验证和动态验证之间取得平衡:能够比静态验证获取更高的程序抽象精度,与动态验证相比又能够确保输入空间的覆盖。然而,由于程序路径数目与分支语个数成指数增长,路径空间爆炸问题成为制约符号执行的瓶颈。在分析并行程序时,由于程序执行的并行性,该问题变得更加严重。如何提高基于符号执行的程序验证的可扩展性是一个挑战性问题。本文的主要贡献涵盖以下三个方面:1.在软件工程领域,正规性质被广泛应用于性质规约。本文提出了符号化验证技术SRV来高效地验证串行程序是否满足给定正规性质。SRV将面向正规性质的路径切片与正规性质引导的动态符号执行有机结合起来:（1）本文提出了一种面向正规性质的路径切片技术来裁剪冗余路径;（2）SRV使用正规性质引导的动态符号执行技术来更快找到违背正规性质的反例路径。本文实现了SRV并将其应用于实际Java程序（总计25.9万行代码）的正规性质验证。相比动态符号执行、正规性质引导的动态符号执行和结合路径切片的动态符号执行,SRV能够获取平均至少8.4倍、8.6倍和7倍的验证加速比。2.消息传递接口（Message Passing Interface,MPI）是高性能计算领域并行编程的标准范式。由于MPI程序的复杂性,例如非确定性和异步性,MPI程序很容易出错。本文提出了一种面向非消息通信依赖MPI程序的符号化验证技术MPI-SV,能够对包含非阻塞和非确定性通信操作的MPI程序进行自动化验证。MPI-SV将符号执行与模型检验有机结合起来:符号执行自动地为模型检验抽取路径层面的通信模型;模型检验可以有效裁剪符号执行的路径空间,并扩大符号执行能够验证的性质范围。本文实现了MPI-SV,并将其应用到实际MPI C程序（总计4.7万行代码）的死锁和时序安全性质验证。实验结果展示了MPI-SV的有效性:（1）对于102个死锁验证任务,MPI-SV在1个小时内能够验证完成90个,而单纯符号执行只验证完成52个;（2）在遍历完程序路径空间和找到死锁方面,MPI-SV相比单纯符号执行能够分别获取平均7.6倍和4.96倍的验证加速比;（3）在验证时序安全性质时,MPI-SV能够成功找到违背性质的反例,而单纯符号执行则不能够发现反例。3.为提高MPI程序性能,基于Master-Slave模式的动态调度策略在MPI编程中被广泛用来实现并行工作进程的负载均衡。动态调度MPI程序由于高度的不确定性导致其可靠性难以保证。本文提出了一种面向Master-Slave模式的符号化验证方法。具体来说,本文扩展了之前的MPI-SV来支持对Master-Slave模式的验证:（1）能够在MPI程序符号执行的过程中自动识别Master-Slave模式;（2）能够对Master-Slave模式的动态调度特征进行建模,使得路径模型能够精确表示给定输入下所有可能的调度策略。本文实现了面向Master-Slave模式的符号化验证方法,并将其应用到实际动态调度MPI程序（总计1.39万行代码）的死锁验证。实验结果显示我们的符号化验证方法能够比单纯符号执行获取平均21.24倍的验证加速比。
李慧勇[6]（2015）在《基于时空约束的车联网事件监控方法与技术研究》文中研究指明随着物联网技术和信息物理融合系统相关理论的发展,车联网系统（Internet of Vehicles）已经成为物联网理论和智能交通系统的重要研究领域,而其中事件实时处理是具有挑战性的研究对象。本文提出了基于车联网理论和事件驱动体系结构以及时空约束的车联网事件监控关键方法和技术,并对相关问题进行了深入细致的研究,主要贡献如下：首先,针对车联网中时空事件的表达和处理问题,提出了车联网的具有时空约束的事件处理语言STEP,建立了STEP语言的形式化语义——操作语义和指称语义,并建立了它们的一致性。其次,针对车联网中时空事件流的处理问题,基于STEP语言提出了车联网时空事件流Petri网处理模型,并给出了相应的事件流处理算法。研究结果表明该模型具有结构有界性和结构守恒性,并且基于该Petri网模型的事件处理算法具有稳定的动态性能,最后,通过仿真工具验证了相关推理的正确性。另外,针对车联网中大规模时空事件流的分布式处理任务,提出了车联网多维QoS改进HEFT调度算法。然后,针对公交车系统中常见的超速监控和未按时到站监控问题,提出了基于STeC/STEP的公交车动态监控策略,并设计和实现了基于该监控策略的公交车动态监控原型系统。使用北京市公交1路为应用场景和数据背景,构造了相关的仿真数据,通过仿真实验,验证了所提出的基于STeC/STEP的公交车动态监控策略的合理性和有效性。最后,针对车联网中非确定时空事件的表达和处理问题,提出了车联网中非确定时空事件的处理语言PSTEP,并建立了该语言的操作语义和指称语义。同时,基于车联网中非确定时空事件可靠度,提出了非确定时空事件流的可靠区间和可靠比的概念,从而方便了用户使用PSTEP语言。
邓辉[7]（2014）在《基于符号与数值混合计算的多项式变迁系统近似互模拟》文中指出计算机飞速发展,促使用户需求单个程序实现更多功能,导致程序行为及结构复杂化,不利于程序设计及性质验证工作。因此,程序行为及结构优化亟待研究及实现。程序行为及结构优化过程中,创建合理的程序形式化刻画系统是研究程序行为及结构的前提。早期的程序形式化刻画系统大都离散化,由抽象的动作、离散的状态及状态间的转移关系构成,可对程序进行基于状态遍历的计算和推理。遗憾的是,它们无法对程序行为即数据流交换过程进行表示和处理。从形式化的角度出发,数据流交换过程可用多项式系统表示的程序是最基础的一类。在了解程序具体行为及整体结构后,定义及判定程序行为等价是实现行为及结构优化的根本。具有相同行为的程序称为等价。基于最精确的系统等价关系互模拟实现程序等价判定,一方面去掉程序中重复的非确定性分支可实现结构优化,另一方面利用行为简单的分支代替行为复杂的分支可实现行为优化。但是,在大部分程序实际应用中,精确的等价关系显得太过严格,适当的近似不会对程序最终结果产生很大影响。为加强程序间关系的灵活性,可在误差范围内放宽等价限制,提出程序近似互模拟概念,并利用数值计算方法创建带误差且误差可控的近似互模拟计算方法,最终实现程序行为及结构近似优化。立足以上需求,本文围绕程序行为及结构优化这一主旨展开研究。针对数据流交换过程可以用多项式系统表示的程序,根据行为特征将之细分为三类,然后分别建立可描述其数据流交换过程的形式化刻画系统,并利用符号与数值混合计算创建程序互模拟及近似互模拟计算方法,其主要贡献包括：（1）构建了程序数据流交换过程划分规则。针对数据流交换过程可用齐次线性多项式系统描述的一类程序,构建了数据流交换过程与齐次线性多项式系统间转换规则。研究得到齐次线性多项式变迁系统,用于描述此类程序数据流交换过程及结构。提出了程序精确行为等价概念,称之为互模拟。基于齐次线性多项式系统系数矩阵的性质,给出了程序互模拟等价计算方法。同时,在给定的变量取值及误差范围内,建立了带误差且误差可控的近似互模拟定义及计算方法,通过矩阵范数实现了近似过程中实际误差的度量。对于实际误差大于给定误差但不大于两倍的给定误差的程序,通过奇异值分解实现了近似程序的求解。实验证明近似互模拟可实现一类程序行为及结构优化。（2）针对数据流交换过程可用非齐次线性多项式系统描述的一类程序,构建了数据流交换过程与非齐次线性多项式系统间转换规则。研究得到非齐次线性多项式变迁系统,用于描述此类程序数据流交换过程及结构。基于互模拟等价及非齐次线性多项式系统增广矩阵的性质,实现了此类程序互模拟等价判定。在非齐次线性多项式系统中,由于常数项的引入,使得针对齐次线性多项式系统建立的近似方法无法得以沿用。为此,在扩大的变量取值范围及给定误差范围内,为此类程序建立了带误差且误差可控的近似互模拟计算方法,通过矩阵范数实现了实际误差的度量。对于实际误差大于给定误差但不大于两倍给定误差的程序,基于QR分解实现了近似程序的求解。实验表明近似互模拟在优化此类程序行为及结构中可行及有效,且近似程序求解过程比齐次线性多项式变迁系统中相应过程节省时间和空间。（3）针对数据流交换过程可用非线性多项式系统描述的一类程序,构建了数据流交换过程与非线性多项式系统间转换规则。研究了非线性多项式变迁系统,用于描述此类程序数据流交换过程及结构。针对线性多项式变迁系统互模拟判定方法无法沿用的问题,基于吴特征列和Groebner基方法实现非线性多项式变迁系统互模拟等价判定,对比分析发现吴特征列方法更优。同时,针对线性多项式变迁系统近似互模拟均需约束变量取值范围的问题,通过对非线性多项式变迁系统近似关系的分析,在无需给定变量取值范围的前提下,在给定误差范围内建立了带误差且误差可控的近似互模拟概念及计算方法。在此过程中近似关系被描述为一个全局最优化问题,称为Max函数,通过填充函数法处理此函数,实现实际误差度量。对于实际误差大于给定误差但不大于两倍的给定误差的程序,通过近似调整非线性多项式系统对应特征列系统中的初式集合,得到了求解近似程序的方法构想。实验表明近似互模拟计算方法实现了程序行为及结构优化,且非线性多项式变迁系统的描述规则及近似互模拟计算方法对于本文所研究的所有类型程序均通用。综上所述,本文以程序行为及结构优化为目标,对可描述程序数据流交换的形式化刻画系统、程序互模拟等价及近似互模拟进行了研究,针对数据流交换过程可用多项式系统表示的程序建立了比较完整的等价及近似理论,为程序行为及结构优化提供了一种形式化的解决思路。
黄滟鸿[8]（2014）在《面向实时嵌入式系统的中断语义理论研究》文中认为随着计算机的发展,实时嵌入式系统被广泛应用于各个行业。相较于通用计算系统,嵌入式系统对安全性、可靠性、实时性以及稳定性都提出了更高的要求。它不仅要求系统实现逻辑正确,而且要求任务运行时可满足相应的时间限制。在实时嵌入式系统中,为了让系统可以及时地与外界环境进行交互,人们引入了“中断机制”。中断机制作为系统与外部设备连接的桥梁,使得系统可以随环境的变化而动态地、实时地做出相应的响应。然而,中断产生的随机性与不确定性却为系统埋下了内存安全和时间安全等方面的隐患。近年来,众多学者从不同的角度、采用不同的方法对中断进行了研究,其目的就是为了在保证中断机制正常运行的同时,提高此类系统的安全性指标。本文以实时嵌入式系统中的中断机制为研究对象,在程序统一理论的指导下,提出可描述实时嵌入式系统的中断行为的抽象建模语言。该语言引入了时间、概率等信息,通过刻画程序的行为研究中断给程序行为、系统表现带来的时间安全问题。该语言中引进的概率程序算子结合了多种概率模型,不仅能更细致、准确地刻画中断环境的不确定性,也可以帮助系统设计者、开发者加深对中断的了解,减少中断对此类系统带来的安全隐患,显着提高此类系统的安全性。本文将提出的研究方法应用于汽车电子领域,结合基于AUTOSAR OS规范的操作系统与汽车发动机管理系统应用案例,验证了该研究方法的可行性与有效性。本文的研究方法有效地提高了系统设计、实现以及测试过程的工作效率,对实时嵌入式系统的开发起了重要的辅助作用。本文的主要内容与贡献包括：一、本文提出了三种用以描述实时嵌入式系统的中断机制的形式化语言：中断建模语言IML、带卫兵的中断建模语言gIML以及带概率的中断建模语言pIML；三种语言的依次提出展示了本文对中断的研究过程。gIML是IML的扩展,pIML是gIML的扩展；三种语言可用于研究不同抽象层次的中断机制。它们不仅包括了常见的程序,如带时间的赋值程序、串行组合程序,而且包括关于中断特征的程序,如解除屏蔽程序、屏蔽中断程序、概率打断程序。pIML中引入的概率信息,使得我们不仅能对中断行为进行定性分析,还能对中断行为进行更为准确、精致的定量分析。二、本文给出了三种中断建模语言的两种语义模型：操作语义和指称语义。操作语义的迁移规则直观地模拟了程序是如何运行的。而指称语义从更为抽象的层次利用数学论域中的对象来描述程序的行为。两种语义都包涵了时间、概率信息,分析与讨论了系统在中断环境下的时间安全问题。本文在操作语义框架下通过互仿真定义了程序的等价性,并推导出一些关于中断的代数规则。同时,这些代数规则也在指称语义的框架下得到了证明。本文还研究了操作语义与指称语义的一致性问题。三、本文提出了带概率的中断建模语言pIML的应用。pIML包含了时间、概率信息,从定量的角度清晰地展示了中断发生对程序运行造成的影响。本文利用工具Maude仿真了pIML的概率操作语义,仿真结果可以协助程序员观察与分析程序运行的状况。pIML的概率指称语义也可以直接用于计算程序在中断影响下的运行时间与对应概率。本文提出可以引入概率分布函数来模拟实际应用场景的中断环境,从而对程序行为进行定量分析,帮助程序员预测系统的表现。本文还以基于AUTOSAR OS规范实现的操作系统与汽车发动机管理系统为例,通过pIM（?）L描述的程序来展示中断的准时发生对实时系统的重要性。
赵也非[9]（2010）在《动态UML子图的形式语义研究》文中指出通用建模语言（UML, Unified Modeling Language）,是一种功能强大的、可视化面向对象建模语言,它提供了多种UML子图,可以刻画系统的不同侧面,包括静态拓扑结构、动态行为、组装方式等。经过几十年的发展,在系统建模领域,设计开发人员普遍采用UML建立系统模型,现在UML已经成为事实的工业标准。UML存在于软件生命周期的各个阶段：需求、设计、分析、实现、测试、发布、维护等。对一些安全关键系统,如网络协议、轨道交通控制系统、嵌入式实时并发系统等,在需求、设计阶段前期,要求保证系统模型的关键功能性属性,和推导量化的非功能属性。设计开发人员通常采用UML建模复杂系统,但是,UML是一种半形式化的元模型,不具备精确的形式语义,不能对关键系统属性进行自动推理。如果能给UML赋予形式化语义,就能在模型检测器的支持下,对关键系统属性,自动进行功能验证和性能分析。静态UML子图用于刻画系统的拓扑结构,动态UML子图用于刻画系统行为,设计开发人员,通常更关注系统运行时（run-time）特性。本文的研究工作,主要是给动态UML子图赋予形式语义,关注的问题有：UML的语义描述不精确,造成需求和设计之间、设计和实现之间,存在着歧义；在描述一个系统时,不同类型的UML子图之间,可能存在语义不一致,甚至位于不同抽象层次的、同一类型的UML图元之间,也可能存在语义冲突；对某些概率、比率、时间相关的实时并发系统,UML的建模和验证能力不足。进程代数（Process Algebras）,用代数理论研究通信并发系统。进程代数基于标签迁移系统,用一组算子作为基本成分,用算子间的组合刻画复杂系统。进程代数的核心是：互模拟等价理论,即在何种意义下,两个进程的行为相同。首先,标签迁移系统能够描述UML状态图／序列图的动态行为,其次,互模拟等价理论,为检测不同UML图元之间的语义等价性,提供了理论基础。概率模型检测（Probabilistic Model Checking）,支持离散时间Markov链和连续时间Markov链,适于建模概率、比率、时间相关的实时并发系统。概率模型检测由英国伯明翰大学首先提出,并提供模型检测器PRISM支持,适合于建模和验证概率、比率相关的实时模型,对系统关键量化性能指标,实现自动推导和分析。本文在动态UML子图形式化方面,进行了研究,主要研究内容和创新点概括如下：1.给UML状态图／序列图赋予LTS操作语义UML状态图／序列图,由基本构成元素和若干种组装方式（或组合片段）构成。UML状态图/序列图被抽象为一个数学模型,LTS结构被提取为另外一个数学模型。对UML状态图/序列图的基本构成元素,本文给出了其到LTS结构的映射规则；对UML状态图/序列图的组装方式（或组合片段）,本文给出了其LTS操作语义,及转换规则。首先给UML状态图/序列图赋予LTS操作语义,而非直接转换为某种进程代数规范,这样做的好处是：因为进程代数是基于LTS结构,所以,如果给定LTS操作语义,就可以根据不同的语法,将其转换为任意一种进程代数形式规范,而非某一种进程代数形式规范。把UML状态图/序列图转换为某一种进程代数形式规范后,如pi演算,基于互模拟等价理论,在工具的支持下,可以验证不同UML图元之间的语义一致性、系统死锁性；通过工具的单步执行,可以观察系统的动态运行情况,以验证需求和设计是否一致。针对基于pi演算的UML序列图,本文分析并推导了：验证互模拟等价性、系统死锁性算法的时间复杂度,给出了定理、证明和结论。2.给扩展的UML状态图赋予概率/随机Kripke结构语义UML状态图在经过扩展之后,和概率模型检测的语法和语义,具有隐式的映射关系,适合于建模概率、比率相关的实时并发系统。扩展的UML状态图被抽象为一个数学模型,概率/随机Kripke结构被定义为另外一个数学模型,给出了映射规则和转换算法,实现了这两种数学模型之间的转换。扩展的UML状态图,由基本构成元素和若干组装方式构成,这样做的好处是：便于使用数学归纳法,对转换算法的正确性进行分析。给UML状态图赋予概率/随机Kripke结构语义后,可以建模和验证实时并发系统,如排队网络、Ad Hoc概率网络等。在模型检测工具PRISM支持下,可以对量化性能指标,进行自动分析和推导；也可通过PRISM单步执行,观测概率、实时系统的动态运行情况。3.提取关键XMI标签及其数据结构,给出形式语义生成算法通常,在给UML赋予形式语义的研究工作,都是在较高抽象层次上,给出从UML图元到形式语义的转换规则和算法。但是,在设计和实现UML形式语义转换器时,需要对动态UML子图导出的XMI文件进行解析,所以,形式语义生成算法,和存储了关键数据/结构信息的XMI标签紧密相关。本文不但在较高层次上,给出了UML子图的操作语义和转换规则,而且提取出关键XMI标签,将其抽象为数据结构,较低抽象层次上,给出了XMI标签相关的形式语义生成算法,可用于设计实现UML形式语义转换器。4.设计并实现了UML形式语义转换器原型工具在Eclipse集成开发环境下,使用Java语言和Xerces解析器,设计并实现了一个UML形式语义转换器原型工具,给UML状态图／序列图赋予LTS形式语义,或概率／随机Kripke形式语义,最后转换为pi演算代码或PRISM代码。软件原型工具采用了多层体系架构：XMI文件解析→关键数据/结构信息存储→形式语义生成→形式规范转换,增强了软件工具的健壮性、可移植性和可扩展性。
王婷[10]（2007）在《基于偏序简化的并发系统模型检测技术的研究》文中认为随着并发软件系统在国民经济、国防等关键领域的广泛应用，如何验证其正确性和可靠性以保证软件质量成为日益紧迫的问题。对并发系统而言，其内在的不确定性使问题的难度更大。通过对并发系统的形式化分析，可以查找出系统设计中的漏洞或缺陷，能够帮助设计者修改和优化系统，使其更规范、有效、合理。可以说形式化方法在软件系统设计的全过程中发挥相当重要的作用。模型检测技术是近二十年来最成功的形式化自动验证技术之一。其因自动化程度高，效率高等优点而被广泛应用于并发系统的分析与验证中。然而模型检测技术的最大障碍是状态爆炸问题——并发系统的状态数量随并发分量的增加呈指数增长。因此本文对并发系统进行模型检测技术以及状态爆炸问题进行了深入研究。主要包括以下四个方面的工作：首先，分析了目前用于形式化描述的语言。以通信系统CCS为代表的进程代数方法，因其概念简洁，可用的数学工具丰富，在并发系统的规范、分析、设计和验证等方面获得了广泛应用。因此，本文决定采用进程代数的形式化描述方法来研究并发系统模型。其次，分析了状态爆炸的成因，将偏序简化技术应用于进程代数模型上。提出了基于进程代数的偏序简化算法，能更大程度上限制并发系统模型的状态空间，有效得提高了性质验证的效率。再次，在偏序简化技术基础上提出了相应的安全性以及死锁性验证算法。并证明了该算法的有效性。最后，设计了支持上述算法的模型检测原型系统MCTool，分析了并发模型的五种进程并发合成简化前后的情况，并使用典型实例，对工具进行了实验验证。实验结果表明在保证并发系统性质验证结果正确的同时，提高了并发系统模型检测的效率。
二、非确定并发系统的基于说明的测试推导（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、非确定并发系统的基于说明的测试推导（论文提纲范文）
（1）基于大数据的道路交通拥堵预测研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究背景及其意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 研究现状 |
| 1.2.1 交通流预测研究现状 |
| 1.2.2 实时交通流研究现状 |
| 1.3 研究难点 |
| 1.4 研究内容和组织结构 |
| 1.4.1 主要研究内容 |
| 1.4.2 论文组织结构 |
| 第二章 相关技术概述与技术基础 |
| 2.1 实时数据流处理技术 |
| 2.1.1 Flink内存管理 |
| 2.1.2 Flink计算资源调度 |
| 2.2 分布式消息队列 |
| 2.2.1 kafka架构 |
| 2.2.2 kafka参数设置 |
| 第三章 基于极限梯度提升集成算法的道路拥堵预测 |
| 3.1 数据描述 |
| 3.2 数据预处理 |
| 3.2.1 数据集筛选 |
| 3.2.2 标签转化 |
| 3.2.3 剔除离群点 |
| 3.2.4 基于多种算法融合的缺失值处理 |
| 3.3 基于特征影响力的特征构建 |
| 3.4 模型评估 |
| 第四章 基于动态扩容多重位分配的海量数据去重算法 |
| 4.1 布隆过滤器 |
| 4.2 动态扩容的多重位分配算法 |
| 4.2.1 假阳性率 |
| 4.2.2 最优N维矩阵 |
| 4.2.3 基于位图的动态扩容 |
| 4.3 实验结果及其分析 |
| 4.3.1 Flink集群搭建 |
| 4.3.2 kafka集群的搭建 |
| 4.3.3 实验结果分析 |
| 第五章 基于Flink的多维度城市道路预测统计模型 |
| 5.1 多维度城市道路预测统计模型建立 |
| 5.2 基于非确定有限状态自动机的车辆违规超速统计 |
| 5.2.1 基于广播状态的多数据源融合 |
| 5.2.2 非确定有限状态自动机 |
| 5.2.3 复杂事件处理的实现过程 |
| 5.3 基于开窗的城市道路拥堵情况统计 |
| 5.3.1 窗口统计 |
| 5.3.2 基于水位线的数据乱序算法 |
| 5.4 基于自定义TopN函数的城市道路车流量统计 |
| 5.5 实验结果及其分析 |
| 第六章 工作总结与展望 |
| 6.1 研究工作总结 |
| 6.2 未来工作展望 |
| 参考文献 |
| 致谢 |
| 攻读学位期间发表的学术论文目录 |
（2）软件定义网络的形式化建模与验证（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 研究背景和动机 |
| 1.2 研究现状和相关工作 |
| 1.3 本文的主要工作 |
| 1.4 本文的组织结构 |
| 第二章 背景知识 |
| 2.1 软件定义网络 |
| 2.2 虚拟局域网 |
| 2.3 形式语言与形式语义 |
| 2.4 NetKAT语言 |
| 2.5 本章小结 |
| 第三章 网络编程语言PDNet |
| 3.1 NetKAT的第二种操作语义 |
| 3.2 PDNet语言 |
| 3.3 NetKAT与PDNet对比与证明 |
| 3.4 本章小结 |
| 第四章 SDN系统建模框架 |
| 4.1 框架概述 |
| 4.2 转发设备模型 |
| 4.3 主机模型 |
| 4.4 攻击者模型 |
| 4.5 本章小节 |
| 第五章 Floodlight控制器的建模与验证 |
| 5.1 Floodlight基本模块 |
| 5.2 Floodlight模型 |
| 5.3 系统模型与验证 |
| 5.4 本章小节 |
| 第六章 TopoGuard安全机制的建模与验证 |
| 6.1 Topo Guard机制 |
| 6.2 Topo Guard模型 |
| 6.3 系统模型与验证 |
| 6.4 改进的Topo Guard建模与验证 |
| 6.5 本章小节 |
| 第七章 总结与展望 |
| 7.1 本文工作总结 |
| 7.2 后续工作展望 |
| 参考文献 |
| 致谢 |
| 研究成果 |
（3）基于MSVL的动静结合程序验证和自动规划（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 符号对照表 |
| 缩略语对照表 |
| 第一章 绪论 |
| 1.1 研究背景和现状 |
| 1.1.1 时序逻辑 |
| 1.1.2 时序逻辑程序 |
| 1.1.3 时序逻辑与程序验证 |
| 1.1.4 时序性质挖掘 |
| 1.1.5 时序逻辑与自动规划 |
| 1.2 本文的研究目的和主要工作 |
| 1.3 论文的组织结构 |
| 第二章 技术背景 |
| 2.1 投影时序逻辑 |
| 2.1.1 语法和语义 |
| 2.2 建模、仿真和验证语言 |
| 2.2.1 语法和语义 |
| 2.2.2 范式和范式图 |
| 2.3 命题投影时序逻辑 |
| 2.3.1 语法和语义 |
| 2.3.2 带标记的范式图 |
| 2.4 本章小结 |
| 第三章 MSVL编译器 |
| 3.1 MSVL程序编译 |
| 3.1.1 预处理 |
| 3.1.2 运行时系统 |
| 3.1.3 编译器实现 |
| 3.2 仿真和建模 |
| 3.2.1 仿真 |
| 3.2.2 建模 |
| 3.3 实例 |
| 3.3.1 简单互斥问题 |
| 3.3.2 哲学家就餐问题 |
| 3.4 本章小结 |
| 第四章 基于MSVL的动静结合程序验证 |
| 4.1 基于反例的抽象精化 |
| 4.1.1 方法原理 |
| 4.1.2 控制流自动机和抽象可达树 |
| 4.2 方法框架 |
| 4.3 算法实现 |
| 4.3.1 静态反例查找 |
| 4.3.2 动态反例检测 |
| 4.3.3 抽象模型精化 |
| 4.4 实现和实验 |
| 4.5 本章小结 |
| 第五章 完全正则时序性质挖掘 |
| 5.1 方法框架 |
| 5.2 算法实现 |
| 5.2.1 性质模板实例化 |
| 5.2.2 性质挖掘 |
| 5.3 方法示例 |
| 5.4 并行挖掘 |
| 5.5 本章小结 |
| 第六章 基于MSVL的自动规划 |
| 6.1 方法框架 |
| 6.2 规划问题建模 |
| 6.3 搜索控制知识描述 |
| 6.4 实验分析 |
| 6.5 本章小结 |
| 第七章 总结与展望 |
| 7.1 工作总结 |
| 7.2 研究展望 |
| 参考文献 |
| 致谢 |
| 作者简介 |
（4）MSVL程序的高效运行时验证方法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 符号对照表 |
| 缩略语对照表 |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 国内外研究现状 |
| 1.2.1 时序逻辑的研究现状 |
| 1.2.2 时序逻辑编程的研究现状 |
| 1.2.3 运行时验证方法的研究现状 |
| 1.2.4 目前方法存在的问题 |
| 1.3 本文研究内容 |
| 1.4 论文组织结构 |
| 第二章 技术背景 |
| 2.1 投影时序逻辑 |
| 2.1.1 语法 |
| 2.1.2 语义 |
| 2.1.3 导出公式与逻辑规则 |
| 2.2 命题投影时序逻辑 |
| 2.3 MSVL及MSVL编译器 |
| 2.4 运行时验证方法 |
| 2.4.1 基本原理 |
| 2.4.2 运行时验证与其他验证方法的对比 |
| 2.4.3 运行时验证的应用范围 |
| 2.5 本章小结 |
| 第三章 基于单机多核系统的并行运行时验证方法 |
| 3.1 MSVL程序的传统运行时验证方法 |
| 3.2 基于单机多核系统的并行运行时验证方法 |
| 3.2.1 基本框架 |
| 3.2.2 插桩 |
| 3.2.3 验证任务分配和结果合并 |
| 3.2.4 验证模块中的相关算法 |
| 3.3 实现和评价 |
| 3.3.1 实现 |
| 3.3.2 验证效率评价 |
| 3.3.3 验证规模评价 |
| 3.3.4 并行机制对性能的提升 |
| 3.4 验证实例 |
| 3.4.1 问题背景 |
| 3.4.2 问题模型 |
| 3.4.3 性质描述 |
| 3.4.4 验证结果 |
| 3.5 本章小结 |
| 第四章 基于分布式网络的并行运行时验证方法 |
| 4.1 基于分布式网络的并行运行时验证方法 |
| 4.1.1 基本框架 |
| 4.1.2 调度算法 |
| 4.1.3 单个机器中序列片段的并行验证 |
| 4.2 实现和评价 |
| 4.2.1 实现 |
| 4.2.2 验证效率评价 |
| 4.3 验证实例 |
| 4.3.1 问题背景 |
| 4.3.2 违反SQLite3数据库API调用规范的实例 |
| 4.3.3 API调用序列规范的描述 |
| 4.3.4 实验结果 |
| 4.3.5 相关工作 |
| 4.4 本章小结 |
| 第五章 MSVL程序内存泄漏的运行时检测方法 |
| 5.1 泄露实例 |
| 5.2 MSVL程序内存泄漏的运行时检测方法 |
| 5.2.1 方法框架 |
| 5.2.2 插桩 |
| 5.2.3 内存泄露检测、消除和修复 |
| 5.2.4 动态符号执行 |
| 5.3 实验结果 |
| 5.3.1 针对单条执行路径DEF LEAK的性能 |
| 5.3.2 采用动态符号执行后DEF LEAK的性能 |
| 5.4 相关工作 |
| 5.4.1 静态内存泄漏检测方法 |
| 5.4.2 动态内存泄漏检测方法 |
| 5.5 本章小结 |
| 第六章 MSVL程序的统一限界运行时验证方法 |
| 6.1 MSVL程序的统一运行时验证方法 |
| 6.2 PPTL限界语义 |
| 6.3 MSVL程序的统一限界运行时验证方法 |
| 6.4 验证实例 |
| 6.4.1 互斥问题 |
| 6.4.2 哲学家就餐问题 |
| 6.4.3 银行家算法 |
| 6.5 本章小结 |
| 第七章 总结与展望 |
| 7.1 工作总结 |
| 7.2 研究展望 |
| 参考文献 |
| 致谢 |
| 作者简介 |
（5）符号化验证关键技术研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 符号化验证 |
| 1.3 相关工作 |
| 1.3.1 正规性质分析与验证 |
| 1.3.2 并行MPI程序的可靠性保证技术 |
| 1.4 研究内容 |
| 1.4.1 串行程序正规性质的符号化验证 |
| 1.4.2 非消息通信依赖MPI程序的符号化验证 |
| 1.4.3 动态调度MPI程序的符号化验证 |
| 1.5 论文结构 |
| 第二章 预备知识 |
| 2.1 符号执行 |
| 2.1.1 静态符号执行 |
| 2.1.2 动态符号执行 |
| 2.1.3 应用 |
| 2.1.4 挑战与应对策略 |
| 2.2 程序切片 |
| 2.2.1 静态切片 |
| 2.2.2 动态切片 |
| 2.2.3 路径切片 |
| 2.3 模型检验 |
| 2.3.1 方法简介 |
| 2.3.2 偏序规约 |
| 第三章 串行程序正规性质符号化验证 |
| 3.1 问题与方法概述 |
| 3.2 正规性质符号化验证 |
| 3.3 正规性质引导的符号执行 |
| 3.3.1 计算历史行为信息 |
| 3.3.2 计算未来行为信息 |
| 3.3.3 候选分支选取 |
| 3.4 面向正规性质的路径切片 |
| 3.4.1 算法概述 |
| 3.4.2 路径切片 |
| 3.4.3 事件序列拼接 |
| 3.4.4 选择性切片 |
| 3.5 讨论 |
| 3.6 实现与实验 |
| 3.6.1 实验设计 |
| 3.6.2 实验结果 |
| 3.7 相关工作 |
| 3.8 本章总结 |
| 第四章 非消息通信依赖MPI程序的符号化验证 |
| 4.1 MPI简介 |
| 4.1.1 MPI语法 |
| 4.1.2 MPI语义 |
| 4.2 问题与方法概述 |
| 4.2.1 问题描述 |
| 4.2.2 方法概述 |
| 4.3 MPI程序符号化验证 |
| 4.4 MPI程序符号执行 |
| 4.4.1 MPI语句的符号执行与阻塞驱动匹配 |
| 4.4.2 MPI符号执行的正确性 |
| 4.5 CSP模型检验 |
| 4.5.1 CSP子集 |
| 4.5.2 CSP建模 |
| 4.5.3 CSP建模的可靠性和完全性 |
| 4.5.4 讨论 |
| 4.6 实现与实验 |
| 4.6.1 工具实现 |
| 4.6.2 研究问题 |
| 4.6.3 实验设计 |
| 4.6.4 实验结果 |
| 4.7 相关工作 |
| 4.8 本章总结 |
| 第五章 动态调度MPI程序的符号化验证 |
| 5.1 Master-Slave模式简介 |
| 5.2 Master-Slave模式的识别 |
| 5.2.1 Master进程的识别 |
| 5.2.2 Slave进程的识别 |
| 5.3 CSP建模方法 |
| 5.3.1 Master进程建模方法 |
| 5.3.2 Slave进程建模方法 |
| 5.3.3 多发送Master-Slave模式的支持 |
| 5.3.4 优化 |
| 5.4 实现与实验 |
| 5.4.1 实现 |
| 5.4.2 实验设计 |
| 5.4.3 实验结果 |
| 5.5 相关工作 |
| 5.6 本章总结 |
| 第六章 结束语 |
| 6.1 本文工作总结 |
| 6.2 研究展望 |
| 致谢 |
| 参考文献 |
| 作者在学期间取得的学术成果 |
（6）基于时空约束的车联网事件监控方法与技术研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.1.1 车联网系统概述 |
| 1.1.2 车联网中的大数据流处理问题 |
| 1.1.3 事件驱动体系结构和事件处理语言 |
| 1.1.4 交通监控系统 |
| 1.2 研究意义与所面临的挑战 |
| 1.3 本文研究工作的体系框架和主要贡献 |
| 1.3.1 本文研究工作的体系框架 |
| 1.3.2 本文研究工作的主要贡献 |
| 1.4 论文的章节安排 |
| 第二章 相关研究现状及预备知识 |
| 2.1 相关研究现状 |
| 2.1.1 时空事件模型及事件处理语言研究现状 |
| 2.1.2 事件流处理模型及方法研究现状 |
| 2.1.3 事件流分布式处理方法研究现状 |
| 2.1.4 公交车监控系统研究现状 |
| 2.1.5 非确定事件模型及非确定事件处理语言研究现状 |
| 2.2 预备知识 |
| 2.2.1 Petri网相关知识 |
| 2.2.2 随机Petri网相关知识 |
| 2.2.3 排队论相关知识 |
| 2.3 本章小结 |
| 第三章 面向车联网的时空事件处理语言STEP |
| 3.1 事件驱动体系结构的车联网系统中的时空事件模型 |
| 3.1.1 车联网系统中的时空数据模型 |
| 3.1.2 车联网系统中的时空事件实例模型 |
| 3.2 面向车联网的时空事件处理语言STEP |
| 3.2.1 STEP语言的语法 |
| 3.2.2 STEP语言的操作语义 |
| 3.3 STEP语言的指称语义 |
| 3.4 STEP语言的语义一致性 |
| 3.5 相关研究工作比较 |
| 3.6 本章小结 |
| 第四章 基于Petri网模型的车联网时空事件流处理方法 |
| 4.1 STEP语句对应的事件流Petri网处理模型 |
| 4.2 STEP语句的时空事件流Petri网处理模型的结构性质 |
| 4.2.1 STEP语句的Petri网处理模型的关联矩阵 |
| 4.2.2 STEP语句的Petri网处理模型的结构性质 |
| 4.3 车联网时空事件流处理程序及其动态性能 |
| 4.3.1 车联网时空事件流处理程序的核心算法 |
| 4.3.2 车联网时空事件流处理程序的排队论模型 |
| 4.3.3 车联网时空事件流处理程序实例动态性能分析 |
| 4.3.4 事件流处理程序实例动态性能仿真实验与结果分析 |
| 4.4 相关研究工作比较 |
| 4.5 本章小结 |
| 第五章 车联网时空事件流的多维QoS分布式处理方法 |
| 5.1 车联网大规模时空事件流分布式处理系统体系框架 |
| 5.2 车联网大规模时空事件流分布式处理任务模型 |
| 5.3 车联网分布式计算资源多维QoS模型 |
| 5.3.1 车联网分布式计算资源间的可靠度模型 |
| 5.3.2 车联网分布式计算资源的多维QoS拓扑结构图模型 |
| 5.4 基于不同用户偏好的多维QoS改进HEFT调度算法 |
| 5.4.1 构造任务优先级列表算法 |
| 5.4.2 为任务列表分配计算资源算法 |
| 5.4.3 算例分析 |
| 5.5 相关研究工作比较 |
| 5.6 本章小结 |
| 第六章 应用案例：基于时空事件的公交车动态监控原型系统 |
| 6.1 应用案例背景及原型系统概述 |
| 6.1.1 北京市第1路公交车线路概况 |
| 6.1.2 公交车动态监控原型系统概述 |
| 6.2 基于STeC/STEP的公交车动态监控策略 |
| 6.2.1 基于STeC语言的公交车辆行为规范 |
| 6.2.2 基于STEP语言的公交车违规行为事件处理语句 |
| 6.2.3 基于STeC/STEP的公交车动态监控策略 |
| 6.3 基于STeC/STEP的公交车动态监控原型系统的设计与实现 |
| 6.3.1 基于AADL的公交车动态监控原型系统体系结构设计 |
| 6.3.2 时空事件流处理引擎STEPEngine的设计与实现 |
| 6.4 基于STeC/STEP的公交车动态监控原型系统仿真实验 |
| 6.5 相关研究工作比较 |
| 6.6 本章小结 |
| 第七章 车联网非确定时空事件处理语言PSTEP |
| 7.1 车联网中非确定时空事件的可能世界模型 |
| 7.2 车联网非确定时空事件处理语言PSTEP |
| 7.2.1 PSTEP语言的语法 |
| 7.2.2 PSTEP语言的操作语义 |
| 7.2.3 PSTEP语言的指称语义 |
| 7.2.4 PSTEP语言的语义一致性 |
| 7.3 车联网非确定时空事件流的可能区间和可能比 |
| 7.3.1 车联网非确定时空事件流的可能区间 |
| 7.3.2 车联网非确定时空事件的可能比 |
| 7.4 相关研究工作比较 |
| 7.5 本章小结 |
| 第八章 总结与展望 |
| 8.1 本文工作总结 |
| 8.2 论文的不足之处与未来工作展望 |
| 参考文献 |
| 攻读博士学位期间发表论文 |
| 参与的科研项目 |
| 致谢 |
（7）基于符号与数值混合计算的多项式变迁系统近似互模拟（论文提纲范文）
| 致谢 |
| 摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 程序的形式化刻画系统 |
| 1.2.2 程序等价理论 |
| 1.2.3 符号与数值混合计算 |
| 1.3 存在的问题 |
| 1.4 论文的研究内容 |
| 1.5 论文的结构安排 |
| 2 相关基础理论与技术 |
| 2.1 进程代数 |
| 2.1.1 标号变迁系统 |
| 2.1.2 等价关系 |
| 2.2 符号计算 |
| 2.2.1 吴特征列方法 |
| 2.2.2 Groebner基方法 |
| 2.3 数值计算 |
| 2.3.1 矩阵范数 |
| 2.3.2 奇异值分解 |
| 2.3.3 QR分解 |
| 2.3.4 填充函数法 |
| 2.4 本章小结 |
| 3 基于数值计算的齐次线性多项式变迁系统近似互模拟 |
| 3.1 齐次线性多项式变迁系统 |
| 3.1.1 数据流交换过程划分规则 |
| 3.1.2 数据流交换过程与齐次线性多项式系统间转换规则 |
| 3.1.3 齐次线性多项式变迁系统定义 |
| 3.2 齐次线性多项式变迁系统互模拟等价 |
| 3.2.1 齐次线性多项式变迁系统互模拟等价定义 |
| 3.2.2 基于系数矩阵性质的齐次线性多项式系统等价 |
| 3.2.3 齐次线性多项式变迁系统互模拟等价计算方法 |
| 3.3 齐次线性多项式变迁系统近似互模拟 |
| 3.3.1 齐次线性多项式变迁系统近似互模拟定义 |
| 3.3.2 基于系数矩阵性质的齐次线性多项式系统近似 |
| 3.3.3 基于奇异值分解的近似齐次线性多项式系统求解 |
| 3.3.4 齐次线性多项式变迁系统近似互模拟计算方法 |
| 3.4 实验 |
| 3.4.1 实验设置 |
| 3.4.2 实验结果与分析 |
| 3.5 本章小结 |
| 4 基于数值计算的非齐次线性多项式变迁系统近似互模拟 |
| 4.1 非齐次线性多项式变迁系统 |
| 4.1.1 数据流交换过程与非齐次线性多项式系统间转换规则 |
| 4.1.2 非齐次线性多项式变迁系统定义 |
| 4.2 非齐次线性多项式变迁系统互模拟等价 |
| 4.2.1 非齐次线性多项式变迁系统互模拟等价定义 |
| 4.2.2 基于增广矩阵性质的非齐次线性多项式系统等价 |
| 4.2.3 非齐次线性多项式变迁系统互模拟等价计算方法 |
| 4.3 非齐次线性多项式变迁系统近似互模拟 |
| 4.3.1 非齐次线性多项式变迁系统近似互模拟定义 |
| 4.3.2 基于增广矩阵性质的非齐次线性多项式系统近似 |
| 4.3.3 基于QR分解的近似非齐次线性多项式系统求解 |
| 4.3.4 非齐次线性多项式变迁系统近似互模拟计算方法 |
| 4.4 实验 |
| 4.4.1 实验设置 |
| 4.4.2 实验结果与分析 |
| 4.5 本章小结 |
| 5 基于符号与数值混合计算的非线性多项式变迁系统近似互模拟 |
| 5.1 非线性多项式变迁系统 |
| 5.1.1 数据流交换过程与非线性多项式系统间转换规则 |
| 5.1.2 非线性多项式变迁系统定义 |
| 5.2 非线性多项式变迁系统互模拟等价 |
| 5.2.1 非线性多项式变迁系统互模拟等价定义 |
| 5.2.2 基于吴特征列和Groebner基的非线性多项式系统等价 |
| 5.2.3 非线性多项式变迁系统互模拟等价计算方法 |
| 5.3 非线性多项式变迁系统近似互模拟 |
| 5.3.1 非线性多项式变迁系统近似互模拟定义 |
| 5.3.2 基于Max函数的非线性多项式系统近似 |
| 5.3.3 基于吴特征列的近似非线性多项式系统求解 |
| 5.3.4 非线性多项式变迁系统近似互模拟计算方法 |
| 5.4 实验 |
| 5.4.1 实验设置 |
| 5.4.2 实验结果与分析 |
| 5.5 本章小结 |
| 6 总结与展望 |
| 6.1 研究工作总结 |
| 6.2 未来工作展望 |
| 参考文献 |
| 附录A |
| 附录B |
| 附录C |
| 附录D |
| 作者简历及攻读博士学位期间取得的研究成果 |
| 学位论文数据集 |
（8）面向实时嵌入式系统的中断语义理论研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 实时嵌入式系统的中断机制 |
| 1.2 中断的研究现状与相关工作 |
| 1.3 本文的指导方法 |
| 1.3.1 程序统一理论 |
| 1.3.2 语义理论的相关工作 |
| 1.4 本文的主要工作 |
| 第二章 中断建模语言IML |
| 2.1 IML描述的中断机制 |
| 2.2 IML的语法 |
| 2.3 IML的操作语义 |
| 2.3.1 操作语义的语义空间 |
| 2.3.2 操作语义的迁移规则 |
| 2.3.3 基于操作语义的程序等价性 |
| 2.4 本章小结 |
| 第三章 IML的指称语义 |
| 3.1 IML的指称语义 |
| 3.1.1 指称语义的语义空间 |
| 3.1.2 程序算子的指称语义 |
| 3.2 IML的代数规则及证明 |
| 3.3 IML的语义一致性 |
| 3.4 本章小结 |
| 第四章 带卫兵的中断建模语言gIML |
| 4.1 gIML的语法 |
| 4.2 gIML的语义 |
| 4.2.1 gIML的操作语义 |
| 4.2.2 gIML的指称语义 |
| 4.3 gIML的代数规则及证明 |
| 4.4 本章小结 |
| 第五章 带概率的中断建模语言pIML |
| 5.1 pIML的语法 |
| 5.2 pIML的概率语义 |
| 5.2.1 pIML的概率操作语义 |
| 5.2.2 pIML的概率指称语义 |
| 5.3 pIML的代数规则及证明 |
| 5.4 本章小结 |
| 第六章 中断建模语言的应用 |
| 6.1 仿真 |
| 6.1.1 语法解析 |
| 6.1.2 语义实现 |
| 6.2 程序运行时间与概率计算 |
| 6.3 概率统计在中断上的应用 |
| 6.4 示例 |
| 6.5 本章小结 |
| 第七章 总结与展望 |
| 参考文献 |
| 致谢 |
| 攻读博士学位期间发表论文和科研情况 |
（9）动态UML子图的形式语义研究（论文提纲范文）
| 论文摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 国内外研究现状 |
| 1.3 本文研究内容 |
| 1.4 本文组织结构 |
| 第二章 相关技术概述 |
| 2.1 UML 2.0 |
| 2.1.1 UML概述 |
| 2.1.2 UML状态图 |
| 2.1.3 UML顺序图 |
| 2.2 形式化方法 |
| 2.2.1 形式化方法概述 |
| 2.2.2 基于LTS结构的pi演算 |
| 2.2.3 概率模型检测 |
| 2.3 XMI概述 |
| 第三章 UML状态图的LTS操作语义 |
| 3.1 引言 |
| 3.1.1 研究背景 |
| 3.1.2 相关工作 |
| 3.2 UML状态图的组装机制及其LTS操作语义 |
| 3.2.1 顺序组装和无触发组装 |
| 3.2.2 选择组装 |
| 3.2.3 分叉组装和汇聚组装 |
| 3.2.4 并行组装和复制组装 |
| 3.3 UML状态图的LTS形式语义生成算法 |
| 3.3.1 关键XMI标签及其数据结构 |
| 3.3.2 算法描述 |
| 3.4 UML状态图在模型精化中的语义等价自动证明 |
| 3.5 小结 |
| 第四章 UML序列图的操作语义及在模型精化一致性检查 |
| 4.1 引言 |
| 4.1.1 研究背景 |
| 4.1.2 相关工作 |
| 4.2 UML序列图的操作语义 |
| 4.2.1 消息的异步发送 |
| 4.2.2 消息的同步发送和内部消息 |
| 4.2.3 分支组合片段 |
| 4.2.4 循环组合片段 |
| 4.2.5 中断组合片段 |
| 4.2.6 并发组合片段 |
| 4.2.7 其它 |
| 4.3 UML序列图的LTS操作语义生成算法 |
| 4.3.1 关键XMI标签及其数据结构 |
| 4.3.2 算法描述 |
| 4.4 UML状态图和序列图的一致性检查 |
| 4.4.1 电话系统的UML序列图模型及其pi演算转换 |
| 4.4.2 电话系统的UML状态图模型及其pi演算转换 |
| 4.4.3 进程代数工具的自动验证 |
| 4.4.4 系统死锁性的手动推导及其时间复杂度 |
| 4.4.5 UML子图间的语义一致性手动推导及时间复杂度 |
| 4.5 小结 |
| 第五章 基于概率模型检测的扩展UML状态图量化分析 |
| 5.1 引言 |
| 5.1.1 研究背景 |
| 5.1.2 相关工作 |
| 5.1.3 概率/随机Kripke结构的形式化定义 |
| 5.2 扩展UML状态图的概率/随机Kripke结构语义 |
| 5.2.1 系统初始化和状态标签 |
| 5.2.2 状态顺序迁移 |
| 5.2.3 状态内部迁移 |
| 5.2.4 状态的选择迁移 |
| 5.2.5 模块声明和模块重命名 |
| 5.2.6 同步并发组合和异步并发组合 |
| 5.3 概率/随机Kripke形式语义生成算法 |
| 5.3.1 关键XMI标签及其数据结构 |
| 5.3.2 算法描述 |
| 5.4 基于概率Kripke结构的模型量化分析 |
| 5.4.1 UML状态图的概率Kripke结构语义 |
| 5.4.2 系统关键属性的PCTL描述和自动验证 |
| 5.5 基于随机Kripke结构的系统性能分析 |
| 5.5.1 排队网络的CTMC形式语义 |
| 5.5.2 关键系统属性的自动推导和证明 |
| 5.5.3 关键系统属性的手动推导和分析 |
| 5.6 小结 |
| 第六章 软件原型工具的设计与实现 |
| 6.1 UML形式语义转换器的体系架构 |
| 6.2 UML形式语义转换器的设计与实现 |
| 6.2.1 软件原型工具的设计原则 |
| 6.2.2 算法和数据结构 |
| 6.2.4 软件原型工具的运行和使用 |
| 6.3 小结 |
| 第七章 结束语 |
| 7.1 本文的主要贡献 |
| 7.2 下一步研究工作 |
| 参考文献 |
| 作者在攻读博士学位期间发表的论文 |
| 作者在攻读博士学位期间取得的其它成果 |
| 致谢 |
（10）基于偏序简化的并发系统模型检测技术的研究（论文提纲范文）
| 摘要 |
| Abstract |
| 目录 |
| 第1章 引言 |
| 1.1 研究的背景和意义 |
| 1.2 模型检测技术的研究现状和问题 |
| 1.3 主要研究内容 |
| 1.4 本文结构及章节安排 |
| 第2章 并发系统的模型检测 |
| 2.1 并发系统 |
| 2.2 形式化方法概述 |
| 2.2.1 并发系统形式化描述的必要性 |
| 2.2.2 形式化方法研究的主要内容 |
| 2.3 模型检测 |
| 2.3.1 模型检测概述 |
| 2.3.2 模型检测形式化描述方法分类 |
| 2.4 模型检测中的状态空间爆炸问题 |
| 2.5 本章小结 |
| 第3章 基于进程代数的偏序简化技术的研究 |
| 3.1 CCS概述 |
| 3.1.1 CCS的基本概念 |
| 3.1.2 CCS的符号和基本算子 |
| 3.2 偏序简化技术简介 |
| 3.2.1 独立性和迹 |
| 3.2.2 稳固集(persistent set)和睡眠集(sleep set)技术 |
| 3.3 基于进程代数的偏序简化 |
| 3.4 本章小结 |
| 第4章 基于偏序简化技术模型检测的原型系统实现 |
| 4.1 MCTool的设计 |
| 4.2 MCTool的系统结构 |
| 4.3 模型检测的输入语言MCTL |
| 4.4 核心算法实现 |
| 4.4.1 状态化简算法 |
| 4.4.2 安全性验证算法 |
| 4.4.3 死锁性验证算法 |
| 4.5 本章小结 |
| 第5章 实例研究 |
| 5.1 五种典型的进程并发合成模式的简化 |
| 5.2 实现对哲学家就餐问题以及资源共享协议的性质验证 |
| 5.3 效率分析 |
| 5.4 本章小结 |
| 第6章 总结与展望 |
| 参考文献 |
| 攻读学位期间发表论文以及科研情况 |
| 致谢 |
四、非确定并发系统的基于说明的测试推导（论文参考文献）
- [1]基于大数据的道路交通拥堵预测研究[D]. 吴成伟. 北京邮电大学, 2021(01)
- [2]软件定义网络的形式化建模与验证[D]. 向霜晴. 华东师范大学, 2020(08)
- [3]基于MSVL的动静结合程序验证和自动规划[D]. 杨凯. 西安电子科技大学, 2019(02)
- [4]MSVL程序的高效运行时验证方法研究[D]. 于斌. 西安电子科技大学, 2019(02)
- [5]符号化验证关键技术研究[D]. 于恒彪. 国防科技大学, 2018(01)
- [6]基于时空约束的车联网事件监控方法与技术研究[D]. 李慧勇. 华东师范大学, 2015(03)
- [7]基于符号与数值混合计算的多项式变迁系统近似互模拟[D]. 邓辉. 北京交通大学, 2014(12)
- [8]面向实时嵌入式系统的中断语义理论研究[D]. 黄滟鸿. 华东师范大学, 2014(01)
- [9]动态UML子图的形式语义研究[D]. 赵也非. 华东师范大学, 2010(12)
- [10]基于偏序简化的并发系统模型检测技术的研究[D]. 王婷. 西北大学, 2007(05)