Merge remote-tracking branch 'onionk/rust-allsupported1' into maint-0.3.3

4 files changed, 45 insertions, 20 deletions

diff --git a/changes/bug27206 b/changes/bug27206
new file mode 100644
index 0000000000..c0fbbed702
--- /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/protoset.rs b/src/rust/protover/protoset.rs
index b99e1a99f7..465b8f2850 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;
@@ -240,8 +242,8 @@ impl ProtoSet {
         false
     }
 
-    /// Retain only the `Version`s in this `ProtoSet` for which the predicate
-    /// `F` returns `true`.
+    /// Returns all the `Version`s in `self` which are not also in the `other`
+    /// `ProtoSet`.
     ///
     /// # Examples
     ///
@@ -250,24 +252,45 @@ impl ProtoSet {
     /// use protover::protoset::ProtoSet;
     ///
     /// # fn do_test() -> Result<bool, ProtoverError> {
-    /// let mut protoset: ProtoSet = "1,3-5,9".parse()?;
+    /// let protoset: ProtoSet = "1,3-6,10-12,15-16".parse()?;
+    /// let other: ProtoSet = "2,5-7,9-11,14-20".parse()?;
     ///
-    /// // Keep only versions less than or equal to 8:
-    /// protoset.retain(|x| x <= &8);
+    /// let subset: ProtoSet = protoset.and_not_in(&other);
     ///
-    /// assert_eq!(protoset.expand(), vec![1, 3, 4, 5]);
+    /// assert_eq!(subset.expand(), vec![1, 3, 4, 12]);
     /// #
     /// # 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();
+    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")
     }
 }
 
diff --git a/src/rust/protover/protover.rs b/src/rust/protover/protover.rs
index b3563b0637..c11c7c1803 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 59a4b5a8a0..9258d869d7 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]