6 ms·

Routines that manipulate UTF-8 strings can produce unsafe results on invalid UTF-8. For example, finding the end of a string may place you into invalid memory

Routines that manipulate UTF-8 strings can produce unsafe results on invalid UTF-8. For example, finding the end of a string may place you into invalid memory if there are missing trailing bytes. To achieve safety, one option is to use routines that always assume that the data they are operating on may be invalid — but such routines are always slow, because they are essentially validating the UTF-8 data continually. Therefore, what most systems do is establish the validity of UTF-8 data as an invariant by running a sanity check once before supplying the data to unsafe-but-fast internal routines. And that's where validators like the one described in this article come in.

Joker_vD 6y ago
> finding the end of a string may place you into invalid memory if there are missing trailing bytes I struggle to imagine such a function. If its signature is "const char * utf8end(const char * s, size_t len)", then the implementation is obviously "return s + len". If the len is missing then, uh, you can't find the end unless there is a terminator character, in which case the implementation is "return s + strlen(s)". And if you mean finding the beginning of the last codepoint, then again, you simply go to the very last byte of the string and rewind back until you see a non-trailing byte (or you've run off the beginning of the string, or you've seen more than 4 bytes in which case you have an invalid string).
- zamadatix 6y ago
  > If the len is missing then, uh, you can't find the end unless there is a terminator character, in which case the implementation is "return s + strlen(s)". Sure, and if you do strlen(s) without checking if there is actually a NUL first then: > finding the end of a string may place you into invalid memory if there are missing trailing bytes. As was originally said. This doesn't mean it's impossible to make such functions but <rest of original comment>.
  - labawi 6y ago
    Function finding end of a string that breaks on invalid utf8 would be silly and is a bad example. A function that counts the number of characters/codepoints or maybe decodes utf8 -> ucs4, may wish to operate on entire codepoints instead of always checking for potential end of buffer mid-decoding. Or perhaps avoid handling of invalid codepoints at all.
    - a1369209993 6y ago
      > may wish to operate on entire codepoints instead of always checking for potential end of buffer mid-decoding That sounds like the sort of reasoning that results in compiler bugs like: thing_t* nextp=p+1; // other declarations for this function if(!p) abort_thing("null pointer"); // optimised out /* CVE-20XX-#####: user-space code can compromise kernel $THING if it mmap()s $STUFF at address zero */
    - naniwaduni 6y ago
      > A function that counts the number of characters/codepoints Have you ever met a use case for the number of codepoints in a unicode string? (One that didn't involve the moral equivalent of "because codepoints are what Twitter counts"?)
      - rectang 6y ago
        When converting from UTF-8 to UTF-32, you need to know the number of codepoints so that you know how much memory to allocate. I feel like you're hinting at something. What is it?
        naniwaduni 6y ago
        Sure. You could also multiply by 4, wasting at worst twice as much memory as optimal on pathological input. But wait, why are you converting from utf-8 to utf-32? To iterate through? You don't need to count your codepoints for that, you can just advance through your utf-8 linearly. To index into it? You might as well index into byte offsets—sure, that makes some possible indices invalid, but so does the finite length of your buffer. And what are you doing with the codepoints anyway? utf-32 turns out to be profoundly useless for pretty much every concrete use case, because its whole appeal, that its code units map 1:1 to code points, presupposes that there's something you'd want to do with the codepoints. There isn't. Code points are practically orthogonal to all of: user-perceived characters, user-perceived graphical symbols, grapheme clusters, text width. They combine arbitrarily in ways that you cannot infer without knowing the semantics of every possible code point. There is no linguistically sensible text operation you can do at the codepoint level. They are completely useless to you. The worst part is, there are a lot of operations you can do with codepoints that seem, to cursory inspection, to do something you want. But they're wrong, all of them, necessarily so, because you're working at a level of abstraction that does not have the information needed to do just about anything correctly, but the cases that are broken are ones where none of your developers even know what the correct result should be.
  - a1369209993 6y ago
    > if you do strlen(s) without checking if there is actually a NUL first Then your problems have nothing to do with invalid UTF-8, because that issue occurs even in pure ASCII.
  - shawxe 6y ago
    > Sure, and if you do strlen(s) without checking if there is actually a NUL first then: >> finding the end of a string may place you into invalid memory if there are missing trailing bytes. You're really losing me here. Either you have a NUL terminated string or you already know the length of the string or you have no way of determining the length of the string that exists in memory that it is safe for you to access and what you have is garbage. Just because data is "valid UTF-8" doesn't make it safe to read. If the end of your string isn't marked and you don't know how long the string is already, it's over.
    - zamadatix 6y ago
      Or you reserved the string ahead of time or it was reused and not zeroed properly or there is more than 1 null in the data and copying must be done with care. Again, it's doable, or you can validate the string once (including more than "it's valid encoding") and make a ton of safe assumptions later instead of each thing that interacts with the string. UTF or not.
- rectang 6y ago
  > I struggle to imagine such a function. The following function will read invalid memory if there are missing trailing bytes: int32_t read_last_code_point(const char *s, size_t len) { s += len; // place pointer at end of string while (!HEADER_BYTE(s)) { // read backwards until header byte found s--; } return DECODE_UTF8(s); // BOOM! May read beyond string end } To fix it, you would either need to establish that the passed-in string was valid UTF-8, or you would need to add a bounds check to DECODE_UTF8, making it slower. When you write string manipulation code, you come across this sort of issue all the time. In isolation, maybe you'd want to fix this function by adding the bounds check. But since you're going to see this problem everywhere, you'll probably solve it through an initial validation pass instead.
  - svrb 6y ago
    Can you give an example of how one might make use of the last code point in a string?
    - rectang 6y ago
      I tried to simplify the example code for the sake of clarity. While I acknowledge it would be unusual to provide a library API for finding the value of the last code point specifically, most string libraries provide something like a "codePointAt" function to return the code point at a specific offset. You'll run into the same problem with DECODE_UTF8 there. int32_t code_point_at(const char *s, size_t len, size_t offset) { const char *end = s + len; while (s < end && offset > 0) { // Move forward by 1-4 bytes depending on header byte value. s += UTF8_SKIP(s); offset--; } if (s >= end) { return -1; } return DECODE_UTF8(s); // BOOM! May read beyond string end }
    - oconnor663 6y ago
      In practice, this sort of thing might be most likely to come up with a chars iterator. The natural iteration logic is something like: 1) If position == end, the iterator is done. 2) Otherwise, read the next byte to determine the number of bytes in the next character. 3) Read all the bytes of the next character, convert them to a regular 32-bit code point, and emit that. In the presence of invalid UTF-8, that iterator is broken. There needs to be an extra check in step 2.5: "Check that the number of bytes reported for the next character doesn't exceed the number of bytes remaining in the string." Iterating over the characters of a string is a pretty common thing to do, and that extra branch is not free.
- iforgotpassword 6y ago
  If you pre-validate the string because maybe you do a lot of transformations and operations with it later, then any functions processing strings become simpler. If you have the start of a 3byte character you can just read the next two bytes and don't need to check if any of the two trailing bytes is actually a nullchar instead (in case of null-terminated strings) or whether pos+2<len. Because otherwise you'd do an oob read. Also you don't need to check if the trailing bytes of your char actually start with 10xxxxxx, you can just mask off the first two bits right away.

Joker_vD 6y ago

> finding the end of a string may place you into invalid memory if there are missing trailing bytes I struggle to imagine such a function. If its signature is "const char * utf8end(const char * s, size_t len)", then the implementation is obviously "return s + len". If the len is missing then, uh, you can't find the end unless there is a terminator character, in which case the implementation is "return s + strlen(s)". And if you mean finding the beginning of the last codepoint, then again, you simply go to the very last byte of the string and rewind back until you see a non-trailing byte (or you've run off the beginning of the string, or you've seen more than 4 bytes in which case you have an invalid string).

zamadatix 6y ago
> If the len is missing then, uh, you can't find the end unless there is a terminator character, in which case the implementation is "return s + strlen(s)". Sure, and if you do strlen(s) without checking if there is actually a NUL first then: > finding the end of a string may place you into invalid memory if there are missing trailing bytes. As was originally said. This doesn't mean it's impossible to make such functions but <rest of original comment>.
- labawi 6y ago
  Function finding end of a string that breaks on invalid utf8 would be silly and is a bad example. A function that counts the number of characters/codepoints or maybe decodes utf8 -> ucs4, may wish to operate on entire codepoints instead of always checking for potential end of buffer mid-decoding. Or perhaps avoid handling of invalid codepoints at all.
  - a1369209993 6y ago
    > may wish to operate on entire codepoints instead of always checking for potential end of buffer mid-decoding That sounds like the sort of reasoning that results in compiler bugs like: thing_t* nextp=p+1; // other declarations for this function if(!p) abort_thing("null pointer"); // optimised out /* CVE-20XX-#####: user-space code can compromise kernel $THING if it mmap()s $STUFF at address zero */
  - naniwaduni 6y ago
    > A function that counts the number of characters/codepoints Have you ever met a use case for the number of codepoints in a unicode string? (One that didn't involve the moral equivalent of "because codepoints are what Twitter counts"?)
    - rectang 6y ago
      When converting from UTF-8 to UTF-32, you need to know the number of codepoints so that you know how much memory to allocate. I feel like you're hinting at something. What is it?
      - naniwaduni 6y ago
        Sure. You could also multiply by 4, wasting at worst twice as much memory as optimal on pathological input. But wait, why are you converting from utf-8 to utf-32? To iterate through? You don't need to count your codepoints for that, you can just advance through your utf-8 linearly. To index into it? You might as well index into byte offsets—sure, that makes some possible indices invalid, but so does the finite length of your buffer. And what are you doing with the codepoints anyway? utf-32 turns out to be profoundly useless for pretty much every concrete use case, because its whole appeal, that its code units map 1:1 to code points, presupposes that there's something you'd want to do with the codepoints. There isn't. Code points are practically orthogonal to all of: user-perceived characters, user-perceived graphical symbols, grapheme clusters, text width. They combine arbitrarily in ways that you cannot infer without knowing the semantics of every possible code point. There is no linguistically sensible text operation you can do at the codepoint level. They are completely useless to you. The worst part is, there are a lot of operations you can do with codepoints that seem, to cursory inspection, to do something you want. But they're wrong, all of them, necessarily so, because you're working at a level of abstraction that does not have the information needed to do just about anything correctly, but the cases that are broken are ones where none of your developers even know what the correct result should be.
- a1369209993 6y ago
  > if you do strlen(s) without checking if there is actually a NUL first Then your problems have nothing to do with invalid UTF-8, because that issue occurs even in pure ASCII.
- shawxe 6y ago
  > Sure, and if you do strlen(s) without checking if there is actually a NUL first then: >> finding the end of a string may place you into invalid memory if there are missing trailing bytes. You're really losing me here. Either you have a NUL terminated string or you already know the length of the string or you have no way of determining the length of the string that exists in memory that it is safe for you to access and what you have is garbage. Just because data is "valid UTF-8" doesn't make it safe to read. If the end of your string isn't marked and you don't know how long the string is already, it's over.
  - zamadatix 6y ago
    Or you reserved the string ahead of time or it was reused and not zeroed properly or there is more than 1 null in the data and copying must be done with care. Again, it's doable, or you can validate the string once (including more than "it's valid encoding") and make a ton of safe assumptions later instead of each thing that interacts with the string. UTF or not.
rectang 6y ago
> I struggle to imagine such a function. The following function will read invalid memory if there are missing trailing bytes: int32_t read_last_code_point(const char *s, size_t len) { s += len; // place pointer at end of string while (!HEADER_BYTE(s)) { // read backwards until header byte found s--; } return DECODE_UTF8(s); // BOOM! May read beyond string end } To fix it, you would either need to establish that the passed-in string was valid UTF-8, or you would need to add a bounds check to DECODE_UTF8, making it slower. When you write string manipulation code, you come across this sort of issue all the time. In isolation, maybe you'd want to fix this function by adding the bounds check. But since you're going to see this problem everywhere, you'll probably solve it through an initial validation pass instead.
- svrb 6y ago
  Can you give an example of how one might make use of the last code point in a string?
  - rectang 6y ago
    I tried to simplify the example code for the sake of clarity. While I acknowledge it would be unusual to provide a library API for finding the value of the last code point specifically, most string libraries provide something like a "codePointAt" function to return the code point at a specific offset. You'll run into the same problem with DECODE_UTF8 there. int32_t code_point_at(const char *s, size_t len, size_t offset) { const char *end = s + len; while (s < end && offset > 0) { // Move forward by 1-4 bytes depending on header byte value. s += UTF8_SKIP(s); offset--; } if (s >= end) { return -1; } return DECODE_UTF8(s); // BOOM! May read beyond string end }
  - oconnor663 6y ago
    In practice, this sort of thing might be most likely to come up with a chars iterator. The natural iteration logic is something like: 1) If position == end, the iterator is done. 2) Otherwise, read the next byte to determine the number of bytes in the next character. 3) Read all the bytes of the next character, convert them to a regular 32-bit code point, and emit that. In the presence of invalid UTF-8, that iterator is broken. There needs to be an extra check in step 2.5: "Check that the number of bytes reported for the next character doesn't exceed the number of bytes remaining in the string." Iterating over the characters of a string is a pretty common thing to do, and that extra branch is not free.
iforgotpassword 6y ago
If you pre-validate the string because maybe you do a lot of transformations and operations with it later, then any functions processing strings become simpler. If you have the start of a 3byte character you can just read the next two bytes and don't need to check if any of the two trailing bytes is actually a nullchar instead (in case of null-terminated strings) or whether pos+2<len. Because otherwise you'd do an oob read. Also you don't need to check if the trailing bytes of your char actually start with 10xxxxxx, you can just mask off the first two bits right away.