diff --git a/luni/src/main/java/java/security/Provider.java b/luni/src/main/java/java/security/Provider.java
index 899625a..a6de19c 100644
--- a/luni/src/main/java/java/security/Provider.java
+++ b/luni/src/main/java/java/security/Provider.java
@@ -25,7 +25,6 @@
 import java.util.Collections;
 import java.util.Enumeration;
 import java.util.HashMap;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
@@ -72,7 +71,7 @@
     private transient LinkedHashMap<String, Service> propertyAliasTable;
 
     // The properties changed via put()
-    private transient Properties changedProperties;
+    private transient LinkedHashMap<Object, Object> changedProperties;
 
     // For getService(String type, String algorithm) optimization:
     // previous result
@@ -194,7 +193,7 @@
 
     private void myPutAll(Map<?,?> t) {
         if (changedProperties == null) {
-            changedProperties = new Properties();
+            changedProperties = new LinkedHashMap<Object, Object>();
         }
         Iterator<? extends Map.Entry<?, ?>> it = t.entrySet().iterator();
         Object key;
@@ -259,7 +258,7 @@
             removeFromPropertyServiceTable(key);
         }
         if (changedProperties == null) {
-            changedProperties = new Properties();
+            changedProperties = new LinkedHashMap<Object, Object>();
         }
         changedProperties.put(key, value);
         return super.put(key, value);
diff --git a/luni/src/test/java/libcore/java/security/ProviderTest.java b/luni/src/test/java/libcore/java/security/ProviderTest.java
index 78608d0..97a80a9 100644
--- a/luni/src/test/java/libcore/java/security/ProviderTest.java
+++ b/luni/src/test/java/libcore/java/security/ProviderTest.java
@@ -212,7 +212,7 @@
             assertEquals(1, position);
             SecureRandom sr = new SecureRandom();
             if (!sr.getAlgorithm().equals("SecureRandom1")) {
-                throw new IllegalStateException("Expected SecureRandom1");
+                throw new IllegalStateException("Expected SecureRandom1 was " + sr.getAlgorithm());
             }
         } finally {
             Security.removeProvider(srp.getName());