<20> My Fixation

Vulnerability

It is true that my brain is just lazy and me not learning the rules of regex is such a learning issue and regex is totally fine.

I have some stuff that might show that is not the case (completely)

People don't care if it is applicable, people want to solve a real problem, well, are avoiding system outages good enough?

My search results showed regex.rip

as the first thing that was relevant to check for a ReDos attack.

<< In the paper

I was unaware of this attack and I need to read more about it but from the looks of a comprehensive literature review (till 2025)

tldr intuition - NFA is a program that takes a lot of time to evaluate an input.

And the time is not fixed but the worse can go upto 2^10 if there are 10 inputs and 2^10 equals 1024.

That is not all, imagine going from 10 inputs to 20 (2x) which leads to a jump of 2^10 (1024) to 2^20 (1024 x 1024 = 1048576) that jump is huge!

So huge that I wouldn't want to count further to demonstrate this jump

<< In the wikipedia

I will attach the wikipedia snip that highlights why I blabbed about NFA above

What we are trying to do is the first part, not exactly, but similar to converting an NFA to DFA.

Funny that NFA -> DFA conversion is one of the first thing I learnt in my Theory of Computation class and at that time I found it really boring because the teaching methods sucked

<< In my brain

Even the paper clearly states the same thing - backtracking takes exponential time which can be used for checking a really long string. This long string can make the regex parser/decoder/checker can cause the system to use all their CPU power to match this regex pattern.

And I think we can use some help from dead mathematicians to get through an engineering hiccup.

I will try to limit my jargon to programming symbols.