Sigma*: symbolic learning of input-output specifications. We present Sigma*, a novel technique for learning symbolic models of software behavior. Sigma* addresses the challenge of synthesizing models of software by using symbolic conjectures and abstraction. By combining dynamic symbolic execution to discover symbolic input-output steps of the programs and counterexample guided abstraction refinement to over-approximate program behavior, Sigma* transforms arbitrary source representation of programs into faithful input-output models. We define a class of stream filters---programs that process streams of data items---for which Sigma* converges to a complete model if abstraction refinement eventually builds up a sufficiently strong abstraction. In other words, Sigma* is complete relative to abstraction. To represent inferred symbolic models, we use a variant of symbolic transducers that can be effectively composed and equivalence checked. Thus, Sigma* enables fully automatic analysis of behavioral properties such as commutativity, reversibility and idempotence, which is useful for web sanitizer verification and stream programs compiler optimizations, as we show experimentally. We also show how models inferred by Sigma* can boost performance of stream programs by parallelized code generation.
Keywords for this software
References in zbMATH (referenced in 11 articles , 1 standard article )
Showing results 1 to 11 of 11.
- Angluin, Dana; Fisman, Dana: Regular (\omega)-languages with an informative right congruence (2021)
- Chockler, Hana; Kesseli, Pascal; Kroening, Daniel; Strichman, Ofer: Learning the language of software errors (2020)
- Fisman, Dana: Inferring regular languages and (\omega)-languages (2018)
- Drews, Samuel; D’Antoni, Loris: Learning symbolic automata (2017)
- Moerman, Joshua; Sammartino, Matteo; Silva, Alexandra; Klin, Bartek; Szynwelski, Michał: Learning nominal automata (2017)
- Cassel, Sofia; Howar, Falk; Jonsson, Bengt; Steffen, Bernhard: Active learning for extended finite state machines (2016)
- Chapman, Martin; Chockler, Hana; Kesseli, Pascal; Kroening, Daniel; Strichman, Ofer; Tautschnig, Michael: Learning the language of error (2015)
- D’Antoni, Loris; Veanes, Margus: Extended symbolic finite automata and transducers (2015)
- Veanes, Margus: Symbolic string transformations with regular lookahead and rollback (2015)
- Isberner, Malte; Howar, Falk; Steffen, Bernhard: Learning register automata: from languages to program structures (2014)
- Botinčan, Matko; Babić, Domagoj: Sigma(^*), symbolic learning of input-output specifications (2013)