bug in ExtendPen (invalid memory access, reading past the end of DBSeq)

[dogarithm]

I have found a memory access violation in ExtendPen resulting in a segfault. I tried to fix this by adding a bounds-checking loop condition, which resolves the segfault. I do not understand all of urmap's code sufficiently to determine if the proposed fix is the best possible fix.

Please feel free to use the proposed fix or fix it in whatever way you deem appropriate. Thanks.

Original code:

urmap/src/extendpen.cpp

Lines 29 to 32 in 836dd6f

	for (int QPos = EndPos + 1; QPos < int(QL); ++QPos)
	{
	byte q = QSeq[QPos];
	byte t = DBSeq[QPos];

The failing code is byte t = DBSeq[QPos] which reads after the end of DBSeq.

...

Proposed fix to the loop:

for (int QPos = EndPos + 1; (QPos < int(QL)) && (QPos + DBLo < m_UFI->m_SeqDataSize); ++QPos)

Another possible fix is to add the following check before the loop:

if (QL + DBLo > m_UFI->m_SeqDataSize)
{
  return -1;
}

This bug might also explain the previously reported segfault issue.

00:32 22020Gb 8 threads
00:32 22020Gb Mapping ../181025_I600_CL100097983_L1_PL1809120059-532_1.fq
00:35 22020Gb 2.0% Mapping unpaired  181025_I600_CL100097983_L1_PL1809120059-532_1.fq=================================================================
==23064==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x7f6d52208dc1 at pc 0x555dbb18914d bp 0x7f6c998cc840 sp 0x7f6c998cc830
READ of size 1 at 0x7f6d52208dc1 thread T2
    #0 0x555dbb18914c in State1::ExtendPen(unsigned int, unsigned int, bool) /home/john/orig/urmap/src/extendpen.cpp:32
    #1 0x555dbb1a41b8 in State1::Search_Lo() /home/john/orig/urmap/src/search1m6.cpp:81
    #2 0x555dbb1a1cb7 in State1::Search(SeqInfo*) /home/john/orig/urmap/src/search1.cpp:21
    #3 0x555dbb184a8e in MapThread /home/john/orig/urmap/src/map.cpp:22
    #4 0x555dbb18552a in cmd_map() [clone ._omp_fn.0] /home/john/orig/urmap/src/map.cpp:60
    #5 0x7f739eb4d78d  (/lib/x86_64-linux-gnu/libgomp.so.1+0x1a78d)
    #6 0x7f739eafe608 in start_thread /build/glibc-eX1tMB/glibc-2.31/nptl/pthread_create.c:477
    #7 0x7f739ea23292 in __clone (/lib/x86_64-linux-gnu/libc.so.6+0x122292)

0x7f6d52208dc1 is located 0 bytes to the right of 3088287169-byte region [0x7f6c9a0d0800,0x7f6d52208dc1)
allocated by thread T0 here:
    #0 0x7f739efb3bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #1 0x555dbb19f74e in UFIndex::FromFile(_IO_FILE*) /home/john/orig/urmap/src/ufindexio.cpp:108
    #2 0x555dbb19ecbd in UFIndex::FromFile(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /home/john/orig/urmap/src/ufindexio.cpp:55
    #3 0x555dbb184e00 in cmd_map() /home/john/orig/urmap/src/map.cpp:43
    #4 0x555dbb1bd41b in main /home/john/orig/urmap/src/cmds.h:12
    #5 0x7f739e9280b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

Thread T2 created by T0 here:
    #0 0x7f739eee0805 in pthread_create (/lib/x86_64-linux-gnu/libasan.so.5+0x3a805)
    #1 0x7f739eb4ddea  (/lib/x86_64-linux-gnu/libgomp.so.1+0x1adea)
    #2 0x7f739eb458e0 in GOMP_parallel (/lib/x86_64-linux-gnu/libgomp.so.1+0x128e0)
    #3 0x7fffd646bcdf  ([stack]+0x1ecdf)
    #4 0x7fffd646be00  ([stack]+0x1ee00)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/john/orig/urmap/src/extendpen.cpp:32 in State1::ExtendPen(unsigned int, unsigned int, bool)
Shadow bytes around the buggy address:
  0x0fee2a439160: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fee2a439170: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fee2a439180: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fee2a439190: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fee2a4391a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0fee2a4391b0: 00 00 00 00 00 00 00 00[01]fa fa fa fa fa fa fa
  0x0fee2a4391c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fee2a4391d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fee2a4391e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fee2a4391f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fee2a439200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==23064==ABORTING