Full_Name: Sergio Gelato Version: 2.4.40 OS: Linux URL: ftp://ftp.openldap.org/incoming/ Submission from: (NULL) (85.225.123.9) As currently implemented (since ITS#7027, 5de85b922aaa5bfa6eb53db6000adf01ebdb0736) the algorithm to shuffle DNS SRV records of a given priority according to their weights is flawed: if all records have the same weight, the implementation is biased towards the first record and against the last. In the most extreme case of two records of weight 1, the current implementation will never swap them (whereas one would have hoped for a swap 50% of the time). The problem can be cured by changing (r <= 0) to (r < 0). (The wording of the RFC may have contributed to this error; I suspect it was written with real random deviates in mind, not integer ones. In any event, the principle that records of equal weight should have the same probability of being picked trumps the RFC since the latter only says what algorithm SHOULD be used.) I've written and tested a patch for this and found it to solve the above problem. My patch also addresses another (operationally minor, which is why I'm not reporting it separately) issue in the same piece of code: what if at least two, but not all, of the records of a given priority have weight zero? One should be prepared to switch to a Fisher-Yates shuffle if "total" becomes zero during the iteration. (Yet another potential issue is overflow of "total" on platforms where INT_MAX==32767 if the sum of the weights exceeds that value. Consider declaring it uint32_t or u_long.)
Sergio.Gelato@astro.su.se wrote: > Full_Name: Sergio Gelato > Version: 2.4.40 > OS: Linux > URL: ftp://ftp.openldap.org/incoming/ > Submission from: (NULL) (85.225.123.9) > > > As currently implemented (since ITS#7027, > 5de85b922aaa5bfa6eb53db6000adf01ebdb0736) the algorithm to shuffle DNS SRV > records of a given priority according to their weights is flawed: if all records > have the same weight, the implementation is biased towards the first record and > against the last. In the most extreme case of two records of weight 1, the > current implementation will never swap them (whereas one would have hoped for a > swap 50% of the time). The problem can be cured by changing (r <= 0) to (r < 0). > (The wording of the RFC may have contributed to this error; I suspect it was > written with real random deviates in mind, not integer ones. In any event, the > principle that records of equal weight should have the same probability of being > picked trumps the RFC since the latter only says what algorithm SHOULD be > used.) > > I've written and tested a patch for this and found it to solve the above > problem. My patch also addresses another (operationally minor, which is why I'm > not reporting it separately) issue in the same piece of code: what if at least > two, but not all, of the records of a given priority have weight zero? One > should be prepared to switch to a Fisher-Yates shuffle if "total" becomes zero > during the iteration. > > (Yet another potential issue is overflow of "total" on platforms where > INT_MAX==32767 if the sum of the weights exceeds that value. Consider declaring > it uint32_t or u_long.) I see no patch nor URL. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/
Sorry for the delay in submitting the patch. I wanted to double-check that no third party would lay a credible claim to it. For good measure, I have split the patch in two: the first only addresses the primary issue, and is obviously too simple to be copyrightable. The second addresses the need for falling back to straight Fisher-Yates in the middle of the shuffle, and may or may not be copyrightable so I'll say this: The attached patch files are derived from OpenLDAP Software. All of the modifications to OpenLDAP Software represented therein were developed by me, Sergio Gelato. I have not assigned rights and/or interest in this work to any party. The modifications are subject to the following notice: Copyright 2015 Sergio Gelato Redistribution and use in source and binary forms, with or without modification, are permitted according to the terms of the OpenLDAP Public License.
moved from Incoming to Software Bugs
Patch is part of the merge request here: https://git.openldap.org/openldap/openldap/-/merge_requests/80
• ee7502ac by Sergio Gelato at 2020-06-22T17:27:30+00:00 ITS#8204 Remove bias towards the first record in RFC2782 shuffle implementation. Prior to this change, given two records of weight 1 the algorithm would return them in the order (0,1) with 100% probability instead of the desired 50%. This was due to an off-by-one error in the range test. srv_rand() returns a float in the range [0.0, 1.0[, so r is an integer in the range [0, total[. The correct probability for record 0 to be chosen is a[0].weight/total, not (a[0].weight+1)/total. • 8006ee58 by Sergio Gelato at 2020-06-22T17:27:30+00:00 ITS#8204 Improved RFC2782 shuffle when several, but not all, records have weight 0. The fallback to a straight Fisher-Yates shuffle needs to occur whenever the sum of the *remaining* weights is zero, or else the remaining records will not be reordered. Testing only once at the beginning covers the case when all weights are zero, and obviously no shuffling is needed when only one weight is zero; but other weight combinations are possible, such as (1, 0, 0).