Applying Formal Methods to Software Development, Explained

UPI Study › Courses › Software Engineering › Free lessons › Lesson 11.3 Free with a free account

Applying Formal Methods to Software Development

Software Engineering · Chapter 11: Requirements Validation, Dependability, and Formal MethodsSection 11.3 · lesson 74 of 1038 min · free with a free account

← What Makes a System Dependable? Core Properties and GoalsNext lesson: Reliability Engineering: Definitions, Goals, and Getting Started →

Earn 3 college credits for Software EngineeringRecommended for credit by NCCRS · Computer Science 301 · self-paced · one payment, lifetime access
Enroll in Software Engineering · $250 →Download the syllabus (PDF)

In this lesson

Proving correctness for every input - and when that rigor is worth its cost.

  • Explain how formal verification differs from testing
  • Describe formal specification, and why it uses mathematics
  • Describe preconditions, postconditions, and invariants
  • Judge when formal methods are worth applying

Transcript

Everything said in the video, section by section (1,040 words). Read along, or search it.

Requirements Validation, Dependability, and Formal Methods

Applying Formal Methods to Software Development

Testing can show that the cases you tried worked. It can never show that every case works. This section covers formal verification, which takes a fundamentally different approach. It covers formal specification, the building blocks of a correctness proof, and the tradeoffs that decide when this rigor is worth it.

Confidence vs. Certainty

50 Passing Tests

A payment-processing function passes fifty carefully chosen test cases, without a single issue. The team is confident. But confidence is not certainty. Somewhere among the inputs nobody tried, an edge case could still be lurking. A passing test shows that one case worked. It never shows that every case would. Formal verification takes a different approach. Instead of trying more inputs, it uses mathematical proof. It establishes that a piece of code behaves correctly for every input satisfying its precondition, not just the ones anyone thought to try.

Figure 1

Sampling vs. Proving

Testing samples the space of possible inputs. It runs a program against a chosen set of cases, and checks the results. It can show that a defect is present, but never that defects are completely absent. Formal verification constructs a mathematical proof instead. A successful proof covers every allowed input at once, by construction. That guarantee has an important limit. A proof only guarantees that the program matches its formal specification. If the specification itself does not capture the real need, that is a validation problem. Formal verification does not replace validation.

Table 1

Testing vs. Formal Verification

Here are the two approaches side by side. Testing checks a chosen sample of possible inputs. Formal verification checks every input the specification allows. A passing test means no defect was found in the cases tried. A successful proof means a mathematical guarantee across all cases. And the costs differ. Testing is moderate, and scales roughly with the effort spent. Formal verification is high, and grows steeply with complexity.

Formal Specification

Requirements in Mathematics

A formal specification states precisely, in mathematical notation like logic or set theory, what a program must do. Natural language is open to more than one reading. A well-formed mathematical statement has exactly one meaning. Take a requirement written in plain language. Return the larger of the two numbers. A formal version states it precisely. Given any two numbers x and y, the result equals x when x is greater than or equal to y, and equals y otherwise. Several formal notations exist. What matters here is the underlying idea, not any one syntax.

Table 3

The Building Blocks of a Proof

A correctness proof is built from three basic pieces. A precondition states what must be true before a piece of code runs. It is the starting assumption the proof is allowed to rely on. A postcondition states what the code guarantees will be true afterward. It is the claim the proof sets out to establish. And an invariant is a condition that stays true throughout every iteration of a loop. It is the link that connects each iteration to the next, and finally to the postcondition.

Figure 2

An Invariant at Work

Here is a loop that sums the numbers from one to n. The precondition says n is not negative. The postcondition says the total equals one plus two, and so on, up to n. The invariant says that at each step, the total equals the sum of the numbers up to the current counter. The argument always has the same shape. Show the invariant holds before the loop begins, and that every iteration preserves it. Then show that when the loop ends, the invariant together with the ending condition implies the postcondition.

Proving Correctness

A Rigorous Argument

So what does proving a program correct actually mean? It means constructing a rigorous logical argument, following the rules of formal logic, that connects the precondition to the postcondition, through every path the code could take. It does not necessarily require a mechanized theorem-proving tool. It means each step follows necessarily from the last, rather than being merely persuasive. The payoff is real. Mathematical certainty, covering every case the specification allows. The cost is real too. It takes specialized mathematical skill and significant time, and it still depends on the specification having been validated.

Figure 3

Why Proofs Don't Scale Gracefully

There is another reason formal methods are applied selectively. They do not scale gracefully. This chart is illustrative. As a component grows in size and complexity, testing effort grows roughly in step. Proof effort grows far more steeply. That is why formal methods are rarely applied to an entire large system, end to end.

Table 4

When Formal Methods Earn Their Cost

Formal methods tend to earn their cost in specific situations. Small, well-bounded components, where the consequence of failure is severe, where testing alone struggles to build confidence, and where the expertise is actually available. Flight control software fits. A defect could be catastrophic, and the core logic is often small and stable. So do security kernels and protocols, where a single flaw can undermine everything built on top. Medical device firmware fits, because patient safety depends on correctness. And so do industrial safety interlocks, which are small, and carry physical risk.

Apply It

Proving Every Utility Function

Let's apply that. A team decides to formally verify every function in a large, ordinary business application, including simple, low-stakes utility functions. It consumes months of specialized effort, with little reduction in defects after release. What went wrong? They applied formal verification as a default, rather than selectively. Proof effort scales steeply. For low-stakes code, testing alone would have built enough confidence, far more cheaply.

Key Terms

The Vocabulary of This Section

Let's lock in the key terms. Formal verification uses mathematical proof to establish that a program satisfies its specification, for every input the specification allows. A formal specification is a precise statement, in mathematical notation, of what a program must do. A precondition is what must be true before code runs. A postcondition is what the code guarantees afterward. And an invariant stays true through every iteration of a loop. A proof is a rigorous logical argument, connecting a precondition to a postcondition through every path the code could take.

Key Takeaways

What to Carry Forward

To pull this together. Testing samples the space of inputs. Formal verification proves correctness for every allowed input at once. Formal specifications use mathematical notation to remove the ambiguity of natural language. Preconditions, postconditions, and invariants are the building blocks a proof connects together. A proof guarantees that a program matches its specification, not that the specification is right. And formal methods are applied selectively, to small, high-consequence components, because proof effort scales so steeply.

About Software Engineering at UPI Study

Software Engineering (Computer Science 301) is a self-paced online course of 103 video lessons in 15 chapters, from process models and agile to requirements, design, user interfaces, reliability, security and project management. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Software Engineering vs Systems Analysis

Why take it here

Why students take Software Engineering with UPI Study

How professional software gets builtSoftware Engineering covers how teams turn requirements into working, maintainable software: process models, agile, requirements, design, testing, reliability and project management. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Software Engineering carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Applying Formal Methods to Software Development

How is formal verification different from software testing?
Testing runs a program on a chosen sample of inputs, so it can show a defect is present but never that defects are absent. Formal verification constructs a mathematical proof that code behaves correctly for every input satisfying its precondition. The trade-off is cost: testing cost is moderate and scales with the effort spent, while proof effort grows steeply with complexity. A proof also only shows the code matches its specification.
What is a formal specification and why does it use mathematics?
A formal specification states precisely, in mathematical notation such as logic or set theory, what a program must do. It uses mathematics because natural language can be read more than one way, while a well-formed mathematical statement has exactly one meaning. For example, "return the larger of two numbers" becomes: for any x and y, the result equals x when x is greater than or equal to y, and y otherwise.
How does a loop invariant help prove a loop correct?
A loop invariant is a condition that stays true on every iteration, linking each pass to the next and finally to the postcondition. The proof has a fixed shape: show the invariant holds before the loop starts, show every iteration preserves it, then show that the invariant plus the exit condition imply the postcondition. For a loop summing 1 to n, with n not negative, the invariant is that the total equals the sum up to the current counter.
Why is formal verification rarely applied to an entire large system?
Because proof effort does not scale gracefully: as a component grows in size and complexity, testing effort grows roughly in step, but proof effort grows far more steeply. Formal methods therefore earn their cost on small, well-bounded components where failure would be severe, such as flight control software, security kernels, and medical device firmware. Formally verifying every function of an ordinary business application can consume months of specialized effort for little reduction in defects.

About the Software Engineering course

How many college credits is Software Engineering?
Software Engineering (Computer Science 301) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Software Engineering cost and what is included?
$250, paid once, with lifetime access: all 103 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Software Engineering take?
It is self-paced with no deadlines. The 103 lessons total about 11 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Software Engineering.

103 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Software Engineering →Download the syllabusEvery course with PRO →
Software Engineering
3 credits · NCCRSEnroll →