Automated combinatorial and spot testing of web service operations.

Introduction & Scope

When developing a new web service, you may need to do an initial spot test walk through the operations or try to break the service based on the permissible data type values. You could hand craft all the operations, with their respective arguments, into a handful of URLs but that would seem pretty inefficient. I found myself in a similar situation and wanted a programmatic way to walk through the service operations with a specific input data set. To be clear, I am not attempting to recreate a full web service testing application but rather a simple script to spot check responses and catch any bugs in a web service endpoint's handler.

Investigating the WSDL

We can automatically flesh out our operations and the message data types by leveraging the endpoint's WSDL. In my case, I was specifically interested in the request/response operations available under the HTTP GET verb. We can get the parameter names and argument types by looking at the types section and then the actual operations under a WSDL binding that includes an HTTP binding element with the verb attribute value of GET.

Fortunately, I am dealing with input messages using just the built in data type schema provided by the WSDL specification. This means that no complex types are involved and the testing input domain is somewhat simplified. Also, most of the web service operations use a standard set of parameter names such that I am able to create a smaller data set of inputs based around them.

The Code

Your modifications would be to the test_args dictionary. You can specify a wide range of different arguments to feed your operations by parameter names. The service I was testing against used many of the same parameter names and corresponding domain.

Conclusion

Thrown together, the script provides an easy way to spot test a web service by automatically processing the WSDL for a particular binding and running those bound operations against a provided set of input messages for it.

More Reading & Resources

• Wikipedia: Web Services Description Language
• MSDN: Understanding WSDL

Text generation using Markov chains.

Introduction

If you are already familiar with finite automata, then understanding a Markov chain will not be as hard. If you are not familiar with one, you can think of finite automata as a flowchart, with states and paths leading from one state to another based on some decision being made. An example could be a room with a light switch; there are the two states of having the light on or off. Using the light switch will transition you between the two states.

The difference between standard finite automata and Markov chains is that instead of having some definite outcome determining each path (eg. yes or no), they are probabilities. Take for example a coin flip, there is a 50% (0.5) chance that it could either be heads or tails.

An Example

Let's explore Markov chains a little deeper with respect to natural languages and take a look at some sample text that will form the corpus of our analysis.

I like turtles. I like rabbits. I don't like snails.

This would render a Markov chain as follows:

The above chain means that, among the sentences:

• 100% (1.0) will start with I.
• This will be followed by like for 66% (0.66) of the time and don't for 33% (0.33) of the time.
• The word don't will always (100% / 1.0) be followed by like.
• Then lastly, turtles, rabbits and snails will all follow like 33% (0.33) of the time.

The nice thing about Markov chains, with respect to natural language modelling, is that they form word dependencies without any knowledge of the language's syntax or semantics. The chain gets created purely based on statistical knowledge extracted from the corpus.

Text Generation

Random Selection

Using the Markov chain example from before and taking the weight of probabilities into account, we can randomly traverse the chain to generate new sentences like:

I don't like turtles. I like snails.

Although, our small corpus does not make for very interesting or new text. We could make it more interesting by adding to it or switching to a much larger corpus altogether. In my case, I decided to take all of Shakespear's sonnets and generate the text from that. You can see some example code that uses it as the corpus below.

The Code

The Markov chains will be built up for each new sentence it comes across. The critical parts to the MarkovChain object are its:

• Cardinalities: The cardinality of the sample space for a given state. In our original example, the cardinality of like is 3 since snails, rabbits and turtles follow out of the like state. The cardinality of I would be 2 since don't and like follow.
• Occurrences: The edge valued occurrences between the different states. For example, a transition from the I to like state occurred twice. The probability can then be easily calculated by taking the number of occurrences on a transition and divide it by the cardinality of the state's sample space. Note, there is also a special start state transition that can be used at the beginning of each new sentence generation.

Using these two parts, a random walk can be made across a chain path, starting from the special start state. Each walk will generate a new sentence based on probabilities of the transitions along the path.

Additional Resources

• Wikipedia: Stochastic Grammar
• Wikipedia: Natural language generation
• Princeton CS206: Markov Model of Natural Language
• Markov-chain Text Generator
• ACL Special Interest Group on Natural Language Generation (SIGGEN)

Detecting cycles in decimal digits and lists.

I was recently working on solving problem 64 for project Euler and one of the needed algorithms was a detection of cycles in a list. This routine works for detecting cycles in lists of cardinality greater than 2.

def get_cycle_len(N):
  i = k = 0
  for j in range(2, len(N)):
    if N[i] == N[j]:
      if k == 0:
        k = j
        i = 1
      else:
        if i == k:
          return k
        i += 1
    else:
      i = 0
      k = 0
  return -1