@conference {365, title = {Transition Power Abstractions for Deep Counterexample Detection}, booktitle = {TACAS}, year = {2022}, publisher = {Springer LNCS series}, organization = {Springer LNCS series}, abstract = {

While model checking safety of infinite-state systems by inferring state invariants has steadily improved recently, most verification tools still rely on a technique based on bounded model checking to detect safety violations. In particular, the current techniques typically analyze executions by unfolding transitions one step at a time, and the slow growth of execution length prevents detection of deep counterexamples before the tool reaches its limits on computations. We propose a novel model-checking algorithm that is capable of both proving unbounded safety and finding long counterexamples. The idea is to use Craig interpolation to guide the creation of symbolic abstractions of exponentially longer sequences of transitions. Our experimental analysis shows that on unsafe benchmarks with deep counterexamples our implementation can detect faulty executions that are at least an order of magnitude longer than those detectable by the state-of-the-art tools.

}, url = {https://link.springer.com/chapter/10.1007/978-3-030-99524-9_29}, author = {Martin Blicha and Grigory Fedyukovich and Antti E. J. Hyv{\"a}rinen and Natasha Sharygina} } @conference {334, title = {Theory-Specific Proof Steps Witnessing Correctness of SMT Executions}, booktitle = {DAC 2021 - 58th Design Automation Conference}, year = {2021}, month = {11/2021}, publisher = {IEEE}, organization = {IEEE}, address = {San Francisco, CA, USA}, doi = {10.1109/DAC18074.2021.9586272}, author = {Rodrigo Otoni and Martin Blicha and Patrick Eugster and Antti E. J. Hyv{\"a}rinen and Natasha Sharygina} } @proceedings {238, title = {Theory Refinement for Program Verification}, year = {2017}, publisher = {Springer LNCS series}, address = {Melbourne, Australia}, abstract = {
Recent progress in automated formal verification is to a large degree\ due to the development of constraint languages that are sufficiently light-weight for reasoning but still expressive enough to prove\ properties of programs. Satisfiability modulo theories (SMT) solvers implement efficient\ decision procedures, but offer little direct support for adapting the constraint language to the task at hand. Theory refinement\ is a new approach that modularly adjusts the\ modeling precision based on the properties being verified through the use of\ combination\ of theories. We implement the approach using an augmented version of the theory of\ bit-vectors and uninterpreted functions capable of directly injecting\ non-clausal refinements to the inherent Boolean structure of SMT. In our comparison to a state-of-the-art model checker, our prototype\ implementation is in general competitive, being several orders of magnitudes faster on some instances that are challenging for flattening,\ while computing models that are significantly more succinct.
}, url = {http://verify.inf.usi.ch/hifrog/theoref}, author = {Antti E. J. Hyv{\"a}rinen and Sepideh Asadi and Karine Even Mendoza and Grigory Fedyukovich and Hana Chockler and Natasha Sharygina} } @conference {202, title = {Towards completeness in Bounded Model Checking through Automatic Recursion Depth Detection}, booktitle = {Brazilian Symposium on Formal Methods (SBMF)}, year = {2014}, address = {Maceio, Brazil.}, author = {Grigory Fedyukovich and Natasha Sharygina} } @conference {154, title = {Termination Analysis with Compositional Transition Invariants}, booktitle = {International Conference on Computer-Aided Verification (CAV)}, year = {2010}, publisher = {Springer}, organization = {Springer}, address = {Edinburgh, UK}, abstract = {

Modern termination provers rely on a safety checker to construct disjunctively well-founded transition invariants. This safety check\ is known to be the bottleneck of the procedure. We present an alternative algorithm that uses a light-weight check based on transitivity of\ ranking relations to prove program termination. We provide an experimental evaluation over a set of 87 Windows drivers, and demonstrate\ that our algorithm is often able to conclude termination by examining\ only a small fraction of the program. As a consequence, our algorithm is\ able to outperform known approaches by multiple orders of magnitude.\ 

}, author = {Kroening, D. and Natasha Sharygina and Tsitovich, A. and Wintersteiger, C.M.} }