7 ms·

I actually (as a big C and C++ fan) quite a damning result for C. Its easy to say "just programming well" when bugs occur in badly written projects, but SQLite

I actually (as a big C and C++ fan) quite a damning result for C. Its easy to say "just programming well" when bugs occur in badly written projects, but SQLite is so well tested, and generally considered well written.

cremno 12y ago
Theo de Raadt, one month ago (not the only and first mail in this (derailed) thread though): >A review of libsqlite source code will demonstrate that it is written >using many old practices of coping with "older systems". Many of the >same techniques that caused unneccessary risk in OpenSSL. https://marc.info/?l=openbsd-misc&m=142566734914439&w=2 https://marc.info/?l=openbsd-misc&m=142566734914439&w=2
- jeremycw 12y ago
  Is there a list of 'best practices' that OpenBSD follows for C code or anything that points out what these 'old practices' are?
  - cremno 12y ago
    I don't think so. There are some other mails (like https://marc.info/?l=openbsd-misc&m=142563704303304&w=2 https://marc.info/?l=openbsd-misc&m=142563704303304&w=2), but I also think now I should've used a different quote.
  - ben_bai 12y ago
    Not really. There is this list [0] of security considerations for ports, which is a good starting point. Everybody writing in the same style [1] doesn't hurt either. [0] http://www.openbsd.org/faq/ports/guide.html#PortsSecurity http://www.openbsd.org/faq/ports/guide.html#PortsSecurity [1] http://www.openbsd.org/cgi-bin/man.cgi/OpenBSD-current/man9/style.9?query=style&sec=9 http://www.openbsd.org/cgi-bin/man.cgi/OpenBSD-current/man9/...
- rogerbinns 12y ago
  Note that the SQLite authors intentionally did that. It runs on many many systems including ones with trivial amounts of RAM. They have ancient compilers. I've waged a many year campaign to get them to at least use size_t and similar "modern" constructs, but no dice. They also only use techniques that are at least 20 years old, to avoid patent issues.
  - FrankBooth 12y ago
    Of course they did. So did the OpenSSL developers. It wasn't an accident. It's simply a design decision that has a set of costs associated with it.
TheLoneWolfling 12y ago
Your sentence to missing a word. Nonetheless, I agree. Eventually one cannot continue putting blame solely on the proximal cause. It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking. Even something as simple as "any writes inside the stack outside my stack frame and all reads inside the stack and after my stack frame should assert" (on an opt-in until the next return) would do wonders towards preventing some of these sorts of errors, although not all.
- comex 12y ago
  Have you heard of MPX? http://en.m.wikipedia.org/wiki/Intel_MPX http://en.m.wikipedia.org/wiki/Intel_MPX
  - TheLoneWolfling 12y ago
    Yes I have, but MPX is primarily for a different use case. Also, MPX has performance issues. See [1]. Also, it has false positives (!). Not a good thing. [1]https://code.google.com/p/address-sanitizer/wiki/IntelMemoryProtectionExtensions https://code.google.com/p/address-sanitizer/wiki/IntelMemory...
    - comex 12y ago
      Hmm... according to that page, the false positives and performance issues seem to largely derive from using the cache structure to store bounds externally. But if you manage the bounds explicitly as part of your data structures, and use BNDMOV/BNDMK rather than BND{ST,LD}X, it should be reasonably fast. What else could Intel do?
      - TheLoneWolfling 12y ago
        Have a read of the linked page again. A large chunk of the performance issues are because in many cases you can't just "use BNDMOV/BNDMK rather than BND{ST,LD}X". There are a number of data structures where managing bounds explicitly has... issues. Namely, you end up with a lot of overhead. And the entire purpose of hardware support is to prevent the overhead. Something like, as I said, an opt-in assert when you read past the end of your stack frame, or write before or after your stack frame, doesn't have the overhead. It doesn't prevent a lot of things - about the only thing it prevents is stack smashing - but it's better than nothing and doesn't have the overhead.
chubot 12y ago
I agree, but lexers and parsers are especially stateful pieces of code. I'm not a static typing person (I like Python, bash, and C), but I have resolved to write all future parsers in OCaml or a similar language. For other types of code, if you don't have a code path explosion, you can do OK in C. For example, numerical simulation code. Unfortunately async code in C like Nginx tends to also produce this code path explosion. And kernel code is also littered with state machines. Another interesting thing is that SQLite's parser is generated with Lemon. It's not even a hand-written parser in C (like Lua), which would be much worse. I guess all the crashes were in the semantic actions of the parser?
- jbangert 12y ago
  I think you shouldn't write parsers by hand at all and instead generate them automatically -- without semantic actions. I wrote a parser generator for tricky binary formats a few months ago - https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-bangert.pdf https://www.usenix.org/system/files/conference/osdi14/osdi14... and there's a paper explaining it here https://github.com/jbangert/nail https://github.com/jbangert/nail
  - Nitramp 12y ago
    I've written parsers with ANTLR, lex/bison, and other tools, and I've hand written parsers. With the generators, it's very hard to get several features of a high quality parser right. In particular error messages and error recovery, but also handling some more esoteric grammars (in particular ones that are not entirely unambiguous, LALR(1), etc). Using a parser generator also complicates your build chain, complicates refactorings, usually means you get bad source tooling, and often slows down the edit/test cycle quite a bit. At the same time, if you're doing it right, writing a simple LL(1) parser by hand really isn't that hard, and the resulting code doesn't have to be much longer than the spec in your generator's language. Even in languages that are not that DSL-friendly (e.g. Java), you can end up with very compact, readable code. Plus you get all your usual tooling to do so (e.g. IDE support).
    - 12y ago
bch 12y ago
I think "damning" might be a bit much -- it's got bugs. Like everything on earth, it's not perfect. I was going to say it's full of meta-programming too, which should allow for simple fixes to have far-reaching implications (indeed, bugs would have same effect), but looking at the repo and build, I'm not seeing signs of meta-programming in effect. Fossil[0] (also initiated by Richard Hipp, and used to (created explictily to) manage the sqlite codebase) however, is a meta-programming example. Point is: C is not untenable, still offers a lot, and has great tooling built up around it. Don't give up on it, but know it's strengths and weaknesses. [0] http://fossil-scm.org/index.html/doc/trunk/www/index.wiki http://fossil-scm.org/index.html/doc/trunk/www/index.wiki
- obstinate 12y ago
  Weakness: the best programmers in the world are empirically unable to write secure code in this language. The errors that cause the insecurity are trivial to prevent via language design, but very difficult for humans to reliably avoid when not protected by the compiler. It's a pretty big one.
- sitkack 12y ago
  I am with you, as a C/C++ programmer we just need to try harder to make correct code.
  - nightpool 12y ago
    It's almost like watching someone with Stockholm syndrome :P (jk <3)
    - Scramblejams 12y ago
      I know you meant that as a joke but I think there's some truth there. It's so easy to become personally invested in the tools we use and instinctively defend them (even to the point of blaming outselves for our tools' shortcomings) rather than try to switch.
      - 12y ago
copx 12y ago
Thought the same, because if you look at what he found.. >ranging from NULL pointer dereferences, to memory fenceposts visible only under ASAN or Valgrind, to pretty straightforward uses of uninitialized pointers (link), bogus calls to free() (link), heap buffer overflows (link), and even stack-based ones (link). .. it seems that all those bugs are not even possible in Rust.
- steveklabnik 12y ago
  ... in safe Rust, yes. But Rust isn't perfect, we _will_ have these kinds of issues crop up, especially with regards to unsafe code. Rust will significantly reduce these kinds of issues, but not completely eliminate them. There is no silver bullet. We've just started unleasing afl on Rust code, and it can still find issues: https://github.com/rust-lang/rust/issues/24276 https://github.com/rust-lang/rust/issues/24276
  - kibwen 12y ago
    Let it be said that the Rust community believes in defense-in-depth. A low-level language with safe defaults is only one piece of the equation; a complement rather than a supplement to testing, auditing, fuzzing, sandboxing, and so on.
  - chubot 12y ago
    Is the stack trace saying that the Rust parser tickles a bug in jemalloc or somehow uses it unsafely? A parser (which uses malloc) seems like a pretty basic use case for 100% safe code. When I think of unsafe code, I think of needing to make raw syscalls, libc calls, or inline assembly. Not string manipulation and malloc. I am not super familiar with Rust, but I imagine you don't have to use unsafe {} every time you need to malloc, right?
    - kibwen 12y ago
      The only reason that the parser was using unsafe code is because it is an extremely old part of the codebase, and likely required the unsafe blocks to hack around some deficiency in the compiler from Rust 0.3 or alike. Recent efforts to overhaul the parser have reduced this dramatically: there are two legitimate remaining uses of `unsafe` (dealing with libc stuff), and four uses of `unsafe` that all have associated FIXMEs.
GFK_of_xmaspast 12y ago
Given all the platforms and hardware and constraints sqlite has to run on, what would you suggest replacing it with.
f- 12y ago
As others have said, parsers for complex formats (be it text-based or binary) are exceptionally hard. There are some classes of C/C++ software where the choice of a language doesn't have such a striking effect. For parsers, the effect is hard to ignore. But parsers are also the kind of stuff you almost always end up writing in C/C++, and there are semi-compelling reasons for doing so - chiefly, performance and flexibility. You can disagree and make your pitch for Ocaml or JavaScript or whatever, but really, if we had clearly superior choices, we wouldn't be dealing with this problem today (or it would be a much more limited phenomenon). There are some interesting contenders, but the revolution won't happen tomorrow, no matter how much we talk about it on HN. Perhaps a more fitting conclusion is that if you are parsing untrusted documents, our brains are too puny to get it right, and the parser really needs to live in a low-overhead sandbox. Mechanisms such as seccomp-bpf offer a really convenient and high-performance way to pull it off.
- TazeTSchnitzel 12y ago
  There are some other interesting choices. Like Rust, or Cyclone.
- chubot 12y ago
  I agree with sandboxing, but a problem is that by using something like seccomp-bpf, you're turning highly portable C code into a highly platform-specific and even architecture-specific system. (Well, it won't be architecture-specific if you use the old plain seccomp, which is probably all you need.) You also need to deal with serialization and deserialization of the parse tree, which isn't super hard, but people still get it wrong. Writing parsers is already hard, but writing secure parsers is at least 2x harder than that, or maybe 4x if you have to port it to 3 platforms. There really needs to be some kind of "libsandbox" for parsers.
- stingraycharles 12y ago
  In C++, we have Boost.Spirit, and for C there is Bison/Flex. Surely those are better and more safe alternatives than hand-rolling your own parser?
  - 12y ago

cremno 12y ago

Theo de Raadt, one month ago (not the only and first mail in this (derailed) thread though): >A review of libsqlite source code will demonstrate that it is written >using many old practices of coping with "older systems". Many of the >same techniques that caused unneccessary risk in OpenSSL. https://marc.info/?l=openbsd-misc&m=142566734914439&w=2 https://marc.info/?l=openbsd-misc&m=142566734914439&w=2

jeremycw 12y ago
Is there a list of 'best practices' that OpenBSD follows for C code or anything that points out what these 'old practices' are?
- cremno 12y ago
  I don't think so. There are some other mails (like https://marc.info/?l=openbsd-misc&m=142563704303304&w=2 https://marc.info/?l=openbsd-misc&m=142563704303304&w=2), but I also think now I should've used a different quote.
- ben_bai 12y ago
  Not really. There is this list [0] of security considerations for ports, which is a good starting point. Everybody writing in the same style [1] doesn't hurt either. [0] http://www.openbsd.org/faq/ports/guide.html#PortsSecurity http://www.openbsd.org/faq/ports/guide.html#PortsSecurity [1] http://www.openbsd.org/cgi-bin/man.cgi/OpenBSD-current/man9/style.9?query=style&sec=9 http://www.openbsd.org/cgi-bin/man.cgi/OpenBSD-current/man9/...
rogerbinns 12y ago
Note that the SQLite authors intentionally did that. It runs on many many systems including ones with trivial amounts of RAM. They have ancient compilers. I've waged a many year campaign to get them to at least use size_t and similar "modern" constructs, but no dice. They also only use techniques that are at least 20 years old, to avoid patent issues.
- FrankBooth 12y ago
  Of course they did. So did the OpenSSL developers. It wasn't an accident. It's simply a design decision that has a set of costs associated with it.

TheLoneWolfling 12y ago

Your sentence to missing a word. Nonetheless, I agree. Eventually one cannot continue putting blame solely on the proximal cause. It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking. Even something as simple as "any writes inside the stack outside my stack frame and all reads inside the stack and after my stack frame should assert" (on an opt-in until the next return) would do wonders towards preventing some of these sorts of errors, although not all.

comex 12y ago
Have you heard of MPX? http://en.m.wikipedia.org/wiki/Intel_MPX http://en.m.wikipedia.org/wiki/Intel_MPX
- TheLoneWolfling 12y ago
  Yes I have, but MPX is primarily for a different use case. Also, MPX has performance issues. See [1]. Also, it has false positives (!). Not a good thing. [1]https://code.google.com/p/address-sanitizer/wiki/IntelMemoryProtectionExtensions https://code.google.com/p/address-sanitizer/wiki/IntelMemory...
  - comex 12y ago
    Hmm... according to that page, the false positives and performance issues seem to largely derive from using the cache structure to store bounds externally. But if you manage the bounds explicitly as part of your data structures, and use BNDMOV/BNDMK rather than BND{ST,LD}X, it should be reasonably fast. What else could Intel do?
    - TheLoneWolfling 12y ago
      Have a read of the linked page again. A large chunk of the performance issues are because in many cases you can't just "use BNDMOV/BNDMK rather than BND{ST,LD}X". There are a number of data structures where managing bounds explicitly has... issues. Namely, you end up with a lot of overhead. And the entire purpose of hardware support is to prevent the overhead. Something like, as I said, an opt-in assert when you read past the end of your stack frame, or write before or after your stack frame, doesn't have the overhead. It doesn't prevent a lot of things - about the only thing it prevents is stack smashing - but it's better than nothing and doesn't have the overhead.

chubot 12y ago

I agree, but lexers and parsers are especially stateful pieces of code. I'm not a static typing person (I like Python, bash, and C), but I have resolved to write all future parsers in OCaml or a similar language. For other types of code, if you don't have a code path explosion, you can do OK in C. For example, numerical simulation code. Unfortunately async code in C like Nginx tends to also produce this code path explosion. And kernel code is also littered with state machines. Another interesting thing is that SQLite's parser is generated with Lemon. It's not even a hand-written parser in C (like Lua), which would be much worse. I guess all the crashes were in the semantic actions of the parser?

jbangert 12y ago
I think you shouldn't write parsers by hand at all and instead generate them automatically -- without semantic actions. I wrote a parser generator for tricky binary formats a few months ago - https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-bangert.pdf https://www.usenix.org/system/files/conference/osdi14/osdi14... and there's a paper explaining it here https://github.com/jbangert/nail https://github.com/jbangert/nail
- Nitramp 12y ago
  I've written parsers with ANTLR, lex/bison, and other tools, and I've hand written parsers. With the generators, it's very hard to get several features of a high quality parser right. In particular error messages and error recovery, but also handling some more esoteric grammars (in particular ones that are not entirely unambiguous, LALR(1), etc). Using a parser generator also complicates your build chain, complicates refactorings, usually means you get bad source tooling, and often slows down the edit/test cycle quite a bit. At the same time, if you're doing it right, writing a simple LL(1) parser by hand really isn't that hard, and the resulting code doesn't have to be much longer than the spec in your generator's language. Even in languages that are not that DSL-friendly (e.g. Java), you can end up with very compact, readable code. Plus you get all your usual tooling to do so (e.g. IDE support).
  - 12y ago

bch 12y ago

I think "damning" might be a bit much -- it's got bugs. Like everything on earth, it's not perfect. I was going to say it's full of meta-programming too, which should allow for simple fixes to have far-reaching implications (indeed, bugs would have same effect), but looking at the repo and build, I'm not seeing signs of meta-programming in effect. Fossil[0] (also initiated by Richard Hipp, and used to (created explictily to) manage the sqlite codebase) however, is a meta-programming example. Point is: C is not untenable, still offers a lot, and has great tooling built up around it. Don't give up on it, but know it's strengths and weaknesses. [0] http://fossil-scm.org/index.html/doc/trunk/www/index.wiki http://fossil-scm.org/index.html/doc/trunk/www/index.wiki

obstinate 12y ago
Weakness: the best programmers in the world are empirically unable to write secure code in this language. The errors that cause the insecurity are trivial to prevent via language design, but very difficult for humans to reliably avoid when not protected by the compiler. It's a pretty big one.
sitkack 12y ago
I am with you, as a C/C++ programmer we just need to try harder to make correct code.
- nightpool 12y ago
  It's almost like watching someone with Stockholm syndrome :P (jk <3)
  - Scramblejams 12y ago
    I know you meant that as a joke but I think there's some truth there. It's so easy to become personally invested in the tools we use and instinctively defend them (even to the point of blaming outselves for our tools' shortcomings) rather than try to switch.
    - 12y ago

copx 12y ago

Thought the same, because if you look at what he found.. >ranging from NULL pointer dereferences, to memory fenceposts visible only under ASAN or Valgrind, to pretty straightforward uses of uninitialized pointers (link), bogus calls to free() (link), heap buffer overflows (link), and even stack-based ones (link). .. it seems that all those bugs are not even possible in Rust.

steveklabnik 12y ago
... in safe Rust, yes. But Rust isn't perfect, we _will_ have these kinds of issues crop up, especially with regards to unsafe code. Rust will significantly reduce these kinds of issues, but not completely eliminate them. There is no silver bullet. We've just started unleasing afl on Rust code, and it can still find issues: https://github.com/rust-lang/rust/issues/24276 https://github.com/rust-lang/rust/issues/24276
- kibwen 12y ago
  Let it be said that the Rust community believes in defense-in-depth. A low-level language with safe defaults is only one piece of the equation; a complement rather than a supplement to testing, auditing, fuzzing, sandboxing, and so on.
- chubot 12y ago
  Is the stack trace saying that the Rust parser tickles a bug in jemalloc or somehow uses it unsafely? A parser (which uses malloc) seems like a pretty basic use case for 100% safe code. When I think of unsafe code, I think of needing to make raw syscalls, libc calls, or inline assembly. Not string manipulation and malloc. I am not super familiar with Rust, but I imagine you don't have to use unsafe {} every time you need to malloc, right?
  - kibwen 12y ago
    The only reason that the parser was using unsafe code is because it is an extremely old part of the codebase, and likely required the unsafe blocks to hack around some deficiency in the compiler from Rust 0.3 or alike. Recent efforts to overhaul the parser have reduced this dramatically: there are two legitimate remaining uses of `unsafe` (dealing with libc stuff), and four uses of `unsafe` that all have associated FIXMEs.

GFK_of_xmaspast 12y ago

Given all the platforms and hardware and constraints sqlite has to run on, what would you suggest replacing it with.

f- 12y ago

As others have said, parsers for complex formats (be it text-based or binary) are exceptionally hard. There are some classes of C/C++ software where the choice of a language doesn't have such a striking effect. For parsers, the effect is hard to ignore. But parsers are also the kind of stuff you almost always end up writing in C/C++, and there are semi-compelling reasons for doing so - chiefly, performance and flexibility. You can disagree and make your pitch for Ocaml or JavaScript or whatever, but really, if we had clearly superior choices, we wouldn't be dealing with this problem today (or it would be a much more limited phenomenon). There are some interesting contenders, but the revolution won't happen tomorrow, no matter how much we talk about it on HN. Perhaps a more fitting conclusion is that if you are parsing untrusted documents, our brains are too puny to get it right, and the parser really needs to live in a low-overhead sandbox. Mechanisms such as seccomp-bpf offer a really convenient and high-performance way to pull it off.

TazeTSchnitzel 12y ago
There are some other interesting choices. Like Rust, or Cyclone.
chubot 12y ago
I agree with sandboxing, but a problem is that by using something like seccomp-bpf, you're turning highly portable C code into a highly platform-specific and even architecture-specific system. (Well, it won't be architecture-specific if you use the old plain seccomp, which is probably all you need.) You also need to deal with serialization and deserialization of the parse tree, which isn't super hard, but people still get it wrong. Writing parsers is already hard, but writing secure parsers is at least 2x harder than that, or maybe 4x if you have to port it to 3 platforms. There really needs to be some kind of "libsandbox" for parsers.
stingraycharles 12y ago
In C++, we have Boost.Spirit, and for C there is Bison/Flex. Surely those are better and more safe alternatives than hand-rolling your own parser?
- 12y ago