In the early stages of designing a complex system—whether it is a randomized algorithm, a robot controller, or a communication protocol—engineers rarely have exact numbers. Transition probabilities might depend on environmental noise, and data structures like arrays might have sizes that vary by deployment.
Traditional formal verification requires concrete numerical values to compute the probability of a system failing or reaching a goal. However, a growing body of research suggests a more flexible approach: treating these unknowns as symbolic parameters. By shifting from numerical computation to symbolic algebraic manipulation, researchers can verify entire classes of systems at once and synthesize the exact parameter ranges that guarantee safety.
From Numbers to Rational Functions
Standard probabilistic model checking treats a system as a Markov chain with fixed transition probabilities. To check a property, such as the probability of reaching an error state, one typically solves a system of linear equations.
As Jansen et al. 2014 and Jansen et al. 2013 argue, this is insufficient for early-stage design. When probabilities are symbolic variables (e.g., $p$ and $1-p$), the result of verification is no longer a single number, but a rational function—a ratio of polynomials in those parameters. This function describes how the system's behavior changes across all possible values of $p$.
The challenge is that symbolic manipulation is computationally expensive. To address this, Jansen et al. 2013 proposed accelerating this process by decomposing Markov chains into strongly connected components and using advanced polynomial factorization, achieving speedups of several orders of magnitude.
Synthesizing Optimal Configurations
Once we can represent system properties as functions of parameters, the problem shifts from verification (does this work?) to synthesis (what values make this work best?).
Jovanovic et al. 2014 and Marta Kwiatkowska describe this as finding parameter valuations that maximize or minimize the probability of reaching specific states. This is particularly useful for cyber-physical systems where one might need to tune time delays or transition rates to ensure a physical goal is met.
This synthesis often involves navigating complex, non-linear spaces. Liu et al. 2016 showed that by translating temporal logic formulas into specialized automata, the search for valid parameters can be framed as a satisfiability problem for SMT solvers. This allows researchers to identify continuous regions of valid configurations, providing designers with a "tolerance window" rather than a single point solution, as noted by Bartocci et al. 2020.
Inducting Over Symbolic Sizes
A distinct but related facet of this research concerns symbolic size induction. When verifying programs that manipulate arrays, the "parameter" is often the size of the data structure, $N$.
Traditional verification struggles here because it tries to find "loop invariants"—logical statements that hold true for every iteration of a loop. Finding these is notoriously difficult. Chakraborty et al. 2020 and Afzal et al. 2020 propose a technique called full-program induction.
Instead of inducting over loop iterations, the authors induct over the global parameter $N$. By proving a property holds for a base case (e.g., $N=1$) and then showing that if it holds for $N-1$ it must hold for $N$, the verifier can bypass the need for explicit loop invariants entirely. As Chakraborty et al. 2022 demonstrate, this approach allows tools like VAJRA to prove complex, non-linear properties of array programs that stymie traditional iterative verifiers.
The Complexity of Uncertainty
While symbolic methods are powerful, they come with steep theoretical costs. Winkler et al. 2019 and Junges et al. 2021 established that determining if there exist parameter values that satisfy a reachability goal in a parametric Markov Decision Process (pMDP) is ETR-complete. This means the problem is as fundamentally difficult as deciding the truth of first-order sentences about the real numbers.
Despite this complexity, the shift toward symbolic reasoning allows for more robust verification. For instance, Bartocci et al. 2019 showed how to generate closed-form invariants for higher-order moments (like variance) in probabilistic loops with symbolic constants. Similarly, Hsu et al. 2018 demonstrated that by synthesizing "coupling proofs," one can reason about probabilistic programs as abstract entities, avoiding manual numerical calculations entirely.
By treating uncertainty not as a missing value but as a symbolic parameter, these techniques provide a mathematical framework for ensuring that systems remain safe and efficient, regardless of the specific environment or scale they encounter.
Key Foundational Work
Parameter Synthesis for Probabilistic Timed Automata Using Stochastic Game Abstractions (2014) — contributed 2 concept elements to this direction.
Minimal counterexamples for linear-time probabilistic verification (2014) — contributed 1 concept elements to this direction.
Accelerating Parametric Probabilistic Verification (2013) — contributed 1 concept elements to this direction.