8 ms·

This is surprising. SQLite is known for having 100% code coverage, fuzzy testing, and a 644:1 tests to code ratio. If even that cannot stop this kind of attack

by jiofih 6y ago

This is surprising. SQLite is known for having 100% code coverage, fuzzy testing, and a 644:1 tests to code ratio. If even that cannot stop this kind of attack then we really need to rethink computers from the ground up... https://sqlite.org/testing.html https://sqlite.org/testing.html

jrockway 6y ago
People have rethought computers from the ground up. The C++ version was slightly faster in a benchmark, though, so their thought was ignored.
- otabdeveloper4 6y ago
  Yeah, I'm sure switching to a more fashionable programming language will automatically fix all bugs and security issues. (sarcasm)
  - mrmonkeyman 6y ago
    Memory leaks are not bugs, they are a fundamental design error.
  - pdimitar 6y ago
    Every little bit helps IMO. Rust seems like it eliminates class of bugs (and so do Haskell and OCaml), the JVM looks like it could prevent another subset of them, and I am sure there are other examples. Not going to bash anyone for using C -- sqlite's team has their priorities and values clearly stated (performance and discipline) -- but it's probably time for all of us to admit that not all recent tech innovation is about fads. Some of it is actually genuinely useful and helps with age-old problems (though sadly, none of it addresses all of them).
  - anyfoo 6y ago
    All of them? No. But will a modern language, where many more properties are mathematically proven through the type system, massively improve the situation? Yes. If you don’t believe me, do the converse and write your next big project completely in assembly (which is effectively untyped), and see what happens.
    - saagarjha 6y ago
      Removed undefined behavior from your code with this one weird trick!
    - dathinab 6y ago
      Through only if has high usability. You currently can bend C++ into ways to have such a type system. The usability this introduced through additional complexity is just very very bad. So no one does it because bad usability means bad productivity and getting a project done with bugs is often better then getting it not done at all (sure there are exceptions!).
      - anyfoo 6y ago
        That's a good point, and I think you've hit one of the main issues why we're still stuck with old, unsafe languages. There is the saying that once you got a Haskell program to compile, it usually just works, and I personally found it to be true a lot. But getting it through the compiler can indeed be much more of a journey than in, say, C. And I realize that the work you have to put in to just even being able to run something can be discouraging, maybe going against a natural (or maybe just common) affinity towards tight, iterative "change-compile-try" approaches. Still, in cases where it really matters, i.e. system software or common, but often mission-critical software like sqlite, maybe it's worth taking the jump?
        pdimitar 6y ago
        I would jump with joy if sqlite3 was rewritten in Haskell, OCaml or Rust. They can bring so much to the table in terms of safety and less development surprises.
  - jrockway 6y ago
    I am not really talking about the present day, though I agree with the other comments that a lot of modern features help. Think back to the era of Lisp machines. Memory safety, macros, OO... all in the 80s! We ignored the lessons and paid the price. People, to this day, still look at you weird when you say "I think you could write a game in a garbage collected language" and don't bat an eye when you say "C is dangerous, but I was very careful." I think what killed us is that computers are expensive (and performance directly translates to the number of computers you need to buy) and security holes are free. Of course you're going to optimize for speed; optimizing for safety can save you at most zero dollars. That's just engineering.
- dathinab 6y ago
  Often times it's more about compatibility with existing libraries or programmers experience then about speed. I often feel that many very experienced C++ devs have fallen into one of tree fallacies: The sunken (learning) cost fallacy (I include sentimental attachment here). The speed fallacy. And the being totally hypnotised/fascinated by C++-complexity fallacy (I include the you can turn C++ into whatever you like fallacy in this one).
GlitchMr 6y ago
"Program testing can be used to show the presence of bugs, but never to show their absence!" - Edsger W. Dijkstra
jonnypotty 6y ago
Someone talking sense here
umvi 6y ago
I'm not convinced. If lockpicking and other ancient hobbies are anything to go on, it doesn't matter how many redesigns you go through; people will just create new specialized/innovative tools to break/attack the most popular ones.
- Quekid5 6y ago
  Locks are physical devices and so are susceptible to all manner of wonderful and surprising physical attacks. Programming languages can artificially limit the attack surface. (Up to hardware exploits which can subvert the processor itself.)
  - c22 6y ago
    I don't understand this reasoning at all. Locks attempt to artificially limit the (physical) attack surface as well. This could, in fact, be a reasonable definition of a lock. So people come up with wonderful and surprising configurations of matter that cause these artificial limitations to fail providing direct access to the lock's root mechanism (via unanticipated route). This is analogous to virtual attacks on information systems which are hardened against familiar routes of ingress and vulnerable to those which are wonderful and surprising.
    - anyfoo 6y ago
      You can apply formal methods to code that you cannot in physical reality. If I show you the equation “x == y”, you won’t be able to pick 7 and 8 to make the equation true. If I give you a mechanical device that works with beads to answer the same question, you might make it work. Of course computers are eventually physical reality, too, and things like rowhammer show that you don’t even need traditional “bugs” to escape your mathematical utopia. But all the bugs talked about here are entirely the fault of the software.
      - vntok 6y ago
        Well one could try to change the meaning of "==" to make the equation true. Think about comparator overloading in supported languages where the x and/or y variables are actually objects, for example.
txutxu 6y ago
Indeed. But my first thought is: how many programs am I using right now on my laptop, that don't have such test coverage? and... how much (probably) undiscovered holes will they have? That without count, that we're living in the times of the hardware related bugs.
Quekid5 6y ago
100% code coverage explores an absolutely miniscule portion of the state space of any given program. This is why formal methods are a thing.
- dathinab 6y ago
  Yes especially for something fairly complex like an sql engine with views and full text search. Through then it also seems that many of the newer bugs sl seem to be around more advanced features which sometimes can be disabled on compiler time. (newer=after they integrated fuzzing into their tested) I wonder if it makes sense for Oses to ship two versions of sqlite one for the small local "trusted" database case and one for the sqlite as file format case which had many features disabled, only allowing the core subset of sqlite. Through if you provide some "evergreen" software you can anyway just include your own version of sqlite. Potentially statically linked in.
- juskrey 6y ago
  Formal methods have formal assumptions.
  - Quekid5 6y ago
    Yes? A huge portion of what a database does is amenable to formal methods. You can even come up with a reasonable rudimentary formal model of a physical machine/CPU and check against that. Sure, the model of the machine may be wrong in subtle ways, but when you discover that, you fix it and recheck your model of a database against the updated model of a physical machine. That said... don't use a language with trivially allows for out-of-bounds indexing, etc. (SQLite was started when there were really few other good options, so that's understandable.)
cztomsik 6y ago
code coverage only says what's been called not if it behaves correctly (I always thought it's obvious)
oh_sigh 6y ago
But Postgres is more complicated than sqlite, and only 10% of the issues were discovered there.
- SQLite 6y ago
  Many reasons for this: (1) Because SQLite is just a function call whereas PostgreSQL is a round-trip message to a separate server process, MRigger was able to run many more test cases per second on SQLite. (2) We fixed bugs faster in SQLite, allowing MRigger to continue testing SQLite sooner. (3) SQLite has much stronger backwards compatibility guarantees than PostgreSQL. We have to continue to support design errors made decades ago, whereas PostgreSQL gets to walk away from their poor design choices with each major release. For this reason, SQLite is rather more complicated than you might imagine. (4) Many of the bugs found by MRigger had to do with the innovative (and controversial) decision by SQLite to use flexible typing rather than strict, rigid typing. SQLite allows you to put text into an INT column, for example. PostgreSQL has a more traditional design that simply does not allow that kind of thing, and hence many of the bugs found by MRigger are simply not applicable to PostgreSQL. (5) The PostgreSQL developers are very clever people and write some of the best software around. When we were developing the cross-DBMS "sqllogictest" test suite for SQLite (https://www.sqlite.org/sqllogictest/doc/trunk/about.wiki https://www.sqlite.org/sqllogictest/doc/trunk/about.wiki) we were able to crash every DBMS we tried it on, except for PostgreSQL. To this day, when somebody has questions about whether or not the behavior of SQLite is correct, our reflexive reply is "What Does PostgreSQL Do?"
  - anarazel 6y ago
    > (1) Because SQLite is just a function call whereas PostgreSQL is a round-trip message to a separate server process, MRigger was able to run many more test cases per second on SQLite. Yea, that made it harder in the past for other test tooling too. IIRC Greg Stark fuzzed our regex library and had to fight against the more complicated interaction due to client / server to make that work. Ended up finding quite a few things... > (3) SQLite has much stronger backwards compatibility guarantees than PostgreSQL. We have to continue to support design errors made decades ago, whereas PostgreSQL gets to walk away from their poor design choices with each major release. For this reason, SQLite is rather more complicated than you might imagine. FWIW, we (pg devs) are pretty hesitant to break backward compat. Sure, each release has a few things, but it's usually pretty corner case-y stuff. Check e.g. the list for the upcoming v13: https://www.postgresql.org/docs/13/release-13.html https://www.postgresql.org/docs/13/release-13.html There's a lot of significant design errors we're continuing to support just because it'd be too painful to break compat.
centimeter 6y ago
Everyone who has been evangelizing strongly typed safe-by-construction languages (or other lightweight formal methods) has been saying this for like 20 years. If you have a memory corruption bug in your application in 2020 it is 110% your fault for making that possible.
rurban 6y ago
It's not surprising. A hack is still a hack, even you apply industry best practices in testing. There are two major security entry points, and none of them were closed since. This is the paper describing both. https://research.checkpoint.com/2019/select-code_execution-from-using-sqlite/ https://research.checkpoint.com/2019/select-code_execution-f...
badrabbit 6y ago
Maybe having a way to architect complexity in a way that preserves the author's intent for input data restriction is one way? Can code be built such that a sql query input could be declared such that it can only be processed in a control flow that ends up interacting with data on disk and return output? I don't mean things like control flow guard that precompute control flow, but an input oriented control flow whitelist enforced by the processor. Programming languages would declare input and explicitly declare what functions can execute as a result of or against that input. So, ideally, each input declaration would have a precomputed control flow graph, the processor will need to register memory as "input" (like NX/DEP) and the program will need to load the control flow graph with an interrupt that causes the processor to track operation resulting from control flow that interacted with the input in memory that is not accessible to the OS. The technology to do this and make it practical exists today but it did't at the advent of modern computing.
- deleted 6y ago
  [deleted]

by jiofih 6y ago

jrockway 6y ago

People have rethought computers from the ground up. The C++ version was slightly faster in a benchmark, though, so their thought was ignored.

otabdeveloper4 6y ago
Yeah, I'm sure switching to a more fashionable programming language will automatically fix all bugs and security issues. (sarcasm)
- mrmonkeyman 6y ago
  Memory leaks are not bugs, they are a fundamental design error.
- pdimitar 6y ago
  Every little bit helps IMO. Rust seems like it eliminates class of bugs (and so do Haskell and OCaml), the JVM looks like it could prevent another subset of them, and I am sure there are other examples. Not going to bash anyone for using C -- sqlite's team has their priorities and values clearly stated (performance and discipline) -- but it's probably time for all of us to admit that not all recent tech innovation is about fads. Some of it is actually genuinely useful and helps with age-old problems (though sadly, none of it addresses all of them).
- anyfoo 6y ago
  All of them? No. But will a modern language, where many more properties are mathematically proven through the type system, massively improve the situation? Yes. If you don’t believe me, do the converse and write your next big project completely in assembly (which is effectively untyped), and see what happens.
  - saagarjha 6y ago
    Removed undefined behavior from your code with this one weird trick!
  - dathinab 6y ago
    Through only if has high usability. You currently can bend C++ into ways to have such a type system. The usability this introduced through additional complexity is just very very bad. So no one does it because bad usability means bad productivity and getting a project done with bugs is often better then getting it not done at all (sure there are exceptions!).
    - anyfoo 6y ago
      That's a good point, and I think you've hit one of the main issues why we're still stuck with old, unsafe languages. There is the saying that once you got a Haskell program to compile, it usually just works, and I personally found it to be true a lot. But getting it through the compiler can indeed be much more of a journey than in, say, C. And I realize that the work you have to put in to just even being able to run something can be discouraging, maybe going against a natural (or maybe just common) affinity towards tight, iterative "change-compile-try" approaches. Still, in cases where it really matters, i.e. system software or common, but often mission-critical software like sqlite, maybe it's worth taking the jump?
      - pdimitar 6y ago
        I would jump with joy if sqlite3 was rewritten in Haskell, OCaml or Rust. They can bring so much to the table in terms of safety and less development surprises.
- jrockway 6y ago
  I am not really talking about the present day, though I agree with the other comments that a lot of modern features help. Think back to the era of Lisp machines. Memory safety, macros, OO... all in the 80s! We ignored the lessons and paid the price. People, to this day, still look at you weird when you say "I think you could write a game in a garbage collected language" and don't bat an eye when you say "C is dangerous, but I was very careful." I think what killed us is that computers are expensive (and performance directly translates to the number of computers you need to buy) and security holes are free. Of course you're going to optimize for speed; optimizing for safety can save you at most zero dollars. That's just engineering.
dathinab 6y ago
Often times it's more about compatibility with existing libraries or programmers experience then about speed. I often feel that many very experienced C++ devs have fallen into one of tree fallacies: The sunken (learning) cost fallacy (I include sentimental attachment here). The speed fallacy. And the being totally hypnotised/fascinated by C++-complexity fallacy (I include the you can turn C++ into whatever you like fallacy in this one).

GlitchMr 6y ago

"Program testing can be used to show the presence of bugs, but never to show their absence!" - Edsger W. Dijkstra

jonnypotty 6y ago

Someone talking sense here

umvi 6y ago

I'm not convinced. If lockpicking and other ancient hobbies are anything to go on, it doesn't matter how many redesigns you go through; people will just create new specialized/innovative tools to break/attack the most popular ones.

Quekid5 6y ago
Locks are physical devices and so are susceptible to all manner of wonderful and surprising physical attacks. Programming languages can artificially limit the attack surface. (Up to hardware exploits which can subvert the processor itself.)
- c22 6y ago
  I don't understand this reasoning at all. Locks attempt to artificially limit the (physical) attack surface as well. This could, in fact, be a reasonable definition of a lock. So people come up with wonderful and surprising configurations of matter that cause these artificial limitations to fail providing direct access to the lock's root mechanism (via unanticipated route). This is analogous to virtual attacks on information systems which are hardened against familiar routes of ingress and vulnerable to those which are wonderful and surprising.
  - anyfoo 6y ago
    You can apply formal methods to code that you cannot in physical reality. If I show you the equation “x == y”, you won’t be able to pick 7 and 8 to make the equation true. If I give you a mechanical device that works with beads to answer the same question, you might make it work. Of course computers are eventually physical reality, too, and things like rowhammer show that you don’t even need traditional “bugs” to escape your mathematical utopia. But all the bugs talked about here are entirely the fault of the software.
    - vntok 6y ago
      Well one could try to change the meaning of "==" to make the equation true. Think about comparator overloading in supported languages where the x and/or y variables are actually objects, for example.

txutxu 6y ago

Indeed. But my first thought is: how many programs am I using right now on my laptop, that don't have such test coverage? and... how much (probably) undiscovered holes will they have? That without count, that we're living in the times of the hardware related bugs.

Quekid5 6y ago

100% code coverage explores an absolutely miniscule portion of the state space of any given program. This is why formal methods are a thing.

dathinab 6y ago
Yes especially for something fairly complex like an sql engine with views and full text search. Through then it also seems that many of the newer bugs sl seem to be around more advanced features which sometimes can be disabled on compiler time. (newer=after they integrated fuzzing into their tested) I wonder if it makes sense for Oses to ship two versions of sqlite one for the small local "trusted" database case and one for the sqlite as file format case which had many features disabled, only allowing the core subset of sqlite. Through if you provide some "evergreen" software you can anyway just include your own version of sqlite. Potentially statically linked in.
juskrey 6y ago
Formal methods have formal assumptions.
- Quekid5 6y ago
  Yes? A huge portion of what a database does is amenable to formal methods. You can even come up with a reasonable rudimentary formal model of a physical machine/CPU and check against that. Sure, the model of the machine may be wrong in subtle ways, but when you discover that, you fix it and recheck your model of a database against the updated model of a physical machine. That said... don't use a language with trivially allows for out-of-bounds indexing, etc. (SQLite was started when there were really few other good options, so that's understandable.)

cztomsik 6y ago

code coverage only says what's been called not if it behaves correctly (I always thought it's obvious)

oh_sigh 6y ago

But Postgres is more complicated than sqlite, and only 10% of the issues were discovered there.

SQLite 6y ago
Many reasons for this: (1) Because SQLite is just a function call whereas PostgreSQL is a round-trip message to a separate server process, MRigger was able to run many more test cases per second on SQLite. (2) We fixed bugs faster in SQLite, allowing MRigger to continue testing SQLite sooner. (3) SQLite has much stronger backwards compatibility guarantees than PostgreSQL. We have to continue to support design errors made decades ago, whereas PostgreSQL gets to walk away from their poor design choices with each major release. For this reason, SQLite is rather more complicated than you might imagine. (4) Many of the bugs found by MRigger had to do with the innovative (and controversial) decision by SQLite to use flexible typing rather than strict, rigid typing. SQLite allows you to put text into an INT column, for example. PostgreSQL has a more traditional design that simply does not allow that kind of thing, and hence many of the bugs found by MRigger are simply not applicable to PostgreSQL. (5) The PostgreSQL developers are very clever people and write some of the best software around. When we were developing the cross-DBMS "sqllogictest" test suite for SQLite (https://www.sqlite.org/sqllogictest/doc/trunk/about.wiki https://www.sqlite.org/sqllogictest/doc/trunk/about.wiki) we were able to crash every DBMS we tried it on, except for PostgreSQL. To this day, when somebody has questions about whether or not the behavior of SQLite is correct, our reflexive reply is "What Does PostgreSQL Do?"
- anarazel 6y ago
  > (1) Because SQLite is just a function call whereas PostgreSQL is a round-trip message to a separate server process, MRigger was able to run many more test cases per second on SQLite. Yea, that made it harder in the past for other test tooling too. IIRC Greg Stark fuzzed our regex library and had to fight against the more complicated interaction due to client / server to make that work. Ended up finding quite a few things... > (3) SQLite has much stronger backwards compatibility guarantees than PostgreSQL. We have to continue to support design errors made decades ago, whereas PostgreSQL gets to walk away from their poor design choices with each major release. For this reason, SQLite is rather more complicated than you might imagine. FWIW, we (pg devs) are pretty hesitant to break backward compat. Sure, each release has a few things, but it's usually pretty corner case-y stuff. Check e.g. the list for the upcoming v13: https://www.postgresql.org/docs/13/release-13.html https://www.postgresql.org/docs/13/release-13.html There's a lot of significant design errors we're continuing to support just because it'd be too painful to break compat.

centimeter 6y ago

Everyone who has been evangelizing strongly typed safe-by-construction languages (or other lightweight formal methods) has been saying this for like 20 years. If you have a memory corruption bug in your application in 2020 it is 110% your fault for making that possible.

rurban 6y ago

It's not surprising. A hack is still a hack, even you apply industry best practices in testing. There are two major security entry points, and none of them were closed since. This is the paper describing both. https://research.checkpoint.com/2019/select-code_execution-from-using-sqlite/ https://research.checkpoint.com/2019/select-code_execution-f...

badrabbit 6y ago

Maybe having a way to architect complexity in a way that preserves the author's intent for input data restriction is one way? Can code be built such that a sql query input could be declared such that it can only be processed in a control flow that ends up interacting with data on disk and return output? I don't mean things like control flow guard that precompute control flow, but an input oriented control flow whitelist enforced by the processor. Programming languages would declare input and explicitly declare what functions can execute as a result of or against that input. So, ideally, each input declaration would have a precomputed control flow graph, the processor will need to register memory as "input" (like NX/DEP) and the program will need to load the control flow graph with an interrupt that causes the processor to track operation resulting from control flow that interacted with the input in memory that is not accessible to the OS. The technology to do this and make it practical exists today but it did't at the advent of modern computing.

deleted 6y ago
[deleted]