Master's thesis

Constraint Horn Clauses as a Verification Back-End for LLM-Generated C++ Specifications

Hochschule München University of Applied SciencesAEMY

Constraint Horn Clauses as a Verification Back-End for LLM-Generated C++ Specifications

Hochschule München is among the largest German universities of applied sciences, located at the heart of Munich, Germany. The working group "AEMY" focuses on safe, secure and smart systems. Our main working areas include RISC-V processor design, WebAssembly runtime development and open source chip design tools.

ACSLGen is our tool that uses AI agents to automatically generate formal ACSL++ specifications for C++ programs, such as function contracts, loop invariants, and class invariants, which are then proven with Frama-C. Deductive verification is powerful but slow, and when a proof fails, the agents get little feedback on why it failed.

Constraint Horn Clauses (CHCs) offer a complementary approach. Program semantics and candidate invariants are encoded as logical clauses and solved automatically by tools such as Z3 Spacer and Eldarica. CHC solvers can quickly refute incorrect invariants with concrete counterexamples, and they can also synthesize invariants on their own.

In this thesis, you will integrate a CHC back end into ACSLGen. Invariants generated by the AI agents are checked with CHC solvers, and the counterexamples are used to repair them. The result is faster feedback and more invariants that can be proven. Potential areas of focus include:

  • Encoding C++ functions and object state (constructors, methods, class invariants) as CHCs
  • Translating ACSLGen’s candidate loop and class invariants into CHC queries
  • Feeding CHC counterexamples back to the AI agents to repair wrong invariants
  • Using invariants synthesized by CHC solvers as hints for the agents
  • Comparing CHC-based checking with Frama-C/WP in terms of success rate and runtime

This project offers an opportunity to gain hands-on experience in static analysis tools and CHCs. For further information or to express your interest feel free to reach out.