RFR: 8315487: Security Providers Filter

Martin Balao mbalao at openjdk.org
Fri Sep 1 15:20:19 UTC 2023 

In addition to the goals, scope, motivation, specification and requirement notes in [JDK-8315487](https://bugs.openjdk.org/browse/JDK-8315487), we would like to describe the most relevant decisions taken during the implementation of this enhancement. These notes are organized by feature, may encompass more than one file or code segment, and are aimed to provide a high-level view of this PR.

## ProvidersFilter

### Filter construction (parser)

The providers filter is constructed from a string value, taken from either a system or a security property with name "jdk.security.providers.filter". This process occurs at sun.security.jca.ProvidersFilter class —simply referred as ProvidersFilter onward— static initialization. Thus, changes to the filter's overridable property are not effective afterwards and no assumptions should be made regarding when this class gets initialized.

The filter's string value is processed with a custom parser of order 'n', being 'n' the number of characters. The parser, represented by the ProvidersFilter.Parser class, can be characterized as a Deterministic Finite Automaton (DFA). The ProvidersFilter.Parser::parse method is the starting point to get characters from the filter's string value and generate state transitions in the parser's internal state-machine. See ProvidersFilter.Parser::nextState for more details about the parser's states and both valid and invalid transitions. The ParsingState enum defines valid parser states and Transition the reasons to move between states. If a filter string cannot be parsed, a ProvidersFilter.ParserException exception is thrown, and turned into an unchecked IllegalArgumentException in the ProvidersFilter.Filter constructor.

While we analyzed —and even tried, at early stages of the development— the use of regular expressions for filter parsing, we discarded the approach in order to get maximum performance, support a more advanced syntax and have flexibility for further extensions in the future.

### Filter (structure and behavior)

A filter is represented by the ProvidersFilter.Filter class. It consists of an ordered list of rules, returned by the parser, that represents filter patterns from left to right (see the filter syntax for reference). At the end of this list, a match-all and deny rule is added for default behavior. When a service is evaluated against the filter, each filter rule is checked in the ProvidersFilter.Filter::apply method. The rule makes an allow or deny decision if the service matches it. Otherwise, the filter moves to the next rule in the sequence.

Rules are made of 3 regular expressions, derived from a filter pattern: provider, service type and algorithm or alias. A service matches a rule when its provider, service type and algorithm or alias matches the corresponding regular expressions in the rule. When a rule is matched by a service, it casts a decision (represented by the ProvidersFilter::FilterDecision class) that has two values: an allow or deny result and a priority that depends on how early (or left, in filter string terms) the rule is positioned in relative terms. Priorities are used for services that have aliases, as a mechanism to disambiguate contradictory decision results depending on which alias or algorithm is evaluated.

When a service with aliases is passed through a filter, independent evaluations are made for the algorithm and each alias. The decision with highest priority (lowest in absolute numbers) is finally effective.

### Filter decisions cache

To accomplish the goal of maximizing performance, most services are passed through the Providers filter at registration time, when added with the java.security.Provider::putService or java.security.Provider::put APIs. While uncommon, providers may override java.security.Provider::getService or java.security.Provider::getServices APIs and return services that were never registered. In these cases, the service is evaluated against the Providers filter the first time used.

Once a service is evaluated against the filter, the decision is stored in the private isAllowed Provider.Service class field. When authorizing further uses of the service, the value from this cache is read, instead of performing a new filter evaluation. If the service does not experience any change, such as gaining or losing an alias (only possible with the legacy API), the cached value remains valid. Otherwise, a new filter evaluation has to take place. For example, a service could have been not allowed but a new alias matches an authorization rule in the filter that flips the previous decision.

The method Provider.Service::computeIsAllowed (that internally invokes ProvidersFilter::computeIsAllowed) can be used to force the recomputation of an authorization cached decision. The method ProvidersFilter::isAllowed, when filtering capabilities are enabled, tries to get the service authorization from the Provider.Service isAllowed field, and triggers a computation if not initialized. For this mechanism to work, the Provider.Service::getIsAllowed private method is exposed through SharedSecrets and accessed from ProvidersFilter.

### Filter checking idiom

At every point in the JDK where any of Provider::getService or Provider::getServices APIs are invoked, a Providers filter check must be applied by calling ProvidersFilter.isAllowed(serviceInstance). It's assumed that serviceInstance is not null. The returned value indicates if the serviceInstance service is allowed or not. When a service is not allowed, the caller must discard it. The reason why we need to apply this checking pattern is because Provider::getService or Provider::getServices APIs may be overwritten by a provider to return unregistered services that were not evaluated against the filter before. If these APIs were not overwritten, the implementation will only return allowed services.

### Debugging the filter

There are 3 mechanisms to debug a filter:

1 - Set the "java.security.debug" System property to "jca" and find filter-related messages prefixed by "ProvidersFilter". This debug output includes information about the filter construction (parsing) as well as evaluations of services against the filter. Note: the application has to trigger the ProvidersFilter class static initialization for this output to be generated, for example by invoking java.security.Security::getProviders.

Example:

java -Djava.security.debug=jca -Djdk.security.providers.filter="SunJCE.Cipher.AES" Main

Filter construction messages:

ProvidersFilter: Parsing: SunJCE.Cipher.AES
ProvidersFilter: --------------------
ProvidersFilter: Rule parsed: SunJCE.Cipher.AES
ProvidersFilter:  * Provider: SunJCE (regexp: \QSunJCE\E)
ProvidersFilter:  * Service type: Cipher (regexp: \QCipher\E)
ProvidersFilter:  * Algorithm: AES (regexp: \QAES\E)
ProvidersFilter:  * Decision: ALLOW - priority: 0
ProvidersFilter: Filter: SunJCE.Cipher.AES; !* (DEFAULT)
ProvidersFilter: --------------------

Filter evaluation messages:

ProvidersFilter: Service filter query (Provider: SunJCE, Service type: Cipher, Algorithm: AES)
ProvidersFilter:  * Decision: ALLOW - priority: 0
ProvidersFilter:  * Made by: SunJCE.Cipher.AES
ProvidersFilter: --------------------
ProvidersFilter: The queried service has aliases. Checking them for a final decision...
ProvidersFilter: --------------------
ProvidersFilter: Service filter query (Provider: SunJCE, Service type: Cipher, Algorithm: OID.2.16.840.1.101.3.4.1)
ProvidersFilter:  * Decision: DENY - priority: 1
ProvidersFilter:  * Made by: !* (DEFAULT)
ProvidersFilter: --------------------
ProvidersFilter: Service filter query (Provider: SunJCE, Service type: Cipher, Algorithm: 2.16.840.1.101.3.4.1)
ProvidersFilter:  * Decision: DENY - priority: 1
ProvidersFilter:  * Made by: !* (DEFAULT)
ProvidersFilter: --------------------
ProvidersFilter: Final decision based on AES algorithm: ALLOW - priority: 0


2 - Pass the -XshowSettings:security:providers JVM argument and check, for each statically installed security provider, which services are allowed and not allowed by the filter.

Example:


java -XshowSettings:security:providers -Djdk.security.providers.filter="SunJCE.Cipher.AES" -version


Security provider static configuration: (in order of preference)
        ...
        ----------------------------------------
   Provider name: SunJCE
   ...
   Provider services allowed: (type : algorithm)
            Cipher.AES
              aliases: [2.16.840.1.101.3.4.1, OID.2.16.840.1.101.3.4.1]
   Provider services NOT allowed: (type : algorithm)
            AlgorithmParameterGenerator.DiffieHellman
              aliases: [1.2.840.113549.1.3.1, DH, OID.1.2.840.113549.1.3.1]
            ...
   ----------------------------------------
   ...


3 - When a filter cannot be constructed, the ProvidersFilter.ParserException exception includes the state of the filter at the time when the error occurred, and indicates which pattern could not be parsed.

Example:

java -XshowSettings:security:providers -Djdk.security.providers.filter="SunJCE.Cipher.AES; My Provider"


Caused by: sun.security.jca.ProvidersFilter$Filter$ParserException: Only whitespace characters are valid after a pattern. Whitespaces that are part of a provider name, service type or algorithm must be escaped.
 * State: POST_PATTERN
 * Filter string: SunJCE.Cipher.AES; My Provider
                                     ---^---


## ServicesMap

Existing Provider::getService and Provider.getServices APIs were changed to return services that are allowed by the Providers filter only. In addition, a new Provider::getServicesNotAllowed method (exposed through the SharedSecrets mechanism) was introduced to obtain services that are not allowed by the Providers filter, for informational purposes only (see -XshowSettings:security:providers). These changes motivated an analysis of how services are stored internally in a Provider instance, and lead to the refactoring that will be explained in this section.

### Existing bugs and inconsistencies

While analyzing the existing services map implementation, we categorized bugs found in 3 sets: 1) Concurrency bugs, 2) Serialization consistency bugs, and 3) Other bugs. While many of these bugs are related to corner cases that are unlikely to be triggered in real providers, others can potentially happen in highly concurrent scenarios and would be difficult to reproduce.

#### 1 - Concurrency bugs

1.1 - A concurrent Provider::getServices call may remove services that are temporarily considered invalid because they are in the midst of an update. I.e. a provider added an alias but not the class name still, and a reader removes the service in between:

Thread-1 (writer): Provider::put("Alg.Alias.MessageDigest.alias1", "alg1") ---> An invalid service is implicitly created
Thread-2 (reader): Provider::getServices() ---> The invalid service is removed
Thread-1 (writer): Provider::put("MessageDigest.alg1", "class1") ---> While the service is added again (valid, now), it won't have alias1.

While the situation sounds unlikely for a regular service registration, it is possible when deserializing Providers as the order in which Property map entries are visited is not guaranteed.

This scenario was not possible before JDK-8276660 because readers only removed invalid entries from legacyMap, but not from legacyStrings. As a result, invalid services could land in legacyMap without losing data after they become valid. See a reference to the JDK-8276660 removal here [1]. We have developed the ServicesConsistency::testInvalidGetServicesRemoval test to reflect this case.

Notice that the fact that legacyMap is a ConcurrentHashMap instance does not prevent this bug from happening, as the problem is between non-atomic and non-synchronized writes.

1.2 - This bug is similar to 1.1 but occurs in Provider::getService [2], and is reflected in the test ServicesConsistency::testInvalidGetServiceRemoval.

1.3 - When signaling legacyChanged = false after recomputing the services set here [3], a concurrent legacyMap update that right before set legacyChanged = true [4] [5] would be missed. This was introduced by JDK-8276660 because, previously, legacyChanged = false was done in ensureLegacyParsed and this method was called in a synchronized getService block. Notice here that making legacyChanged volatile did not prevent this issue, as the problem is that publishing the new computed set and resetting the legacyChanged variable is not an atomic operation and a new update could have happened in between. We think that this type of problem can be solved in a lock-free way with a pattern such as the one proposed in ServicesMap::getServicesSet, that includes a double compare and exchange with a placeholder while computing the set.

1.4 - In operations such as Provider::implReplaceAll, there is a window in which all services look gone for readers [6] and this may cause spurious NoSuchAlgorithmException exceptions. Before JDK-8276660 the operation was seen as atomic by readers. The replaceAll change in the Properties map was made on legacyStrings by writers but only visible after readers impacted changes under a synchronized block. We think that replaceAll and putAll should be atomic for readers. In particular, putAll would be the legacy API mechanism to ensure that readers see services only when they have all their attributes added, and there is no risk of obtaining a service with half of them. See a test that checks an atomic replaceAll behavior in ServicesConsistency::testReplaceAllIsAtomic and a test that checks a putAll atomic behavior in ServicesConsistency::testPutAllIsAtomic.

1.5 - When a reader obtains a service from the legacyMap, Service::newInstance or Service::supportsParameter may be invoked and cached values such as classCache, constructorCache, hasKeyAttributes, supportedFormats and supportedClasses set. If there are further changes to the service (i.e.: new attributes added), cached values are never invalidated and there is a single service instance. As a result, the service information becomes inconsistent and the new attributes are missed, even for new readers. This did not happen before JDK-8276660 because ensureLegacyParsed started with a clear legacyMap and new Service instances (with uninitialized cache fields) were added. This bug is reflected in ServicesConsistency::testInvalidCachedClass, ServicesConsistency::testInvalidCachedHasKeyAttributes and ServicesConsistency::testInvalidCachedSupportedKeyFormats tests.

#### 2 - Serialization consistency bugs

This type of bugs make a deserialized Provider to have different services (class names, aliases and attributes) than the original instance. What they have in common is one or more of the following traits: 1) lack of synchronization between the Properties map and the actual inner services map, 2) an incorrect assumption that the Properties map is visited, while deserializing, in the same order in which entries were originally added, or 3) an inconsistent collision behavior between the Provider::put and Provider::putService APIs.

We will show some examples that, while unrealistic, serve for the purpose of illustrating the aforementioned inconsistencies:

2.1 - Case-sensitive entries

Ordered list of actions:

put("MessageDigest.alg", "class1")
put("MessageDigest.ALG", "class2")

The previous list of actions creates a single Service instance that has "class2" as its class name. In the Properties map, however, both entries are present.

List of actions in the order that they are executed while deserializing the provider:

put("MessageDigest.ALG", "class2")
put("MessageDigest.alg", "class1")

The created Service instance, after deserialization, has "class1" as its class name.

This case is reflected in the ServicesConsistency::testSerializationClassnameConsistency test.

2.2 - Entries by alias

Ordered list of actions:

put("MessageDigest.alg", "class1")
put("Alg.Alias.MessageDigest.alias", "alg")
put("Alg.Alias.MessageDigest.alias2", "alias")

The previous list of actions creates a single Service instance that has "alg" as its algorithm, and "alias" and "alias2" as its aliases.

List of actions in the order that they are executed while deserializing the provider:

put("Alg.Alias.MessageDigest.alias2", "alias")
put("Alg.Alias.MessageDigest.alias", "alg")
put("MessageDigest.alg", "class1")

After deserialization there will be two Service instances: one has "alias" as its algorithm and "alias2" as its alias, and the other has "alg" as its algorithm and "alias" as its alias. The former instance is invalid and reachable by "alias2" only, and the latter is valid and reachable by "alg" or "alias".

2.3 - Algorithm case-insensitive collision between Provider::putService and Provider::put

Ordered list of actions:

put("MessageDigest.ALG", "class1")
putService(new Service(provider, "MessageDigest", "alg", "class2", null, null))

The previous list of actions creates two Service instances, from which the one using "class2" as its class name is visible. However, the Properties map has entries for both services.

List of actions in the order that they are executed while deserializing the provider:

put("MessageDigest.alg", "class2")
put("MessageDigest.ALG", "class1")

After deserialization, only the Service instance that has "class1" as its class name is available.

This case is related to the ServicesConsistency::testCurrentAPIServicesOverride test.

2.4 - Alias collision between Provider::putService and Provider::put

putService(new Service(provider, "MessageDigest", "alg1", "class1", List.of("alias"), null))
put("MessageDigest.alg2", "class2")
put("Alg.Alias.MessageDigest.alias", "alg2")

The previous list of actions creates two service instances, from which the one using "class1" as its class name is visible by "alias". However, the Properties map has the entry "Alg.Alias.MessageDigest.alias" associated with the service instance using "class2" as its class name.

List of actions executed while deserializing the provider (in any order):

put("MessageDigest.alg1", "class1")
put("MessageDigest.alg2", "class2")
put("Alg.Alias.MessageDigest.alias", "alg2")

After deserialization, the Service instance using "class2" as its class name is the one identified by the alias "alias".

This same inconsistency may occur with the algorithm instead of the alias.

This case is related to the ServicesConsistency::legacyAPIServicesOverride test.

2.5 - Overwrites of algorithms with aliases

Ordered list of actions:

put("MessageDigest.alg1", "class1")
put("Alg.Alias.MessageDigest.alias1", "alg1")
put("MessageDigest.alg2", "class2")
put("Alg.Alias.MessageDigest.alg1", "alg2")

The previous list of actions creates two service instances, one that has "alg1" as its algorithm, "class1" as its class name and "alias1" as its alias, and the other that has "alg2" as its algorithm, "class2" as its class name and "alg1" as its alias.

List of actions in the order that they are executed while deserializing the provider:

put("MessageDigest.alg2", "class2")
put("Alg.Alias.MessageDigest.alg1", "alg2")
put("MessageDigest.alg1", "class1")
put("Alg.Alias.MessageDigest.alias1", "alg1")

After deserialization, a single Service instance is created. This instance has "alg2" as its algorithm, "class1" as its class name, and "alg1" and "alias1" as its aliases.

This case is related to the ServicesConsistency::testLegacyAPIAliasCannotBeAlgorithm test.

#### 3 - Other bugs

3.1 - Invalid services (without a class name) can be returned in Provider::getService, even when they are removed from the legacyMap [7]. This case is reflected in the ServicesConsistency::testInvalidServiceNotReturned test.

3.2 - Methods Provider::implMerge and Provider::implCompute pass a "null" value as the 2nd parameter to Provider::parseLegacy and a remove action [8]. In the case of an alias, Provider::parseLegacy will throw a NullPointerException here [9]. This issue has been introduced by JDK-8276660, and is reflected in the tests ServicesConsistency::testComputeDoesNotThrowNPE and ServicesConsistency::testMergeDoesNotThrowNPE.

Note: we might be overlooking more bugs, as we decided to go with a new implementation at this point.

### Proposal

We replaced the mechanism through which Service instances are organized inside a Provider, while maintaining the existing APIs to store and fetch services. These APIs are internally called Legacy and Current. The solution was designed to follow the principles of avoiding bottlenecks for service map readers (lock-free, thread-safe), ensuring consistency after Providers deserialization, ensuring consistency between the Provider's properties map and the actual services, enforcing consistency between the Legacy and Current APIs, and maintaining previous behavior to the maximum extent possible.

What follows is a description of the most relevant design choices:

1 - Properties map synchronization: what you see on the Properties map is what you get from the internal services map

Adding, modifying or removing a service has a direct or indirect impact on the Properties map to enforce consistency. For example, adding an uppercase entry may overwrite a previous lowercase one. While this behavior is different from a regular Properties structure, having both entries would break synchronization with the internal services map (which is case insensitive) and is problematic for serialization. Other cases, such as adding entries by aliases, are also handled and canonicalized.

2 - The Current API (Provider::putService) has preference over the Legacy API (Provider::put).

We kept the preference of Provider::getService and Provider::getServices methods for Current API services over Legacy API counterparts. However, the internal map is now unified and Legacy services may be overwritten —notice that the opposite is not possible—. This was redesigned considering that there is a single Properties map, and we aim to keep it aligned to the internal services map. For expected behavior between the Legacy and Current APIs, we suggest looking at the ServicesConsistency::testLegacyAPIServicesOverride and ServicesConsistency::testCurrentAPIServicesOverride tests.

3 - Copy-on-write strategy for Legacy API service changes

We implemented a copy-on-write strategy that reminds of the one before JDK-8276660 but has a key difference: the new implementation is lock-free and faster from a service readers point of view. This strategy makes it possible to have service consistency in multi-threaded scenarios, and fix many of the concurrency bugs previously described. In terms of time consistency, we do not enforce that constraint between different services obtained from Provider::getServices. In other words, the Set<Service> returned may have an old version of service A and a new version of service B, even when the change to service A was applied first. We consider that it is not worth paying a synchronization cost for this type of consistency. Notice that Current API services do not require this approach because they are immutable: once added, they cannot be changed.

4 - Lock-free Provider::getServices

The Provider::getServices method is optimized for service readers with a cached set and a lock-free implementation.

## SunNativeProvider

Changes were introduced to make the SunNativeProvider security provider use the Provider::putService API to register services, instead of the legacy Provider::putAll. This was the only security provider in OpenJDK using a non-Provider::putService API. While this change does not have any observable implications, it is in the interest of a better code —and sets a better example— to align it with the other OpenJDK security providers. In our assessment, these are the OpenJDK providers using the Providers::putService API: SunJCE, SunPKCS11, SunRsaSign, SunEC, SUN, SunJSSE, SunMSCAPI, XMLDSigRI, JdkLDAP, JdkSASL, SunJGSS, SunPCSC, Apple and SunJarVerification.

## Testing

As part of our testing, we observed no regressions in the following test categories:

  * jdk:tier1
  * jdk/java/security
  * jdk/sun/security

Additionally, we introduced the following new regression tests:

  * jdk/sun/security/provider/ProvidersFilterTest.java
  * jdk/java/security/Provider/ServicesConsistency.java

Finally, we extended the following tests:

  * jdk/tools/launcher/Settings.java


This contribution is co-authored by Francisco Ferrari and Martin Balao.

--
[1] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1332
[2] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1289
[3] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1340
[4] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1145
[5] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1181
[6] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L976
[7] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1285-L1301
[8] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L999-L1016
[9] - https://github.com/openjdk/jdk/blob/jdk-20-ga/src/java.base/share/classes/java/security/Provider.java#L1146

-------------

Commit messages:
 - 8315487: Security Providers Filter

Changes: https://git.openjdk.org/jdk/pull/15539/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=15539&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8315487
  Stats: 4600 lines in 24 files changed: 4029 ins; 323 del; 248 mod
  Patch: https://git.openjdk.org/jdk/pull/15539.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/15539/head:pull/15539

PR: https://git.openjdk.org/jdk/pull/15539

More information about the security-dev mailing list