Skip to content

Compiler Testing.md

Latest commit

 

History

History
51 lines (47 loc) · 3.49 KB

Compiler Testing.md

File metadata and controls

51 lines (47 loc) · 3.49 KB
Raw

Why Compilers?

Compilers are a key part of software development:

  • Correctness is relied upon
  • Compiler bugs can affect derived analysis tools that test for program correctness
  • Can induce bugs in compiled software that are very difficult to debug Compilers are also incredibly complex, and can be in the millions of lines (e.g. gcc, or clang + llvm).
Bug Type Description Danger
Crash Causes the compiler to fail to compile a program. Prevents complex projects from building (difficult for the developer to determine how to fix build). Affects developer trust in the compiler.
Miscompilation Compilation is successful, but the output is incorrect. Very difficult for a developer to debug (debugging , analysis tools & tests can be affected). reduces trust in compiler.

Testing Difficulty

  • [[Undefined Behaviour]], [[Unspecified Behaviour]] or [[Implementation Defined Behaviour]] dependent (e.g. target architecture) behaviour.
  • lack of clear language semantics, specifications not thoroughly
  • compiler defined languages i.e. the chosen definition is the implementation allows arguability about bugs.
  • No oracle to define exactly output or the proper behaviour of output.
  • Output can include non-determinism (i.e. from IO), and non-termination

There is no [[Oracle]] practically buildable for a complex, Turing complete language compiler's output (would effectively be building a reference compiler, which itself needs to be tested).

As a result compilers are considered [[Non-Testable Programs]].

Alternative Oracles

Bug Type Description Difficulty
Crash Bugs Need to run the compiler on fuzzed inputs, can check for crashes (as well as other bugs via [[Dynamic Analysis]] - e.g. instrumentation with [[Compiler Sanitizers]]) Relatively Easy
Miscompilation As per [[Compiler Testing#Testing Difficulty|testing difficulties]] we cannot check compiler output correctness entirely, but we can place more limited checks on the output. Difficult

CrossCheck Implementations

Use [[Differential Testing]] to check output.

  1. Produce input (valid for language standard)
  2. Invoke with many different standard-compliant compilers
  3. Run output binaries
  4. Compare results (stdout, stderr, etc) The main limitations:
  • Programs must be free of [[Undefined Behaviour]] and [[Unspecified Behaviour]]
  • Compilers must agree on [[Implementation Defined Behaviour]]
  • Multiple compilers must be available (e.g. different versions of the same compiler (or with different optimisations) to check for regressions, or entirely independent compilers)
  • Programs must be deterministic (when run we provide same inputs, expect same outputs) (limits more complex & necessarily nondeterministic )

CrossCheck Equivalent Programs

Use [[Metamorphic Testing]] to check output.

  1. Take a program, and generate or manually create multiple standard-defined equivalent programs (e.g. vanilla vs optimised, different implementations of the algorithm, automatically generated by semantically idempotent transformations).
  2. Compile and run the programs
  3. Check the program outputs Limitations:
  • Programs must be free of [[Undefined Behaviour]] and [[Unspecified Behaviour]] [[Random Program Generation]] is used for this.

Does it Matter?

Ulta-Rare bugs only found in artificial examples.

  • From a developer perspective, other that trust in the compiler, usually no.
  • From a compiler writer perspective, can indicate other bugs, often argued.
  • From a security standpoint - yes!