September 2018 - tor-commits - lists.torproject.org

[tor/master] rust/protover: add ProtoSet::and_not_in()
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 578f7326eda7307c420286c01b57f71925901533 Author: cypherpunks <cypherpunks(a)torproject.org> Date: Thu Aug 9 21:25:18 2018 +0000 rust/protover: add ProtoSet::and_not_in() This is a way more efficient version of retain(). --- src/rust/protover/protoset.rs | 53 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) diff --git a/src/rust/protover/protoset.rs b/src/rust/protover/protoset.rs index b99e1a99f..27c16c700 100644 --- a/src/rust/protover/protoset.rs +++ b/src/rust/protover/protoset.rs @@ -4,6 +4,8 @@ //! Sets for lazily storing ordered, non-overlapping ranges of integers. +use std::cmp; +use std::iter; use std::slice; use std::str::FromStr; use std::u32; @@ -269,6 +271,57 @@ impl ProtoSet { expanded.retain(f); *self = expanded.into(); } + + /// Returns all the `Version`s in `self` which are not also in the `other` + /// `ProtoSet`. + /// + /// # Examples + /// + /// ``` + /// # use protover::errors::ProtoverError; + /// use protover::protoset::ProtoSet; + /// + /// # fn do_test() -> Result<bool, ProtoverError> { + /// let protoset: ProtoSet = "1,3-6,10-12,15-16".parse()?; + /// let other: ProtoSet = "2,5-7,9-11,14-20".parse()?; + /// + /// let subset: ProtoSet = protoset.and_not_in(&other); + /// + /// assert_eq!(subset.expand(), vec![1, 3, 4, 12]); + /// # + /// # Ok(true) + /// # } + /// # fn main() { do_test(); } // wrap the test so we can use the ? operator + /// ``` + pub fn and_not_in(&self, other: &Self) -> Self { + if self.is_empty() || other.is_empty() { + return self.clone(); + } + + let pairs = self.iter().flat_map(|&(lo, hi)| { + let the_end = (hi + 1, hi + 1); // special case to mark the end of the range. + let excluded_ranges = other + .iter() + .cloned() // have to be owned tuples, to match iter::once(the_end). + .skip_while(move|&(_, hi2)| hi2 < lo) // skip the non-overlapping ranges. + .take_while(move|&(lo2, _)| lo2 <= hi) // take all the overlapping ones. + .chain(iter::once(the_end)); + + let mut nextlo = lo; + excluded_ranges.filter_map(move |(excluded_lo, excluded_hi)| { + let pair = if nextlo < excluded_lo { + Some((nextlo, excluded_lo - 1)) + } else { + None + }; + nextlo = cmp::min(excluded_hi, u32::MAX - 1) + 1; + pair + }) + }); + + let pairs = pairs.collect(); + ProtoSet::is_ok(ProtoSet{ pairs }).expect("should be already sorted") + } } impl FromStr for ProtoSet {

1 0

[tor/maint-0.3.4] rust/protover: use .and_not_in() instead of .retain() in all_supported()
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit c613d5513491861431c2852cf4072ae256ba2c67 Author: cypherpunks <cypherpunks(a)torproject.org> Date: Thu Aug 9 21:26:10 2018 +0000 rust/protover: use .and_not_in() instead of .retain() in all_supported() .retain() would allocating a Vec of billions of integers and check them one at a time to separate the supported versions from the unsupported. This leads to a memory DoS. Closes ticket 27206. Bugfix on e6625113c98c281b0a649598d7daa347c28915e9. --- changes/bug27206 | 4 ++++ src/rust/protover/protover.rs | 4 +--- src/rust/protover/tests/protover.rs | 8 ++++---- 3 files changed, 9 insertions(+), 7 deletions(-) diff --git a/changes/bug27206 b/changes/bug27206 new file mode 100644 index 000000000..c0fbbed70 --- /dev/null +++ b/changes/bug27206 @@ -0,0 +1,4 @@ + o Minor bugfixes (rust): + - protover_all_supported() would attempt to allocate up to 16GB on some + inputs, leading to a potential memory DoS. Fixes bug 27206; bugfix on + 0.3.3.5-rc. diff --git a/src/rust/protover/protover.rs b/src/rust/protover/protover.rs index b3563b063..c11c7c180 100644 --- a/src/rust/protover/protover.rs +++ b/src/rust/protover/protover.rs @@ -365,7 +365,6 @@ impl UnvalidatedProtoEntry { let maybe_supported_versions: Option<&ProtoSet> = supported.get(&supported_protocol); let supported_versions: &ProtoSet; - let mut unsupported_versions: ProtoSet; // If the protocol wasn't in the map, then we don't know about it // and don't support any of its versions. Add its versions to the @@ -378,8 +377,7 @@ impl UnvalidatedProtoEntry { } else { supported_versions = maybe_supported_versions.unwrap(); } - unsupported_versions = versions.clone(); - unsupported_versions.retain(|x| !supported_versions.contains(x)); + let unsupported_versions = versions.and_not_in(supported_versions); if !unsupported_versions.is_empty() { unsupported.insert(protocol.clone(), unsupported_versions); diff --git a/src/rust/protover/tests/protover.rs b/src/rust/protover/tests/protover.rs index 59a4b5a8a..9258d869d 100644 --- a/src/rust/protover/tests/protover.rs +++ b/src/rust/protover/tests/protover.rs @@ -354,18 +354,18 @@ fn protover_all_supported_should_exclude_some_versions_and_entire_protocols() { #[test] fn protover_all_supported_should_not_dos_anyones_computer() { - let proto: UnvalidatedProtoEntry = "Sleen=1-2147483648".parse().unwrap(); + let proto: UnvalidatedProtoEntry = "Link=1-2147483648".parse().unwrap(); let result: String = proto.all_supported().unwrap().to_string(); - assert_eq!(result, "Sleen=1-2147483648".to_string()); + assert_eq!(result, "Link=6-2147483648".to_string()); } #[test] fn protover_all_supported_should_not_dos_anyones_computer_max_versions() { - let proto: UnvalidatedProtoEntry = "Sleen=1-4294967294".parse().unwrap(); + let proto: UnvalidatedProtoEntry = "Link=1-4294967294".parse().unwrap(); let result: String = proto.all_supported().unwrap().to_string(); - assert_eq!(result, "Sleen=1-4294967294".to_string()); + assert_eq!(result, "Link=6-4294967294".to_string()); } #[test]

1 0

[tor/maint-0.3.4] rust/protover: delete ProtoSet::retain
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 5c47f725b0e1628aab1d6f5b43dc32a493ce58e8 Author: cypherpunks <cypherpunks(a)torproject.org> Date: Wed Aug 15 03:23:08 2018 +0000 rust/protover: delete ProtoSet::retain As the comment noted, it was horribly inefficient. --- src/rust/protover/protoset.rs | 30 ------------------------------ 1 file changed, 30 deletions(-) diff --git a/src/rust/protover/protoset.rs b/src/rust/protover/protoset.rs index 27c16c700..465b8f285 100644 --- a/src/rust/protover/protoset.rs +++ b/src/rust/protover/protoset.rs @@ -242,36 +242,6 @@ impl ProtoSet { false } - /// Retain only the `Version`s in this `ProtoSet` for which the predicate - /// `F` returns `true`. - /// - /// # Examples - /// - /// ``` - /// # use protover::errors::ProtoverError; - /// use protover::protoset::ProtoSet; - /// - /// # fn do_test() -> Result<bool, ProtoverError> { - /// let mut protoset: ProtoSet = "1,3-5,9".parse()?; - /// - /// // Keep only versions less than or equal to 8: - /// protoset.retain(|x| x <= &8); - /// - /// assert_eq!(protoset.expand(), vec![1, 3, 4, 5]); - /// # - /// # Ok(true) - /// # } - /// # fn main() { do_test(); } // wrap the test so we can use the ? operator - /// ``` - // XXX we could probably do something more efficient here. —isis - pub fn retain<F>(&mut self, f: F) - where F: FnMut(&Version) -> bool - { - let mut expanded: Vec<Version> = self.clone().expand(); - expanded.retain(f); - *self = expanded.into(); - } - /// Returns all the `Version`s in `self` which are not also in the `other` /// `ProtoSet`. ///

1 0

[tor/maint-0.3.4] Merge remote-tracking branch 'onionk/rust-allsupported1' into maint-0.3.3
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 75b95e1c8e28e1136b5bc98fd89321e478f4b836 Merge: a546e0760 5c47f725b Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Sep 18 08:31:08 2018 -0400 Merge remote-tracking branch 'onionk/rust-allsupported1' into maint-0.3.3 changes/bug27206 | 4 +++ src/rust/protover/protoset.rs | 49 +++++++++++++++++++++++++++---------- src/rust/protover/protover.rs | 4 +-- src/rust/protover/tests/protover.rs | 8 +++--- 4 files changed, 45 insertions(+), 20 deletions(-)

1 0

[tor/maint-0.3.4] Merge branch 'maint-0.3.3' into maint-0.3.4
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 2ddbaf9cdc3c850a56ef1f3bf6977c903e24bb39 Merge: 6f47734ea 75b95e1c8 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Sep 18 08:31:14 2018 -0400 Merge branch 'maint-0.3.3' into maint-0.3.4 changes/bug27206 | 4 +++ src/rust/protover/protoset.rs | 49 +++++++++++++++++++++++++++---------- src/rust/protover/protover.rs | 4 +-- src/rust/protover/tests/protover.rs | 8 +++--- 4 files changed, 45 insertions(+), 20 deletions(-)

1 0

[tor/master] Merge remote-tracking branch 'onionk/rust-allsupported1' into maint-0.3.3
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 75b95e1c8e28e1136b5bc98fd89321e478f4b836 Merge: a546e0760 5c47f725b Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Sep 18 08:31:08 2018 -0400 Merge remote-tracking branch 'onionk/rust-allsupported1' into maint-0.3.3 changes/bug27206 | 4 +++ src/rust/protover/protoset.rs | 49 +++++++++++++++++++++++++++---------- src/rust/protover/protover.rs | 4 +-- src/rust/protover/tests/protover.rs | 8 +++--- 4 files changed, 45 insertions(+), 20 deletions(-)

1 0

[tor/master] rust/protover: use .and_not_in() instead of .retain() in all_supported()
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit c613d5513491861431c2852cf4072ae256ba2c67 Author: cypherpunks <cypherpunks(a)torproject.org> Date: Thu Aug 9 21:26:10 2018 +0000 rust/protover: use .and_not_in() instead of .retain() in all_supported() .retain() would allocating a Vec of billions of integers and check them one at a time to separate the supported versions from the unsupported. This leads to a memory DoS. Closes ticket 27206. Bugfix on e6625113c98c281b0a649598d7daa347c28915e9. --- changes/bug27206 | 4 ++++ src/rust/protover/protover.rs | 4 +--- src/rust/protover/tests/protover.rs | 8 ++++---- 3 files changed, 9 insertions(+), 7 deletions(-) diff --git a/changes/bug27206 b/changes/bug27206 new file mode 100644 index 000000000..c0fbbed70 --- /dev/null +++ b/changes/bug27206 @@ -0,0 +1,4 @@ + o Minor bugfixes (rust): + - protover_all_supported() would attempt to allocate up to 16GB on some + inputs, leading to a potential memory DoS. Fixes bug 27206; bugfix on + 0.3.3.5-rc. diff --git a/src/rust/protover/protover.rs b/src/rust/protover/protover.rs index b3563b063..c11c7c180 100644 --- a/src/rust/protover/protover.rs +++ b/src/rust/protover/protover.rs @@ -365,7 +365,6 @@ impl UnvalidatedProtoEntry { let maybe_supported_versions: Option<&ProtoSet> = supported.get(&supported_protocol); let supported_versions: &ProtoSet; - let mut unsupported_versions: ProtoSet; // If the protocol wasn't in the map, then we don't know about it // and don't support any of its versions. Add its versions to the @@ -378,8 +377,7 @@ impl UnvalidatedProtoEntry { } else { supported_versions = maybe_supported_versions.unwrap(); } - unsupported_versions = versions.clone(); - unsupported_versions.retain(|x| !supported_versions.contains(x)); + let unsupported_versions = versions.and_not_in(supported_versions); if !unsupported_versions.is_empty() { unsupported.insert(protocol.clone(), unsupported_versions); diff --git a/src/rust/protover/tests/protover.rs b/src/rust/protover/tests/protover.rs index 59a4b5a8a..9258d869d 100644 --- a/src/rust/protover/tests/protover.rs +++ b/src/rust/protover/tests/protover.rs @@ -354,18 +354,18 @@ fn protover_all_supported_should_exclude_some_versions_and_entire_protocols() { #[test] fn protover_all_supported_should_not_dos_anyones_computer() { - let proto: UnvalidatedProtoEntry = "Sleen=1-2147483648".parse().unwrap(); + let proto: UnvalidatedProtoEntry = "Link=1-2147483648".parse().unwrap(); let result: String = proto.all_supported().unwrap().to_string(); - assert_eq!(result, "Sleen=1-2147483648".to_string()); + assert_eq!(result, "Link=6-2147483648".to_string()); } #[test] fn protover_all_supported_should_not_dos_anyones_computer_max_versions() { - let proto: UnvalidatedProtoEntry = "Sleen=1-4294967294".parse().unwrap(); + let proto: UnvalidatedProtoEntry = "Link=1-4294967294".parse().unwrap(); let result: String = proto.all_supported().unwrap().to_string(); - assert_eq!(result, "Sleen=1-4294967294".to_string()); + assert_eq!(result, "Link=6-4294967294".to_string()); } #[test]

1 0

[tor/master] rust/protover: delete ProtoSet::retain
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 5c47f725b0e1628aab1d6f5b43dc32a493ce58e8 Author: cypherpunks <cypherpunks(a)torproject.org> Date: Wed Aug 15 03:23:08 2018 +0000 rust/protover: delete ProtoSet::retain As the comment noted, it was horribly inefficient. --- src/rust/protover/protoset.rs | 30 ------------------------------ 1 file changed, 30 deletions(-) diff --git a/src/rust/protover/protoset.rs b/src/rust/protover/protoset.rs index 27c16c700..465b8f285 100644 --- a/src/rust/protover/protoset.rs +++ b/src/rust/protover/protoset.rs @@ -242,36 +242,6 @@ impl ProtoSet { false } - /// Retain only the `Version`s in this `ProtoSet` for which the predicate - /// `F` returns `true`. - /// - /// # Examples - /// - /// ``` - /// # use protover::errors::ProtoverError; - /// use protover::protoset::ProtoSet; - /// - /// # fn do_test() -> Result<bool, ProtoverError> { - /// let mut protoset: ProtoSet = "1,3-5,9".parse()?; - /// - /// // Keep only versions less than or equal to 8: - /// protoset.retain(|x| x <= &8); - /// - /// assert_eq!(protoset.expand(), vec![1, 3, 4, 5]); - /// # - /// # Ok(true) - /// # } - /// # fn main() { do_test(); } // wrap the test so we can use the ? operator - /// ``` - // XXX we could probably do something more efficient here. —isis - pub fn retain<F>(&mut self, f: F) - where F: FnMut(&Version) -> bool - { - let mut expanded: Vec<Version> = self.clone().expand(); - expanded.retain(f); - *self = expanded.into(); - } - /// Returns all the `Version`s in `self` which are not also in the `other` /// `ProtoSet`. ///

1 0

[tor/master] Merge branch 'maint-0.3.3' into maint-0.3.4
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 2ddbaf9cdc3c850a56ef1f3bf6977c903e24bb39 Merge: 6f47734ea 75b95e1c8 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Sep 18 08:31:14 2018 -0400 Merge branch 'maint-0.3.3' into maint-0.3.4 changes/bug27206 | 4 +++ src/rust/protover/protoset.rs | 49 +++++++++++++++++++++++++++---------- src/rust/protover/protover.rs | 4 +-- src/rust/protover/tests/protover.rs | 8 +++--- 4 files changed, 45 insertions(+), 20 deletions(-)

1 0

[tor/release-0.3.3] rust/protover: add ProtoSet::and_not_in()
by nickm＠torproject.org 18 Sep '18

18 Sep '18

commit 578f7326eda7307c420286c01b57f71925901533 Author: cypherpunks <cypherpunks(a)torproject.org> Date: Thu Aug 9 21:25:18 2018 +0000 rust/protover: add ProtoSet::and_not_in() This is a way more efficient version of retain(). --- src/rust/protover/protoset.rs | 53 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) diff --git a/src/rust/protover/protoset.rs b/src/rust/protover/protoset.rs index b99e1a99f..27c16c700 100644 --- a/src/rust/protover/protoset.rs +++ b/src/rust/protover/protoset.rs @@ -4,6 +4,8 @@ //! Sets for lazily storing ordered, non-overlapping ranges of integers. +use std::cmp; +use std::iter; use std::slice; use std::str::FromStr; use std::u32; @@ -269,6 +271,57 @@ impl ProtoSet { expanded.retain(f); *self = expanded.into(); } + + /// Returns all the `Version`s in `self` which are not also in the `other` + /// `ProtoSet`. + /// + /// # Examples + /// + /// ``` + /// # use protover::errors::ProtoverError; + /// use protover::protoset::ProtoSet; + /// + /// # fn do_test() -> Result<bool, ProtoverError> { + /// let protoset: ProtoSet = "1,3-6,10-12,15-16".parse()?; + /// let other: ProtoSet = "2,5-7,9-11,14-20".parse()?; + /// + /// let subset: ProtoSet = protoset.and_not_in(&other); + /// + /// assert_eq!(subset.expand(), vec![1, 3, 4, 12]); + /// # + /// # Ok(true) + /// # } + /// # fn main() { do_test(); } // wrap the test so we can use the ? operator + /// ``` + pub fn and_not_in(&self, other: &Self) -> Self { + if self.is_empty() || other.is_empty() { + return self.clone(); + } + + let pairs = self.iter().flat_map(|&(lo, hi)| { + let the_end = (hi + 1, hi + 1); // special case to mark the end of the range. + let excluded_ranges = other + .iter() + .cloned() // have to be owned tuples, to match iter::once(the_end). + .skip_while(move|&(_, hi2)| hi2 < lo) // skip the non-overlapping ranges. + .take_while(move|&(lo2, _)| lo2 <= hi) // take all the overlapping ones. + .chain(iter::once(the_end)); + + let mut nextlo = lo; + excluded_ranges.filter_map(move |(excluded_lo, excluded_hi)| { + let pair = if nextlo < excluded_lo { + Some((nextlo, excluded_lo - 1)) + } else { + None + }; + nextlo = cmp::min(excluded_hi, u32::MAX - 1) + 1; + pair + }) + }); + + let pairs = pairs.collect(); + ProtoSet::is_ok(ProtoSet{ pairs }).expect("should be already sorted") + } } impl FromStr for ProtoSet {

1 0