netdev - Overflow bug in Vegas

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 9 Apr 2008 13:57:23 -0700
From:	"Lachlan Andrew" <lachlan.andrew@...il.com>
To:	Netdev <netdev@...r.kernel.org>
Subject: Overflow bug in Vegas

Greetings all,

There is an overflow bug in  net/ipv4/tcp_vegas.c  for large BDPs
(e.g. 400Mbit/s, 400ms).
The multiplication  (old_wnd * vegas->baseRTT) << V_PARAM_SHIFT
overflows a  u32.

The attached patch relative to 2.6.25-rc7 fixes that.

(No-one would ever use Vegas on a path like that, but it will affect
algorithms derived from the Vegas code.  I found the bug while testing
the Linux port of Microsoft's Compound TCP, from
<http://netlab.caltech.edu/lachlan/ctcp/>.  That patch is derived from
Angelo Castellani's which used the Vegas code.)

Cheers,
Lachlan


--- linux-2.6.25-rc7/net/ipv4/tcp_vegas.c	2008-03-27 18:25:07.000000000 -0800
+++ linux-2.6.25-rc7/net/ipv4/tcp_vegas.c-new	2008-04-09
13:14:43.000000000 -0700
@@ -229,7 +229,8 @@ static void tcp_vegas_cong_avoid(struct
 			 */
 			tcp_reno_cong_avoid(sk, ack, in_flight);
 		} else {
-			u32 rtt, target_cwnd, diff;
+			u32 rtt, diff;
+			u64 target_cwnd;

 			/* We have enough RTT samples, so, using the Vegas
 			 * algorithm, we determine if we should increase or
@@ -252,8 +253,9 @@ static void tcp_vegas_cong_avoid(struct
 			 * We keep it as a fixed point number with
 			 * V_PARAM_SHIFT bits to the right of the binary point.
 			 */
-			target_cwnd = ((old_wnd * vegas->baseRTT)
-				       << V_PARAM_SHIFT) / rtt;
+			target_cwnd = ((u64)old_wnd * vegas->baseRTT);
+			target_cwnd <<= V_PARAM_SHIFT;
+			do_div(target_cwnd, rtt);

 			/* Calculate the difference between the window we had,
 			 * and the window we would like to have. This quantity
@@ -279,7 +281,7 @@ static void tcp_vegas_cong_avoid(struct
 				 * utilization.
 				 */
 				tp->snd_cwnd = min(tp->snd_cwnd,
-						   (target_cwnd >>
+						   ((u32)target_cwnd >>
 						    V_PARAM_SHIFT)+1);

 			} else if (tp->snd_cwnd <= tp->snd_ssthresh) {

-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Ph: +1 (626) 395-8820    Fax: +1 (626) 568-3603
http://netlab.caltech.edu/lachlan

Download attachment "Vegas-patch" of type "application/octet-stream" (1235 bytes)