Uploaded image for project: 'Groovy'
  1. Groovy
  2. GROOVY-7530

disjoint() does not work correctly if objects don't implement Comparable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 2.4.4
    • Fix Version/s: 2.4.7
    • Component/s: groovy-runtime
    • Labels:
      None

      Description

      class Foo {
      
          private String name
      
          Foo(String name) {
              this.name = name
          }
      
          public boolean equals(Object o) {
              if (this == o) return true
              if (o == null || getClass() != o.getClass()) return false
              Foo that = (Foo) o
              return Objects.equals(name, that.name)
          }
      
          public int hashCode() {
              return Objects.hash(name)
          }
      
      }
      
      def a = [new Foo("foo")]
      def b = [new Foo("foo")]    
      assert !a.disjoint(b)
      

      If disjoint() is used on a list with objects not implementing Comparable the wrong result is returned.
      intersect() shows the same wrong behavior.

      It's looks like the NumberAwareComparator not implementing the equals case as of commit 286532c is the problem.

        Issue Links

          Activity

          Hide
          jeegar12 Jeegar added a comment -

          Please would you make this Fix ASAP, as this is causing vulnerability issues in our project.

          Show
          jeegar12 Jeegar added a comment - Please would you make this Fix ASAP, as this is causing vulnerability issues in our project.
          Hide
          blackdrag Jochen Theodorou added a comment -

          If it is non-static Groovy code calling the method, you can provide your own extension module to provide this method by yourself and overwrite the version in the runtime as at quick fix. As for the vulnerability, it would be nice to have explained how. Because otherwise a fix of this (if done), may not fix your problem.

          Show
          blackdrag Jochen Theodorou added a comment - If it is non-static Groovy code calling the method, you can provide your own extension module to provide this method by yourself and overwrite the version in the runtime as at quick fix. As for the vulnerability, it would be nice to have explained how. Because otherwise a fix of this (if done), may not fix your problem.
          Hide
          kekekevin Kevin Tung added a comment -
          compare.groovy
          class Foo {
          
              private String name
          
              Foo(String name) {
                  this.name = name
              }
          
              boolean equals(o) {
                  if (this.is(o)) return true
                  if (getClass() != o.class) return false
          
                  Foo that = (Foo) o
          
                  if (name != that.name) return false
          
                  return true
              }
          
              int hashCode() {
                  return Objects.hash(name)
              }
          
          }
          
          
          def a = [new Foo("foo")]
          def b = [new Foo("foo")] as Object[]
          
          a.removeAll(b)
          assert !a
          
          def c = [new Foo("foo")]
          def d = [new Foo("foo")] as Object[]
          
          c.retainAll(d)
          assert c
          

          Seems like this will also fail for certain implementations of removeAll and retainAll. Since NumberAwareComparator seems to be the root cause of this issue, there could be quite a few extension methods required to workaround this issue. Would you happen to know if there are additional instances where NumberAwareComparator is the only source of comparison?

          Also, while it may be possible to implement Comparable on objects in which I control the source, any objects that are imported are beyond my control.

          Show
          kekekevin Kevin Tung added a comment - compare.groovy class Foo { private String name Foo( String name) { this .name = name } boolean equals(o) { if ( this .is(o)) return true if (getClass() != o.class) return false Foo that = (Foo) o if (name != that.name) return false return true } int hashCode() { return Objects.hash(name) } } def a = [ new Foo( "foo" )] def b = [ new Foo( "foo" )] as Object [] a.removeAll(b) assert !a def c = [ new Foo( "foo" )] def d = [ new Foo( "foo" )] as Object [] c.retainAll(d) assert c Seems like this will also fail for certain implementations of removeAll and retainAll. Since NumberAwareComparator seems to be the root cause of this issue, there could be quite a few extension methods required to workaround this issue. Would you happen to know if there are additional instances where NumberAwareComparator is the only source of comparison? Also, while it may be possible to implement Comparable on objects in which I control the source, any objects that are imported are beyond my control.
          Hide
          jeegar12 Jeegar added a comment -

          I agree with Kevin on this!
          Can we get this fixed at the base class level?

          Show
          jeegar12 Jeegar added a comment - I agree with Kevin on this! Can we get this fixed at the base class level?
          Hide
          apreston Andrew Preston added a comment -

          Hi Tobias - would you be able to raise this fix for priority? We need to remediate vulnerability issues asap.

          Show
          apreston Andrew Preston added a comment - Hi Tobias - would you be able to raise this fix for priority? We need to remediate vulnerability issues asap.
          Hide
          paulk Paul King added a comment -

          I'm still keen to understand if there is a vulnerability issue. Jeegar can you elaborate further? Do you mean security vulnerability? Or just that it doesn't behave as you expected?

          Show
          paulk Paul King added a comment - I'm still keen to understand if there is a vulnerability issue. Jeegar can you elaborate further? Do you mean security vulnerability? Or just that it doesn't behave as you expected?
          Hide
          blackdrag Jochen Theodorou added a comment -

          if there is an issue about talking about the security problem per se, then I suggest mailing either us directly by mail or to use the apache security infrastructure through http://www.apache.org/security/

          Show
          blackdrag Jochen Theodorou added a comment - if there is an issue about talking about the security problem per se, then I suggest mailing either us directly by mail or to use the apache security infrastructure through http://www.apache.org/security/
          Hide
          apreston Andrew Preston added a comment -

          Paul/Jochen - apologies for the lack of clarity. In order to mitigate a security vulernability with Groovy 1.7.0 through 2.4.3 (CVE-2015-3253) we attempted to upgrade to 2.4.4 where we are running into this disjoint not working properly. I will defer to Jeegar to clarify his comment.

          Show
          apreston Andrew Preston added a comment - Paul/Jochen - apologies for the lack of clarity. In order to mitigate a security vulernability with Groovy 1.7.0 through 2.4.3 (CVE-2015-3253) we attempted to upgrade to 2.4.4 where we are running into this disjoint not working properly. I will defer to Jeegar to clarify his comment.
          Hide
          blackdrag Jochen Theodorou added a comment -

          Ok, thanks for the clarification. We had been very very much irritated by this code causing a vulnerability issue. It is not out of question, since the example exploit for CVE-2015-3253 you mentioned actually does misuse a sorting structure in Java for the exploit. so I could not totally exclude such a possibility.

          Anyway... back to the problem.

          def a = [new Foo("foo")]
          def b = [new Foo("foo")]    
          assert !a.disjoint(b)
          

          The basic problem is as follows.. if the objects are somehow comparable, then you can do disjoint in O(nlogn), by first sorting one and then checking against the other. If the objects are not comparable and if I can only check for equality, then I am required to use an O(n*n) approach, by checking each elements of one list, against each of the other.. well it is more like n*n/2, but that does not matter when looking at the complexity. So in older versions we first did check both lists if all elements are Comparable, to then later decide on the strategy and go with the nlogn of the n*n variant. But this approach did also not get the desired results, as can be seen in the test in 286532c

          But I am wondering now... maybe the better approach is to add one more check like

          if (o1.getClass()==o2.getClass() && (o1.equals(o2)) return 0;
          

          But I wonder what we are supposed to return if equals gives false. If we say we return only 0, we could also think about removing the class check. or we keep the class check and return -1 in case of equals returning false.

          Show
          blackdrag Jochen Theodorou added a comment - Ok, thanks for the clarification. We had been very very much irritated by this code causing a vulnerability issue. It is not out of question, since the example exploit for CVE-2015-3253 you mentioned actually does misuse a sorting structure in Java for the exploit. so I could not totally exclude such a possibility. Anyway... back to the problem. def a = [ new Foo( "foo" )] def b = [ new Foo( "foo" )] assert !a.disjoint(b) The basic problem is as follows.. if the objects are somehow comparable, then you can do disjoint in O(nlogn), by first sorting one and then checking against the other. If the objects are not comparable and if I can only check for equality, then I am required to use an O(n*n) approach, by checking each elements of one list, against each of the other.. well it is more like n*n/2, but that does not matter when looking at the complexity. So in older versions we first did check both lists if all elements are Comparable, to then later decide on the strategy and go with the nlogn of the n*n variant. But this approach did also not get the desired results, as can be seen in the test in 286532c But I am wondering now... maybe the better approach is to add one more check like if (o1.getClass()==o2.getClass() && (o1.equals(o2)) return 0; But I wonder what we are supposed to return if equals gives false. If we say we return only 0, we could also think about removing the class check. or we keep the class check and return -1 in case of equals returning false.
          Hide
          kekekevin Kevin Tung added a comment -

          The additional check you have outlined makes sense to me, but I think you might be able to drop the class check and defer that responsibility to equals(). If equals() returns false then return -1 would seem safe.

          Show
          kekekevin Kevin Tung added a comment - The additional check you have outlined makes sense to me, but I think you might be able to drop the class check and defer that responsibility to equals(). If equals() returns false then return -1 would seem safe.
          Hide
          kekekevin Kevin Tung added a comment -

          Hm another consideration would be for the scenario in which the equals() is an expensive operation is that this additional check might only be warranted if the hashCodes are equal.

          Show
          kekekevin Kevin Tung added a comment - Hm another consideration would be for the scenario in which the equals() is an expensive operation is that this additional check might only be warranted if the hashCodes are equal.
          Hide
          blackdrag Jochen Theodorou added a comment -

          yes, also a good idea... I do like this more, because it preserves that hashcode order in case of unrelated objects

          Show
          blackdrag Jochen Theodorou added a comment - yes, also a good idea... I do like this more, because it preserves that hashcode order in case of unrelated objects
          Hide
          apreston Andrew Preston added a comment -

          All - I see the fix version was removed. Is there a future release date targeted for this fix?

          Show
          apreston Andrew Preston added a comment - All - I see the fix version was removed. Is there a future release date targeted for this fix?
          Hide
          paulk Paul King added a comment -

          We use the fix date to record the actual version in which it was fixed not the target one - unless it is a blocker when the two should coincide.

          Show
          paulk Paul King added a comment - We use the fix date to record the actual version in which it was fixed not the target one - unless it is a blocker when the two should coincide.
          Hide
          githubbot ASF GitHub Bot added a comment -

          GitHub user paulk-asert opened a pull request:

          https://github.com/apache/groovy/pull/276

          GROOVY-7530 and GROOVY-7602: intersect and disjoint broken for non-Co…

          …mparable objects (closes #276)

          You can merge this pull request into a Git repository by running:

          $ git pull https://github.com/paulk-asert/groovy groovy7530

          Alternatively you can review and apply these changes as the patch at:

          https://github.com/apache/groovy/pull/276.patch

          To close this pull request, make a commit to your master/trunk branch
          with (at least) the following in the commit message:

          This closes #276


          commit d3692554fc6792b6e59dc9691dfbc1add168c86c
          Author: paulk <paulk@asert.com.au>
          Date: 2016-03-02T11:37:07Z

          GROOVY-7530 and GROOVY-7602: intersect and disjoint broken for non-Comparable objects (closes #276)


          Show
          githubbot ASF GitHub Bot added a comment - GitHub user paulk-asert opened a pull request: https://github.com/apache/groovy/pull/276 GROOVY-7530 and GROOVY-7602 : intersect and disjoint broken for non-Co… …mparable objects (closes #276) You can merge this pull request into a Git repository by running: $ git pull https://github.com/paulk-asert/groovy groovy7530 Alternatively you can review and apply these changes as the patch at: https://github.com/apache/groovy/pull/276.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #276 commit d3692554fc6792b6e59dc9691dfbc1add168c86c Author: paulk <paulk@asert.com.au> Date: 2016-03-02T11:37:07Z GROOVY-7530 and GROOVY-7602 : intersect and disjoint broken for non-Comparable objects (closes #276)
          Hide
          paulk Paul King added a comment -

          If I understood all the earlier comments, PR#276 should be what we require.

          Show
          paulk Paul King added a comment - If I understood all the earlier comments, PR#276 should be what we require.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user asfgit closed the pull request at:

          https://github.com/apache/groovy/pull/276

          Show
          githubbot ASF GitHub Bot added a comment - Github user asfgit closed the pull request at: https://github.com/apache/groovy/pull/276
          Hide
          paulk Paul King added a comment -

          merged PR

          Show
          paulk Paul King added a comment - merged PR
          Hide
          apreston Andrew Preston added a comment -

          Hi All -

          I see this is merged to fix version 2.4.7 - can you confirm when this will be released and available for download?

          Thanks
          Andre

          Show
          apreston Andrew Preston added a comment - Hi All - I see this is merged to fix version 2.4.7 - can you confirm when this will be released and available for download? Thanks Andre
          Hide
          paulk Paul King added a comment -

          There is no date set at this stage. There are over twenty bug fixes already, so it would be good if we can do another release not too far down the track. You can grab snapshot artifacts in the meantime if you want.

          Show
          paulk Paul King added a comment - There is no date set at this stage. There are over twenty bug fixes already, so it would be good if we can do another release not too far down the track. You can grab snapshot artifacts in the meantime if you want.

            People

            • Assignee:
              paulk Paul King
              Reporter:
              tahlers Tobias Ahlers
            • Votes:
              5 Vote for this issue
              Watchers:
              8 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development