Hi Kiran, Emmanuel,

Last night while talking to Emmanuel we discussed how to test the codec. I'm posting the conversation and findings here so they're shared and we were dead tired so it might get forgotten.

The idea here is to write a PDU generator that generates a limited set of PDU's for an ASN.1 [D|B]er structure for extensively testing the validity of a codec. 

First we need to generate a network for the structure based on it's ASN TLV combinations similar but not quite the same as the diagrams being drawn on our wiki. Let's take a look at one example:

Instead of using this diagram let's draw it this way: 


Here each TLV Tag is represented as a node in a network. I just annotated this new network with SEQ, etype, s2kparams, and salt for correlation back to the original diagram off the wiki but these are not important for what we will do.

So this network graph in memory which can be read from state transition table representing the network, is used to generate a permutation tree. The permutation tree will use a depth first search algorithm to find all the paths from the state at the first node 0x30 until the end: I should have drawn a start node there right before the 0x30 node. Note that limiting cycle traversal to at least once is what produces the limited set of permutations since cycles can make for an infinite number of permutations. Also we must at least traverse the cycle once to be able to detect it.

There could be cycles in the network but they will be detected and while generating the permutation tree each cycle will be traversed at least once. The permutation tree is then used to generate correct PDUs by walking each leaf up the tree up towards the root. We do the walk from leaf to root so TLV length calculations are easier while building the PDU. Each leaf to node path is a PDU and we create random values for things like INTEGERs and OCTET STRINGS etc. Once these correct PDUs are generated they can be fed into the codec to get positive matches.

To generate incorrect PDUs we simply take each leaf to root path with N nodes and generate N PDU's from it. We do this by altering the tag on each TLV node in the generated incorrect/bad PDUs. So we might have the following leaf-to-root path:

end --> 0x02 --> 0xA0 --> 0x30 --> start

Here we'd generate 3 incorrect PDU's by making each PDU have the wrong tag value at each TLV node. 

This solves most cases for thoroughly testing a codec but it does not cover situations where values can be null or cannot be null or when values are limited to ranges or sets of valid values defined in the ASN.1 for the structure. With this we simply have to annotate the network nodes with value constraints like cannot be null or must be in some range. This way we can produce extra bad PDU's and good PDU's based on these constraints. 


Alex Karasulu
My Blog :: http://www.jroller.com/akarasulu/
Apache Directory Server :: http://directory.apache.org
Apache MINA :: http://mina.apache.org
To set up a meeting with me: http://tungle.me/AlexKarasulu