Merge branch 'security-fp-prevent-billion-laughs-attack-11-11' into '11-11-stable'

Prevent Billion Laughs attack

See merge request gitlab/gitlabhq!3144

7 files changed, 249 insertions, 8 deletions

diff --git a/changelogs/unreleased/security-fp-prevent-billion-laughs-attack.yml b/changelogs/unreleased/security-fp-prevent-billion-laughs-attack.yml
new file mode 100644
index 00000000000..4e0cf848931
--- /dev/null
+++ b/changelogs/unreleased/security-fp-prevent-billion-laughs-attack.yml
@@ -0,0 +1,5 @@
+---
+title: Prevent Billion Laughs attack
+merge_request:
+author:
+type: security
diff --git a/lib/gitlab/ci/config.rb b/lib/gitlab/ci/config.rb
index f187e456993..a7e4eb47dbb 100644
--- a/lib/gitlab/ci/config.rb
+++ b/lib/gitlab/ci/config.rb
@@ -15,6 +15,9 @@ module Gitlab
 
         @global = Entry::Global.new(@config)
         @global.compose!
+      rescue Gitlab::Config::Loader::Yaml::DataTooLargeError => e
+        Gitlab::Sentry.track_exception(e, extra: { user: user.inspect, project: project.inspect })
+        raise Config::ConfigError, e.message
       rescue Gitlab::Config::Loader::FormatError,
              Extendable::ExtensionError,
              External::Processor::IncludeError => e
diff --git a/lib/gitlab/config/loader/yaml.rb b/lib/gitlab/config/loader/yaml.rb
index 8159f8b8026..4cedab1545c 100644
--- a/lib/gitlab/config/loader/yaml.rb
+++ b/lib/gitlab/config/loader/yaml.rb
@@ -4,6 +4,13 @@ module Gitlab
   module Config
     module Loader
       class Yaml
+        DataTooLargeError = Class.new(Loader::FormatError)
+
+        include Gitlab::Utils::StrongMemoize
+
+        MAX_YAML_SIZE = 1.megabyte
+        MAX_YAML_DEPTH = 100
+
         def initialize(config)
           @config = YAML.safe_load(config, [Symbol], [], true)
         rescue Psych::Exception => e
@@ -11,16 +18,35 @@ module Gitlab
         end
 
         def valid?
-          @config.is_a?(Hash)
+          hash? && !too_big?
         end
 
         def load!
-          unless valid?
-            raise Loader::FormatError, 'Invalid configuration format'
-          end
+          raise DataTooLargeError, 'The parsed YAML is too big' if too_big?
+          raise Loader::FormatError, 'Invalid configuration format' unless hash?
 
           @config.deep_symbolize_keys
         end
+
+        private
+
+        def hash?
+          @config.is_a?(Hash)
+        end
+
+        def too_big?
+          return false unless Feature.enabled?(:ci_yaml_limit_size, default_enabled: true)
+
+          !deep_size.valid?
+        end
+
+        def deep_size
+          strong_memoize(:deep_size) do
+            Gitlab::Utils::DeepSize.new(@config,
+              max_size: MAX_YAML_SIZE,
+              max_depth: MAX_YAML_DEPTH)
+          end
+        end
       end
     end
   end
diff --git a/lib/gitlab/utils/deep_size.rb b/lib/gitlab/utils/deep_size.rb
new file mode 100644
index 00000000000..562cf09e249
--- /dev/null
+++ b/lib/gitlab/utils/deep_size.rb
@@ -0,0 +1,79 @@
+# frozen_string_literal: true
+
+require 'objspace'
+
+module Gitlab
+  module Utils
+    class DeepSize
+      Error = Class.new(StandardError)
+      TooMuchDataError = Class.new(Error)
+
+      DEFAULT_MAX_SIZE = 1.megabyte
+      DEFAULT_MAX_DEPTH = 100
+
+      def initialize(root, max_size: DEFAULT_MAX_SIZE, max_depth: DEFAULT_MAX_DEPTH)
+        @root = root
+        @max_size = max_size
+        @max_depth = max_depth
+        @size = 0
+        @depth = 0
+
+        evaluate
+      end
+
+      def valid?
+        !too_big? && !too_deep?
+      end
+
+      private
+
+      def evaluate
+        add_object(@root)
+      rescue Error
+        # NOOP
+      end
+
+      def too_big?
+        @size > @max_size
+      end
+
+      def too_deep?
+        @depth > @max_depth
+      end
+
+      def add_object(object)
+        @size += ObjectSpace.memsize_of(object)
+        raise TooMuchDataError if @size > @max_size
+
+        add_array(object) if object.is_a?(Array)
+        add_hash(object) if object.is_a?(Hash)
+      end
+
+      def add_array(object)
+        with_nesting do
+          object.each do |n|
+            add_object(n)
+          end
+        end
+      end
+
+      def add_hash(object)
+        with_nesting do
+          object.each do |key, value|
+            add_object(key)
+            add_object(value)
+          end
+        end
+      end
+
+      def with_nesting
+        @depth += 1
+        raise TooMuchDataError if too_deep?
+
+        yield
+
+        @depth -= 1
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/ci/config_spec.rb b/spec/lib/gitlab/ci/config_spec.rb
index 64396a746ee..d7c657383df 100644
--- a/spec/lib/gitlab/ci/config_spec.rb
+++ b/spec/lib/gitlab/ci/config_spec.rb
@@ -90,6 +90,27 @@ describe Gitlab::Ci::Config do
       end
     end
 
+    context 'when yml is too big' do
+      let(:yml) do
+        <<~YAML
+          --- &1
+          - hi
+          - *1
+        YAML
+      end
+
+      describe '.new' do
+        it 'raises error' do
+          expect(Gitlab::Sentry).to receive(:track_exception)
+
+          expect { config }.to raise_error(
+            described_class::ConfigError,
+            /The parsed YAML is too big/
+          )
+        end
+      end
+    end
+
     context 'when config logic is incorrect' do
       let(:yml) { 'before_script: "ls"' }
 
diff --git a/spec/lib/gitlab/config/loader/yaml_spec.rb b/spec/lib/gitlab/config/loader/yaml_spec.rb
index 44c9a3896a8..0affeb01f6a 100644
--- a/spec/lib/gitlab/config/loader/yaml_spec.rb
+++ b/spec/lib/gitlab/config/loader/yaml_spec.rb
@@ -8,7 +8,7 @@ describe Gitlab::Config::Loader::Yaml do
 
     describe '#valid?' do
       it 'returns true' do
-        expect(loader.valid?).to be true
+        expect(loader).to be_valid
       end
     end
 
@@ -24,7 +24,7 @@ describe Gitlab::Config::Loader::Yaml do
 
     describe '#valid?' do
       it 'returns false' do
-        expect(loader.valid?).to be false
+        expect(loader).not_to be_valid
       end
     end
 
@@ -43,7 +43,10 @@ describe Gitlab::Config::Loader::Yaml do
 
     describe '#initialize' do
       it 'raises FormatError' do
-        expect { loader }.to raise_error(Gitlab::Config::Loader::FormatError, 'Unknown alias: bad_alias')
+        expect { loader }.to raise_error(
+          Gitlab::Config::Loader::FormatError,
+          'Unknown alias: bad_alias'
+        )
       end
     end
   end
@@ -53,7 +56,68 @@ describe Gitlab::Config::Loader::Yaml do
 
     describe '#valid?' do
       it 'returns false' do
-        expect(loader.valid?).to be false
+        expect(loader).not_to be_valid
+      end
+    end
+  end
+
+  # Prevent Billion Laughs attack: https://gitlab.com/gitlab-org/gitlab-ce/issues/56018
+  context 'when yaml size is too large' do
+    let(:yml) do
+      <<~YAML
+        a: &a ["lol","lol","lol","lol","lol","lol","lol","lol","lol"]
+        b: &b [*a,*a,*a,*a,*a,*a,*a,*a,*a]
+        c: &c [*b,*b,*b,*b,*b,*b,*b,*b,*b]
+        d: &d [*c,*c,*c,*c,*c,*c,*c,*c,*c]
+        e: &e [*d,*d,*d,*d,*d,*d,*d,*d,*d]
+        f: &f [*e,*e,*e,*e,*e,*e,*e,*e,*e]
+        g: &g [*f,*f,*f,*f,*f,*f,*f,*f,*f]
+        h: &h [*g,*g,*g,*g,*g,*g,*g,*g,*g]
+        i: &i [*h,*h,*h,*h,*h,*h,*h,*h,*h]
+      YAML
+    end
+
+    describe '#valid?' do
+      it 'returns false' do
+        expect(loader).not_to be_valid
+      end
+
+      it 'returns true if "ci_yaml_limit_size" feature flag is disabled' do
+        stub_feature_flags(ci_yaml_limit_size: false)
+
+        expect(loader).to be_valid
+      end
+    end
+
+    describe '#load!' do
+      it 'raises FormatError' do
+        expect { loader.load! }.to raise_error(
+          Gitlab::Config::Loader::FormatError,
+          'The parsed YAML is too big'
+        )
+      end
+    end
+  end
+
+  # Prevent Billion Laughs attack: https://gitlab.com/gitlab-org/gitlab-ce/issues/56018
+  context 'when yaml has cyclic data structure' do
+    let(:yml) do
+      <<~YAML
+        --- &1
+        - hi
+        - *1
+      YAML
+    end
+
+    describe '#valid?' do
+      it 'returns false' do
+        expect(loader.valid?).to be(false)
+      end
+    end
+
+    describe '#load!' do
+      it 'raises FormatError' do
+        expect { loader.load! }.to raise_error(Gitlab::Config::Loader::FormatError, 'The parsed YAML is too big')
       end
     end
   end
diff --git a/spec/lib/gitlab/utils/deep_size_spec.rb b/spec/lib/gitlab/utils/deep_size_spec.rb
new file mode 100644
index 00000000000..1e619a15980
--- /dev/null
+++ b/spec/lib/gitlab/utils/deep_size_spec.rb
@@ -0,0 +1,43 @@
+require 'spec_helper'
+
+describe Gitlab::Utils::DeepSize do
+  let(:data) do
+    {
+      a: [1, 2, 3],
+      b: {
+        c: [4, 5],
+        d: [
+          { e: [[6], [7]] }
+        ]
+      }
+    }
+  end
+
+  let(:max_size) { 1.kilobyte }
+  let(:max_depth) { 10 }
+  let(:deep_size) { described_class.new(data, max_size: max_size, max_depth: max_depth) }
+
+  describe '#evaluate' do
+    context 'when data within size and depth limits' do
+      it 'returns true' do
+        expect(deep_size).to be_valid
+      end
+    end
+
+    context 'when data not within size limit' do
+      let(:max_size) { 200.bytes }
+
+      it 'returns false' do
+        expect(deep_size).not_to be_valid
+      end
+    end
+
+    context 'when data not within depth limit' do
+      let(:max_depth) { 2 }
+
+      it 'returns false' do
+        expect(deep_size).not_to be_valid
+      end
+    end
+  end
+end