logo
ProjectForthcoming

Sparsity-guided Efficient SMT-solving for Program Verification

The status, timeline and source of this project. A free account opens every field.

Source: EU Funding & Tenders Portal

Satisfiability modulo theories (SMT) is a ubiquitous framework in modern software verification. It can express a significant number of classical program verification tasks, e.g. invariant generation, reachability and pre/post-conditions, in complex programs with arrays, pointers, real/integer variables, and user-defined data structures. State-of-the-art SMT solvers, such as cvc5/Z3, form the backb

Status
Prospective
Sector
Education
Location
United Kingdom
Updated
19 Nov 2026
Source
EU Funding & Tenders Portal

ConstructChat

Ask ConstructChat about Sparsity-guided Efficient SMT-solving for Program Verification

Pick a question to edit it, or write your own.

First answer free · no account

I am a

Project Information FAQ

Project Information

3 Q
The project “Sparsity-guided Efficient SMT-solving for Program Verification” is an infrastructure initiative in the Education sector, located in United Kingdom. Taiyo aggregates data on it from EU Funding & Tenders Portal.

Participants

Not available for this record.

Status

Original status

forthcoming

Taiyo status

Prospective

Taiyo last update

2026-11-19

Contact

Not available for this record.

Description

Description

Satisfiability modulo theories (SMT) is a ubiquitous framework in modern software verification. It can express a significant number of classical program verification tasks, e.g. invariant generation, reachability and pre/post-conditions, in complex programs with arrays, pointers, real/integer variables, and user-defined data structures. State-of-the-art SMT solvers, such as cvc5/Z3, form the backbone of modern verification suites. Unfortunately, SMT-based verification methods are far from perfect in terms of scalability. They are especially slow when the desired property depends on a large portion of the program, such as a function with hundreds/thousands of lines. A primary reason is that solvers are designed for *general-purpose* constraint-solving. When a program analysis tool, such as Boogie, reduces a verification task to SMT and passes it to a solver, such as Z3, the solver has no knowledge of the original program or any of its structural and sparsity properties that are inherited by the SMT instance. Thus, it spends significant time exploring unpromising solution paths or applying unproductive heuristics. In this project, we will exploit the structural sparsity of programs to design faster bespoke SMT-solving algorithms for software verification tasks. It is well-known that control-flow graphs of structured programs are sparse and decomposable. Formally, they have bounded treewidth/pathwidth. Thus, one can successively find small cuts that decompose the graphs into parts of a small size. The idea is to guide the SMT-solver with a promising approximation or decision order based on these decompositions. This is because the SMT instance inherits the sparsity and structure of the underlying program. Thus, it can be decomposed into small parts by successively solving low-dimensional sub-instances. More specifically, this project will use the decomposition to design faster algorithms for satisfiability checking and (approximate) quantifier/variable elimination.

Location

Country

United Kingdom (UK)

Source

Source

EU Funding & Tenders Portal

URL

More Details

Record type

Project

Sector

Education

Article published date

2026-02-01

More on this project

Research

Free account

View all details

You are reading the public part. A free account opens the rest:

  • Every detail on this project
  • News and media coverage
  • Technical research
View all details

Free account · no card · lands you back on this project