Last night while talking to Emmanuel= we discussed how to test the codec. I'm posting the=A0conversation=A0a= nd findings here so they're shared and we were dead tired so it might g= et forgotten.

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

First we need= to generate a network for the structure based on it's ASN TLV combinat= ions 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 thi= s diagram let's draw it this way:=A0

Here each TLV Tag is represented as a node in a n= etwork. I just annotated this new network with SEQ, etype, s2kparams, and s= alt 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 perm= utation 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:= =A0I should have drawn a start node there right before the 0x30 node.=A0Not= e that limiting cycle traversal to at least once is what produces the limit= ed set of permutations since cycles can make for an infinite number of perm= utations. Also we must at least traverse the cycle once to be able to detec= t it.

There could be cycles in the ne= twork but they will be detected and while generating the permutation tree e= ach cycle will be traversed at least once. The permutation tree is then use= d 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 easie= r while building the PDU. Each leaf to node path is a PDU and we create ran= dom values for things like INTEGERs and OCTET STRINGS etc.=A0Once these cor= rect PDUs are generated they can be fed into the codec to get positive matc= hes.

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 alte= ring the tag on each TLV node in the generated incorrect/bad PDUs. So we mi= ght have the following leaf-to-root path:

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

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

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 valu= e 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.= =A0

WDYT?