LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming

1 Introduction

Automated Test Case Generation (ATCG) [Anand et al., 2013] is a critical component of software engineering, particularly in competitive programming, where the performance and correctness of algorithms are tested against diverse and challenging inputs. As the complexity of software and algorithmic problems increases, manual test case creation becomes infeasible, prompting the rise of automated solutions. Recent advancements in deep learning have significantly improved the generation of test cases, yet several fundamental challenges persist. Ensuring adherence to intricate input specifications and capturing corner cases effectively remain elusive, often necessitating additional manual analysis.

The inadequacy of test suites has been a persistent issue in software testing. For example, the Defects4J dataset, as highlighted by Fraser and Arcuri [2011], has shown that incomplete test cases lead to insufficient program analysis. Similarly, the CodeNet dataset, a benchmark for competitive programming [Puri et al., 2021], suffers from a lack of high-quality test cases, as noted by Zhao et al. [2024]. These limitations not only hinder robust algorithm validation but also exacerbate challenges in program repair [Tian et al., 2022]. Even recent prompt-based methods leveraging Large Language Models (LLMs), such as ChatGPT, and mutation-based frameworks like MuTAP [Dakhel et al., 2024], often produce invalid or incomplete test cases for competitive programming due to the complexity of test case specifications.

∗Corresponding author

These shortcomings highlight a critical gap in automated testing: existing methods struggle to generate test cases that adhere strictly to complex problem constraints while capturing edge cases essential for algorithm validation. For instance, inaccuracies in some program synthesis benchmarks, as revealed by Liu et al. [2023], further emphasize the necessity of robust testing frameworks capable of addressing these gaps.

To tackle these challenges, we propose Context-Free Grammars with Counters (CCFGs), a novel formalism that integrates both syntactic and semantic elements of problem input specifications. By leveraging a fine-tuned CodeT5 [Wang et al., 2021] model, our approach translates natural language descriptions into CCFGs, enabling the automated generation of test cases that are valid, specification-compliant, and highly effective in uncovering algorithmic flaws. Figure 1 illustrates our proposed framework.

Our main contributions are threefold:

• We introduce CCFGs to encode problem input specifications, capturing both syntax and semantics in a unified framework tailored for competitive programming.
• We develop a specialized model to map natural language problem descriptions to CCFGs, ensuring precise and specification-compliant test case generation.
• Using the CodeContests dataset [Li et al., 2022], we demonstrate that CCFG-based test cases significantly outperform baseline methods in identifying algorithmic errors and distinguishing correct from incorrect solutions.

Note that the CodeContests dataset is a powerful resource for benchmarking and evaluating test case generation methods due to its diverse collection of competitive programming platforms such as AtCoder, CodeChef, Codeforces, etc.

One of the key strengths of our approach lies in its ability to overcome the primary limitation of grammar-based test case generation techniques-the need for a manually written input grammar for each specification. Unlike traditional methods that require crafting a dedicated grammar for every input specification, our approach generalizes seamlessly across all input specifications in competitive programming problems. This eliminates the need for extensive manual effort and expertise to define grammars, enabling broader applicability and reducing the risk of incomplete or erroneous test coverage. By bypassing the reliance on handcrafted grammars, our method ensures scalability and efficiency, adapting to diverse input formats without requiring tailored adjustments for each new specification. This capability not only simplifies the testing process but also enhances its robustness and versatility, making it particularly suited for dynamic and varied environments like competitive programming.

2 RelatedWork

2.1 Test Case Generation using LLMs

Recent advancements in LLMs have opened new possibilities for ATCG by leveraging their ability to understand and generate structured data, natural language, and code with remarkable accuracy [Feng et al., 2020; Guo et al., 2022; Li et al., 2022; Rozi`ere et al., 2023; Team et al., 2024].

TestAug [Yang et al., 2022] and ChatTESTER [Yuan et al., 2023] utilized ChatGPT to derive test cases directly from natural language descriptions of code, often accompanied by code snippets. These methods provide a straightforward way to automate test case generation but face limitations in covering complex program logic and edge cases due to the inherent difficulty in aligning natural language prompts with precise program semantics. TestEval [Wang et al., 2024] introduced a dataset of 210 Python programs sourced from LeetCode and designed three evaluation tasks: overall coverage, targeted line/branch coverage, and targeted path coverage.

CodaMosa [Lemieux et al., 2023] utilizes a programming dataset to generate test cases by leveraging the LLM (OpenAI's Codex [Chen et al., 2021]). Codex produces initial test cases that are syntactically and semantically meaningful, providing a strong foundation for further exploration. These test cases are then iteratively mutated to maximize code coverage. However, while CodaMosa effectively optimizes for code coverage, this metric does not always correlate with fault detection or real-world program behavior.

Recently, Xia et al. [2024], introduced Fuzz4All generating test cases of many different languages by leveraging the multilingual capabilities of LLMs. This approach accepts inputs in various formats, such as example code snippets, program specifications, or documentation, and uses multiple prompts to guide the LLM in generating fuzzing inputs.

2.2 Grammar-based Test Case Generation

Grammar-based fuzzing is well-established in software testing that uses formal grammars to guide the generation of inputs. The foundational work on fuzz testing by Miller et al. [1990] laid the groundwork for input generation techniques, demonstrating the effectiveness of random input generation. However, random fuzzing techniques often fail when targeting structured inputs because they are unlikely to produce valid test cases. On the other hand, grammar-based fuzzing, which relies on CFGs to generate syntactically valid test inputs, marked a substantial improvement over purely random input generation techniques by enabling more targeted testing.

Grammar-based white-box fuzzing [Godefroid et al., 2008] enhances traditional grammar-based fuzzing by incorporating symbolic execution, enabling the exploration of program paths. Srivastava and Payer [2021] have proposed Gramatron, which uses grammar automatons in conjunction with aggressive mutation operators to synthesize bug triggers faster.

Note that a significant limitation of grammar-based test case generation or fuzzing techniques is the requirement for a manually written input grammar. This dependency introduces several challenges, particularly in terms of time, expertise, and coverage. Crafting a comprehensive input grammar requires a deep understanding of the input structure, including syntax and semantics, which demands significant effort and domainspecific knowledge from the developer or tester.

3 Methodology

We introduce the Context-Free Grammars With Counters (CCFG) to mitigate the limitations of previous approaches to automated testing of competitive programming. CCFGs are tailor-made to capture the formal semantics of most programming competition problems in the concise form of formal grammar by utilizing the counters to capture numerical values specified in the specifications.

3.1 Context-Free Grammars With Counters

Let us start with a motivating example. Example 1 is an input specification of "1369 C. RationalLee" from Codeforces. 1

Example 1 (Input Specification).

• The first line contains one integer t.
• Next 3t lines contain test cases-one per three lines.
• The first line of each test case contains two integers n and k.
• The second line of each test case contains n integers a1, . . . , an.
• The third line contains k integers b1, . . . , bk.

To explain the necessity of CCFGs, let us describe the input specification of Example 1 using a CFG as follows; for simplicity, we assume we modify a generation algorithm of CFG to sample values of variables t, n, k, ai and bi according to their constraints during the generation.

1 https://codeforces.com/problemset/problem/1369/C

Example 2 (Incorrect CFG of Example 1).

While the above grammar can generate all valid test cases, it also generates invalid ones. During generation, each application of the production rule for T produces a single test case. Therefore, we need to limit the number of such applications to t, where the value of t is determined during the generation.

Intuitively, CCFG restricts the number of applications of production rules by using a counter to track the number of applications and selecting the next production rule based on the counter's value. Using this approach, we can modify the CFG of Example 2 to obtain the correct CCFG in Example 3.

Example 3 (Correct CCFG of Example 1).

Next, we generate test cases using the CCFG as follows. When applying the production rule for Ti to Tt, we set the value of an internal counter to t. Then, during the derivation of Ti-1, we decrement the counter by 1. Finally, when the counter value reaches 1, we apply the production for T1 to Ti.

Note that the proposed CCFG is substantially different from the grammar studied by Chistikov et al. [2018] as our CCFG can associate the integer input with non-terminals by predefined production rules during the parsing while Chistikov et al. consider a grammar that resets or adds integers to a pre-defined set of counters at each step.

3.2 CCFGT5 TranslationModel

Inspired by the idea of grammar prompting [Wang et al., 2023], which enables LLMs to use domain-specific constraints expressed through a formal grammar, we propose a translation model, CCFGT5, designed to translate a problem input specification in NL into a concise CCFG while preserving the original semantics. This model incorporates two specifically fine-tuned CodeT5 modules: one focuses on grammar, and the other on constraints. We use Adam optimizer with learning rate 10-5 and cross-entropy loss function to train each CodeT5 model. We generate candidate grammars and constraints with repetition penalty 2.5 and length penalty 1.0 from each model.

We also use a specialized CCFG tokenizer to enable effective training. Our tokenizer converts a CCFG into a list of grammar symbols and labels each symbol type with descriptive words, such as 'variable' and 'nonterminal,' to enhance the readability from the LLM's perspective.

4 Experiments

We evaluate the practical usefulness of CCFGs through experimental validation. All implementations and associated codes and datasets used in these experiments are available in our GitHub repository. 2

4.1 Dataset

We use the CodeContests dataset, which consists of various programming problems sourced from different competitive platforms [Li et al., 2022]. This dataset includes algorithms for programs in various programming languages and public, private, and generated test cases for each problem.

We manually created CCFGs for 1,500 different problems based on their descriptions and categorized the human-labeled grammars into three levels: easy, normal and hard. Easy problems consist of simple grammars that consist solely of variables, without any complex structures or additional elements. Normal problems include grammars with one nonterminal that requires counting or tracking. Lastly, hard problems encompass grammars that have more than one nonterminal. These grammars are the most complex, involving multiple non-terminal elements and adding layers of complexity and structure. After categorizing the grammars, we split them into a training dataset with 1,200 problems and an evaluation dataset with 300 problems. Notably, the training dataset contains more difficult grammars to help the model learn complex syntactic structures effectively. Table 1 summarizes the difficulty distribution of each dataset.

We filter out 6 problems from the evaluation dataset for which CodeContests has no incorrect solutions that are necessary for evaluation. Additionally, we exclude 23 more problems that our CCFG implementation cannot fully support, due to the combinatorial complexity of input specification.

4.2 Test Case Sampling

As in Example 1, the value of a variable in a test case often determines the number of subsequent lines or variables in that test case. Therefore, we can control the length of the generated test cases by varying the interval of variable sampling during the generation. Instead of using the original interval (n, n+k), we sample a value of a variable from one of the following options: (1) the interval (n, n + k), (2) the interval (n, n + log k), (3) (n, n + log log k), or (4) the minimum value n. When generating ten long test cases, we first create a test case using option (1). If it fails (e.g., due to the timeout), we then try the options (2) and (3) in order. We also generate ten medium and short test cases by starting with options (2) and (3), respectively. Finally, if we succeed in generating a corner case with option (4), we replace one of the short test cases with the corner case.

2 https://github.com/Aditi1612/Grammar-based-test-case-generation

4.3 Baselines

Mutation-based fuzzing. We utilize the public and private test cases from the CodeContests dataset, tokenizing these test cases based on spaces and newline characters. We then randomly select 30% of tokens for mutation, adapting our approach according to the token type: integer, float, or string. This selective mutation process enables effective fuzzing while still adhering to the original input specifications.

Direct test case generation fromLLMs. We employ two LLMs, OpenAI's ChatGPT 4 and Google's Gemini, to generate test cases directly. We provide an input specification and a strict format required for generating the test cases. To fully exploit the performance of LLMs, we use the Chain-ofThought (CoT) [Wei et al., 2022] style prompt.

4.4 EvaluationMetrics

We carefully design evaluation metrics to address the following research questions throughout experimental results: (1) Is the CCFG-based approach better than direct test case generation? (2) Which method is most effective for generating CCFGs from descriptions?

Validity and generality. We say that a test case is valid if it follows the logical input specification of the problem. We evaluate the validity of each test case by determining whether or not the ground-truth grammar can parse the test case. Since it is computationally undecidable [Hopcroft et al., 2007] to decide whether or not a given CCFG is valid, we instead empirically measure element-based validity of grammar as the ratio of valid test cases to the total number of test cases. Additionally, we measure set-based validity of a grammar by checking whether all generated test cases are valid. The value of the set-based validity is either 0 or 1, while element-based validity can take any value in between. We say a set of test cases is valid if its set-based validity is 1.

Note that the validity alone cannot ensure that the grammar generates all the possible test cases described by the input specification. To measure how many valid test cases can be covered by a grammar, we define element-based generality of a grammar as the ratio of test cases that can be parsed by the grammar to the total number of test cases generated by the ground-truth grammar. A set-based generality of a grammar is 1 if and only if the test case-based generality is also 1. In this case, we call the grammar is general; otherwise, the set-based generality is 0. If the set of test cases generated by a grammar is valid and the grammar is general, we say that the grammar is (empirically) semantically equivalent to the ground-truth grammar. In contrast, we say that a grammar is syntactically equivalent to the ground truth if two grammars are equivalent except for the naming of variables.

Effectiveness. The primary purpose of test cases in competitive programming is to distinguish between correct and incorrect algorithms. For a given problem p, let Ap be a set of all incorrect algorithms implying that for each y ∈ Ap, there always exists a valid test case x such that ˆ y(x) ̸= y(x), where ˆ y(x) is the correct output for x. Then, we define the effectiveness E(x, Ap) of a test case x with respect to Ap as

which is the ratio of incorrect algorithms in Ap that are distinguishable by the test case x to all incorrect algorithms Ap. We extend to define the element-based effectiveness Eelt(X, Ap) of a set X of test cases with respect to Ap as

Note that the element-based effectiveness of a set of test cases is the average effectiveness of individual test cases in the set. If each test case can distinguish different incorrect algorithms, then the entire set can identify more incorrect algorithms compared to any single test case. Therefore, the diversity of the algorithms that the set can distinguish is also important. Thus, we define set-based effectiveness Eset(X, Ap) of a set X of test cases as

For experiments, we determine the correct output ˆ y(x) for a test case x by executing up to ten correct algorithms from the dataset and selecting the most frequently occurring output as the correct one. Additionally, for each problem p, we sample at most ten incorrect algorithms to create a set designated as Ap. We treat the output of algorithms that exceed twice the original timeout as ⊥, which is always considered incorrect.

We use a total of ten test cases from thirty test cases generated by CCFGs to compute set-based effectiveness, consisting of four short test cases (including corner case if possible) and three medium and long test cases. This approach ensures that we are using the same number of test cases as in the case of direct generation.

4.5 Analysis of Experimental Results

Table 2 presents statistics for test cases generated by either baseline algorithms or CCFGs. CCFG-based test cases with CCFGT510 exhibit the highest set-based validity and both types of effectiveness, achieving 81.18%, 42.26% and 67.73%. In contrast, direct generation using ChatGPT shows the highest element-based validity with 91.38%. Furthermore, when comparing the results of direct generation of ChatGPT and those of CCFG-based ChatGPT5, the latter shows higher effectiveness (65.29% compared to 63.54%).

It is important to note that the differences between the element-based validity and the set-based validity of CCFGbased approaches are relatively smaller than those in other categories. This suggests that the validity of each test case generated by the CCFG-based approach is more consistent for each problem specification. Once correct grammar and constraints are established, only valid test cases are generated. Additionally, when considering ChatGPT, the set-based validity over well-defined test sets with the CCFG-based approach is 93.36% (77.86%× 271/226), which is higher than the validity of direct generation at 78.97%. This indicates that the CCFG-based approach is more likely to fail in generating test cases than producing invalid ones.

As mentioned in Section 4.1, we use a human-labeled grammar as the ground-truth only when the grammar can parse all the public and private test cases in the CodeContests dataset. Therefore, the validity of these test cases is represented by the ratio of problems with well-defined test case sets to the number of total problems: 76.75% (208 out of 271) and 99.63% (270 out of 271). We also anticipate that the element-based and set-based effectiveness could reach 52.51% and 83.40%, respectively, which are of ground-truth grammars, if the model successfully generates semantically correct grammars.

Observation 1: CCFGs are especially effective for problems with more complex input specifications.

Table 3 shows the relationship between the difficulty of test case specifications, set-based validity, and effectiveness. We observe that the direct test case generation using ChatGPT achieves the highest validity and effectiveness, with 88.68% and 74.37% for problems with easy specifications. In contrast, CCFGT510 shows the highest results for problems with normal or hard specifications.

Interestingly, CCFGT510 exhibits a less pronounced tendency for validity to decrease as difficulty increases compared to other methods. This observation also highlights the robustness of CCFGT5 in understanding complex specifications.

Observation 2: Longer test cases tend to be more (elementwise) effective, but the set of test cases with various lengths is the most effective.

Table 4 presents the relationship between the length of test cases and effectiveness. This result indicates that the variation in intervals during generation impacts the efficiency of the resulting test case set, suggesting there is potential for increasing efficiency by improving the generation algorithm of CCFG. We also observe that the union of short and long test cases exhibits the highest effectiveness among combinations from the results using 20 test cases. This indicates that short and long test cases identify different incorrect problems.

Consequently, we conclude that utilizing a CCFG-based approach not only eliminates the need for individual test case validation but also enhances the effectiveness of test cases, particularly when input specifications are complex. Additionally, there is potential to further increase effectiveness by generating more test cases, which is straightforward with CCFGs, along with improved heuristics for diverse generation.

Observation 3: CCFGT5 generates more valid and general grammars than LLMs such as ChatGPT and Gemini.

The evaluation results presented in Table 5 demonstrate CCFGT5 produces the most general grammars (81.18%) and those that are semantically equivalent (78.23%). Notably, the average element-based generality closely aligns with the average set-based generality across all methods, with differences of less than or equal to 4.15%p for ChatGPT5. Since this difference reflects the ratio of ground-truth test cases parsed by non-general grammars, it suggests that determining whether a grammar is general using only a few sampled ground-truth test cases is reliable. When we compare CCFGT5 and LLMs, the ratios of syntactically different grammars to semantically equivalent grammars are 42.63% (1-16.24/40.96) and 63.68% (1-49.82/78.23) for GPT and CCFGT5, respectively. It indicates that LLMs generate more syntactically variant grammars compared to the fine-tuned CodeT5 model. Additionally, we use Jaccard similarity J(G, V ), which represents the ratio of the intersection to the union to measure the similarity between the set G of general grammars and the set of valid grammars V :

As a result, all similarities are greater than 80%, with CCFGT510 showing the largest similarity with 92.98%. This indicates that the most valid grammars are also general, and they can generate all the test cases based on how we sample the variables.

4.6 Case Study

We analyzed several failure cases where our proposed CCFGT5 model struggles to generate accurate CCFGs and their associated constraints. Frequently, the model misinterprets natural language constraints, converting them incorrectly into numerical constraints, and often handles grammars in natural language format rather than structured CCFG. This leads to incomplete coverage of specified constraints and the omission of additional implicit constraints. Also, the model fails to cover all the constraints present in the CCFG, along with some unknown constraints that are not included in the problem specification.

In Example 4, the model extracts a constraint for a variable n in natural language rather than converting it in to the expected formal expression n ≤ 105 . Note that every constraint in ground-truth grammars consists solely of formal expressions.

Our model encounters difficulties in understanding the necessity of translating the natural language explanation into a formal representation. This failure is caused by the fact that most specifications in our training dataset contain explicit formal representations for constraints, while this example has such constraints in natural language.

The first line contains a positive integer n --- the original number. The number of digits in this number does not exceed 10ˆ5. The number is written without any leading zeroes.

Grammar: ["<S> -> n"] Constraints: ["Thenumberdoesnotexceed10ˆ5."]

Additionally, in Example 5, CCFGT5 erroneously conflates xi as a variable that does not use a counter. This indicates that the model fails to understand the meaning of "Each line", which implies a use of a counter for x.

In contrast, the model accurately produces x i as a variable that uses counters in Constraint. This inconsistency arises because we compose CCFGT5 with two independent finetuned CodeT5 modules for grammars and constraints, which assign different meanings for xi.

Example 5 (103 C. Russian Roulette from Codeforces).

The first line contains three integers n,

k and p (...) Then follow p lines; they are the queries. Each line contains one integer xi (1 <= xi <= n) (...)

Grammar: [ ..., "<Y_i> -> <Y_i-1> <n> xi", "<Y_1> -> xi" ] Constraints: [..., "1<=x_i<=n"]

These failures are caused by uncommon natural language expressions for constraints and inconsistent variable representations in the CodeContests dataset. Data augmentation and normalization can address these issues.

5 Conclusions

We presented a novel framework leveraging CCFGs for ATCG in competitive programming. By translating input specifications into formal grammars, our method bridges the gap between specification complexity and test case validity, offering substantial improvements in the accuracy and coverage of generated test cases. Experiments highlight the effectiveness of our approach in distinguishing incorrect algorithms and ensuring specification compliance.

We will expand CCFGs to handle broader input domains and optimizing sampling strategies. By advancing these directions, our methodology could serve as a foundation for scalable, reliable test case generation across diverse software engineering applications.

Acknowledgments

Sung and Han were supported by the NRF grant (RS-202500562134) and the AI Graduate School Program at Yonsei University (RS-2020-II201361) funded by the Korean government (MSIT). Aditi and Ko were supported by the NRF grant (RS-2023-00208094) funded by MSIT.