Today I Learned

Jun 24, 2019 | 1 minute read

Today I learned about Catastrophic Backtracking in Regular Expressions. This is a form of Regex that has O(2^N) CPU complexity, causing it to effectively never return when executed against even a reasonably short string. I won’t attempt to go into depth, the link above does a great job of that, but this affected our service by blocking the main thread and causing the service to become entirely unresponsive with a pegged CPU. We did not initially identify the problematic regex as it seem innocuous enough, so it took several days to diagnose the root cause. Identifying the root cause was exacerbated because the problematic regex was only executed in a small number of circumstances, so the service would be healthy until this reasonably rare case was encountered again in several hours or the next day.