Training Binary Classifiers as Data Structure Invariants
Authors:
Open Access
- 1 May 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 759-770
Abstract
We present a technique to distinguish valid from invalid data structure objects. The technique is based on building an artificial neural network, more precisely a binary classifier, and training it to identify valid and invalid instances of a data structure. The obtained classifier can then be used in place of the data structure's invariant, in order to attempt to identify (in)correct behaviors in programs manipulating the structure. In order to produce the valid objects to train the network, an assumed-correct set of object building routines is randomly executed. Invalid instances are produced by generating values for object fields that "break" the collected valid values, i.e., that assign values to object fields that have not been observed as feasible in the assumed-correct executions that led to the collected valid instances. We experimentally assess this approach, over a benchmark of data structures. We show that this learning technique produces classifiers that achieve significantly better accuracy in classifying valid/invalid objects compared to a technique for dynamic invariant detection, and leads to improved bug finding.Keywords
This publication has 26 references indexed in Scilit:
- Symbolic PathFinder: integrating symbolic execution with model checking for Java bytecode analysisAutomated Software Engineering, 2013
- Artificial neural networks as multi-networks automated test oracleAutomated Software Engineering, 2011
- An automated framework for software test oracleInformation and Software Technology, 2011
- Code Contracts for .NET: Runtime Verification and So Much More2010
- The Daikon system for dynamic detection of likely invariantsScience of Computer Programming, 2007
- JWalk: a tool for lazy, systematic testing of java classes by design introspection and user interactionAutomated Software Engineering, 2007
- Kodkod: A Relational Model Finder2007
- Automatic Testing of Object-Oriented Software2007
- Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential ImpactEmpirical Software Engineering, 2005
- Isomorph-free model enumerationACM Transactions on Programming Languages and Systems, 1998