导读:本文包含了最坏情况下执行时间论文开题报告文献综述及选题提纲参考文献，主要关键词:软件安全,最坏情况执行时间,指令剖面,控制流树
最坏情况下执行时间论文文献综述
孟凡奇[1]（2018）在《面向软件开发初期的最坏情况执行时间快速估计与优化》一文中研究指出实时系统中的软件安全不仅与软件的功能是否达到预期有关,同时还取决于软件的运行能否满足截止时间要求。随着软件在实时系统中发挥的作用越来越关键,程序的规模和结构也随之变得更加庞大和复杂,致使超时风险及超时损失的严重程度都不断增加。由于在软件开发初期对有失效倾向的模块进行预测,既可以大幅提高软件的质量,又可以降低缺陷的修复成本。因此,应该在系统开发初期便对程序的最坏情况执行时间(Worst-Case Execution Time,WCET)进行快速估计,而后立即将估值反馈至源码以定位性能瓶颈,进而通过源码优化消除瓶颈,实现以较低成本防控超时风险的目的。然而,现有WCET的静态分析方法虽然可以保证估值安全但效率普遍较低,为了避免等待或者频繁切换界面,程序员往往将WCET估计推迟到系统开发后期才进行。加之估值取自目标代码因而难以映射到源码层次,以及基于目标代码的传统性能优化不能有效降低WCET等问题,给早期超时风险的预警及防控造成了极大困难。为此,本文开展面向软件开发初期的WCET快速估计与优化方法研究,对于超时风险的早期预警与防控,降低实时系统的开发成本、增强系统可靠性以及保障软件安全,具有重要的理论意义和应用价值。针对现有方法无法实时给出程序的WCET估值,因而难以与开发进程同步并对超时风险进行实时预警的问题,研究并提出一种基于指令剖面的WCET快速估计方法。将程序的模拟执行时间、动态指令类型数与其目标代码的模糊哈希值相结合,设计了面向WCET非线性估计的程序特征模型。在此基础上,开发了静态相似度与动态相似度相结合的训练样本优选算法。当基于IPET的WCET分析方法(以下简称“IPET方法”)可用时,提取程序的静态和动态特征,与其WCET估值一并存入样本库。若IPET方法在预定时间内没能给出分析结果,则依据静态相似度与动态相似度从样本库中优选训练样本,并采用最小二乘支持向量机进行学习与非线性预测。实验结果表明,本文方法的平均效率高,能够伴随编译过程快速估计程序整体的WCET,且对估计精度的影响较小,适用于软件开发初期的超时风险实时预警。针对现有方法不支持在源码层次显示函数或语句的WCET以及存在过高估计,因而难以快速定位代码性能瓶颈的问题,研究并提出一种层次化的WCET快速估计方法。使用控制流树计算函数或语句的WCET,并利用字节码保留的层次结构信息将WCET反馈至源码。分析了现有方法存在过高估计的原因。在此基础上,提出了不合理高估的判定条件,并与基于控制流树的WCET估计算法融合,在快速估计WCET的同时统计高估风险数据。设计了WCET反馈与超时风险预警机制,依据时间预算判定代码是否超时,一旦发现超时便触发相应警示。实验结果表明,本文方法不仅能够快速估计函数或语句的WCET并在源码层次予以显示,而且能够自动判定不合理的高估,进而减少确认时效缺陷的时间开销,提高代码性能瓶颈的定位效率。针对现有方法没有考虑复杂程序中非正交嵌套循环的局部最大迭代次数在转换为内外层循环的相对约束关系时出现的不可整除情况,因而导致WCET被过高估计进而误导程序员盲目优化程序代码的问题,研究并提出一种基于局部相对约束的WCET高估值修正方法。从处理器行为分析和控制流分析两个方面剖析了现有方法出现过高估计的原因。在此基础上,给出判定含非正交嵌套循环程序存在WCET过高估计的必要条件。针对此类特殊高估,设计了基于局部相对约束的WCET过高估值修正算法,由内至外逐层修正最坏情况执行路径上非分支部分中非正交嵌套循环的相对约束关系。实验结果表明,本文方法能够在确保WCET安全估计的前提下,有效降低在含非正交嵌套循环程序上出现的WCET过高估计,避免不必要的代码优化代价。针对现有方法优化WCET对代码后期的可维护性影响大且可移植性差,不能以较小代价有效防控超时风险的问题,研究并提出一种基于不变路径的源码重构WCET优化方法。该方法利用标注反馈技术在源码上识别WCEP及不变路径。而后,依据不变路径以及循环对WCET优化的影响程度,对程序源码进行了优化热点区域的划分。同时,针对WCET优化可能产生克隆代码以致影响软件后期维护的问题,通过克隆元素的数量与克隆代码之间的距离计算维护代价,并据此设计了WCET源码重构优化策略。实验结果表明,本文方法能够以较小的可维护性代价降低程序的WCET,进而防控软件的超时风险,且优化结果具有可移植性。综上所述,本文的研究为解决如何在软件开发初期快速估计及优化WCET,进而检测代码中的超时风险并对其进行有效防控,确保软件满足执行时间约束等科学问题提供了新的思路与方法。有利于实时系统开发过程中的软硬件协同设计,有益于降低实时系统的开发成本并提高系统的软件安全性。(本文来源于《哈尔滨工业大学》期刊2018-03-01）
李军义,李双,张焱,李仁发[2]（2015）在《基于MPA与静态预估的最坏执行时间分析方法》一文中研究指出针对现有嵌入式系统最坏执行时间(WCET)的静态分析方法效率低下问题,利用最小传播算法对程序流进行分析,获得程序中每一个基本块的最小树约束,通过象征性循环上界约束对所求函数中的内部循环变量进行再次约束,并结合最小树约束获得程序的WCET表达式。使用静态预估分析方法对每一个基本块的底层指令周期进行绝对估值,将底层指令周期代入WCET表达式计算出程序最终的WCET值。实验结果表明,与基于程序控制流程图的程序执行时间静态分析方法相比,该方法在保证程序分析精度的同时,大幅提高了分析效率。(本文来源于《计算机工程》期刊2015年10期）
殷锋社,汤小明[3]（2013）在《实时系统最坏执行时间分析及测试》一文中研究指出程序最坏执行时间是实时系统可调度分析的基础,同时也是对系统进行性能分析,提前发现系统瓶颈的重要依据。本文首先论述了程序最坏执行时间(WCET)分析计算的主要方法,然后介绍了主要的测试工具及其应用情况,最后针对程序最坏执行时间的工程应用提出可行建议。(本文来源于《电子测试》期刊2013年10期）
黎嘉翰[4]（2013）在《基于抽象分析的最坏执行时间分析技术》一文中研究指出最坏执行时间（WCET）估值的需求在于为计算机控制产品和其他实时计算机系统的程序的时效性提供保证。这些估值可以用来保证中断的及时地响应，也可以确保周期任务的吞吐量，还有作为任务调度或调度策略的输入等其他的情况。为了得到程序的WCET估值，软件与硬件的性能都必须去考虑。WCET估值传统的计算方法是通过测试或者繁琐的手动分析，而这些方法即耗时又容易出错。相反，静态WCET分析可以计算出可靠的WCET估值却不需要真正的运行程序。最坏执行时间（WCET）分析目的是为了确定在特定的硬件平台环境下运行的一个程序其执行时间的上限。静态分析是计算出最坏执行时间的主要的方法之一，而且该方法不需要依靠在真正的硬件环境或模拟平台上运行得出结果。通常，静态分析一般包括3个阶段：Flow analysis, Low-level analysis and Calculation。在此论文中，我们将提出一种方法名为抽象分析来进行静态分析。在Flowanalysis阶段，首先为测量的程序建立控制流图（CFG），并将数据信息与该控制流图相结合。然后对建立好的控制流图进行抽象分析得出基本的抽象结构。使用这些抽象结构可以将分析分成若干相互独立的处理部分，这些独立的处理部分可以并行的方式运行分析。而且根据这些抽象结构定义的方法，流信息可以自动地在流分析阶段生成。对于Low-level analysis阶段，我们使用由先前其他论文中提出的常见方法来得出处理器行为的时序。这些结果很大程度上决定了我们的计算正确与否。在Calculation阶段，采用一种新的基于路径计算的方法来计算WCET的估值，而这种方法是基于抽象分析并可以有效的处理流信息。该方法解决了常用基于路径方法的存在的缺点，就是这些方法不能很好的处理循环嵌套时的流信息。实验数据表明我们的方法是一个有效的分析方法，其具有统一地解决问题的性质。而且在某些情况下可以得到更好的结果。(本文来源于《电子科技大学》期刊2013-03-19）
汤森森[5]（2012）在《任务最坏执行时间分析与任务调度检测仿真工具的实现》一文中研究指出随着社会的发展，计算机的应用已经渗透到了人们经济生活中的各个方面，特别是嵌入式系统的应用正在不断的从军工设备向企业设备以及普通的家用设备转移。这种发展趋势使得嵌入式软件的复杂度以及规模都在不断增长，从而导致了开发时间和费用的不断增长，寻找到一种新的能够提高开发效率的嵌入式软件开发模式是当前研究的重点。由于在嵌入式软件开发中的绝大部分错误是在需求分析的早期阶段引入的，这些错误将随着开发的深入逐渐放大，而且这些错误发现得越晚，对其进行修改所需付出的代价也越大。所以在嵌入式软件开发的早期阶段就发现问题，对于节省嵌入式软件开发时间起着至关重要的作用。本文就致力于在嵌入式实时系统开发的早期阶段，检测系统内任务模型的可调度性。为了检测嵌入式实时系统内任务模型的可调度性，首先应该得到任务的最坏执行时间信息，只有在得到任务最坏执行时间前提下，才能分析任务的可调度性。所以在本文的前一部分，重点讨论了如何采用静态分析的方法来计算任务的最坏执行时间（Worst Case Execution Time，WCET）。采用此方法可以避免传统动态测量方法的各种弊端，如消耗时间长，结果不准确等，使得到的结果更加安全和准确。在得到任务的最坏执行时间后，就可以开展对任务的可调度性检测工作了，在论文的后半部分，详细介绍了一款嵌入式任务调度检测仿真工具（SchedulingCheck&Simulate Tool，SCST）的使用以及开发过程。该工具可以对嵌入式系统模型进行比较准确和快速的可调度性检测，而且能够以甘特图的形式对系统内任务的执行过程进行仿真。本人在工具开发过程中主要负责系统模型和任务模型的建立以及调度算法的设计。本文最后采用静态分析的方法对一些基准程序进行了分析，并用所得到的结果与真实值做对比，验证了分析的精确性；然后用SCST检测了几个任务模型的用例，并与国外同类型软件TIMES作分析结果对比，验证了此工具的高效性和准确性。最后总结了在课题研究中所遇到的问题和困难，指出了分析方法和工具的不足之处以及可以改进的地方。(本文来源于《电子科技大学》期刊2012-03-01）
曾辉[6]（2010）在《最小化最坏执行时间的指令缓存锁定算法》一文中研究指出通过静态指令缓存锁定,最小化实时嵌入式系统的最坏执行时间.本文使用执行流树来进行分析,将问题描述为一个线性规划模型;从理论上证明了一般性问题是NP难的;对于含有某些特定模式的具体的子问题,给出了求解其最优解的多项式时间算法.实验表明,本文的算法在减少应用的最坏执行时间上效果很好.(本文来源于《武汉大学学报(理学版)》期刊2010年06期）
张保民,吴国伟,姚琳[7]（2010）在《程序最坏执行时间极值统计方法》一文中研究指出程序的最坏执行时间WCET是实时系统时间操作方面的可信基础,现有的WCET静态分析方法都需要对系统某种程度上的额外知识和限定性假设,导致现有的WCET分析方法本质上为偏高估计,降低了资源的利用率和系统的性能。给出一种基于极值统计的程序最坏执行时间估计新方法,采用程序执行时间的测量值作为样本,利用Gumbel分布建立程序最坏执行时间统计模型,根据测量样本序列预测执行时间的最大值,与以往的方法相比,这种方法综合体现了各种硬件特性对程序执行时间的影响,估计结果更为精确,更适合处理硬件特性和软件复杂度较高情况下的程序最坏执行时间估计。实验结果表明利用Gumbel分布建立的WCET估计模型能够快速且有效地给出实时程序的最坏执行时间估计。(本文来源于《计算机工程与应用》期刊2010年26期）
吴国伟,姚琳,岳峰[8]（2010）在《一种快速程序最坏执行时间分析方法研究》一文中研究指出给出一种带有路径冲突检测的程序最坏情况执行时间估计方法,这种方法首先检测程序中存在的分支约束,然后将程序中存在的分支约束信息转化为程序流程控制图(CFG图)中结点之间的语义冲突,并按照结点对的形式保存在相应的冲突数组里,在接下来的WCET计算阶段通过边搜索程序执行路径边检测冲突数组里保存的已有的冲突关系以便在搜索路径的同时排除非可行执行路径,最终在可行执行路径集中选择具有最大执行时间的执行路径。与以往的方法相比,在保持估计精度的前提下,本文的方法避免了穷举所有执行路径带来的复杂度,提高了搜索的效率。实验结果表明本文方法对于语句间语义依赖关系比较强的实时程序能够快速且有效地给出估计结果。(本文来源于《计算机工程与应用》期刊2010年21期）
吴国伟,李张[9]（2010）在《一种精确程序最坏执行时间分析方法》一文中研究指出Java语言的动态特性使程序的最坏执行时间分析较悲观和难以预测,提出一种精确最坏执行时间分析方法,在高层分析中,引入一种标记方法,对带有标记的Java类文件进行反编译提取控制流程,得到每一个基本块中的Java字节码指令的最坏情况下的执行次数,在底层分析中,建立结合流水线和高级缓存影响的时间模型,得到每条指令所对应的执行时间,最后结合高层分析和底层分析的结果得到程序的最坏情况下的执行时间。实验表明,该方法可以使对实时Java程序的最坏情况执行时间预测更加安全和精确。(本文来源于《计算机工程与应用》期刊2010年18期）
吕鸣松[10]（2009）在《实时系统最坏情况执行时间分析技术的研究》一文中研究指出实时系统时间验证主要包括可调度性分析和最坏情况执行时间(WCET)分析。其中WCET分析的目的是计算实时任务在最坏情况下的执行时间,其结果是可调度性分析的重要输入。在硬实时系统中,为保证分析结果的安全性,通常采用静态方法分析程序的WCET。静态分析主要包括处理器行为分析、程序流分析和WCET计算叁个子任务。目前在WCET计算技术方面,隐式路径枚举技术是主导技术,但是该技术的主要问题是描述复杂程序控制流程信息的能力很有限,进而也限制了处理器行为分析所能采用的技术。在处理器行为分析方面,Cache分析一直是一个难度较大的任务。目前基于抽象解释技术的分析方法在分析LRU替换策略中占有主导地位,但是对于基于FIFO等其他替换策略的Cache行为的分析尚不成熟。随着处理器体系结构向多核发展,共享Cache成为了主要的设计趋势之一。不同核心上的程序在共享Cache中相互干涉,给Cache分析带来了极大的挑战。此外,随着WCET分析技术的不断发展,相关技术在实际系统中的可用性问题也逐渐受到越来越多的关注。基于上述研究现状,本文针对WCET静态分析中的WCET计算、单核与多核Cache行为分析、实时操作系统WCET分析等课题进行了深入研究。主要工作包括如下几点：(1)提出了一种全新的基于模型检测技术的WCET计算方法,设计了从程序到对应自动机模型的转换语义。该方法作为静态WCET分析的基础性框架,充分利用了模型检测技术搜索最优解的能力,使得分析结果具有更高的精度。探索了采用不同工作原理的模型检测器用于WCET计算的时间可伸缩性和空间可伸缩性,给出了基于模型检测技术的WCET计算方法的适用范围。(2)提出了一种基于剪枝思想的单核系统Cache分析方法。在基于模型检测技术的WCET计算框架的基础上,研究了利用这一技术对单核系统中采用FIFO替换策略的Cache进行分析的方法。针对模型检测技术在WCET分析中可能出现的状态空间爆炸问题,提出了基于剪枝思想的分析方法。该方法通过削减程序模型中符合特定条件的程序分支,能够在不损失分析精度的前提下,有效提高分析的性能以及可伸缩性。(3)提出了一种面向多核共享Cache的处理器行为分析方法。分析多核系统的共享Cache,关键在于对程序间的干涉情况进行精确的分析。现有的方法在分析这一问题的过程中只考虑了不同核心上的程序在地址上的冲突情况,导致分析结果的过度估计过高。本文采用模型检测技术对多核共享Cache的行为进行建模,模型能够在更细的粒度上挖掘冲突发生的时间关系,从而大大提高了分析的精确性。(4)对工业界广泛使用的μC/OS-Ⅱ实时操作系统进行了WCET分析。实时操作系统以控制密集型代码为主,其代码结构和时间行为特性与普通应用程序有很大区别。本文对μC/OS-Ⅱ实时操作系统的系统调用和禁止中断区间进行了静态WCET分析,详细分析了传统技术在分析实时操作系统代码时的精度以及尚存在的主要问题。同时,实验结果本身就是对μC/OS-Ⅱ实时操作系统实时特性的一个完整的量化描述,它对于使用者了解该系统的时间特性,以及对于系统开发者改善系统的实时性能都具有重要的应用价值。(5)本文在新加坡国立大学开发的Chronos工具的基础上,设计并实现了一个支持多核体系结构的静态WCET分析工具,实现了本文所提出的基于模型检测技术的WCET计算方法、基于FIFO替换算法的单核Cache行为分析、面向多核共享Cache的处理器行为分析、实时操作系统WCET分析等具体技术和方法,并验证了这些方法的正确性和有效性。总之,本文研究了采用模型检测技术进行静态WCET分析的问题,实验表明采用这种技术能够有效的提高静态分析的精确性。同时还探讨了采用静态WCET分析方法分析实时操作系统的可行性及主要问题。本文的研究对于静态WCET分析以及WCET分析可用性等领域的研究具有一定的参考价值。(本文来源于《东北大学》期刊2009-11-02）
最坏情况下执行时间论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对现有嵌入式系统最坏执行时间(WCET)的静态分析方法效率低下问题,利用最小传播算法对程序流进行分析,获得程序中每一个基本块的最小树约束,通过象征性循环上界约束对所求函数中的内部循环变量进行再次约束,并结合最小树约束获得程序的WCET表达式。使用静态预估分析方法对每一个基本块的底层指令周期进行绝对估值,将底层指令周期代入WCET表达式计算出程序最终的WCET值。实验结果表明,与基于程序控制流程图的程序执行时间静态分析方法相比,该方法在保证程序分析精度的同时,大幅提高了分析效率。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最坏情况下执行时间论文参考文献
[1].孟凡奇.面向软件开发初期的最坏情况执行时间快速估计与优化[D].哈尔滨工业大学.2018
[2].李军义,李双,张焱,李仁发.基于MPA与静态预估的最坏执行时间分析方法[J].计算机工程.2015
[3].殷锋社,汤小明.实时系统最坏执行时间分析及测试[J].电子测试.2013
[4].黎嘉翰.基于抽象分析的最坏执行时间分析技术[D].电子科技大学.2013
[5].汤森森.任务最坏执行时间分析与任务调度检测仿真工具的实现[D].电子科技大学.2012
[6].曾辉.最小化最坏执行时间的指令缓存锁定算法[J].武汉大学学报(理学版).2010
[7].张保民,吴国伟,姚琳.程序最坏执行时间极值统计方法[J].计算机工程与应用.2010
[8].吴国伟,姚琳,岳峰.一种快速程序最坏执行时间分析方法研究[J].计算机工程与应用.2010
[9].吴国伟,李张.一种精确程序最坏执行时间分析方法[J].计算机工程与应用.2010
[10].吕鸣松.实时系统最坏情况执行时间分析技术的研究[D].东北大学.2009