Sound regular expression semantics for dynamic symbolic execution of JavaScript. / Loring, Blake; Mitchell, Duncan; Kinder, Johannes.

PLDI'19: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2019. p. 425-438.

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

Published

Documents

Abstract

Support for regular expressions in symbolic execution-based tools for test generation and bug finding is insufficient. Common aspects of mainstream regular expression engines, such as backreferences or greedy matching, are ignored or imprecisely approximated, leading to poor test coverage or missed bugs. In this paper, we present a model for the complete regular expression language of ECMAScript 2015 (ES6), which is sound for dynamic symbolic execution of the test and exec functions. We model regular expression operations using string constraints and classical regular expressions and use a refinement scheme to address the problem of matching precedence and greediness. We implemented our model in ExpoSE, a dynamic symbolic execution engine for JavaScript, and evaluated it on over 1,000 Node.js packages containing regular expressions, demonstrating that the strategy is effective and can significantly increase the number of successful regular expression queries and therefore boost coverage.
Original languageEnglish
Title of host publicationPLDI'19
Subtitle of host publicationProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation
PublisherACM
Pages425-438
Number of pages14
ISBN (Electronic)978-1-4503-6712-7/19/06
DOIs
Publication statusPublished - 8 Jun 2019
Event40th ACM SIGPLAN Conference on Programming Language Design and Implementation - Phoenix Convention Center, Phoenix, United States
Duration: 24 Jun 2019 → …
https://pldi19.sigplan.org/home

Conference

Conference40th ACM SIGPLAN Conference on Programming Language Design and Implementation
Abbreviated titlePLDI'19
CountryUnited States
CityPhoenix
Period24/06/19 → …
Internet address
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 33909581