Mooshak's ConceptsIn this page we start by introducing some background that relates to Mooshak and then give information on how Mooshak works and the decisions taken in order to judge contestants' submissions and how they are ranked in a contest.
International Programming Contests
The ACM International Collegiate Programming Contest is a programming world championship for college students organized and conducted yearly by the ACM. It started in 1970 as a local contest somewhere in Texas and has since grown exponentially in the number of participating universities each year. The numbers are impressive: in 2000 there were more then 2700 teams, from 1079 universities, 70 countries, participating in 42 regional contests distributed among 82 locations.
The ACM programming contest provides students with an opportunity to demonstrate and sharpen their problem solving and computing skills. Apart from the fun of competing (and hopefully winning), the contest is also an excelent opportunity to make international contacts in computing science. The Contest is a two-tiered competition among teams of students representing institutions of higher education. The winning teams of the regional contests (held from mid-September to mid-December each year) will go forward to the contest world finals which are held in the following Spring.
The Regionals and World Finals usually comprehend a 5-hours programming contest with 8 or 9 problems to be solved by teams. Teams are composed by upto 3 students and may submit their program solutions in a number of programming languages, usually: Pascal, C, C++ or Java. A submitted solution is declared as accepted if it successfully produces the same outputs, for a set of input tests, as those of the jury. The team that solves more problems in less (accumulated) time, is declared the winner.
There are other similar contests taking place:
What is Mooshak?Mooshak is a client-server application to fully manage and run programming contests. It is web-based and therefore all of its functionalities are accessible through interfaces deployed on a web-browser, irrespective of the operating system were the browser is running. These interfaces use the HTML 4.0 frame set and no processing is made on the browser, except for some data input validations that are implemented with ECMAScript. Java and plugins were avoided on purpose to simplify the use of the interface by any machine on the Internet.
Main FeaturesMooshak provides a number of features, namely:
The automated judge is the corner stone of Mooshak. Its role is to automatically classify a submission according to a set of rules and produce a report with the evaluation for further validation by a judge person.
A submission is composed by data relevant for the evaluation process, that is the program source code, the team-id, the problem-id, and the programming language (this is automatically inferred from the source code file extension). Submissions are automatically judged and the corresponding result is almost instantaneously displayed to the teams, although initially in a pending state.
Judge persons have the responsibility of validating pending classifications, making them final, and occasionally modify initial classifications. A classification may have to be modified as a result of changes in the compilation and execution conditions (e.g. changes in test cases) that required reevaluating submissions. Reevaluation produces another report that has to be compared with previous ones.
The automated judging can be divided in two parts according to the type of analysis:
Static analysis starts by verifying if the submitted problem has already been solved, in which case the submission is rejected and no classification is given. Then it goes on to confirm the verifications made by the interface, i.e. by double checking the submitted data for team ownership, problem-id and size of program source. If it succeeds in this verification, it compiles the submitted program using the compilation command line defined in the administration interface. Mooshak can be more or less tolerant according to the flags chosen for each compiler. An error or compiler warning detected in this stage aborts the automated judging and dynamic analysis is skipped. The following table lists the verifications performed during static analysis and the associated classifications upon failure.
Dynamic analysis involves the execution of the submitted program with each test case assigned to the problem. A test is defined by an input and an output file. The input file is passed by the standard input to the program being executed and its standard output is compared with the output file. The errors detected during dynamic analysis determine the classifications listed in the following table.
Each classification has an associated severity rank and the final classification is that with the highest severity rank found in all test cases. The highest severity is given to the rare situation where the system has an indication that the test failed due to lack of operating system resources (inability to launch more processes, for instance). The lowest severity is the case where no other error was found, using the test cases, and therefore the submission is accepted as a solution to the problem.
The automatic judge marks an execution as "Accepted" only if the the standard output is exactly equal to the test output file. Otherwise the output file and standard output are normalized and compared again. In the normalization both outputs being compared are stripped of all formatting characters. If after this process the outputs become equal then the submission is marked as having a "presentation error"; otherwise it is marked as a "wrong answer". In the current implementation the normalization trims white characters (spaces, newlines and tabulation characters) and replaces sequences of white characters by a single space. This is a general normalization rule since white characters are only used for formatting. In a specific problem other classes of characters could have the same meaning. For instance, in a problem where the only meaningful characters are digits, other characters, such as letters or punctuation, could be treated as formatting characters. This cannot be done in general since many problems have a meaningful output that includes letters. This feature will require having a meaningful class of characters defined for each problem output.
Rules to rank teams:Mooshak uses the rules defined by the ACM-ICPC committee to rank contestants at contests.
One initial security issue is related with the system support for different types of users with different access permissions. This is handled by ensuring user authentication and then associate types of users with different interface views of the system.
The compilation and the execution of programs are the two most insecure points of a contest management system. Provided it fits in a single file, a team can submit virtually any program in one of the contest languages, including a bogus or malicious program capable of jeopardizing the system and ruin the contest. For that reason Mooshak compiles and executes programs in a secure environment, with the privileges of an insecure user and with several limits. Most of these limits are independent of problems, with the exception of execution timeout that is adjusted to each problem. The timeout for each problem is determined before the contest and it is the maximum time taken by the judges solutions, with all test cases, rounded up for the next integer (in seconds). The timeout for compilation is 60 seconds. The other resource limits enforced are listed in the following table with their default values in bytes (except for the number of child-processes).
A single Mooshak node - one Web server accessible through a set of Web clients on users machines - is sufficient for running a small programming contest (i.e. a contest with up to 20 teams) where reliability is not at premium. Running an official contest, with a concern for reliability and larger number of teams, distributed in several sites, and a simultaneous online contest, requires a more complex setup, with a network of interconnected nodes.
A link from a node X towards a node Y, represents the direction in which contest data must be replicated (from server X to server Y). The main reasons for replicating contest data between Mooshak servers are to support:
The Mooshak network configuration for a particular contest may contain several of these links. The following figure represents the network for a contest taking place simultaneously in two sites, A and B, the first using two servers (Server A1 and Server A2) for load balancing and the last using just one server (Server B). Each site has a backup with an updated version of the contest data, capable of replacing any of the main servers in case of failure. Site A maintains also an online version of the contest where anyone on the Internet can compete against the official contestants physically located at either site A or at site B. Some nodes are connected in unidirectional links, such as those connecting servers with the backup nodes or online-contest servers, and other are bidirectional, such as those connecting contest servers among them.
The Mooshak replication uses the rsync remote-update protocol. This protocol updates differences between two sets of files over a network link, using an efficient checksum-search algorithm. The replication procedure is invoked frequently to propagate changes to other servers, typically every 60 seconds, and copies only the data that has been changed since the last replication. The object files produced by the compilation of programs are not replicated, just the evaluation reports. If necessary the programs may be reevaluated in a different machine.
The main issue with replication is the consistency of contest data, namely that no data fails to be replicated or is overwritten by replicated data. To guarantee that no data fails to be replicated we must ensure that there is a replication path connecting all servers interfacing with official contestants.
To address the problem of data being overwritten, we must differentiate between contest definition data (such teams, problems, programming languages) and contest transactions (such as submissions, questions and printouts). Of these two, contest transactions, specially submissions, are particularly important. To guarantee uniqueness all transaction data is keyed by a timestamp, the team ID and the problem ID. Thus, if team ID is unique in the system, and transactions from the same team are consistently sent to the same server, then there is no danger of losing transactions due to overwritten data since each transaction key is also unique.
Contest data is not, in principle, changed after the beginning of the contest. It should be updated in a single node for consistency sake, and that node must have a path to every other node in the network. The only exception to this case is the creation of teams for online-contest servers, as we allow contestants to register during the contest. In case of using load balancing for online-contest servers it is important to assign team creation to a single server. Otherwise, two teams with the same name, and same group, registering at same time in different servers could (although not very likely) share the same record.
For the above setup to work properly, all servers clocks must be synchronized. This can be achieved using the Network Time Protocol (NTP).