Financial Markets, Random Testing and Constraint Programming


Nowadays, all major financial markets use computer trading systems to support their trading activities. Because failures in these systems can cause serious economic damage, reliability is a top goal in their development.

Stock Exchange. By Travel Aficionado, from http://www.flickr.com/photos/travel_aficionado/2396814840/

The complex functionality that trading systems deliver makes testing them challenging. A tester with knowledge in the financial domain can generate test cases that cover the most usual trading scenarios, but it is practically impossible to come up with all the situations that will occur in production. At Cinnober, the company that develops the trading system TRADExpress, the manual generation of test cases is complemented with random testing, as an attempt to cover uncommon (yet possible) scenarios.

For random testing to be effective, an automatic mechanism that decides the correctness of each random test is needed. This mechanism is commonly called test oracle, and it can range from a simple crash check to an independent implementation of the system’s functionality.

At Cinnober fairly simple test oracles were used, which were only able to detect failures such as negative prices in trades and system crashes. Encouraged by previous success in applying random testing, we decided to develop a more complete test oracle. The test oracle would be accurate and cheap to develop and maintain, while covering a significant part of the TRADExpress functionality. As the core functionality of the system can be seen as a combinatorial problem (matching bid and ask orders placed in an order book), we chose to use a constraint model of it as the test oracle.

The functionality to test: continuous double auction

The main mechanism to match orders is called continuous double auction (CDA). In a CDA, orders are stored in an order book and matched against each other as soon as their constraints allow it. The main operations that a trader can perform are to enter, update and cancel orders. A trade order usually includes, at least, these attributes:

  • Side (bid or ask)
  • Quantity
  • Minimum acceptable quantity
  • Limit price (worst acceptable price)

Let’s see now how our CDA works through an example. Consider this order book, where orders are represented following the notation (quantity [>= minimum acceptable quantity] @ price):

Bid orders Ask orders
b1: 50 (>= 20) @ 24 a1: 15 @ 23
b2: 50 @ 22

In this state, no match between bid and ask orders is possible: the price limit constraint allows a1 to match only with b1, but this is not possible because the minimum quantity constraint of b1 cannot be satisfied. What happens if a trader enters a new order a2 with quantity 40 and limit price 24?

Bid orders Ask orders
b1: 50 (>= 20) @ 24 a1: 15 @ 23
b2: 50 @ 22 -> a2: 40 @ 24

The new order a2 gets lower priority than a1 because of its worse limit price. But now a1 and a2 can satisfy together the minimum quantity constraint of b1. Therefore the orders are matched, resulting in b1 trading 15 units with a1 and 35 units with a2. After the trade, b1 and a1 are totally filled, and the quantity of a2 is updated:

Bid orders Ask orders
b2: 50 @ 22 a2: 5 @ 24

The test oracle

As the example shows, the CDA problem is very naturally described in terms of constraints, and an optimization objective: to maximize the total traded quantity between orders in every match. This makes the implementation very direct, which is a good feature for a test oracle: a MiniZinc formulation of the problem captures the logic explained above in less than 100 lines of code! (get some example data files here). Note that the actual model used as a test oracle is, unfortunately, a little more complex: for example, it is decomposed into two steps to reflect the expected behavior of TRADExpress.

code bug. By gui.tavares, from http://www.flickr.com/photos/guitavares/1703252007/

The outcome

The most interesting part came at the end, when we ran the tests: after a few random trader operations, the constraint-based oracle reported system failures! The failures were triggered by complex scenarios, which could not be anticipated by a more systematic process based on the manual selection of test cases. Such is the result of combining the innocence of random testing with the soundness of a constraint-based oracle.

To learn more

The complete model is given in the following paper:

This application was developed as a master’s thesis between the Royal Institute of Technology (Sweden) and Cinnober Financial Technology AB. Further detail and background information is given in the master’s thesis report:

Advertisements
This entry was posted in 2010, 66 Auxiliary to Financial and Insurance Activities, 66.11 Administration of Financial Markets, CP Conference, K Financial and Insurance Activities and tagged , , , . Bookmark the permalink.

One Response to Financial Markets, Random Testing and Constraint Programming

  1. Pingback: Another Guest Post | Constraint Applications Blog by Helmut Simonis

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s