Dissertation > Excellent graduate degree dissertation topics show

Clocks Manipulation Applying to the Formal Verificationof Timed System

Author: GuiYaYun
Tutor: XuQingGuo
School: Shanghai University
Course: Computer Software and Theory
Keywords: Timed automaton Property Verification Model Checking SimulationGraph Emptiness Checking
CLC: TP301.1
Type: Master's thesis
Year: 2013
Downloads: 1
Quote: 0
Read: Download Dissertation

Abstract


The real-time system is a way to specify that the system completes the functionswithin adetermined time, and make a timely response to external and internal random events insynchronous or asynchronous time. Currently, the real-time system has been involved in the vastmajority fields, for example the application of embedded systems in our daily life and militaryfields. Since embedded systems are not closed system, theyare often in a larger systemand play amajor impact on the entire system by controlling system operation. Almost all of the safety-criticalsystems and most embedded systems are real-time systems. Therefore, it ismeaningfulandimportant toensure the correctness of real-time system design.In order to ensure the correctness of the system design, we are needed to checkwhether thesystem model satisfies certain property or not. Due to the introduction of thereal-valued time,formal verification fortime systems is more challenging. Because clock value is continuous andmonotonically increasing, the real-time system state space is infinite and the traditional untimedsystem verification methodsare not suitable for the real-time system verification. Simulationgraphof the real-time system is a zone-based transition system. According to region equivalence,the infinite state space is equivalentlydivided into a finitestate space. In this thesis, we use regionconstruction technology to solve thestate space explosion problem, and propose a verificationframework PVofTA which automatically check the required properties of the real-time systembased on the simulation graph technology.Thespecificworkis as following:Firstly, under the preliminary work of ourresearch group, FormalVerification ofTimeAutomatonframework which is short for FVofTA and the based-on predicate abstractionverification template oftimed automata ExTA,we further analysis the syntax oftimed automata andthesemantics ofits transition system and associated properties, specially the clock constraints andzones which are present as Difference Bound Matric and tightened to canonical form, to make itmore conducive to application and automation in practice.Secondly,on the basis of research work on the TBA’s emptiness checkingand the simulationgraph technology,we propose areal-time system verification framework to automaticallycheck thesatisfaction of its properties. By the definition of product automata, we calculate the productautomaton of the whole real-time system by synchronizing the subsystems and at the same time,withforward calculation operator Post, we calculate the simulation graph of the product automatonby starting from the initial node. The liveness property and reachability property are twofundamental properties for real-time system. Therefore, according to some researches, the propertychecking of the real-time system can be converted into some state’s reachability checking or thesimulation graph’s emptiness checkingfor lasso paths. By the way,we also give the details of theproduct automata and simulation graph calculation process through specific examples.Finally, given the verification framework, we implement the templates with use of theadvanced language technology and check them on a specific example, the classical real-timesystem"Railway Crossing System", to further verify the feasibility and practicality of theframework.In summary, to resolve the system state space explosion problem, this paperanalyze and research on the region construction and simulation graph. On the basis of above work, we proposea verification framework for the property satisfaction checking of real-time system and then putthe framework in practice,check them on specific examples. All these work is aimed to automatizethe formal verification of real-time systems and improve the efficiency.

Related Dissertations

  1. Software Testing and Reliability Computing Based on Model Rebuilding,TP311.53
  2. Forecasting Model and Applied Research of Based on Time Series ARCH,O211.61
  3. Research and Implement on Static Malware Detection System Based on Program Semantics,TP393.08
  4. ParaModel system model validation and code generation framework,TP338.6
  5. Towards the Verification of Services Collaboration Based on Model Checking,TP311.52
  6. Based on the design and implementation of model checking , model-driven development system,TP311.52
  7. Research on Model Checking Based Software Analysis,TP311.52
  8. Program Validation Tool Based on Slice,TP311.52
  9. Model Extraction and Model Checking Research for Java Concurrent Programs,TP312.2
  10. Verification of Rules in Spatial Access Control Systems Through Model Checking,TP393.08
  11. The Application of Model Checking in Configuration,TP301.1
  12. Empirical Study of Service Quality of Software Technical Support,F407.672
  13. Research on Cooperative Epistemic Logics for Multi-Agent System,TP18
  14. Model Checking Propositional Projection Temporal Logic Based on SPIN,TP311.52
  15. UML - based security protocol modeling and automatic detection,TP311.52
  16. The Research and Implementation of Algorithms for Model-Checking Tool FPTAT for Real-Time Systems,TP311.5
  17. Planning Based on Model Checking,TP18
  18. Research and Implementation of Metadata Management Prototype Tool Based on CWM,TP311.13
  19. Formal Verification of Hybrid Systems and Its Application,TP13
  20. Property Checking of BPEL4WS Based on π-calculus,TP393.01
  21. Kunming eastern outskirts of landfill leachate diffusion mathematical model,X703

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Automata Theory
© 2012 www.DissertationTopic.Net  Mobile