Implementation does not match specification

[willmurnane]

In the process of developing a Rust implementation of this specification, I implemented a check that the Rust implementation's behavior matches the Java code, and was surprised to find that the Java code does not implement what the ABNF says it does. Specifically, the ABNF says that access tokens include quoted strings composed of characters 0x20 and greater with a few exceptions, but the Java code accepts the characters 0x0 through 0x1f, as demonstrated by running this code:

package test.access;
import org.apache.accumulo.access.AccessEvaluator;
import org.apache.accumulo.access.AccessExpression;
import org.apache.accumulo.access.Authorizations;
import org.apache.accumulo.access.IllegalAccessExpressionException;

public class Main {
    public static void main(String[] args) {
        for (char i = 0; i < 0x25; i++) {
            String s = String.format("\"%c\"", i);
            System.out.printf("Character 0x%02x %s -> ", (int)i, s);
            try {
                if (i == 0x22) {
                    System.out.printf("Double quote is illegal, skipping\n");
                }
                AccessExpression.of(s);
                System.out.printf(" %s", AccessExpression.of(s));
                System.out.printf(" %s", AccessEvaluator.of(Authorizations.of(String.format("%c", i))).canAccess(s));
                if (i < 0x20) {
                    System.out.printf("(expected failure)\n");
                } else {
                    System.out.printf("(expected success)\n");
                }
            } catch (IllegalAccessExpressionException iaee) {
                System.out.printf("%s Failed!\n", s);
            }
        }
    }
}

I'm not sure what the intended behavior is here, should the specification or the code be updated to match the other?

[keith-turner]

I'm not sure what the intended behavior is here, should the specification or the code be updated to match the other?

Good find, we do need to fix this one way or another.

We would like access expression to be human readable. The current code was created to be compatible with the code in Accumulo which accepts any byte between the quotes (and therefore may not be human readable). The ABNF was created w/ the goal of being human readable, but the impl does not currently match the spec. Also looking back uncertain if the ABNF definition of UTF8 is correct, we may have copied it from somewhere w/o validating.

We could potentially do the following to work towards achieving this goal.

1. Update the specification to define the relaxed and strict modes of operation and the reason they exist. The relaxed parsing mode would accept any byte between quotes and be compatible w/ existing Accumulo code. The strict parsing mode would only accept UTF8 between quotes and must error when anything else is seen.
2. Double check if the existing ABNF definition of UTF8 is correct.
3. Update the java code to support strict and relaxed parsing modes.

Going to mark this as a blocker, this should be fixed before 1.0 is released.

[willmurnane]

It looks to me like the access expression parser ColumnVisibilityParser in Accumulo still assumes that the byte sequences it's parsing represent valid UTF-8. I think the best way to handle this in the specification is not to worry about the definition of how UTF-8 codepoints are represented in bytes; that's easy to find and implemented in many languages' standard library/string type. A simpler description means there's less to read, less to implement, and probably better correctness in other implementations.

If an additional mode is under consideration, I think a Unicode-normalizing mode would be a good target. The rules for doing this type of normalization are complicated, but are often implemented as part of the standard library or an easy to find package (Java, Rust, Python, etc).

[keith-turner]

A simpler description means there's less to read, less to implement, and probably better correctness in other implementations.

That sounds great, I would support simplifying the ABNF to state an authorization is utf8 without defining utf8.

It looks to me like the access expression parser ColumnVisibilityParser in Accumulo still assumes that the byte sequences it's parsing represent valid UTF-8.

I looked into this, the code is happy with non utf8 data. However there are multiple javadocs that mention UTF-8 is expected but that its not checked for like here

If an additional mode is under consideration

Not sure if that is the best solution, do need to resolve this problem in some way though and bring the spec and code into agreement while considering compatibility with existing data. Could also change the spec to state that any byte is allowed between quotes.

I wrote the following test to experiment with using non utf8 data in Accumulo (added this to VisibilityEvaluatorTest locally). Ran this test in 2.1.5-SNAPSHOT. This shows the code in Accumulo is happy and works w/ non utf8 data.

  @Test
  public void testNonUtf8() throws VisibilityParseException {
    byte[] auth1 = new byte[]{(byte) 0xf0,'a'};
    byte[] auth2 = new byte[]{(byte) 0xe0,'c'};
    byte[] auth3 = new byte[]{(byte) 0xb0,'d'};

    var decoder = StandardCharsets.UTF_8.newDecoder().onUnmappableCharacter(CodingErrorAction.REPORT).onMalformedInput(CodingErrorAction.REPORT);
    // verify the auths are not utf8
    assertThrows(CharacterCodingException.class, ()->decoder.decode(ByteBuffer.wrap(auth1)));
    assertThrows(CharacterCodingException.class, ()->decoder.decode(ByteBuffer.wrap(auth2)));
    assertThrows(CharacterCodingException.class, ()->decoder.decode(ByteBuffer.wrap(auth3)));

    VisibilityEvaluator evaluator = new VisibilityEvaluator(new Authorizations(List.of(ByteBuffer.wrap(auth1), ByteBuffer.wrap(auth2))));

    // Construct an expression avoiding passing data through String as it may corrupt/transform the data
    ByteArrayOutputStream out = new ByteArrayOutputStream();
    out.writeBytes(quote(auth1));
    out.write('&');
    out.writeBytes(quote(auth2));
    byte[] exp1 = out.toByteArray();

    assertTrue(evaluator.evaluate(new ColumnVisibility(exp1)));

    for(int i =0; i<exp1.length;i++){
      System.out.printf("%d %x %s\n", i, exp1[i], (char)exp1[i]);
    }

    out = new ByteArrayOutputStream();
    out.writeBytes(quote(auth1));
    out.write('&');
    out.writeBytes(quote(auth3));
    byte[] exp2 = out.toByteArray();

    assertFalse(evaluator.evaluate(new ColumnVisibility(exp2)));
  }

[willmurnane]

Ah, I misremembered Java semantics, I thought new String(invalidUtf8Bytes, StandardCharsets.UTF8) threw, but it doesn't, just replaces with .

I think accumulo-access would be a better standard if valid UTF-8 were required. Since access expressions are human-facing (at least at some level; for example, they're not encoded as CBOR or JSON or Protobuf or whatever), a requirement that they be human-readable in a popular encoding makes sense to me. I understand you'd probably like to keep existing Accumulo code compatible with this spec, though, so I think documenting the actual behavior you're trying to be compatible with is a good solution.

access-token            = 1*( ALPHA / DIGIT / "_" / "-" / "." / ":" / slash )
access-token            =/ DQUOTE 1*(utf8-subset / escaped) DQUOTE

utf8-subset             = %x00-21 / %x23-5B / %x5D-FF; any byte, except 0x22 '"' or 0x5C '\'
escaped                 = "\" DQUOTE / "\\" ; '\"' or '\\'
slash                   = "/"

[willmurnane]

I had missed #55 previously, and I think the proposed solution there is also good.

[keith-turner]

Re #55 that issue does not capture that the spec and code are not currently in agreement. Would be good to keep this issue open to get the spec, code, and javadocs all in sync. Also need to remove the detailed UTF8 definition.

I understand you'd probably like to keep existing Accumulo code compatible with this spec

If an accumulo 2.x system happened to have non utf8 data in an access expression then what happens if accumulo 4 uses this library and it throws an exception when it sees that data? Is that data unscannable until it is manually fixed? Also would want to avoid data being silently transformed (like non utf8 chars are just transformed to something else) if that could cause false positives or false negatives in evaluation. Not sure what the best solution to this is, but these are my main concerns.

Also wondering what the performance impact is if this code starts validating utf8 when it did not in the past. This could be determined w/ testing. But probably need to figure how compatibility should be handled first.

[dlmarion]

Created #89 that alters the internal storage of AccessExpression's and Authorization's from String to byte[]. This change, when completed, should allow us to change the specification to remove UTF8 as a restriction.

[willmurnane]

I think making this a non-text format makes it a less generally useful specification. I know for my own purposes treating access expressions as strings is an easier mental model than a “bag of bytes”. If the expression isn’t expected to be a valid string (and I think UTF-8 is the normal way of encoding that these days) then every downstream consumer of this library has to consider how to display the expression very carefully.

Additionally, if a byte-oriented format were necessary, I think the model would be simpler if it didn’t require quoting for so many bytes. It would be simpler if only ()$| required quoting (probably with \) rather than requiring double-quotes around some tokens and not others.

I think the concept of a generic access expression not tied to any particular standard is a useful one, but I think evolving this in the direction of a byte oriented format makes it less generally applicable. I would suggest making Accumulo 4.0 a breaking change in the narrow cases where people were using non-UTF-8 bytes, and providing an iterator that people can modify and run as necessary to convert the expressions on their data to valid strings.

[dlmarion]

@willmurnane - I understand where you are coming from and I mostly agree.

I'm looking at this from the following viewpoint:

1. I think we can all agree that access expressions and authorizations should be human-readable.
2. They likely are human-readable in most, if not all, cases. The tokens used in these things are domain specific and a human in most cases has to manage them at some level.
3. The current 2.x implementation allowed non-UTF-8 characters. I'm not sure how we would write an iterator that fixed a users domain specific tokens. I think the user would need to write it. Additionally, this only fixes half of the problem, if we fixed the access expressions, then we would need to fix the authorizations too.

I'm thinking that we can make the specification and implementation backwards compatible, but highly highly recommend to the users that they stick with a strict UTF-8 policy. I think @keith-turner mentioned this above in some regard. We could have two specifications, one strict and one relaxed. I don't see any harm if other implementations only want to implement the strict specification.

[keith-turner]

One path we could consider is following the blue print for what we did w/ removing table properties from system config (see apache/accumulo#4537). That could look something like the following.

1. In 2.1.5 or greater offer a new tool that can scan tables and find non utf8 visibility fields. The tool would return the key and the user could then take corrective action for those keys.
2. In the 2.1.5 pre upgrade step warn user that they should run this tool if they suspect they might have offending visibility fields.
3. In 4.0 the code will simply fail when it sees non utf8 chars on ingest and scan.

Writing an iterator that only returns non utf8 visibility keys would be easy. The harder part would be running it over all data, that would probably need to be something that could be done piecemeal.

One thing I am not sure about w/ the above is doing the validation at ingest time, what would that look like for bulk import and batch write? If scans would fail on non-utf8 data, then we would want to make it really hard to ingest that data into the system. If we do checks before the 2.1->4.0 upgrade but its still easy for users to ingest offending data after the upgrade, then it has the potential to cause unwanted surprises at scan time.

[keith-turner]

One thing that has been giving me heart burn is the idea of scans failing in 4.0 when they see non utf8. Realized the scans do not have to fail, they could just log an error and consider the data as not visible. So the scan still runs, the offending data is never seen, and maybe your logs fill up (would probably need to rate limit these messages).