From 3b2278aa3541c3bc2a8591a112c8aa478bc2f2b8 Mon Sep 17 00:00:00 2001 From: Lev Walkin Date: Sun, 24 Jan 2016 16:43:50 -0800 Subject: fix overflow bug comparing ranges --- .gitignore | 2 +- libasn1fix/Makefile.am | 14 +++--- libasn1fix/asn1fix_crange.c | 117 +++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 124 insertions(+), 9 deletions(-) diff --git a/.gitignore b/.gitignore index afef88c7..11fa1c16 100644 --- a/.gitignore +++ b/.gitignore @@ -66,7 +66,7 @@ doc/docsrc/*.xdv # /libasn1fix/ /libasn1fix/Makefile -/libasn1fix/check_fixer +/libasn1fix/check_* # /libasn1parser/ /libasn1parser/Makefile diff --git a/libasn1fix/Makefile.am b/libasn1fix/Makefile.am index 0b82cb70..44131d7a 100644 --- a/libasn1fix/Makefile.am +++ b/libasn1fix/Makefile.am @@ -28,14 +28,16 @@ libasn1fix_la_SOURCES = \ asn1fix_cws.c asn1fix_cws.h \ asn1fix_constraint_compat.c -check_PROGRAMS = check_fixer - check_fixer_LDADD = $(noinst_LTLIBRARIES) \ $(top_builddir)/libasn1parser/libasn1parser.la check_fixer_CPPFLAGS = -DTOP_SRCDIR=${top_srcdir} $(AM_CPPFLAGS) -check_fixer_DEPENDENCIES = $(check_fixer_LDADD) -TESTS_ENVIRONMENT= ./check_fixer -TESTS = ${top_srcdir}/tests/*.asn1 -## TESTS = ${check_PROGRAMS} # This is an alternate form of testing +check_crange_SOURCES = asn1fix_crange.c asn1fix_constraint_compat.c +check_crange_CPPFLAGS = -DUNIT_TEST $(AM_CPPFLAGS) +check_crange_LDADD = $(noinst_LTLIBRARIES) \ + $(top_builddir)/libasn1parser/libasn1parser.la + +check_PROGRAMS = check_crange check_fixer + +TESTS = ${check_PROGRAMS} diff --git a/libasn1fix/asn1fix_crange.c b/libasn1fix/asn1fix_crange.c index d76a3398..311c727c 100644 --- a/libasn1fix/asn1fix_crange.c +++ b/libasn1fix/asn1fix_crange.c @@ -158,6 +158,9 @@ _edge_value(const asn1cnst_edge_t *edge) { case ARE_MAX: strcpy(buf, "MAX"); break; case ARE_VALUE: snprintf(buf, sizeof(buf), "%" PRIdASN, edge->value); + break; + default: + assert(!"edge->type"); } return buf; } @@ -385,6 +388,19 @@ _range_overlap(const asn1cnst_range_t *ra, const asn1cnst_range_t *rb) { return 1; } + +static int _range_partial_compare(const void *pa, const void *pb) { + const asn1cnst_range_t *ra = *(const void * const *)pa; + const asn1cnst_range_t *rb = *(const void * const *)pb; + + return _edge_compare(&ra->left, &rb->left); +} + +static void _range_partial_sort_elements(asn1cnst_range_t *r) { + qsort(r->elements, r->el_count, sizeof(r->elements[0]), + _range_partial_compare); +} + /* * (MIN..20) x (10..15) = (MIN..9,10..15,16..20) */ @@ -429,7 +445,7 @@ _range_split(asn1cnst_range_t *ra, const asn1cnst_range_t *rb) { nr->left = ra->left; nr->right = rb->left; if(nr->right.type == ARE_VALUE) { - if(nr->right.value - 1 >= nr->right.value) { + if(nr->right.value == INTMAX_MIN) { /* We've hit the limit here. */ break; } @@ -449,7 +465,7 @@ _range_split(asn1cnst_range_t *ra, const asn1cnst_range_t *rb) { nr->left = rb->right; nr->right = ra->right; if(nr->left.type == ARE_VALUE) { - if(nr->left.value + 1 <= nr->left.value) { + if(nr->left.value == INTMAX_MAX) { /* We've hit the limit here. */ break; } @@ -474,6 +490,8 @@ _range_split(asn1cnst_range_t *ra, const asn1cnst_range_t *rb) { _range_insert(range, nr); + _range_partial_sort_elements(range); + return range; } @@ -1017,3 +1035,98 @@ asn1constraint_compute_PER_range(asn1p_expr_type_e expr_type, const asn1p_constr return range; } +#ifdef UNIT_TEST +int main() { + asn1cnst_range_t *ra = _range_new(); + asn1cnst_range_t *rb = _range_new(); + + fprintf(stderr, "Testing (MIN..20) x (10..15) => (MIN..9,10..15,16..20)\n"); + + /* (MIN..20) */ + ra->left.type = ARE_MIN; + ra->right.type = ARE_VALUE; ra->right.value = 20; + + /* (10..15) */ + rb->left.type = ARE_VALUE; rb->left.value = 10; + rb->right.type = ARE_VALUE; rb->right.value = 15; + + /* + * (MIN..20) x (10..15) = (MIN..9,10..15,16..20) + */ + asn1cnst_range_t *r = _range_split(ra, rb); + assert(r); + assert(r->left.type == ARE_MIN); + assert(r->right.type == ARE_MAX); + + assert(r->el_count == 3); + assert(r->elements[0]->elements == NULL); + assert(r->elements[1]->elements == NULL); + assert(r->elements[2]->elements == NULL); + + /* (MIN..9) */ + fprintf(stderr, "[0].left = %s\n", _edge_value(&r->elements[0]->left)); + fprintf(stderr, "[0].right = %s\n", _edge_value(&r->elements[0]->right)); + assert(r->elements[0]->left.type == ARE_MIN); + assert(r->elements[0]->right.type == ARE_VALUE); + assert(r->elements[0]->right.value == 9); + + /* (10..15) */ + fprintf(stderr, "[1].left = %s\n", _edge_value(&r->elements[1]->left)); + fprintf(stderr, "[1].right = %s\n", _edge_value(&r->elements[1]->right)); + assert(r->elements[1]->left.type == ARE_VALUE); + assert(r->elements[1]->left.value == 10); + assert(r->elements[1]->right.type == ARE_VALUE); + assert(r->elements[1]->right.value == 15); + + /* (16..20) */ + fprintf(stderr, "[2].left = %s\n", _edge_value(&r->elements[2]->left)); + fprintf(stderr, "[2].right = %s\n", _edge_value(&r->elements[2]->right)); + assert(r->elements[2]->left.type == ARE_VALUE); + assert(r->elements[2]->left.value == 16); + assert(r->elements[2]->right.type == ARE_VALUE); + assert(r->elements[2]->right.value == 20); + + _range_free(r); + + + + fprintf(stderr, "Testing (MIN..20) x (..15) => (..15,16..20)\n"); + + /* (MIN..20) */ + ra->left.type = ARE_MIN; + ra->right.type = ARE_VALUE; ra->right.value = 20; + + /* (..15) */ + rb->left.type = ARE_VALUE; rb->left.value = INTMAX_MIN; + rb->right.type = ARE_VALUE; rb->right.value = 15; + + r = _range_split(ra, rb); + assert(r); + assert(r->left.type == ARE_MIN); + assert(r->right.type == ARE_MAX); + + assert(r->el_count == 2); + assert(r->elements[0]->elements == NULL); + assert(r->elements[1]->elements == NULL); + + /* (..16) */ + fprintf(stderr, "[0].left = %s\n", _edge_value(&r->elements[0]->left)); + fprintf(stderr, "[0].right = %s\n", _edge_value(&r->elements[0]->right)); + assert(r->elements[0]->left.type == ARE_VALUE); + assert(r->elements[0]->left.value == INTMAX_MIN); + assert(r->elements[0]->right.type == ARE_VALUE); + assert(r->elements[0]->right.value == 15); + + /* (16..20) */ + fprintf(stderr, "[1].left = %s\n", _edge_value(&r->elements[1]->left)); + fprintf(stderr, "[1].right = %s\n", _edge_value(&r->elements[1]->right)); + assert(r->elements[1]->left.type == ARE_VALUE); + assert(r->elements[1]->left.value == 16); + assert(r->elements[1]->right.type == ARE_VALUE); + assert(r->elements[1]->right.value == 20); + + _range_free(r); + + return 0; +} +#endif -- cgit v1.2.3