3 ms·

A huge reason anything accepting network (or other potentially hostile input) should use parser generators and validate the entire input before using any of it

by pdkl95 11y ago

A huge reason anything accepting network (or other potentially hostile input) should use parser generators and validate the entire input before using any of it is security. Additionally, all of those grammars should, whenever possible, be no more complex than deterministic context-free. As Meredith and Sergey explain in their talk[1] at 28c3, Turing complete input and parsers that don't validate the input are creating a "weird machine" just waiting to be programmed in malicious and unexpected ways. [1] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...

jstimpfle 11y ago
Couple questions coming--sharing some experience and hoping to learn something. Do you think the use of parser generators is practical also for performance-critical binary data? For example video streams? (I've never parsed one but I imagine they could be so optimized that it could be impractical to do it with a generic parser generator). What formats are examples of complex structure where parser generators are practical? For my personal needs, I've been getting along very well with plain text relational data. Like numPersons 2 numAncestors 1 person john "John Doe" person jane "Jane Dane" ancestor john jane That's so trivial that I would never want to depend on a parser generator. Instead I handroll a parser for this format in 10 minutes and 20 lines of C if I don't mind bad error messages. And what parser generator would make it easy to check (relational) integrity of above data in a secure way? If I leave away the num* fields above, the parser would need one token of lookahead. What type of grammars are these two versions?
- deleted 11y ago
  [deleted]
- pdkl95 11y ago
  > Do you think the use of parser generators is practical also for performance-critical binary data? That's not a question I consider very important, because prioritizing performance over correctness (safety) is irresponsible. That said, using a parser generator shouldn't have a significant impact on performance. When a network is involved, the parser isn't going to be the bottleneck anyway. > video I am not very familiar with the details of video formats, but I would suggest trying the parser combinator library Meredith mentions in the talk in my previous [1], known as "hammer"[2]. It's very easy to use, and it has specific support for bit-level parsing of binary formats. > numPersons 2 I highly recommend not using formats like this, because it's more complex than deterministic context-free. Using a length field requires that the parser remember state. It's also redundant information, creating the possibility of a miss-match between the number specified in "numPersons" and the actual number of rows. A format that uses s-expressions would be safer and more easier to implement: (ancestry (ancestor (person john "John Doe") (person jane "Jane Doe") ) ) The closing tag of the s-expression provides a similar benefit as the num* fields by simply marking the end of a complete record/field. > That's so trivial that I would never want to depend on a parser generator Is it really "trivial"? Or is your parse that you write in 10 minutes accepting ambiguous or invalid data? Is it actually checking for all of the error conditions? For most real-world grammars, it's unlikely you will catch all of the subtle ambiguities, interactions, and edge cases. The benefit of using a parser generator is that those entire classes of bugs are impossible. > check (relational) integrity In the trivial example you gave, you shouldn't have a grammar that requires checking relational integrity. In a more complex grammar, such checks would be the job of whatever is walking the AST that the parser returns. Parsers interpret syntax, not semantics. > If I leave away the num* fields above, the parser would need one token of lookahead. You need at least one token of lookahead anyway. Including the num* fields means the parser needs to remember and manage state. [2] https://github.com/UpstandingHackers/hammer https://github.com/UpstandingHackers/hammer
  - jstimpfle 11y ago
    >> numPersons 2 > I highly recommend not using formats like this, because it's more complex than deterministic context-free. Barely. It avoids the complexity of look-ahead and reallocating growing buffers. > A format that uses s-expressions would be safer and more easier to implement: Trees are unsuitable for almost anything computationally, at least as authoritative representation. Prefer flat. (Widget hierarchies are one of a few counterexamples where the tradeoffs are different). This s-expression you gave is much more complex to parse. Granted, you get parsing as a tree for free. But then you have to go inside the tree and see what's there. That there are two persons per ancestor, etc. Navigating trees is hard. > Is it really "trivial"? Is it actually checking for all of the error conditions? Yes. Yes. Of course. It's the most boring code in the world. Parse numbers, allocate arrays correspondingly, parse each following table in a loop corresponding to the numbers parsed. You can do it all using scanf. Bail out as soon as a bad line comes in. 20 lines. > The benefit of using a parser generator is that those entire classes of bugs are impossible. Yeah. Well, they are not impossible. They are only possible in the parser generator. And interfacing a parser generator is itself not necessarily trivial. Plus, dependencies are a maintenance burden. The other approach is to make the design so simple (like the relational example) to make them (the classes) nonexistent. > You need at least one token of lookahead anyway. Not in the example I gave. > Including the num* fields means the parser needs to remember and manage state. I would hardly call that state. It's an immutable number, initialized in sequential code without real data dependencies (the data dependencies are resolved in the format -- you can not go wrong parsing it).
- vinceguidry 11y ago
  Data, if you have to format it in text, is best done using a regular grammar, which you can read with regular expressions into objects. You would then do the validations on the objects rather than on the string-formatted data.
  - jstimpfle 11y ago
    Good point. But, are there practical tools for this? I still have to decide how I store the data in memory. For example, struct Model { int numPersons; int numAncestors; struct Person *person; struct Ancestor *ancestor; }; Or SOA instead of AOS? struct Model { int numPersons; int numAncestors; struct string *personname; struct string *persondesc; struct string *ancestorancestor; struct string *ancestordescendant; }; etc. Do you know tools which are in practice a better choice than the super boring ad-hoc code I described? Unless I'd have to define many of these types of formats the cost of going meta is just too high.
    - vinceguidry 11y ago
      I use Ruby, so I can't help you re: tooling. But if you are parsing a regular grammar with regular expressions, how much tooling do you need? The regexp does all the work. All you have to do is ensure that your data format is sane, that your delimiters can never appear in the data. With stuff like your problem, I can never be sure the data is clean, so I always default to a format like CSV or JSON and use standard library tools. I would shudder to have to work with that kind of data in C / C++ for the very reason you're asking these questions in this thread. It's low-level code for a high-level task. You're bound to fuck it up eventually and not foresee an edge case. But it would depend on what you want to do with the data. If you're walking trees, then you're going to want to store them in memory as trees. Whichever memory structure would be the most efficient in the algorithm you've got planned. Personally, since it's relational, I wouldn't bother with file storage at all and just dump it into a relational database, even if it's just SQLite. That would give you the most flexibility.
      - 11y ago

by pdkl95 11y ago

jstimpfle 11y ago

Couple questions coming--sharing some experience and hoping to learn something. Do you think the use of parser generators is practical also for performance-critical binary data? For example video streams? (I've never parsed one but I imagine they could be so optimized that it could be impractical to do it with a generic parser generator). What formats are examples of complex structure where parser generators are practical? For my personal needs, I've been getting along very well with plain text relational data. Like numPersons 2 numAncestors 1 person john "John Doe" person jane "Jane Dane" ancestor john jane That's so trivial that I would never want to depend on a parser generator. Instead I handroll a parser for this format in 10 minutes and 20 lines of C if I don't mind bad error messages. And what parser generator would make it easy to check (relational) integrity of above data in a secure way? If I leave away the num* fields above, the parser would need one token of lookahead. What type of grammars are these two versions?

deleted 11y ago
[deleted]
pdkl95 11y ago
> Do you think the use of parser generators is practical also for performance-critical binary data? That's not a question I consider very important, because prioritizing performance over correctness (safety) is irresponsible. That said, using a parser generator shouldn't have a significant impact on performance. When a network is involved, the parser isn't going to be the bottleneck anyway. > video I am not very familiar with the details of video formats, but I would suggest trying the parser combinator library Meredith mentions in the talk in my previous [1], known as "hammer"[2]. It's very easy to use, and it has specific support for bit-level parsing of binary formats. > numPersons 2 I highly recommend not using formats like this, because it's more complex than deterministic context-free. Using a length field requires that the parser remember state. It's also redundant information, creating the possibility of a miss-match between the number specified in "numPersons" and the actual number of rows. A format that uses s-expressions would be safer and more easier to implement: (ancestry (ancestor (person john "John Doe") (person jane "Jane Doe") ) ) The closing tag of the s-expression provides a similar benefit as the num* fields by simply marking the end of a complete record/field. > That's so trivial that I would never want to depend on a parser generator Is it really "trivial"? Or is your parse that you write in 10 minutes accepting ambiguous or invalid data? Is it actually checking for all of the error conditions? For most real-world grammars, it's unlikely you will catch all of the subtle ambiguities, interactions, and edge cases. The benefit of using a parser generator is that those entire classes of bugs are impossible. > check (relational) integrity In the trivial example you gave, you shouldn't have a grammar that requires checking relational integrity. In a more complex grammar, such checks would be the job of whatever is walking the AST that the parser returns. Parsers interpret syntax, not semantics. > If I leave away the num* fields above, the parser would need one token of lookahead. You need at least one token of lookahead anyway. Including the num* fields means the parser needs to remember and manage state. [2] https://github.com/UpstandingHackers/hammer https://github.com/UpstandingHackers/hammer
- jstimpfle 11y ago
  >> numPersons 2 > I highly recommend not using formats like this, because it's more complex than deterministic context-free. Barely. It avoids the complexity of look-ahead and reallocating growing buffers. > A format that uses s-expressions would be safer and more easier to implement: Trees are unsuitable for almost anything computationally, at least as authoritative representation. Prefer flat. (Widget hierarchies are one of a few counterexamples where the tradeoffs are different). This s-expression you gave is much more complex to parse. Granted, you get parsing as a tree for free. But then you have to go inside the tree and see what's there. That there are two persons per ancestor, etc. Navigating trees is hard. > Is it really "trivial"? Is it actually checking for all of the error conditions? Yes. Yes. Of course. It's the most boring code in the world. Parse numbers, allocate arrays correspondingly, parse each following table in a loop corresponding to the numbers parsed. You can do it all using scanf. Bail out as soon as a bad line comes in. 20 lines. > The benefit of using a parser generator is that those entire classes of bugs are impossible. Yeah. Well, they are not impossible. They are only possible in the parser generator. And interfacing a parser generator is itself not necessarily trivial. Plus, dependencies are a maintenance burden. The other approach is to make the design so simple (like the relational example) to make them (the classes) nonexistent. > You need at least one token of lookahead anyway. Not in the example I gave. > Including the num* fields means the parser needs to remember and manage state. I would hardly call that state. It's an immutable number, initialized in sequential code without real data dependencies (the data dependencies are resolved in the format -- you can not go wrong parsing it).
vinceguidry 11y ago
Data, if you have to format it in text, is best done using a regular grammar, which you can read with regular expressions into objects. You would then do the validations on the objects rather than on the string-formatted data.
- jstimpfle 11y ago
  Good point. But, are there practical tools for this? I still have to decide how I store the data in memory. For example, struct Model { int numPersons; int numAncestors; struct Person *person; struct Ancestor *ancestor; }; Or SOA instead of AOS? struct Model { int numPersons; int numAncestors; struct string *personname; struct string *persondesc; struct string *ancestorancestor; struct string *ancestordescendant; }; etc. Do you know tools which are in practice a better choice than the super boring ad-hoc code I described? Unless I'd have to define many of these types of formats the cost of going meta is just too high.
  - vinceguidry 11y ago
    I use Ruby, so I can't help you re: tooling. But if you are parsing a regular grammar with regular expressions, how much tooling do you need? The regexp does all the work. All you have to do is ensure that your data format is sane, that your delimiters can never appear in the data. With stuff like your problem, I can never be sure the data is clean, so I always default to a format like CSV or JSON and use standard library tools. I would shudder to have to work with that kind of data in C / C++ for the very reason you're asking these questions in this thread. It's low-level code for a high-level task. You're bound to fuck it up eventually and not foresee an edge case. But it would depend on what you want to do with the data. If you're walking trees, then you're going to want to store them in memory as trees. Whichever memory structure would be the most efficient in the algorithm you've got planned. Personally, since it's relational, I wouldn't bother with file storage at all and just dump it into a relational database, even if it's just SQLite. That would give you the most flexibility.
    - 11y ago