Fault-based test generation for regular expressions by mutation

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10370000" target="_blank" >RIV/00216208:11320/19:10370000 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Q0t25ijHFl" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Q0t25ijHFl</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/stvr.1664" target="_blank" >10.1002/stvr.1664</a>

Result language

angličtina

Original language name

Fault-based test generation for regular expressions by mutation

Original language description

Regular expressions are used to characterize sets of strings (i.e., languages) using a pattern-based syntax. They are applied in different contexts as, for example, data validation in web forms. However, writing a regular expression that exactly captures the desired set of strings could be particularly difficult, and techniques are sought to validate regular expressions or test their use in applications. A common means to regular expression validation and testing is the generation of a set of labeled strings (i.e., strings together with their evaluation). We here propose a fault-based approach for generating strings usable as tests for regular expressions. We define some fault classes representing mistakes that could be made when writing a regular expression, and we introduce the notion of distinguishing string, i.e., a string that is able to expose a fault. Given a regular expression, our approach generates a test suite composed of distinguishing strings that are able to detect possible faults in the regular expression. We present different versions of the approach, which provide different results in terms of test suite size and generation time. Experiments show that the proposed approach can generate compact test suites and that, using suitable optimizations, the generation time is reasonable. Exploiting the proposed fault classes, we use the notion of mutation score to assess the ability of a generic set of strings in exposing possible faults contained in the regular expression under test. A comparison with other test generation tools in terms of mutation score, size, and generation time shows the advantages and limits of our approach.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA17-12465S" target="_blank" >GA17-12465S: Verification and Bug Hunting for Advanced Software</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Software Testing Verification and Reliability

ISSN

0960-0833

e-ISSN

—

Volume of the periodical

29

Issue of the periodical within the volume

1-2

Country of publishing house

GB - UNITED KINGDOM

Number of pages

22

Pages from-to

1-22

UT code for WoS article

000458911000001

EID of the result in the Scopus database

2-s2.0-85043345890