Formal specification

In computer science, formal specifications are mathematically based techniques whose purpose are to help with the implementation of systems and software. They are used to describe a system, to analyze its behavior, and to aid in its design by verifying key properties of interest through rigorous and effective reasoning tools.[1][2] These specifications are formal in the sense that they have a syntax, their semantics fall within one domain, and they are able to be used to infer useful information.[3]

Motivation

In each passing decade computer systems have become increasingly more powerful and as a result they have become more impactful to society. Because of this, better techniques are needed to assist in the design and implementation of reliable software. Established engineering disciplines use mathematical analysis as the foundation of creating and validating product design. Formal specifications are one such way to achieve this in software engineering reliability as once predicted. Other methods such as testing are more commonly used to enhance code quality.[1]

Uses

Given such a specification, it is possible to use formal verification techniques to demonstrate that a system design is correct with respect to its specification. This allows incorrect system designs to be revised before any major investments have been made into an actual implementation. Another approach is to use provably correct refinement steps to transform a specification into a design, which is ultimately transformed into an implementation that is correct by construction.

It is important to note that a formal specification is not an implementation, but rather it may be used to develop an implementation. Formal specifications describe what a system should do, not how the system should do it.

A good specification must have some of the following attributes: adequate, internally consistent, unambiguous, complete, satisfied, minimal[3]

A good specification will have:[3]

One of the main reasons there is interest in formal specifications is that they will provide an ability to perform proofs on software implementations.[2] These proofs may be used to validate a specification, verify correctness of design, or to prove that a program satisfies a specification.[2]

Limitations

A design (or implementation) cannot ever be declared “correct” on its own. It can only ever be “correct with respect to a given specification”. Whether the formal specification correctly describes the problem to be solved is a separate issue. It is also a difficult issue to address, since it ultimately concerns the problem constructing abstracted formal representations of an informal concrete problem domain, and such an abstraction step is not amenable to formal proof. However, it is possible to validate a specification by proving “challenge” theorems concerning properties that the specification is expected to exhibit. If correct, these theorems reinforce the specifier's understanding of the specification and its relationship with the underlying problem domain. If not, the specification probably needs to be changed to better reflect the domain understanding of those involved with producing (and implementing) the specification.

Formal methods of software development are not widely used in industry. Most companies do not consider it cost-effective to apply them in their software development processes.[4] This may be for a variety of reasons, some of which are:

Other limitations:[3]

Paradigms

Formal specification techniques have existed in various domains and on various scales for quite some time.[6] Implementations of formal specifications will differ depending on what kind of system they are attempting to model, how they are applied and at what point in the software life cycle they have been introduced.[2] These types of models can be categorized into the following specification paradigms:

In addition to the above paradigms there are ways to apply certain heuristics to help improve the creation of these specifications. The paper referenced here best discusses heuristics to use when designing a specification.[6] They do so by applying a divide-and-conquer approach.

Software tools

The Z notation is an example of a leading formal specification language. Others include the Specification Language(VDM-SL) of the Vienna Development Method and the Abstract Machine Notation (AMN) of the B-Method. In the Web services area, formal specification is often used to describe non-functional properties[7] (Web services Quality of Service).

Some tools are:[4]

Examples

For implementation examples, refer to the links in Software Tools section.

See also

References

  1. 1 2 Hierons, R. M.; Krause, P.; Lüttgen, G.; Simons, A. J. H.; Vilkomir, S.; Woodward, M. R.; Zedan, H.; Bogdanov, K.; Bowen, J. P.; Cleaveland, R.; Derrick, J.; Dick, J.; Gheorghe, M.; Harman, M.; Kapoor, K. (2009). "Using formal specifications to support testing". ACM Computing Surveys. 41 (2): 1. doi:10.1145/1459352.1459354.
  2. 1 2 3 4 5 Gaudel, M. -C. (1994). "Formal specification techniques". Proceedings of 16th International Conference on Software Engineering. pp. 223–223. doi:10.1109/ICSE.1994.296781. ISBN 0-8186-5855-X.
  3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Lamsweerde, A. V. (2000). "Formal specification". Proceedings of the conference on the future of Software engineering - ICSE '00. p. 147. doi:10.1145/336512.336546. ISBN 1581132530.
  4. 1 2 3 4 Sommerville, Ian (2009). "Formal Specification" (PDF). Software Engineering. Retrieved 3 February 2013.
  5. 1 2 3 Nummenmaa, Timo; Tiensuu, Aleksi; Berki, Eleni; Mikkonen, Tommi; Kuittinen, Jussi; Kultima, Annakaisa (4 August 2011). "Supporting agile development by facilitating natural user interaction with executable formal specifications". ACM SIGSOFT Software Engineering Notes. 36 (4): 1–10. doi:10.1145/1988997.2003643.
  6. 1 2 van der Poll, John A.; Paula Kotze (2002). "What design heuristics may enhance the utility of a formal specification?". Proceedings of the 2002 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology. SAICSIT '02: 179–194.
  7. ↑ S-Cube Knowledge Model: Formal Specification

External links

This article is issued from Wikipedia - version of the 11/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.