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

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

On Sun, Apr 03, 2022 at 08:22:44PM +0300, Sergei Shtylyov wrote:
> On 4/3/22 6:17 PM, Alan Stern wrote:
> 
> >>    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.
> 
>    What SVACE means, in this case. :-)
> 
> >  In my copy of the file, line 240 is the assignment.
> 
>    For SVACE as well. This is not a full report -- some details did follow but I failed
> to copy/paste them...
> 
> > 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.
> 
>    SVACE doesn't know what qh->ps.bw_uperiod could be...
> 
> >>    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.
> 
>    I figured. :-)
> 
> >> 	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.
> 
>    Ah! That's what I missed...
> 
> > High-speed transfers don't use split 
> > transactions, so they don't reserve any bandwidth for complete-splits.
> 
>     Aha! I still lack the detailed enough knowledge of the USB 2.0 spec...
> 
> >> 		/* 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.
> 
>    Aha!
> 
> >> 			for ((j = 2, m = 1 << (j+8)); j < 8; (++j, m <<= 1)) {
> > 
> > We always have 2 <= j < 8.
> 
>    BTW, why don't we start with 0?

That's another detail from the USB 2.0 spec.  Here's how full/low-speed 
split interrupt transactions work, in brief:

	The host controller sends a Start Split packet in uframe n on the
	HS bus.

	The intervening hub carries out the interrupt transaction on the 
	FS/LS bus at some time in uframe n+1 or shortly thereafter.  The
	transaction completes at some point during uframe n+1, n+2, or n+3, 
	depending on how much data was transferred and how much other stuff 
	is happening on the FS/LS bus.

	The hub doesn't make the data it received from the device available 
	until the uframe after the FS/LS transfer completes.  So it won't 
	send data back to the host until uframe n+2, n+3, or n+4.

	Since n >= 0, there's no point scheduling a Complete Split packet
	until uframe 2 at the earliest because the data won't be ready yet.

This ignores one significant complication: If n is large enough, the hub 
might want to send the interrupt data back to the host in uframe 0 or 1 of 
the _next_ frame.  The design of the EHCI controller makes handling these 
cases unreasonably difficult -- they require special FSTN (Frame Span 
Traversal Node) data structures -- and therefore ehci-hcd doesn't implement 
them.

As a result, ehci-hcd is unable to schedule some loads on full- or low-speed 
buses that in theory could be handled: those involving relatively high 
bandwidth.  This tends to show up more with full-speed isochronous rather 
than interrupt transfers, however; things like video applications.

Alan Stern

> >> 				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() --
> 
>    Yes, seeing them (again)...
> 
> > 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.
> 
>    Yes.
> 
>    Thank you for the prompt reply! :-)
> 
> > Alan Stern
> 
> MBR, Sergey