R crash when `union = T` in `image_line_segment_detector()`

[matthew-law]

Similarly to #7 and #19, when I set union = T in image_line_segment_detector(), R crashes. The following reproduces the error for me:

library(image.LineSegmentDetector)
library(pixmap)

image <- read.pnm(file = system.file("extdata", "le-piree.pgm", package="image.LineSegmentDetector"), cellres = 1)

linesegments <- image_line_segment_detector(image@grey * 255, union = T)

sessionInfo:

R version 4.0.5 (2021-03-31)
Platform: x86_64-apple-darwin17.0 (64-bit)
Running under: macOS Big Sur 10.16

Matrix products: default
LAPACK: /Library/Frameworks/R.framework/Versions/4.0/Resources/lib/libRlapack.dylib

locale:
[1] en_GB.UTF-8/en_GB.UTF-8/en_GB.UTF-8/C/en_GB.UTF-8/en_GB.UTF-8

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] pixmap_0.4-12                   image.LineSegmentDetector_0.1.0

loaded via a namespace (and not attached):
 [1] Rcpp_1.0.7         pillar_1.6.3       compiler_4.0.5     class_7.3-19       tools_4.0.5       
 [6] digest_0.6.28      jsonlite_1.7.2     evaluate_0.14      lifecycle_1.0.1    tibble_3.1.5      
[11] lattice_0.20-44    pkgconfig_2.0.3    rlang_0.4.11       DBI_1.1.1          yaml_2.2.1        
[16] xfun_0.26          fastmap_1.1.0      e1071_1.7-9        dplyr_1.0.7        httr_1.4.2        
[21] knitr_1.36         raster_3.4-13      generics_0.1.0     vctrs_0.3.8        classInt_0.4-3    
[26] grid_4.0.5         tidyselect_1.1.1   glue_1.4.2         sf_1.0-2           R6_2.5.1          
[31] fansi_0.5.0        rmarkdown_2.10     bookdown_0.23      sp_1.4-5           purrr_0.3.4       
[36] clipr_0.7.1        magrittr_2.0.1     units_0.7-2        codetools_0.2-18   ellipsis_0.3.2    
[41] htmltools_0.5.2    assertthat_0.2.1   KernSmooth_2.23-20 utf8_1.2.2         proxy_0.4-26      
[46] crayon_1.4.1 

[jwijffels]

Thanks for the crash report. Issue #7 and #19 are unrelated but indeed I can confirm the core dump.

[jwijffels]

I can only reproduce this crash on Windows, not on an Ubuntu Linux machine which I have access to.

[matthew-law]

If it helps, I came across it running macOS (full details in the sessionInfo)

[jwijffels]

what do you get when you run the code using R -d valgrind?

[matthew-law]

Maybe a basic question, but how do I actually run the code using R -d valgrind? Is valgrind something I need to download, and do I run it from the terminal?

[jwijffels]

I thought on Mac this was brew install valgrind
And next start up R with R -d valgrind and pass on the code with gives the 💣

[matthew-law]

Hmm, I get

valgrind: Linux is required for this software.
Error: valgrind: An unsatisfied requirement failed this build.

when I run brew install valgrind

[jwijffels]

Ok, I'll find another way to debug this using GDB.

[jwijffels]

Debug trace using the address sanitizer RDsan using wch1/r-debug

> library(image.LineSegmentDetector)
> library(pixmap)
> 
> image <- read.pnm(file = system.file("extdata", "le-piree.pgm", package="image.LineSegmentDetector"), cellres = 1)
> 
> linesegments <- image_line_segment_detector(image@grey * 255, union = T)
=================================================================
==14==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000575fb0 at pc 0x7fd75cf9fa10 bp 0x7ffc26c03a70 sp 0x7ffc26c03a60
READ of size 8 at 0x602000575fb0 thread T0
    #0 0x7fd75cf9fa0f in LineSegmentDetection /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:2599
    #1 0x7fd75cf89fd2 in detect_line_segments(Rcpp::Vector<14, Rcpp::PreserveStorage>, int, int, double, double, double, double, double, double, int, int, double, int, double, double, double) /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/line_segment_detector.cpp:31
    #2 0x7fd75cf5472f in _image_LineSegmentDetector_detect_line_segments /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/RcppExports.cpp:30
    #3 0x7fd767109454 in R_doDotCall /tmp/r-source/src/main/dotcode.c:672
    #4 0x7fd767124014 in do_dotcall /tmp/r-source/src/main/dotcode.c:1284
    #5 0x7fd7671d7640 in bcEval /tmp/r-source/src/main/eval.c:7139
    #6 0x7fd7671a95e6 in Rf_eval /tmp/r-source/src/main/eval.c:748
    #7 0x7fd7671afca5 in R_execClosure /tmp/r-source/src/main/eval.c:1918
    #8 0x7fd7671af396 in Rf_applyClosure /tmp/r-source/src/main/eval.c:1844
    #9 0x7fd7671d6d6a in bcEval /tmp/r-source/src/main/eval.c:7107
    #10 0x7fd7671a95e6 in Rf_eval /tmp/r-source/src/main/eval.c:748
    #11 0x7fd7671afca5 in R_execClosure /tmp/r-source/src/main/eval.c:1918
    #12 0x7fd7671af396 in Rf_applyClosure /tmp/r-source/src/main/eval.c:1844
    #13 0x7fd7671aa7bf in Rf_eval /tmp/r-source/src/main/eval.c:871
    #14 0x7fd7671b7daa in do_set /tmp/r-source/src/main/eval.c:2990
    #15 0x7fd7671a9f71 in Rf_eval /tmp/r-source/src/main/eval.c:823
    #16 0x7fd7672588eb in Rf_ReplIteration /tmp/r-source/src/main/main.c:264
    #17 0x7fd767258dca in R_ReplConsole /tmp/r-source/src/main/main.c:316
    #18 0x7fd76725b43d in run_Rmainloop /tmp/r-source/src/main/main.c:1130
    #19 0x7fd76725b457 in Rf_mainloop /tmp/r-source/src/main/main.c:1137
    #20 0x55996bb02238 in main /tmp/r-source/src/main/Rmain.c:29
    #21 0x7fd7663140b2 in __libc_start_main (/usr/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #22 0x55996bb0210d in _start (/usr/local/RDsan/lib/R/bin/exec/R+0x110d)

0x602000575fb0 is located 0 bytes inside of 16-byte region [0x602000575fb0,0x602000575fc0)
freed by thread T0 here:
    #0 0x7fd7678f11c7 in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:123
    #1 0x7fd75cf92950 in free_image_int /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:408
    #2 0x7fd75cf9dd4e in line_segment_grower /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:2344
    #3 0x7fd75cf9f8f6 in LineSegmentDetection /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:2575
    #4 0x7fd75cf89fd2 in detect_line_segments(Rcpp::Vector<14, Rcpp::PreserveStorage>, int, int, double, double, double, double, double, double, int, int, double, int, double, double, double) /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/line_segment_detector.cpp:31
    #5 0x7fd75cf5472f in _image_LineSegmentDetector_detect_line_segments /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/RcppExports.cpp:30
    #6 0x7fd767109454 in R_doDotCall /tmp/r-source/src/main/dotcode.c:672
    #7 0x7fd767124014 in do_dotcall /tmp/r-source/src/main/dotcode.c:1284
    #8 0x7fd7671d7640 in bcEval /tmp/r-source/src/main/eval.c:7139
    #9 0x7fd7671a95e6 in Rf_eval /tmp/r-source/src/main/eval.c:748
    #10 0x7fd7671afca5 in R_execClosure /tmp/r-source/src/main/eval.c:1918
    #11 0x7fd7671af396 in Rf_applyClosure /tmp/r-source/src/main/eval.c:1844
    #12 0x7fd7671d6d6a in bcEval /tmp/r-source/src/main/eval.c:7107
    #13 0x7fd7671a95e6 in Rf_eval /tmp/r-source/src/main/eval.c:748
    #14 0x7fd7671afca5 in R_execClosure /tmp/r-source/src/main/eval.c:1918
    #15 0x7fd7671af396 in Rf_applyClosure /tmp/r-source/src/main/eval.c:1844
    #16 0x7fd7671aa7bf in Rf_eval /tmp/r-source/src/main/eval.c:871
    #17 0x7fd7671b7daa in do_set /tmp/r-source/src/main/eval.c:2990
    #18 0x7fd7671a9f71 in Rf_eval /tmp/r-source/src/main/eval.c:823
    #19 0x7fd7672588eb in Rf_ReplIteration /tmp/r-source/src/main/main.c:264
    #20 0x7fd767258dca in R_ReplConsole /tmp/r-source/src/main/main.c:316
    #21 0x7fd76725b43d in run_Rmainloop /tmp/r-source/src/main/main.c:1130
    #22 0x7fd76725b457 in Rf_mainloop /tmp/r-source/src/main/main.c:1137
    #23 0x55996bb02238 in main /tmp/r-source/src/main/Rmain.c:29
    #24 0x7fd7663140b2 in __libc_start_main (/usr/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

previously allocated by thread T0 here:
    #0 0x7fd7678f1527 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x7fd75cf92987 in new_image_int /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:423
    #2 0x7fd75cf92aa3 in new_image_int_ini /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:442
    #3 0x7fd75cf9e94d in LineSegmentDetection /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:2489
    #4 0x7fd75cf89fd2 in detect_line_segments(Rcpp::Vector<14, Rcpp::PreserveStorage>, int, int, double, double, double, double, double, double, int, int, double, int, double, double, double) /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/line_segment_detector.cpp:31
    #5 0x7fd75cf5472f in _image_LineSegmentDetector_detect_line_segments /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/RcppExports.cpp:30
    #6 0x7fd767109454 in R_doDotCall /tmp/r-source/src/main/dotcode.c:672
    #7 0x7fd767124014 in do_dotcall /tmp/r-source/src/main/dotcode.c:1284
    #8 0x7fd7671d7640 in bcEval /tmp/r-source/src/main/eval.c:7139
    #9 0x7fd7671a95e6 in Rf_eval /tmp/r-source/src/main/eval.c:748
    #10 0x7fd7671afca5 in R_execClosure /tmp/r-source/src/main/eval.c:1918
    #11 0x7fd7671af396 in Rf_applyClosure /tmp/r-source/src/main/eval.c:1844
    #12 0x7fd7671d6d6a in bcEval /tmp/r-source/src/main/eval.c:7107
    #13 0x7fd7671a95e6 in Rf_eval /tmp/r-source/src/main/eval.c:748
    #14 0x7fd7671afca5 in R_execClosure /tmp/r-source/src/main/eval.c:1918
    #15 0x7fd7671af396 in Rf_applyClosure /tmp/r-source/src/main/eval.c:1844
    #16 0x7fd7671aa7bf in Rf_eval /tmp/r-source/src/main/eval.c:871
    #17 0x7fd7671b7daa in do_set /tmp/r-source/src/main/eval.c:2990
    #18 0x7fd7671a9f71 in Rf_eval /tmp/r-source/src/main/eval.c:823
    #19 0x7fd7672588eb in Rf_ReplIteration /tmp/r-source/src/main/main.c:264
    #20 0x7fd767258dca in R_ReplConsole /tmp/r-source/src/main/main.c:316
    #21 0x7fd76725b43d in run_Rmainloop /tmp/r-source/src/main/main.c:1130
    #22 0x7fd76725b457 in Rf_mainloop /tmp/r-source/src/main/main.c:1137
    #23 0x55996bb02238 in main /tmp/r-source/src/main/Rmain.c:29
    #24 0x7fd7663140b2 in __libc_start_main (/usr/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

SUMMARY: AddressSanitizer: heap-use-after-free /tmp/RtmpSYxsFy/R.INSTALLf35be2df52/image.LineSegmentDetector/src/lsd.c:2599 in LineSegmentDetection
Shadow bytes around the buggy address:
  0x0c04800a6ba0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fd fd
  0x0c04800a6bb0: fa fa fd fd fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c04800a6bc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c04800a6bd0: fa fa fd fd fa fa fd fd fa fa fd fd fa fa fa fa
  0x0c04800a6be0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c04800a6bf0: fa fa 00 04 fa fa[fd]fd fa fa 03 fa fa fa fa fa
  0x0c04800a6c00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c04800a6c10: fa fa 00 fa fa fa fd fa fa fa 03 fa fa fa fd fd
  0x0c04800a6c20: fa fa fd fa fa fa fd fd fa fa fd fd fa fa fd fa
  0x0c04800a6c30: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c04800a6c40: fa fa fd fd fa fa fd fa fa fa fd fa fa fa fd fd
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
  Shadow gap:              cc
==14==ABORTING

coming from here https://github.com/bnosac/image/blob/master/image.LineSegmentDetector/src/lsd.c#L2599 caused by region->xsize and region->ysize equal to 0
image is being freed https://github.com/bnosac/image/blob/master/image.LineSegmentDetector/src/lsd.c#L2344 but as region->xsize and region->ysize are equal to 0, no new one is created

[jwijffels]

Hello @rafael-grompone-von-gioi
Can you shed some light on this crash using the LSD line segment detector implementation. It looks like an extra check is needed checking that region->xsize and region->ysize are bigger than 0

[rafael-grompone-von-gioi]

Hi,

I'm not sure of understanding the problem, but I see that lines 2339 to 2346 are different from the equivalent in my code which are:

  /* initialize some structures */
  if( reg_img != NULL && reg_x != NULL && reg_y != NULL ) /* save region data */
    region = new_image_int_ini(angles->xsize,angles->ysize,0);
  used = new_image_char_ini(xsize,ysize,NOTUSED);
  reg = (struct point *) calloc( (size_t) (xsize*ysize), sizeof(struct point) );
  if( reg == NULL ) error("not enough memory!");

As you can see, there is no memory freed in my version. Do you know why was it changed?

Anyway, all that about reg_img, reg_x and reg_y was just to be able to store and analyse the assigment of pixels into regions. It was useful for my while developping the algorithm, but I'm not sure it is of much use now. I think it could be removed.

I take the oportunity to point out a small bug (which was discovered by someone I can't remember now who). In lines 2600 and 2601 it should be

      if( region->xsize > (unsigned int) INT_MAX ||
          region->ysize > (unsigned int) INT_MAX )

while in line 2601 we now read region->xsize, so both times it is checking the X size.

I hope this helps. Don't hesitate if there are further questions.

Best!

[rafael-grompone-von-gioi]

Hi again,

I just see another difference with my code, probably the important for this problem. In my code, at the begining of the function LineSegmentDetection there is a series of checks to verify the input consistency; those checks were removed:

  /* check parameters */
  if( img == NULL || X <= 0 || Y <= 0 ) error("invalid image input.");
  if( scale <= 0.0 ) error("'scale' value must be positive.");
  if( sigma_scale <= 0.0 ) error("'sigma_scale' value must be positive.");
  if( quant < 0.0 ) error("'quant' value must be positive.");
  if( ang_th <= 0.0 || ang_th >= 180.0 )
    error("'ang_th' value must be in the range (0,180).");
  if( density_th < 0.0 || density_th > 1.0 )
    error("'density_th' value must be in the range [0,1].");
  if( n_bins <= 0 ) error("'n_bins' value must be positive.");

As you can see, the first check is that the image size is larger than zero. So this may explain why the check may be needed.

As my code was done assuming those conditions were satisfied, I would not remove those checks because there are probably many other places were they are assumed.

best

[jwijffels]

Regarding the removal of the check parameters.

That was needed in order to make CRAN happy, which didn't like the use of printf. And I didn't put time to replace it with the Rprintf R equivalent which was allowed and just commented it out. I don't think these are the culprit here as the default ones which are used in the example are the ones from the paper

image_line_segment_detector(
  x,
  scale = 0.8,
  sigma_scale = 0.6,
  quant = 2,
  ang_th = 22.5,
  log_eps = 0,
  density_th = 0.7,
  n_bins = 1024,
  union = FALSE,
  union_min_length = 5,
  union_max_distance = 5,
  union_ang_th = 7,
  union_use_NFA = FALSE,
  union_log_eps = 0
)

After a second look, I'll see if I can add the check at if( img == NULL || X <= 0 || Y <= 0 ) error("invalid image input."); and clean R nicely instead of letting it segfault.

About this,

  if( region->xsize > (unsigned int) INT_MAX ||
      region->ysize > (unsigned int) INT_MAX )

I saw that as well and tested out if this might have been the reason of the 💣 but that wasn't the cause

As you can see, there is no memory freed in my version. Do you know why was it changed?

Not sure, I thought I took the C code version 1.6 from http://www.ipol.im/pub/art/2012/gjmr-lsd/ but indeed it looks a bit different. Where is the last version of the code? Is it version 1.6 at http://www.ipol.im/pub/art/2012/gjmr-lsd/

On version 1.6 at ipol now there is in the comments

  HISTORY:
   - version 1.6 - nov 2011:
                             - changes in the interface,
                             - max_grad parameter removed,
                             - the factor 11 was added to the number of test
                               to consider the different precision values
                               tested,
                             - a minor bug corrected in the gradient sorting
                               code,
                             - the algorithm now also returns p and log_nfa
                               for each detection,
                             - a minor bug was corrected in the image scaling,
                             - the angle comparison in "isaligned" changed
                               from < to <=,
                             - "eps" variable renamed "log_eps",
                             - "lsd_scale_region" interface was added,
                             - minor changes to comments.

while this R wrapper has: https://github.com/bnosac/image/blob/master/image.LineSegmentDetector/src/lsd.c#L57
Maybe this wasn't the last version that you put on ipol?

    HISTORY:
    - version 1.6 - nov 2011: Changes in the interface,
                              max_grad parameter removed,
                              the factor 11 was added to the number of test
                              to consider the different precision values tested,
                              a minor bug corrected in the gradient sorting
                              code.

[rafael-grompone-von-gioi]

Yes, the last version of the LSD code is the 1.6 at Ipol you mention.

[jwijffels]

But one of the parameters checked is the image size. If you have X or Y equal to zero, that menas that test is needed. Or am I wrong?

yes, I'll add this check again. I disabled all the error() commands as they used printf and I should use Rprintf on R