基于K Framework的向量化机器学习指令语义形式化

ARM针对ARMv8.1-M微处理器架构推出基于M-Profile向量化扩展方案的技术,并命名为ARM Helium,声明能为ARM Cortex-M处理器提升达15倍的机器学习性能.随着物联网的高速发展,微处理器指令执行正确性尤为重要.指令集的官方手册作为芯片模拟程序,片上应用程序开发的依据,是程序正确性基本保障.主要介绍利用可执行语义框架K Framework对ARMv8.1-M官方参考手册中向量化机器学习指令的语义正确性研究.基于ARMv8.1-M的官方参考手册自动提取指令集中描述向量化机器学习指令执行过程的伪代码,并将其转换为形式化语义转换规则.通过K Framework提供的可执行框架利用测试用例,验证机器学习指令算数运算执行的正确性.     

一种基于语义的安全协议形式化模型

在分析实际网络环境中安全协议的运行特点之后,提出了安全协议建模分析的两点基本假设.在此基础上,提出了一种基于语义的安全协议形式化模型,具体包括基于角色事件的协议静态描述模型和基于运行状态的协议动态执行模型,给出了模型的基本语法及形式语义,明确了模型推理过程中涉及到的一些关键性概念,并以简化的NSL协议为例进行了说明,为实现自动化验证打下了必要的基础.     

字节码虚拟机的构造和验证

提出一种虚拟机构造和验证方案.给出字节码程序运行环境BVM(bytecode virtual machine)的形式化定义;采用X86机器语言构造虚拟机CertVM(certified virtual machine);并证明该虚拟机实现符合相应程序规范并和BVM之间具有模拟关系.利用辅助工具Coq给出证明,所有证明均可机器自动检查.CertVM确保在硬件环境满足其语义规范的情况下,已验证的字节码程序能够在给定虚拟机环境中正常运行.给出的方案不仅为虚拟机验证提供理论基础,而且为可信软件构造提供了一种有益的尝试.     

基于CK610的Dalvik虚拟机移植与优化

研究Android系统专属的Dalvik虚拟机,分析Dalvik虚拟机的解释器、本地方法桥以及C库在CK610平台上的移植与优化。基于Dalvik虚拟机解释器的字节码分发机制,提出一种改进型Threaded分发机制,并实现硬件平台定制型MInterp解释器,实验证明该 MInterp解释器能使Dalvik虚拟机的运行速度提升1倍以上。     

元模型层次的UML动态子图到Coq形式规范的转换

UML动态子图主要包括序列图和状态图等,它们在描述系统的行为方面应用广泛,但是半形式化的语义使它们不能直接进行形式化验证。Coq是目前主流的交互式定理证明器,用形式化的Coq规范来描述UML动态子图模型,可以在此基础上进行对模型的属性进行验证等工作。基于现有工作,提出将UML动态子图模型转换为Coq形式规范的框架,在元模型层次给出状态图和序列图的转换规则,介绍算法和原型工具实现。这种元模型层次的转换方法,保证了转换前后的语法正确性,为进一步分析验证提供了基础。     

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

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

基于Trace合并和寄存器分配的Dalvik优化

Dalvik虚拟机作为Android系统上运行所有应用程序的基础,其性能瓶颈一直制约着Android系统的用户体验。通过研究Android系统中的Dalvik架构,分析其解释器和JIT模块的工作原理,发现热Trace选择过程中短Trace编译损耗大以及即时编译过程中寄存器分配不合理的情况。结合Java虚拟机技术和编译器技术,在现有热Trace选择和寄存器分配机制的基础上,提出基于Trace合并和寄存器分配的优化算法,在国产高性能嵌入式CPU CSKY体系下移植Dalvik虚拟机并实现了上述优化算法。通过实验证明优化后Dalvik执行Java程序的性能提高了近10%。     

操作系统汇编级形式化设计和验证方法

由于系统的巨大规模,操作系统设计和实现的正确性很难用传统的方法进行描述和验证.在汇编层形式化地对系统模块的功能语义进行建模,提出一种汇编级的系统状态模型,作为汇编语言层设计和验证的纽带.通过定义系统状态模型的合法状态和状态转换函数来建立系统状态模型的论域,并以此来描述汇编层的论域.通过验证汇编层的功能模块的正确性来保证汇编语言层设计的正确性,达到对系统功能实现的正确性验证.同时,使用定理证明工具Isabelle/HOL来形式化地描述这一系统状态模型,基于这一形式化模型,在Isabelle/HOL中验证系统模块的功能语义的正确性.以实现的安全可信OS（verified secure operating system,简称VSOS）为例,阐述了所提出的形式化设计和验证方法,说明了这一方法的可行性.     

基于指令交换的代码混淆方法

软件程序是按一定顺序排列的指令序列,指令的排列组合构成了千变万化的程序语义.指令顺序重排通常会相应地导致程序语义的变化,通过分析相邻指令序列的相对独立性,可以在不影响程序语义的前提下交换相邻指令序列,增大指令距离,改变程序特征,在一定程度上增加逆向分析代价.通过改进程序的形式化定义论证相邻指令交换的充分条件,采用模拟退火算法实现随机化的指令乱序混淆方法,并将指令乱序方法与虚拟机代码保护技术融合,实现基于指令乱序的虚拟机代码保护系统IS-VMP,使用加密算法实例进行系统测试,验证了指令乱序混淆算法的可行性与有效性.     

具有冲突约束的RBAC模型的形式化规范与证明

在实际应用"基于角色的访问控制"(RBAC)模型时,经常遇到由于责任分离等策略而引起的冲突问题,如权限间的互斥等.访问控制操作应满足某些约束条件,以避免冲突的存在.但这些冲突关系相当复杂,如何检测出冲突问题是模型安全实施的重要保证.借助Z语言,提出了基于状态的RBAC形式化模型,对状态转换函数进行了形式化规范,描述了操作的具体内容和应满足的冲突约束条件.根据安全不变量给出了安全性定理,分别进行数学的和形式化的证明.最后,通过实例分析,说明在实际系统中,如何形式化规约和验证RBAC系统并检测出冲突问题,从而为今后使用RBAC模型开发具有高安全保证的系统提供了一种形式化规范和证明方法.     

一种基于活性顺序图的运行时验证研究

运行时验证是一种轻量级的形式化验证方法,使用可视化的需求规约描述语言建模需求规约场景是运行时验证领域的研究热点。针对目前基于活性顺序图的运行时验证方法中容易产生冗余性质、二值语义的验证结果不准确、基于Maude工具引擎的重写逻辑验证算法效率较低等问题,提出一种基于活性顺序图的运行时验证的改进方法,以支持现有的运行时验证技术。实验表明,改进方法验证结果准确,且验证过程开销较小。     

基于时序描述逻辑的UML状态图语义

将UML图形转换成形式化规范是一种精确UML语义、扩大形式化软件方法适用范围的有效途径。鉴于描述逻辑强的可判定推理能力,提出一种采用时序描述逻辑形式化UML状态图,对描述逻辑进行时序扩展,得到可以表示动态和时序语义的形式化规范——时序描述逻辑,给出一套UML状态图向时序描述逻辑表达式转换的规则,通过实例验证了该方法的可行性。     

基于UML的形式化规范说明研究

软件的规范说明阶段 ( specification phase)对于软件的整体开发过程来说是一个非常重要的阶段 ,UML方法是目前比较流行的软件工程开发方法 ,它对软件整体开发过程提供了一套有用的模型。本文根据 UML和谓词转换 ,提出一种面向对象的形式化规范说明方法 ,并给出一组和 UML相对应的数学模型。本文的方法吸收了 UML和一般形式化方法的优点 ,具有数学的严谨性和精确性 ,并且更加易于理解和表达。     

UML状态机的形式语义

许多大型系统在进行分析和设计时,均采用UML作为需求描述语言,尤其是一些对安全性要求较高的系统,更是广泛采用UML的动态行为描述机制--状态机来描述协议及控制机制.但是,由于UML没有形式化的动态语义,不利于对其所描述的需求进行形式化验证和证明.为了解决这一问题,采用以下方法为UML状态机构建形式语义.把UML状态机中的状态映射到一种项代数上,用归纳的状态项表示状态机的状态.然后,把状态项映射到一种加标记的变迁系统LTS上,LTS-状态是状态机的状态项,LTS-变迁是UML状态机的微步.最后,用Plotk     

Runtime monitoring and verification of systems with hidden information

This paper describes a technique for runtime monitoring (RM) and runtime verification (RV) of systems with invisible events and data artifacts. Our approach combines well-known hidden markov model (HMM) techniques for learning and subsequent identification of hidden artifacts, with runtime monitoring of probabilistic formal specifications. The proposed approach entails a process in which the end-user first develops and validates deterministic formal specification assertions, s/he then identifies hidden artifacts in those assertions. Those artifacts induce the state set of the identifying HMM. HMM parameters are learned using standard frequency analysis techniques. In the verification or monitoring phase, the system emits visible events and data symbols, used by the HMM to deduce invisible events and data symbols, and sequences thereof; both types of symbols are then used by a probabilistic formal specification assertion to monitor or verify the system.     

Goto and Concurrency Introducing Safe Jumps in Esterel

Esterel is a design language for the specification of real time embedded systems. Based on the synchronous concurrency paradigm, its semantics describes execution as a succession of instants of computation. In this work, we consider the introduction of a new gotopause instruction in the language, which acts as a non-instantaneous jump instruction compatible with concurrency. It allows the programmer to activate state control points anywhere in the program, from where the execution is resumed in the next instant. In order to provide the formal semantics of the extended language, we first define a state semantics of Esterel, which we prove observationally equivalent to the original logical behavioral semantics. Including gotopause in the state semantics is then straightforward. We sketch two key applications of our new primitive: a direct encoding of automata and a quasi-linear rewriting of programs eliminating schizophrenic behaviors.     

基于一致性测试理论的Statechart描述的测试用例自动生成

本文研究Statechart描述的测试语义和测试用例的自动生成.基于Tretmans的从标记转换系统描述自动生成测试用例的方法,我们研究如何从Statechart描述自动生成测试用例.本文的主要贡献在于建立了基于Statechart描述的一致性测试和测试用例生成的形式化基础.为Statechart描述建立了形式化测试语...     

Bridging the gap between formal semantics and implementation of triple graph grammars

The correctness of model transformations is a crucial element for model-driven engineering of high-quality software. A prerequisite to verify model transformations at the level of the model transformation specification is that an unambiguous formal semantics exists and that the implementation of the model transformation language adheres to this semantics. However, for existing relational model transformation approaches, it is usually not really clear under which constraints particular implementations really conform to the formal semantics. In this paper, we will bridge this gap for the formal semantics of triple graph grammars (TGG) and an existing efficient implementation. While the formal semantics assumes backtracking and ignores non-determinism, practical implementations do not support backtracking, require rule sets that ensure determinism, and include further optimizations. Therefore, we capture how the considered TGG implementation realizes the transformation by means of operational rules, define required criteria, and show conformance to the formal semantics if these criteria are fulfilled. We further outline how static and runtime checks can be employed to guarantee these criteria.