diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
index 7e34cc6..be61b94 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
@@ -30,7 +30,8 @@
 @RunWith(JUnit4.class)
 public class LabelTest {
 
-  private static final String BAD_PACKAGE_CHARS = "package names may contain only";
+  private static final String BAD_PACKAGE_CHARS =
+      "package names may contain A-Z, a-z, 0-9, or any of";
   private static final String INVALID_TARGET_NAME = "invalid target name";
   private static final String INVALID_PACKAGE_NAME = "invalid package name";
 
@@ -89,7 +90,7 @@
   @Test
   public void testLabelResolutionBadSyntax() throws Exception {
     try {
-      parseCommandLine("//absolute:A+bad%syntax", "");
+      parseCommandLine("//absolute:A+bad:syntax", "");
       fail();
     } catch (LabelSyntaxException e) {
       // Expected exception
@@ -303,12 +304,6 @@
                       "//foo:bar:");
     assertSyntaxError("target names may not contain ':'",
                       "//foo/bar::");
-    assertSyntaxError("target names may not contain '&'",
-                      "//foo:bar&");
-    // Warning: if these assertions are false, tools that assume that they can safely quote labels
-    // may need to be fixed. Please consult with bazel-dev before loosening these restrictions.
-    assertSyntaxError("target names may not contain '''", "//foo/bar:baz'foo");
-    assertSyntaxError("target names may not contain '\"'", "//foo/bar:baz\"foo");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java
index 2156ddf..fcb187f 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java
@@ -53,6 +53,37 @@
     assertThat(LabelValidator.validatePackageName("a/b..")).isNull();
     assertThat(LabelValidator.validatePackageName("a$( )/b..")).isNull();
 
+    // These are in ascii code order.
+    assertThat(LabelValidator.validatePackageName("foo!bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo\"bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo#bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo$bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo%bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo&bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo'bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo(bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo)bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo*bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo+bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo,bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo-bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo.bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo+bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo;bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo<bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo=bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo>bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo?bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo[bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo]bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo^bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo_bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo`bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo{bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo|bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo}bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo~bar")).isNull();
+
     // Bad:
     assertThat(LabelValidator.validatePackageName("/foo"))
         .isEqualTo("package names may not start with '/'");
@@ -82,16 +113,39 @@
 
   @Test
   public void testValidateTargetName() throws Exception {
-
     assertThat(LabelValidator.validateTargetName("foo")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo!bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo\"bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo#bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo$bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo%bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo&bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo'bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo(bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo)bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo*bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo+bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo_bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo=bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo,bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo-bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo.bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo@bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo+bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo;bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo<bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo=bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo>bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo?bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo[bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo]bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo^bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo_bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo`bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo{bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo|bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo}bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo~bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo#bar")).isNull();
+
+    assertThat(LabelValidator.validateTargetName("foo/bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo@bar")).isNull();
 
     assertThat(LabelValidator.validateTargetName("foo/"))
         .isEqualTo("target names may not end with '/'");
@@ -99,8 +153,6 @@
         .isEqualTo("target names may not contain ':'");
     assertThat(LabelValidator.validateTargetName("bar:"))
         .isEqualTo("target names may not contain ':'");
-    assertThat(LabelValidator.validateTargetName("bar&"))
-        .isEqualTo("target names may not contain '&'");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
index 012e120..e33d1f3 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
@@ -50,7 +50,7 @@
   @Test
   public void testInvalidPatterns() throws TargetParsingException {
     try {
-      parse("Bar&&&java");
+      parse("Bar@java");
       fail();
     } catch (TargetParsingException expected) {
     }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java b/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java
index 57b7c59..c422f77 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java
@@ -167,7 +167,7 @@
             "bad_out_name/BUILD",
             "genrule(name='a',",
             "        cmd='ls',",
-            "        outs=['!@#'])");
+            "        outs=['!@#:'])");
 
     reporter.removeHandler(failFastHandler);
     packageFactory.createPackageForTesting(
@@ -175,7 +175,7 @@
         buildfile,
         getPackageManager(),
         reporter);
-    assertContainsEvent("illegal output file name '!@#' in rule //bad_out_name:a");
+    assertContainsEvent("illegal output file name '!@#:' in rule //bad_out_name:a");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
index e4729d3..ba07b68 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
@@ -236,10 +236,10 @@
 
   @Test
   public void testGetPackageWithInvalidName() throws Exception {
-    scratch.file("invalidpackagename&42/BUILD", "cc_library(name = 'foo') # a BUILD file");
+    scratch.file("invalidpackagename:42/BUILD", "cc_library(name = 'foo') # a BUILD file");
     checkGetPackageFails(
-        "invalidpackagename&42",
-        "no such package 'invalidpackagename&42': Invalid package name 'invalidpackagename&42'");
+        "invalidpackagename:42",
+        "no such package 'invalidpackagename:42': Invalid package name 'invalidpackagename:42'");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java
index f6ec361..a7f81a2 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java
@@ -712,8 +712,6 @@
   public void testFailingValidations() {
     expectValidationFail("");
     expectValidationFail("\\");
-    expectValidationFail("foo:**");
-    expectValidationFail("//foo/*");
   }
 
   private void expectValidationFail(String target) {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
index 195d987..4d63399 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -243,8 +243,8 @@
 
   @Test
   public void testInvalidPackageName() throws Exception {
-    scratch.file("parentpackage/invalidpackagename%42/BUILD");
-    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/invalidpackagename%42");
+    scratch.file("parentpackage/invalidpackagename:42/BUILD");
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/invalidpackagename:42");
     assertThat(packageLookupValue.packageExists()).isFalse();
     assertThat(packageLookupValue.getErrorReason()).isEqualTo(ErrorReason.INVALID_PACKAGE_NAME);
     assertThat(packageLookupValue.getErrorMsg()).isNotNull();