Author: thebeing
Date: Tue Mar 10 12:43:03 2015
New Revision: 38391
URL: http://svn.gna.org/viewcvs/gnustep?rev=38391&view=rev
Log:
Fix a vulnerability in the timsort algorithm where an algorithmic problem
caused an
invariant to no longer hold for certain inputs, potentially leading to a read
beyond
an array boundary (result in a segfault under our implementation).
See
http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
for an in-depth explanation of the problem. Also: ‘Yeah!’ for formal
verification!
Modified:
libs/base/trunk/ChangeLog
libs/base/trunk/Source/GSTimSort.m
Modified: libs/base/trunk/ChangeLog
URL:
http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/ChangeLog?rev=38391&r1=38390&r2=38391&view=diff
==============================================================================
--- libs/base/trunk/ChangeLog (original)
+++ libs/base/trunk/ChangeLog Tue Mar 10 12:43:03 2015
@@ -1,3 +1,10 @@
+2015-03-10 Niels Grewe <[email protected]>
+
+ * Source/GSTimSort.m: Fix a DoS vulnerability discovered in the
+ Timsort algorithm. For information about the problem please refer to
+ http://www.envisage-project.eu/proving-android-java-and-python-sorting
+ -algorithm-is-broken-and-how-to-fix-it/
+
2015-03-08 Richard Frith-Macdonald <[email protected]>
* Source/NSFileHandle.m: ([-sslHandshakeEstablished:outgoing:])
Modified: libs/base/trunk/Source/GSTimSort.m
URL:
http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Source/GSTimSort.m?rev=38391&r1=38390&r2=38391&view=diff
==============================================================================
--- libs/base/trunk/Source/GSTimSort.m (original)
+++ libs/base/trunk/Source/GSTimSort.m Tue Mar 10 12:43:03 2015
@@ -615,38 +615,36 @@
NSDebugMLLog(@"GSTimSort", @"Pushing run: %@", NSStringFromRange(r));
}
+/**
+ * Ensure that the invariant enabling the algorithm holds for the stack.
+ *
+ * see:
http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/#sec3
+ */
- (void) suggestMerge
{
while (stackSize > 1)
{
NSInteger n = stackSize -2;
-
- if (n > 0)
- {
- NSUInteger topLen = runStack[n+1].length;
- NSUInteger midLen = runStack[n].length;
- NSUInteger botLen = runStack[n-1].length;
- if (botLen <= (midLen + topLen))
- {
- if (botLen < topLen)
- {
- n--;
- }
- GS_TIMSORT_MERGE_AT_INDEX(self, n);
+ if ( (n >= 1
+ && runStack[n-1].length <= (runStack[n].length
+ + runStack[n+1].length)
+ )
+ || (n >= 2
+ && runStack[n-2].length <= (runStack[n].length
+ + runStack[n-1].length)
+ )
+ )
+ {
+ if (runStack[n-1].length < runStack[n+1].length)
+ {
+ n--;
}
- else if (midLen <= topLen)
- {
- GS_TIMSORT_MERGE_AT_INDEX(self, n);
- }
- else
- {
- break;
- }
- }
- else
- {
- break;
- }
+ }
+ else if (runStack[n].length > runStack[n+1].length)
+ {
+ break; //invariant reached
+ }
+ GS_TIMSORT_MERGE_AT_INDEX(self, n);
}
}
_______________________________________________
Gnustep-cvs mailing list
[email protected]
https://mail.gna.org/listinfo/gnustep-cvs
