基于分布函数的程序执行时间的静态预估

CPU体系结构越来越复杂,令传统的程序最大执行时间分析（worse case execution time,WCET）方法越来越难准确估计出程序运行时间.而基于分布函数的WCET就是从概率角度,宏观上把握程序运行时间区间,绕过复杂的底层硬件特性.分别用贝塔分布和正态分布模拟8087指令的运行时间,进行指令叠加后用正态分布模拟整个程序的运行时间;实验结果表明,基于分布函数的程序执行时间预估方法是可行的;最后对估计出来的时间区间作了调整.     

一种精确程序最坏执行时间分析方法

Java语言的动态特性使程序的最坏执行时间分析较悲观和难以预测,提出一种精确最坏执行时间分析方法,在高层分析中,引入一种标记方法,对带有标记的Java类文件进行反编译提取控制流程,得到每一个基本块中的Java 字节码指令的最坏情况下的执行次数,在底层分析中,建立结合流水线和高级缓存影响的时间模型,得到每条指令所对应的执行时间,最后结合高层分析和底层分析的结果得到程序的最坏情况下的执行时间。实验表明,该方法可以使对实时Java 程序的最坏情况执行时间预测更加安全和精确。     

程序最坏执行时间极值统计方法

程序的最坏执行时间WCET是实时系统时间操作方面的可信基础,现有的WCET静态分析方法都需要对系统某种程度上的额外知识和限定性假设,导致现有的WCET分析方法本质上为偏高估计,降低了资源的利用率和系统的性能。给出一种基于极值统计的程序最坏执行时间估计新方法,采用程序执行时间的测量值作为样本,利用Gumbel分布建立程序最坏执行时间统计模型,根据测量样本序列预测执行时间的最大值,与以往的方法相比,这种方法综合体现了各种硬件特性对程序执行时间的影响,估计结果更为精确,更适合处理硬件特性和软件复杂度较高情况下的程序最坏执行时间估计。实验结果表明利用Gumbel分布建立的WCET估计模型能够快速且有效地给出实时程序的最坏执行时间估计。     

一种面向实时系统的程序基本块指令预取技术

面向通用计算机系统的指令预取技术无法满足实时系统的应用需求,其中一个重要原因是：无效预取引起的指令Cache内容污染使得实时任务WCET评估值不够精确,导致系统可调度性下降,严重影响系统效率.以简化实时任务WCET分析、降低任务WCET评估值为目标,提出一种基于程序基本块的指令预取方法.该方法以基本块为粒度执行指令预取,避免了传统指令预取技术引入的无效预取;通过简化最坏情况下的指令访问命中/缺失情况判定,简化任务WCET分析过程并优化WCET评估值.实时基准测试程序评估结果表明：与常规无预取方法相比,该预取方法可使实时任务WCET评估值降低约20%,平均执行情况下的指令Cache访问性能提升约10%.     

一种基于子结构分析的基本块重排算法

基本块重排是一类通过重新排布基本块在存储中的位置,以减少转移开销和指令cache失效率的编译优化技术.介绍了一种基于子结构分析的基本块重排算法.该算法通过统计剖视信息中控制流图的边执行频率,基于处理器转移预测策略构建转移开销模型和基本块排布收益模型.算法采用局部子结构优化的策略,改善基本块在存储中的排列顺序,从而减少转移开销,并提高指令cache的使用率,改善程序的总体性能.在UniCore处理器平台上进行了实验.实验结果表明,与其他基本块重排算法相比,该基本块重排算法在更大程度上减少转移开销和指令cache失效率的同时,其时间复杂度保持为O(n×logn).     

基于程序周期行为的快速模拟方法

提出了一种基于程序周期行为的快速模拟方法,通过对基本块执行次数和基本块跳转关系进行统计采样和分类,选择有代表性的程序片段来执行,能够在保证模拟精度的同时极大地缩短模拟时间。实验结果表明,在模拟了龙芯2号微体系结构的sim-godson模拟器上,采用这种方法SPEC2000测试程序可以在1h内运行完,误差率不超过5%。     

WCET可预测的Java指令集硬件实现

为能以硬件方式直接执行CISC结构的Java字节码,设计并实现适用于32位嵌入式实时Java平台的JPOR-32指令集。分析Java虚拟机规范中各Java字节码的功能和实现原理,设定执行每条指令时信号和数据在Java处理器数据通路上的变化,采用微指令方式执行复杂指令,简单指令直接执行,从而使JPOR-32的指令集具有RISC特性。实验结果验证了指令集的正确性及其最坏情况执行时间(WCET)的可预测性。     

基于动态分析的底层虚拟机混淆器反混淆方法

底层虚拟机混淆器(OLLVM)是一个著名的代码混淆工具,除了用于保护商业软件的安全外,也被恶意代码的开发者所利用,以此增加分析难度。为便于安全研究人员对ARM恶意程序进行分析,提出并实现了基于动态分析的OLLVM自动化反混淆方法。对于虚假控制流,根据不透明谓词的内存特征监控内存读写并利用动态污点分析技术识别虚假控制流来完成反混淆;对于控制流平坦化,通过动态运行程序并记录基本块的执行顺序来完成反混淆;同时利用多执行路径构造来提高代码覆盖率,最后通过指令修复还原基本块之间的关系。实验结果表明,该方法可准确消除可执行程序中因混淆产生的条件分支,且反混淆后得到的程序其运行结果与未混淆的程序保持一致,能有效完成对ARM混淆程序的反混淆工作。     

基于WCET的SPM实时性管理策略

提出一种基于最坏情况执行时间(WCET)的SPM静态分配算法,该算法采用额外的WCET分析工具获得任务最坏情况执行路径(WCEP),针对最坏情况执行路径,把程序划分为全局变量、全局堆栈、指令块等节点,用包含节点和节点间关系的CFG描述应用程序,采用考虑节点间关系的算法把选中的节点分配到SPM中。仿真实验结果表明,采用该分配策略管理SPM空间比不采用SPM时的实时性提高54%左右。     

可平台迁移的最坏执行时间分析

当前的很多最坏执行时间分析工具都是针对特定的编程语言或特定的编译器的,因而缺乏平台间的迁移性,从而不能被广泛使用.介绍了一种基于Java字节码的可平台迁移的最坏执行时间分析方法.该分析方法包括两方面：一是对字节码（javabyte code）的高层分析,提取出程序数据流和控制流信息;二是对Java虚拟机的底层分析,获得虚拟机的时间模型.最后这两种分析结合得到程序的最坏执行时间.同时还探讨了将来的研究方向.     

An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution

Previously published methods for estimation of the worst-case execution time on high-performance processors with complex pipelines and multi-level memory hierarchies result in overestimations owing to insufficient path and/or timing analysis. This does not only give rise to poor utilization of processing resources but also reduces the schedulability in real-time systems. This paper presents a method that integrates path and timing analysis to accurately predict the worst-case execution time for real-time programs on high-performance processors. The unique feature of the method is that it extends cycle-level architectural simulation techniques to enable symbolic execution with unknown input data values; it uses alternative instruction semantics to handle unknown operands. We show that the method can exclude many infeasible (or non-executable) program paths and can calculate path information, such as bounds on number of loop iterations, without the need for manual annotations of programs. Moreover, the method is shown to accurately analyze timing properties of complex features in high-performance processors using multiple-issue pipelines and instruction and data caches. The combined path and timing analysis capability is shown to derive exact estimates of the worst-case execution time for six out of seven programs in our benchmark suite.     

ROPDetector:一种基于硬件性能计数器的ROP攻击实时检测方法

面向返回编程(Return-Oriented Programming,ROP)是针对软件漏洞利用最广泛的攻击技术之一,能够绕过数据执行保护、地址空间布局随机化等防御机制.本文提出了一种基于硬件的ROP攻击实时检测方法,在不需要任何边缘信息(如源代码、编译器支持)和二进制重写的情况下,利用现代CPU中的硬件性能计数器监控...     

基于FPGA的多操作位逻辑运算控制器的设计

提出了应用FPGA设计可执行多操作位逻辑运算控制器的思路,该控制器接收到逻辑运算命令与多操作位后,在内部时序脉冲作用下,可以自主完成PLC逻辑运算指令的功能,运算结果传输到系统数据总线.设计多操作位逻辑运算的PLC指令,论述了该控制器的电路构成和基本原理,分析指令在内部时序脉冲作用的执行过程并给出了流程图,应用Verilog HDL语言实现相关硬件的构建和连接,应用梯形图程序进行仿真测试.测试表明:该控制器可以自主完成每条指令的运算,实现了逻辑运算指令的执行与系统其他功能模块的并行处理,提高了PLC执行指令序列的速度.     

LDMBL: An architecture for reducing code duplication in heavyweight binary instrumentations

Emergence of instrumentation frameworks has vastly contributed to the software engineering practices. As the instrumentation use cases become more complex, complexity of instrumenting programs also increases, leading to a higher risk of software defects, increased development time, and decreased maintainability. In security applications such as symbolic execution and taint analysis, which need to instrument a large number of instruction types, this complexity is prominent. This paper presents an architecture based on the Pin binary instrumentation framework to abstract the low‐level OS and hardware‐dependent implementation details, facilitate code reuse in heavyweight instrumentation use cases, and improve instrumenting program development time. Instructions of x86 and x86‐64 hardware architectures are formally categorized using the Z language based on the Pin framework API. This categorization is used to automate the instrumentation phase on the basis of a configuration list. Furthermore, instrumentation context data such as register data are modeled in an object‐oriented scheme. This makes it possible to focus the instrumenting program development time on writing the essential analysis logics while access to low‐level OS and hardware dependencies are streamlined. The proposed architecture is evaluated by instrumenting 135 instruction types in a concrete symbolic execution engine, resulting in a reduction of the instrumenting program size by 59.7%. Furthermore, performance overhead measure against the SPEC CINT2006 programs is limited to 8.7%.     

基于QEMU的高效指令追踪技术

系统模拟器通过模拟处理器、内存、外设等硬件资源创建一个完整的虚拟计算机环境, 支持运行和调试不同架构的软件, 可大大缩短跨架构的软件开发周期. 模拟器的调试模块通常具有指令追踪功能, 可记录程序运行的指令序列以用于进一步分析, 如程序运行时间评估、程序行为模式分析、软硬件联合仿真等. 支持RISC-V架构的主流模拟器QEMU和Spike均具有指令追踪功能, 但其时间和空间开销过大, 在应对规模较大的应用时效率低下. 本文提出了一种基于QEMU的指令追踪技术, 将程序中的基本块、控制流图等静态信息与分支选择等动态信息解耦, 在保证指令序列不失真的同时高效追踪执行序列. 相比QEMU原生实现的指令追踪, 本文提出的指令追踪技术的时间开销平均降低了80%以上, 空间开销平均降低了95%以上. 此外, 本文面向RISC-V架构, 实现了多种场景下的指令序列离线分析, 包括指令分类统计、程序热点标记、行为模式分析等.     

A comparison of instruction memories from the WCET perspective

Hard real-time systems demand high performance in combination with a timing predictable program execution. The performance of a system in the worst-case, represented by its worst case execution time (WCET), highly depends on the design of the memory subsystem. In this paper we focus on the instruction memory hierarchy and quantify the impact of different on-chip instruction memories on the worst-case timing of the system. A function-based dynamic instruction scratchpad (D-ISP), an instruction cache, and static instruction scratchpads using basic-block-based and function-based assignment algorithms are compared. Therefore, we provide WCET bounds for systems with different on-chip instruction memories and different off-chip memory timings.We show that for small memory sizes a static instruction scratchpad usually outperforms the other memories in terms of the WCET estimate. However, with increasing memory sizes the D-ISP is able to reach lower WCET bounds. An instruction cache can only provide lower WCET bounds than the other memories, if no suitable assignment for the static instruction scratchpads is found or if the D-ISP suffers from thrashing or frequently loads unused code.     

Hardware-Based Profiling: An Effective Technique for Profile-Driven Optimization

Profile-based optimization can be used for instruction scheduling, loop scheduling, data preloading, function in-lining, and instruction cache performance enhancement. However, these techniques have not been embraced by software vendors because programs instrumented for profiling run significantly slower, an awkward compile-run-recompile sequence is required, and a test input suite must be collected and validated for each program. This paper introduces hardware-based profiling that uses traditional branch handling hardware to generate profile information in real time. Techniques are presented for both one-level and two-level branch hardware organizations. The approach produces high accuracy with small slowdown in execution (0.4%–4.6%). This allows a program to be profiled while it is used, eliminating the need for a test input suite. With contemporary processors driven increasingly by compiler support, hardware-based profiling is important for high-performance systems.