The Library
Theoretical and practical tools for validating discrete and real-time systems
Tools
Qu, Hongyang (2005) Theoretical and practical tools for validating discrete and real-time systems. PhD thesis, University of Warwick.
|
PDF
WRAP_THESIS_Qu_2005.pdf - Submitted Version - Requires a PDF viewer. Download (1539Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b2072942~S1
Abstract
System validation has been investigated for a long time. Testing is used to find errors inside a system; in contrast, model checking is used to verify whether a given property holds in the system. Both methods have their own advantages and interact with each other. This thesis focuses on four methodologies for model checking and testing. In the end, they are integrated into a practical validating tool set, which is described in this thesis. Many techniques have been developed to manage the state space for a complicated system. But they still fail to reduce the state space for some large-scale concurrent systems. We propose using code annotation as a means of manually controlling the state space. This solution provides a trade-off between computability and exhaustiveness. When a suspicious execution is found either by testing or by model checking, it can be difficult to repeat this execution in a real environment due to nondeterministic choices existing in the system. We suggest enforcing a given execution by code transformation. In addition, we extend our method from a single path to partial order executions. In order to repeat at least one such execution, we need to provide appropriate values satisfying the path's initial precondition in its environment. It is easy to obtain the precondition in a discrete environment, but difficult in a real-time environment, especially for a partial order, since the computation would involve time constraints in the latter case. We present a real-time model first, and then a methodology to compute the precondition on this model. When every action in the system is associated with a probability density function, it is possible to calculate the probability of the occurrence of a particular execution. We give a method to calculate the probability by inte- gration on a group of independent continuous random variables, each of which is corresponding to an action either executed, or enabled but not fired. The research described in this thesis provides some new ideas for ap- plying formal methods to classical software development tools.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Computer programs -- Validation, Real-time data processing | ||||
Publisher: | Department of Computer Science | ||||
Place of Publication: | Coventry, UK | ||||
Official Date: | October 2005 | ||||
Dates: |
|
||||
DOI: | CS-RR-419 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Thesis Type: | PhD | ||||
Publication Status: | Published | ||||
Supervisor(s)/Advisor: | Peled, Doron | ||||
Extent: | xv, 244 leaves | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year