Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Static analysis of regular expressions
Thesis (MSc)--Stellenbosch University, 2017
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2017
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613966765654016 |
|---|---|
| access_status_str | Open Access |
| author | Weideman, Nicolaas Hendrik |
| author2 | Van der Merwe, Andries Brink |
| author_browse | Van der Merwe, Andries Brink Weideman, Nicolaas Hendrik |
| author_facet | Van der Merwe, Andries Brink Weideman, Nicolaas Hendrik |
| author_sort | Weideman, Nicolaas Hendrik |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2017 |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/102879 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:44:33.029Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2017 |
| publishDateRange | 2017 |
| publishDateSort | 2017 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/102879 Static analysis of regular expressions Weideman, Nicolaas Hendrik Van der Merwe, Andries Brink Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Computer Science. Computer programming language -- Regular expressions UCTD Automata theory Computer programming language -- Denial-of-service attack (DoS attack) Computer programming language -- Backtracking matchers Computer software -- Static analysis techniques Thesis (MSc)--Stellenbosch University, 2017 ENGLISH ABSTRACT : Regular expressions are widely used throughout the programming community. In most cases, regular expressions allow for pattern matching tasks to be performed efficiently, but in some instances regular expression matching can be extremely slow. The exploit of the potential slowness of regular expression matching, is known as a regular expression denial of service attack. We investigate regular expression denial of service attacks, by approaching it from a computational complexity and automata theoretic point of view. A method for accurately modeling the matching time behaviour of a backtracking regular expression matcher, by using automata theoretic methods, is presented. We analyze our models by using the concept of ambiguity in nondeterministic finite-state automata. Our approach is evaluated on repositories of regular expressions often used in practice. Techniques for mitigating the vulnerability of backtracking regular expression matchers are investigated as a means to thwart regular expression denial of service attacks. AFRIKAANSE OPSOMMING : Reguliere uitdrukkings word gereeld gebruik in die skryf van sagteware. In die meeste gevalle stel sulke uitdrukkings mens in staat om patroonherkenningsprobleme op ’n doeltreffende manier op te los. Daar is egter sommige situasies waar hierdie proses uiters tydrowend kan wees. Die uitbuiting van sulke kwesbaarhede staan as ’n diensontseggingaanval bekend. Ons ondersoek hierdie aanvalle vanuit die oogpunt van berekeningskompleksiteit en outomateteorie. ’n Metode word gegee om die herkenningstyd van ’n terugspoor herkenner van reguliere uitdrukkings akkuraat te modelleer. Ons analiseer die modelle deur gebruik te maak van die konsep van dubbelsinnigheid in nie-deterministiese eindigetoestand-outomate. Die metodes word getoets deur dit toe te pas op magasyne van reguliere uitdrukkings wat in die praktyk gebruik word. Tegnieke om die kwesbaarheid van terugspoor herkenners van reguliere uitdrukkings te verbeter word ondersoek, met die doelwit om diensontseggingaanvalle te voorkom. 2017-11-19T13:28:16Z 2017-12-11T11:07:11Z 2017-11-19T13:28:16Z 2017-12-11T11:07:11Z 2017-11-19 Thesis http://hdl.handle.net/10019.1/102879 en_ZA Stellenbosch University xiii, 100 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Computer programming language -- Regular expressions UCTD Automata theory Computer programming language -- Denial-of-service attack (DoS attack) Computer programming language -- Backtracking matchers Computer software -- Static analysis techniques Weideman, Nicolaas Hendrik Static analysis of regular expressions |
| title | Static analysis of regular expressions |
| title_full | Static analysis of regular expressions |
| title_fullStr | Static analysis of regular expressions |
| title_full_unstemmed | Static analysis of regular expressions |
| title_short | Static analysis of regular expressions |
| title_sort | static analysis of regular expressions |
| topic | Computer programming language -- Regular expressions UCTD Automata theory Computer programming language -- Denial-of-service attack (DoS attack) Computer programming language -- Backtracking matchers Computer software -- Static analysis techniques |
| url | http://hdl.handle.net/10019.1/102879 |
| work_keys_str_mv | AT weidemannicolaashendrik staticanalysisofregularexpressions |