Skip to content

Avoid tview buffer overflow for positions with ≥14 digits#2032

Merged
jkbonfield merged 1 commit into
samtools:developfrom
jmarshall:tview/big-pos
Apr 18, 2024
Merged

Avoid tview buffer overflow for positions with ≥14 digits#2032
jkbonfield merged 1 commit into
samtools:developfrom
jmarshall:tview/big-pos

Conversation

@jmarshall

@jmarshall jmarshall commented Apr 17, 2024

Copy link
Copy Markdown
Member

As reported by @jmunoz94 in bioconda/bioconda-recipes#47137, the following crashes on some platforms, e.g., Linux:

$ samtools tview -dT   -p 17:99999999999999999999 test/mpileup/mpileup.1.bam test/mpileup/mpileup.ref.fa
malloc(): invalid next size (unsorted)
Aborted

$ samtools tview -dT -p chr1:99999999999999999999 wgEncodeUwRepliSeqBg02esG1bAlnRep1.bam GRCh38.fa
malloc(): corrupted top size
Aborted

(I happened to test this with wgEncodeUwRepliSeqBg02esG1bAlnRep1.bam lying around from previously looking into #1884. This particular BAM file demonstrates some additional problems as described below.)

Using AddressSanitizer this can be quickly tracked down to a buffer overflow within bam_tview.c due to the very large position. This buffer's size was not revised when the 64-bit hts_pos_t was introduced in #1117. This PR rewrites it using faidx_fetch_seq64() instead to avoid needing to build region strings at all.

Testing this further with fewer 9s I noticed some additional problems:

$ samtools tview -d T -p chr1:999999 wgEncodeUwRepliSeqBg02esG1bAlnRep1.bam GRCh38-chr1.fa
  1000001   1000011   1000021   1000031   1000041   1000051   1000061           
GGGTGGAGCGCGCCGCCACGGACCACGGGCGNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
.....C.CA..CT.A..CA...AAG.ACCT.                                                 
.T.G.C.CA..CT.A..CA...AAG.ACCT.     

Notice that the reference line reverts to NNNNNN at positions past the reads. This turns out to be a buglet that has existed since 67392b8 in 2009! I've also fixed this in this commit: Fix tv->ref guard (compare the similar code in tv_pl_func()) so that areas with no reads show the reference rather than ...NNNNNN...

Additionally with this data file samtools goes into an infinite(?) loop when given two fewer 9s than in the original report:

$ samtools tview -d T -p chr1:999999999999999999 wgEncodeUwRepliSeqBg02esG1bAlnRep1.bam GRCh38-chr1.fa
[runs for a long time]

This can be traced to the do … while loop in hts_itr_query(), which loops perhaps forever through negative bin numbers. Possibly this code should check for a beg value massively beyond the maximum position covered by the index's bins and sidestep most of its processing. (I haven't addressed that in this PR and can raise it as an HTSlib issue if you wish.)

Finally these positions specified on the command line are well beyond 263 so are ingested as unrelated values within the range of hts_pos_t (or even negative) because hts_parse_decimal() does no overflow checking.

Looking back at PR samtools/htslib#171 there's surprisingly little discussion and no mention of overflow handling. It didn't occur to me that people would specify positions unrelated to any reality-based meaningful chromosome positions, so it didn't occur to me that people might specify numbers of such magnitude, beyond 263. This could be left as is (garbage in, garbage out! Or alternatively: Doctor, it hurts when I do this…) on the basis that such input deserves what it gets, or overflow detection could be added to hts_parse_decimal() and reported in some way.

This buffer size was not revised when the 64-bit hts_pos_t was introduced.
Rewrite using faidx_fetch_seq64() instead to avoid needing to build region
strings at all. (Adjust p_end_i because it is sadly 0-based INclusive.)

Also fix tv->ref guard (compare the similar code in tv_pl_func()) so that
areas with no reads show the reference rather than ...NNNNNNNN...
@jkbonfield

jkbonfield commented Apr 18, 2024

Copy link
Copy Markdown
Contributor

Good catch - thanks.

This can be traced to the do … while loop in hts_itr_query(), which loops perhaps forever through negative bin numbers. Possibly this code should check for a beg value massively beyond the maximum position covered by the index's bins and sidestep most of its processing. (I haven't addressed that in this PR and can raise it as an HTSlib issue if you wish.)

It's probably worth fixing as it's another potential denial of service to web servers and the like, which could happen with anything doing bin lookups.

I noted this hangs

samtools tview -dT   -p 17:316659272122369 test/mpileup/mpileup.1.bam test/mpileup/mpileup.ref.fa

While ...68 does not.

I assume this is where it goes negative, but the complexities of the bin computation means it's an unexpectedly odd number (11ffffb6e0000 in hex is the last valid value).

Edit: I note this is approx 2^48, so well within the valid range of hts_pos. I'm aware it's likely than nlvls will change for larger chromosomes, but I wonder if it could be coaxed to trigger this bug purely from existing SAM files and the auto-computation of bins. I did try and fail, so we're probably fine.

@jkbonfield jkbonfield merged commit 2f40f36 into samtools:develop Apr 18, 2024
@jmarshall jmarshall deleted the tview/big-pos branch April 18, 2024 19:55
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants