davisjam314

4 ms·

1.
by davisjam314 6y ago
Thanks, folks!
2.
by davisjam314 6y ago
Interestingly, the backtracking engines can also be viewed as using automata. The trouble is actually in how they simulate the automaton. They use backtracking -- like a depth-first search. Since they don't remember where they'v
3.
by davisjam314 6y ago
(This is a repetition of my replies to your thread on Twitter). My goal was not to prove that super-linear behavior is possible, but rather to understand questions like: 1. How common are such regexes in practice? (~10%) 2. Do developers kn
4.
by davisjam314 6y ago
Thank you for the suggestion. I added notes about typical sizes depending on the complexity of the regex. TLDR: ~30 chars is too long for exponential regexes. 1K-5K chars are too long for quadratic regexes. Higher polynomials blow up somewh
5.
by davisjam314 6y ago
> This seems like a quibble, but putting the emphasis on "using an appropriate engine" in parentheses at the end is burying the lede. Sticking to regular languages will not, in itself, help. Yes. I attempted to make this point
6.
by davisjam314 6y ago
The name for this in the security literature is "algorithmic complexity attacks". They were first proposed by Crosby & Wallach in 2003, with a running example of degraded hash tables.
7.
by davisjam314 6y ago
---- Tangent: I am the author of the Lingua Franca paper. I hope you enjoyed it!
8.
by davisjam314 6y ago
Yes, those terms are definitely imprecise. My target audience for that blog post was "anyone vaguely technical, from programmers to managers". I therefore attempted to minimize the amount of technical detail and to focus on the co
9.
ReDoS: Regular Expression Denial of Service(levelup.gitconnected.com)
83 points by davisjam314 6y ago|37 comments
10.
by davisjam314 6y ago
This is a "technical two-pager" of my doctoral research about regex denial of service.
11.
A principled approach to GraphQL query cost analysis(medium.com)
46 points by davisjam314 6y ago|11 comments
12.
by davisjam314 6y ago
Why you should measure the cost of your GraphQL queries, and how you should do it. This is a summary of a research paper.
13.
by davisjam314 6y ago
This post is intended as a “technical two-pager” to summarize a security vulnerability called Regex-based Denial of Service (AKA Regex DoS, ReDoS). There are a variety of write-ups about ReDoS, but I’m not aware of a good one-stop-shop with