Reggae: Automated test generation for programs using complex regular expressions

Nuo Li, Tao Xie, Nikolai Tillmann, Jonathan De Halleux, Wolfram Schulte

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

Abstract

Test coverage such as branch coverage is commonly measured to assess the sufficiency of test inputs. To reduce tedious manual efforts in generating high-covering test inputs, various automated techniques have been proposed. Some recent effective techniques include Dynamic Symbolic Execution (DSE) based on path exploration. However, these existing DSE techniques cannot generate high-covering test inputs for programs using complex regular expressions due to large exploration space; these complex regular expressions are commonly used for input validation and information extraction. To address this issue, we propose an approach, named Reggae, to reduce the exploration space of DSE in test generation. In our evaluation, we apply Reggae on various input-validation programs that use complex regular expressions. Empirical results show that Reggae helps a test-generation tool generate test inputs to achieve 79% branch coverage of validators, improved from 29% achieved without the help of Reggae.

Original languageEnglish (US)
Title of host publicationASE2009 - 24th IEEE/ACM International Conference on Automated Software Engineering
Pages515-519
Number of pages5
DOIs
StatePublished - 2009
Externally publishedYes
Event24th IEEE/ACM International Conference on Automated Software Engineering, ASE2009 - Auckland, New Zealand
Duration: Nov 16 2009Nov 20 2009

Publication series

NameASE2009 - 24th IEEE/ACM International Conference on Automated Software Engineering

Other

Other24th IEEE/ACM International Conference on Automated Software Engineering, ASE2009
Country/TerritoryNew Zealand
CityAuckland
Period11/16/0911/20/09

Keywords

  • Dynamic symbolic execution
  • String generation
  • Test generation

ASJC Scopus subject areas

  • Computer Science Applications
  • Software

Cite this