Re: Buffer overflow in drivers/usb/host/ehci-sched.c?

[Alan Stern <stern@rowland.harvard.edu>]

On Sun, Apr 03, 2022 at 12:12:48AM +0300, Sergei Shtylyov wrote:
> Hello!
> 
>    The following function in the EHCI scheduling code causes the SVACE static analyzer to
> report possible buffer overflow (see the last assignment below), e.g.:
> 
> Buffer 'ehci->bandwidth' of size 64 accessed at ehci-sched.c:240 can overflow, since its
> index 'i + j' can have value 66 that is out of range, as indicated by preceding conditional
> expression at ehci-sched.c:240.

Not sure what you mean.  In my copy of the file, line 240 is the assignment.  
There is a conditional in line 239 and in line 238 (the "for" condition), 
but I don't see how either one indicates that i+j could be as large as 66.

>    I tried hard to analyze this code but couldn't quite figure out whether an overflow could
> actually happen... Maybe Alan (or Greg?) could please help me out?

All right.  Hold on to your hat...

> static void reserve_release_intr_bandwidth(struct ehci_hcd *ehci,
> 		struct ehci_qh *qh, int sign)
> {
> 	unsigned		start_uf;
> 	unsigned		i, j, m;
> 	int			usecs = qh->ps.usecs;
> 	int			c_usecs = qh->ps.c_usecs;
> 	int			tt_usecs = qh->ps.tt_usecs;
> 	struct ehci_tt		*tt;
> 
> 	if (qh->ps.phase == NO_FRAME)	/* Bandwidth wasn't reserved */
> 		return;
> 	start_uf = qh->ps.bw_phase << 3;

This guarantees that start_uf is a multiple of 8.

> 	bandwidth_dbg(ehci, sign, "intr", &qh->ps);
> 
> 	if (sign < 0) {		/* Release bandwidth */
> 		usecs = -usecs;
> 		c_usecs = -c_usecs;
> 		tt_usecs = -tt_usecs;
> 	}
> 
> 	/* Entire transaction (high speed) or start-split (full/low speed) */
> 	for (i = start_uf + qh->ps.phase_uf; i < EHCI_BANDWIDTH_SIZE;
> 			i += qh->ps.bw_uperiod)
> 		ehci->bandwidth[i] += usecs;
> 
> 	/* Complete-split (full/low speed) */
> 	if (qh->ps.c_usecs) {

The fact that c_usecs is nonzero guarantees that we are dealing with a 
full/low-speed endpoint.  High-speed transfers don't use split 
transactions, so they don't reserve any bandwidth for complete-splits.

> 		/* NOTE: adjustments needed for FSTN */
> 		for (i = start_uf; i < EHCI_BANDWIDTH_SIZE;
> 				i += qh->ps.bw_uperiod) {

It takes a little checking to make sure, but in fact bw_uperiod is always a 
multiple of 8 for full/low-speed endpoints.  (Such endpoints don't make use 
of microframes; everything is in multiples of frames, i.e., multiples of 8 
microframes.)

Therefore i is always a multiple of 8 between 0 and 56 (inclusive), since 
EHCI_BANDWIDTH_SIZE is 64.

> 			for ((j = 2, m = 1 << (j+8)); j < 8; (++j, m <<= 1)) {

We always have 2 <= j < 8.

> 				if (qh->ps.cs_mask & m)
> 					ehci->bandwidth[i+j] += c_usecs;

Therefore 2 <= i+j < 56+8 = 64.

> 			}
> 		}
> 	}
> [...]
> 
>    There shouldn't be a buffer overflow iff qh->ps.bw_uperiod is a 
>    multiple of 8, right?

Correct; see above.  To probe that qh->ps.bw_uperiod is always a multiple of 
8, search the driver for assignments to qh->ps.bw_uperiod.  (The only such 
assignments occur in ehci-q.c:qh_make() -- the assignments in ehci-sched.c 
are all to stream->ps.bw_uperiod, and a stream is different from a qh.)  The
first assigment is for high-speed endpoints and the second is for 
full/low-speed endpoints.  That second assignment does:

			qh->ps.bw_uperiod = qh->ps.bw_period << 3;

which is always a multiple of 8.

Alan Stern