Certified complexity


The project aims to the construction of a formally verified complexity preserving compiler from a large subset of C to some typical microcontroller assembly, of the kind traditionally used in embedded systems. The work comprise the definition of cost models for the input and target languages, and the machine-checked proof of preservation of complexity (concrete, not asymptotic) along compilation. The compiler will also return tight and certified cost annotations for the source program, providing a reliable infrastructure to draw temporal assertions on the executable code while reasoning on the source.\nThe compiler will be open source, and all proofs will be public domain.

  • Status
  • Completed
  • Project Launch
  • 01 February 2010
  • Project completed
  • 31 March 2013
ICT complexity compiler certified complexity