Hammer is a nifty parser combinator library from the people behind Language-Theoretic Security [1].
Their goal is to promote the use of context-free formats and protocols, to avoid falling into the trap of trying to parse recursively-enumerable languages, a problem that reduces to the halting problem. The idea is that by sticking to context-free grammars, protocols will be easier to parse, and the bulk of memory corruption errors can eliminated.
Meredith Patterson and Sergey Bratus gave an excellent talk on the subject at 28c3 [2], and they've put together a video series on using Hammer to build a secure parser for JSON RPC [3].
Their 28c3 talk is truly exceptional, and it's nearly
enough to give one nightmares, or at the very least, it
will give you the kind of haunting enduring doubts that
most would rather not have. The part about HTML5+CSS3 being
unintentionally turning complete still bothers me.
As the name suggests you lose context, you can't "remember" anything you've seen in the token stream. So you can't really parse languages that use indentation. Although you can circumvent that by processing indentation in the lexer or inbetween lexer and parser.
Meh, you're probably going to want to limit your buffer size anyway in any highly concurrent system. Assuming you need to scan them anyway, delimited fields can also be faster to scan. If a field can't contain 0x00, and is 0x00 terminated (you can ensure this), then you don't need to do as many bounds-checks. If you know what you're doing, then Ragels 'noend' directive enables this, for instance.
Great work by the LANGSEC crowd. My recent interest in parsers was those verified for correctness or security. So, they have security and a certain amount of correctness. A great next step would be combining it with work on formal verification of parsers or generators (see below). On top of that, ensure the subset could generate SPARK and/or CompCert-compatible C code to automate much of the rest of the problem.
Smart move. It's a good default far as work vs results tradeoff. I'll try to keep your project in mind when I review my collection of verification papers in case I see any little-known, C verification methods that might help.
I've been using ragel for a few years, and really like it; but it does have the problem of not handling very well bit based structures (or, even, 8 bits based structures).
Also, the author closed the mailing list and packed up; presumably to work for a company who 'bought him out'. Closing the mailing list was a notch rude...
Hammer does look pretty nice, I'm definitely going to have a poke at it!
Before I moved down to MIT, I studied with Sergey, so the name is not at all coincidental. Nail tries a slightly different agenda. Instead of trying to make people design their formats in a reasonable way (which is excellent in the long term), Nail tries to allow people to get some (maybe most) of the benefits of parser generators, but for arbitrary formats.
I also made some different design decisions than Hammer, giving it a slightly different goal: code generation instead of runtime combinators, output generation, no semantic actions...
Would you consider using Nail to not just parse content-formats like JSON, but (dependent/semantic) type validation on the values of the data itself. Some of this involves business logic as well. For example, let's say I encode some data in JSON. Well I can parse JSON well, but then I need something inside that JSON to be an integer. Ok, that's fairly easy. But then I need that integer to be between 10 and 20. Ok, we have a filter now. But then, I need that integer to be less than or equal to a value defined elsewhere, but only if that value exists, because it's optional. And then, finally if a certain business condition is not met (by contacting the database), the entire input must be considered invalid and discarded. All of this is a form of data validation, but it increasingly involves more and more complexity.
I've been looking for a parser generator in C (currently using AttoParsec in Haskell, but looking to reduce dependencies), so I'll check out both Hammer & Nail - right now Hammer is downloading scons and gettext dependencies while Nail is downloading 80M worth of Boost libraries.
Grr, whatever happened to plain C with no dependencies?
Their goal is to promote the use of context-free formats and protocols, to avoid falling into the trap of trying to parse recursively-enumerable languages, a problem that reduces to the halting problem. The idea is that by sticking to context-free grammars, protocols will be easier to parse, and the bulk of memory corruption errors can eliminated.
Meredith Patterson and Sergey Bratus gave an excellent talk on the subject at 28c3 [2], and they've put together a video series on using Hammer to build a secure parser for JSON RPC [3].
[1] http://langsec.org/
[2] https://www.youtube.com/watch?v=3kEfedtQVOY
[3] https://github.com/sergeybratus/HammerPrimer