Experimental performance of an algorithm often has a big gap from its theoretical complexity analysis. It is necessary to understand the characteristics of the experimental performances of di erent algorithms for the same problem to select an appropriate algorithm depending on available computing resources and properties of input data. In this paper, we present AOBA, an integrated online platform for testing, evaluating, analyzing and comparing di erent algorithms for various types of string processing problems. New algorithms can be submitted to AOBA and will be evaluated with many test data. All experiments work on the web: everyone can use AOBA without any local environment for experiments. AOBA also includes a powerful in-browser visualizer for analyzing and comparing performances of algorithms.
String processing is one of the most important research elds in computer science. Various kinds of data including natural language sentences, biological sequences, and other types of sequences of symbols are strings in nature. Even numerical sequences can be seen as strings and moreover any kinds of data handled by a computer are represented as strings of bits in the end. So e cient string processing algorithms and their implementations can make a huge impact on the wide range of applications. It is important to understand and evaluate the performances of string processing algorithms fairly and correctly.
It is common for theoretical and experimental evaluations of an algorithm
to diverge. For instance, Cantone and Faro [
In this regard, several performance evaluation tools have been developed so
far. Hume and Sunday [
In this paper, we introduce AOBA (An Online Benchmark tool for Algorithms in stringology), an integrated platform on the web for testing and evaluating string processing algorithms. AOBA is not limited to the exact matching problem. It can handle various types of string processing problems including pattern matching, pattern mining, string compression, and so on. In the abstract, it can handle problems that have a unique solution text for an input text.
This paper is organized as follows. In Section 2, we give a brief description of AOBA. In Section 3, we describe the backend in detail and discuss its security. In Section 4, we provide experimental results on selected algorithms evaluated with AOBA. Finally, in Section 5, we summarize our work. 2
AOBA is an integrated web platform for string processing algorithms. Without any local environments, users can easily test their algorithms and compare their performance with other algorithms submitted to AOBA. AOBA is available at http://aoba.iss.is.tohoku.ac.jp. A demonstration video is also available at https://youtu.be/d1Z5-LBLLJI. Below are the key features of AOBA: { complete support on the web, no need for a local environment; { compatibility with various types of string processing problems; { integrated datasets and evaluation environments; { support for adding new problems and datasets through user requests; { fair and secure evaluation by a sandbox environment; { powerful visualizer for comparing performances of di erent algorithms.
In order to test and evaluate their algorithm implementations on AOBA, users should make a submission. A submission should contain source les and build/run scripts that instruct the system how to compile the source les and run the program. Each submission should target only one problem (for instance, the exact matching problem). Each problem has multiple test cases, each consisting of two text les: the input and the expected output.
Once a submission has been made, AOBA compiles the source les according to the build script. After that, AOBA runs the program on the input text and compares the actual output from the program with the expected output for all test cases. The execution time and the maximum memory usage are measured during the execution. We call these measurement results the performance of the algorithm. Detailed descriptions of the evaluation ow will be given in Section 2.1. All compilations and executions are done in a sandbox environment whose speci cations are de ned for each problem.
We have also implemented an in-browser visualizer to analyze performances of algorithms. The performance of the submission is plotted immediately after execution. Detailed descriptions of the visualizer will be given in Section 2.2. Users can also request to add new problems and test cases to AOBA. Currently, approval from administrators is needed to publish a new problem. 2.1
This section describes the work ow of an algorithm testing and evaluation in AOBA. A submission is processed in two steps, pre-evaluation and evaluation. In both steps, the submitted source code will be compiled with the build script. Then, the input data text is fed into the algorithm through the standard input. The compiled code is executed with the run script, and the actual output is veri ed for correctness by comparing with the expected output.
When the submission is made, it is immediately proceeded to the pre-evaluation step. The pre-evaluation step veri es the correctness of the submission by running it on a small number of test cases. If any error is found in this step, the submission is disallowed to proceed to the next step. Once the pre-evaluation has successfully completed, the submission can proceed to the evaluation step upon the user's request.
The evaluation step measures the performance, i.e., execution time and max memory usage, of the submission by running the program on test cases. Each test case used in the evaluation step has metadata representing characteristics of the test case in addition to the input and the output texts. The number of parameters constituting the metadata, the semantics and the type of each parameter are de ned for each problem. For example, a test case of the exact matching problem has three integer parameters: text length n, pattern length m and alphabet size . At any time during the evaluation step, one can check the evaluation progress and the evaluation results with the visualizer.
Note that we have set some limitations on the number of executions on each step to provide our computational resources equally for every user. 2.2
The evaluation result is given as multi-dimensional data corresponding to the multiple parameters associated with test cases. AOBA is equipped with an inbrowser visualizer that helps understanding the intricate result. By aggregating some axes, it shows the result in a 2D or 3D plot image, depending on the user's preference. Figure 1 shows a screenshot of the visualizer interface, which consists of the setting area and the plot area. The setting area holds settings about axes and their parameters. This visualizer is reactive: the plot is updated immediately whenever any changes to the settings are made.
The visualizer can simultaneously plot evaluation results from di erent
submissions for the same problem. Figure 1 compares the performance of the
Horspool algorithm [
The visualizer is available on both of the submission page and the problem page in the web site. The one on the submission page shows the performance of that speci c submission. On the problem page, it shows the best performances of submissions that have the fastest execution time or the most e cient memory usage, among all submissions for the problem. 3
AOBA needs to safely execute untrusted source codes submitted by users. At the same time, measured performances must be accurate. In this section, we describe the secure execution environment called sandbox and the accurate performance measurement method to realize it. We also discuss security based on possible attacks. Finally, we describe the whole system architecture. 3.1
A sandbox is an evaluation environment for safe program execution. Sandbox environments have widely been studied in the computer security eld. Existing sandboxes are mainly realized by the following methods [15{17], among which AOBA uses the container-based method.
Container-based The Linux kernel provides features for grouping processes together and allocating computational resources for each group. The one called namespace allocates operating-system-level resources, like process ID, interprocess communication, network, le system processes. On the other hand, cgroups restricts the physical resources that can be handled by the process in the group such as CPU and memory. Processes can be abstracted from the environment in which they actually run. This type of abstraction method is called a container. Containers are much lighter and faster than virtual machines, since containers virtualize at the operating system level, unlike the virtual machines that virtualize hardware-level resources. ptrace-based A system call ptrace is used for monitoring and controlling resources consumed by running processes. By using this in conjunction with setrlimit and seccomp system calls, an untrusted source code can be executed on limited resources.
LSM-based Linux Security Modules (LSM) is a framework that enables the many di erent access control models to be implemented as loadable kernel modules. Since it is loaded into the kernel and the processes are controlled from the kernel, the overhead is less than that of ptrace.
In addition to security, it is also important not to interfere with the
performance of the process, so that the original execution time is measured as
accurately as possible. Merry and Bruce [
In fact, Mares and Blackham [
To provide secure and fast IO access AOBA creates a tmpfs volume and mounts it to the Docker container. Since tmpfs is stored in the main memory instead of the hard disk, it ensures fast access to the data. When there is not enough space for the tmpfs volume in the main memory, the data access time will be slow. As a workaround, AOBA allocates memory needed for the container data before the execution, assuming the total size of data does not exceed the total main memory size. 3.2
A measured performance may di er from the ideal value by mainly two factors: an error due to the unstable measurement and a malicious program that attempts
to rewrite the measurement result. In this section, we give a detailed description of measuring execution time and memory usage on AOBA to prevent unstable measurement. We discuss its security in Section 3.3.
Measure execution time While measuring it outside a container is the safest way, a measured result contains time required for the API calls between the internal system and a container. This overhead may cause unstable results. In fact, we con rmed that an error of up to 200ms occurs on our environment. Instead, AOBA measures execution time directly inside a container by the time command. This method improves the accuracy but has a greater security risk. We will explain how to deal with it in Section 3.3. Measure memory usage Generally, memory usage of a single process can be measured by the ps command and so on. However, this method cannot be used because AOBA allows multi-processing. Therefore, memory usage is measured by total memory usage over a whole container for multi-processing. More speci cally, its value equals to max usage in bytes in the memory subsystem of cgroups. The value measured by this method contains extra memory usage due to other processes such as time command. However, this error is constant and negligibly small for su ciently large problems.
These measurement methods realize accurate measurement. Nevertheless, outliers may be measured depending on system conditions, so a measurement for a test case is repeated. Under the current setting, the program is repeatedly run three times. Among the runs, the one with the fastest execution time is reported as the nal result. 3.3
Various kinds of attacks to the system are possible in both of program
compilation and execution. Tochev and Bogdanov [
all possible answers to a source code. This can be prevented by preparing a su ciently complex problem and limiting the submission le size. A more aggressive attack is possible: embedding test cases that are obtained illegally.
Therefore, it is needed to ensure test cases are inaccessible from users.
cessive le, Denial of Service (DoS) attacks during compilation and execution, excessive disk/memory usage, etc. fall under this type. Attacks of this type can be prevented by limiting available resources such as disk/memory usage and execution time.
such as the answer of a test case is one of this type of attacks. As a more critical example, it is possible to break a sandbox environment. The security of containers and permissions should be maintained properly because most of these attacks depend on their vulnerabilities.
To protect AOBA from these types of attacks, we limit memory/disk usage, submission size, compilation/execution time, and access rights.
In addition to the above, various attacks can be considered because AOBA also allows multi-threading and multi-processing. For example, a process that remains running after its parent process has nished, called an orphan process, may cause some attacks that break a sandbox. A fork bomb attack is also possible. It is a DoS attack that creates processes in nitely to slow down the system. Each container has a process id space provided by namespace. A container kills all remaining processes in this space when it terminates. It ensures orphan processes in a container cannot break it. Available resources from a container are limited by cgroups, thus DoS attacks due to multi-processing like a fork bomb do not a ect the entire system.
Moreover, attacks that rewrite the performance fraudulently should be considered because AOBA attaches importance to the reliability of measured performances. Memory usage is measured outside and throughout a container, so its value reliable as long as the security of containers is maintained.
A measurement of an execution time has more security threats compared to that of memory usage because it is done in a directory inside the container. For example, it is a possible attack that the main process of a submitted program creates an orphan process and terminates itself immediately to make its execution time less. After that, an orphan process calculates and outputs an answer. A more aggressive attack kills the process of the time command during the execution and writes fake output to tamper with execution time. To protect from such attacks, the time command for the measurement is executed by the root user, then the user is switched to a general user called the guest user that executes a submitted program. This method ensures that it cannot disturb a process of the time command. Outputs from the time command and a submitted program are redirected to speci c les in a container by the root user. The guest user for the execution has no access rights to these les. Therefore, orphan processes cannot overwrite such outputs. Only a process whose execution time is measured by the time command can write outputs. In this way, the security of an execution time measurement is guaranteed. 3.4
The whole system of AOBA consists of the following ve components. Web provides an interface that allows users to interact with AOBA. Web-Internal dispatches jobs related to a submission to appropriate components, manages and checks the status of other components.
Database stores data used in Web and Web-Internal.
Storage stores large les such as submitted source les and test cases. Executor executes and evaluates submitted les in a sandbox environment. AOBA evaluates submissions as follows. Web component receives submissions via the web, then Web-Internal component creates a job for each submission DatabasSetorage
Executor Pull the job from the job
queue Fetch the submitted files and test cases Build and execute for a
test case Save the execution log
to Storage Evaluate the output and report the result
Repeat for all test cases Report the completion
of the job W eb Receive a submission Save the submitted files
to Storage Add a submission entry
to Database
Repeat these steps twice for pre-evaluation and evaluation.
Create and add a job to
the job queue
Add the evaluation result entry to Database Add the job result entry to Database Build the docker image Create a /data volume
with tmpfs
Create a container Mount the /data volume to the container Start the container Execute the build.sh
Stop a container Copy an input file to
/data/INPUT
Start the container Execute the run.sh with following redirections and measuring execution time.
/data/INPUT → stdin stdout → /data/OUTPUT
Stop a container Fetch /data/OUTPUT Measure memory usage Delete a container and
volumes : an operation in a container and pushes it to the job queue for the pre-evaluation step. A job is an execution unit of the Executor; the collection of information necessary for evaluating the submission such as the ID of a submission and test cases. Then the Executor pulls the job from the job queue and evaluates it. If the submission passes the pre-evaluation, Web-Internal component creates another job for the evaluation step. The Executor evaluates it as well as the pre-evaluation step. Figure 2 shows the detailed evaluation ow.
All of these components except Web-Internal can be distributed to multiple hosts. Moreover, the Executor components are not hosted on the same machine with the other components for measurement stability. 4
In this section, we show experimental results about several string problems as examples to demonstrate testing and analyzing algorithms in AOBA. In all experiments, an executor is hosted in a PC with Xeon E3-1220 V2, Ubuntu 18.04, Docker 18.09.0, 8GB RAM. In the sandbox, available resources are limited to 1 physical core, 1GB RAM.
First, we show evaluation results for the exact matching problem on AOBA
to demonstrate examining the performance distribution of many algorithms. The
exact string matching consists in nding all occurrences of a given pattern string
P in a given string T . A lot of exact matching algorithms are researched and
proposed [
Figure 3 is the heat map plot of the visualizer that shows the distribution of algorithms that has the fastest execution time against parameters m and . Based on the obtained knowledge of the properties of algorithms, the most suitable algorithm can be selected for a target application.
Another problem that AOBA is equipped with is the order preserving pattern
matching problem (OPPM) [
We let AOBA compare the KMP-based algorithm (OP-KMP) [
We introduced an integrated evaluation web platform AOBA designed for
testing and analyzing the performance of algorithms for diverse types of string
processing problems. We are expecting that the platform will help researchers to
study e cient algorithms and implementations. In fact, some of the authors,
Kobayashi et al. [
Still, the datasets and problems that currently AOBA provides may not be su ciently many. We will continue enhancing AOBA, while users' contributions are very much welcome. We are also considering releasing an on-premise version.
A whole execution of an evaluation takes much time as the number of test cases increases. In addition, AOBA reports an algorithm's performance based on many multiple runs to make results more accurate but it also takes time. Currently, AOBA has an insu cient number of executor components. Some problems take several hours to evaluate a single submission. This can be solved by scaling executor components. However, more strategic solutions can also be considered. For instance, the performance may be approximated by using some test cases instead of all of them.