Parallel test generation and execution with Korat

Sasa Misailovic, Aleksandar Milicevic, Nemanja Petrovic, Sarfraz Khurshid, Darko Marinov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present novel algorithms for parallel testing of code that takes structurally complex test inputs. The algorithms build on the Korat algorithm for constraint-based generation of structurally complex test inputs. Given an imperative predicate that specifies the desired structural constraints and a finitization that bounds the desired input size, Korat performs a systematic search to generate all test inputs (within the bounds) that satisfy the constraints. We present how to generate test inputs with a parallel search in Korat and how to execute test inputs in parallel, both off-line (when the inputs are saved on disk) and on-line (when execution immediately follows generation). The inputs that Korat generates enable bounded-exhaustive testing that checks the code under test exhaustively for all inputs within the given bounds. We also describe a novel methodology for reducing the number of equivalent inputs that Korat can generate. Our development of parallel Korat and the methodology for reducing equivalent inputs are motivated by testing an application developed at Google. The experimental results on running parallel Korat across up to 1024 machines on the Google's infrastructure show that parallel test generation and execution can achieve significant speedup, up to 543.55 times.

Original languageEnglish (US)
Title of host publication6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2007
Pages135-144
Number of pages10
DOIs
StatePublished - Dec 1 2007
Event6th Joint Meeting of the European Software Engineering Conference and the 14th ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2007 - Dubrovnik, Croatia
Duration: Sep 3 2007Sep 7 2007

Publication series

Name6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2007

Other

Other6th Joint Meeting of the European Software Engineering Conference and the 14th ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2007
CountryCroatia
CityDubrovnik
Period9/3/079/7/07

Keywords

  • Bounded-exhaustive testing
  • Korat
  • Parallel testing
  • Test data generation

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Parallel test generation and execution with Korat'. Together they form a unique fingerprint.

  • Cite this

    Misailovic, S., Milicevic, A., Petrovic, N., Khurshid, S., & Marinov, D. (2007). Parallel test generation and execution with Korat. In 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2007 (pp. 135-144). (6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2007). https://doi.org/10.1145/1287624.1287645