Low Level Design: An Online Judge

Abstract

Online judges are systems designed for the reliable evaluation of algorithm source code submitted by users, which is next compiled and tested in a homogeneous environment. Online judges are becoming popular in various applications. Thus, we would like to review the state of the art for these systems. We classify them according to their principal objectives into systems supporting organization of competitive programming contests, enhancing education and recruitment processes, facilitating the solving of data mining challenges, online compilers and development platforms integrated as components of other custom systems. Moreover, we introduce a formal definition of an online judge system and summarize the common evaluation methodology supported by such systems. We will create an online judge for low level design, that can test multiple classes in one time and also check the code quality and we will also add visual representation of output for multiple input. We will check security of all classes. Main aim of the project is that student / user can test his/her low level design code quality, and the compiler will report errors/bugs if code has any

Introduction

I. INTRODUCTION

'A Programming Language Is Low Level When Its Programs Require Attention To The Irrelevant'

An online judge is an online system to test programs in programming contests. They are also used to practice for such contests like ICPC. The system can compile and execute your code, and test your code with pre-constructed data. We will create an online judge for low level design, that can test multiple classes in one time and also check the code quality and we will also add visual representation of output for multiple input. We will check security of all classes. Main aim of the project is that student / user can test his/her low level design code quality , and the compiler will report errors/bugs if code has any.

Automatic Online Judge system is built to assist to check the      correctness of program code by automatically receives code submitted by programmer, subsequently, it would compile, run and repeatedly key in all predefined input into the running program and capture the output. The output produced by the program is compared with predefines output which are assumed to be correct to judge the precision of the program code. Automatic Online Assessment System is used for different purposes. In order to assist computer programmers around the world to have the mechanism to practice and enhance their programming skills, many Automatic Online Judge System are built to serve for this purpose. In order to help students around the world to learn and upgrade their programming knowledge, and most important, to participate the annual ACM ICPC Programming contest, University of Valladolid provide UVA Online Judge System. The system allow user to read programming exercise then browse the source code and submit. Upon submission, user‘s code is compiled and run, the system automatically key in predefined input, and then compare output from users with the output predefined by administrators and generate status result. In order to get a correct result, user program outputs must match with predefined outputs from the system.

II. WORKING OF AN ONLINE JUDGE

Online judges are platform where you can submit solution to problem in your desirable language by writing some code on it online IDE’S or you can submit by writing code on your own IDE present on your system. As far as it evaluation of submitted code is concern it is as follows… As soon as you submit your solution it goes to their server and your code is run on their system IDE’s. Your code is check against several test cases file as per their prescribed time limit, if your algorithm fails to run within the time limit constraints it will give you an TLE(Time Limit Exceeded) error. Next if your algorithm successfully run on all test cases file within time limit given on problem ,then it matches the output what your code generate and it standard pre-written code. If your output and and what generate from pre-written code matches then it will give AC. Other than this their are some situation where you may be getting WA it may be due to corner test cases and overflow situation you have to also take this into consideration.

As users are allowed to submit any type of code on the online judge, it is quite obvious that some might submit some malicious code. How malicious? Some code can execute other processes.

Some code can look into your file directory, and get some information. Some code can run administrative command. Some code can consume the server’s bandwidth. And there are many facts, that a code can do. And you obviously don’t want to let the program do that. So how can we enforce this permission rules as well? So how does an online judge handles above scenarios? Any

way, the process to limit permission and hardware for System’s safety is called Code Sand-Boxing. So let's have a look in to some Code Sand-boxing approaches

A lame Way: I have seen some online judge projects where the developer tried to find the malicious functions on a code before executing the code. For example, if your code is on C++, the judge will first check if there is any line of code where “system” word is used. This solution won’t work for various reason, as many programming language doesn’t work in the same way. You can generate a function dynamically and call it in some programming language, so filtering won’t work in those code. Another thing, what if you need to print “system” as output? This solution will say that the code is malicious but it isn’t.

A long Historical Way: In this approach, most the online judge works. And this solution is applicable to Linux based system. Stack Overflow/Runtime Error can be checked by the return value of a program. If it is 0, then you can say the program ran successfully, otherwise crashed. Memory Limit limitation and time limit limitations can be provided using various Unix based libraries. Some programming language supports this kind of limitations flag by default, for example, Java.

Directory permission is easy on Linux, you just create a user and permit that user for some directories as well as some read/write permission. Then execute a program using that user, file directory problem can be solved. Also, that code can’t run some administrative command. Limiting network capabilities is also possible using some libraries, for example, Trickle. In this solution, one need to setup various libraries and write various codes just solve one security hole.

The modern way: All of the above problems are solved if you use Docker or container based VM (Virtual Machine). You can create a container which will have an initial memory, with preset network permission, Time limit for the container. All the hassles will be taken care of by the VM. Developers just can focus on the other things. In this solution, the whole judging system may seem to be slower than the other two methods but actually in large scale it is quite faster, and way safer, cleaner than any other solution.

III. WHY LOW LEVEL DESIGN

Low-level design (LLD) is a component-level design process that follows a step-by-step refinement process. This process can be used for designing data structures, required software architecture, source code and ultimately, performance algorithms. Overall, the data organization may be defined during requirement analysis and then refined during data design work. Post-build, each component is specified in detail. The LLD phase is the stage where the actual software components are designed. During the detailed phase the logical and functional design is done and the design of application structure is developed during the highlevel design phase. The goal of LLD or a low-level design document (LLDD) is to give the internal logical design of the actual program code Low-level design is created based on the high-level design. LLD describes the class diagrams with the methods and relations between classes and program specs. Low-level design is a detailed description of every module of software. It describes every module in detail by incorporating the logic behind every component in the system. It delves deep into every specification of every system, providing a micro-level design

IV. HOW TO INTEGRATE LOW LEVEL DESIGN WITH ONLINE JUDGE

1. We will create an online judge for low level design , that can test multiple classes in one time and also check the code quality and we will also add visual representation of output for multiple input.
2. When user submit the lld code then code judge evaluate the code and create a package on server that will run against a main file.
3. Server also contains stuffs like author’s code , user’s code and both code will run on multiple inputs.
4. Input contains large text data which have edge cases and if user’s code and author’s code results the same , then online judge will display accepted.
5. If a user code has compilation issue, then online judge would display compilation error.
6.  Input contains large text data which have edge cases and if user’s code and author’s code results are different, then online judge will display WA(wrong answer).
7. We will store output after every set of input so we can create, visual representation of low level design.

V. DESIGN OF ONLINE JUDGE MODULE

Online judge is the core function of the experimental platform for programming courses. Firstly, students can check the experiments to be completed by selecting experimental topics, and then program online. Then, enter the online judge phase, that is, the code is submitted to the background server for compilation, and the server executes according to the input data specified by the teacher. Finally, the results are fed back to the students, and the students choose the next operation according to the results. If the results are correct, it means that the experiment is completed; if not, they can modify, re submit, until it is correct. The flow of the whole online experiment is shown in Figure below.

The specific steps of automatic judge on server are as follows:

1. Step 1: Get the solution code according to the task number and create a temporary source code file.
2. Step 2: Call the compiler of the corresponding language to compile the source code file. If it passes the compilation, it will jump to step 3. Otherwise, it will be regarded as a compilation error. Save the compilation error information and jump to step 6.
3. Step 3: Run the compiled program of step 2 to restrict the program from executing illegal operations. Start the timer and load the standard input data prepared by the teacher and wait for the output data. If the operation is abnormal, save the exception information and jump to step 6. If the memory consumption exceeds the limit, jump to step 6. If the time consumption exceeds the timer, jump to step 6. Otherwise, the output data is compared with the standard output. Generally, there are three kinds of comparison results: complete matching when removing the front and back blanks and line feed, mismatching when removing the front and back blanks and line feed, and partial matching.
4. Step 4: If there are other test data, go to step 3.
5. Step 5: Give the time cost and space occupied and calculate the score.
6. Step 6: Save the results, upload the source code file to the corresponding experimental folder and return

VIII. RESULTS

Using this we are able to judge the low level design code and are able to check errors like compilation error,wrong answer,time limit exceed, runtime error. If the code submitted by the user absolutely when then the judge displays accepted and if it is having any issue then it displays the error.

Conclusion

There are various online judges Hackerrank, HackerEarth, Codechef. All of the have their respective algorithms and systems of evaluating submissions. Let’s consider an online judge who is accepting the submission for a given problem. For this submission, the judge has some input and some output files loaded in it already. The judge passes the submission to the processor and this processor has some processing limits. With the increase of number in tech field the demand for developers have increased , which has increased the demand of compilers.People nowadays not only require compiler for running their codes in respective languages of their choice but the demand for checking low level design of a software has also increased significantly. So that has motivated us to work on the low level design online judge.

References

[1] Ebru Özdo?ru Kand?rmaz, Ufuk Tiryaki, Ali Hikmet Dogru. “Reference model for low level design.” In Proceedings of the 7th Turkish national software architecture conference, at Istanbul, Turkey. (PDF) A Reference Model for Low-Level Design (researchgate.net) . [2] Szymon Wasik, Maciej Antczak, Jan Badura, Artur Laskowski, and Tomasz Sternal. 2016. A Survey on Online Judge Systems and Their Applications. ACM Comput. Surv. 1, 1, Article 1 (January 2016), 35 pages. DOI: 10.1145/nnnnnnn.nnnnnnn [3] SAURAV SUMAN. “System Design – Online Coding/ Judge platform” System Design — Online Coding / Judge Platform | by Saurav Suman | Medium [4] A. Kurnia, A. Lim, B. Cheang, Online Judge, Comput. Educ. 36(4)(2001) 299-315. DOI: https://doi.org/10.1016/S0360-1315(01)00018-5 [5] Steven S. Skiena, Miguel A. Revilla, Programming challenges: the programming contest training manual, Acm SIGACT News. 34(3)(2003)68 -74. DOI: https://doi.org/10.1145/945526.945539 [6] C.A. Higgins, G.R. Gray, P. Symeonidis, A. Tsintsifas, Automated assessment and experiences of teaching programming, J. Educ. Resour. Comput. 5(3)(2005)5.DOI: https://doi.org/10.1145/1163405.1163410 [7] Peking University.POJ:PKU Judge Online. http://poj.org/. [8] HangZhou DIANZI University.HDOJ. http://acm.hdu.edu.cn/. [9] M. Joy, N. Griffiths, R. Boyatt, The boss online submission and assessment system, J. Educ. Resour. Comput. 5(3)(2005)2.DOI: https://doi.org/10.1145/1163405.1163407 [10] California State University.PC2:a programming contest control system. http://pc2.ecs.csus.edu/. [11] R.Y. Toledo, Y. C. Mota , An e-Learning Collaborative Filtering Approach to Suggest Problems to Solve in Programming Online Judges, International Journal of Distance Education Technologies. 12(2)(2014)51-65.DOI: https://doi.org/10.4018/ijdet.2014040103 [12] J.Q. Li, Source code assessment system research and development, Master Thesis, Beijing University of Chemical Technology, 2008. [13] T-C. Wang, Y-L. Luo, K-Z. Zuo, The research in practice teaching of data structure based on online judge, Computer Education. (10) (2010) 88-91. DOI: https://doi.org/ 10.3969/j.issn.1672-5913.2010.10.026

Copyright

Copyright © 2023 Kunal Girdhar, Lakshay Arora, Siddharth Sharma. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.