The software systems

ABSTRACT:

Formal Methods are the techniques which provide an overview of the development of software's in various fields with implementing several types of formal methods. The different types of formal methods are implemented in latest applications with proof to support the roles played in the software. The rise and fall of formal methods are specified so that the future gets benefitted.

INTRODUCTION:

Formal methods are a kind of technique used the specification, development and verification of the software systems. It also provides support for hardware systems as well. Formal methods are mainly used in the development of high-integrity system where safety and security is important.

Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular logic calculi program semantics and algebraic data types are the ways to solve the problems in software and hardware specification and verification.

HISTORY:

Formal methods - Past:[15]

In the early days, formal method research are focussed on proving systems are secure and funded by National Security Agency.

  • Bell-LaPadula model
  • Biba integrity model
  • Clark-Wilson model

Operating systems, more specifically, kernel showed the interest of the systems to prove secure. Here the process of proving can be done by the formal property of the system, modelling the system that might be a semantic structure like a state machine or syntactic structure like a logic expression and final the proving methods that depends on the induction over traces of the state machine model or on the deduction to show that an implication models and automatically proved by machine or interactive guidance of human.

In the early 80's, major research results with general purpose were theorem proving tools like Affirm that support for reasoning the equational logic, Hierarchy Development Methodology which is a special specification language and it has collection of decision procedures for propositional logic. BAN logic - logic of authentication that accumulates belief during the run of the protocol[15].

In the early 90's to the present, there was lots of new thread developments in the fields like model checking i.e hardware verification. In 1996 model checker FDR was used to highlight the mistakes in the Needham-Schroeder protocol , theorem proving COQ was used in 2009 to analyze the Needham-Schroeder protocol and SET and software specification[15].

Tony Hoare recently said that "The experience, judgment, and intuition of programmers who have survived the rigors of testing are what make programs of the present day useful, efficient, and (nearly) correct. Formal methods for achieving correctness must support the intuitive judgment of programmers, not replace it." What is, today, the role of Formal Methods in software development?

Using a structured questionnaire, data was collected between November 2007 and December 2008 on 62 industrial projects. The projects survey resulted in diminish from Europe, Northern America, South America, Australia, and Asia. For 56 of the projects, data was collected from individuals directly who was in the projects, and in the remaining projects information were taken from the literature[16].

Some 20% of responses additionally indicated that the projects related to software development tools themselves, such as operating systems, compilers, and CASE tools, and a further 10% related to computing applications within the domain, such as high-performance computing, runtime code optimisation, file system replication, access control, communications protocols, and microcomputer design[16].

CSP- Communicating Sequential Process

Communicating Sequential Processes [1] is used to specify the interactions between concurrent processes, structuring computer operating systems and the specification of programming languages. Process Calculi are used for computing concurrent systems.

Introduction:

Python is a high-level programming language [2] which is used to make the code structure understandable by programmers. Python in used in web application such as mod_python for Apache web server [3]. Python can be embedded into some software products say Maya, MotionBuilder, Softimage, modo and Blender.[3] ESRI (Economic and Social Research Institute) is now promoting Python as the best choice for writing scripts in ArcGIS (a group of Geographic Information Systems software products). [4] Python is implemented in CSP with network/ distributed support. [3]

IMPLEMENTATION OF PyCSP and CSP:

The PyCSP and CSP are used as channel and process in a network for sending message for communication over the channels.[5] This diagram shows two processes p1 and p2 communicating over the channels c1 and c2.

A PyCSP process is created to assign initial parameter for the functionality of CSP process. The remaining parameters are passed directly to the function when the function starts. Here we create one2one channel so that a reader and a writer is assumed. [5]

The channel connects the processes in a network at the ends when the processes are created. If communication takes places say the message is passed to the person across another end, the message is read by process p1 through the channel c1 and on the other side channel c1 writes the message to process p2. These functions can be done using the processes using these parameters cin and cout. [5] If deadlock occurs by using wrong channel then PyCSP can be used for solving this issue. PyCSP uses read () and write () methods for the processes, provided processes shouldn't use wrong channels. [5] A program can be illustrated for explaining this Processes.

There are many central abstraction methods in PyCSP which can be used in different fields.

ALTERNATIVE method is the process where many number of standard input statements are present according to the reading data present. This is done by two states: ready and unready. If it is ready then execution takes place.

PyCSP Implementation:

In this method Python code is used for portable implementation. By the help of this, these techniques can be implemented in mobile phones. It uses threads, CSP processes and OS processes. Python uses kernel threads for multi-threading in multi-core and multi-processor architectures. Synchronization and python decorators are also used.

PyCSP processes are used by the programmers for shorter and understandable source code in which classes are created for every type of process.

Parallel and Sequence are straight forward implementations. Parallel is used at start() on the processes of each one and then uses join() to synchronize with the termination.

Channels are used to protect the users from not using the wrong channel. Read and write methods are used by the processes.

Channel Poisoning supports PyCSP for terminating a process network.

Alternate and guards are the other implementation techniques used.

Application:

Brain Tumor Detection:

This is an e-science application targets planning of stereotactic radiation of brain-tumors. The aim is to set up a number of radiation sources that reduces the amount of energy absorbed by healthy brain-tissue with enough energy within the tumor. [5] The modeling of the radiation is a simple Monte-Carlo simulation of a radiation source where the probability of a ray depositing its energy in any point is proportional to the density of the tissue, or inversely proportional to the light on the CT scan of the brain. [5]

There are number of radiation sources produced, CSP takes scalable solution where the radiation sources produces vector particles, processes receive this vector particles through a channel so that the particles can be traced through the brain tissue. When this method is used it reaches very high degrees of parallelism, so that by the ray-tracing processes, rays are produced in billions.

The radiation source after creating the particles sends a "finished" [5] message on termination channel. The terminator process allows the radiation sources to finish, so that it can poison the channel for transmitting the vector particles to the ray tracers, by which the ray tracer terminates if a new vector particle comes in.

The Vienna Development Method (VDM) a collection of techniques for the formal specification and development of computing system. VDM is one of the best example of Formal methods.Derived from the work of the Vienna Laboratory, IBM 1970 is well-established set of methods and tools based on formal specification languages - VDM Specification Language (VDM-SL).This is an extended form of VDM + +, which supports the modeling of object-oriented and parallel systems [6].

VDM Features:

The ISO Standard contains a formal definition of the language's semantics. Some texts prefer a more concisemathematical syntax.

VDM-SL, a model description of system functions performed on the data.It includes some definitions of data types and functions.

Basic Types: Numeric, characters and token.

Type Constructors: Union, product and Composite types.[7]

Structuring:

The main difference between the VDM-SL and VDM + + code, the secret is in the structure.In VDM-SL there is a conventional modular extension and VDM + + provides a mechanism through which to build a traditional object-oriented classes and inheritance.

Structuring in VDM-SL:

ISO standard for VDM-SL is an informative annex containing the various principles of structuring. They all follow the traditional principles of information hiding modules and can be explained as follows:

  • Module naming: Each module is a syntactic began with the name of the module.
  • Importing:. We can import the definitions that were exported from other modules.
  • Exporting: From the definition of the module, the desire to gain access to other modules are implemented.[7]

Structuring in VDM++:

The structure of VDM++ are done using classes and multiple inheritance.

  • Classes: Each and every class began with the class name.
  • Inheritance: The class name in the class heading when a class inherits constructs from other classes.[7]

CASE STUDY:

Intercredit Bank N.A. (ICB) operates as a community bank with 4 full-service offices in Miami-Dade County and a recently opened full-service office in Broward County. The bank was founded in 1992. Management of the organisation decided to implement an electronic document management system which make their business processes more efficient. After evaluating several products, they selected ATNETS (Advanced Technology Network Systems) VDM to meet document management needs companywide[8]. ICB has started implementing VDM Five years ago and its still in use.

Roles of VDM in ICB:

The main reason for implementing VDM systems is to integrate all the different departments of ICB's together.To achieve this goal ATNETS developed a system in which clients files are stored by the account number and related to any other activities with the bank. All information is stored together electronically.Each department has a number of specific requirements for its electronic filing system.ATNETS created specific method of implementation for each department

High Security:

There was a common problem that someone would take a paper document from their files and then not return it, or else re-file it in the wrong location. But Now they are sure that their documents can't be misplaced, since everything is electronic. The risk of financial loss has been greatly reduced.

Protecting Customer Information:

VDM's security features, such as password protection and distribution rights ensure that only authorized bank personnel retrieve documents stored in the secure VDM repository.

Back-file Conversion:

The aim of electronic office ICB is now becoming a reality.More than 2 million documents are converted into electronic documents.This process is expected to be done in three months.ATNETS spot scanning team manages the entire process of ICB.[8]

Future Benefits:

  • When auditors come in, they can use the online system to view documents either at the office of the audit or in their own office. This makes the process much easier, efficient, and faster.
  • Employee's become significantly more productive and efficient.
  • Scanned documents are easily accessed at employee's desktop and can be distributed quickly via email to clients or co-workers.

Z notation:

Z notation was developed by Abrial in 1977. Steve Schuman and Bertrand Meyer helped him for its development. Z notation was updated further by Abrial at the Programming Research Group at Oxford University while he worked in the early eighties[9].

Z is the standard mathematical notation used in axiomatic set theory, lambda calculus and first-order predicate logic. The mathematical notation of Z consists of a small kernel, complemented with a large collection of useful articles and traders said the Z mathematical toolkitThis is a collection of mathematical theories: definitions and legislation on issues such as sets, tuples, relations, sequences of functions, and its operators.In Z, we use these mathematical objects to model data structures and other parts of the computer system.

Application:

Mondex Smart Card

In the early 1990's, the National Westminster Bank and Platform Seven2 developed a smartcard-based electronic cash system with secure and for free. They assured the card was secure, where authentication, transaction and institution that issued the card by using sophisticated system of encryption locks and keys. In this way, chips make it much more certain that any given card is genuine.

Platform Seven decided to certify Mondex to one of the very highest standards It requires a formal proof that the concrete design obeys the abstract security properties The evaluation was carried out by the Logica Commercial Licenced Evaluation Facility, with key parts of the work subcontracted to the University of York to ensure independence and to deliver the specification and proof using Z [Spivey 1989; Woodcock and Davies 1996].

In 1999, Mondex achieved its ITSEC Level E6 [11], which approximates to Common Criteria Level 7 [12]. certificate: the very first product ever to do so. As a part of the ITSEC E6 process, the entire Mondex development was additionally subject to rigorous testing. No errors were found in any part of the system subjected to the use of formal methods.

In 2006, Mondex was renovated as pilot project for the Grand Challenge by applying Moore's Law in Verified Software. The scope was to test the state of the art in mechanical verification moved on in ten years. Challenge was taken by eight using different formal methods. By Z proofs, The cost of mechanising was only 10% of the original development cost. Interestingly, almost all methods achieved the same level of automation, producing the similar results.

Some of the other applications are "The Maeslant Kering Storm Surge Barrier", Radio Therapy Machine, etc.

Vampire

Vampire is developed in Manchester University by Andrei Voronkov and Alexandre Riazanov. Vampire is a theorem prover. More precisely, it proves theorems in first-order logic. The vampire was started to develop in 1994. The current version of vampire is the third generation of vampire. The main advantage of vampire is its fastness in theorem proving . Normally theorem proving have many applications like software verification, hardware verification, hardware design, knowledge representation and reasoning, semantic web, algebra and proving theorems in mathematics. Vampire is used in level-2 of formal method while formal methods are used in number of levels. Some levels are level-0, level-1 and level-2. In level-0 formal specifications will be undertaken, in level-1 formal development and verifications are done and in level-2 theorem provers are used and the vampire is being used in level-2 of formal methods. When a theorem is proven, the system produces a verifiable proof, which validates both the classification phase and the refutation of the CNF.

Resolution theorem proving:

Resolution theorem proving is one of the theoretical methods of proving theorem in first order logic. Normally FOL allow expression to have a structure. In this the first order logic is converted into conjunctive normal form. Unification is the procedure for searching for a consistent set of substitutions of elements. Resolution theorem proving works by negating the assertion that is to be proved, and trying to prove a contradiction or the empty set. We should substitute name in the place of variable or variable in the place of name. If both sides have same name or variable we should ignore it.

Awards won by vampire:

Vampire had won many tropies for its theorem proving since 1999 and it had won about 20 trophies in total. When compared to any other theorem prover vampire is the leading one. It takes part in the following three divisions of the competition:

  • FOF division- First order logic considers the world contains object (people, house), relations(brother of, bigger than), functions(one more than, end of) where other logics such as propositional logic considers the world to be of facts.
  • CNF division- It is the dual of DNF (Disjunctive normal form), where the roles of 'and' and 'or' are being reversed in the distribution step to reach a 'product of sums'. First order in conjuctive normal form. This division was called MIX.
  • LTB division- problems with very large axioms (some of them contain about 3.5 million axioms).

2008- Vampire won CASC (Cade ATP System competition) in two divisions of world cup in theorem proving. Two divisions are FOF (First- order formula) and CNF (formulas in Conjuctive normal form).

2009- Vampire won CASC in three divisions of world cup in theorem proving. This time it had won in three divisions namely FOF, CNF and LTB (Large theories division). In CNF division vampire solved 181 problems out of 200 while all other together solved 174 problems.

Note: 'W*' means that vampire solved more problems that all other problem provers in this division and '-' means that the division did not exist that year. " 'W' denotes that vampire had won the competition and the ' ' blank space denotes that other theorem provers had won the competition.[13]

Main features of vampire:

Vampire have two main features they are interpolation and symbol elimination. Both are implemented using symbols and formulas that are colored.

Interpolation:

Interpolation is nothing but adding one or two to the other content. In this we are going to add formulas L and r to I. Here L,I and I, R that is I is implied by L and implies R. Every symbol that occurs in I also occurs in L and R. We can assume that we have two two colors left and right. Some symbols may be in left color and some may be in right color and some may also be transparent and the symbol occurs according to its color. If its color is left then it will occur in L and if its color is right then it will occur in R. The following example is clear to the above mentioned.

Vampire in industries:

It is been used in the latest processors from AMD, Intel and others, theorem proving has been used to verify that division and other operations are correct.

Conclusion:

In the future, we expect that the role of formal methods in the entire system-development process will increase, especially as the tools and methods successful in one domain carry over to others. Basic research on new specification and new verification techniques languages will be supported continuously and new verification techniques. Similarly, sufficient training will be given to all system developers and make them very familiar as to all the formal methods as a common communication language.

Reference:

  1. http://en.wikipedia.org/wiki/Communicating_sequential_processes
  2. "What is Python Good For?".General Python FAQ. Python Foundation. Retrieved 2008-09-05.
  3. http://en.wikipedia.org/wiki/Python_ (programming_language)
  4. "About getting started with writing geoprocessing scripts". November 2006. Retrieved April 2007.
  5. http://www.cs.uit.no/~johnm/publications/pdf/bjorndalen2007pycsp.pdf
  6. http://www.vienna.cc/e/evdm.htm
  7. http://en.wikipedia.org/wiki/Vienna_Development_Method
  8. http://www.atnets.com/AtnetsOnline/Images/PDF/IntercreditVDMCS_Eng.pdf
  9. http://en.wikipedia.org/wiki/Z_notation
  10. http://spivey.oriel.ox.ac.uk/mike/zrm/zrm.pdf
  11. ITSEC. 1991. Information technology security evaluation criteria (ITSEC): Preliminary harmonised criteria. Tech. Rep. Document COM(90) 314, Version 1.2, Commission of the European Communities. Jun.
  12. CCRA. 2006. Common criteria for information technology security evaluation. Part 1: Introduction and general model. Tech. Rep. CCMB-2006-09-001, Version 3.1, Revision 1, Common Criteria Recognition Agreement. Sep
  13. http://vprover.org/trophies.cgi
  14. http://vprover.org/interpol.cgi

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!