rb_to_array and rb_min exhibits inconsistent results in a malformed serialize input

[ChenHuajun]

As mentioned in PR #42, the roaring_buffer_reader exhibits inconsistent results, as follows:

postgres=# select rb_to_array('\x3a300000010000000000000000000000000000000000000000000000000000000000000000000000000000000008'::roaringbitmap);
 rb_to_array
-------------
 {0}
(1 row)

postgres=# select rb_min('\x3a300000010000000000000000000000000000000000000000000000000000000000000000000000000000000008'::roaringbitmap);
 rb_min
--------
  12346
(1 row)

But the input is a malformed binary, ‘{0}’ should be:

postgres=# select '{0}'::roaringbitmap;
             roaringbitmap
----------------------------------------
 \x3a3000000100000000000000100000000000
(1 row)

[ChenHuajun]

Here's the English translation of your technical text:

The correct serialized data for '{0}':

3a300000
01000000
00000000
10000000--offset
0000

The actual input data has an abnormal offset value of 0, which points to the beginning at 0x3a300000(so rb_min returns 12346) :

3a300000
01000000
00000000
00000000--offset
00000000
00000000
00000000
00000000
00000000
00000000
00000000
0008

The roaring_bitmap_portable_deserialize_safe skipped parsing the offset, thus wasn't affected by the incorrect offset:

bool ra_portable_deserialize(roaring_array_t *answer, const char *buf, const size_t maxbytes, size_t * readbytes) {
...
    if ((!hasrun) || (size >= NO_OFFSET_THRESHOLD)) {
        *readbytes += size * 4;
        if(*readbytes > maxbytes) {// data is corrupted?
          fprintf(stderr, "Ran out of bytes while reading offsets.\n");
          ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
          return false;
        }

        // skipping the offsets
        buf += size * 4;
    }

The roaring_buffer_reader functionality optimizes performance through lazy deserialization, which depends on the offset.

It appears that roaring_buffer_reader would have difficulty producing the same results as croaring when dealing with malformed binary input.

[andreas]

I agree with your analysis 👍

Some ideas for how to deal with this:

• Accept inconsistent results for incorrectly serialized bitmaps (status quo). As far as I'm aware, there's no security vulnerabilities as such: if the offset header points outside the buffer, you'll get an error rather than a buffer overflow.
• roaringbitmap_in and rb_from_bytea currently returns the original byte buffer if roaring_bitmap_portable_deserialize_safe succeeds. As an alternative, a new buffer could be allocated, serialized into and returned. This would guarantee a correct offset header.
• roaring_buffer_create could ignore the offset header similar to roaring_bitmap_portable_deserialize_safe, and compute offsets itself. There's already a code path for that, though it will be slower.
• Perhaps roaring_bitmap_portable_deseriable_frozen offers comparable performance to using roaring buffer? If you're interested, I can try implement the change and benchmark the two solutions.

[ChenHuajun]

Thank you for your suggestion. Re-serializing roaringbitmap_inand rb_from_byteaseems like a solid solution.

Using roaring_bitmap_portable_deserialize_frozen for rb_contains boosts performance compared to roaring_bitmap_portable_deserialize, but it's still much slower than roaring_buffer_reader.

my test result as the following:

• roaring_buffer_reader:4.886 ms
• roaring_bitmap_portable_deserialize:19.349 ms
• roaring_bitmap_portable_deserialize_frozen(only r2):16.665 ms
• roaring_bitmap_portable_deserialize_frozen(r1 and r2):14.345 ms

detail of test case:

create temp table tb_test_bitmaps as
  select id,rb_build_agg((random()*10000000)::int) bitmap
    from generate_series(1,100)id, generate_series(1,100000)b
    group by id;
	
explain analyze
with t as(
  select (select bitmap from tb_test_bitmaps where id=1 limit 1) ra1,(select bitmap from tb_test_bitmaps where id=2 limit 1) ra2
)
select rb_contains(ra1,ra2) from t,generate_series(1,100);

 Planning Time: 0.111 ms
 Execution Time: 4.886 ms


explain analyze
with t as(
  select (select bitmap from tb_test_bitmaps where id=1 limit 1) ra1,(select bitmap from tb_test_bitmaps where id=2 limit 1) ra2
)
select rb_contains1(ra1,ra2) from t,generate_series(1,100);

 Planning Time: 0.182 ms
 Execution Time: 19.349 ms

explain analyze
with t as(
  select (select bitmap from tb_test_bitmaps where id=1 limit 1) ra1,(select bitmap from tb_test_bitmaps where id=2 limit 1) ra2
)
select rb_contains2(ra1,ra2) from t,generate_series(1,100);
 Planning Time: 0.097 ms
 Execution Time: 16.665 ms


explain analyze
with t as(
  select (select bitmap from tb_test_bitmaps where id=1 limit 1) ra1,(select bitmap from tb_test_bitmaps where id=2 limit 1) ra2
)
select rb_contains3(ra1,ra2) from t,generate_series(1,100);

 Planning Time: 0.097 ms
 Execution Time: 14.345 ms

roaringbitmap.c:

PG_FUNCTION_INFO_V1(rb_contains1);
Datum rb_contains1(PG_FUNCTION_ARGS);

Datum
rb_contains1(PG_FUNCTION_ARGS) {
    bytea *serializedbytes1 = PG_GETARG_BYTEA_P(0);
    bytea *serializedbytes2 = PG_GETARG_BYTEA_P(1);
    roaring_bitmap_t *r1;
    roaring_bitmap_t *r2;
    bool iscontain;

    r1 = roaring_bitmap_portable_deserialize(VARDATA(serializedbytes1));
    if (!r1)
        ereport(ERROR,
                (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
                 errmsg("bitmap format is error")));

    r2 = roaring_bitmap_portable_deserialize(VARDATA(serializedbytes2));
    if (!r2) {
        roaring_bitmap_free(r1);
        ereport(ERROR,
                (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
                 errmsg("bitmap format is error")));
    }

    roaring_bitmap_and_inplace(r1, r2);
    iscontain = roaring_bitmap_equals(r1, r2);

    roaring_bitmap_free(r1);
    roaring_bitmap_free(r2);
    PG_RETURN_BOOL(iscontain);
}

PG_FUNCTION_INFO_V1(rb_contains2);
Datum rb_contains2(PG_FUNCTION_ARGS);

Datum
rb_contains2(PG_FUNCTION_ARGS) {
    bytea *serializedbytes1 = PG_GETARG_BYTEA_P(0);
    bytea *serializedbytes2 = PG_GETARG_BYTEA_P(1);
    roaring_bitmap_t *r1;
    roaring_bitmap_t *r2;
    bool iscontain;

    r1 = roaring_bitmap_portable_deserialize(VARDATA(serializedbytes1));
    if (!r1)
        ereport(ERROR,
                (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
                 errmsg("bitmap format is error")));

    r2 = roaring_bitmap_portable_deserialize_frozen(VARDATA(serializedbytes2));
    if (!r2) {
        roaring_bitmap_free(r1);
        ereport(ERROR,
                (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
                 errmsg("bitmap format is error")));
    }

    roaring_bitmap_and_inplace(r1, r2);
    iscontain = roaring_bitmap_equals(r1, r2);

    roaring_bitmap_free(r1);
    roaring_bitmap_free(r2);
    PG_RETURN_BOOL(iscontain);
}
PG_FUNCTION_INFO_V1(rb_contains3);
Datum rb_contains3(PG_FUNCTION_ARGS);
Datum
rb_contains3(PG_FUNCTION_ARGS) {
    bytea *serializedbytes1 = PG_GETARG_BYTEA_P(0);
    bytea *serializedbytes2 = PG_GETARG_BYTEA_P(1);
    roaring_bitmap_t *r1;
    roaring_bitmap_t *r2;
    bool iscontain;

    r1 = roaring_bitmap_portable_deserialize_frozen(VARDATA(serializedbytes1));
    if (!r1)
        ereport(ERROR,
                (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
                 errmsg("bitmap format is error")));

    r2 = roaring_bitmap_portable_deserialize_frozen(VARDATA(serializedbytes2));
    if (!r2) {
        roaring_bitmap_free(r1);
        ereport(ERROR,
                (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
                 errmsg("bitmap format is error")));
    }

    roaring_bitmap_and_inplace(r1, r2);
    iscontain = roaring_bitmap_equals(r1, r2);

    roaring_bitmap_free(r1);
    roaring_bitmap_free(r2);
    PG_RETURN_BOOL(iscontain);
}

roaringbitmap--0.5.sql:

CREATE OR REPLACE FUNCTION rb_contains1(roaringbitmap, roaringbitmap)
  RETURNS bool
  AS  'MODULE_PATHNAME', 'rb_contains1'
  LANGUAGE C STRICT IMMUTABLE PARALLEL SAFE;

CREATE OR REPLACE FUNCTION rb_contains2(roaringbitmap, roaringbitmap)
  RETURNS bool
  AS  'MODULE_PATHNAME', 'rb_contains2'
  LANGUAGE C STRICT IMMUTABLE PARALLEL SAFE;

CREATE OR REPLACE FUNCTION rb_contains3(roaringbitmap, roaringbitmap)
  RETURNS bool
  AS  'MODULE_PATHNAME', 'rb_contains3'
  LANGUAGE C STRICT IMMUTABLE PARALLEL SAFE;