diff --git a/ci-tooling/lib/debian/profile.rb b/ci-tooling/lib/debian/profile.rb
index bdef0ee3..36e94e9f 100644
--- a/ci-tooling/lib/debian/profile.rb
+++ b/ci-tooling/lib/debian/profile.rb
@@ -62,11 +62,15 @@ module Debian
     def matches?(array_or_profile)
       ary = [*array_or_profile]
 
+      # If both are empty they alwyas match.
+      return true if empty? && ary.empty?
+
       # A Group is an AND relationship between profiles, so all our Profiles
-      # must match at least one search profile.
+      # must match at least one search profile. That is to say that there also
+      # must be at least one profile in "us".
       # If we are 'cross nocheck' the input must have at least
       # 'cross' and 'nocheck'.
-      all? do |profile|
+      !empty? && all? do |profile|
         ary.any? { |check_profile| profile.matches?(check_profile) }
       end
     end
diff --git a/ci-tooling/lib/debian/relationship.rb b/ci-tooling/lib/debian/relationship.rb
index bcd54c92..22629fa6 100644
--- a/ci-tooling/lib/debian/relationship.rb
+++ b/ci-tooling/lib/debian/relationship.rb
@@ -110,7 +110,8 @@ module Debian
     def applicable_to_profile?(array_or_profile)
       group = array_or_profile
       group = ProfileGroup.new(group) unless group.is_a?(ProfileGroup)
-      profiles.any? { |x| x.matches?(group) }
+      profiles_ = profiles || [ProfileGroup.new(nil)]
+      profiles_.any? { |x| x.matches?(group) }
     end
 
     def substvar?
diff --git a/ci-tooling/test/test_debian_relationship.rb b/ci-tooling/test/test_debian_relationship.rb
index 2e1c0232..d4adac75 100644
--- a/ci-tooling/test/test_debian_relationship.rb
+++ b/ci-tooling/test/test_debian_relationship.rb
@@ -77,6 +77,15 @@ module Debian
       assert rel.applicable_to_profile?('cross   nocheck')
       assert rel.applicable_to_profile?(ProfileGroup.new(%w[cross nocheck]))
       refute rel.applicable_to_profile?(nil)
+
+      rel = Relationship.new('foo')
+      assert rel.applicable_to_profile?(nil)
+      refute rel.applicable_to_profile?('nocheck')
+
+      rel = Relationship.new('foo <cross>')
+      refute rel.applicable_to_profile?(nil)
+      refute rel.applicable_to_profile?('nocheck')
+      assert rel.applicable_to_profile?('cross')
     end
 
     def test_compare