Possible UB reported by UBSan

[nsubiron]

Not sure if the project is still maintained, but I thought this might be interesting. I happened to run it under sanitizers and UBSan reports undefined behavior when running the tests for long strings.

third-party/levenshtein-sse/levenshtein-sse.hpp:367:67: runtime error: addition of unsigned offset to 0x555555e9b260 overflowed to 0x555555e9b254

Breakpoint 1, 0x00005555555ab1b0 in __ubsan::ScopedReport::~ScopedReport() ()
(gdb) bt
#0  0x00005555555ab1b0 in __ubsan::ScopedReport::~ScopedReport() ()
#1  0x00005555555af9cb in handlePointerOverflowImpl(__ubsan::PointerOverflowData*, unsigned long, unsigned long, __ubsan::ReportOptions) ()
#2  0x00005555555afa1a in __ubsan_handle_pointer_overflow_abort ()
#3  0x00005555555c03bb in levenshteinSSE::LevenshteinIterationSIMD<char>::performSSE (a=0x555555e9b1b0 "A somewhat longer string", b=0x555555e9b1e0 "Here is a maybe even longer string!", i=@0x7fffffffcc38: 16, 
    j=1, bLen=35, diag=0x555555e9b260, diag2=0x555555e9b350) at third-party/levenshtein-sse/levenshtein-sse.hpp:367
#4  0x00005555555bc9cb in levenshteinSSE::LevenshteinIterationSIMD<char>::performSIMD (a=0x555555e9b1b0 "A somewhat longer string", b=0x555555e9b1e0 "Here is a maybe even longer string!", 
    i=@0x7fffffffcc38: 16, j=1, bLen=35, diag=0x555555e9b260, diag2=0x555555e9b350) at third-party/levenshtein-sse/levenshtein-sse.hpp:266
#5  0x00005555555b9d06 in levenshteinSSE::LevenshteinIterationSIMDWrap<levenshteinSSE::AlignmentAllocator<unsigned int, 16ul>, levenshteinSSE::AlignmentAllocator<unsigned int, 16ul>, char>::perform (
    a=0x555555e9b1b0 "A somewhat longer string", b=0x555555e9b1e0 "Here is a maybe even longer string!", i=@0x7fffffffcc38: 16, j=1, bLen=35, diag=..., diag2=...)
    at third-party/levenshtein-sse/levenshtein-sse.hpp:717
#6  0x00005555555b9218 in levenshteinSSE::levenshteinDiagonal<unsigned int, char const*, char const*> (a=0x555555e9b1b0 "A somewhat longer string", aEnd=0x555555e9b1c8 "", 
    b=0x555555e9b1e0 "Here is a maybe even longer string!", bEnd=0x555555e9b203 "") at third-party/levenshtein-sse/levenshtein-sse.hpp:775
#7  0x00005555555b8cef in levenshteinSSE::levenshtein<char const*, char const*> (a=0x555555e9b1b0 "A somewhat longer string", aEnd=0x555555e9b1c8 "", b=0x555555e9b1e0 "Here is a maybe even longer string!", 
    bEnd=0x555555e9b203 "") at third-party/levenshtein-sse/levenshtein-sse.hpp:860
#8  0x00005555555b8755 in levenshteinSSE::levenshtein<char const*, char const*> (a=0x555555e9b1b0 "A somewhat longer string", aEnd=0x555555e9b1c8 "", b=0x555555e9b1e0 "Here is a maybe even longer string!", 
    bEnd=0x555555e9b203 "") at third-party/levenshtein-sse/levenshtein-sse.hpp:944
#9  0x00005555555b870c in levenshteinSSE::LevenshteinContainer<true>::calc<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > (a=..., b=...) at third-party/levenshtein-sse/levenshtein-sse.hpp:927
#10 0x00005555555b5535 in levenshteinSSE::levenshtein<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > (a=..., b=...) at third-party/levenshtein-sse/levenshtein-sse.hpp:951
#11 0x00005555555b2b09 in levenshteinStringExpect<char> (a=..., b=..., expected=17) at third-party/levenshtein-sse/test/test.cpp:18
#12 0x00005555555b0ce9 in main () at third-party/levenshtein-sse/test/test.cpp:64

(using llvm-10 toolchain on linux, I haven't tested any other compilers)

[addaleax]

Thanks! I’ll take a look, although I can’t promise when I’ll get to it :) My guess is that UBSan is halfway right here, but that this isn’t UB in the sense that it would crash a real-world program because the access wouldn’t cross a page boundary