Live data from Hacker News

Algorithmic complexity attacks and libc qsort()

calmerthanyouare.org

41–50 of 55 posts

Re: Algorithmic complexity attacks and libc qsort()

#41
post #34
post #33

Earlier quoted context omitted.

Looks like it is fixed now: $ expr \( -2147483648 \) \* -1 2147483648 $ expr \( -2147483648 \) / -1 2147483648 $ uname -srm FreeBSD 10.0-RELEASE amd64 Or maybe it doesn't work on i386?

It's likely an i386 thing: $ echo | awk '{ print 2 ** 31 }' 2147483648 Make sure you are using /bin/expr and maybe give -9223372036854775808 a whirl too.

It now reports overflow instead of crashing, but the first case is still incorrect:

  $ which expr

  /bin/expr

  $ expr \( -9223372036854775808 \) \* -1

  -9223372036854775808

  $ expr \( -9223372036854775808 \) / -1 

  expr: overflow
Looking at the source code:

  void

  assert_times(intmax_t a, intmax_t b, intmax_t r)

  {

          /*

           * if first operand is 0, no overflow is possible,

           * else result of division test must match second operand

           */

          if (a != 0 && r / a != b)

                  errx(ERR_EXIT, "overflow");

    }


  struct val *

  op_times(struct val *a, struct val *b)

  {

          struct val *r;


          assert_to_integer(a);

          assert_to_integer(b);

          r = make_integer(a->u.i * b->u.i);

          assert_times(a->u.i, b->u.i, r->u.i);


          free_value(a);

          free_value(b);

          return (r);

  }


  void

  assert_div(intmax_t a, intmax_t b)

  {

          if (b == 0)

                  errx(ERR_EXIT, "division by zero");

          /* only INTMAX_MIN / -1 causes overflow */

          if (a == INTMAX_MIN && b == -1)

                  errx(ERR_EXIT, "overflow");

  }


  struct val *

  op_div(struct val *a, struct val *b)

  {

          struct val *r;

          assert_to_integer(a);

          assert_to_integer(b);

          /* assert based on operands only, not on result */

          assert_div(a->u.i, b->u.i);

          r = make_integer(a->u.i / b->u.i);

          free_value(a);

          free_value(b);

          return (r);

  }
Looks like the check for overflow in the multiplication case is broken since the check itself does not account for overflow. I'll try to remember to submit a patch when I get home.

Re: Algorithmic complexity attacks and libc qsort()

#46

Just in case anyone is curious, this does not effect any implementation of std::sort in C++ I am aware of. They all use introsort -- basically use quicksort until you have done some number of partitions, then switch to heapsorting the cells of the partition. This ensures fast quick-sort performance while guaranteeing O(n log n) worst case.

In Linux-land, glibc's qsort also uses introsort, and musl libc's uses smoothsort:

http://www.etalabs.net/compare_libcs.html

Re: Algorithmic complexity attacks and libc qsort()

#47
post #41
post #34

Earlier quoted context omitted.

It's likely an i386 thing: $ echo | awk '{ print 2 ** 31 }' 2147483648 Make sure you are using /bin/expr and maybe give -9223372036854775808 a whirl too.

It now reports overflow instead of crashing, but the first case is still incorrect: $ which expr /bin/expr $ expr \( -9223372036854775808 \) \* -1 -9223372036854775808 $ expr \( -9223372036854775808 \) / -1 expr: overflow Looking at the source code: void assert_times(intmax_t a, intmax_t b, intmax_t r) { /* * if first operand is 0, no overflow is possible, * else result of division test must match second operand */ i…

thanks!

Re: Algorithmic complexity attacks and libc qsort()

#49
post #16
post #10

Earlier quoted context omitted.

I've always liked mergesort for this reason. It's easier to understand and there's no wondering about complexity.

Well, sometimes you have space constraints. The O(n) extra-space required by mergesort isn't always available. But if you don't have space constraints, mergesort is a very good choice because you can easily write a highly scalable parallel version of the algorithm.

Mergesort gets pretty damn efficient, even with moderate buffer space.

Re: Algorithmic complexity attacks and libc qsort()

#50
post #9

As someone who implemented an open source quicksort ( http://www.mqseries.net/phpBB2/viewtopic.php?p=273722 ) which is used by many in production: Now this is very interesting, but could also be prevented with a random number generator (which influences the selection of the pivot element). If this would have been exploited, people would have looked into mitigating this. Edit: You can detect recursion-tree-degeneratio…

Yeah, random pivot quicksort is n log n expected case. Its pretty easy to show that it is realistically impossible to exceed n log n for large data sets. The constants are quite high, though, due to the need to generate a random number for each element.

Additionally, quicksort is just as easy to implement in parallel as mergesort and runs about as fast since it can be performed in-place.

Post reply on HN