Rathnayake , Asiri (2015). Semantics, analysis and security of backtracking regular expression matchers. University of Birmingham. Ph.D.
|
RathnayakeMudiyanselage15PhD.pdf
PDF - Accepted Version Download (713kB) |
Abstract
Regular expressions are ubiquitous in computer science. Originally defined by Kleene in 1956, they have become a staple of the computer science undergraduate curriculum. Practical applications of regular expressions are numerous, ranging from compiler construction through smart text editors to network intrusion detection systems. Despite having been vigorously studied and formalized in many ways, recent practical implementations of regular expressions have drawn criticism for their use of a non-standard backtracking algorithm. In this research, we investigate the reasons for this deviation and develop a semantics view of regular expressions that formalizes the backtracking paradigm. In the process we discover a novel static analysis capable of detecting exponential runtime vulnerabilities; an extremely undesired reality of backtracking regular expression matchers.
| Type of Work: | Thesis (Doctorates > Ph.D.) | ||||||
|---|---|---|---|---|---|---|---|
| Award Type: | Doctorates > Ph.D. | ||||||
| Supervisor(s): |
|
||||||
| Licence: | |||||||
| College/Faculty: | Colleges (2008 onwards) > College of Engineering & Physical Sciences | ||||||
| School or Department: | School of Computer Science | ||||||
| Funders: | Other | ||||||
| Other Funders: | The University of Birmingham | ||||||
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science | ||||||
| URI: | http://etheses.bham.ac.uk/id/eprint/6011 |
Actions
 |
Request a Correction |
 |
View Item |
Downloads
Downloads per month over past year