9 ms·
Puffs: Parsing Untrusted File Formats Safely
- evincarofautumn 9y agoSome curious things about the language: • All operators have equal precedence, so parentheses are required when mixing operators. I guess they’ve seen one too many bugs from precedence confusion. • It doesn’t have dependent types; rather, it uses a proof checker with some built-in knowledge about the language, and a way to specify preconditions, postconditions, and invariants that the checker can reason about. • There is limited effect typing: functions can be marked pure, impure (!), or impure coroutine (?). • There doesn’t appear to be any kind of polymorphism—over types, effects, refinements, or proofs.
- johnlbevan2 9y ago> "All operators have equal precedence, so parentheses are required..." Just to play devil's advocate (aka be annoying); parentheses are operators. Ref: https://softwareengineering.stackexchange.com/a/208354/69247 https://softwareengineering.stackexchange.com/a/208354/69247
- Chris2048 9y agoI don't find that link convincing. For one thing, the premise is assumed in the question. Secondly, when it says "they also include ()[] as operators" is implies it is talking about language-specific terminology rather than a general term. WP describes: https://en.wikipedia.org/wiki/Operator_(computer_programming) https://en.wikipedia.org/wiki/Operator_(computer_programming... > Occasionally parts of a language may be described as "matchfix" or "circumfix" operators, either to simplify the language's description or implementation. Bu then, the term "operator" seems to also have mathematical roots: https://en.wikipedia.org/wiki/Operator_(mathematics) https://en.wikipedia.org/wiki/Operator_(mathematics) The relevant part seems to be the definition refering to syntax, or denotation: > Operator is also used for denoting the symbol of a mathematical operation. This is related with the meaning of "operator" in computer programming Now, whether "the symbol" implies a singular symbol, and excludes delimiter symbols might be a matter of semantics ;-)
- _dcwr 9y agoA devil's advocate is not an annoying person but someone who argues against something he truly believes in or hopes to be true in order to provide a debate and help prove the point in stronger ways and show onlookers that contrary opinions were considered. It comes from canonization process in Vatican where someone (who is not an actual satan worshiper or against the church) argued in favor of the devil (against the candidate) to force the other pro-sainthood side to provide good solid proof of the sainthood, miracles done, etc. of the candidate. What you're doing is just being annoying by nitpicking the casual wording. There is no debate to be had from "parentheses are kinda operators" and the meaning of the original line was understandable, even if you consider parentheses operators.
- masklinn 9y ago> All operators have equal precedence, so parentheses are required when mixing operators. Doesn't that mean it rejects precedence? In a language equal precedence (e.g. Smalltalk), operators would just be executed from LTR or RTL.
- evincarofautumn 9y agoI agree, although I suppose different operators could still have different associativity in a language without precedence. I took that phrasing from the “Puffs the Language” documentation.
- masklinn 9y ago> I suppose different operators could still have different associativity in a language without precedence That… is true, and I have a hard time computing how it would even work.
- klodolph 9y agoThink exponentiation, where 2^3^4 might be 2^(3^4), but where subtraction 2-3-4 is (2-3)-4.
- mnarayan01 9y agoConsider: 2-3^4
- irishsultan 9y agoSince there is no precedence in this (hypothetical) language that would be an invalid expression.
- evincarofautumn 9y agoOne way to do it would be to have a default associativity between different operators, but chains of the same operator can override it, e.g. suppose “⧺” means concatenation (rightward), “×” means repetition (leftward), and the default is leftward: [1, 2] ⧺ [3, 4] ⧺ [5, 6] × 2 × 3 (([1, 2] ⧺ ([3, 4] ⧺ [5, 6])) × 2) × 3 [ [ [1…6], [1…6] ], [ [1…6], [1…6] ], [ [1…6], [1…6] ] ] I dunno how good an idea that would be in practice, though.
- skybrian 9y agoAn aside: I'm writing a toy language without operator-specific precedence and it's surprisingly readable. One trick is to treat expressions without spaces (a+b) as higher precedence than expressions with spaces (a + b). This is enough to write many formulas in an intuitive way, with few parentheses.
- amenghra 9y agoThe best way to solve precedence confusion (IMHO) is to have your IDE show you how the expression is going to get parsed. Possible ways to achieve this include highlighting subexpressions, underlines, light-colored parenthesis, showing a tree, etc. This could be done only on mouse-over to not burden the overall UI.
- nigeltao 9y ago> I guess they’ve seen one too many bugs from precedence confusion. Yep. I just filed a precedence bug at https://github.com/jbangert/nail/issues/7 https://github.com/jbangert/nail/issues/7 for Nail, which is a security-concious project. (It was presented at LangSec 2014). > It doesn’t have dependent types. Yep. Programming language theorists love type systems, and dependent types are one way to prove bounds safety, but they're not the only way. Puffs is an imperative language, not functional (for the reasons described in https://github.com/google/puffs/blob/master/doc/related-work.md https://github.com/google/puffs/blob/master/doc/related-work...). With mutable state, a Puffs variable's within-bounds-ness can change over that variable's lifetime, but its type does not. > There is limited effect typing: functions can be marked pure, impure (!), or impure coroutine (?). Yep. That's the current design, although I'll probably revise that based on recent experience. The question mark denotes a coroutine, as you noted, but also whether that function can (very roughly speaking) throw an exception. I think we will need separate syntaxes for those two concepts, since I've wanted the latter without the former. > There doesn’t appear to be any kind of polymorphism—over types, effects, refinements, or proofs. Yep. Haven't needed it yet, and I've erred on the side of simplicity and leaving things out.
- darkblackcorner 9y agoCorrect me if I'm wrong but does Rust not already solve this issue (fast like C, safe, compile-time checks)? Edit: nevermind, I missed "can be used anywhere C libraries are used"...
- tambourine_man 9y agoThat's a great acronym
- microcolonel 9y agoThis is very interesting, after kicking the tires on a few parsers, I've come to the conclusion that most parsers are absolute garbage, and it's nobody's fault in particular. This should make it close to feasible to write fast native parsers (especially validators) which aren't a liability.
- andrewchambers 9y agoWhat makes this language specific to parsing files? It mentions that it is a DSL for parsing files a few times... why not network packets, or any other task.
- fixermark 9y agoI interpret that to be more a statement of creator intent than a restriction on the end-user. The general vibe I get is "This language is verbose as hell and puts a lot of constraints on what your functions are allowed to do; writing a full-sized application in Puffs alone is going to be a super-tedious exercise."
- gowld 9y agoNetwork packets are files.
- CapacitorSet 9y ago>The aim is to produce software libraries that are as safe as Go or Rust, roughly speaking, but as fast as C, and that can be used anywhere C libraries are used. I'm all for having different implementations of software, but does Rust not fulfill these requirements?
- Ded7xSEoPKYNsDd 9y agoThere are C compilers for many architectures that the Rust compiler (today) does not support. They may also be referring to the fact that you can't just drop it into existing projects with their complicated build systems in the same way that you can drop a few generated ".c" and ".h"files.
- yaantc 9y agoGreat points, plus from the puff readme: "In Rust, integer overflow is checked at run time in debug mode and silently ignored in release mode by default, as the run time performance penalty was deemed too great.". With puff, it's statically checked. I haven't delved into puff's details, but to support as many environment as possible in an easy way today, a DSL generating C seems a pragmatic decision.
- steveklabnik 9y agoSmall note here, we left the spec broad enough that if the runtime checks get cheap enough, we can do them in release mode as well.
- tveita 9y agoBy default, but it is possible to enable integer overflow for release builds with "-C overflow-checks".
- lossolo 9y agoBut it's about checking it compile time because of overhead not at runtime.
- ekr 9y agoAn interesting observation: this was written by the brother of Terence Tao.
- dullgiulio 9y agoIf I am not wrong, he is a member of the Go core team?
- nigeltao 9y agoYep, a member of the Go core team, although not as active in the Go community these days as I was in past years. And yep, I'm also Terry's brother.
- margorczynski 9y ago> The aim is to produce software libraries that are as safe as Go or Rust, roughly speaking, but as fast as C, and that can be used anywhere C libraries are used One question about this to people more versed in language compilation - wouldn't it be possible for SAFE Rust code to be faster than C code considering that the Rust compiler has much more syntax to play around and optimize? Cause many of those safe constructs are part of the language and can be taken into account
- pkhuong 9y agoThe expressiveness of LLVM IR is very close to C. Given a high enough tolerance for pain, one could implement the same rewrite that the rust compiler would implement in C (without even going into inline assembly). In practice… maybe. However, I find we're more forgiving of unpredictable performance (either wrt analysis runtime or quality of analysis) in safety checking tools than in code generators. The ergonomics of bitblasting code generation questions to SAT aren't great.
- CapacitorSet 9y agoI wouldn't be too sure about that. Rust gives more compile-time guarantees, allowing the compiler not to emit code for otherwise plausible conditions (see eg. pointer aliasing); on the other hand, C compilers typically rely on undefined behaviour to apply optimisations, whereas Rust may not have as much undefined behaviour due to its safety.
- steveklabnik 9y agoSafe Rust has no UB, outside of some bugs, to be clear. That said, optimization is all about guarantees: this broad of a claim (UB vs info) because both are about what's guaranteed, and what's not. That is, they play similar roles, so you'd have to be comparing how much of each is in what amount in what code. We generally expect Rust to be roughly as fast as C, sometimes faster, sometimes slower. Modulo optimizer bugs in each case, of course.
- chrismorgan 9y agoIn theory, yes, some Rust code can be faster than the C or C++ code people would write, especially as pertains to the guarantees offered by its aliasing control. In practice, LLVM hasn’t had any incentive to implement those sorts of optimisations at this stage (because before Rust came along nothing would benefit from them), so the benefits are generally theoretical only. It remains to be seen what this will effect.
- tom_mellior 9y agoDoes anyone know what analysis or prover they use to discharge proof obligations? I poked around the .md files in the repository, but I haven't seen this addressed anywhere. I'm not (yet) motivated to dig into the actual source...
- haskellandchill 9y agoLooks like it is not a general system, they prove the hardcoded binary operations: https://github.com/google/puffs/blob/master/lang/check/assert.go#L270 https://github.com/google/puffs/blob/master/lang/check/asser...
- tom_mellior 9y agoThanks. From what I've seen in that file and another one in the same directory, it seems to be a standard abstract interpreter on a domain of intervals. I would have expected a more refined relational domain that can express certain inequalities, but this seems to be enough for a first prototype.
- nigeltao 9y agoI'm not entirely sure what you had in mind, but you can express certain inequalities. For example, https://github.com/google/puffs/blob/master/std/gif/decode_lzw.puffs https://github.com/google/puffs/blob/master/std/gif/decode_l... has this line: assert n_bits < (width + 8) via etc The 'via' syntax is discussed at https://github.com/google/puffs/blob/master/doc/puffs-the-language.md https://github.com/google/puffs/blob/master/doc/puffs-the-la...
- tom_mellior 9y agoThanks for your answer. Yes, this kind of symbolic inequalities was what I had in mind. The solution via "via" is quite clever. In the beginning I had thought that maybe you were using something like Pentagons: https://www.microsoft.com/en-us/research/publication/pentagons-a-weakly-relational-abstract-domain-for-the-efficient-validation-of-array-accesses/ https://www.microsoft.com/en-us/research/publication/pentago... which were developed explicitly in the context of proving array bounds checks. You might want to give them a look. They would cost you in implementation effort, of course, but they might make Puffs (almost as) fast and pretty smart!
- actionowl 9y agoWe're google, we can pick any name we want, even if a very similar project is already using it. https://www.netbsd.org/docs/puffs/ https://www.netbsd.org/docs/puffs/
- acdha 9y agoCreating a filesystem in user-space is “very similar”? I mean, they both involve files but… http://netbsd.gw.com/cgi-bin/man-cgi?puffs+4.i386+NetBSD-7.1 http://netbsd.gw.com/cgi-bin/man-cgi?puffs+4.i386+NetBSD-7.1
- deepsun 9y agoWhat will I get if I type "sudo apt install puffs"? What do I have if I see libpuffs.so somewhere?
- acdha 9y agoThat's a valid question but not the same as saying the projects are very similar. In that case in particular, the answer would come down to “Are you running on NetBSD?” and so the most likely answer is that the NetBSD package maintainer would package it as "google-puffs" or something like that.
- nigeltao 9y agoYeah, it'd be unfortunate, but not unprecedented. For example, Debian has both epiphany and epiphany-browser, which are two separate things.
- nigeltao 9y agoI'm considering a name change: https://groups.google.com/d/topic/puffslang/cSrH-s7UqwA/discussion https://groups.google.com/d/topic/puffslang/cSrH-s7UqwA/disc... As for the "We're google, we can pick any name we want" assumption that somebody else wrote earlier, https://github.com/google/puffs https://github.com/google/puffs says "Disclaimer: This is not an official Google product, it is just code that happens to be owned by Google". Also, before the launch, I didn't find many hits for "puffs" when searching github.com projects, or searching "apt search puffs", or searching the Web in general for queries like [puffs programming], or uses of the ".puffs" file extension. It's not like I cackled maniacally as I deliberately screwed over the NetBSD puffs project, whether for myself or on behalf of Google, I just didn't find it. I am bad at searching. Sorry.
- Santosh83 9y agoCan this DSL be extended to cover other classes of bugs and undefined behaviour in C without spilling over into runtime checks?
- nigeltao 9y agoPossibly. I'd like Puffs (and its generated C code) to be free of UB (and I've skimmed the blog.regehr.org posts), but I'm not 100% certain if it is.
- tc 9y agoThis DSL seems largely motivated by the desire for provable compile-time bounds checking. One general-purpose modern language that can check bounds at compile time and generate code that is performance-competitive with C is ATS: http://www.ats-lang.org/ http://www.ats-lang.org/ Dependent types are meant to solve exactly this class of problem. Rust has an RFC for adding these: https://github.com/rust-lang/rfcs/issues/1930 https://github.com/rust-lang/rfcs/issues/1930
- throwaway613834 9y agoAren't dependent types undecidable?
- yeahbutbut 9y agoMaybe.
- throwaway613834 9y agoWhat do you mean by "maybe"? [1] https://cs.stackexchange.com/questions/12691 https://cs.stackexchange.com/questions/12691
- yeahbutbut 9y agoI was trying to be punny by implying indecision... edit: also thanks for the link :)
- throwaway613834 9y agoOhh wow that went over my head haha.
- tomp 9y agointegers with additions are decidable - that's pretty much what you need to verify array bounds (multiplication with a constant is included as well, so matrices should work too).
- eridius 9y ago> The aim is to produce software libraries that are as safe as Go or Rust, roughly speaking, but as fast as C, and that can be used anywhere C libraries are used. This is kind of a weird thing to say, because Rust is as fast as C, and can be used to create C-compatible libraries.
- nigeltao 9y agoSee my other comment (written after your comment). Search this page for "That announcement has more to say about the comparison to Rust, which is probably the most frequently asked question."
- nigeltao 9y agoHi, Puffs author here. ingve linked to the github page instead of the announcement e-mail: https://groups.google.com/forum/#!topic/puffslang/2z61mNTAMns/discussion https://groups.google.com/forum/#!topic/puffslang/2z61mNTAMn... That announcement has more to say about the comparison to Rust, which is probably the most frequently asked question. There's also some more words, on Rust and on other related work like Dafny, at https://github.com/google/puffs/blob/master/doc/related-work.md https://github.com/google/puffs/blob/master/doc/related-work... Edit: It's also not Rust per se, but the numbers at https://github.com/google/puffs/blob/master/doc/benchmarks.md https://github.com/google/puffs/blob/master/doc/benchmarks.m... shows that, on Puffs' benchmarks, gcc 7.2 noticably outperforms clang/llvm 5.0. I'm sure this is a solvable problem, and not a fundamental flaw with llvm, but fixing that's beyond my llvm knowledge.
- kleiba 9y agoCoincidentally, the word "Puffs" in German is a colloquial expression for "brothels". Not that it matters much in your context, just a piece of trivia...
- vvanders 9y ago> Some of the safe languages (Go, Java, JavaScript, Python, Rust, etc.) are faster than others, but generally speaking, they're not as fast as C/C++. Consider an array indexing expression like "a[i]". I don't think you'll win any friends in the Rust camp by making broad statements like that. Performance of "unsafe" vs "safe" languages largely boils down to memory access patterns, cache usage and how many levels of indirection you tend to hit. Rust easily matches C/C++ while keeping high level abstractions(bounds checks are done at slice level and not per-element access). I don't think Mozilla would have used Rust for Servo/Quantum if it was slower than C++. It's certainly held true in all the cases I've used Rust in place of C++.
- nigeltao 9y agoFirst, as I said in another comment, Rust is great tech, written by great engineers. Puffs is still different (with different trade-offs). And, yes, memory access patterns, cache usage, etc. affect performance. And, yes, in general, Rust performs comparably to C/C++. As I noted elsewhere, Rust with runtime arithmetic overflow checks currently performs worse than Rust without such checks. So, yes, Rust without those checks is as fast as C, and in general, arithmetic overflow isn't the biggest concern. steveklabnik, a Rust expert, commented on this page that, in the future, "if the runtime checks get cheap enough, we can do them in release mode as well". If so, that's great, I'm happy to be proven wrong. Cheap still isn't zero, though, and see "nanoseconds become milliseconds" at https://groups.google.com/forum/#!topic/puffslang/2z61mNTAMns/discussion https://groups.google.com/forum/#!topic/puffslang/2z61mNTAMn... In contrast, Puffs today performs as fast as C, with arithmetic overflow checks. They just happen to be compile time checks. And sometimes overflow is indeed a concern (search for "underflow" in https://blog.chromium.org/2012/05/tale-of-two-pwnies-part-1.html https://blog.chromium.org/2012/05/tale-of-two-pwnies-part-1....). I'm sorry, but I don't understand what you mean by bounds checks being done at the slice level and not per-element access. A statement like "pixels[y * stride + x] = etc" is per-element, right?
- rurban 9y agoLooks like a mix of ATS and Pony, but without the rich proof system of ATS, without the safeties provided by both and without the performance advantages of both. Wonder why they still try to reinvent the wheel, when there are already established and better langs out there. Well, it's Google, so they are still academics.