Uploaded image for project: 'Data Management'
  1. Data Management
  2. DM-3112

Invalid read in afw::math::Interpolate --- off-by-one bug

    Details

    • Type: Bug
    • Status: Done
    • Resolution: Done
    • Fix Version/s: None
    • Component/s: afw
    • Labels:
      None

      Description

      Nate Lust discovered an invalid read in afw::math::makeInterpolate by running valgrind on a test for PSFEx.

      ==23324== Invalid read of size 8
      ==23324==    at 0x1B09ACE4: lsst::afw::math::makeInterpolate(std::vector<double, std::allocator<double> > const&, std::vector<double, std::allocator<double> > const&, lsst::afw::math::Interpolate::Style) (Interpolate.cc:74)
      ==23324==    by 0x1B0A9B16: lsst::afw::math::BackgroundMI::_setGridColumns(lsst::afw::math::Interpolate::Style, lsst::afw::math::UndersampleStyle, int, std::vector<int, std::allocator<int> > const&) const (BackgroundMI.cc:168)
      ==23324==    by 0x1B0AC7A9: boost::shared_ptr<lsst::afw::image::Image<float> > lsst::afw::math::BackgroundMI::doGetImage<float>(lsst::afw::geom::Box2I const&, lsst::afw::math::Interpolate::Style, lsst::afw::math::UndersampleStyle) const (BackgroundMI.cc:339)
      ==23324==    by 0x1B0AA0E8: lsst::afw::math::BackgroundMI::_getImage(lsst::afw::geom::Box2I const&, lsst::afw::math::Interpolate::Style, lsst::afw::math::UndersampleStyle, float) const (BackgroundMI.cc:453)
      

      On inspection, the loop is running off the end of the array: when i = x.size() - 1 (i.e., the last element), then it's trying to access x[i+1], which is off the end.

        Attachments

          Issue Links

            Activity

            Hide
            price Paul Price added a comment -

            One-line fix for review:

            pprice@tiger-sumire:~/LSST/afw (tickets/DM-3112=) $ git --no-pager log --patch --reverse origin/master..
            commit 4f190f38e0b513629d4f886c0427c86f8ca6f753
            Author: Paul Price <price@astro.princeton.edu>
            Date:   Fri Jul 10 14:12:43 2015 -0400
             
                interpolate: fix off-by-one bug in InterpolateConstant
                
                Nate Lust found an "invalid read" in the "recenter" function
                when running Valgrind on a test of PSFEx.  Inspection of the
                code found that we were running off the end of the array.
                This error is not (in general) reproduced by running valgrind
                on afw's interpolate.py test, probably because we're getting
                more space back from the standard library than we ask for.
                Changing the test to use 8 or 16 values allows valgrind to
                see the error, which goes away with this fix, but I've not
                modified the test.
             
            diff --git a/src/math/Interpolate.cc b/src/math/Interpolate.cc
            index 50e1738..3736739 100644
            --- a/src/math/Interpolate.cc
            +++ b/src/math/Interpolate.cc
            @@ -69,7 +69,7 @@ namespace {
                     recentered_x[j] = 0.5*(3*x[0] - x[1]);
                     recentered_y[j] = y[0];
             
            -        for (unsigned int i = 0; i < x.size(); ++i) {
            +        for (std::size_t i = 0; i < x.size() - 1; ++i) {
                         ++j;
                         recentered_x[j] = 0.5*(x[i] + x[i + 1]);
                         recentered_y[j] = 0.5*(y[i] + y[i + 1]);
            

            Show
            price Paul Price added a comment - One-line fix for review: pprice@tiger-sumire:~/LSST/afw (tickets/DM-3112=) $ git --no-pager log --patch --reverse origin/master.. commit 4f190f38e0b513629d4f886c0427c86f8ca6f753 Author: Paul Price <price@astro.princeton.edu> Date: Fri Jul 10 14:12:43 2015 -0400   interpolate: fix off-by-one bug in InterpolateConstant Nate Lust found an "invalid read" in the "recenter" function when running Valgrind on a test of PSFEx. Inspection of the code found that we were running off the end of the array. This error is not (in general) reproduced by running valgrind on afw's interpolate.py test, probably because we're getting more space back from the standard library than we ask for. Changing the test to use 8 or 16 values allows valgrind to see the error, which goes away with this fix, but I've not modified the test.   diff --git a/src/math/Interpolate.cc b/src/math/Interpolate.cc index 50e1738..3736739 100644 --- a/src/math/Interpolate.cc +++ b/src/math/Interpolate.cc @@ -69,7 +69,7 @@ namespace { recentered_x[j] = 0.5*(3*x[0] - x[1]); recentered_y[j] = y[0]; - for (unsigned int i = 0; i < x.size(); ++i) { + for (std::size_t i = 0; i < x.size() - 1; ++i) { ++j; recentered_x[j] = 0.5*(x[i] + x[i + 1]); recentered_y[j] = 0.5*(y[i] + y[i + 1]);
            Hide
            price Paul Price added a comment -

            Oh, hang on — test doesn't pass now…

            Show
            price Paul Price added a comment - Oh, hang on — test doesn't pass now…
            Hide
            price Paul Price added a comment -

            Test passes now:

            pprice@tiger-sumire:~/LSST/afw (tickets/DM-3112=) $ git --no-pager log --patch --reverse origin/master..
            commit 518fe3cd0bf4b4e01bf130d4fc9f51c486fe6b30
            Author: Paul Price <price@astro.princeton.edu>
            Date:   Fri Jul 10 14:12:43 2015 -0400
             
                interpolate: fix off-by-one bug in InterpolateConstant
                
                Nate Lust found an "invalid read" in the "recenter" function
                when running Valgrind on a test of PSFEx.  Inspection of the
                code found that we were running off the end of the array.
                This error is not (in general) reproduced by running valgrind
                on afw's interpolate.py test, probably because we're getting
                more space back from the standard library than we ask for.
                Changing the test to use 8 or 16 values allows valgrind to
                see the error, which goes away with this fix, but I've not
                modified the test.
             
            diff --git a/src/math/Interpolate.cc b/src/math/Interpolate.cc
            index 50e1738..4b01742 100644
            --- a/src/math/Interpolate.cc
            +++ b/src/math/Interpolate.cc
            @@ -54,7 +54,7 @@ namespace {
                                           str(boost::format("Dimensions of x and y must match; %ul != %ul")
                                               % x.size() % y.size()));
                     }
            -        unsigned int const len = x.size();
            +        std::size_t const len = x.size();
                     if (len == 0) {
                         throw LSST_EXCEPT(pex::exceptions::InvalidParameterError,
                                           "You must provide at least 1 point");
            @@ -65,17 +65,15 @@ namespace {
                     std::vector<double> recentered_x(len + 1);
                     std::vector<double> recentered_y(len + 1);
             
            -        int j = 0; 
            -        recentered_x[j] = 0.5*(3*x[0] - x[1]);
            -        recentered_y[j] = y[0];
            +        recentered_x[0] = 0.5*(3*x[0] - x[1]);
            +        recentered_y[0] = y[0];
             
            -        for (unsigned int i = 0; i < x.size(); ++i) {
            -            ++j;
            +        for (std::size_t i = 0, j = 1; i < len - 1; ++i, ++j) {
                         recentered_x[j] = 0.5*(x[i] + x[i + 1]);
                         recentered_y[j] = 0.5*(y[i] + y[i + 1]);
                     }
            -        recentered_x[j] = 0.5*(3*x[len - 1] - x[len - 2]);
            -        recentered_y[j] = y[len - 1];
            +        recentered_x[len] = 0.5*(3*x[len - 1] - x[len - 2]);
            +        recentered_y[len] = y[len - 1];
             
                     return std::make_pair(recentered_x, recentered_y);        
                 }
            

            Show
            price Paul Price added a comment - Test passes now: pprice@tiger-sumire:~/LSST/afw (tickets/DM-3112=) $ git --no-pager log --patch --reverse origin/master.. commit 518fe3cd0bf4b4e01bf130d4fc9f51c486fe6b30 Author: Paul Price <price@astro.princeton.edu> Date: Fri Jul 10 14:12:43 2015 -0400   interpolate: fix off-by-one bug in InterpolateConstant Nate Lust found an "invalid read" in the "recenter" function when running Valgrind on a test of PSFEx. Inspection of the code found that we were running off the end of the array. This error is not (in general) reproduced by running valgrind on afw's interpolate.py test, probably because we're getting more space back from the standard library than we ask for. Changing the test to use 8 or 16 values allows valgrind to see the error, which goes away with this fix, but I've not modified the test.   diff --git a/src/math/Interpolate.cc b/src/math/Interpolate.cc index 50e1738..4b01742 100644 --- a/src/math/Interpolate.cc +++ b/src/math/Interpolate.cc @@ -54,7 +54,7 @@ namespace { str(boost::format("Dimensions of x and y must match; %ul != %ul") % x.size() % y.size())); } - unsigned int const len = x.size(); + std::size_t const len = x.size(); if (len == 0) { throw LSST_EXCEPT(pex::exceptions::InvalidParameterError, "You must provide at least 1 point"); @@ -65,17 +65,15 @@ namespace { std::vector<double> recentered_x(len + 1); std::vector<double> recentered_y(len + 1); - int j = 0; - recentered_x[j] = 0.5*(3*x[0] - x[1]); - recentered_y[j] = y[0]; + recentered_x[0] = 0.5*(3*x[0] - x[1]); + recentered_y[0] = y[0]; - for (unsigned int i = 0; i < x.size(); ++i) { - ++j; + for (std::size_t i = 0, j = 1; i < len - 1; ++i, ++j) { recentered_x[j] = 0.5*(x[i] + x[i + 1]); recentered_y[j] = 0.5*(y[i] + y[i + 1]); } - recentered_x[j] = 0.5*(3*x[len - 1] - x[len - 2]); - recentered_y[j] = y[len - 1]; + recentered_x[len] = 0.5*(3*x[len - 1] - x[len - 2]); + recentered_y[len] = y[len - 1]; return std::make_pair(recentered_x, recentered_y); }
            Hide
            swinbank John Swinbank added a comment -

            Looks good. Nice catch both!

            Show
            swinbank John Swinbank added a comment - Looks good. Nice catch both!
            Hide
            nlust Nate Lust added a comment -

            you may have already merged this, but I got it built. The changes look good and I can verify the tests run.

            Show
            nlust Nate Lust added a comment - you may have already merged this, but I got it built. The changes look good and I can verify the tests run.
            Hide
            price Paul Price added a comment -

            Thanks, both.

            Merged to master.

            Show
            price Paul Price added a comment - Thanks, both. Merged to master.

              People

              • Assignee:
                price Paul Price
                Reporter:
                price Paul Price
                Reviewers:
                John Swinbank, Nate Lust
                Watchers:
                John Swinbank, Nate Lust, Paul Price
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:

                  Summary Panel