Lec 44: Equivalence Checking between Programs

Lec 44: Equivalence Checking between Programs

by Prof. Chandan Karfa · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UMZSoftware EngineeringUMZTSoftware testing and verification
🎙 Prof. Chandan Karfa 👥 229K 📅 September 10, 2026 ⏱ 50 min 👁 1 📄 tutorial 🧭 2026-09-10
Available in: English (current) Français

Keywords

equivalence checkingcompiler bugtranslation validationundecidabilityFSMD

Summary

This lecture introduces the concept of equivalence checking between programs, focusing on verifying that two programs compute the same function. It motivates the problem through compiler optimizations, where a buggy compiler might produce non-equivalent code. Two strategies are discussed: verified compilers (e.g., CompCert) and translation validation, where each transformation is checked for equivalence. The speaker notes that general equivalence checking is undecidable, giving the McCarthy 91 function as an example. The lecture then proposes representing programs as Finite State Machines with Datapath (FSMD), which separates control and data flow. It explains how to construct an FSMD from a program and defines paths, execution conditions, and data transformation. The session also addresses granularity issues: line-by-line and basic-block-level equivalence checking are insufficient when code moves across loop boundaries. The approach is to break the program into paths and combine their equivalence proofs.

140 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a solid foundation for understanding formal verification of software. The argumentation is clear: starting with practical compiler bugs, moving to theoretical undecidability, and then proposing a structured representation. The example of McCarthy 91 demonstrates the difficulty of equivalence proofs. The discussion of granularity highlights practical challenges.

Scientific Rigor, Source Quality, Title Accuracy

The lecture maintains scientific rigor by referencing well-known concepts like compiler bugs and verified compilers. However, sources are primarily implicit; it mentions GCC bug reports and CompCert without providing direct references in the slides. The title accurately reflects the content.

104 words

Title / Content Match

The title accurately describes the lecture's focus on equivalence checking between programs.

Quality & Reliability

8/10

The lecture is delivered by an IIT professor and provides a formal treatment of equivalence checking, including undecidability and technical definitions. The content is accurate but limited to the course scope.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Contribution & Novelties

This lecture provides a structured introduction to equivalence checking, contrasting with naive FSM approaches, and introducing the FSMD model for program representation. It underlines the pitfalls of basic-block-level equivalence when code moves across loops.

Pour aller plus loin :

  • McCarthy 91 function — Illustrates undecidability of equivalence and complexity of recursive program analysis.
  • Translation validation — Technique to verify compiler transformations without proof of compiler correctness.
  • CompCert — A formally verified C compiler that only applies proven optimizations.

78 words

Radar Profile

The radar profile shows high technical depth and reliability, moderate information quantity, and strong formal-method orientation.

Reliability 8/10