(Iniitial version) |
No edit summary |
||
| Line 17: | Line 17: | ||
* Targeted release: [[Releases/{{FedoraVersion||next}} | {{FedoraVersion|long|next}} ]] | * Targeted release: [[Releases/{{FedoraVersion||next}} | {{FedoraVersion|long|next}} ]] | ||
* Last updated: 2008-08-07 | * Last updated: 2008-08-07 | ||
* Percentage of completion: | * Percentage of completion: 80% | ||
<!-- CHANGE THE "FedoraVersion" TEMPLATES ABOVE TO PLAIN NUMBERS WHEN YOU COMPLETE YOUR PAGE. --> | <!-- CHANGE THE "FedoraVersion" TEMPLATES ABOVE TO PLAIN NUMBERS WHEN YOU COMPLETE YOUR PAGE. --> | ||
== Detailed Description == | == Detailed Description == | ||
<!-- | No realistic software or hardware can be exhaustively tested; | ||
exhaustively a program that adds two 64-bit numbers would take more than 10^100 years. | |||
<!-- 10**128 / (4*10**9) / 3600. / 24 / 365.25 = 7.9220219535072374e+110 --> | |||
So for decades people have worked to develop tools that can apply | |||
mathematical techniques to prove that software and hardware does or does not do something. | |||
These tools can be used for other purposes where proving something is true, | |||
or solving for values given a large number of constraints, are important. | |||
Here are some of these kinds of tools, along with packages of programs | |||
that perform them: | |||
* Automated Theorem Provers: These take mathematical facts and attempt to prove a goal, completely automatically. Packages: ''prover9'' and ''Zenon''. | |||
* Interactive Theorem Provers: These let humans take mathematical facts and attempt to prove a goal, in cases where the automated tools can't manage. Package: ''Coq'' | |||
* Program Provers: These take software programs and break them down into verification conditions (VCs) for the above to solve. Package: ''Why'' (which can handle annotated C and Java) | |||
* Boolean Satisfiability (SAT) solvers: These take boolean equations and solve for them; they are a basic building block for some implementations of the above. Package: ''MiniSAT'' | |||
* Formal specification languages: These let people describe software or systems using a mathematically rigorous language, such as Z. Package: ''tex-zfuzz'' | |||
Do ''not'' assume that you can just take a program prover on a big existing program and start | |||
using it effectively. Scale can be a problem, all such tools have limitations, | |||
and these tools are just ''starting'' to become mature. | |||
Nevertheless, for those who are interested in the technology or who wish to help it mature, | |||
these are a great place to start. | |||
== Benefit to Fedora == | == Benefit to Fedora == | ||
This enables developers to start using these kinds of programs in a variety of circumstances. | |||
== Scope == | == Scope == | ||
Developers have had to package a number of programs, most of which have not been packaged before. | |||
In some cases, we've had to address integration problems (e.g., Zenon changed its input format, but the | |||
Why developers didn't know that). | |||
It has no effect on those who don't wish to use these tools. | |||
== Test Plan == | == Test Plan == | ||
No special hardware or system preparation is required; simply install the packages | |||
listed above. | |||
Many of the toolsuites include some checking. | |||
In addition, the "Why" suite can use many other tools; we have used its | |||
"binary-search.c" example with gwhy to test integration with Zenon and Coq. | |||
<!-- This does not need to be a full-fledged document. Describe the dimensions of tests that this feature is expected to pass when it is done. If it needs to be tested with different hardware or software configurations, indicate them. The QA team will turn this information into a more complete test plan. The more specific you can be, the better the final test plan will be. | <!-- This does not need to be a full-fledged document. Describe the dimensions of tests that this feature is expected to pass when it is done. If it needs to be tested with different hardware or software configurations, indicate them. The QA team will turn this information into a more complete test plan. The more specific you can be, the better the final test plan will be. | ||
| Line 45: | Line 74: | ||
== User Experience == | == User Experience == | ||
Target users will notice that they can easily install these tools. | |||
<!-- If this feature is noticeable by its target audience, how will their experiences change as a result? Describe what they will see or notice. --> | <!-- If this feature is noticeable by its target audience, how will their experiences change as a result? Describe what they will see or notice. --> | ||
== Dependencies == | == Dependencies == | ||
There are no special dependencies. | |||
<!-- What other packages (RPMs) depend on this package? Are there changes outside the developers' control on which completion of this feature depends? In other words, completion of another feature owned by someone else? Other upstream projects like the kernel (if this is not a kernel feature)? --> | <!-- What other packages (RPMs) depend on this package? Are there changes outside the developers' control on which completion of this feature depends? In other words, completion of another feature owned by someone else? Other upstream projects like the kernel (if this is not a kernel feature)? --> | ||
== Contingency Plan == | == Contingency Plan == | ||
None necessary, revert any undesirable packages. | |||
<!-- If you cannot complete your feature by the final development freeze, what is the backup plan? This might be as simple as "None necessary, revert to previous release behaviour." Or it might not. If you feature is not completed in time we want to assure others that other parts of Fedora will not be in jeopardy. --> | <!-- If you cannot complete your feature by the final development freeze, what is the backup plan? This might be as simple as "None necessary, revert to previous release behaviour." Or it might not. If you feature is not completed in time we want to assure others that other parts of Fedora will not be in jeopardy. --> | ||
== Documentation == | == Documentation == | ||
Documentation on these tools is notoriously bad; some packages don't | |||
have any documentation at all. | |||
We have written some brief documentation in some cases, and tried to include | |||
some documentation with the tools. | |||
We expect this to improve in future releases. | |||
<!-- Is there upstream documentation on this feature, or notes you have written yourself? Link to that material here so other interested developers can get involved. --> | <!-- Is there upstream documentation on this feature, or notes you have written yourself? Link to that material here so other interested developers can get involved. --> | ||
== Release Notes == | == Release Notes == | ||
No special release notes. | |||
<!-- The Fedora Release Notes inform end-users how to deal with platform changes such as ABIs/APIs, configuration or data file formats, or upgrade concerns. If there are any such changes involved in this feature, indicate them here. You can also link to upstream documentation if it satisfies this need. This information forms the basis of the release notes edited by the documentation team and shipped with the release. --> | <!-- The Fedora Release Notes inform end-users how to deal with platform changes such as ABIs/APIs, configuration or data file formats, or upgrade concerns. If there are any such changes involved in this feature, indicate them here. You can also link to upstream documentation if it satisfies this need. This information forms the basis of the release notes edited by the documentation team and shipped with the release. --> | ||
Revision as of 18:54, 7 August 2008
Feature Name
Provers
Summary
Add basic support for some key provers, solvers, and formal methods tools. These tools let you prove that some facts are true (given other facts) and/or model systems using mathematics, and can be used to greatly increase the reliability of software and hardware.
Owner
- Name: David A. Wheeler
Current status
- Targeted release: Fedora 42
- Last updated: 2008-08-07
- Percentage of completion: 80%
Detailed Description
No realistic software or hardware can be exhaustively tested; exhaustively a program that adds two 64-bit numbers would take more than 10^100 years. So for decades people have worked to develop tools that can apply mathematical techniques to prove that software and hardware does or does not do something. These tools can be used for other purposes where proving something is true, or solving for values given a large number of constraints, are important.
Here are some of these kinds of tools, along with packages of programs that perform them:
- Automated Theorem Provers: These take mathematical facts and attempt to prove a goal, completely automatically. Packages: prover9 and Zenon.
- Interactive Theorem Provers: These let humans take mathematical facts and attempt to prove a goal, in cases where the automated tools can't manage. Package: Coq
- Program Provers: These take software programs and break them down into verification conditions (VCs) for the above to solve. Package: Why (which can handle annotated C and Java)
- Boolean Satisfiability (SAT) solvers: These take boolean equations and solve for them; they are a basic building block for some implementations of the above. Package: MiniSAT
- Formal specification languages: These let people describe software or systems using a mathematically rigorous language, such as Z. Package: tex-zfuzz
Do not assume that you can just take a program prover on a big existing program and start using it effectively. Scale can be a problem, all such tools have limitations, and these tools are just starting to become mature. Nevertheless, for those who are interested in the technology or who wish to help it mature, these are a great place to start.
Benefit to Fedora
This enables developers to start using these kinds of programs in a variety of circumstances.
Scope
Developers have had to package a number of programs, most of which have not been packaged before. In some cases, we've had to address integration problems (e.g., Zenon changed its input format, but the Why developers didn't know that). It has no effect on those who don't wish to use these tools.
Test Plan
No special hardware or system preparation is required; simply install the packages listed above. Many of the toolsuites include some checking. In addition, the "Why" suite can use many other tools; we have used its "binary-search.c" example with gwhy to test integration with Zenon and Coq.
User Experience
Target users will notice that they can easily install these tools.
Dependencies
There are no special dependencies.
Contingency Plan
None necessary, revert any undesirable packages.
Documentation
Documentation on these tools is notoriously bad; some packages don't have any documentation at all. We have written some brief documentation in some cases, and tried to include some documentation with the tools. We expect this to improve in future releases.
Release Notes
No special release notes.