[sqlite] Backport icuLikeCompare patch from SQLite.

[sqlite] Backport icuLikeCompare patch from SQLite.

Original Chromium CL at https://codereview.chromium.org/1643803003

"Use safe macros for UTF-8 iteration in sqlite"

SQLite interpretation: https://www.sqlite.org/src/info/424b7aee3310b978

"Fix the ICU extension LIKE function so that it does not read past the
end of a buffer if it it passed malformed utf-8."

BUG=575205

[Scott Hess - ex-Googler, 2016-02-26 22:31:45]

shess@chromium.org changed reviewers:
+ jshin@chromium.org

[Scott Hess - ex-Googler, 2016-02-26 22:31:46]

This backports the patch SQLite uses to fix the problem.  AFAICT, it does
actually fix the bug, though obviously with a somewhat different approach than
you used.

[Scott Hess - ex-Googler, 2016-02-26 22:34:58]

Description was changed from

==========
[sqlite] Backport icuCompareFunc patch from SQLite.

Original Chromium CL at https://codereview.chromium.org/1643803003

"Use safe macros for UTF-8 iteration in sqlite"

SQLite interpretation: https://www.sqlite.org/src/info/424b7aee3310b978

"Fix the ICU extension LIKE function so that it does not read past the
end of a buffer if it it passed malformed utf-8."

BUG=575205
==========

to

==========
[sqlite] Backport icuLikeCompare patch from SQLite.

Original Chromium CL at https://codereview.chromium.org/1643803003

"Use safe macros for UTF-8 iteration in sqlite"

SQLite interpretation: https://www.sqlite.org/src/info/424b7aee3310b978

"Fix the ICU extension LIKE function so that it does not read past the
end of a buffer if it it passed malformed utf-8."

BUG=575205
==========

[Scott Hess - ex-Googler, 2016-03-02 18:40:14]

On 2016/02/26 22:31:46, Scott Hess wrote:
> This backports the patch SQLite uses to fix the problem.  AFAICT, it does
> actually fix the bug, though obviously with a somewhat different approach than
> you used.

This one too!  Again, icu.c is the only important bit.  And this one maybe
warrants a bit more inspection, because they're writing their own UTF-8
handling.  I think it's consistent with SQLite UTF-8 handling as a whole.

[jungshik at Google, 2016-03-11 21:37:08]

Sorry for the late reply. The upstream change has some issues with malformed
UTF-8.

https://codereview.chromium.org/1742693003/diff/1/third_party/sqlite/src/ext/...
File third_party/sqlite/src/ext/icu/icu.c (right):

https://codereview.chromium.org/1742693003/diff/1/third_party/sqlite/src/ext/...
third_party/sqlite/src/ext/icu/icu.c:76: 0x00, 0x01, 0x02, 0x03, 0x00, 0x01,
0x00, 0x00,
The last line for 0xf8 ~ 0xff should be dropped. It's for the original (and
obsolete) definition of UTF-8 with up to 8 byte sequences to represent code
points up to 0x7FFF FFFF.  
The current definition only allows up to 4 bytes for code points up to 0x10FFFF.

https://codereview.chromium.org/1742693003/diff/1/third_party/sqlite/src/ext/...
third_party/sqlite/src/ext/icu/icu.c:81: if( c>=0xc0 ){                         
                 \
For the same reason, |c| has to be bound by 0xf8. ( c < 0xf8) and there should
be an else-clause to return a value signifying an error in input (U+FFFD or
sth.)

https://codereview.chromium.org/1742693003/diff/1/third_party/sqlite/src/ext/...
third_party/sqlite/src/ext/icu/icu.c:83: while( (*zIn & 0xc0)==0x80 ){          
               \
Moreover, a check has to be in place for cases where # of 'trailing bytes' (
0x80 ~ 0xBF) is smaller than required. (e.g. a lead byte 0xEA is followed by
only one trailing byte).

https://codereview.chromium.org/1742693003/diff/1/third_party/sqlite/src/ext/...
third_party/sqlite/src/ext/icu/icu.c:90: if( *(zIn++)>=0xc0 ){                  
                 \
same comment as for the previous |if c>=0xc0|.

[Scott Hess - ex-Googler, 2016-03-11 23:32:33]

I think there are two levels, here.  At one level is whether the new code makes
invalid assumptions based on the input that lead to buffer overruns, which I
think does not happen.

The second level is about whether it does the "right" thing.  In the code you
originally wrote, the invalid runs would all be  converted U+FFFD.  Since the
overall comparison code does not flag these values, it will simply compare
between the strings.  As best I understand things, with the new code, invalid
code points will be returned, and, again, the invalidness will be ignored and
they'll be compared between the strings.

AFAICT, in either case strings broken in the same way will end up comparing
correctly.  In your code there are cases where strings will look equal when they
aren't.  The same is true of their code, where an invalidly decoded code point
could equal a validly decoded code point.  Is that about right?

[jungshik at Google, 2016-04-05 20:00:52]

Sorry for the terribly late reply. I drafted one and then never sent it out. 

On 2016/03/11 23:32:33, Scott Hess wrote:
> I think there are two levels, here.  At one level is whether the new code
makes
> invalid assumptions based on the input that lead to buffer overruns, which I
> think does not happen.

I agree. 

 
> The second level is about whether it does the "right" thing.  In the code you
> originally wrote, the invalid runs would all be  converted U+FFFD.  Since the
> overall comparison code does not flag these values, it will simply compare
> between the strings.  As best I understand things, with the new code, invalid
> code points will be returned, and, again, the invalidness will be ignored and
> they'll be compared between the strings.


> AFAICT, in either case strings broken in the same way will end up comparing
> correctly.  In your code there are cases where strings will look equal when
they
> aren't.  The same is true of their code, where an invalidly decoded code point
> could equal a validly decoded code point.  Is that about right?

Yeah, that's about right *if* strings are sequences of *bytes* as opposed to 
*Unicode characters*.  

The upstream change treats over-long UTF-8 sequences (invalid per UTF-8 spec) as
equivalent to their canonical representation.  As you know well, a single
character can be 
represented in multiple ways *if* overlong sequences are allowed. For instance, 
'A' (0x41) can be represented in 8(4)  different ways (1-byte ASCII, 2 ~ 8 bytes
in the old UTF-8 
and 2 ~ 4 bytes in the new but still invalid UTF-8) *if* over-long sequences are
allowed. 
This makes me worried (of a possible security issue: I don't have any concrete
case in mind, though).