InvAASTCluster: On Applying Invariant-Based Program Clustering to Introductory Programming Assignments

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F25%3A00387602" target="_blank" >RIV/68407700:21730/25:00387602 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.jss.2025.112481" target="_blank" >https://doi.org/10.1016/j.jss.2025.112481</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jss.2025.112481" target="_blank" >10.1016/j.jss.2025.112481</a>

Result language

angličtina

Original language name

InvAASTCluster: On Applying Invariant-Based Program Clustering to Introductory Programming Assignments

Original language description

Due to the vast number of students enrolled in programming courses, there has been an increasing number of automated program repair techniques focused on introductory programming assignments (IPAs). Typically, such techniques use program clustering to take advantage of previous correct student implementations to repair a new incorrect submission. These repair techniques use clustering methods since analyzing all available correct submissions to repair a program is not feasible. However, conventional clustering methods rely on program representations based on features such as abstract syntax trees (ASTs), syntax, control flow, and data flow. This paper proposes InvAASTCluster, a novel approach for program clustering that uses dynamically generated program invariants to cluster semantically equivalent IPAs. InvAASTCluster’s program representation uses a combination of the program’s semantics, through its invariants, and its structure through its anonymized abstract syntax tree (AASTs). Invariants denote conditions that must remain true during program execution, while AASTs are ASTs devoid of variable and function names, retaining only their types. Our experiments show that the proposed program representation outperforms syntax-based representations when clustering a set of correct IPAs. Furthermore, we integrate InvAASTCluster into a state-of-the-art clustering-based program repair tool. Our results show that InvAASTCluster advances the current state-of-the-art when used by clustering-based repair tools by repairing around 13% more students’ programs, in a shorter amount of time.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

The Journal of Systems and Software

ISSN

0164-1212

e-ISSN

1873-1228

Volume of the periodical

230

Issue of the periodical within the volume

December

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

—

UT code for WoS article

001532765400001

EID of the result in the Scopus database

2-s2.0-105009886596