[PATCH 5/8]: Add protection against invalid parameters

[PATCH 5/8]: Add protection against invalid parameters

[Gerrit Renker]

[DCCP]: Add protection against invalid parameters to TFRC routines

 1) For the forward X_calc lookup, it 
    * protects effectively against RTT=0 (this case is possible), by
      returning the maximal lookup value instead of just setting it to 1
    * reformulates the array-bounds exceeded condition: this only happens
      if p is greater than 1E6 (due to the scaling)
    * the case of negative indices can now with certainty be excluded, 
      since documentation shows that the formulas are within bounds
    * additional protection against p = 0 (would give divide-by-zero)

 2) For the reverse lookup, it warns against
    * protects against exceeding array bounds
    * now returns 0 if f(p) = 0, due to function definition
    * warns about minimal resolution error and returns the smallest table
      value instead of p=0 [this would mask congestion conditions]

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/lib/tfrc_equation.c |   33 +++++++++++++++++++--------------
 1 file changed, 19 insertions(+), 14 deletions(-)

--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -588,22 +588,19 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
 	u32 f;
 	u64 tmp1, tmp2;
 
+	/* check against invalid parameters and divide-by-zero   */
+	BUG_ON(p >  1000000);		/* p must not exceed 100%   */
+	BUG_ON(p = 0);			/* f(0) = 0, divide by zero */
+	if(R = 0) {			/* possible  divide by zero */
+		DCCP_CRIT("WARNING: RTT is 0, returning maximum X_calc.");
+		return ~0U;
+ 	}
+
 	if (p < TFRC_CALC_X_SPLIT) 		      /* 0      <= p <  0.05  */
 		index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
 	else		 			      /* 0.05   <= p <= 1.00  */
 		index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
 
-	if (index < 0)
-		/* p should be 0 unless there is a bug in my code */
-		index = 0;
-
-	if (R = 0) {
-		DCCP_WARN("RTT=0, setting to 1\n");
-		R = 1; /* RTT can't be zero or else divide by zero */
-	}
-
-	BUG_ON(index >= TFRC_CALC_X_ARRSIZE);
-
 	if (p >= TFRC_CALC_X_SPLIT)
 		f = tfrc_calc_x_lookup[index][0];
 	else
@@ -633,13 +630,21 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalu
 	int ctr = 0;
 	int small;
 
-	if (fvalue < tfrc_calc_x_lookup[0][1])
+	if (fvalue = 0)	/* f(p) = 0  whenever  p = 0 */
 		return 0;
 
+	/* Error cases. */
+	if (fvalue < tfrc_calc_x_lookup[0][1]) {
+		DCCP_WARN("fvalue %d smaller than resolution\n", fvalue);
+		return tfrc_calc_x_lookup[0][1];
+	}
+	if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0]) {
+		DCCP_WARN("fvalue %d exceeds bounds!\n", fvalue);
+		return 1000000;
+	}
+
 	if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
 		small = 1;
-	else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
-		return 1000000;
 	else
 		small = 0;
 

Re: [PATCH 5/8]: Add protection against invalid parameters

[Ian McDonald]

On 12/2/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:

> [DCCP]: Add protection against invalid parameters to TFRC routines
>
> +       BUG_ON(p >  1000000);           /* p must not exceed 100%   */
> +       BUG_ON(p = 0);                 /* f(0) = 0, divide by zero */

I know I put the original BUG_ONs in but can we change this to a
DCCP_BUG or a WARN - just to prevent the possible issues depending on
bottom half context...

Ian
-- 
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group

Re: [PATCH 5/8]: Add protection against invalid parameters

[Gerrit Renker]

Quoting Ian McDonald:
|  On 12/2/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
|  
|  > [DCCP]: Add protection against invalid parameters to TFRC routines
|  >
|  > +       BUG_ON(p >  1000000);           /* p must not exceed 100%   */
|  > +       BUG_ON(p = 0);                 /* f(0) = 0, divide by zero */
|  
|  I know I put the original BUG_ONs in but can we change this to a
|  DCCP_BUG or a WARN - just to prevent the possible issues depending on
|  bottom half context...
I thought about this too and initially both were DCCP_BUG_ON(). However,
this just delays the Kerboom! -- as I have had to learn painfully:
	* case `p > 1000000' leads to accessing illegal memory - kernel panics
	* case `p = 0' leads to division by zero

I have had one kernel Oops because of not making them DCCP_BUG_ON. The good
side of using this is safety: if this condition is met, we will know from console
output, and we will also know that there is serious trouble somewhere else.

Re: [PATCH 5/8]: Add protection against invalid parameters

[Ian McDonald]

On 12/3/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> Quoting Ian McDonald:
> I thought about this too and initially both were DCCP_BUG_ON(). However,
> this just delays the Kerboom! -- as I have had to learn painfully:
>         * case `p > 1000000' leads to accessing illegal memory - kernel panics
>         * case `p = 0' leads to division by zero
>
> I have had one kernel Oops because of not making them DCCP_BUG_ON. The good
> side of using this is safety: if this condition is met, we will know from console
> output, and we will also know that there is serious trouble somewhere else.
>
I definitely want these things to go to the console/logs. I think
DCCP_BUG_ON does do this - how to stop the divide by zero is then to
return from the function at that point so next statement can't get
executed. It doesn't ever halt the system though which is good. The
reason I say this is good as in the back of my mind I am thinking of
people looking for DoS vulnerabilities...

However BUG_ON does work and forces the code to get tidied so the
condition doesn't occur again. So whichever way I'm happy to go ahead
with it.

Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
-- 
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group

Re: [PATCH 5/8]: Add protection against invalid parameters

[Gerrit Renker]

Quoting Ian McDonald:
|  The
|  reason I say this is good as in the back of my mind I am thinking of
|  people looking for DoS vulnerabilities...
|  
|  However BUG_ON does work and forces the code to get tidied so the
|  condition doesn't occur again. So whichever way I'm happy to go ahead
|  with it.
What you are saying is very important and I suggest auditing the code against
calling this function with invalid parameters as next to-do.

I would further like to inform you and Arnaldo that I have ironed out an error
of mine in this patch (uploaded), namely the following

--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -19,7 +19,7 @@ #include "tfrc.h"
 
 #define TFRC_CALC_X_ARRSIZE 500
 #define TFRC_CALC_X_SPLIT   50000	/* 0.05 * 1000000, details below */
-#define TFRC_SMALLEST_P	    TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE
+#define TFRC_SMALLEST_P	    (TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE)
 

This is required since later on the code calls
  index = p/TFRC_SMALLEST_P -1;
which cpp expands as
 index = p/TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE -1;
       = (p/TFRC_CALC_X_SPLIT)/TFRC_CALC_X_ARRSIZE -1;
since `/' associates to the left. This can lead to an index of -1 (boom!).

This is fixed in the uploaded version.

Re: [PATCH 5/8]: Add protection against invalid parameters

[Arnaldo Carvalho de Melo]

On Sun, Dec 03, 2006 at 03:26:20PM +0000, Gerrit Renker wrote:
> Quoting Ian McDonald:
> |  The
> |  reason I say this is good as in the back of my mind I am thinking of
> |  people looking for DoS vulnerabilities...
> |  
> |  However BUG_ON does work and forces the code to get tidied so the
> |  condition doesn't occur again. So whichever way I'm happy to go ahead
> |  with it.
> What you are saying is very important and I suggest auditing the code against
> calling this function with invalid parameters as next to-do.
> 
> I would further like to inform you and Arnaldo that I have ironed out an error
> of mine in this patch (uploaded), namely the following

Heh, I was _just_ hitting enter to commit exactly this patch, so lemme
get the_whole_lot again to get this one, thanks a lot!

- Arnaldo