directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Karasulu <>
Subject [Codec] How to make a PDU generator to produce permutions of good and bad PDU's for full test coverage
Date Sat, 20 Nov 2010 01:13:47 GMT
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:

[image: ETYPE_INFO2_ENTRY.png]
Instead of using this diagram let's draw it this way:

[image: graph.tiff]

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 ::
Apache Directory Server ::
Apache MINA ::
To set up a meeting with me:

View raw message