Regular Expressions:
Amazing and Dangerous

https://www.sw.it.aoyama.ac.jp/2021/pub/RubyKaigi/

Ruby Kaigi Takeout 2021, Online, September 9, 2021

Martin J. DÜRST (マーティンと呼んでください)

duerst@it.aoyama.ac.jp, Aoyama Gakuin University

© 2021 Martin J. Dürst, Aoyama Gakuin University

Topic

Regular Expressions can be Amazingly convenient but also extremely Dangerous

Motivation

Feature #17837: Add support for Regexp timeouts (by Sam Saffron)

How to detect/prevent dangerous regular expressions

Dangerous: Very slow (on some inputs)

Current ideas:

• Timeout (Regexp.timeout)
• Backtrack limit (Rexexp.backtrack_limit=, Regexp.last_backtrack_count)

Background

• Regular Expression Denial of Service
• Active research topic, in particular James Davis' PhD thesis (247 pages) [1]

[1] On the Impact and Defeat of Regular Expression Denial of Service, James C. Davis, PhD thesis, Virginia Politechnic, 2020.

Conventions Used

Code is mostly green, monospace
puts 'Hello Ruby!'

Variable parts are orange
puts "some string"

Results are indicated with "⇒"
1 + 1 ⇒ 2

Audience Self-Intro

• Who has used regular expressions?
• Who has had problems with using regular expressions?
• Who knows that regular expressions can be very slow?

Speaker Self-Intro

• From Switzerland, living and working in Japan
• Ruby Committer
• W3C Internationalization Interest Group Chair, IETF WG member,...
• Professor at Aoyama Gakuin University (青山学院大学)
• Teaching: Algorithms, Compilers, Math for CS students, Ruby on Rails, Functional Programming,..., in Japanese and English
• Research topics: Software Internationalization,
  World Wide Web Architecture, Programming Languagues (Ruby!)

Contributions to Ruby

Mainly in the following areas:

• Encoding conversion (String#encode, Ruby 1.9)
• Unicode normalization (String#unicode-normalize, Ruby 2.2)
• Non-ASCII case conversion (String#upcase,..., Ruby 2.4)
• Unicode version updates (Unicode 14.0.0 comming to Ruby soon)

Why Amazing

• Well suited Domain Specific Language (DSL) for string processing
  (Matz: "You can do that with a regular expression.")
• Compact, intuitive syntax (in simple cases!)
  Example: /Perl|Python|Pascal/
• Simple basic semantics (sequence, alternative, repetition)

Amazing Examples

• Usual: Simple string matching/extraction/replacement/splitting/...
• Real: Efficient Pure Ruby Unicode Normalization (NFC/NFD/NFKC/NFKD, eprun, String#unicode_normalize)
• Possible: Unicode Bidirectional Algorithm implementation (sorry, in Perl) [1]
• Surreal: Find smallest prime factor >1
  ("1"*63 =~ /^(11+?)\1*$/; puts $1.size ⇒ 7)

[1] Fun with Regular Expressions: An Implementation of the Unicode Bidi Algorithm, Martin J. Dürst, 26th Internationalization & Unicode Conference, San Jose, USA, Sept. 2004

Surreal: Smallest Prime Factor

/^(11+?)\1*$/

How does it work?

/^___$/: match from start to end, not just a part

1+: one or more 1s

11+: two or more 1s

11+?: two or more 1s, lazy (prefer as few as possible)

(___): remember what you matched (as \1 and $1)

\1*: what you remembered, 0 or more times

Surreal at Work

"1"*9 =~ /^(11+?)\1*$/: Smallest prime factor of 9

First try: (11) 11 11 11 1  ⇒ fail

Second try: (111) 111 111 ⇒ succeed, 3

Surreal gets Slow (Exhibit P)

"1"*63 =~ /^(11+?)\1*$/; puts $1.size ⇒ 7, 0.054s

"1"*11939 =~ /^(11+?)\1*$/; puts $1.size ⇒ 11939, 0.078s

"1"*99371 =~ /^(11+?)\1*$/; puts $1.size ⇒ 99371, 2.698s

"1"*193939 =~ /^(11+?)\1*$/; puts $1.size ⇒ 193939, 10.930s

⇒ Regular expressions are dangerous

(prime numbers from Wikipedia)

Dangerous Regular Expressions

"Some people, when confronted with a problem, think
'I know, I'll use regular expressions.'
Now they have two problems."

- Jamie Zawiski

background on this quote

[1] The 'mailto' URI Scheme, M. Dürst, L. Masinter, and J. Zawinski, RFC 6068, October 2010.

Why Dangerous

• Too well suited for string processing
• Compact syntax
• Extensions: Complex syntax
  (+: more than one; ?: zero or one; +?: more than one, lazy)
• Extensions: Complex semantics

  ⇒ medium writability, very low readability

• Many implementation variants
• Unpredictable time behavior

Unpredictable Time Behavior

• Simple regular exressions can be processed extremely efficiently
• Extended functionality requires more general algorithm
• Backtracking tries every possibility, in a well-defined order
• Optimizations are possible, but vary by implementation
• Regular expressions come in all kinds of shapes
• Optimizations work for some regular expressions, but not others

A Very Flat Regular Expression

irb> 'a'.unicode_normalize :nfc

irb> p UnicodeNormalize::REGEXP_C

/[̀́̓̈́ʹ;·क़-य़ড়ঢ়য়ਲ਼ਸ਼ਖ਼-ਜ਼ਫ਼ଡ଼ଢ଼གྷཌྷདྷབྷཛྷཀྵཱཱིུྲྀླཱྀྀྒྷྜྷྡྷྦྷྫྷྐྵάέήίόύώΆιΈΉΐΊΰΎ΅`ΌΏ´  ΩKÅ〈〉⫝̸豈-嗀塚晴凞-羽蘒諸逸都飯-舘並-龎יִײַשׁ-זּטּ-לּמּנּסּףּפּצּ-פֿ텞-텤톻-퇀-精][̀-͎͐-ͯ҃-֑҇-ׇֽֿׁׂׅׄؐ-ًؚ-ٰٟۖ-ۜ۟-۪ۤۧۨ-ܑۭܰ-݊߫-߽߳ࠖ-࠙ࠛ-ࠣࠥ-ࠧࠩ-࡙࠭-࡛࣓-ࣣ࣡-़्ࣿ॑-়॔া্ৗ਼઼଼੍્৾ା୍ୖୗா்ௗ಼్ౕౖೂ್ೕೖ഻഼ാ്ൗ්ාෟุ-ฺ่-๋ຸ-຺່-໋ཱིེུ༹༘༙༵༷-ཽྀྂ-྄࿆྆྇ီ့္်ႍ፝-᜔᜴្᤹ᢩ፟៝-᩠᤻ᨘᨗ᩵-᩿᩼᪰-᬴᪽ᬵ᭄᭫-᯦᰷᮪᮫᯲᯳᭳᳐-᳔᳒-᳢᳠-᳨᳭᳴᳸᳹᷀-᷹᷻-᷿⃐-⃥⃜⃡-⃰⳯-⵿⳱ⷠ-〪ⷿ-゙゚〯꙯ꙴ-꠆꣄꙽ꚞꚟ꛰꛱꣠-꤫꣱-꦳꥓꧀꤭ꪰꪲ-꫶꯭ﬞꪴꪷꪸꪾ꪿꫁︠-︯ǽˠͶ-ͺ਍ਏਸ-਺ਿ૥૦ത-ധཆ-ཐ၆ၿႹႺᄀ-ᄂᄧᄳᄴᅳᇀᇊስሶዩዪጻጼጾፍፗ፦-፬፰-፴ᑂᑆᑞᒰᒺᒽᓂᓃᖯᖿᗀᘿᚶᚷᜫᠹᠺ᧠ᨴᩇ᪙᰿ᵂᵄᵅᶗ櫰-櫴欰-欶벞텥-텩텭-텲텻-톂톅-톋톪-톭퉂-퉄--------]*|[<->A-PR-Za-pr-z¨À-ÏÑ-ÖØ-Ýà-ïñ-öø-ýÿ-ďĒ-ĥĨ-İĴ-ķĹ-ľŃ-ňŌ-őŔ-ťŨ-ſƠơƯưƷǍ-ǜǞ-ǣǦ-ǰǴǵǸ-țȞȟȦ-ȳʒ΅ΆΈ-ΊΌΎ-ΑΕΗῚ?ΡΥΩ-αεηιορυω-ώϒ-ϔЀЁЃІЇЌ-ЎАГЕ-КОУЧЫЭаге-коучыэѐёѓіїќ-ўѴ-ѷӁӂӐ-ӓӖ-ӟӢ-ӵӸӹآ-اويۀ-ۂےۓەनऩरऱळऴেোৌେୈୋୌஒஔெேொ-ௌెైಿೀೆ-ೈೊೋെേൊ-ൌෙේො-ෞဥဦᬅ-ᬎᬑᬒᬺ-ᭃḀ-ẙẛẠ-ỹἀ-ἕἘ-Ἕἠ-ὅὈ-Ὅὐ-ὗὙὛὝὟ-ὰὲὴὶὸὺὼᾀ-ᾴᾶ-Ὰᾼ᾿῁-ῄῆ-ῈῊῌ-ῒῖ-Ὶ῝-ῢῤ-ῪῬ῭ῲ-ῴῶ-ῸῺῼ῾←→↔↚↛↮⇍-⇐⇒⇔∃∄∈∉∋∌∣-∦∼≁≃-≅≇-≉≍≠-≢≤≥≭-≽⊀-⊉⊑⊒⊢⊨⊩⊫-⊯⊲-⊵⋠-⋣⋪-⋭うか-ぢつ-どは-ぽゔゝゞウカ-ヂツ-ドハ-ポワ-ヲヴヷ-ヺヽヾ႙-ႜႥႫᄮᄯᄱᄲፇፋፌᒹᒻᒼᒾᖸ-ᖻ]?[̀-͎͐-ͯ҃-֑҇-ׇֽֿׁׂׅׄؐ-ًؚ-ٰٟۖ-ۜ۟-۪ۤۧۨ-ܑۭܰ-݊߫-߽߳ࠖ-࠙ࠛ-ࠣࠥ-ࠧࠩ-࡙࠭-࡛࣓-ࣣ࣡-़्ࣿ॑-়॔া্ৗ਼઼଼੍્৾ା୍ୖୗா்ௗ಼్ౕౖೂ್ೕೖ഻഼ാ്ൗ්ාෟุ-ฺ่-๋ຸ-຺່-໋ཱིེུ༹༘༙༵༷-ཽྀྂ-྄࿆྆྇ီ့္်ႍ፝-᜔᜴្᤹ᢩ፟៝-᩠᤻ᨘᨗ᩵-᩿᩼᪰-᬴᪽ᬵ᭄᭫-᯦᰷᮪᮫᯲᯳᭳᳐-᳔᳒-᳢᳠-᳨᳭᳴᳸᳹᷀-᷹᷻-᷿⃐-⃥⃜⃡-⃰⳯-⵿⳱ⷠ-〪ⷿ-゙゚〯꙯ꙴ-꠆꣄꙽ꚞꚟ꛰꛱꣠-꤫꣱-꦳꥓꧀꤭ꪰꪲ-꫶꯭ﬞꪴꪷꪸꪾ꪿꫁︠-︯ǽˠͶ-ͺ਍ਏਸ-਺ਿ૥૦ത-ധཆ-ເ?၆ၿႹႺᄀ-ᄂᄧᄳᄴᅳᇀᇊስሶዩዪጻጼጾፍፗ፦-፬፰-፴ᑂᑆᑞᒰᒺᒽᓂᓃᖯᖿᗀᘿᚶᚷᜫᠹᠺ᧠ᨴᩇ᪙᰿ᵂᵄᵅᶗ櫰-櫴欰-欶벞텥-텩텭-텲텻-톂톅-톋톪-톭퉂-퉄--------]+|[가개갸걔거게겨계고과괘괴교구궈궤귀규그긔기까깨꺄꺠꺼께껴꼐꼬꽈꽤꾀꾜꾸꿔꿰뀌뀨끄끠끼나내냐냬너네녀녜노놔놰뇌뇨누눠눼뉘뉴느늬니다대댜댸더데뎌뎨도돠돼되됴두둬뒈뒤듀드듸디따때땨떄떠떼뗘뗴또똬뙈뙤뚀뚜뚸뛔뛰뜌뜨띄띠라래랴럐러레려례로롸뢔뢰료루뤄뤠뤼류르릐리마매먀먜머메며몌모뫄뫠뫼묘무뭐뭬뮈뮤므믜미바배뱌뱨버베벼볘보봐봬뵈뵤부붜붸뷔뷰브븨비빠빼뺘뺴뻐뻬뼈뼤뽀뽜뽸뾔뾰뿌뿨쀄쀠쀼쁘쁴삐사새샤섀서세셔셰소솨쇄쇠쇼수숴쉐쉬슈스싀시싸쌔쌰썌써쎄쎠쎼쏘쏴쐐쐬쑈쑤쒀쒜쒸쓔쓰씌씨아애야얘어에여예오와왜외요우워웨위유으의이자재쟈쟤저제져졔조좌좨죄죠주줘줴쥐쥬즈즤지짜째쨔쨰쩌쩨쪄쪠쪼쫘쫴쬐쬬쭈쭤쮀쮜쮸쯔쯰찌차채챠챼처체쳐쳬초촤쵀최쵸추춰췌취츄츠츼치카캐캬컈커케켜켸코콰쾌쾨쿄쿠쿼퀘퀴큐크킈키타태탸턔터테텨톄토톼퇘퇴툐투퉈퉤튀튜트틔티파패퍄퍠퍼페펴폐포퐈퐤푀표푸풔풰퓌퓨프픠피하해햐햬허헤혀혜호화홰회효후훠훼휘휴흐희히][ᆨ-ᇂ]|[ᄀ-ᄒ][ᅡ-ᅵ][ᆨ-ᇂ]?/x

ReDoS

• Regular Expression Denial of Service
• Famous incidents, e.g. Stack Overflow, Cloudflare, Atom
• How can we avoid it
  
  • When using Ruby
  • In Ruby itself

We Need Real Data

• Take large collection of regular expressions
• Extract regular expressions relevant to Ruby
• Find slow regular expressions and input where they are slow
  
• Examine exact behavior with Ruby
• Examine how to best stop slow regular expressions

Regular Expression Data Origin

• Study of regular expressions across programming languages ([1])
  
• Artifact with actual data available from Zenodo
• Data from data/production-regexes/uniq-regexes-8.json used,
  limited to regular expressions marked with rubygems

[1] Why Aren’t Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions,
J.C. Davis, L.G. Michael IV, C.A Coghlan, F. Servant, and D. Lee,
ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, August 2019, pp. 443–454

Regular Expression Evaluation

• Vulnerable Regex Detector by J.C. Davis (github)
• Uses 4 different vulnerability detectors (RXXR2, REXPLOITER, RegexStaticAnalysis, ReScue)
• Each vulnerability detector uses different strategy (rewriting, guided fuzzing,...)
  (slow regular expressions can be fast on almost all input)
• Software Evaluation with docker, uses ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]

Hardware Used

• Main jobs: Two servers, sometimes running jobs overnight
  (Dell PowerEdge R740xd, 2 Intel Xeon Gold 5220 2.2GHz, 18C/36T, Ubuntu)
• Additional work: One notebook computer
  (Panasonic Let's Note QV, Intel Core i7-8665U 1.9GHz, 4C/8T, WSL2/Ubuntu)

Exhibit E

• Regular expression: /"([^"]*(&[ ]*[\n\r]+)?)*"/

Exhibit E, Structure

• Regular expression: /"([^"]*(&[ ]*[\n\r]+)?)*"/
• Structured display:
  

  /"(
      [^"]*
      (
        &
        [ ]*
        [\n\r]+
      )?
    )*
  /x

Exhibit E, Attack

• Regular expression: /"([^"]*(&[ ]*[\n\r]+)?)*"/
  
• Attack vector:
  prefix: 【"】, pump: 【&\n】, suffix: 【】
• Attack strings:
  prefix + pump*n_pumps + suffix

Exhibit E, Timing

• Regular expression: /"([^"]*(&[ ]*[\n\r]+)?)*"/
  
• Attack vector:
  prefix: 【"】, pump: 【&\n】, suffix: 【】
• Time behavior: exponential explosion

  pumps	attack vector	time [s]
  1	"&\n	0.00096
  2	"&\n&\n	0.00617
  3	"&\n&\n&\n	1.21982
  4	"&\n&\n&\n&\n	timeout (>10)

• Why exponential: Nested quantifier ((()*)*)
  Other nested quantifiers are possible, too (*+, ++, +*,...)

Evaluation Result

• Start with 537'806 unique regular expressions extracted from repositories for 8 languages (e.g. rubygems)
• Reduce to 153'334, all labeled rubygems
• Identify 234 regular expressions that are dangerous/vulnerable
  • Attacks match: 13 expressions
  • Attacks do not match: 221 expressions
  • Typical distribution, failure often takes longer
• Timeout distribution:
  • 16 pumps or less: 91 expressions (exponential?)
  • 16 < ≦32 pumps: 111 expressions (exponential?)
  • 640 < ≦3584 pumps: 4 expressions (cubic?)
  • 8192 < pumps: 28 expressions (quadratic?)

How to Improve Ruby

• Introduce Regexp.timeout?
  • Advantage: Time in seconds
  • Problem: Ruby-level timeouts don't always work
  • Dealt with by using external processes
  • Problem: Implementation may be tricky or slow things down
• Introduce Regexp.backtrack_limit?
  • Initial implementation by Nobu Nakada
  • No information on backtracks used by failing matches
  • Tried to implement, but not complete
  • Dealt with by using binary search
  • Problem: Some slow matches don't count backtracks

My opinion:
Fixing ReDoS problem would make Ruby a "better citizen"
Basics available for evaluation of solutions, but more work needed

Exhibit Q

• Regular expression: /["']([^"']+)["'].*already exists/
  simplified: /"[^"]+".*end/ or /a[^a]+a.*e/
• Attack vector:
  prefix:【"b】pump: 【"b】suffix: 【】

  "bb"b"b"b"b"b"b"b"b"b"b"b"b"b"b"b"b"b"b...

• Time behavior: quadratic (10 times longer → 100 times slower)

  pumps	time [s]
  4096	0.054
  40960	5.204

• Why quadratic:
  
  • Start at every "b" combination
  • Check all the rest whether it ends with already exists
• .* creates dangerous overlaps

Recommendations (Summary)

• Use regular expressions only where they are really suited
• Use //x to make regular expression structure visible
• Write tests for your regular expressions
  (test coverage tools don't look inside regular expressions)
• Check for potentially slow regular expressions
• Use various online tools
• Restrict length of input strings
• Avoid regular expressions from user input

Acknowledgments

• Sam Saffron for starting
• Nobu Nakada (中田 伸悦) for the backtrack_limit implementation
• James C. Davis for all his research
• Matz (まつもと ゆきひろ) for Ruby, a programmer's best friend
• Amaya, Opera 12.17, and coderay for slide production and display

Q & A

Send questions and comments to Martin Dürst
(mailto:duerst@it.aoyama.ac.jp)
or open/contribute to a bug report or feature request

The latest version of this presentation is available at:

https://www.sw.it.aoyama.ac.jp/2021/pub/RubyKaigi/