Introduction
Software systems are used in almost every industry to perform important operations. For example, they can be used to manage financial transactions, medical records, control aircraft systems etc. It is vital to ensure that software systems behave as intended. If there is an error in the software it can cause a loss of money, sensitive data being exposed, disruptions to business and potentially safety risks.
Formal verification can help to ensure that the software meets the required specification. Software engineering can utilize mathematical logic to verify the software will meet it’s intended specification. This can help to make sure the software works correctly and highlight any potential vulnerabilities. It also can help developers identify errors that may have been made in the programming. It can also help to avoid security vulnerabilities.
What is formal verification?
Formal verification can be used to verify software will behave as intended using mathematical methods. Unlike testing software, formal verification can be used to use mathematical logic to verify some properties will hold for the given scenarios. This can help to verify the software will perform as intended. For example, ensuring a banking application will calculate transactions correctly, a healthcare system will keep sensitive data safe or an aviation control programme will respond accordingly to the conditions.
This can be done by specifying exactly what the program should do using mathematical statements and verifying that it meets those specifications. Formal verification can be used for functions, algorithms, components or an entire system. It can help reduce uncertainty around how the software will behave by making sure the requirements are clear.
How formal verification works
Formal verification can be used by firstly determining what the desired behavior for the software should be by using a formal specification. From this, the requirements can be converted to mathematical statements. Depending on how complex the software is, logical statements, mathematical models, verification conditions or theorem proving can be used.
The program can be analysed to see if it meets the required properties. Verification tools can help to determine if the logic is correct, there are any contradictions and if certain conditions are true. If the proof fails, the engineer will look into the issue and make changes to the program or specification. This helps to make a link between what the software should do and what it is doing.
Mathematical concepts used in formal verification
1. Logical Conditions
Logical conditions are statements that can be used to determine that certain conditions will be true at a point in the program. This can help software engineers to use mathematical statements to specify the requirements. For example, ensuring a banking application will not have a negative balance after a transaction unless there is an overdraft facility.
Or the total amount being taken out of an account will equal the amount being added to the account (excluding any clearly defined fees). This can help developers to identify when the program is not behaving as intended. They can be added before or after an operation to make sure important conditions are still true. They help in formal verification by using logical statements.
2. Precondition
A precondition is a condition that must be met before the program, function or operation runs. This specifies what must happen for the operation to run properly. For example, a function that averages a set of numbers may require that there is at least 1 number in the set. Or a banking application may require that the customer is authenticated, the amount to be transferred is a positive number and that the account is allowed to perform the transaction.
This can help developers to know what conditions must be met for a program to run. If these conditions are not met the software may not allow the request to be processed. By clearly defining the preconditions, it can reduce any ambiguity and avoid invalid inputs. During formal verification, engineers will use mathematical logic to determine that the required preconditions are met.
3. Postcondition
A postcondition is what must be true after a program or function has been run. For example, a function that transfers money between 2 bank accounts may have a postcondition that states that the source account has had the amount subtracted and the destination account has had the amount added. This can help developers to clearly define what they expect to happen after an operation.
This is particularly useful for verifying functions that manipulate data, perform calculations or interact with other components. Engineers can compare what the program is actually doing compared to the postconditions to ensure that the program is performing the way it should for the given specification. This can help to gain confidence that individual operations are doing what they should.
4. Invariants
An invariant is something that must be true throughout a part of the program. This is particularly useful with loops, algorithms and complex data structures. For example, if a program was processing a list of customer transactions, an invariant may be that all transactions processed so far have been added to the total. Or if there is a database management application, there may be an invariant to ensure the customer records have the correct relationship with their transactions.
This can help to ensure that important conditions are still true throughout the program. During formal verification, engineers will ensure that the invariant is true before entering the loop, they will ensure that it still holds after each loop and they can use it to reason about the final result. This can help developers to identify any logical errors.
5. Correctness
Correctness refers to whether a program can perform the intended functionality. If the program meets the conditions in the specification then it is said to be correct. Formal verification can be used to use mathematical methods to verify that the program is correct. There are 2 types of correctness; partial and total. Partial correctness means that if the program finishes running, it will return the correct postcondition. Whereas, total correctness means that not only will the program return the correct result but it will also finish running.
This is important as there may be situations where the program returns the correct answer but runs forever. By using mathematical methods to verify the correctness, developers can identify any logical errors, incorrect calculations and unexpected results. This is particularly useful for applications where incorrect results could impact financial decisions, medical treatment, transport etc.
Theorem Proving
One of the main techniques used in formal verification is theorem proving. This uses mathematical logic to determine whether a statement is true based on a set of assumptions, definitions and previous results. In software engineering, this can help to prove that the program meets the formal specification. Engineers will create a mathematical proposition that defines the properties that the software should have.
They will then create a proof to show that the operations performed will maintain those properties. Some theorem provers will require the user to provide logical steps however others can be automated. There are several tools that can help to create and verify mathematical proofs such as Coq, Lean and Isabelle. This is particularly useful for complex algorithms within the software and can provide a high confidence that the program is correct. Proofs can take a lot of mathematical knowledge and time to create but can provide strong evidence that the program meets the intended requirements.
Types of formal verification
1. Model Checking
Model checking is a type of formal verification that looks at a mathematical model to verify whether certain properties hold. Engineers will create a model that outlines the possible states of the software and what transitions can happen. A model checker will look at this model to determine if the required conditions are met. For example, looking at a model of an automated banking system and ensuring that 2 conflicting transactions will not update the same account inconsistently.
This can be very useful for identifying issues with concurrency, interaction between components and complex systems. If a property is not met, the model checker may be able to provide a counterexample showing what events happened to cause the issue. This can help developers to understand what went wrong and fix the design. However if the system becomes very large it can have some limitations.
2. Static Analysis
Static analysis looks at the source code or compiled code without running the program. This can help identify any potential issues with the programming. Some static analysis methods utilise formal methods and mathematical logic to analyse properties such as data flow, variable usage and paths. For example, identifying that a variable is being used before it has been assigned a value.
Or an operation may return an invalid result. In security focused applications, static analysis can help identify any potentially unsafe input handling. There are several tools available such as Frama-C, CodeQL and various compiler analysis systems. Whilst this does not prove that everything is correct it can be an efficient method to find potential issues early on and improve the overall quality.
3. Hoare Logic
Hoare logic is a mathematical system that can be used to reason about the correctness of computer programs. It uses a Hoare triple which is commonly written as {P} C {Q}. P is the precondition, C is the statement/statement(s) and Q is the postcondition. This shows that if the precondition is true and the program is run according to the assumptions, then the postcondition should also be true.
For example, if there is a function that adds a given amount to an account balance. The precondition could be that the initial balance and extra amount are valid numbers. Whilst the postcondition would be that the new balance is the sum of the numbers. This provides formal rules to reason about assignments, conditionals, loops and sequences. It is widely used for verifying programs.
4. Symbolic Execution
Symbolic execution looks at the behaviour of a program by using symbolic values. Instead of just using one set of test data, the inputs will be represented by symbols. This will look at all the different paths that could be taken. For example, a discount calculation may behave differently depending on whether the customer has purchased over a certain amount.
Symbolic execution will look at the conditions and determine what inputs would cause each outcome. This can help identify situations where the program may return unexpected results. This can be useful for analysing complex conditionals and finding any errors that may be missed when testing. However, if there are many branches or complex loops this can get very computationally expensive.
How formal verification can help avoid programming errors
There are many reasons why programming errors can occur. This can be due to incorrect assumptions, poor algorithms, unexpected inputs and errors with complex operations. Traditional testing can help to identify many of these issues. However it is generally impossible to test all the possible inputs and paths. Formal verification can help overcome this issue by allowing engineers to define the requirements mathematically. For example, proving that a sorting algorithm will always return an ordered result for the given inputs. Or that a financial calculation will maintain important mathematical relationships.
Engineers can also verify that the program will terminate correctly and the operations are maintaining important invariants. If there is a contradiction or a requirement that cannot be proven, engineers can look into the logic before it gets to production. This can help to reduce the risk of defects getting into the production software. It also provides a more systematic approach to developing software. Whilst it cannot guarantee that there will be no issues with the implementation or operations, it can provide an extra level of confidence to improve the quality of software engineering.
Why formal verification is important for software security
Security is an important aspect to consider when developing software. This can be affected by incorrect access control, unsafe data handling, authentication errors and unexpected behaviour. Formal verification can help by allowing engineers to define security properties and analyse them mathematically. For example, ensuring that only authenticated users with the correct permissions can access sensitive records. Or that sensitive information cannot be accessed by an unauthorised operation.
Formal methods can help developers to analyse that these conditions are true throughout different states. This can be particularly useful for security focused components as small logical errors can create serious vulnerabilities. However, formal verification should be used in conjunction with secure development practices, careful implementation and appropriate security testing.
Real life examples of formal verification
- Banking/Financial
Banking requires software to manage account balances, process payments, approve transactions, calculate interest and keep accurate financial records. If there is an error this can cause incorrect balances, double payments or loss of money. Formal verification can help financial software engineers to ensure important transaction rules are maintained. For example, verifying that a money transfer function will ensure that the amount taken from one account will equal the amount added to another account.
Engineers can define conditions to ensure unauthorised operations cannot be performed. This can be particularly useful for payment systems, financial algorithms and banking. Using mathematical logic can help reduce the risk of logical issues occurring in important components. Whilst it doesn’t replace financial auditing, it can provide extra evidence that key operations are performing as intended.
- Healthcare/Medical
Healthcare organisations require software to manage electronic health records, process lab results, support medical equipment and help healthcare professionals make decisions. If there is an error this can impact patient information and potentially affect important decisions. Formal verification can help ensure that healthcare applications meet important requirements. Ensuring patient records are linked to the correct individuals and ensuring authorised users have the correct access to sensitive information.
It can also be used for software used to control medical devices. Engineers can ensure that certain conditions and safety requirements are maintained. For example, software used in an infusion pump may require that there are certain limits on the medication being delivered. Mathematical verification can help ensure that the software is following these requirements within the verified model. As healthcare systems can be complex with lots of interactions between software, hardware and humans formal verification should be used in conjunction with clinical validation, compliance and thorough safety testing.
- Aviation/Aerospace
Software used within aviation needs to be reliable. If there is an issue with flight control systems, navigation systems or aircraft monitoring it can have serious implications. These systems often run constantly and need to respond appropriately to different conditions. Formal verification can help engineers ensure that key components meet their design requirements. For example, flight control software may require that certain conditions are met and respond appropriately to the sensor information. Engineers can use mathematical models and theorem proving to analyse that the software will meet these requirements.
Formal methods can also be used for aerospace systems where software may be used to control operations, navigation and communications. As these systems have strict safety requirements, verification can provide valuable evidence that the key components are performing as expected. However, mathematical proofs should be used in conjunction with hardware testing, integration, environmental testing and other engineering checks to gain confidence that the entire aviation/aerospace system is working as intended.
- Automotive and Transport Systems
Software is commonly used in vehicles to control engine functions, braking assists, driver assistance systems, navigation and communication between different parts of the vehicle electronics. As vehicles become more connected and automated, having reliable software is increasingly important. Formal verification allows Automotive engineers to verify the control algorithms to ensure they meet the requirements as well as ensuring that safety criteria are met. For example an Electronic Braking System may have requirements that it handles information from sensors and dynamically changing driving conditions.
An engineer can model these requirements and use formal verification methods to determine if the software behaves correctly. Formal verification can also be used to verify railway signalling systems and other transport technologies. This enables engineers to identify any issues within the design before deploying the software. In a real world setting there are many unpredictable factors so formal verification needs to be supported by thorough simulation, testing and safety evaluations.
5. Cryptography and Communications
Cryptography software protects information through mathematical algorithms. Despite mathematical algorithms being used, there can be errors within the software. This may affect the encryption key handling, authentication processes or state of the protocol which would affect the security of an otherwise reliable design. To ensure the software meets important security properties, engineers can use formal verification. This can help to ensure the cryptography software and protocol meet important security criteria. For example a developer can verify that confidential information cannot be accessed by an unauthorised party based on the assumptions within the security model.
Authentication protocols can also be verified to ensure they do not allow impersonation and communication processes can be verified that the confidentiality requirements are met. Formal verification is very useful within this type of software as it allows engineers to use logical reasoning. However, the cryptography software will need to be implemented, deployed and maintained to ensure it is protected.
Popular Formal Verification Tools
There are various tools available that can assist with formal verification. Different tools offer different features depending on the programming language, verification technique and complexity of the software.
- Coq
This tool allows users to perform interactive theorem proving. It uses a powerful logical system to help developers and mathematicians create formal proofs. Coq can be used to verify mathematical properties, algorithms and software components. The developer defines the proposition and uses a series of tactics to create a proof. This is checked by the kernel within Coq.
This can be very useful for projects where the mathematical aspects are important. It has been used to support research and development of verified programming languages, algorithms and software. This can be quite complex to learn as you need to have knowledge of formal logic and creating proofs. It provides a structured way of creating high reliability mathematical proofs.
- Isabelle
This is a general purpose interactive theorem proving tool. It can be used to formalise mathematical proofs and verify properties of software and hardware. It can support multiple logical systems and offers several tools to help build proofs. Software Engineers can use this tool to reason about algorithms, software and system properties.
This is useful for academics and projects where detailed mathematical analysis is needed. It also offers automated reasoning features which can help simplify some elements of the process. Some complex verification may be needed.
- Lean
Lean is a proof assistant that allows users to formalise mathematics. It can be used to create machine-checked proofs. It combines a programming language with a powerful logical system. This means users can create mathematical objects, propositions and prove that statements are true based on existing assumptions.
It is commonly used for formal mathematics. It can also be used to reason about software properties. It provides an interactive environment which can help developers create proofs. The proofs will be ensured to meet the logical rules of the system. This can be very useful for anyone who is interested in combining programming with mathematics.
- Frama-C
This is an analysis tool for verifying software written in C. It offers several analysis techniques to help understand how software will behave. It includes verification features using formal specifications and logical annotations.
Developers can analyse memory safety, functional correctness and other important properties of the C programs. This is particularly useful for embedded systems and safety critical software as C is commonly used.
Advantages of Formal Verification
Formal verification can offer many benefits to an organisation. As mathematical reasoning is used, it can increase the reliability of the software as it can be determined if the critical properties are met with the given assumptions. This reduces the chances of errors within the logic causing issues within the application once deployed. It can also increase the security of the software as restrictions, information protection and other security properties can be formally specified. Formal specifications can also increase the documentation of software.
This can make it easier for development teams to understand what is required and determine if the requirements are met. Finding defects at an early stage can reduce the cost and disruption caused by fixing issues. Formal methods can be very useful for software that supports critical services or performs actions that could cause serious issues if incorrect. Formal verification provides evidence that the software is correct based on mathematical reasoning. This makes the engineering process stronger.
Disadvantages of Formal Verification
Despite the benefits, Formal Verification can present several challenges. Large systems can be very complex with millions of lines of code, many components and complex interactions. Creating accurate mathematical specifications can be challenging due to the need to understand the requirements of the system in great detail. This can also be quite complex as it requires knowledge of mathematical logic, programming theory and specific tools.
It can also be very time consuming with large amounts of processing power needed. Proofs may also be difficult to create for complex algorithms. As the proof will only prove the properties under the given assumptions, there is no guarantee the full application will be safe if the specification is incomplete, incorrect or based on unrealistic assumptions. It is important to use formal verification strategically to ensure it is applied to components that are critical to be correct and reliable.
Formal Verification vs Testing
Formal verification can be very useful to improve the quality of software. However, it is different to traditional testing. Traditional testing involves running the program with certain inputs and determining if the actual outputs match expectations. This includes unit testing, integration testing, system testing and acceptance testing. This can be helpful to identify any real-world issues. However, this usually only tests a small number of scenarios.
Formal verification uses mathematical reasoning to determine if the properties will be met within the scenarios defined within the formal proof. For example, a developer may test a banking function for different transaction amounts. Whereas, formal verification can prove a mathematical property is met for all inputs that meet the preconditions. Neither can fully replace each other but combining both techniques will improve the overall quality of software.
Best Practice for Formal Verification
To successfully implement formal verification, it is important to plan ahead and understand the software being developed. Identify the components that would have the most impact if they were incorrect. This could include payment processing, authentication, medical devices and safety critical algorithms. Ensure requirements are defined clearly before creating mathematical specifications. Choose the right verification tool for your programming language and complexity of your application.
Provide training to your development teams and work with experts when creating complex proofs. Formal verification should be applied throughout the development lifecycle. Any important changes to the software should have their specifications and proofs reviewed. Combining this with code reviews, automated testing, security checks and continuous integration will help create more reliable applications.
The Future of Formal Verification
As software becomes more complex and is used for more critical operations, the importance of formal verification will increase. As new technologies develop such as artificial intelligence, autonomous transport, cloud computing, financial technology and connected devices, new challenges arise. These technologies often include complex algorithms and interactions. Improvements in automated theorem proving, model checking and verification tools have increased the accessibility of formal methods.
Artificial intelligence may help engineers by suggesting specifications, creating proof steps and identifying potential logical issues. However, care must be taken when reviewing automatically generated proofs and specifications to ensure they are correct. Formal verification may be more integrated with programming languages. This can help identify certain correctness issues early on within the code. As tools continue to improve, formal methods may become more practical for a wider variety of software.
Conclusion
Formal verification can be a useful tool within software engineering. Mathematical logic can be used to determine if the program meets the desired specifications. Various techniques can be used such as logical assertions, preconditions, postconditions, program invariants, Hoare logic, model checking, symbolic execution and theorem proving. This can help identify any potential issues with the software before deployment.
This can be very useful within critical industries such as banking, healthcare, aviation, transport, cryptography. Whilst it does require specialist knowledge, careful specifications and a lot of work to implement, it can be a powerful tool to create reliable programs. It cannot fully replace testing, security checks and real-world validation but can help compliment the tools. As software is becoming more influential within critical services, formal verification will continue to be an important tool within developing reliable, secure and consistent applications.
