Print Email Download Reference This Send to Kindle Reddit This
submit to reddit

Types and importances of formal methods

Formal Methods

1.1. Overview

The software engineers and designers always try to develop reliable and consistent software but the behavior of software is often a surprise for them. Mostly software systems fail and can not fulfill the requirements, there are many reasons of their failure but most of them fail due to incomplete and ambiguous requirement specification, which are hardly difficult to handle by using traditional software development process. Formal methods are used as an emerging technology which handles these problems in systematic way using logical arguments.

Formal methods [f-2] consist of the set of techniques and tools based on mathematical modeling and formal logic that are used to specify and verify requirements and designs for computer systems and software. Further, formal methods [f-3] refer to mathematical rigorous techniques and tools for the specification, design and verification of software and hardware systems. Single formal technique is not well suitable for all kinds of problems, therefore integration of methods in same time is necessary. Formal specification provides the power to clearly express the meanings, across natural languages barriers, just like legal languages, which were developed to prevent misinterpretation of law. Formal specification was developed to prevent misinterpretation of specifications [f-4].

1.2. Specification Techniques

Generally there are two classes of specification techniques as discussed in [14], which are given below.

Algebraic Specification: The system is specified in terms of its operations and their relationships for example larch [John], CCS [R. Milner] and OBJ [R. N. Shutt] etc.

Model-Based Specification: The system is specified in terms of a state model that is constructed using mathematical constructs such as sets and sequences. Operations are defined by modifications to the system's state. The major examples of model-based specification are PVS [S. Owre], CSP [Jim], VDM [language manual] and Z Notation [Jim wood cock].

1.3. Scope of the Formal Methods Use

Following are the three dimensions scope of the formal method use:

1. in all or selected stages of the software development life cycle, normally the larger pay off of formal methods occurs in the early stage of life cycle.

2. in all or customized component of systems, where critical assessments is essential.

3. full or customized system functionality. Although proofs and correctness are traditionally associated with formal methods to ensure that functional specification of system fulfill the requirement criteria. Formal methods are well applied to the most important properties of system.

1.4. Benefits of Formal Methods

Formal methods have number of benefits major of them are given below

* Formal methods eliminate the ambiguities, which are found inevitable in informal specifications. By eliminating these ambiguities readers and writes have consistency in understanding the specifications, and requirements are implemented accurately and correctly.

* Formal methods also provide formal proofs of the given formal specification that also remove the ambiguities from requirement analysis.

* The formal proofs and formal specification both provide repeatable and systematic approach for analysis.

* Formal methods provide the facility to complete the project on schedule time and also within budget.

* Formal specification and formal proofs both are applied in any stage of software development life cycle.

* The flow and syntax in formal proofs and formal specification can also be checked by computer based tool.

1.5. Classification of Formal Methods

Formal methods are used for both software and hardware designing or software- hardware co-designing. Classification of formal methods with respect to the use of it, is given below as discussed in [Klaus Schneider].

Writing Formal Specification: Formal methods are used to reason about mathematical objects. However, hardware circuits are not mathematical objects, they are real world physical objects. Therefore, it is necessary to develop mathematical model of system and also describe the properties of that system [r1]. The formal specification of a system is written in term of mathematical notation which is precise and unambiguous.

Proving Properties about the Specification: The requirement specification normally given in informal languages when we write it in formal specification language then this is an error-prone. This formal specification is used for proving the properties of the system. In [rr] A. Hall define it as:

"In informal specification, it is hard to tell what an error is because it is not clear what is being said, when challenged, people try to define their informal specification by reinterpreting it to meet the criticism. With a formal specification, we have found that errors are much more easily found and once they are found everyone is more ready to agree that they are error."

Deriving Implementation from a given Specification: Once the specification is written then it is helpful to design models which automatically derives the implementation of system with the full requirements. This idea actually belongs to the fifth generation of the programming language, i.e., PROLOG [Leon], where the implementation phase and system specification is very closely related to each other.

However, specifications are often given in a declarative manner and not in constructive manner. This means that these specifications only describe what the system should do but not how this function can be achieved. It is certainly impossible to derive correct program from declarative specification since these problems are inherently undecidable thus the machine can never solve them. Therefore, the construction of appropriate implementation always remains a creative task for human being [r1].

Verifying a specification w.r.t. a given implementation: It is possible that the description of the system which is automatically derived may be less detailed. However, the design steps that are used to refine the description of the system must not effect the validity of the system specification. However, it must be checked that the abstract implementations satisfy the original specification. This is a formal verification process. The formal verification can be applied in two different ways. One method is based on the automated theorem proving for the certain formal language. In 1980 another technique was developed which is called model checking. In model checking the description of the system is not given in the logic. The procedure of model checking is task to evaluate the specification in interpretation.

1.6. Types of Formal Methods

Following are some types of formal methods.

1.6.1. Sophistication-Based Formal Methods

Formal techniques can be heavy-duty or lightweight [type-1]. The light weight techniques [type-2] do not require advance mathematical background and theorem proving skills for usage of them. Formal methods techniques that include the feature of light weight are Z notation and VDM tools. The heavy-duty approach of formal methods is uses advance mathematic and theorem proving skills PVS and Acl2 [Jose] are examples of heavy-duty weight techniques.

1.6.2. Semantic-Based Formal Methods

Formal methods based on semantic foundation are most commonly used for formal specification [type-3]. Model oriented and property oriented are two main semantic- based approaches of formal methods. VDM, CSP [C. Hoare], Statcharts [Q. Zhao], RAIZE [Dang], Petri-nets [D.Kartson] and B-Method [K. Lano] are common examples of model oriented formal methods. On the other hand property oriented formal methods approaches that enables minimal constraints on the system's behavior, which are necessary, the internal structure of system is not prescribe in detail. ANNA [D. C. Luckham], and Larch are examples of property oriented formal methods.

1.6.3. Application-Based Formal Methods

According to the system's nature, the different approaches are applied on the system for specification [type-3]. With respect to the applicability, the formal languages are different from one another. VDM, Z and Larch are used for sequential formalism. LOTOS [Hubert] and MTCS [Walter] are used for concurrent modeling process. Similarly for real-time formalism ET-Lotos [L. leonard] is used.

1.6.4. Graphical-Based Formal Approaches

Petri-nets and SDL [El-Gendy] are two well-known graphical approaches, which are used for formal specification of systems. Data flow diagram (DFD) [R. Sato] and Unified modeling language (UML) are two semi formal methods techniques which are graphical based. Finite state machine (FMS) is also considered as formal specification technique.

1.7. Why We need Formal Methods

Formal methods are normally used in critical systems due to its some distinguish properties. When we write formal specification of a system then it is (1) unambiguous because the syntax used in formal methods can has only single interpretation, (2) consistent and (3) complete [13]. Another strong reason to use the formal method is that the formal specification involves investing more effort in the early phases of software development and this reduces requirements errors as it forces a detailed analysis of the requirements. Use of formal specification means that the cost profile of a project has changed because there are greater up front costs as more time and effort are spent developing the specification, however, implementation and validation costs should be reduced as the specification process reduces errors and ambiguities in the requirements. Testing does not give us enough confidence so we have to provide a formal proof that software is correct.

1.8. Application of Formal Methods

Formal specification techniques are applicable in many real time systems but are most applicable in the development of critical systems and standards [16].

1.8.1. Security Critical Systems

Security critical system involves authorize use of system. For the verification of network protocol, formal methods are used [16]. The network security is essential for every organization either it is private or government sector because intruder effect the networks which can cause for loss of precious information and resource, therefore the use of formal methods for writing specification of protocol are helpful to achieve security goals of protocols. Some security models are formalized and the verified by using formal automated tools [17].

1.8.2. Complex Systems

Formal approach is used to develop the complex systems [18]. This is the only technique, which gives us precisely specifying models of system for the complex software system [19].

1.8.3. Safety critical systems

Safety critical systems are also called life critical systems because in the safety critical systems failure of the system or software might be dangerous for life. Criticality is often expressed in terms of:

* Reliability

* Availability

* Maintainability

* Safety

* Security

Critical systems make expensive methods worthwhile and needs experience. The most common Examples of safety-critical systems are given below [15].

Medicine: The medicine is critical area where we cannot afford the failure of the system because the failure of the system means failure of the life or some bad effect on the life. Following are the some machine and system used in medicine.

* Heart-lung machines

* Mechanical ventilation systems

* Infusion pumps and Insulin pumps

* Radiation therapy machines

* Robotic surgery machines

* Defibrillator machines

Nuclear Engineering: Nuclear reactor control system has a close relationship with safety critical systems. Even the miner mistake can cause the inerrable lose of life.

Transport: The transportation system is implemented almost in every country of the world. The railway signaling and control system belongs to safety critical systems. If the problem occurs in this system, the lives would be in danger zone.

Aviation: Aviation includes all those activities that are manmade flying devices like aircraft and fighter jet. Following are the some systems related to it.

* Air traffic control systems

* Avionics, particularly fly-by-wire systems

* Radio navigation RAIM

* Aircrew life support systems

* Flight planning to determine fuel requirements for a flight

1.9. Formal Methods Tools and Notations

Formal methods consist of formal mathematical models or notations, and generally employ a collection of tools to support the syntax checking of specification, as well as the proof of the properties [r1]. There are more than 90 tools of formal methods which are exists and are in use. Some of them are briefly introduced which are commonly used.

1.9.1. B Method

B method is a formal specification method which allows highly accurate expression of the specification's required properties. It proves automatically that the properties are coherent and unambiguous. It was developed by J. R. Abrial. It is very closely related to the Z notation and provides support for the development of programming language code form the specification. The mostly applicable area of B method is safety critical systems. As compare to Z language the B language is slightly low level and it focused on the refinement of cod rather than only formal specification. An evolution of B method is now also in used that is called Event B. it is simpler notation and Rodin Platform is used as tool support for it. The objectives of the B method are the construction of correct software, modeling of system in their environment, formal specification and simplify programming.

1.9.2. Communicating Sequential Process

Communicating sequential process (CSP) is a formal approach used to describe patterns of interaction in concurrent systems. It is based on mathematical theory of concurrency which is known as process algebra. C. A. R. Hoare describes CSP in 1978 and its first version has substantially different syntax as compare to the later version. The earlier version can not determine the unbounded non determinism.

1.9.3. Petri Nets

Petri nets is technique of formal methods and most suitable to model concurrent behavior of the distributed systems. It consists of directed arcs, transition and places. Arcs run from transition to place and vice versa. Places are called input of the transition from which an arc runs to transition and the places are called output of the transition to which arc runs from transition. The Petri nets' behavior is nondeterministic.

1.9.4. Language of Temporal Ordering Specification (LOTOS)

LOTOS is formal specification language for the design of distributed system. It is standardized by international standard organization (ISO) for protocols and open system interconnection (OSI) services. It is a mathematical based technique and normally used for writing formal specification of data communication system. It has various specification styles and various level of abstraction. Initially it was based on calculus of computing and later on some of its concepts are taken from another formal language that is communicating sequential process.

1.9.5. EVES

It is an integrated environment that provides support for the formal development of system from requirement to code. It can also be used for mathematical modeling analysis and formal modeling, this tool has various features including proof checker, integrated automated deduction system, reusable library framework, compiler, interpreter and also with portability feature. The mathematic of EVES is based on the Zermelo-Fraenkel set theory with the axiom of choice (ZFC) without the convention distinction between formula and terms.

1.9.6. Higher Order Logic (HOL)

HOL contains the feature of parser, type checker and theorem prover. This is an interactive mechanized proof assistant, which support both forward and backward proofs. HOL used higher order logic as description language, which provides an expressive and general mechanism for reasoning about the classes of systems. Usually HOL is applied in specification and verification of microprocessor, compilers interface unit, process algebra, algorithms and distributed algorithms.

1.9.7. LARCH

Larch is a property oriented specification language supporting for sequential programs, and abstract data types. Larch includes the following feature like parser, user-directed prover and type checker. Larch prover (LP) treats in designing equation as rewrite rules and other inferences like induction and proof by cases. LP work as midway between the automatic theorem proving mode and proof checking mode. Larch has been used for formalizing digital circuit and verification of it.

1.9.8. NP-TOOLS

NP-TOOLS is a framework that mathematically proves a safety properties of large scale systems and software. The systems which are analyzed by NP-tools set can be modeled graphical block schema editor or translators and can also modeled by using the combination of both. In NP-tools the requirements are expressed using integer arithmetic and propositional logic.

Proofs are automatically performed in NP-tools that is a main strength of this tool. It is a verification tool box for general purpose, this have been used for nuclear power plants, avionic and programmable logic controller. This tool supports in the analysis of very large system, fast performance, memory efficient it also generate counter example when property is not fulfilled.

1.9.9. Vienna Development Method

Vienna Development Method (VDM) is a set of techniques for modeling computing systems, analyzing those models and progressing to detailed design and coding [32].

The VDM is one of the longest-established formal methods for the development of computer-based systems. It is a model-based approach and it was developed at the IBM's Vienna laboratory in 1970. It has grown to include the group of techniques and tools based on a formal specification language. For writing the formal specification, the VDM-SL tool is used. Support for VDM includes commercial and academic tools for analyzing models, including support for testing and proving properties of models and generating program code from validated VDM models [15].

1.9.10. VDM++

VDM++ is formal object oriented specification language, derived from the VDM and it extends VDM by providing object orientation, parallel and real time features [industrial VDM++]. Since 1992 it has been developing. The VDM++ language is the language supported by the VDM++ toolbox [language manual]. This toolbox includes many features like syntax checker, type checker (semantic checker) and an interpreter this tool can also generate code of c++ and java language, modeling of UML from formal specification is another feature of this toolbox.

Following is the list of tools and techniques which are also used for formal specification.

ACL2, ADL (Algebraic design language), ASLAN, BDDs (Binary decision diagrams), CCS (calculus of communication systems), Circal (CiRcuit CALculus), Concurrency workbench, COQ, DisCo, Estelle, Evolving Algebra, Extended ML (EML), HyTech, IMPS (Interactive Mathematical Proof System), Isabelle, JAPE (Just another proof editor), KIV (Karlsruhe interactive verification), Kronos, LAMBDA, leant, LEGO, LUSTER, Maintainer's Assistant, Meije tools, Murphi, Nqthm, Nuprl, OBJ, Otter, Penelope, Pi-calculus is based on CCS (Calculus of Communicating Systems), ProofPower, PVS (Prototype Verification System), RAISE, Refinement Calculus, RESOLVE, RRL (Rewrite Rule Laboratory), SCR (Software Cost Reduction), SDL (Specification and Description Language), SDVS (State Delta Verification System), SMV, Specware, SPIN, STeP Stanford Temporal Prover, TAM (Temporal Agent Model), TLA (Temporal Logic of Actions), TPS, ETPS, Trio, TTMRTTL, UNITY, UPPAAL.

1.10. Case Study

For the explanation of VDM++ specification, a simple specification of Airport is taken as an example from [vdm book]. In this case study, the aircraft flies from the one airport, then it sends request for permission to land at the airport. When the aircraft reaches at the airport then it waits and circling continuously till the runway become free. Only those aircrafts allow circling which have permission for landing. The aircrafts which are circling can land on the bases of first come first serve. The specification of Airport is described by Q. Charatan and A. Kans using VDM-SL, however we use VDM++ to model it. The complete specification written in VDM++ consists of class specification, which has the following components.

Class Header: This contains name of declaration class and information about inheritance. Inheritance could be a single or multiple. Here in this case study the name of class is Airport and class is a keyword.

class Airport

Types: Types are the definitions of any data types used in the specification class. In the given specification types is a keyword and Aircraft is variable whose type is token.

Types

Aircraft=TOKEN

Instance Variables: Instance variables are used to model the attributes whose type can be sets, sequence, maps and object references. It may have initial expression and invariant. In this specification three instance variables are used where two variables permission and landed are of type set and third variable circling is of type sequence. Inv mk-Airport is an invariant function defined on this system. Where invariants are define as:

* landed is a subset of Permission, i.e., the landed aircraft must have permission for landing

* intersection of circling and landed must be empty, for example one aircraft can not be reside in both, in circling queue and landed set

* every aircraft is unique there no duplication.

Initial expression in this specification is init mk-Airport where it is define that initially permission and landed are empty set and circling is empty sequence.

instance variables

permission:set of Aircraft;

landed:set of Aircraft;

circling:seq of Aircraft;

inv mk-Airport(p,l,c)== l subset p

and elems c subset p

and elems c inter l ={}

and isUnique(c);

init mk-Airport(p,l,c)== p={} and l = {} and c=[];

Functions: Functions can be defined implicitly or explicitly through expression. Instance variable cannot be referred by the functions. The function isUnique is defined in Airport specification. This function will return us a unique id of aircraft.

functions

isUnique(seqIn:seq of Aircraft) query:bool

pre

true

pos

query รณ forall i,j in set inds seqIn & i <> j => seqIn(i) <> seq(j);

Operations: These are the class methods which can be defined implicitly or explicitly through imperative statements and can also be mixture of both. Pre and post condition expression are used in the implicit operation style. In the specification wr and rd are access modifiers where wr means that there is access of both read and write operation and rd mean the there is only read access.

The operation denoted by givPermission() defined in the specification, is modeled to grant the permission to aircraft. Pre-condition ensures that the aircraft which is going to take permission don't have already permission, then permissions will be granted to this aircraft in the post-condition.

operations

givePermission(craftin:Aircraft)

ext wr permission:set of Aircraft

pre

craftin not in set permission

post permission=permission~ union {craftin};

The operation denoted by getPermission() keeps the record of those aircraft which have get permission prior to circling, in this operation the pre-condition true means that there is no constraint and post-condition return the value of permission attribute.

getPermission()permissionout:set of Aircraft

ext rd permission:set of Aircraft

pre

true

post permissionout= permission;

The operation denoted by allowToCircle() is defined in this specification that allows the aircraft for circling. Pre-condition shows the constraints over this operation that ensure that the only those aircrafts allow to circle which have permission and not already exist in circling and post-condition allow the aircraft for circling.

allowToCircle(craftIn:Aircraft)

ext rd permission:set of Aircraft

rd landed:set of Aircraft

wr circling:seq of Aircraft

pre

craftIn in set permission and craftIn not in set elems circling and craftIn not in set landed

post circling = circling~ ^ [craftIn];

The following operation denoted by getCircling() returns the value of circling aircrafts.

getCircling()circlingOut: seq of Aircraft

ext rd circling:seq of Aircraft

pre

true

post circlingOut=circling;

In the operation, denoted by recardLandsing(), the pre-condition ensures that there must be at least one aircraft which is in circling, for example, the circling cannot be empty, and the post-condition records the modification of landed aircraft after the completion.

recordLanding()

ext wr circling:seq of Aircraft

wr landed: set of Aircraft

pre

circling <> []

post

landed =landed union {hd circling~} and circling = tl circling~ ;

The functionality of getLanded () operation is Similar to the getcircling() operation except that this returns the value of landed aircraft.

getLanded()landedout:set of Aircraft

ext rd landed:set of Aircraft

pre

true

post landedout=landed;

The operation denoted by numberWaiting (), returns the total number of aircraft which are waiting. Total is an out put variable, card is a keyword that provides the cardinality of permission minus landed which are the total number of waiting aircrafts.

numberWaiting()total:nat

ext rd landed:set of Aircraft

rd permission:set of Aircarft

pre

true

post

total= card (permission\landed);

end Airport

Print Email Download Reference This Send to Kindle Reddit This

Share This Essay

To share this essay on Reddit, Facebook, Twitter, or Google+ just click on the buttons below:

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays

Doing your resits? We can help!