Validation and Verification


  • There are three basic methods of verifying and validating code

    • Inspection
    • Testing
    • Formal methods


  • A primary method in open source

  • Whole program review / module review: results logged in issue tracker

  • Pull request review: Github has special modes for this

  • "Many eyes make all bugs shallow" —somebody, maybe

Facilitating Inspection

  • Show all your code

  • Everything should be easy to access and understand

  • Developer documentation is real

  • Invite inspection by the community


  • For where inspection fails (not other way around)

  • Pervasive in industry; rapidly becoming pervasive in open source

A Test Is An Input-Output Pair

  • This includes "should fail" negative tests

  • How to get correct outputs? (the "effective oracle" problem)

    • Slow but correct code (but few tests)
    • Working backward from output to input
    • "Easy" inputs

Testing Doesn't Work

  • Space of possible tests is ridiculously big, like 10^1000

  • Tests can only fail

  • Test failures usually give minimal insight

  • Best that can be hoped for is to test enough cases a user might encounter that the program is known to "kind of" work

Opaque Box vs Clear Box

  • Opaque Box: Tests given without knowledge of implementation

  • Clear Box: Use implementation knowledge to construct tests

  • Both are valuable

Test Domains

  • Idea: Divide input or output space up such that only one representative in each domain need be tested

    • How to draw domain boundaries?
    • There are still a lot
    • Better idea: formal methods plus testing

Testing Kinds

  • What should be tested?

    • System (acceptance)
    • Unit
    • Integration
    • Regression
  • Integration testing can be

    • bottom-up
    • top-down

Testing Methods

  • Random (e.g. "fuzz testing")

  • "User Tests"

  • Code-driven

  • Domain-driven

  • Coverage-driven

Regression Tests

  • Bugs can come back, tests are expensive: run tests after every change

  • Debugging: Write tests for every fix, add tests to regression test suite

Test and Integration Frameworks

  • "Test-driven development" says write tests first, then code to pass tests: typically unit tests and/or system tests

  • Idea is to always run tests ("regression test")

    • So build environment + code is always full of tests
    • Without automatic support from tools, this gets ugly fast
  • Integrated with build environment for "continuous integration"

  • Lots and lots of unit testing and CI tools and frameworks out there

Coverage Testing

  • How much of the program has been tested?

    • All statements?
    • All branches (each way)?
    • All code paths?
    • All data patterns?
  • Automated tools (e.g. gcov) exist

  • 100% coverage is impossible

  • Untested code is broken code

Testing Infrastructure

  • Tests need to be maintained with code

  • Tests need to be runnable automatically

  • Test failures need to be logged as tickets until fixed

Formal Methods

  • A footnote; always a footnote

  • Formal methods involve

    • Writing down a mathematical model of a system
    • Using that model to verify system properties
  • Not a validation technique

  • Not related to "formal inspection"

  • Can be used for requirements, design, implementation

Last modified: Thursday, 30 July 2020, 1:57 AM