IEEE Transactions on Software Engineering · 2020 · 22 citations · 48 references
Language StudiesComputer ScienceComputational LinguisticsNatural Language ProcessingSyntaxGrammarParsingSyntactic AnalysisSyntactic ParsingSyntax AnalysisSyntax ParsingGrammar Learning From Examples
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Grammars</i> can serve as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">producers</i> for structured test inputs that are syntactically correct by construction. A probabilistic grammar assigns probabilities to individual productions, thus controlling the distribution of input elements. Using the grammars as input parsers, we show how to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">learn input distributions from input samples,</i> allowing to create inputs that are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">similar</i> to the sample; by <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">inverting</i> the probabilities, we can create inputs that are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dissimilar</i> to the sample. This allows for three <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">test generation strategies</i> : 1) “Common inputs”–by learning from common inputs, we can create inputs that are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">similar</i> to the sample; this is useful for regression testing. 2) “Uncommon inputs”–learning from common inputs and inverting probabilities yields inputs that are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">strongly dissimilar</i> to the sample; this is useful for completing a test suite with “inputs from hell” that test uncommon features, yet are syntactically valid. 3) “Failure-inducing inputs”–learning from inputs that caused failures in the past gives us inputs that share similar features and thus also have a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">high chance of triggering bugs</i> ; this is useful for testing the completeness of fixes. Our evaluation on three common input formats (JSON, JavaScript, CSS) shows the effectiveness of these approaches. Results show that “common inputs” reproduced 96 percent of the methods induced by the samples. In contrast, for almost all subjects (95 percent), the “uncommon inputs” covered significantly different methods from the samples. Learning from failure-inducing samples reproduced all exceptions (100 percent) triggered by the failure-inducing samples and discovered new exceptions not found in any of the samples learned from.
48
Koushik Sen, Darko Marinov, Gul Agha · 2005 · 1.7K citations
Patrice Godefroid, Nils Klarlund, Koushik Sen · 2005 · 1.5K citations
A Survey on Software Fault Localization
W. Eric Wong, Ruizhi Gao, Yihao Li et al. · IEEE Transactions on Software Engineering · 2016 · 1.1K citations
Gordon Fraser, Andrea Arcuri · 2011 · 1K citations