Constraint programming for random testing of a trading system

Constraint Programming for Random Testing of a Trading System Roberto Casta˜neda Lozano Master’s thesis. Stockholm, January 28, 2010. School of Information and Communication Technology KTH Royal Institute of Technology School of Engineering in Computer Science Polytechnic University of Valencia Reference: II-C2-DSIC24/09 Constraint Programming for Random Testing of a Trading System Roberto Casta˜neda Lozano Supervisors Christian Schulte (Royal Institute of Technology, Sweden) Lars Wahlberg (Cinnober Financial Technology AB, Sweden) Federico Barber (Polytechnic University of Valencia, Spain) Examiner Federico Barber This master’s thesis has been developed in the context of an exchange program between the School of Engineering in Computer Science at the Polytechnic University of Valencia and the School of Information and Communication Technology at the Royal Institute of Technology, Sweden. The thesis was defended and examined in January 2010 at the Royal Institute of Technology, obtaining a grade of A in the ECTS grading scale. The project has also been awarded the Swedish Artificial Intelligence Society (SAIS) Best AI Master’s Thesis Award 2010. Abstract Financial markets use complex computer trading systems whose failures can cause serious economic damage, making reliability a major concern. Automated random testing has been shown to be useful in finding defects in these systems, but its inherent test oracle problem (automatic generation of the expected system output) is a drawback that has typically prevented its application on a larger scale. Two main tasks have been carried out in this thesis as a solution to the test oracle problem. First, an independent model of a real trading system based on constraint programming, a method for solving combinatorial problems, has been created. Then, the model has been integrated as a true test oracle in automated random tests. The test oracle maintains the expected state of an order book throughout a sequence of random trade order actions, and provides the expected output of every auction triggered in the order book by generating a corresponding constraint program that is solved with the aid of a constraint programming system. Constraint programming has allowed the development of an inexpensive, yet reliable test oracle. In 500 random test cases, the test oracle has detected two system failures. These failures correspond to defects that had been present for several years without being discovered neither by less complete oracles nor by the application of more systematic testing approaches. The main contributions of this thesis are: (1) empirical evidence of both the suitability of applying constraint programming to solve the test oracle problem and the effectiveness of true test oracles in random testing, and (2) a first attempt, as far as the author is aware, to model a non-theoretical continuous double auction using constraint programming. Keywords: constraint programming, random testing, trading system, test oracle, continuous double auction. Programaci´on con restricciones aplicado a la prueba aleatoria de sistemas de comercio electr´onico Roberto Casta˜neda Lozano Resumen Los mercados financieros emplean sistemas de comercio electr´onico complejos, en los que fallos de ejecuci´on pueden acarrear graves perjuicios econ´omicos: su fiabilidad es, por lo tanto, un objetivo principal. La ejecuci´on de pruebas aleatorias ha demostrado ser ´util en la detecci´on de defectos en estos sistemas, pero el problema del or´aculo (c´omo generar autom´aticamente la salida esperada del sistema) ha impedido una implantaci´on mayor de esta t´ecnica. Este proyecto plantea una soluci´on al problema del or´aculo que consta de dos fases: en primer lugar, utilizando programaci´on con restricciones se ha creado un modelo de un sistema real de comercio electr´onico. Posteriormente, el modelo se ha integrado como un or´aculo en pruebas aleatorias autom´aticas. El or´aculo mantiene el estado esperado de un libro de ´ordenes durante una secuencia de acciones aleatorias y, para cada subasta ejecutada, proporciona la salida esperada, a trav´es de la resoluci´on de un problema de satisfacci´on de restricciones. El uso de programaci´on con restricciones ha posibilitado el desarrollo de un or´aculo de prueba fiable a la vez que econ´omico. En 500 pruebas aleatorias, el or´aculo ha detectado dos fallos en el sistema. Estos fallos corresponden a defectos que hab´ıan estado presentes en el sistema sin ser descubiertos por or´aculos menos completos ni por otros enfoques m´as sistem´aticos. Las principales contribuciones de este proyecto son: (1) la demostraci´on emp´ırica de la idoneidad de usar programaci´on con restricciones como soluci´on al problema del or´aculo y de la efectividad de utilizar or´aculos completos en las pruebas aleatorias, y (2) el primer modelo documentado de una doble subasta continua de un sistema real utilizando programaci´on con restricciones. Palabras clave: programaci´on con restricciones, pruebas aleatorias, sistemas de comercio electr´onico, or´aculos, doble subasta continua. Programaci´o amb restriccions aplicat a la prova aleat`oria de sistemes de comer¸c electr`onic Roberto Casta˜neda Lozano Resum Els mercats financers empren sistemes de comer¸c electr`onic complexos, en els quals fallades d’execuci´o poden implicar greus perjudicis econ`omics: la seua fiabilitat ´es, per tant, un objectiu principal. L’execuci´o de proves aleat`ories ha demostrat ser ´util en la detecci´o de defectes en aquests sistemes, per`o el problema de l’oracle (com generar autom`aticament l’eixida esperada del sistema) ha impedit una implantaci´o major d’aquesta t`ecnica. Aquest projecte planteja una soluci´o al problema de l’oracle que consta de dues fases: en primer lloc, utilitzant programaci´o amb restriccions s’ha creat un model d’un sistema real de comer¸c electr`onic. Posteriorment, el model s’ha integrat com un oracle en proves aleat`ories autom`atiques. L’oracle mant´e l’estat esperat d’un llibre d’ordres durant una seq¨u`encia d’accions aleat`ories i, per a cada subhasta executada, proporciona l’eixida esperada, mitjan¸cant la resoluci´o d’un problema de satisfacci´o de restriccions. L’´us de programaci´o amb restriccions ha possibilitat el desenvolupament d’un oracle de prova fiable alhora que econ`omic. En 500 proves aleat`ories, l’oracle ha detectat dues fallades en el sistema. Aquestes fallades corresponen a defectes que havien estat presents en el sistema sense ser descoberts per oracles menys complets ni per altres enfocaments m´es sistem`atics. Les principals contribucions d’aquest projecte s´on: (1) la demostraci´o emp´ırica de la idone¨ıtat d’usar programaci´o amb restriccions com a soluci´o al problema de l’oracle i de l’efectivitat d’utilitzar oracles complets en les proves aleat`ories, i (2) el primer model documentat d’una doble subhasta cont´ınua d’un sistema real utilitzant programaci´o amb restriccions. Paraules clau: programaci´o amb restriccions, proves aleat`ories, sistemes de comer¸c electr`onic, oracles, doble subhasta cont´ınua. Acknowledgements This master’s thesis has benefited from the advice, guidance and deep knowledge of my supervisors Christian Schulte, Lars Wahlberg and Federico Barber, who are truly experts in their respective fields. I am profoundly grateful to them. I am indebted to my girlfriend Eleonore L¨ovgren and my good friend and colleague Carles Tom´as Mart´ı for providing valuable feedback on earlier versions of this report. Finally, I wish to thank my parents and my little brother for their support and love, which I strongly feel despite the long distance that keeps us apart. Contents 1 Introduction 1 1.1 Background ............................... 1 1.2 Previous work at Cinnober . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problemstatement ........................... 3 1.4 Proposedsolution............................ 3 1.5 Relatedresearch............................. 5 1.6 Reportoverview............................. 6 2 Random testing 7 2.1 Introduction............................... 7 2.2 Input................................... 8 2.3 Oracles.................................. 9 2.4 Testoutput ............................... 12 3 Constraint programming 15 3.1 Introduction............................... 15 3.2 Constraint problem modeling . . . . . . . . . . . . . . . . . . . . . 16 3.3 Constraint problem solving . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Availablesystems............................ 22 4 The trading system 25 4.1 Introduction............................... 25 4.2 Structure ................................ 26 4.3 Tradeorders............................... 28 4.4 Ordermatching............................. 31 4.5 The testing framework . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Development of the test system 37 5.1 Introduction............................... 37 5.2 Systemoverview ............................ 38 5.3 Requirements .............................. 38 5.4 Designspecification........................... 41 5.5 Computation of the expected trades . . . . . . . . . . . . . . . . . . 49 5.6 Implementation............................. 56 5.7 Practical aspects of the development process . . . . . . . . . . . . . 59 6 Results and analysis 63 6.1 Introduction............................... 63 6.2 Characteristics of the order book oracle . . . . . . . . . . . . . . . . 64 6.3 Randomtestcases ........................... 67 6.4 Problems found in the trading system . . . . . . . . . . . . . . . . . 69 6.5 Impact of the order book oracle . . . . . . . . . . . . . . . . . . . . 71 7 Conclusion and further work 73 7.1 Conclusion................................ 73 7.2 Furtherwork .............................. 75 References 77 Glossary 81 A Java code documentation 85 A.1 OrderBookActor ............................ 85 A.2 OrderBookOracle............................ 87 A.3 OrderBookModel ............................ 88 B Test cases for the order matching 91 B.1 Test cases for the order matcher . . . . . . . . . . . . . . . . . . . . 91 B.2 Test cases for the order re-matcher . . . . . . . . . . . . . . . . . . 97 List of Figures 2.1 Random testing model with an oracle . . . . . . . . . . . . . . . . . 10 3.1 Search tree for the Send More Money problem............ 21 3.2 Search tree for the constrained Send Most Money problem . . . . . 22 4.1 Basic architecture of TRADExpress .................. 27 4.2 Usual structure of an order book representation . . . . . . . . . . . 28 4.3 Order book after consecutively inserting b4,b3,b2,b0and b1. . . . 31 4.4 UML activity diagram of an order insertion/update in TRADExpress 33 4.5 Architecture of the TRADExpress testing framework . . . . . . . . 35 4.6 Basic components of a simulation . . . . . . . . . . . . . . . . . . . 36 5.1 Main components and interactions of the system . . . . . . . . . . . 38 5.2 UML sequence diagram of an action performed on TRADExpress . 42 5.3 Simplified UML class diagram of the test system . . . . . . . . . . . 43 5.4 Trade orders taxonomy for the input domain modeling . . . . . . . 44 5.5 UML sequence diagram of the calculation of the expected trade events 46 5.6 Example of a test script with one oracle and one actor . . . . . . . 58 5.7 Timeline of the development process . . . . . . . . . . . . . . . . . 60 6CHAPTER 1. INTRODUCTION 1.5.3 Constraint programming and trading systems The system to be modeled in this project can be seen as a continuous double auction (which is the term typically used in the research literature). The study of this problem has attracted much interest from different areas. Several articles present theoretical models formulated using constraint programming [31, 23] or closely related techniques such as integer programming [20]. Unlike the work presented above, this project aims to create a model of an existing trading system, which is used in several financial markets around the world. Aspects like order priority or visibility, which are usual issues in most of the existent trading systems [14, Ch. 2, Appx.], do not seem to have been previously considered in research constraint programming models. 1.6 Report overview This report can be clearly divided into two main blocks: the first four chapters introduce the problem that the thesis deals with and its proposed goals, as well as the basic knowledge that the reader may need to understand the developed work; the rest of the chapters explain the development of the proposed solution, its evaluation and the drawn conclusions. The most frequent terms related to the main concepts used in this work are compiled in a glossary at the end of the report. Chapter 2 deals with the foundations of automated random testing of software systems, with a focus on the test design process. Chapter 3 shows the main principles of constraint programming: how problems can be specified, and how they are typically solved by constraint programming systems. Chapter 4 includes an overview of Cinnober’s TRADExpress system, with a focus on those aspects that are relevant for the aim of this project. Chapter 5 contains a description of the design process of the order book model and the way it is introduced into the trading simulation framework. The chapter explains and justifies the main implementation decisions. Chapter 6 shows results related to each goal presented above and discusses in which degree the chosen solution approach solves the presented problem. Chapter 7 presents the drawn conclusions and proposes possible further work in the area. Chapter 2 Random testing 2.1 Introduction The development of a software system is constantly exposed to errors, understood as human actions that produce incorrect results. As a consequence of an error, a software system may contain defects, also called bugs: flaws that may cause the system to fail to perform its required function. The execution of a software system that contains defects may finally cause deviations from its expected behavior, called failures [11]. A desirable goal for all software systems is to reduce their number of defects, so that less failures are experienced when using it. Another important goal is to ensure that a system meets the specified requirements and serves the purpose for which it has been created. These goals are achieved in software development by applying testing: software testing is the process of both detecting defects in a system and determining if it meets the requirements and fits its purpose [11]. Software testing can be roughly classified into functional and non-functional testing. Functional testing analyzes the specification of the system’s functionality, while non-functional testing analyzes the system’s quality characteristics, such as its performance or its usability. Functional testing is often also referred to as black-box testing, because it does not refer to the system’s internal structure (even though black-box testing can be also applied to non-functional testing) [11]. Software testing can be classified as well into manual testing (performed manually) and automated testing (performed with the help of a computer system). Because of its flexibility, manual testing can be very effective in finding system failures, but when tests are too time consuming or require high precision, it might be a better option to automate them. In this way, the cost of running several times a test case is reduced, and greater consistency and repeatability can be achieved, which is very important, for example, for regression testing purposes [11]. 7 8CHAPTER 2. RANDOM TESTING An automated test case that does not change from one execution to another is considered to be only at a first stage of automation [17]. A more advanced level in test automation includes auto-generation of test cases, and mechanisms to automatically detect system failures. Random testing is a black-box technique that can be found on this level: in random testing, the test cases are selected randomly over a pre-selected domain, and a so-called oracle is typically used to automatically detect failures in the system. By randomizing automatic tests, a greater coverage is obtained, and new errors can be found in every new test run [17]. The following sections in this chapter deal with three main aspects that are critical for a successful application of random testing: Section 2.2 explains how the input data can be designed and generated, Section 2.3 shows how oracles are integrated in the testing model and which types of oracles can be designed, and Section 2.4 discusses different aspects related with the management of the output obtained from the application of random testing. 2.2 Input There are three main characteristics that determine the input in random tests: the domain from which the input is extracted, the distribution that the input data follows, and the size of the input. How these characteristics are designed is a key decision in random testing. A poor design of any of them will lead to poor results, regardless of the quality of the oracle or the output analysis that is performed [18]. 2.2.1 Domain The input domain of a complex system can be considered practically infinite, and the selection of a meaningful subset strongly depends on each system and the testing goals. A common approach is to partition the domain into sub-domains corresponding to different functionalities of the system, defining thus clusters of similar input actions. This makes it possible to assign a different probability or weight to each action, making a so-called operational profile, which can be used as a model for the test input domain [13]. 2.2.2 Distribution The distribution for the input data is determined by assigning probabilities to the operational profile, whose structure is determined by the considered domain. Two fundamental approaches can be applied, depending on the testing goals: the operational profile can be chosen so that it models realistic system input, helping thus to asses the reliability of the system (see Subsection 2.4.2); or it can be chosen so 2.3. ORACLES 9 that it represents completely unrealistic system input, making it possible to detect low frequency defects whose failures would be hard to cause with more systematic testing [12]. Creating a realistic input model for a complex system is not trivial. Different techniques can be applied in order to create an operational profile that matches the expected system usage. A common one is to apply statistical methods to historical data of the software system in order to create a model that is representable as an operational profile. Operational profiles for newly created functionality require alternative estimation methods. Further detail about how to develop operational profiles can be found in [27]. 2.2.3 Size A complex system usually requires that a test case comprises a sequence of actions, specially if it includes persistent state [13]. The question that immediately arises then is how many actions, or long running time is enough for making a meaningful test case? The answer depends, once again, on the testing goals and the structure of the system: •If the intention is to make a realistic simulation, the running time should be long enough to reproduce a typical sequence of actions that depend on each other. There is usually no need to reproduce a whole typical system session, if such concept exists in the system under test [27, p. 22]. In this case, the running time could be modeled from analysis on real input data. •If the intention is instead to deliberately create unrealistic random tests, the length can be chosen in an ad-hoc manner. For example, the input size can be determined from experience from previous projects, coverage vs. running length optimization, or even randomly as well. 2.3 Oracles A test oracle can be generally defined as a source to determine expected output to compare with the actual output of the software under test [11]. In the context of automated testing, a test oracle is an alternate program or mechanism that provides that information [16]. There is a broad range of test oracles, from basic routines that check essential properties of the system to duplicates of the system under test that are able to generate the expected output for all possible inputs. The basic model used in random testing with an oracle is shown in Figure 2.1. A critical success factor in random testing is to have a good mechanism to verify the system output. Without applying oracles in random testing only spectacular 10 CHAPTER 2. RANDOM TESTING failures can be detected [15]. This strategy can still be convenient in systems where inconsistent or erroneous states frequently lead to system crashes (see [19] for an example). Random input Test oracle System under test Actual output Expected output = ? Test result Figure 2.1: Random testing model with an oracle 2.3.1 Characteristics As mentioned above, many different types of oracles can be used in random testing. Oracles vary widely in attributes such as complexity, completeness or independence from the system under test. Table 2.1 lists the main characteristics that must be considered in the design of an oracle together with a brief description in the form of some questions that each characteristic proposes. Characteristic Description Completeness Which input is covered? Which failures can be detected? Accuracy How similar is to the system under test? How independent? Usability How is the information given? Does it fit the intended use? Maintainability How complex is the oracle? How costly is it to update it? Performance How fast does it generate output? How often must be run? Cost How much does it cost to make it? How much to execute it? Table 2.1: Main characteristics of a test oracle (source: [18]) As in every software system, many trade-offs must be taken into account in the design of a test oracle. The more complete and accurate an oracle is, the more complex (and therefore less maintainable and more expensive) it will be. A complex oracle is more likely to contain defects and thus lead to false alarms in the comparison between expected and actual output. A complex oracle is generally more sensitive to changes in the system under test, and therefore harder to maintain. If 2.3. ORACLES 11 the test oracle shares components with the system under test, defects can be missed because of both the oracle and the system under test generating the same wrong output due to a defect in the shared component. 2.3.2 Types of oracles Although different test oracles vary widely in the characteristics discussed in Subsection 2.3.1, four main types can be identified: true oracle, consistent oracle, selfreferential oracle and heuristic oracle. Not using a test oracle at all, as discussed at the beginning of this section, is sometimes identified as a strategy as well. For a more detailed taxonomy of test oracles, see [15]. The decision of which test oracle type to use depends on many factors, such as the nature of the system under test and the testing goals, the availability of existing oracles, the cost of creating a new oracle and the recognition of useful heuristics. Many times, a combination of different oracle strategies can be the most effective way of making the most of random testing. True oracle A true oracle is an independent implementation of the system under test that reproduces the output that is expected from it. The independence can be achieved by, for example, using different algorithms or development platforms, and ensures that the same design defects will not appear in both systems. This type of oracle can be very expensive to implement and maintain, so completeness is not usually achieved. Instead, true oracles are usually applied to test the system for specific input sub-domains. Consistent oracle A consistent oracle uses the system output from a previous test run as the expected out for the next one. Therefore, differences in the system output from two consecutive runs are considered as failures by the test oracle. This type of oracle is especially useful for regression testing. Because the correctness of the output from the system under test is not being directly evaluated, a broad range of the input domain can be used. On the other hand, historical defects are likely to remain undetected, as the potential wrong output does not change over the different runs. Self-referential oracle A self-referential oracle embeds expected system output within the input data. When using this type of oracle, the random generator seed is usually included in the test input, in order to be able to repeat a specific test run. An independent analysis 12 CHAPTER 2. RANDOM TESTING is usually run at the end to identify system failures. In this way, the test execution (which is performed first) and the system’s output verification are decoupled. A great advantage of this is that post-test analysis can be applied extensively, and it can be always extended without the need of modifying the tests. Heuristic oracle A heuristic oracle verifies some characteristics of the system output by exploiting detected patterns in it. Unlike the true oracle, a heuristic oracle cannot decide if a certain system output is correct, but it can be very effective in detecting system failures in cases where there are simple and predictable relationships between input and output. In comparison with the true oracle, a heuristic oracle is simple to develop and maintain (because of its lower complexity), and fast to run. On the other hand, because of its simplicity, it can fail to detect those system failures which break complex patterns and which often respond to the most “interesting” system defects. 2.4 Test output In order to make it possible to find the defects that exist behind failures detected by random tests, some post-processing is usually needed. But the output of a random test is not only useful to find system failures: some common reliability models can be estimated by applying statistical analysis to it. 2.4.1 Test case reduction One of the main goals of every kind of software testing is, as discussed at the beginning of this chapter, to find failures in the system under test. When a failure is encountered, the defect that causes it still needs to be found. The process of looking for the defect that causes a certain failure in a system is commonly called debugging. Even though debugging falls out of the scope of the testing activities [11], it can be facilitated by simplifying the output of a failed test case. As discussed in 2.2.3, random test cases for systems with persistent state are usually in the form of sequences of actions, which depending on the system’s nature may necessarily be long. When such a test case detects a failure, it can be very hard to find the defect that is causing it, because of the length and complexity of the action sequence. It is usual, therefore, to apply test case reduction to the failed test case in order to find a simpler one that causes the same failure. A reduction process for a random test case can be very tedious, so automation is very desirable. Delta debugging, for example, is a general automatic technique that 2.4. TEST OUTPUT 13 obtains minimal equivalent test cases. The algorithm takes as input the test case and a function that tells whether the test has passed or not. The test case is run then over and over again under changed circumstances until the minimum instance that still causes the system failure is found. Further detail is given in [36, Ch. 13]. 2.4.2 Reliability estimation Software reliability can be defined as the ability of a software system to perform its required functions for a specified period of time or number of operations [11]. Reliability assessment is often included in the list of goals of software testing. By analyzing the output from several random tests applied to a system, various reliability models can be built. A basic measure that is used in many of them is the failure rate, which can be defined as the number of expected failures per time unit and is usually represented by the symbol λ. A class of models that is widely used in software reliability estimation describes failure processes by non-homogeneous Poisson processes [35, Ch. 4]. By simply calculating the average time between failures from the test output, the Mean Time Between Failures (MTBF) can be obtained, and thus the failure rate λ=1 MT BF . The number of failures in a period of time is modelled as a variable X∼Pois(λ). The probability that kfailures will occur in a time Tcan be then calculated in the following way [19]: P{X=k}=(λT)k k!e−λT The application of reliability models usually require some assumptions, whose validity may depend on the special circumstances of each system. Some of the most usual ones required in times between failure models are [19]: •Times between failures are independent. •No new defects are introduced during the defect removal process. •Each defect has equal probability of exposure. •The system is immediately repaired after a failure. •Failure rate is proportional to the number of remaining defects. The accuracy of a model obtained from random testing output depends not only on the validity of the required assumptions and the statistical confidence of the estimated measures, but also on how realistic the test input is designed. 14 CHAPTER 2. RANDOM TESTING Chapter 3 Constraint programming 3.1 Introduction Constraint programming is a programming paradigm used to model and solve problems with a discrete set of solutions. A big part of its power lies in its declarative nature, summarized in this quote: Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. (Eugene C. Freuder [8]) In constraint programming, the model of a problem is given by a set of variables with finite domains (so they can take a finite number of different values) and a set of relations between these variables, called constraints, that must hold in every solution [22]. Such a model is called constraint satisfaction problem (CSP), or simply constraint problem. The solutions to this problem (all possible combination of values for the defined variables for which the given constraints hold) are automatically solved by a constraint programming system. Optionally, a cost function (also called objective function) over the variables can be added to the model in order to express preference between several solutions. The solutions become, in this case, the subset of the solutions to the former problem where the cost function is minimized or maximized. Constraint programming is a particularly useful technique for dealing with combinatorial, typically NP-complete, real life problems. One of its most successful application areas is probably scheduling and planning problems, but there are many others, such as power networks and bioinformatics. Some other areas where constraint programming has recently started to be applied are, for example, formal software verification and optimization of computer programs [30, 33]. In the software testing area, the technique is mainly used to generate test data in automated testing (see Subsection 1.5.2). 15 22 CHAPTER 3. CONSTRAINT PROGRAMMING has been added in order to generate a simpler search tree. The same propagators and search strategy as in the previous example has been used. As it can be seen, the first valid combination of values, with cost 10875, is found in the node 3. Immediately after the solution is detected, a propagator representing the following constraint is added: 10000 ×M+ 1000 ×O+ 100 ×N+ 10 ×E+Y > 10875 The next explored node (4) gives a new solution that satisfies this constraint, because its cost is 10876. Therefore, the propagator is updated with the new maximum found cost: 10000 ×M+ 1000 ×O+ 100 ×N+ 10 ×E+Y > 10876 Because the maximum possible value for the cost function under the node 5 is 10876, this node is pruned and the search finishes. 1 5 2 43 Node D E M N O S T Y 1[2..4] 7 1 8 0 9 [2..4] [4..6] 22 7 1 8 0 9 [3..4] [5..6] 32 7 1 8 0 9 3 5 42 7 1 8 0 9 4 6 Figure 3.2: Search tree and possible values for the constrained Send Most Money problem As mentioned above, the solution that maximizes the cost function is given by the node 4: {D7→ 2, E 7→ 7, M 7→ 1, N 7→ 8, O 7→ 0, S 7→ 9, T 7→ 4, Y 7→ 6} 3.4 Available systems A constraint programming system is a computer system that provides a set of reusable services, such as propagation and search (see Section 3.3), for solving constraint problems. The early existence of mature constraint programming systems is one of the most important causes for the width of the application field of this technique [30, Ch. 14]. In this section, a very brief survey of some of the main available constraint programming systems will be given. 3.4. AVAILABLE SYSTEMS 23 The existent systems can be classified depending on if they are standalone (that is, programming languages, typically extensions of some declarative language such as Prolog, or programs by themselves), or they are delivered as libraries written in a mainstream, imperative language such as Java or C++. 3.4.1 Standalone constraint programming systems The traditional approach to build constraint programming systems has been to extend Prolog systems with constraint capabilities. Two examples of this approach are SICStus Prolog, and ECLiPSe, which are respectively proprietary and licensed under a variation of the MPL license. It is possible to adapt both systems to perform parallel search, although none of them formally supports it at the time of writing this report. An alternative approach to the Prolog extension is that of Minion, a system built in C++ that takes a file describing a CSP problem and returns its solution. This lack of interface flexibility allows Minion to be efficient and simple at the same time. Minion is licensed under the GPL license. 3.4.2 Library constraint programming systems The constraint system that pioneered the idea of a constraint programming library is ILOG Solver [30, Ch. 14], a proprietary system owned by IBM which is accessible from several mainstream imperative languages, such as Java, C++, and .NET. In the free software category, several libraries such as Choco and JaCoP (implemented in Java) or Gecode (implemented in C++) can be mentioned. While both Choco and JaCoP (licensed respectively under the BSD and AGPL license) set their main focus on ease of use, Gecode (licensed under the MIT license) has openness and efficiency as its main goals, supporting parallel search and showing good performance results in its website. 24 CHAPTER 3. CONSTRAINT PROGRAMMING Chapter 4 The trading system 4.1 Introduction A financial market is, as mentioned in the introduction of this report, a system that allows buyers and sellers to trade and exchange items of value such as commodities and equity shares. Financial markets have been revolutionized during the last decades by the fast development of computer systems and networks and the introduction of important regulatory changes. Today, almost all financial markets in the world use electronic trading systems, which are subject to challenging requirements in terms of efficiency, flexibility and reliability [34]. TRADExpress, the target system of this master’s thesis, is a trading system developed by a Swedish company called Cinnober that aims to meet the demanding requirements of nowadays’ financial markets. TRADExpress is a complex system developed entirely in Java that supports many different market structures and models, and comprises several components that sum up to millions of lines of code [5]. In this chapter, an overview of the most essential aspects of TRADExpress is given, with a focus on those parts that are targeted by the developed random tests. Section 4.2 introduces the essential business modules and architecture of TRADExpress. Section 4.3 explains the different types of trade orders that TRADExpress allows, and how they are organized in the system. Section 4.4 deals with how trade orders are matched against each other in different trading mechanisms. Finally, Section 4.5 gives an overview of the framework that is used in Cinnober for testing TRADExpress at the system level. 25 26 CHAPTER 4. THE TRADING SYSTEM 4.2 Structure 4.2.1 Instruments A financial instrument (usually called in this context just instrument) can be described as an item of value, not necessarily physical, on which trades can be performed. A financial market usually offers different instruments of a specific type to trade with [34]. TRADExpress makes it possible to manage several markets, where instruments of different types can be organized in a hierarchical structure with different depth levels [5]. 4.2.2 Market participants Market participants can be defined as the people and institutions that interact in a financial market. Their structure and organization depends on each type of market, but it is generally possible to identify four main types of participants [34]: •Customers: invest or disinvest their money by buying and/or selling negotiable instruments. •Brokers: act as agents on behalf of customers, in order to facilitate the access to markets. •Dealers: trade on own behalf, assuming thus the risk of their operations. •Market makers: make money by selling to a higher price than they buy to. Add continuity to the market trade flow by ensuring that there is always a counterpart to trade with. TRADExpress offers an abstract participant model that supports many different configurations. In TRADExpress, all participants belong to some member. The type of participant is defined by its user roles, which state the allowed actions and the information access rights. The market administrators are just defined as participants with special roles. By combining different roles, this model makes it possible to define a rich set of participant types [5]. 4.2.3 System architecture TRADExpress has a complex architecture, designed to deal with demanding reliability, flexibility and performance requirements. From the user’s perspective, TRADExpress can be seen as a system that follows a classical client-server model, where the whole system acts as a service provider to connected clients. However, the system itself is made up of several servers, which can be in its turn replicated. 4.2. STRUCTURE 27 Furthermore, the architecture of each server is divided into three abstraction layers: the base layer acts as a platform, and includes middleware and persistence services. Above this, the generic trading engine is built with all the standard business components. On top of the system, a customization layer allows to add customer specific business rules and trading strategies [4]. Even though TRADExpress comprises many different servers, four main ones provide the basic functionality that this project needs to consider (see Figure 4.1): •Trading Application multipleXer (TAX): handles connections with clients, converts protocols and routes transactions. •Matching Engine (ME): handles the business functionality of the system, including the processing of trade orders and the information dissemination to different connections. •Query Server (QS): maintains a copy of the state for different instruments, and serves some client queries in order to lower the load of the ME. •Common Data (CD): acts as a repository for the system’s reference data, containing information, for example, about the defined users and instruments. TAX CD ME QS Server sideClient side Figure 4.1: Basic architecture of TRADExpress (adapted from [4]) TRADExpress can be accessed by clients by using two main protocols: External Messaging Application programming interface (EMAPI) and Financial Information eXchange (FIX). EMAPI is a proprietary protocol which is explicitly designed to access TRADExpress, providing low latency and full functionality [4]. FIX is a standard, widely used protocol for trading systems maintained by FIX Protocol Ltd. In both cases, TCP/IP is used at the transport layer when connecting to TRADExpress. 28 CHAPTER 4. THE TRADING SYSTEM 4.3 Trade orders 4.3.1 Order books The main aim of a trading system is to store and match trade orders placed by different participants. This function is performed in a component called order book, which is already identified as a core component of every trading system at the introduction of this report. The order book can be seen as a register of the orders that are placed in a certain instrument and have not been matched yet. It is usual to represent it as a table with two columns, respectively containing the buy orders (bid side), and the sell orders (ask side). In both cases, the orders are sorted by priority, having the top order the highest priority (see Figure 4.2). Bid orders Ask orders b0: bid order with highest priority a0: ask order with highest priority . . .. . . bn: bid order with lowest priority am: ask order with lowest priority Figure 4.2: Usual structure of an order book representation Depending on the scope, two main types of order books can be defined [34]: •Public order books: show the orders from all participants anonymously. •Private order books: show the orders that a specific participant has placed, and contains information that belongs to the private scope of those orders. In TRADExpress, several order books can be defined for an instrument. When using the EMAPI protocol, information about the state of an order book is obtained by participants by setting subscriptions on the message dissemination flows that are of interest. The following flows are considered in this project [3]: •Order book event flow: contains events with information about the state of an order book, such as order placements, updates and cancellations. •Trade flow: contains events with information about the trades which occur (that is, which are executed) as a result of order matchings in the order book. Both flows have public and private versions, containing the private ones extra information about the disseminated events. 4.3. TRADE ORDERS 29 4.3.2 Order attributes The wide range of trading strategies that are applied in financial markets nowadays calls for orders where many different conditions and preferences can be expressed. This is modeled in TRADExpress by defining several attributes that can be attached to an order. The main ones are shown in Table 4.1. Attribute Description Order book Specifies the order book where the order will be placed. Side Specifies if the order must be placed in the bid or ask side of the order book, i.e., if it is a buy or sell order. Quantity Specifies the amount of instrument units that it is desired to trade with. It is possible to specify a minimum quantity, as well as the part of the quantity that is shown in the public order book. Price condition Specifies which prices are accepted for trading and how they should be formed: •Market price: the order will be executed at the price set by the market. •Limit price: the order will be executed if the trade price is as good or better than a given one. •Pegged price: the accepted execution price of the order depends on other prices. Visibility Specifies if the order is transparent (visible in the public order book), or dark (visible only in the private order book). Validity period Specifies the start and end of the period when an order is allowed to match. Table 4.1: Main order attributes in TRADExpress (source: [34]) 4.3.3 Order types The combination of the attributes mentioned in Subsection 4.3.2 provides the user of TRADExpress with a wide range of available order types, which make it possible to apply different trading strategies. The most common order types are shown in Table 4.2. Besides the attributes mentioned in this table, a trade order in TRADExpress must always specify the order book, side and quantity q. 30 CHAPTER 4. THE TRADING SYSTEM Type Description Characteristic values Market Executed at the price set by the market and then cancelled. Price condition: market price Validity period: first match only Limit Executed if the price is equal or better than p. Price condition: limit price Limit price: p Fill-or-kill (FoK) Either executed at the whole quantity qwhen inserted or cancelled. Minimum quantity: q Validity period: first match only Fill-and-kill (FaK) Executed when inserted, the remaining quantity (if any) is cancelled. Validity period: first match only All-or-none (AoN) Executed only at the whole quantity q. Minimum quantity: q Iceberg Executed considering the quantity q, but just showing the public quantity qp. Public quantity: qp, qp< q Pegged Executed at the best price in its side plus some price offset po. Cancelled if there are no orders to peg to. Price condition: pegged price Price offset: po Table 4.2: Main order types in TRADExpress (source: [3, 34]) In order to simplify and avoid ambiguity in the following chapters, the following notation will be applied to the studied order types: a market order with quantity qwill be simply represented as q. A limit order with quantity qand limit price pwill be represented as q@p. A minimum quantity limit order with quantity q, minimum quantity qmand limit price pwill be represented as q(≥qm) @ p. More special attribute values will be explicitly mentioned next to the order. Note that an all-or-none order with quantity qand limit price pcan be thus represented as q(≥q) @ p. It is worth noting that the mentioned types of orders are just some of the most used attribute combinations. The number of possible combinations in TRADExpress is practically infinite, and makes the order book a complex system from the design and verification points of view. 4.3.4 Order priority A common requirement for a trading system is to encourage “generous” prices, high quantities and transparency in the trade orders. In order to guarantee these 4.4. ORDER MATCHING 31 principles, TRADExpress prioritizes the orders in an order book side by applying the following criteria, sorted by precedence [3]: 1. Price (limit price for limit orders): more generous orders get higher priority 2. Visibility: transparent orders get higher priority 3. Minimum quantity: orders without minimum quantity get higher priority 4. Time: orders inserted before get higher priority Figure 4.3 shows an example of how the order priority algorithm is applied in TRADExpress. In the example, the bid orders b4,b3,b2,b0and b1are inserted consecutively, and the ask side is empty so they are stored in the order book. Even though it is the first inserted order, b4obtains the lowest priority because its price limit is the less generous one. b2obtains higher priority than b3because it is transparent. b0and b1obtain higher priority than b2because they do not have minimum quantity constraints. Last, b0obtains higher priority than b1because it is inserted before. →Bid orders Ask orders b0: 100 @ 10.1 →b1: 100 @ 10.1 b2: 100 (≥100) @ 10.1 b3: 100 @ 10.1 (dark) b4: 100 @ 10 Figure 4.3: Order book after consecutively inserting b4,b3,b2,b0and b1 4.4 Order matching An order book in TRADExpress offers several mechanisms to organize the way in which orders match each other to form trades. Matching mechanisms are applied to individual order books, and can be changed during the trading day. The continuous limit order mechanism, called auto-matching in TRADExpress, is probably the most predominant mechanism used nowadays in financial markets [14, Ch. 2], and for this reason it often concentrates the test efforts and it is as well the target of this project. From a computational point of view, it is well known that the order matching problem where orders can have minimum quantity constraints is NP-complete [20]. This complexity class includes all matching mechanisms in TRADExpress where minimum quantity orders are accepted, auto-matching being among them. 38 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM 5.2 System overview The structure of the developed random test system is mainly based in an integration of the random testing model shown in Figure 2.1 into the existing random testing framework outlined in Figure 4.6. This scheme comprises the two main components of the test system (the order book actor and the order book oracle), plus the system under test (TRADExpress), as shown in Figure 5.1. These two main components are driven, in their turn, by the simulation core, which decides which actor is to perform the action in each simulation step, according to the sequence given at the end of Section 4.5. The main roles of each component are: •Order book actor: Picks randomly pre-defined actions to perform on a specific order book of TRADExpress and verifies that the trades calculated by TRADExpress are the same as the order book oracle expects. •Order book oracle: keeps the state of a specific order book with the input provided by each actor associated with that order book and calculates which trades correspond to a specific state on request of an actor. OrderBookActor 1 OrderBookActor n . . . TRADExpress Bid Ask . . .. . . OrderBookOracle Bid Ask . . .. . . Figure 5.1: Main components and interactions of the system Although Figure 5.1 shows, for the sake of simplicity, a system where a single order book is tested with the help of an oracle, the developed system supports testing an arbitrary number of order books in the same simulation, by simply partitioning the set of actors and defining a new oracle that generates expected results for each order book under test. This allows to reproduce a situation that is closer to the real use of the system and therefore more interesting for testing purposes. 5.3 Requirements As Section 1.4 states, the main aim of this project is to model the business logic that controls the trade order matching in TRADExpress to be able to verify its output 5.3. REQUIREMENTS 39 through randomly generated trading sequences. This high-level goal is decomposed in this section into several requirements, stated in a solution-independent manner, and prioritized in a must-should-could scale. Subsection 5.3.1 lists the main functional requirements, and Subsection 5.3.2 lists the main quality or non-functional requirements. 5.3.1 Functionality 1. Verification of the TRADExpress output (a) The test system must be able to calculate the expected trade events and verify that they are received in the TRADExpress’ public trade flow (see Subsection 4.3.1) after each random action performed on it. For each trade event, at least the following fields will be calculated and verified: •Traded quantity •Price at which the trade is executed (b) The test system could be able to calculate the expected order events and verify that they are received in the TRADExpress’ public and/or private order book event flow after each random action performed on it. 2. Action types The test system must be able to perform the following actions on a specific TRADExpress order book, by sending the corresponding request message: •Insert a new trade order •Update an existing trade order •Cancel an existing trade order The test system should ensure that every generated insert, update and cancel order request is valid according to the TRADExpress specification. 3. Order attributes The test system must be able to generate random valid values from a uniform distribution for, at least, the following order attributes (see Subsection 4.3.2) of an insert or update order request: •Side •Quantity 40 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM •Minimum quantity (in fill-or-kill and all-or-none orders) •Limit price (if the order has a limit price condition) •Price offset (if the order has a pegged price condition) The test system should allow the user to specify the range in which random prices and quantities are generated. 4. Order types The test system must be able to insert and update at least 80 % of the order types listed in 4.2. 5.3.2 Quality 1. Accuracy (a) The test system must be designed without reference to the code or internal structure of TRADExpress. (b) The test system should use a declarative programming paradigm for the computation of the expected trades. (c) The test system should use a different programming platform than the one used by TRADExpress for the computation of the expected trades. 2. Usability (a) The test system must display information enough about each simulation step so that a simulation sequence can be unambiguously reconstructed by the user. (b) The test system must adhere to the style of the automated tests that already exist at Cinnober. (c) The test system must provide a mechanism to repeat deterministically a specific simulation sequence. (d) The test system should follow the notation introduced in Chapter 4 when displaying information to the user. 3. Maintainability (a) The test system must be developed in less than 5000 lines of source code (excluding comments and blank lines). 5.4. DESIGN SPECIFICATION 41 (b) The test system’s source code should include a comment for each subroutine that defines its input, purpose and result of calling it. (c) The test system should include a suite of automated test cases covering its own calculation of expected trades for the order attributes and types specified in 5.3.1. 5.4 Design specification Two main approaches have been used in the design process: the test system has been designed in an object-oriented fashion both at its highest abstraction level and at a component level for those components that interact with the existing random testing framework. The part of the system that deals with the order matching has been approached in a declarative way, by using constraint programming (see Chapter 3), and its design specification, detailed in Section 5.5, consists therefore of a constraint problem. The object-oriented design methodology has been chosen due to two main reasons: •The requirement of adhering to the automated test development style used in Cinnober (see Subsection 5.3.2), and the ease of interfacing the existing random testing framework. •The well-known benefits that object-oriented offers, particularly modularity and simplicity to map the concepts introduced in Chapter 2 such as test oracle. In its turn, constraint programming has been chosen for the design and implementation of the trade calculation logic because, as mentioned in the introduction, it allows to model this complex problem in a formal mathematical notation that helps to close the gap between requirements and implementation, and removes a big part of the implementation effort, which is shifted to the constraint programming system. The constraint programming models are encapsulated in object-oriented classes, and are specified in Section 5.5. The rest of the section is organized as follows: Subsection 5.4.1 shows the design of the test system by describing the main classes and their interactions and responsibilities. Then, the design is specified for the three main aspects of random testing identified in Chapter 2: the input (Subsection 5.4.2), the test oracle (Subsection 5.4.3) and the output (Subsection 5.4.4). 42 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM 5.4.1 Overview of the test system Section 5.2 identifies the actor and the order book oracle as the main components of the test system. The behavior of both of them is driven by the simulation core, which is in charge, as mentioned in the overview, of selecting the actor to perform an action in each simulation step. The order book actor gets the expected trade events from the oracle, and compares them to what it actually gets from TRADExpress. Figure 5.2 shows a sequence diagram specified in Unified Modeling Language (UML) with the sequence that each simulation step follows. :Simulation :OrderBookActor :OrderBookOracle TE act() order action request order action response getExpectedTradeEvents() expected trade events trade event 1 . . . trade event m assert {trade event 1 . . . m}=expected trade events LoopLoop [until end of simulation] Figure 5.2: UML sequence diagram of an action performed on TRADExpress (TE) The order book oracle relies on an inner component, the order book model, to hold a representation of the order book under test and to calculate the expected trade events in a given state. In order to perform this task, the order book model uses finally the order matcher and re-matcher spaces, which, together with their base class, contain the constraint programming model that defines the order matching calculations. Figure 5.3 shows a simplified UML class diagram with the main classes of the test system and their relationships. 5.4. DESIGN SPECIFICATION 43 Simulation startSimulation() OrderBookActor act() OrderBookOracle getExpectedTradeEvents() : TradeEvent [] OrderBookModel registerOrderEvent(orderEvent : OrderEvent) match() : TradeEvent [] rematch(isBidTheIncomingSide : boolean) : TradeEvent [] OrderMatcherSpace OrderRematcherSpace OrderMatcherBaseSpace getBestSolution() : Trade [] 1..* 1 includes 1..* 1includes 1..* 0..1 consults maintains 1 uses uses Figure 5.3: Simplified UML class diagram of the test system 5.4.2 The input As it can be inferred from the functional requirements (see Subsection 5.3.1), the input domain for the test system is focused in those actions that modify the state of an order book, either by inserting, updating, or cancelling orders in it. The subdomains for this case can be seen as the different combinations between purposed actions (functional requirement 2) and considered order types (functional requirement 4). As explained in 4.3.3, there are many of these combinations, so an strategy must be adopted in order to select a representative subset of them. Figure 5.4 shows a taxonomy tree of trade orders with the most usual combinations of attributes (see functional requirement 3). The leaves of the tree contain the trade order types that have been chosen as representatives of each class. Note that, for the sake of clarity and simplicity, iceberg orders have been discarded in this first version of the test system. 44 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM All orders Undefined price Market Defined price Limit price Minimum quantity Longer All-or-none One match Fill-or-kill No minimum quantity Longer Limit One match Fill-and-kill Pegged price Pegged Figure 5.4: Trade orders taxonomy for the input domain modeling The class in charge of performing the input actions is, as mentioned above, the order book actor. The probability of an actor and action being chosen, as well as the number of actions (which defines the size of the input sequence) and the actors that participate can be specified by the user before running the random test. This allows the user to tune the input distribution depending on the goals of the random test (see Subsection 5.4.2). An order book actor is able to perform the following actions: •Insert a market order: insert a market order with random side and quantity. •Insert a limit order: insert a limit order with random side, quantity and limit price. •Insert a fill-or-kill order: insert a fill-or-kill order with random side and quantity, minimum quantity set to the quantity and random limit price. •Insert a fill-and-kill order: insert a fill-and-kill order with random side, quantity and limit price. •Insert an all-or-none order: insert an all-or-none order with random side and quantity, minimum quantity set to the quantity and random limit price. •Insert a pegged order: select a random side. Insert, if there are orders to peg to in the side, a pegged order pegged to the best side price, with random quantity and random price offset within a fixed range. 5.4. DESIGN SPECIFICATION 45 •Update an order: select randomly an own order from the order book. If there is any, update it with a new random quantity, and new random values for each relevant attribute depending on the order type. •Cancel an order: select randomly an own order from the order book. If there is any, cancel it. All quantities and prices can be limited to a certain range, and the decimal precision of prices can be also specified. 5.4.3 The order book oracle As Chapter 2 explains, there are different types of oracles that vary in completeness, complexity and other characteristics. The developed order book oracle can be classified as a true oracle, as it aims to reproduce the exact expected trade flow output for the specific input sub-domain explained in the previous subsection. The main challenge in the design of the order book oracle is to implement the functionality stated in the functional requirement 1 without sacrificing simplicity and independence (see quality requirements 1 and 3). In order to reduce the complexity, an inner class called order book model has been defined. This class represents the state of the order book, and contains methods to calculate expected trades out of that state (see Section 5.5), and a single method to change its state. It is the responsibility of the order book oracle to keep the order book model updated with the corresponding order events that are received or inferred from the trade events. The most complex operation that the order book oracle performs is the calculation of the expected trade events that are derived from a user order action, such as the insertion of a new order. Figure 5.5 shows an UML sequence diagram with the interactions that take place between TRADExpress, the oracle and the order book model in these calculations. The sequence can be summarized in the following steps: 1. The oracle receives all the order events from TRADExpress and initializes a queue of order events with the one corresponding to the user action. 2. The oracle extracts the oldest order event from the queue, and updates the order book model with it. 3. The oracle gets the expected trades from performing a match in the order model, and updates it with the order events that are derived from those trades and the order events that are expected after a match. 4. The oracle gets the expected trades from performing a re-match in the order model, and updates it with the order events that are derived from those trades and the order events that are expected after a re-match. 46 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM :OrderBookOracle :OrderBookModel TE user order event system order event 1 . . . system order event n add user order event to the event queue Q registerOrderEvent(order event popped from Q) match() expected trade events from match registerOrderEvent(system order event i) LoopLoop [for each system order event i after the match] rematch(side of popped order event) expected trade events from re-match registerOrderEvent(system order event j ) LoopLoop [for each system order event j after the re-match] add unvisited price recalculation order events to Q LoopLoop [while Qis not empty] Figure 5.5: UML sequence diagram of the calculation of the expected trade events 5.4. DESIGN SPECIFICATION 47 5. The oracle adds all possible price recalculation events that are derived from the state of the order book model and have not been added before to the queue, and if the queue is not empty goes to step 2 again. 6. The oracle returns the set of all calculated expected trades. The algorithm 1 shows the process described above in a more formal way. The key data structures are the set of trade events to return F, the queue of order events that wait to be processed Qand the set Vof order events that are waiting in Q or have already been processed. After the order book model has calculated which trade events should be expected from a match or a re-match, derived order events must be calculated in order to update the state of the order book model: Input: A set of order events Ecorresponding to the latest user action. Output: A set of trade events T(expected result to the latest user action). T← ∅ eu←user order event ∈E Q← {eu}// Q is a queue of order events to process V← {eu}// V is a set of visited order events while Q6=∅do eo←oldest event ∈Q Q=Q− {eo} register {eo}in the order book model OB T←T∪ {expected trades from a match in OB} register {e∈E:e derived from the match expected trades} ∪ {e∈E:e is a one match order cancel event} ∪ {e∈E:e is a pegged order cancel event}in OB T←T∪ {expected trades from a re-match in OB} register {e∈E:e derived from the re-match expected trades} ∪ {e∈E:e is a pegged order cancel event}in OB EP← {e∈E:e is a pegged order recalculation event} Q←Q∪(EP−V) V←V∪EP end return T Algorithm 1: Calculation of the expected trade events by the test oracle •Order events derived from expected trades: order events that represent the cancellation of completely filled orders and the update of the quantity of partially filled orders. 54 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM atq(x0)=0 atq(xi) i > 0 =atq(xi−1) + qx−1,atq(xi−1) + qx−1≤qc atq(xi−1),otherwise Trade price The execution price tp at which two orders trade is set by the resting side, and it must fall into the visible spread, if this can be defined: c∈B=⇒tpb,a =maxx∈C0lpx,|C0|>0∧maxx∈C0lpx> lpa lpa,otherwise ∀hb, ai ∈ B×A:tqb,a >0 c∈A=⇒tpb,a =minx∈C0lpx,|C0|>0∧minx∈C0lpx< lpb lpb,otherwise ∀hb, ai ∈ B×A:tqb,a >0 where C0is the set of resting visible orders in the incoming side: C0={x∈C:mqx= 0}−{c} 5.5.3 The order re-matcher The order re-matcher is applied when there are potential trades that the order matcher cannot solve. New variables, including auxiliary ones, are defined, and the cost function becomes more complex, as there is a hierarchy of criteria defined in order to chose between different order combinations. As the order re-matcher is always applied after the order matcher, the incoming order is not considered (it could have been completely filled by the order matcher). However, the incoming side is still taken into account for the calculation of the execution price. Input data •The order book inherited from the common model. •The incoming side C∈ {B, A}. 5.5. COMPUTATION OF THE EXPECTED TRADES 55 Variables and domain •The traded quantity variables inherited from the common model. •The non-negative integer variable eqp, which represents the equilibrium price of the order matching and whose domain is the set of different order limit prices {lpx:x∈B∪A}. •The auxiliary integer variable im, which represents the imbalance in a calculated matching. •The auxiliary integer variables itmax,itmin,jtmax and jtmin, which represent the indexes of the minimum intervals that contain orders that trade. •The auxiliary non-negative integer variables tq0, ..., tqn+m−1, where tqkrepresents the total traded quantity between orders whose indexes sum k. Cost function The solution must lexicographically maximize the following tuple of integer variables (note that the expressions with negative sign are to be minimized): maximize htq, −|im|,−(itmax +jtmax),(itmin +jtmin),−eqp, tq0, . . . , tqn+m−1i Constraints Auxiliary variables definition im represents the difference between the total can trade quantity in the bid and ask sides (see Subsection 4.4.4): im =X b∈B: lpb=eqp mqb=0 (qb−tqb)−X a∈A: lpa=eqp mqa=0 (qa−tqa) itmax,itmin,jtmax and jtmin respectively represent the maximum and minimum indexes, for the bid and ask side, of an order that trades: itmax = max({−1}∪{i:bi∈B∧tqbi>0}) itmin = min({n}∪{i:bi∈B∧tqbi>0}) jtmax = max({−1}∪{j:aj∈A∧tqaj>0}) 56 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM jtmin = min({m}∪{j:aj∈A∧tqaj>0}) tqkrepresents the total traded quantity between orders whose indexes sum k: tqk=X bi∈B aj∈A i+j=k tqbi,aj∀k: 0 ≤k < n +m Equilibrium price: an order that has worse limit price than the equilibrium price eqp cannot trade: lpb< eqp =⇒tqb= 0 ∀b∈B lpa> eqp =⇒tqa= 0 ∀a∈A Must trade quantity: the total must trade quantity in both sides must be completely filled (see Subsection 4.4.4): X b∈B: lpb>eqp mqb=0 (qb−tqb) + X a∈A: lpa<eqp mqa=0 (qa−tqa)=0 Trade price The execution price tp at which two orders trade is set by the resting side: tpb,a =lpb, C =A lpa, C =B∀hb, ai ∈ B×A:tqb,a >0 5.6 Implementation The implementation decisions taken in this project have a great impact in the fulfilment of the requirements stated in Section 5.3, specially the quality ones. They can be divided in two parts, analogously to how the specification of the design is organized: those related to the actor, oracle and order book model are detailed in Subsection 5.6.1; those related to how the order book model computes the expected trades are detailed in Subsection 5.6.2. 5.6. IMPLEMENTATION 57 5.6.1 Actor, oracle and order book model Language and platform With the aim of reusing existing work and reduce integration and learnability costs (see quality requirement 2), the actor, oracle and order book model component have been implemented as regular Java classes, and are integrated into the existing simulation framework (see Figure 4.5) at the same level as the existing components. Appendix A includes the Javadoc documentation of the main classes. In order to minimize the complexity and increase the maintainability and readability of the Java code (see requirement 3), high-level constructions as the following ones have been applied whenever possible: •The order predicates defined in the orders taxonomy shown in Figure 5.4 have been directly implemented as classes that implement the Predicate interface of the Apache Commons, a library of reusable Java components. These predicates are used, for example, for filtering orders in collections. •The logic that controls the order priority is encapsulated as a class that implements the Comparator interface of the Java platform. The order book model is sorted according to this comparator. Other comparators are defined in order to avoid code replication and increase the readability of the code. User interface The development of an advanced user interface falls out of the scope of this project. The test system simply uses the console standard output to display the action performed, the state of the order book model and the expected and actual trades in each simulation step, as stated in requirement 2. The random number generation is centralized and initialized by a seed, which can be specified by the user in the test script. As the state of the tested order books in TRADExpress is restarted between each run, the user can repeat a certain test case of interest by simply specifying that the same seed should be used in the test script. Figure 5.6 shows an example test script with only one actor and one oracle where the initialization seed is set to 1000 and the simulation length is set to 100 steps. Furthermore, the test oracle returns the expected trades as matcher objects, which can be directly used by the constructions implemented in the random testing framework for performing comparisons. 58 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM @Test public void simpleScenarioWithOneActor () { setSeed (1000L) ; setExecutionLength(100L) ; OrderBookOracle tOracle = new OrderBookOracle(this , MOPS USER, mOrderBook ) ; addOracle ( tOracle ) ; addActor (new OrderBookActor(this , ”PARTICIPANT” , USER, mOrderBook , 100) . useOrderBookOracle ( tOracle ) . s e t P r i c e L i m i t s (1 0 , 1000) . setQtyLimits ( 10 , 100) . weight Act ion ( OrderBookActor . INSERT LIMIT ORDER , 30) . weightAction ( OrderBookActor .INSERT ALL OR NONE ORDER, 30) . weightA ctio n ( OrderBookActor . INSERT FILL AND KILL ORDER , 20) . weightAction ( OrderBookActor .CANCEL ORDER, 10) ) ; startSimulation () ; } Figure 5.6: Example of a test script with one oracle and one actor 5.6.2 Computation of the expected trades As mentioned in the previous sections, the components in charge of computing the expected trades given a model of a certain state of the order book are the OrderMatcherBaseSpace and the derived OrderMatcherSpace and OrderRematcherSpace. These components are defined as classes and encapsulate constraint problems to be solved by a constraint programming system. As Section 3.4 shows, there are many constraint programming systems that could potentially solve the order matcher and re-matcher problems specified in Section 5.5. Gecode has been chosen out of them for the following reasons, among others: •It is delivered as a C++ library, which makes the integration with the test system easy. •Its openness reduces the risk that the lack of a needed feature will block the development. •I have previous experience with it, which has reduced the development time. The Gecode models, written in standard C++, have been implemented as a shared library, and are connected to the rest of the test system by using the Java Native Interface (JNI). In this way, the quality requirement 1 has been satisfied. As for the Java code, the C++ code makes an intensive use of high-level constructions, for example by applying methods and structures from the C++ Standard Library 5.7. PRACTICAL ASPECTS OF THE DEVELOPMENT PROCESS 59 and using the direct modeling support ([32, Ch. 6]) provided by Gecode whenever possible. 5.7 Practical aspects of the development process The previous sections have introduced the design specification and the main implementation decisions taken in the development of the test system. This section sets one more level of abstraction and deals with the development process itself, the methods applied, the organization of the available time and the main faced issues. 5.7.1 Organization of the development process As the initial time plan states, the development phase of this master’s thesis has been carried out in a period of 8 weeks, between October and November 2009. As stated in the introduction to this chapter (Section 5.1), the test system has been implemented iteratively, adding support for testing, generation, modeling and verification of an order type in each iteration. The following practices have been applied to the development process: •Explicit statement of the requirements and prioritization by means of a backlog. •Test-driven development applied to the trade calculation subsystem, as stated in the quality requirement 3. Appendix B includes a selection of the most illustrative developed test cases. •Version control of the code base, documentation and programming diary. Figure 5.7 shows a timeline with the main events of the development period. The first working version, available since week 42 and enlarged during weeks 43 and 44, uses only the order matcher specified in Subsection 5.5.2. Week 45 was spent in trying to generalize the order matcher model so that it could support all situations with all-or-none (AoN) orders involved. By the end of week 45, splitting up the initial order matcher into two matchers (the matcher and the re-matcher) was identified as the only possible option to reproduce the expected behavior of TRADExpress. Week 46 and 47 were taken to develop the order re-matcher, and the final version supporting all-or-none orders was available on week 48. As a consequence of the design changes, the development of support for all-or-none orders has taken practically the same time as the development of support for all the other order types together. 60 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM Week 41 Week 42 Week 43 Week 44 Week 45 Week 46 Week 47 Week 48 October 2009 November 2009 Supports limit orders Supports FaK orders Supports market orders Supports FoK orders Supports pegged orders Supports AON orders Test framework built Order matcher splitting Lexicographical optimization Figure 5.7: Timeline of the development process 5.7.2 Issues Trade priority in the order re-matcher Figure 5.7 above shows the insight of using lexicographical optimization for the order re-matcher as a main event in the development process. This is translated into the following cost function in the final re-matcher problem (from Subsection 5.5.3): maximize htq, −|im|,−(itmax +jtmax),(itmin +jtmin),−eqp, tq0, . . . , tqn+m−1i While the first two elements of the tuple tq and −|im|are easily inferred from the requirements database, the rest of elements are added only on the basis of observations of actual results from TRADExpress, because it has not been possible to infer the information found in the requirements database and example scenarios with enough precision to be able to formalize it. Therefore, the order re-matcher might produce false positive results (that is, expected trades that do not match the actual results) in those order book states that are complex enough to contain several possible order combinations with the same total trade quantity tq and absolute imbalance |im|. Some of such cases have been detected, documented and added to the test suite. As an order re-matcher attempt can only succeed when all-or-none orders are inserted into an order book, and furthermore the order book must reach a quite complex situation for this issue to be reproduced, its impact to the test process can be seen as limited. In order to evaluate the frequency of failure of the test oracle due to this issue, a simple experiment has been performed: random test cases with an input sub-domain designed to maximize the number of complex order re-matcher situations (exclusive insertion of all-or-none orders with a constant limit price) have been run. In these cases, no more than 10% of successful re-matches (that is, those with tq > 0) have been revealed as false positives. 5.7. PRACTICAL ASPECTS OF THE DEVELOPMENT PROCESS 61 Domain of the order attributes In order to avoid precision problems associated with the use of floating point numbers, TRADExpress uses Java long integers for representing prices and quantities, even if the formers are presented to users as real numbers [4]. Standard C++ and Gecode, in their turn, only support standard integers, which typically use half the bytes of Java long integers. This type mismatch limits the input domain: quantities and prices must be limited so that they fit into standard C++ integer variables. On the other hand, attempts to calculate the expected trades in certain order book configurations (with many orders and high quantities) might end up in a search explosion when solving the associated constraint problem. This issue limits the input domain as well, specially when including all-or-none orders, which generally add more combinatorial richness to the constraint problem. Even though these issues prevent the exploration of the whole domain of the order attributes, situations of equivalent complexity from the order matching perspective can be generated with limited price and quantity values, and thus the same coverage can be obtained as if we were able to explore the whole domain of these attributes. The impact of both issues to the potential coverage of the test system is considered to be thus limited again. 62 CHAPTER 5. DEVELOPMENT OF THE TEST SYSTEM Chapter 6 Results and analysis 6.1 Introduction This chapter analyzes, with the help of the collected results, in which degree the chosen solution fulfills the problem stated in Section 1.3. The discussion is organized by showing results and assessing the achievement of each of the goals presented in Subsection 1.4.1: 1. Evaluate the suitability of constraint programming as a modeling technique for solving the order matching problem. 2. Evaluate how the introduction of a true test oracle contributes to the improvement of the trading system’s testing process. In order to assess the degree of achievement of the first goal, the main characteristics of the order book oracle, such as its completeness and maintainability will be examined by considering, whenever possible, measures like the ones anticipated in Subsection 1.4.2. The success of the second goal will be analyzed, in its turn, by looking at the defects found in TRADExpress during the development and execution of the implemented test system. The chapter is organized in two main parts, each of them respectively related to the goals listed above: the first part (Section 6.2) analyzes the main characteristics of the developed test oracle, and how the application of constraint programming affects them. The second part (sections 6.3, 6.4 and 6.5) analyzes the impact of the order book oracle in the random trading simulations, by referring to the collected results. 63 70 CHAPTER 6. RESULTS AND ANALYSIS Bid orders Ask orders b1: 16 @ ? Incoming order without best priority is allowed to match As the common order matcher constraint problem defines, no order is allowed to match against orders in the other side if there are unfilled non-minimum quantity condition orders with better priority in its side. However, if a visible MBBO is defined (this is, if there are non-minimum quantity orders in both sides of the order book) an incoming order with the same limit price but worse priority than other orders existing in its side is wrongly allowed by TRADExpress to match, by-passing them. The following steps are a simplification of the sequence generated by the test system that causes the failure: 1. The AoN order a1is inserted in an order book containing b0,a0and a2.a1has the same limit price than a0, but it gets worse priority for being a minimum quantity order: Bid orders →Ask orders b0: 18 (≥18) @ 32 a0: 4 @ 28 →a1: 18 (≥18) @ 28 a2: 16 @ 38 2. The incoming order a1is wrongly allowed to match in the first order match attempt, even though a0has higher priority and, because it is not a minimum quantity order, it should never be bypassed by an order with lower priority: b0↔a1: 18 @ 32 6.4.2 Documentation defects The development of the order book model has required a formalization of the TRADExpress order matching requirements, which were stated only in natural language at the beginning of this project. As a side benefit of this process, some documentation mistakes and ambiguities have been detected and fixed. Two main types of defects have been identified in a total of six corrected requirements: •Ambiguous statements due to the use of a natural language (English). •Erroneous calculations and system expectations in illustrative examples. 6.5. IMPACT OF THE ORDER BOOK ORACLE 71 6.5 Impact of the order book oracle As Chapter 1 states, the main contribution of this work with respect to the previous work performed at Cinnober is the introduction of a true oracle, able to calculate the expected output of a TRADExpress order book for a subset, detailed in Subsection 5.4.2, of its input domain. In [19], a total of five defects are found in TRADExpress by applying random testing. Although an heuristic test oracle is developed, it actually does not take part in the detection of any of the found failures. In [21], no test oracle is used, and no failures are discovered. The author argues that “the system under test has been tested frequently and very rigidly for a long time, so no major errors were expected to be found” [21, p. 66]. Yet two new defects has been discovered in this project, even though TRADExpress is older and thus presumably more mature, due to the introduction of a true test oracle. This suggests the idea that the random testing capacity of finding new failures in TRADExpress without using a more complete test oracle was exhausted. It is important to notice that a less complete test oracle than the true oracle could have given some results as well: a heuristic oracle verifying that an order book does not only contain pegged orders after each input action could have detected the remaining pegged order failure (see Subsection 6.4.1). The incoming order failure is, however, harder to discover: detecting if an incoming order should match or not is equivalent in complexity to solving the match problem, which falls into the scope of a true oracle. Finally, even if the use of a less complete test oracle could have helped to find failures, it is arguable whether many side benefits of the modeling and formalization task performed in this project, such as the documentation corrections described in Subsection 6.4.2, would have been obtained. 72 CHAPTER 6. RESULTS AND ANALYSIS Chapter 7 Conclusion and further work 7.1 Conclusion This thesis aimed to provide a solution to the test oracle problem raised in the previous work on random testing applied to the trading system TRADExpress. The proposed solution has been to develop a model of the core component of TRADExpress, the order book, by applying constraint programming, and to integrate the model as a true oracle into the existing random test framework. This work has involved answering, through empirical research, two main questions: 1. In which degree does constraint programming represent a satisfactory solution for modeling complex existing systems such as TRADExpress? 2. How does the testing process improve by the addition of a true test oracle to the random testing framework? The following two subsections summarize the work related to each question and draw the respective conclusions. 7.1.1 Constraint programming and the order book model The main procedure executed in the order book model applies two different continuous double auctions (called match and re-match). The specifications of these auctions, initially given as functional requirements stated in a natural language, have been formalized into constraint satisfaction problems to be solved by a constraint programming system. This has been the first attempt, as far as the author is aware, to model a non-theoretical continuous double auction problem with this technique. 73 74 CHAPTER 7. CONCLUSION AND FURTHER WORK Because the model has been integrated as a true test oracle, its main design goals are those of the oracle: completeness, accuracy, and maintainability. Constraint programming has proven to support well these goals: because of the use of a different programming paradigm to that of TRADExpress, the test oracle is highly independent. Furthermore, constraint programming, as a declarative programming paradigm, has contributed to its accuracy by narrowing the gap between specifications and implementation. Last, the reuse of the search capabilities of the constraint programming system and the high level of abstraction of the oracle implementation have reduced its number of lines of code to a fifth of those used in TRADExpress to deliver the same functionality, contributing to a lower complexity and a higher maintainability. From this discussion, the first question can be answered: constraint programming has proven to be suitable for modeling a complex existing system comprising combinatorial problems, and has shown to contribute well to the common design goals followed in the development of test oracles. 7.1.2 The order book model as a true test oracle The second step in the proposed solution has been to integrate the order book model as a test oracle into the existing random testing framework. The test oracle updates the state of the order book model and triggers the computation of the double auctions through different actions, such as insertions and cancellations of trade orders. An actor that exercises approximately a third of the functionality of the main matching mechanism, including the most typical trade order types, has been added to the framework. Finally, a set of random test cases with the new configuration has been designed and run. In 500 executed test cases, with a total of 45144 input actions, the true test oracle has detected two failures that had been present in TRADExpress for several years. These failures had not been discovered by previous random testing approaches with less complete test oracles. While one of these failures might have actually been detected with a less complete test oracle, detecting the other one would have been hard without a true oracle. Furthermore, the development of an independent, welldefined model of the system as a solution to the oracle problem has implied a formalization task that has brought side benefits, such as the disambiguation and correction of functional requirements. Following this discussion, an answer can be given to the second question: a true test oracle has shown to significantly improve the capacity of finding failures through random testing. Although the development of a true test oracle based on an independent model of the system can be costly, the application of suitable declarative programming techniques can lower a great part of the implementation effort, besides bringing some side benefits derived from their reduction of the gap 7.2. FURTHER WORK 75 between specification and implementation. 7.2 Further work This thesis can be seen as a continuation of the work done in [19] and [21] on random testing in the context of the trading system TRADExpress. The obtained results encourage further research in the directions followed in this project. 7.2.1 Further development of the system model The developed test oracle covers approximately a third of the functionality of the main matching mechanism offered by TRADExpress. An obvious continuation of this work is to enlarge the model with more order types and order book configurations, with the goal of increasing the test coverage and finding new failures. Other matching mechanisms offered by TRADExpress, like the so-called auction, could be as well modeled and tested in a similar way as it is done here. 7.2.2 Continuous double auction as a dynamic CSP In a continuous double auction as the one performed in the auto-matching mechanism, every trade order action triggers a matching computation that typically alters the order book in a limited way. Instead of building a new constraint satisfaction problem (CSP) and solving it from scratch after each user action (as it has been done in this project), the problem could be more naturally modeled as a dynamic CSP [26]. In this way, the match computation could be made more effective, as the results of the previous computations would be reused. 7.2.3 Automatic test case reduction To manually isolate a failure that has been found in a long random test case is a very tedious task. This process can fortunately be automated (see, for example, [36, Ch. 13]). The random testing framework could be adapted by following the steps suggested in Subsection 5.4.4, and the benefits of automatic test case reduction could be measured by, for example, inserting artificial failures in the system under test and calculating the test case reduction rate in several situations. 7.2.4 Operational profiles and reliability assessment Reliability assessment is often included in the list of goals of software testing. As Section 2.4 points out, reliability estimation requires the use of a realistic operational profile in the test input distribution. The development of an operational 76 CHAPTER 7. CONCLUSION AND FURTHER WORK profile, following for example the methods detailed in [27], based on real usage data of TRADExpress could be an interesting step towards the creation of realistic reliability estimation models such as the ones described in Subsection 2.4.2. References [1] Hakim Belhaouari and Fr´ed´eric Peschanski. A constraint logic programming approach to automated testing. In ICLP ’08: Proceedings of the 24th International Conference on Logic Programming, pages 754–758, Berlin, Heidelberg, 2008. Springer-Verlag. Cited on page 5. [2] Eyal Bin, Roy Emek, Gil Shurek, and Avi Ziv. Using a constraint satisfaction formulation and solution techniques for random test program generation. IBM Systems Journal, 41(3):386–402, 2002. Cited on page 5. [3] Cinnober Financial Technology AB. TRADExpress Trading Engine - Functional Requirements Database, 2009. Cited on pages 28, 30, 31, 32, and 34. [4] Cinnober Financial Technology AB. TRADExpress Trading Engine - System Architecture Course, 2009. Cited on pages 27 and 61. [5] Cinnober Financial Technology AB. TRADExpress Trading System - System Overview, 2009. Cited on pages 1, 2, 25, 26, and 66. [6] D. Epstein. On the NP-completeness of cryptarithms. SIGACT News, 18(3):38– 40, 1987. Cited on page 17. [7] Ming Fan, Jan Stallaert, and Andrew B. Whinston. The internet and the future of financial markets. Commun. ACM, 43(11):82–88, 2000. Cited on page 1. [8] Eugene C. Freuder. In pursuit of the holy grail. Constraints, 2(1):57–61, 1997. Cited on pages 4 and 15. [9] Marie-Claude Gaudel. Testing can be formal, too. In TAPSOFT ’95: Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, pages 82–96, London, UK, 1995. SpringerVerlag. Cited on page 3. [10] Arnaud Gotlieb, Bernard Botella, and Michel Rueher. Automatic test data generation using constraint solving techniques. SIGSOFT Softw. Eng. Notes, 23(2):53–62, 1998. Cited on page 5. 77 78 REFERENCES [11] Dorothy Graham, Erik van Veenendaal, Isabel Evans, and Rex Black. Foundations of Software Testing: ISTQB Certification. Int. Thomson Business Press, 2006. Cited on pages 3, 7, 9, 12, and 13. [12] Johan Gundemark. Random tests in a market place system. Master’s thesis, Uppsala University, Uppsala, Sweden, 2005. Cited on pages 2, 5, and 9. [13] Dick Hamlet. When only random testing will do. In RT ’06: Proceedings of the 1st international workshop on Random testing, pages 1–9, New York, USA, 2006. ACM. Cited on pages 8 and 9. [14] Joel Hasbrouck. Empirical Market Microstructure: The Institutions, Economics, and Econometrics of Securities Trading. Oxford University Press, New York, USA, 2007. Cited on pages 6 and 31. [15] Douglas Hoffman. A taxonomy for test oracles. Proceedings of 11th International Quality Week, 1998. Cited on pages 10 and 11. [16] Douglas Hoffman. Heuristic test oracles. Software Testing and Quality Engineering, pages 29–32, March/April 1999. Cited on page 9. [17] Douglas Hoffman. Mutating automated tests. StarEast, 2000. Cited on page 8. [18] Douglas Hoffman. Using oracles in test automation. Proceedings of Pacific Northwest Software Quality Conference, pages 90–117, 2001. Cited on pages 8, 10, 65, and 67. [19] Noah H¨ojeberg. Random tests in a trading system: random tests in a trading system using simulations and a test oracle. Master’s thesis, School of Computer Science and Communication, KTH Royal Institute of Technology, Stockholm, Sweden, 2008. Cited on pages 2, 3, 10, 13, 71, and 75. [20] Jayant R. Kalagnanam, Andrew J. Davenport, and Ho S. Lee. Computational aspects of clearing continuous call double auctions with assignment constraints and indivisible demand. Electronic Commerce Research, 1(3):221–238, 2001. Cited on pages 6 and 31. [21] David Karlgren. Random testing of a market place system. Master’s thesis, Division of Mathematical Statistics, KTH Royal Institute of Technology, Stockholm, Sweden, 2009. Cited on pages 2, 3, 71, and 75. [22] Mikael Zayenz Lagerkvist. Techniques for efficient constraint propagation, 2008. Cited on pages 15 and 20. REFERENCES 79 [23] H. G. Lee and R. M Lee. Electronic call market for commodity transactions: Design of computer-mediated order matching system. Journal of Organizational Computing and Electronic Commerce, 8(4):307–334, January 1999. Cited on page 6. [24] Andreas Lundgren. Abstraction levels of automated test scripts. Master’s thesis, Faculty of Engineering, Lund University, Lund, Sweden, 2008. Cited on page 2. [25] C. Meudec. ATGen: automatic test data generation using constraint logic programming and symbolic execution. Software Testing Verification and Reliability, 11(2):81–96, 2001. Cited on page 5. [26] Sanjay Mittal and Brian Falkenhainer. Dynamic constraint satisfaction problems. In Proceedings of the Eighth National Conference on Artificial Intelligence, pages 25–32, 1990. Cited on page 75. [27] J.D. Musa. Operational profiles in software-reliability engineering. Software, IEEE, 10(2):14–32, Mar 1993. Cited on pages 9 and 76. [28] M. Petit and A. Gotlieb. An ongoing work on statistical structural testing via probabilistic concurrent constraint programming. In First International Workshop on Model, Design and Validation. Proceedings, pages 19–27, Nov. 2004. Cited on page 5. [29] L. Prechelt. An empirical comparison of seven programming languages. Computer, 33(10):23–29, Oct 2000. Cited on page 65. [30] Francesca Rossi, Peter van Beek, and Toby Walsh. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Elsevier Science Inc., New York, USA, 2006. Cited on pages 4, 15, 16, 19, 21, 22, and 23. [31] Young U. Ryu. Hierarchical constraint satisfaction of multilateral trade matching in commodity auction markets. Annals of Operations Research, 71(0):317– 334, January 1997. Cited on page 6. [32] Christian Schulte, Guido Tack, and Mikael Z. Lagerkvist. Modeling with Gecode, 2009. Cited on page 59. [33] Guido Tack. Constraint Propagation – Models, Techniques, Implementation. Doctoral Dissertation, Saarland University, Jan 2009. Cited on page 15. [34] Georg von Zweigbergk. An introduction to financial markets. Technical report, Cinnober Financial Technology AB, 2009. Cited on pages 1, 25, 26, 28, 29, 30, and 32. 86 APPENDIX A. JAVA CODE DOCUMENTATION public OrderBookActor useOrderBookOracle(OrderBookOracle pOrderBookOracle) Specifies that the actor will use pOrderBookOracle for verifying the public trade flow. public OrderBookActor setQtyLimits(int pMinQty, int pMaxQty) Sets the lower (pMinQty) and higher (pMaxQty) limits for quantity generation. public OrderBookActor setPriceLimits(int pMinPrice, int pMaxPrice) Sets the lower (pMinPrice) and higher (pMaxPrice) limits for price generation. public OrderBookActor setPriceDecimalLevel(int pPriceDecimalLevel) Specifies the number of decimal digits that the actor will use in its order prices. Note that a high decimal level can lead to round-off errors and thus incorrect expected trade prices. public int getPriceDecimalLevel() Returns the number of decimal digits that the actor will use in its order prices. public void insertLimitOrder() Inserts a limit order. public void insertMarketOrder() Inserts a market order. public void insertFillAndKillOrder() Inserts a fill-and-kill order. public void insertFillOrKillOrder() Inserts a fill-or-kill order. public void insertPeggedOrder() Inserts a pegged order. A.2. ORDERBOOKORACLE 87 public void insertAllOrNoneOrder() Inserts an all-or-none order. public void updateOrder() Updates an order. public void cancelOrder() Cancels an order. public void restoreState() Cancels all its orders in the order book. A.2 OrderBookOracle A.2.1 Constructors public OrderBookOracle(Simulation pSimulation, String pUserAlias, Instrument pInstrument) Initializes the order book oracle. A.2.2 Methods public void prediction() Prepares the EMAPI subscriptions for all the participating actors. public Instrument getInstrument() Returns the tradable instrument the oracle looks at. public void addEmapiActor(OrderBookActor pOrderBookActor) Adds pOrderBookActor to the list of actors that participate in the trading for the order book. public void cleanOrderEventQueues() Cleans the order event message queues of all actors. 88 APPENDIX A. JAVA CODE DOCUMENTATION public void printOrderBook() Prints out the oracle’s internal order book state. public EmapiTradeEventMatcher[] getExpectedTradeEvents() Returns an array of matchers for the trade events that are expected to happen as a consequence of the last order action performed in the order book. public List getAllPrivateOrderEvents() Returns all private order events registered in the internal order book. public long getBestLimitPriceInSide(boolean pIsBid) Returns the best limit price in the given side of the internal order book. If there are no orders in the side, it returns 0. public void restoreState() Restores the state of the order book. A.3 OrderBookModel A.3.1 Constructors public OrderBookModel(Instrument pInstrument, double pTick) Initializes the order book model. A.3.2 Methods public void registerOrderEvent(EmapiOrderEventPrivateIf pOrderEvent) Updates the order book model with the order event pOrderEvent. public long getBestLimitPriceInSide(boolean pIsBid) Returns the best limit price in the given side of the order book. If there are no orders in the side, it returns 0. public List getOrderEventList() Returns a list with all private order events in the order book. A.3. ORDERBOOKMODEL 89 public List match() Returns a list of trade event matchers that are expected to be the result of matching the contained orders. Calls the external library ”ordermatcher”. public List rematch(boolean pIsBidTheIncomingSide) Returns a list of trade event matchers that are expected to be the result of applying a re-match to the contained orders. Calls the external library ”ordermatcher”. public List toTradeEventMatcherList(List pTrades) Converts a list of TradeModel objects to a list of trade event matcher objects. public List getCancelOrderEventMatchersAfterMatch() Returns a list of cancel order event matchers with the cancel events expected after a match attempt for those orders that are valid only until the next match. public List getOrderEventMatchersFromTrades(List pTrades) Returns a list of order event matchers that are expected to be caused by the trades in pTrades. public List getPriceRecalculationOrderEventMatchers() Returns a list of order matchers due to price recalculation of pegged orders. public List getCancelPeggedOrderEventMatchers(List pBaseOrders) Returns a list of order matchers due to cancel of pegged orders when there is nothing to peg to. It includes only the order events that have not occurred yet in pBaseOrders. public String toString() Returns a string with a representation of the order book state. 90 APPENDIX A. JAVA CODE DOCUMENTATION Appendix B Test cases for the order matching As Section 5.7 explains, the trade calculation subsystem, which includes the classes OrderMatcherBaseSpace,OrderMatcherSpace and OrderRematcherSpace, has been developed by following a test-driven development style: on top of a test framework based on CppUnit (a C++ testing framework), automated test cases defining the expected behavior of the order matcher and re-matcher have been added, and then the functionality has been implemented and verified by just running the test cases. This has been performed iteratively, according to the cycles illustrated in Figure 5.7. The test suite includes a total of 77 test cases: 46 of them test the order matcher, and the remaining 31 test the order re-matcher. For the sake of conciseness, only those test cases that are considered to be more illustrative are included in this appendix. Section B.1 contains the selected test cases for the order matcher, and Section B.2 contains the selected test cases for the order re-matcher. All test cases follow the notation introduced in Chapter 4. Each test case includes a title, an optional description, a figure with the input order book state, and the expected output. B.1 Test cases for the order matcher B.1.1 Test cases with non-minimum quantity orders only 1. Incoming order completely fills resting order •Input: Bid orders →Ask orders b0: 25 @ 100 →a0: 25 @ 100 91 92 APPENDIX B. TEST CASES FOR THE ORDER MATCHING •Expected output: b0↔a0: 25 @ 100 2. Incoming order completely fills several resting orders •Input: →Bid orders Ask orders →b0: 100 @ 100 a0: 25 @ 100 a1: 75 @ 100 •Expected output: b0↔a0: 25 @ 100 b0↔a1: 75 @ 100 3. Incoming order gets highest priority in its side •Description: The incoming order gets higher priority than a1because of its better price, and is allowed thus to completely fill the two resting bid orders. •Input: Bid orders →Ask orders b0: 25 @ 100 →a0: 75 @ 100 b1: 35 @ 100 a1: 150 @ 105 •Expected output: b0↔a0: 25 @ 100 b1↔a0: 35 @ 100 4. Incoming order partially fills the resting order with highest priority •Input: →Bid orders Ask orders →b0: 30 @ 25 a0: 200 @ 23 a1: 30 @ 24 a2: 10 @ 25 •Expected output: b0↔a0: 30 @ 23 B.1. TEST CASES FOR THE ORDER MATCHER 93 B.1.2 Test cases with incoming minimum quantity orders 1. Incoming minimum quantity order does not reach match limit price •Description: Even though b0gets the highest priority in its side, the best ask order (which offers exactly the quantity needed) cannot trade at a price lower than 101, so no match is possible. •Input: →Bid orders Ask orders →b0: 100 (≥100) @ 100 a0: 100 @ 101 b1: 100 @ 99 •Expected output: (no trades expected) 2. Incoming minimum quantity order cannot fill its minimum quantity •Description: The incoming order a0is only allowed to match b0, because of the price constraints. However, b0cannot fill it completely, so no match is possible. •Input: Bid orders →Ask orders b0: 2000 @ 229 →a0: 3000 (≥3000) @ 229 b1: 3000 @ 228 •Expected output: (no trades expected) 3. Incoming minimum quantity order is completely filled •Description: The incoming order a0can match against both b0and b1. These two orders can contribute with the required quantity, so two trades are created in priority order, at the price set by the orders in the resting side. •Input: Bid orders →Ask orders b0: 2000 @ 229 →a0: 3000 (≥3000) @ 228 b1: 3000 @ 228 94 APPENDIX B. TEST CASES FOR THE ORDER MATCHING •Expected output: b0↔a0: 2000 @ 229 b1↔a0: 1000 @ 228 B.1.3 Test cases with resting minimum quantity orders 1. Incoming order is completely filled •Input: →Bid orders Ask orders →b0: 40 @ 6 a0: 20 (≥20) @ 5 a1: 30 @ 6 •Expected output: b0↔a0: 20 @ 5 b0↔a1: 20 @ 6 2. Incoming order is completely filled •Description: The price of the trade between b0and a0is moved to the best possible visible price existing in the order book before b0is inserted. •Input: →Bid orders Ask orders →b0: 40 @ 60 a0: 20 (≥20) @ 50 b1: 10 @ 55 a1: 30 @ 60 •Expected output: b0↔a0: 20 @ 55 b0↔a1: 20 @ 60 3. Incoming order bypasses a0and is completely filled •Description: The minimum quantity constraint of a0cannot be satisfied. Minimum quantity orders can be bypassed, so b0matches against the lower priority limit order a1. •Input: B.1. TEST CASES FOR THE ORDER MATCHER 95 →Bid orders Ask orders →b0: 40 @ 6 a0: 50 (≥50) @ 5 a1: 30 @ 6 •Expected output: b0↔a1: 30 @ 6 4. Incoming order cannot fill alone a resting order •Description: In order to satisfy the minimum quantity constraint of a0,b1needs the quantity of b0. This situation can only be solved by executing a re-match. •Input: →Bid orders Ask orders b0: 100 @ 104 a0: 200 (≥200) @ 103 →b1: 100 (≥100) @ 104 •Expected output: (no trades expected) 5. Incoming order is filled against several orders •Input: Bid orders →Ask orders b0: 10 @ 100 →a0: 18 @ 98 b1: 10 (≥10) @ 100 b2: 5 (≥5) @ 100 b3: 3 @ 99 •Expected output: b0↔a0: 10 @ 100 b2↔a0: 5 @ 100 b3↔a0: 3 @ 99 6. Incoming order is filled against best resting order •Description: The price of the trade between b0and a0is moved to the best possible visible price existing in the order book before a0is inserted.