Regular expressions are widely used to describe and document regular languages, and to identify a set of (valid) strings. Often they are not available or known, and they must be learned or inferred. Classical approaches like L* make strong assumptions that normally do not hold. More feasible are testing approaches in which it is possible only to generate strings and check them with the underlying system acting as oracle. In this paper, we devise a method that starting from an initial guess of the regular expression, it repeatedly generates and feeds strings to the system to check whether they are accepted or not, and it tries to repair consistently the alleged solution. Our approach is based on an evolutionary algorithm in which both the population of possible solutions and the set of strings co-evolve. Mutation is used for the population evolution in order to produce the offspring. We run a set of experiments showing that the string generation policy is effective and that the evolutionary approach outperforms existing techniques for regular expression repair.
Regular Expression Learning with Evolutionary Testing and Repair / P. Arcaini, A. Gargantini, E. Riccobene (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: Testing Software and Systems / [a cura di] C. Gaston, N. Kosmatov, P. Le Gall. - [s.l] : Springer, 2019. - ISBN 9783030312794. - pp. 22-40 (( Intervento presentato al 31. convegno IFIP International Conference on Testing Software and Systems tenutosi a Paris nel 2019 [10.1007/978-3-030-31280-0_2].
Regular Expression Learning with Evolutionary Testing and Repair
E. Riccobene
2019
Abstract
Regular expressions are widely used to describe and document regular languages, and to identify a set of (valid) strings. Often they are not available or known, and they must be learned or inferred. Classical approaches like L* make strong assumptions that normally do not hold. More feasible are testing approaches in which it is possible only to generate strings and check them with the underlying system acting as oracle. In this paper, we devise a method that starting from an initial guess of the regular expression, it repeatedly generates and feeds strings to the system to check whether they are accepted or not, and it tries to repair consistently the alleged solution. Our approach is based on an evolutionary algorithm in which both the population of possible solutions and the set of strings co-evolve. Mutation is used for the population evolution in order to produce the offspring. We run a set of experiments showing that the string generation policy is effective and that the evolutionary approach outperforms existing techniques for regular expression repair.File | Dimensione | Formato | |
---|---|---|---|
ea_regexrep_ICTSS2019.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
515.77 kB
Formato
Adobe PDF
|
515.77 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Arcaini2019_Chapter_RegularExpressionLearningWithE.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
532.4 kB
Formato
Adobe PDF
|
532.4 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.