Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent ...Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model （αPTL） which extends the projection temporal logic （PTL） to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.展开更多
Projection temporal logic(PTL) is an extension of interval temporal logic(ITL) with a new projection operator prj and infinite intervals which has been well investigated in the past ten years.In this paper,we review t...Projection temporal logic(PTL) is an extension of interval temporal logic(ITL) with a new projection operator prj and infinite intervals which has been well investigated in the past ten years.In this paper,we review the work on PTL in four aspects:(1) decidability,complexity and expressiveness of propositional PTL(PPTL);(2) modeling,simulation and verification language(MSVL);(3) formal verification approaches with MSVL and PPTL;and(4) supporting toolkit MSV.展开更多
The TLL XYZ/E is a formal language able to represent the dynamic semantics and the static semantics in a unified framework. It supports the whole process of program development, i.e. from the abstract specification to...The TLL XYZ/E is a formal language able to represent the dynamic semantics and the static semantics in a unified framework. It supports the whole process of program development, i.e. from the abstract specification to the efficiently executable program in a formal, precise and convenient way. The steam boiler control specification problem, a large case study in the fields of real time, hybrid and communication systems, is discussed with XYZ/E. The approach covers physical model construction, formal specification, stepwise refinement, verification, executable program and visual user interface programming.展开更多
Recurrent neural networks (RNNs) have been heavily used in applications relying on sequence data such as time series and natural languages. As a matter of fact, their behaviors lack rigorous quality assurance due to t...Recurrent neural networks (RNNs) have been heavily used in applications relying on sequence data such as time series and natural languages. As a matter of fact, their behaviors lack rigorous quality assurance due to the black-box nature of deep learning. It is an urgent and challenging task to formally reason about the behaviors of RNNs. To this end, we first present an extension of linear-time temporal logic to reason about properties with respect to RNNs, such as local robustness, reachability, and some temporal properties. Based on the proposed logic, we formalize the verification obligation as a Hoare-like triple, from both qualitative and quantitative perspectives. The former concerns whether all the outputs resulting from the inputs fulfilling the pre-condition satisfy the post-condition, whereas the latter is to compute the probability that the post-condition is satisfied on the premise that the inputs fulfill the pre-condition. To tackle these problems, we develop a systematic verification framework, mainly based on polyhedron propagation, dimension-preserving abstraction, and the Monte Carlo sampling. We also implement our algorithm with a prototype tool and conduct experiments to demonstrate its feasibility and efficiency.展开更多
模型检查是一种用于并发系统的性质验证的算法技术.LTLC(linear temporal logic with clocks)是一种连续时间时序逻辑,它是线性时序逻辑LTL的一种实时扩充.讨论实时系统关于LTLC公式的模型检查问题,将实时系统关于LTLC公式的模型检查化...模型检查是一种用于并发系统的性质验证的算法技术.LTLC(linear temporal logic with clocks)是一种连续时间时序逻辑,它是线性时序逻辑LTL的一种实时扩充.讨论实时系统关于LTLC公式的模型检查问题,将实时系统关于LTLC公式的模型检查化归为有穷状态转换系统关于LTL公式的模型检查,从而可以利用LTL的模型检查工具来对LTLC进行模型检查.由于LTLC既能表示实时系统的性质,又能表示实时系统的实现,这就使得时序逻辑LTLC的模型检查过程既能用于实时系统的性质验证,又能用于实时系统之间的一致性验证.展开更多
基金Acknowledgements We thank for anonymous referees for their suggestions and comments. This research was based on work supported by grants from Science Foundation of China Project （60833001, 61100063, 61073040 and 61103023）, and by a Humboldt Fellowship （X.Y.） from Alexander von Humboldt Foundation.
文摘Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model （αPTL） which extends the projection temporal logic （PTL） to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.
基金supported by the National Natural Science Foundation of China(Grant Nos.61133001,61272117,61202038,61322202,61420106004 and 91418201)
文摘Projection temporal logic(PTL) is an extension of interval temporal logic(ITL) with a new projection operator prj and infinite intervals which has been well investigated in the past ten years.In this paper,we review the work on PTL in four aspects:(1) decidability,complexity and expressiveness of propositional PTL(PPTL);(2) modeling,simulation and verification language(MSVL);(3) formal verification approaches with MSVL and PPTL;and(4) supporting toolkit MSV.
文摘The TLL XYZ/E is a formal language able to represent the dynamic semantics and the static semantics in a unified framework. It supports the whole process of program development, i.e. from the abstract specification to the efficiently executable program in a formal, precise and convenient way. The steam boiler control specification problem, a large case study in the fields of real time, hybrid and communication systems, is discussed with XYZ/E. The approach covers physical model construction, formal specification, stepwise refinement, verification, executable program and visual user interface programming.
基金supported by the National Natural Science Foundation of China under Grant Nos.61872371,62032024,and U19A2062the Open Fund from the State Key Laboratory of High Performance Computing of China(HPCL)under Grant No.202001-07.
文摘Recurrent neural networks (RNNs) have been heavily used in applications relying on sequence data such as time series and natural languages. As a matter of fact, their behaviors lack rigorous quality assurance due to the black-box nature of deep learning. It is an urgent and challenging task to formally reason about the behaviors of RNNs. To this end, we first present an extension of linear-time temporal logic to reason about properties with respect to RNNs, such as local robustness, reachability, and some temporal properties. Based on the proposed logic, we formalize the verification obligation as a Hoare-like triple, from both qualitative and quantitative perspectives. The former concerns whether all the outputs resulting from the inputs fulfilling the pre-condition satisfy the post-condition, whereas the latter is to compute the probability that the post-condition is satisfied on the premise that the inputs fulfill the pre-condition. To tackle these problems, we develop a systematic verification framework, mainly based on polyhedron propagation, dimension-preserving abstraction, and the Monte Carlo sampling. We also implement our algorithm with a prototype tool and conduct experiments to demonstrate its feasibility and efficiency.
基金Supposed by the National Natural Science Foundation of China under Grant Nos.6053406060473094(国家自然科学基金)+3 种基金the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z136(国家高技术研究发展计划(863))the National Basic Research Program of China under Grant No.2003CB317002(国家重点基础研究发展计划(973))the 2006 Mountaineering Program ofShanghaiChina under Grant No.06JC14065(上海市科委2006年度"登山行动计划")
文摘在对当前面向服务体系架构(service-oriented architecture,简称SOA)研究的基础上,给出了一个以企业服务总线(enterprise service bus,简称ESB)为中心的面向服务软件体系架构参考模型(SOA reference model,简称SOARM),是集Petri网和时序逻辑于一体的形式化SOA分析、验证和确认方法.基于以客户为中心的面向服务架构设计理念,即根据用户提出系统规范/需求,服务提供者提供服务或组合服务来满足服务消费者,服务接口和ESB作为实现面向服务架构的关键部分.虚拟计算环境下,服务语义的一致性验证是十分必要的,SOARM采用新的模式:通过Petri网为服务的行为建模,时序逻辑来描述服务语义一致性约束,综合运用分而治之的精炼检测思想和SOA模型检测合成方法,通过对这些子服务性质的检验来验证整个系统的规范.用商业银行综合前置系统说明了如何使用这种方法来实现面向服务的设计.
文摘模型检查是一种用于并发系统的性质验证的算法技术.LTLC(linear temporal logic with clocks)是一种连续时间时序逻辑,它是线性时序逻辑LTL的一种实时扩充.讨论实时系统关于LTLC公式的模型检查问题,将实时系统关于LTLC公式的模型检查化归为有穷状态转换系统关于LTL公式的模型检查,从而可以利用LTL的模型检查工具来对LTLC进行模型检查.由于LTLC既能表示实时系统的性质,又能表示实时系统的实现,这就使得时序逻辑LTLC的模型检查过程既能用于实时系统的性质验证,又能用于实时系统之间的一致性验证.
