RoaringBitmap / RoaringBitmap/roaring
is not safe to call RunOptimize() on some ReadFrom inputs
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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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