11 ms·
Stranger Strings: An exploitable flaw in SQLite
- sgt 4y agoImpressive work
- harryvederci 4y ago"This bug is an array-bounds overflow. The bug is only accessible when using some of the C-language APIs provided by SQLite. The bug cannot be reached using SQL nor can it be reached by providing SQLite with a corrupt database file. The bug only comes up when very long string inputs (greater than 2 billion bytes in length) are provided as arguments to a few specific C-language interfaces, and even then only under special circumstances." Source: https://www.sqlite.org/cves.html#status_of_recent_sqlite_cves https://www.sqlite.org/cves.html#status_of_recent_sqlite_cve...
- efficax 4y agoah looks like they had 32 bit assumptions that broke on 64 bit chips.
- remram 4y ago... in one internal function. It seems that the assumptions totally hold for the library as a whole.
- zoomablemind 4y agoI vagely remember that there were a few more places in SQLite codebase which could benefit from proper use of size_t type. Catching increment overflows is not that straightforward, perhaps some review specifically for such cases may help SQLite get even more robust.
- chmaynard 4y ago> The bug is only accessible when using some of the C-language APIs provided by SQLite. I assume the SQLite CLI (sqlite3) uses these APIs. Could the bug be triggered indirectly by input to sqlite3? The article doesn't appear to address this question.
- torstenvl 4y ago[EDIT: https://sqlite.org/forum/forumpost/3607259d3c https://sqlite.org/forum/forumpost/3607259d3c appears to be only one way this bug can rear its head, not the core of the bug itself]
- SQLite 4y agoThe CLI does use the relevant APIs, however I don't know of a way to reach this bug using a script input to the CLI. If there is such a path that I don't know about, it seems like it would require at least a 2GB input script.
- _the_inflator 4y agoThis, and also there is the saying: "Never trust the frontend" So in any case a string length check in the Backend should help here. Also if you get strings from a Browser Frontend, it seems unlikely you could create a payload of 2GB due to several reasons, one being string length limitations on the Browser side: https://stackoverflow.com/questions/34957890/javascript-string-size-limit-256-mb-for-me-is-it-the-same-for-all-browsers?noredirect=1&lq=1 https://stackoverflow.com/questions/34957890/javascript-stri...
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- gregors 4y agoGreat work!!! "SQLite is extensively tested with 100% branch test coverage. We discovered this vulnerability despite the tests, which raises the question: how did the tests miss it?" Tests only validate known behavior. They didn't have a test that exercised a large string. I don't know how their test suite works but I'm curious if quickcheck might have possibly found this or if the 32-bit viewpoint of the programmer at the time would have also limited possible generated values?
- RHSeeger 4y agoIndeed. Tests do not tell you code is correct. They only tell you a list of ways it is not incorrect.
- aa-jv 4y ago.. and combined with coverage they also tell you what you are yet to test properly.
- j0hnyl 4y agoIt's nice to see such comprehensive research that covers seemingly every angle a bug, its context, and history.
- three14 4y agoQuick turnaround! July 14, 2022: Reported vulnerability to the Computer Emergency Response Team (CERT) Coordination Center. July 15, 2022: CERT/CC reported vulnerability to SQLite maintainers. July 18, 2022: SQLite maintainers confirmed the vulnerability and fixed it in source code. July 21, 2022: SQLite maintainers released SQLite version 3.39.2 with fix.
- mmmpop 4y ago
- deleted 4y ago[deleted]
- veltas 4y ago> 100% branch coverage says that every line of code has been executed, but not how many times Actually, 100% branch coverage says every line has been executed but also that every branch has been both taken and not taken. So e.g. every non-constant if statement is both taken and not taken.
- XCSme 4y agoSo also all combination of branches should be tested, right? Doesn't that lead to exponential test-case growth?
- SCHiM 4y agoNo so that's exactly it. Not all combinations are tested, all branches are both taken and not taken, but not all combinations of taken/not taken are tested.
- IshKebab 4y agoIt's only possible to execute all lines if you take/don't take every if branch. They're the same.
- mort96 4y agoNo? Take this code: void foo(int arg) { int *x = malloc(sizeof(int)); if (arg) { free(x); } } If your test only ever calls `foo` with a non-zero `arg`, you have covered 100% of the lines in the function, but you never discover the memory leak bug in the case where `if` body isn't executed.
- rhdunn 4y agoAn if statement without an else can have the case where line coverage does not cover the "don't take the branch" part of branch coverage. Therefore, if not taking that branch results in a bug line coverage only will not pick up that bug. -- For example, if you initialize a value in an if statement's then branch but don't have a default value for it or an else branch to provide a default. Or even if you have a ternary operator (which has an implicit if-then-else take/don't take branch) that is usually only one line.
- p-e-w 4y agoIt's bugs like this one that lead me to believe that yes, "rewrite everything in Rust" is in fact the solution. I have the greatest respect for the quality of the SQLite codebase, which is one of the best-tested open source projects in existence, but at the end of the day, if formatting a string can lead to arbitrary code execution, it's time to question the foundations you're building on. As long as C and C++ are considered acceptable languages for writing mission critical software, these vulnerabilities will never go away. We have incredible static analysis tools and hyper-advanced fuzzers driven by genetic algorithms, and yet this continues to happen despite every precaution imaginable being taken. It's time to fix the problem at its root. Languages that are memory unsafe by default need to be phased out sooner rather than later.
- chmaynard 4y agoJust curious, what language was used to write the Rust compiler?
- _flux 4y agoLike C was used to write C and OCaml was used to write OCaml, Rust is written in Rust. Mostly, anyway, the GitHub repository seems to have also JavaScript, Python and Shell. Though to actually get binaries out of it LLVM is used, which itself is written in C++.
- xxpor 4y agoRust is written in Rust today, but it was bootstrapped in OCaml.
- nequo 4y agoOriginally OCaml, and now Rust: https://github.com/rust-lang/rust https://github.com/rust-lang/rust
- jraph 4y agoFair point, but the Rust compiler is not there at runtime. It also only needs to be written once for all the Rust programs, so assuming Rust is safer, you restrict the unsafety to the compiler (and the unsafe constructions of Rust, which are clearly marked as unsafe if memory serves). (the Rust compiler is written in Rust, but the LLVM backend it uses (and soon GCC, IIRC), is still written in C++)
- jeffbee 4y agoWhen using respectable language, is it guaranteed that these types of overflows are impossible? Suppose for example I call C++'s std::string::string(const char*) ... is it fundamentally impossible for it to fail in this way, or is it just UB if you pass it a huge string?
- LegionMammal978 4y agoThe constructor is guaranteed to either construct a valid `std::string` or throw an `std::bad_alloc` exception if the allocation fails. If there were a size limit past which calling the function is undefined, that would have to be noted in the function's documentation.
- jeffbee 4y agoHonestly I don't see anything in the chapter and verse that supports your argument. It says that the constructor has a precondition that [s, s+traits::length(s)) is a valid range, which throws just a little uncertainty over the question without resolving it. It seems easy to create a range that is not valid (consider a very large starting position s, for example).
- leni536 4y agoThat basically means that s+traits::length(s) must be defined behavior. If s is not a pointer to a 0-terminated string then the behavior of this constructor is undefined.
- LegionMammal978 4y agoThe requirements are perfectly well-defined. I'll be working with the N4868 draft of the C++20 standard [0]. First, `std::string::string(s)` is equivalent to `std::string::string(s, std::char_traits<char>::length(s))` (§21.3.3.3). Next, `std::char_traits<char>::length(s)` is equal to the smallest `size_t` value `i` such that `s[i] == 0` (§21.2.2, §21.2.4.2). From here, we yield our only preconditions for the call being valid: `s` must point to either a `char` equal to 0 or an element of an array of `char`s that is eventually followed by a 0 (§7.6.1.2, §7.6.6), and there must be no thread or signal handler concurrently modifying it (which would cause a data race, §6.9.2.2). These are necessary for each `s[i]` access in the length computation to be valid. Letting `n` be the computed length, we have our final precondition, that `[s, s + n)` is a valid range (§21.3.3.3). "Valid range" has a specific meaning in the standard (§23.3.1): > A sentinel `s` is called reachable from an iterator `i` if and only if there is a finite sequence of applications of the expression `++i` that makes `i == s`. If `s` is reachable from `i`, `[i, s)` denotes a valid range. Since `s` must point to an array of `char`s of length greater than `n`, `s + n` is clearly reachable from `s`. Therefore, `[s, s + n)` denotes a valid range, given our preconditions. The only length restriction in the standard is that the source string must be no more than `SIZE_MAX` characters long (excluding the null terminator), since otherwise `std::char_traits<char>::length(s)` would have no correct return value. [0] https://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4868.pdf https://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4868.p...
- josefx 4y agoC strings, not even once.
- marcodiego 4y agoI wonder what would be the simplest/fastest kind of test that could detect this flaw considering that SQLite is extremely well-tested. Wouldn't mutation tests catch it?
- russellbeattie 4y agoThe root of this problem seems to be the widespread availability of 64-bit CPUs. ≥ When this code was first written, most processors had 32-bit registers and 4GB of addressable memory, so allocating 1GB strings as input was impractical. Now that 64-bit processors are quite common, allocating such large strings is feasible and the vulnerable conditions are reachable. One has to wonder how much code written in the past 30 years has safety checks assuming 32-bit processors which now have vulnerabilities like this one. I'd bet quite a lot.