diff -u b/core/lib/Drupal/Core/Config/ConfigInstaller.php b/core/lib/Drupal/Core/Config/ConfigInstaller.php
--- b/core/lib/Drupal/Core/Config/ConfigInstaller.php
+++ b/core/lib/Drupal/Core/Config/ConfigInstaller.php
@@ -124,10 +124,9 @@
       $collection_info = $this->configManager->getConfigCollectionInfo();
       foreach ($collection_info->getCollectionNames() as $collection) {
         $config_to_create = $this->getConfigToCreate($storage, $collection, $prefix, $profile_storages);
-        // If we're installing a profile ensure configuration that is overriding
-        // is excluded.
-        // @todo Exclude simple configuration that already exists because it
-        //   will have been imported already.
+        // @todo If we're installing a profile we could exclude simple
+        //   configuration that already exists because it will have been
+        //   overridden already. Do we need to do that work?
         if (!empty($config_to_create)) {
           $this->createConfiguration($collection, $config_to_create);
         }
@@ -260,7 +259,9 @@
       if ($this->drupalInstallationAttempted()) {
         // During installation profile provided configuration overrides can have
         // dependencies that can not possibly be installed. Therefore, only
-        // override simple configuration.
+        // override simple configuration. As this method is called before
+        // modules are installed the only way to determine if they are
+        // configuration entities is the presence of a dependencies key.
         foreach ($profile_overrides as $name => $override_data) {
           if (!isset($override_data['dependencies'])) {
             $data[$name] = $override_data;
only in patch2:
unchanged:
--- a/core/modules/config/src/Tests/ConfigInstallProfileUnmetDependenciesTest.php
+++ b/core/modules/config/src/Tests/ConfigInstallProfileUnmetDependenciesTest.php
@@ -44,11 +44,10 @@ protected function setUp() {
       }
     }
 
-    // Add a dependency that can not be met because User is installed before
-    // Action.
+    // Add a dependency that can not be met.
     $config_file = $dest . DIRECTORY_SEPARATOR . InstallStorage::CONFIG_INSTALL_DIRECTORY . DIRECTORY_SEPARATOR . 'system.action.user_block_user_action.yml';
     $action = Yaml::decode(file_get_contents($config_file));
-    $action['dependencies']['module'][] = 'action';
+    $action['dependencies']['module'][] = 'does_not_exist';
     file_put_contents($config_file, Yaml::encode($action));
 
     parent::setUp();
@@ -90,7 +89,7 @@ public function testInstalled() {
     else {
       $this->fail('Expected Drupal\Core\Config\UnmetDependenciesException exception thrown');
     }
-    $this->assertErrorLogged('Configuration objects provided by <em class="placeholder">user</em> have unmet dependencies: <em class="placeholder">system.action.user_block_user_action (action)</em>');
+    $this->assertErrorLogged('Configuration objects provided by <em class="placeholder">testing_config_overrides</em> have unmet dependencies: <em class="placeholder">system.action.user_block_user_action (does_not_exist)</em>');
   }
 
 }
only in patch2:
unchanged:
--- a/core/modules/config/tests/src/Functional/ConfigInstallProfileOverrideTest.php
+++ b/core/modules/config/tests/src/Functional/ConfigInstallProfileOverrideTest.php
@@ -8,6 +8,7 @@
 use Drupal\Core\Config\FileStorage;
 use Drupal\system\Entity\Action;
 use Drupal\tour\Entity\Tour;
+use Drupal\user\Entity\Role;
 
 /**
  * Tests installation and removal of configuration objects in install, disable
@@ -109,6 +110,11 @@ public function testInstallProfileConfigOverwrite() {
     $this->rebuildContainer();
     $this->assertEqual($config_test_storage->load('override_unmet')->label(), 'Override', 'The optional config_test entity is overridden by the profile optional configuration and is installed when its dependencies are met.');
     $this->assertEqual($config_test_storage->load('completely_new')->label(), 'Completely new optional configuration', 'The optional config_test entity is provided by the profile optional configuration and is installed when its dependencies are met.');
+
+    // Ensure the authenticated role has the access tour permission.
+    $role = Role::load(Role::AUTHENTICATED_ID);
+    $this->assertTrue($role->hasPermission('access tour'), 'The Authenticated role has the "access tour" permission.');
+    $this->assertEquals(['module' => ['tour']], $role->getDependencies());
   }
 
 }
only in patch2:
unchanged:
--- /dev/null
+++ b/core/modules/user/tests/src/Functional/Update/UserUpdateRoleDependenciesTest.php
@@ -0,0 +1,46 @@
+<?php
+
+namespace Drupal\Tests\user\Functional\Update;
+
+use Drupal\FunctionalTests\Update\UpdatePathTestBase;
+use Drupal\user\Entity\Role;
+
+/**
+ * Tests user_post_update_update_roles() upgrade path.
+ *
+ * @group Update
+ */
+class UserUpdateRoleDependenciesTest extends UpdatePathTestBase {
+
+  /**
+   * {@inheritdoc}
+   */
+  protected function setDatabaseDumpFiles() {
+    $this->databaseDumpFiles = [
+      __DIR__ . '/../../../../../system/tests/fixtures/update/drupal-8-rc1.bare.standard.php.gz',
+    ];
+  }
+
+  /**
+   * Tests that roles have dependencies and only existing permissions.
+   */
+  public function testRolePermissions() {
+    // Edit the role to have a non-existent permission.
+    $raw_config = $this->config('user.role.authenticated');
+    $permissions = $raw_config->get('permissions');
+    $permissions[] = 'does_not_exist';
+    $raw_config
+      ->set('permissions', $permissions)
+      ->save();
+
+    $authenticated = Role::load('authenticated');
+    $this->assertTrue($authenticated->hasPermission('does_not_exist'), 'Authenticated role has a permission that does not exist');
+    $this->assertEquals([], $authenticated->getDependencies());
+
+    $this->runUpdates();
+    $authenticated = Role::load('authenticated');
+    $this->assertFalse($authenticated->hasPermission('does_not_exist'), 'Authenticated role does not have a permission that does not exist');
+    $this->assertEquals(['config' => ['filter.format.basic_html'], 'module' => ['comment', 'contact', 'filter', 'search', 'shortcut', 'system']], $authenticated->getDependencies());
+  }
+
+}
only in patch2:
unchanged:
--- a/core/modules/user/user.post_update.php
+++ b/core/modules/user/user.post_update.php
@@ -20,3 +20,17 @@ function user_post_update_enforce_order_of_permissions() {
   };
   array_map($entity_save, Role::loadMultiple());
 }
+
+/**
+ * Calculate role dependencies and remove non-existent permissions.
+ */
+function user_post_update_update_roles() {
+  $existing_permissions = array_keys(\Drupal::service('user.permissions')->getPermissions());
+  $entity_save = function (Role $role) use ($existing_permissions) {
+    $permissions = array_intersect($role->getPermissions(), $existing_permissions);
+    $role
+      ->set('permissions', $permissions)
+      ->save();
+  };
+  array_map($entity_save, Role::loadMultiple());
+}