RoaringBitmap / RoaringBitmap/roaring

is not safe to call RunOptimize() on some ReadFrom inputs

Open
#181 6 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Go
Stars
2.9k
Forks
262
Avg merge
2h 34m
Merged PRs (30d)
8

Description

Assuming any data is valid if loaded by ReadFrom , calling RunOptimize() should be safe. but for example in this case :

package main

import (
	"encoding/base64"
	"log"

	"github.com/RoaringBitmap/roaring"
)

func main() {
	// some invalid data, base64 for readability of non-visual chars
	t, _ := base64.StdEncoding.DecodeString("OzAEAAAwMAAAMDABADAwAAAwMAEAMDAAADAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDA=")

	m := roaring.NewBitmap()

	// no error on invalid data
	err := m.UnmarshalBinary(t)
	if err != nil {
		log.Fatal(err)
	}
	m.RunOptimize()
}

Result is :

panic: then fundamental arrayContainer assumption of deduplicated content was broken

goroutine 1 [running]:
github.com/RoaringBitmap/roaring.(*arrayContainer).numberOfRuns(0xc42000a120, 0x1)
	/home/f0rud/src/github.com/RoaringBitmap/roaring/arraycontainer.go:927 +0xca
github.com/RoaringBitmap/roaring.(*arrayContainer).toEfficientContainer(0xc42000a120, 0x533fa0, 0xc42000a100)
	/home/f0rud/src/github.com/RoaringBitmap/roaring/arraycontainer.go:942 +0x2f
github.com/RoaringBitmap/roaring.(*roaringArray).runOptimize(0xc420049f10)
	/home/f0rud/src/github.com/RoaringBitmap/roaring/roaringarray.go:130 +0x7a
github.com/RoaringBitmap/roaring.(*Bitmap).RunOptimize(0xc420049f10)
	/home/f0rud/src/github.com/RoaringBitmap/roaring/roaring.go:96 +0x2d
main.main()
	/home/f0rud/src/roar/main.go:21 +0xfd
exit status 2

also there was another panic (" panic: then fundamental arrayContainer assumption of sorted ac.content was broken ") for this payload (base64 of payload):

OzAFAAAwMAAAMDABADAwAAAwMAEAMDAAADAwAAAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMP8wMDAwMAAwMDAw

either

  • My assumption is wrong
  • or ReadFrom should validate input for "fundamental arrayContainer assumptions"

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the provided Go reproducer and trace UnmarshalBinary or ReadFrom into the arrayContainer assumptions exercised by RunOptimize. Inspect arraycontainer.go and roaringarray.go, then verify that malformed input is rejected without a panic while valid input can still be optimized.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.