View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0030518CommunityOCCT:Foundation Classespublic2019-02-25 23:402019-09-29 12:36
Reportergalbramc Assigned Tobugmaster  
PrioritynormalSeveritycrash 
Status closedResolutionfixed 
PlatformLinuxOSUbuntu 
Product Version7.3.0 
Target Version7.4.0Fixed in Version7.4.0 
Summary0030518: Foundation Classes - NCollection_IndexedDataMap array out of bounds
DescriptionIterating over a NCollection_IndexedDataMap can access out of array bounds. The attached example compiles with the llvm sanitizer and when executed gives the following error:

./NCollection_BaseMap
Going out of array bounds!
=================================================================
==19306==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x618000000bb0 at pc 0x00000040b8f2 bp 0x7ffe95c2dc10 sp 0x7ffe95c2dc08
READ of size 8 at 0x618000000bb0 thread T0
    #0 0x40b8f1 in NCollection_IndexedDataMap<TopoDS_Shape, NCollection_List<TopoDS_Shape>, TopTools_ShapeMapHasher>::Iterator::Next() opencascade-7.3/build_memcheck/install/include/opencascade/NCollection_IndexedDataMap.hxx:111
    0000001 0x4086d8 in main NCollection_IndexedDataMap.cpp:39
    0000002 0x7f24c20eef44 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21f44)
    #3 0x407ec8 (NCollection_IndexedDataMap+0x407ec8)

0x618000000bb0 is located 0 bytes to the right of 816-byte region [0x618000000880,0x618000000bb0)
allocated by thread T0 here:
    #0 0x7f24c41726a8 in __interceptor_calloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xda6a8)
    0000001 0x7f24c3e96998 in Standard_MMgrRaw::Allocate(unsigned long) opencascade-7.3/src/Standard/Standard_MMgrRaw.cxx:41
    0000002 0x7f24c3e8b651 in Standard::Allocate(unsigned long) opencascade-7.3/src/Standard/Standard.cxx:240
    #3 0x7f24c3f0d59f in NCollection_BaseAllocator::Allocate(unsigned long) opencascade-7.3/src/NCollection/NCollection_BaseAllocator.cxx:37
    #4 0x7f24c3f14779 in NCollection_BaseMap::BeginResize(int, int&, NCollection_ListNode**&, NCollection_ListNode**&) const opencascade-7.3/src/NCollection/NCollection_BaseMap.cxx:45
    #5 0x40c5fa in NCollection_IndexedDataMap<TopoDS_Shape, NCollection_List<TopoDS_Shape>, TopTools_ShapeMapHasher>::ReSize(int) opencascade-7.3/build_memcheck/install/include/opencascade/NCollection_IndexedDataMap.hxx:223
    #6 0x40b384 in NCollection_IndexedDataMap<TopoDS_Shape, NCollection_List<TopoDS_Shape>, TopTools_ShapeMapHasher>::Add(TopoDS_Shape const&, NCollection_List<TopoDS_Shape> const&) opencascade-7.3/build_memcheck/install/include/opencascade/NCollection_IndexedDataMap.hxx:256
    0000007 0x4084f2 in main NCollection_BaseMap_array_out_of_bound/NCollection_BaseMap.cpp:32
    0000008 0x7f24c20eef44 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21f44)

SUMMARY: AddressSanitizer: heap-buffer-overflow opencascade-7.3/build_memcheck/install/include/opencascade/NCollection_IndexedDataMap.hxx:111 in NCollection_IndexedDataMap<TopoDS_Shape, NCollection_List<TopoDS_Shape>, TopTools_ShapeMapHasher>::Iterator::Next()
Shadow bytes around the buggy address:
  0x0c307fff8120: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c307fff8130: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c307fff8140: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c307fff8150: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c307fff8160: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c307fff8170: 00 00 00 00 00 00[fa]fa fa fa fa fa fa fa fa fa
  0x0c307fff8180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c307fff8190: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c307fff81a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c307fff81b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c307fff81c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable: 00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone: fa
  Freed heap region: fd
  Stack left redzone: f1
  Stack mid redzone: f2
  Stack right redzone: f3
  Stack after return: f5
  Stack use after scope: f8
  Global redzone: f9
  Global init order: f6
  Poisoned by user: f7
  Container overflow: fc
  Array cookie: ac
  Intra object redzone: bb
  ASan internal: fe
  Left alloca redzone: ca
  Right alloca redzone: cb
==19306==ABORTING


I found changing NColloection_BaseMap.hxx

  //! Resizable
  Standard_Boolean Resizable() const
  { return IsEmpty() || (mySize > myNbBuckets); }

to

  //! Resizable
  Standard_Boolean Resizable() const
  { return IsEmpty() || (mySize >= myNbBuckets); }

avoids the error, but I don't know that this is the correct solution.
Steps To ReproduceCompile and run the attached example. You might need the -fuse-ld=gold flag on certain platforms. g++ must be 4.9 or newer.
TagsNo tags attached.
Test case numberNot required

Attached Files

  • NCollection_IndexedDataMap_array_out_of_bound.tgz (1,223 bytes)

Relationships

child of 0030557 newdpasukhi Open CASCADE Coding - eliminate errors reported by -fsanitize 

Activities

galbramc

2019-02-25 23:40

reporter  

NCollection_IndexedDataMap_array_out_of_bound.tgz (1,223 bytes)

abv

2019-09-16 07:12

manager   ~0087106

Indexed map allocates two buffers of size myNbBuckets + 1: first (myData1) addressed by hash code of the item, and second (myData2) - by its index. Note that both indices and hash codes in OCCT maps are 1-based. Nodes in myData1 are stored in elements [1, myNbBuckets], and element 0 seems to be never used. In myData2 the nodes are stored with index - 1. Thus everything is fine provided that number of elements in the map (mySize, returned by Extent()) is not greater than myNbBuckets + 1.

Method Resizable() checks whether the map has to grow to accommodate one more element. If mySize == myNbBuckets, it returns False, the map is not resized, and after addition of the new element mySize = myNbBuckets + 1. For hash-coded storage it is OK, since hash code is always computed for range [1, myNbBuckets]; the only drawback is that map necessarily becomes saturated (at least one of elements stores two nodes). For index-based storage it is OK as well: it just uses full length of the array, and the element with index mySize is put into the last element of the array (mySize - 1 = myNbBuckets).

The reason why out-of-bounds read happens is in implementation of method Next() in NCollection_IndexedDataMap::Iterator: it advances to the next element of the array uncoditionally, and then method More() is expected to be called to check whether current value is valid. This is indeed an out-of-bounds read, even if the value should never be used in normal situations, thus better to be avoided.

git

2019-09-16 08:04

administrator   ~0087108

Branch CR30518 has been created by abv.

SHA-1: b292a46232d02f1d2b9459e575afe49b7d15c391


Detailed log of new commits:

Author: abv
Date: Mon Sep 16 08:01:13 2019 +0300

    0030518: Foundation Classes - NCollection_IndexedDataMap array out of bounds
    
    Implementation of NCollection_IndexedDataMap::Iterator is revised to avoid unintended access to the element out of array bounds

git

2019-09-17 06:15

administrator   ~0087175

Branch CR30518 has been updated by abv.

SHA-1: 35bd28c9696fb805e21fb686be15a02820e7fca6


Detailed log of new commits:

Author: abv
Date: Tue Sep 17 06:11:22 2019 +0300

    Safer version

abv

2019-09-17 06:21

manager   ~0087176

First version of the patch (storing pointer to the nodes and then advancing by incrementing that pointer) broke test case "sat read_parallel_1 C2" on Debian80-64:

satread /dn62/occt_tests_data/private/unsorted/sat/ACIS22569-matricemobile.sat ss
 File SAT to read : /dn62/occt_tests_data/private/unsorted/sat/ACIS22569-matricemobile.sat
 -- Names of variables BREP-DRAW prefixed by : ss
*** Error in `DRAWEXE': double free or corruption (!prev): 0x00007fe3080063f0 ***

I have no access to Linux environment with Products thus cannot investigate that with reasonable effort, alas.

Updated version just committed stores pointer to the map and uses its methods to iterate; it should be more safe e.g. if the map gets resized during iteration.

git

2019-09-19 23:17

administrator   ~0087332

Branch CR30518_week38 has been created by abv.

SHA-1: 68fb36d38da989159d9bfa2885746d5e6ef6aec4


Detailed log of new commits:

Author: abv
Date: Mon Sep 16 08:01:13 2019 +0300

    0030518: Foundation Classes - NCollection_IndexedDataMap array out of bounds
    
    Implementation of NCollection_IndexedDataMap::Iterator is revised to avoid unintended access to the element out of array bounds

abv

2019-09-20 09:32

manager   ~0087343

The problem with test sat read_parallel_1 C2 seems to be a bogus one. I have pushed branch CR30518_week38 based on current IR prototype, and tests are OK on that branch - see Jenkins job CR30518-abv (please ignore warnings on deprecated symbols in Products - this is apparently due to use of master of products with WEEK38 branch of OCCT). I suppose the branch is OK, please review.

git

2019-09-22 11:40

administrator   ~0087410

Branch CR30518 has been deleted by inv.

SHA-1: 35bd28c9696fb805e21fb686be15a02820e7fca6

git

2019-09-29 12:36

administrator   ~0087614

Branch CR30518_week38 has been deleted by inv.

SHA-1: 68fb36d38da989159d9bfa2885746d5e6ef6aec4

Related Changesets

occt: master eb62cbc4

2019-09-16 05:01:13

abv


Committer: bugmaster Details Diff		 0030518: Foundation Classes - NCollection_IndexedDataMap array out of bounds

Implementation of NCollection_IndexedDataMap::Iterator is revised to avoid unintended access to the element out of array bounds		 Affected Issues
0030518
mod - src/NCollection/NCollection_BaseMap.cxx Diff File
mod - src/NCollection/NCollection_IndexedDataMap.hxx Diff File

Issue History

Date Modified Username Field Change
2019-02-25 23:40 galbramc New Issue
2019-02-25 23:40 galbramc Assigned To => msv
2019-02-25 23:40 galbramc File Added: NCollection_IndexedDataMap_array_out_of_bound.tgz
2019-02-26 10:21 msv Assigned To msv => abv
2019-02-26 10:21 msv Category OCCT:Modeling Algorithms => OCCT:Foundation Classes
2019-03-13 13:54 kgv Relationship added child of 0030557
2019-03-13 13:55 kgv Summary NCollection_IndexedDataMap array out of bounds => Foundation Classes - NCollection_IndexedDataMap array out of bounds
2019-03-24 16:38 kgv Assigned To abv => tizmaylo
2019-03-24 16:38 kgv Status new => assigned
2019-03-24 16:38 kgv Target Version => 7.4.0
2019-09-16 07:12 abv Note Added: 0087106
2019-09-16 08:04 git Note Added: 0087108
2019-09-17 06:15 git Note Added: 0087175
2019-09-17 06:21 abv Note Added: 0087176
2019-09-19 23:17 git Note Added: 0087332
2019-09-20 09:32 abv Note Added: 0087343
2019-09-20 09:32 abv Assigned To tizmaylo => kgv
2019-09-20 09:32 abv Status assigned => resolved
2019-09-20 12:27 kgv Assigned To kgv => bugmaster
2019-09-20 12:27 kgv Status resolved => reviewed
2019-09-20 14:00 bugmaster Test case number => Not required
2019-09-21 18:13 bugmaster Changeset attached => occt master eb62cbc4
2019-09-21 18:13 bugmaster Status reviewed => verified
2019-09-21 18:13 bugmaster Resolution open => fixed
2019-09-22 11:40 git Note Added: 0087410
2019-09-29 12:36 git Note Added: 0087614