Communication protocols, a class of critical systems, play an important role in industry. These protocols are critical because the tolerance for faults in these systems is low and it is highly desirable that these systems work correctly. Therefore, an effective methodology for describing and verifying that these systems behave according to their specifications is vitally important. Model checking is a verification technique in which a mathematically precise model of the system, either concrete or with abstraction, is built and a specification of how the system should behave is given. Then the system is considered correct if its model satisfies its specification. However, due to their size and complexity, critical systems, such as communication systems, are notoriously resistant to formal modelling and verification. In this thesis, we propose using graph transformation systems (GTSs), a visual semantic modelling approach, to model the behaviour of dynamically evolving communication protocols. Then, we show how a GTS model can facilitate verification of invariant properties of potentially unbounded communication systems. Finally, due to the use of similar isomorphic components in communication systems, we show how to exploit symmetries of these dynamically evolving models described by GTSs, to reduce the size of the model under verification. We use graph transformation systems to provide an expressive and intuitive visual description of the system state as a graph and for the computations of the system as a finite set of rules that transform the state graphs. Our model is well-suited for describing the behaviour of individual components, error-free communication channels amongst the components, and dynamic component creation and elimination. Thus, the structure of the generated model closely resembles the way in which communication protocols are typically separated into three levels: the first describing local features or components, the second characterizing interactions among components, and the third showing the evolution of the component set. The graph transformation semantics follows this scheme, enabling a clean separation of concerns when describing a protocol. This separation of concerns is a necessity for formal analysis of system behaviour. We prove that the finite set of graph transformation rules that describe behaviour of the system can be used to perform verification for invariant properties of the system. We show that if a property is preserved by the finite set of transformation rules describing the system model, and if the initial state satisfies the property, then the property is an invariant of the system model. Therefore, our verification method may avoid the explicit analysis of the potentially enormous state space that the transformation rules encode. In this thesis, we also develop symmetry reduction techniques applicable to dynamically evolving GTS models. The necessity to extend the existing symmetry reduction techniques arises because these techniques are not applicable to dynamic models such as those described by GTSs, and, in addition, these existing techniques may offer only limited reduction to systems that are not fully symmetric. We present an algorithm for generating a symmetry-reduced quotient model directly from a set of graph transformation rules. The generated quotient model is bisimilar to the model under verification and may be exponentially smaller than that model.

Interactive theorem proving provides a general approach to modeling and verification of both finite-state and infinite-state systems but requires significant human efforts to deal with many tedious proofs. On the other hand, model-checking is limited to some application domain with small finite-state space. A natural thought for this problem is to integrate these two approaches. To keep the consistency of the integration and ensure the correctness of verification, we suggest to use type theory based theorem provers (e.g. Lego) as the platform for the integration and build a model-checker to do parts of the verification automatically. We formalise a verification system of both CCS and an imperative language in the proof development system Lego which can be used to verify both finite-state and infinite-state problems. Then a model-checker, LegoMC, is implemented to generate Lego proof terras for finite-state problems automatically. Therefore people can use Lego to verify a general problem with some of its finite sub-problems verified by LegoMC. On the other hand, this integration extends the power of model-checking to verify more complicated and infinite-state models as well. The development of automatic techniques and the integration of different reasoning methods would directly benefit the verification community. It is expected that further extension and development of this verification environment would be able to handle real life systems. On the other hand, the research gives us some experiences about how to automate proofs in interactive theorem provers and therefore will improve the usability and applicability of the theorem proving technology.

No description available.

Verification of the on-die power grid is a key step in the design of complex high performance integrated circuits. For the very large grids in modern designs, incremental verification is highly desirable, because it allows one to skip the verification of a certain section of the grid (internal nodes) and instead, verify only the rest of the grid (external nodes). The focus of this work is to develop efficient techniques for incremental verification in the context of vectorless constraints-based grid verification, under dynamic conditions. The traditional difficulty is that the dynamic case requires iterative analysis of both the internal and the external sections. A solution in the transient case is provided through two key contributions: 1) a bound on the internal nodes’ voltages is developed that eliminates the need for iterative analysis, and 2) a multi-port Norton approach is used to construct a reduced macromodel for the internal section.

Verification of the on-die power grid is a key step in the design of complex high performance integrated circuits. For the very large grids in modern designs, incremental verification is highly desirable, because it allows one to skip the verification of a certain section of the grid (internal nodes) and instead, verify only the rest of the grid (external nodes). The focus of this work is to develop efficient techniques for incremental verification in the context of vectorless constraints-based grid verification, under dynamic conditions. The traditional difficulty is that the dynamic case requires iterative analysis of both the internal and the external sections. A solution in the transient case is provided through two key contributions: 1) a bound on the internal nodes’ voltages is developed that eliminates the need for iterative analysis, and 2) a multi-port Norton approach is used to construct a reduced macromodel for the internal section.

Proof-carrying code is an application of software verification techniques to the problem of ensuring the safety of mobile code. However, previous proof-carrying code systems have assumed that mobile code will faithfully execute the instructions of the program. Realistic implementations of computing systems are susceptible to probabilistic behaviours that can alter the execution of a program in ways that can result in corruption or security breaches. We investigate the use of a probabilistic bytecode language to model deterministic programs that are executed on probabilistic computing systems. To model probabilistic safety properties, a probabilistic logic is adapted to out bytecode instruction language, and soundness is proven. A sketch of a completeness proof of the logic is also shown.

"January 2004" / Bibliography: leaves 183-198. / xv, 198 leaves : ill. ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / As no single specification or verification method is able to solve all classes of problems, especially with industrial-sized applications, a diversity of modelling languages and analysis techniques specialised and optimized for various domains is needed, along with the ability to use them in combination. The work presented in this thesis has concentrated on developing techniques to support the use of a combination of modelling languages, especially visual languages, for system specification. Also, in order to tackle the main obstacles of model checking and make it more accessible to and usable by practising engineers, this work has focused on providing lightweight but effective methods and tools to alleviate the state space explosion problem in model checking. / Thesis (Ph.D.)--University of Adelaide, School of Computer Science, 2004

Thesis (M.A.)--University of Wyoming, 2008. / Title from PDF title page (viewed on Mar. 23, 2010). Includes bibliographical references (p. 93-94).

Thesis (Ph. D.)--University of Wisconsin--Madison, 1973. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Bibliography: leaves 262-263.

In this thesis, we investigate model checking problems for parametric single-index regression models when the variables are measured with different types of errors. The large sample behaviours of the test statistics can be used to develop properly centered and scaled model checking procedures. In addition, a dimension reduction model-adaptive strategy is employed, with the special requirements for the models with measurement errors, to improve the proposed testing procedures. This makes the test statistics converge to their weak limit under the null hypothesis with the convergence rates not depending on the dimension of predictor vector. Furthermore, the proposed tests behave like a classical local smoothing test with only one-dimensional predictor. Therefore the proposed methods have potential for alleviating the difficulties associated with high dimensionality in hypothesis testing.. Chapter 2 provides some tests for a parametric single-index regression model when predictors are measured with errors in an additive manner and validation dataset is available. The two proposed tests have consistency rates not depending on the dimension of predictor vector. One of these tests has a bias term that may become arbitrarily large with increasing sample size, but has smaller asymptotic variance. The other test is asymptotically unbiased with larger asymptotic variance. Both are still omnibus against general alternatives. Besides, a systematic study is conducted to give an insight on the effect of the ratio between the size of primary data and the size of validation data on the asymptotic behavior of these tests. Simulation studies are carried out to examine the finite-sample performances of the proposed tests. Also the tests are applied to a real data set about breast cancer with validation data obtained from a nutrition study.. Chapter 3 introduces a minimum projected-distance test for a parametric single-index regression model when predictors are measured with Berkson type errors. The distribution of the measurement error is assumed to be known up to several parameters. This test is constructed by combining the minimum distance test with a dimension reduction model-adaptive strategy. After properly centering, the minimum projected-distance test statistic is asymptotically normal at a convergence rate of order nh^(1/2) and can detect a sequence of local alternatives distinct from the null model with a rate of order n^(-1/2) h^(-1/4) where n is the sample size and h is a sequence of bandwidths tending to 0 as n tends infinity. These rates do not depend on the dimensionality of predictor vector, which implies that the proposed test has potential for alleviating the curse of dimensionality in hypothesis testing in this field. Further, as the test is asymptotically biased, two bias-correction methods are suggested to construct asymptotically unbiased tests. In addition, we discuss some details in the implementation of the proposed tests and then provide a simplified procedure. Simulations indicate desirable finite-sample performances of the tests. Besides, we illustrate the proposed model checking procedures by using two real datasets to illustrate the effects of air pollution on Emphysema.. Chapter 4 provides a nonparametric test for checking a parametric single-index regression model when predictor vector and response are measured with distortion errors. We estimate the true values of response and predictor, and then plug the estimated values into a test statistic to develop a model checking procedure. The dimension reduction model-adaptive strategy is also employed to improve its theoretical properties and finite sample performance. Another interesting observation in this work is that, with properly selected bandwidths and kernel functions in a limited range, the proposed test statistic has the same limiting distribution as that under the classical regression setup without distortion measurement errors. Simulation studies are conducted.