[GRASS-dev] [GRASS GIS] #3564: Inconsistent results from qsort callback in g.mkfontcap

GDAL · May 21, 2018, 8:06pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
---------------------+-------------------------
Reporter: yugr | Owner: grass-dev@…
Type: defect | Status: new
Priority: normal | Milestone:
Component: Default | Version: 7.4.0
Keywords: | CPU: All
Platform: All |
---------------------+-------------------------
Hi,

qsort callback compare_fonts in g.mkfontcap may return invalid result when
arguments are swapped. Such bugs may causes inconsistent order or even
crashes in some qsort implementations
(https://bugzilla.samba.org/show_bug.cgi?id=3959).

The issue has been detected when running standard testsuite under
SortChecker? (https://github.com/yugr/sortcheck):

g.mkfontcap[15109]: qsort: comparison function is not symmetric
(comparison function 0x4023c0 (/build/grass-7.0.3/dist.x86_64-pc-linux-
gnu/bin/g.mkfontcap+0x4023c0), called from 0x4017a8
(/build/grass-7.0.3/dist.x86_64-pc-linux-gnu/bin/g.mkfontcap+0x4017a8),
cmdline is "/build/grass-7.0.3/dist.x86_64-pc-linux-gnu/bin/g.mkfontcap
-s")

Problem is in lines
     if (aa->type != bb->type)
         return (aa->type > bb->type);
which should be replaced with something like
     if (aa->type != bb->type)
         return (aa->type > bb->type) ? 1 : -1;

As a side note, many qsort callbacks in Grass are vulnerable to integer
overflows e.g. cmp_edge in ./lib/vector/neta/spanningtree.c:

return ((edge_cost_pair *) pa)->cost - ((edge_cost_pair *) pb)->cost;

or longcmp in ./raster/r.kappa/prt_mat.c:

return (*a - *b);

and many many others.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564>
GRASS GIS <https://grass.osgeo.org>

GDAL · May 21, 2018, 8:54pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------
Changes (by mmetz):

* keywords: => qsort callback
* milestone: => 7.6.0

Comment:

Replying to [ticket:3564 yugr]:
> Hi,
>
> qsort callback compare_fonts in g.mkfontcap may return invalid result
when arguments are swapped. Such bugs may causes inconsistent order or
even crashes in some qsort implementations
(https://bugzilla.samba.org/show_bug.cgi?id=3959).
>
> The issue has been detected when running standard testsuite under
SortChecker? (https://github.com/yugr/sortcheck):
>
> g.mkfontcap[15109]: qsort: comparison function is not symmetric
(comparison function 0x4023c0 (/build/grass-7.0.3/dist.x86_64-pc-linux-
gnu/bin/g.mkfontcap+0x4023c0), called from 0x4017a8
(/build/grass-7.0.3/dist.x86_64-pc-linux-gnu/bin/g.mkfontcap+0x4017a8),
cmdline is "/build/grass-7.0.3/dist.x86_64-pc-linux-gnu/bin/g.mkfontcap
-s")
>
> Problem is in lines
> if (aa->type != bb->type)
> return (aa->type > bb->type);
> which should be replaced with something like
> if (aa->type != bb->type)
> return (aa->type > bb->type) ? 1 : -1;

Fixed in trunk r72727.
>
> As a side note, many qsort callbacks in Grass are vulnerable to integer
overflows e.g. cmp_edge in ./lib/vector/neta/spanningtree.c:
>
> return ((edge_cost_pair *) pa)->cost - ((edge_cost_pair *)
pb)->cost;
>

Fixed in trunk r72728.

> or longcmp in ./raster/r.kappa/prt_mat.c:
>
> return (*a - *b);

Fixed in trunk r72729.
>
> and many many others.

If you already have a list of these many other problems, can you provide
such a list? That would be very helpful.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:1>
GRASS GIS <https://grass.osgeo.org>

GDAL · May 21, 2018, 9:26pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by yugr):

Hi Markus,

> If you already have a list of these many other problems, can you provide
such a list? That would be very helpful.

I wasn't sure you'd be interested in these potential overflows (e.g. some
may be highly unlikely due to small subtracted values) so didn't report
them in first comment.

There you go (found by manual analysis of source code):

./lib/vector/neta/spanningtree.c

   static int cmp_edge(const void *pa, const void *pb)
   {
     return ((edge_cost_pair *) pa)->cost - ((edge_cost_pair *) pb)->cost;
   }

./lib/vector/Vlib/break_lines.c

   static int cmp(const void *a, const void *b)
   {
     int ai = *(int *)a;
     int bi = *(int *)b;

return (ai - bi);
}

./raster/r.distance/edges.c

   static int cmp(const void *aa, const void *bb)
   {
     const struct CatEdgeList *a = aa, *b = bb;

return (int)(a->cat - b->cat);
}

./raster/r.kappa/prt_mat.c

   static int longcomp(const void *aa, const void *bb)
   {
     const long *a = aa;
     const long *b = bb;

return (*a - *b);
}

./raster/r.stats/stats.c

   static int node_compare(const void *pp, const void *qq)
   {
     struct Node *const *p = pp, *const *q = qq;
     register int i, x;
     register const CELL *a, *b;

     a = (*p)->values;
     b = (*q)->values;
     for (i = nfiles; --i >= 0;)
         if (x = (*a++ - *b++), x)
             return x;

return 0;
}

./raster/r.what/main.c

   static int by_row(const void *ii, const void *jj)
   {
     const struct order *i = ii, *j = jj;

return i->row - j->row;
}

./vector/v.generalize/misc.c

   static int cmp(const void *a, const void *b)
   {
     int ai = *(int *)a;
     int bi = *(int *)b;

return (ai - bi);
}

./vector/v.overlay/area_area.c

   static int cmp_int(const void *a, const void *b)
   {
     return (*(int *)a - *(int *)b);
   }

./vector/v.to.rast/support.c

   static int cmp_labels_i(const void *a, const void *b)
   {
     struct My_labels_rule *al = (struct My_labels_rule *) a;
     struct My_labels_rule *bl = (struct My_labels_rule *) b;

return (al->i - bl->i);
}

./vector/v.vect.stats/main.c

   static int cmp_area(const void *pa, const void *pb)
   {
     AREA_CAT *p1 = (AREA_CAT *) pa;
     AREA_CAT *p2 = (AREA_CAT *) pb;

return (p1->area_cat - p2->area_cat);
}

./vector/v.what.rast/search.c
./vector/v.what.rast3/search.c

   /* for qsort, order list by row */
   int by_row(const void *ii, const void *jj)
   {
     const struct order *i = ii, *j = jj;

return i->row - j->row;
}

   /* for qsort, order list by cat */
   int by_cat(const void *ii, const void *jj)
   {
     const struct order *i = ii, *j = jj;

return i->cat - j->cat;
}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:2>
GRASS GIS <https://grass.osgeo.org>

GDAL · May 22, 2018, 7:15am

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

Replying to [comment:2 yugr]:
> Hi Markus,
>
> > If you already have a list of these many other problems, can you
provide such a list? That would be very helpful.
>
> I wasn't sure you'd be interested in these potential overflows (e.g.
some may be highly unlikely due to small subtracted values) so didn't
report them in first comment.

I am interested. The comparison in g.mkfontcap was wrong, it returned 0
when it should return -1. The comparison in r.kappa was clearly dangerous
because it converted long to int. The remaining cases need to be checked
individually: if the integers to be subtracted are always positive,
integer overflow can not happen.

Thanks for the list!

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:3>
GRASS GIS <https://grass.osgeo.org>

GDAL · May 22, 2018, 2:12pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by yugr):

One more symmetry issue in ./vector/v.profile/main.c:
   static int compdist(const void *d1, const void *d2)
   {
     ...
     if (r1->distance > r2->distance)
         return 1;
     else
         return -1;
   }

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:4>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 6:38pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

In [changeset:"73135" 73135]:
{{{
#!CommitTicketReference repository="" revision="73135"
v.profile: fix qsort cmp fn (see #3564)
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:5>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 7:38pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

In [changeset:"73136" 73136]:
{{{
#!CommitTicketReference repository="" revision="73136"
r.what: fix qsort cmp fn (see #3564)
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:6>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 7:41pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

In [changeset:"73137" 73137]:
{{{
#!CommitTicketReference repository="" revision="73137"
r.stats: fix qsort cmp fn (see #3564)
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:7>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 7:43pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

In [changeset:"73138" 73138]:
{{{
#!CommitTicketReference repository="" revision="73138"
r.kappa: fix qsort cmp fn (see #3564)
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:8>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 7:44pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

In [changeset:"73139" 73139]:
{{{
#!CommitTicketReference repository="" revision="73139"
r.distance: fix qsort cmp fn (see #3564)
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:9>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 7:46pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------

Comment (by mmetz):

In [changeset:"73140" 73140]:
{{{
#!CommitTicketReference repository="" revision="73140"
Vlib: add comment to qsort cmp fn (see #3564)
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:10>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 22, 2018, 7:50pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: closed
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: fixed | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------
Changes (by mmetz):

* status: new => closed
* resolution: => fixed

Comment:

All instances of possible inconsistent results or potential buffer
overflow have been fixed.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:11>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 23, 2018, 5:42am

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: reopened
  Priority: normal | Milestone: 7.6.0
Component: Default | Version: 7.4.0
Resolution: | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------
Changes (by neteler):

* status: closed => reopened
* resolution: fixed =>

Comment:

Do(n't) we want a bulk backport? If yes, I can do that

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:12>
GRASS GIS <https://grass.osgeo.org>

GDAL · August 23, 2018, 3:16pm

#3564: Inconsistent results from qsort callback in g.mkfontcap
----------------------+----------------------------
  Reporter: yugr | Owner: grass-dev@…
      Type: defect | Status: closed
  Priority: normal | Milestone: 7.4.2
Component: Default | Version: 7.4.0
Resolution: fixed | Keywords: qsort callback
       CPU: All | Platform: All
----------------------+----------------------------
Changes (by mmetz):

* status: reopened => closed
* resolution: => fixed
* milestone: 7.6.0 => 7.4.2

Comment:

Replying to [comment:12 neteler]:
> Do(n't) we want a bulk backport? If yes, I can do that

Backported to relbr74 with r73145.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3564#comment:13>
GRASS GIS <https://grass.osgeo.org>