{"id":31785,"date":"2021-03-04T20:40:59","date_gmt":"2021-03-05T01:40:59","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=31785"},"modified":"2021-03-04T20:40:59","modified_gmt":"2021-03-05T01:40:59","slug":"accidentally-quadratic-parsing-with-sscanf","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2021\/03\/04\/accidentally-quadratic-parsing-with-sscanf\/","title":{"rendered":"Accidentally Quadratic Parsing With sscanf"},"content":{"rendered":"

T0ST<\/a> (via Hacker News<\/a>):<\/p>\n

GTA Online. Infamous<\/a> for its slow loading times. Having picked up the game again to finish some of the newer heists I was shocked<\/em> (\/s) to discover that it still loads just as slow as the day it was released 7 years ago.<\/p>

[…]<\/p>

Enter stack sampling: for closed source applications there’s only one option. Dump the running process’ stack and current instruction pointer’s location to build a calling tree in set intervals. Then add them up to get statistics on what’s going on.<\/p>

[…]<\/p>

Disassembling the now-less-obfuscated dump reveals that one of the addresses has a label pulled out of somewhere! It’s strlen<\/code>? Going down the call stack the next one is labeled vscan_fn<\/code> and after that the labels end, tho I’m fairly confident it’s sscanf<\/code><\/a>.<\/p>

It’s parsing something. Parsing what? Untangling the disassembly would take forever so I decided to dump some samples from the running process using x64dbg<\/a>. Some debug-stepping later it turns out it’s… JSON!<\/p>\n

[…]<\/p>\n

To be fair I had no idea most sscanf<\/code> implementations called strlen<\/code> so I can’t blame the developer who wrote this. I would assume it just scanned byte by byte and could stop on a NULL<\/code>.<\/p><\/blockquote>\n\n

And then there’s another quadratic array membership test.<\/p>\n\n

Michael Brown<\/a>:<\/p>\n

The performance problem with sscanf<\/code> O(N2<\/sup>) in glibc has been known since at least 2014 (see bug 17577<\/a>). Ironically, if they’d used fscanf<\/code> (reading from a file instead of loading it into memory first) the problem wouldn’t exist.<\/p><\/blockquote>\n\n

Matt Keeter<\/a>:<\/p>\n

This sparked a great deal<\/a> of discussion:\nWas this C’s fault?\nPerhaps “web shit”<\/a>?\nCapitalism and incentives<\/a>?<\/p>

Still, folks in the comments section generally agreed:\nthey<\/em> wouldn’t write anything that silly.<\/p>

[…]<\/p>

Yes, I had made the exact same mistake as the programmers working on GTA Online: I had an accidentally quadratic parser!<\/p>\n

[…]<\/p>\n

As someone that has been programming for many years,\nthis was a perfectly-timed reminder that there are always<\/em> pitfalls out there.\nThe documentation for sscanf<\/code><\/a>\ndoes not include a time complexity,\nso this is particularly tricky footgun<\/a>,\nand I’m sure it’s not the only one lurking in the darkness.<\/p><\/blockquote>\n\n

Git<\/a> (via Hacker News<\/a>):<\/p>\n

This header lists functions that have been banned from our code base, because they’re too easy to misuse (and even if used correctly, complicate audits).<\/p><\/blockquote>\n\n

Previously:<\/p>\n