CoChat
Sign Up
Cited by 55

Automated clustering and program repair for introductory programming assignments

Gulwani, Sumit, Radiček, Ivan, Zuleger, Florian·2018·ACM SIGPLAN Notices
DOI 10.1145/3296979.3192387
Open this paper in CoChat — free account

Abstract

Providing feedback on programming assignments is a tedious task for the instructor, and even impossible in large Massive Open Online Courses with thousands of students. Previous research has suggested that program repair techniques can be used to generate feedback in programming education. In this paper, we present a novel fully automated program repair algorithm for introductory programming assignments. The key idea of the technique, which enables automation and scalability, is to use the existing correct student solutions to repair the incorrect attempts. We evaluate the approach in two experiments: (I) We evaluate the number, size and quality of the generated repairs on 4,293 incorrect student attempts from an existing MOOC. We find that our approach can repair 97% of student attempts, while 81% of those are small repairs of good quality. (II) We conduct a preliminary user study on performance and repair usefulness in an interactive teaching setting. We obtain promising initial results (the average usefulness grade 3.4 on a scale from 1 to 5), and conclude that our approach can be used in an interactive setting.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3296979.3192387

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • CLARA clusters multiple correct implementations and selects the one that produces the smallest fix when aligned with the buggy program.

    “CLARA clusters multiple correct implementations and selects the one that produces the smallest fix when aligned with the buggy program.”

    From Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization (2025) · cites this paper as Gulwani, Radicek, and Zuleger 2018

    In “Constraint-Optimization Local Repairs” (page not specified), the paper says CLARA runs the repair algorithm on each cluster of correct programs and chooses the repair with the lowest syntactic-distance cost. But the claim says it selects one correct implementation; the “Summary” says a repair can combine expressions from multiple correct solutions within a cluster. (LLM, conf=0.87)

    Experimental — accuracy not yet measured

  • Both VERIFIX and CLARA require an exact match between control flow graphs and a bijective relationship between variables; otherwise they return a structural mismatch error.

    “Both tools require an exact match between the control flow graphs (e.g., branches, loops) and a bijective relationship between the variables; otherwise, they return a structural mismatch error.”

    From Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization (2025) · cites this paper as Gulwani, Radicek, and Zuleger 2018

    The Matching and §4 Matching and Clustering passages say CLARA requires matching control flow and defines program matching using a bijective variable relation. But Matching explicitly allows different branching structures when the looping structure matches, so an exact match of branches is not required. The paper does not establish VERIFIX’s requirements or say either tool returns a ‘structural mismatch error.’ (LLM, conf=0.89)

    Experimental — accuracy not yet measured

  • Our method allows LLMs to repair more programs than other configurations and state-of-the-art symbolic program repair tools.

    “This method enables LLMS to repair more programs and produce superior fixes with smaller patches, outperforming both other configurations and state-of-the-art symbolic program repair tools (Gulwani, Radicek, and Zuleger 2018; Ahmed et al. 2022).”

    From Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization (2025) · cites this paper as Gulwani, Radicek, and Zuleger 2018

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 33

  1. Anne Adam and Jean-Pierre Laurent. 1980. LAURA, a system to debug student programs. Artificial Intelligence 15, 1âĂŞ2 (1980), 75 -122. h ps://doi.org/10.1016/0004-3702(80)90023-5 · DOI
  2. Andrea Arcuri. 2008. On the Automation of Fixing Software Bugs. In Companion of the 30th International Conference on Software Engi- neering (ICSE Companion '08). ACM, New York, NY, USA, 1003-1006. h ps://doi.org/10.1145/1370175.1370223 · DOI
  3. D. Beyer, A. Cimatti, A. Griggio, M. E. Keremoglu, S. F. University, and R. Sebastiani. 2009. Software model checking via large-block encoding. In 2009 Formal Methods in Computer-Aided Design. 25-32. h ps://doi.org/10.1109/FMCAD.2009.5351147 · DOI
  4. Satish Chandra, Emina Torlak, Shaon Barman, and Rastislav Bodik. 2011. Angelic Debugging. In Proceedings of the 33rd International Con- ference on Software Engineering (ICSE '11). ACM, New York, NY, USA, 121-130. h ps://doi.org/10.1145/1985793.1985811 · DOI
  5. Loris D'Antoni, Roopsha Samanta, and Rishabh Singh. 2016. Qlose: Program Repair with Quantitative Objectives. In Com- puter Aided Verification -28th International Conference, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part II. 383-401. h p://dx.doi.org/10.1007/978-3-319-41540-6_21 · DOI
  6. Rajdeep Das, Umair Z. Ahmed, Amey Karkare, and Sumit Gul- wani. 2016. Prutor: A System for Tutoring CS1 and Collect- ing Student Programs for Analysis. CoRR abs/1608.03828 (2016). h p://arxiv.org/abs/1608.03828 · arXiv
  7. V. Debroy and W.E. Wong. 2010. Using Mutation to Automatically Suggest Fixes for Faulty Programs. In Software Testing, Verification and Validation (ICST), 2010 Third International Conference on. 65-74. h ps://doi.org/10.1109/ICST.2010.66 · DOI
  8. A. Drummond, Y. Lu, S. Chaudhuri, C. Jermaine, J. Warren, and S. Rixner. 2014. Learning to Grade Student Programs in a Massive Open Online Course. In Data Mining (ICDM), 2014 IEEE International Con- ference on. 785-790. h ps://doi.org/10.1109/ICDM.2014.142 · DOI
  9. Stephanie Forrest, ThanhVu Nguyen, Westley Weimer, and Claire Le Goues. 2009. A Genetic Programming Approach to Automated Software Repair. In Proceedings of the 11th Annual Conference on Ge- netic and Evolutionary Computation (GECCO '09). ACM, New York, NY, USA, 947-954. h ps://doi.org/10.1145/1569901.1570031 · DOI
  10. Elena L. Glassman, Jeremy Scott, Rishabh Singh, Philip Guo, and Robert Miller. 2014. OverCode: Visualizing Variation in Student Solu- tions to Programming Problems at Scale. In Proceedings of the Adjunct Publication of the 27th Annual ACM Symposium on User Interface Soft- ware and Technology (UIST'14 Adjunct). ACM, New York, NY, USA, 129-130. h ps://doi.org/10.1145/2658779.2658809 · DOI
  11. Divya Gopinath, Muhammad Zubair Malik, and Sarfraz Khurshid. 2011. Specification-based Program Repair Using SAT. In Pro- ceedings of the 17th International Conference on Tools and Algo- rithms for the Construction and Analysis of Systems: Part of the Joint European Conferences on Theory and Practice of Software (TACAS'11/ETAPS'11). Springer-Verlag, Berlin, Heidelberg, 173-188. h p://dl.acm.org/citation.cfm?id=1987389.1987408
  12. C. Le Goues, N. Holtschulte, E. K. Smith, Y. Brun, P. Devanbu, S. Forrest, and W. Weimer. 2015. The ManyBugs and Intro- Class Benchmarks for Automated Repair of C Programs. IEEE Transactions on Software Engineering 41, 12 (Dec 2015), 1236-1256. h ps://doi.org/10.1109/TSE.2015.2454513 · DOI · Paper page
  13. Sumit Gulwani, Ivan Radiček, and Florian Zuleger. 2014. Feedback Generation for Performance Problems in Introductory Programming Assignments. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014). ACM, New York, NY, USA, 41-51. h ps://doi.org/10.1145/2635868.2635912 · DOI
  14. Andrew Head, Elena Glassman, Gustavo Soares, Ryo Suzuki, Lu- cas Figueredo, Loris D'Antoni, and Björn Hartmann. 2017. Writ- ing Reusable Code Feedback at Scale with Mixed-Initiative Pro- gram Synthesis. In Proceedings of the Fourth (2017) ACM Conference on Learning @ Scale (L@S '17). ACM, New York, NY, USA, 89-98. h ps://doi.org/10.1145/3051457.3051467 · DOI
  15. Petri Ihantola, Tuukka Ahoniemi, Ville Karavirta, and Otto Sep- pälä. 2010. Review of Recent Systems for Automatic Assess- ment of Programming Assignments. In Proceedings of the 10th Koli Calling International Conference on Computing Education Re- search (Koli Calling '10). ACM, New York, NY, USA, 86-93. h ps://doi.org/10.1145/1930464.1930480 · DOI
  16. Barbara Jobstmann, Andreas Griesmayer, and Roderick Bloem. 2005. Program Repair As a Game. In Proceedings of the 17th International Conference on Computer Aided Verification (CAV'05). Springer-Verlag, Berlin, Heidelberg, 226-238. h ps://doi.org/10.1007/11513988_23 · DOI
  17. Shalini Kaleeswaran, Anirudh Santhiar, Aditya Kanade, and Sumit Gulwani. 2016. Semi-supervised Verified Feedback Generation. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016). ACM, New York, NY, USA, 739-750. h ps://doi.org/10.1145/2950290.2950363 · DOI
  18. Yalin Ke, Kathryn T. Stolee, Claire Le Goues, and Yuriy Brun. 2015. Re- pairing Programs with Semantic Code Search (T). In Proceedings of the 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE) (ASE '15). IEEE Computer Society, Washington, DC, USA, 295-306. h p://dx.doi.org/10.1109/ASE.2015.60 · DOI
  19. Dohyeong Kim, Yonghwi Kwon, Peng Liu, I. Luk Kim, David Mitchel Perry, Xiangyu Zhang, and Gustavo Rodriguez-Rivera. 2016. Apex: Automatic Programming Assignment Error Explanation. In Proceedings of the 2016 ACM SIGPLAN International Confer- ence on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016). ACM, New York, NY, USA, 311-327. h ps://doi.org/10.1145/2983990.2984031 · DOI
  20. Robert Könighofer and Roderick Bloem. 2011. Automated Er- ror Localization and Correction for Imperative Programs. In Pro- ceedings of the International Conference on Formal Methods in Computer-Aided Design (FMCAD '11). FMCAD Inc, Austin, TX, 91- 100. h p://dl.acm.org/citation.cfm?id=2157654.2157671
  21. Fan Long and Martin Rinard. 2016. Automatic Patch Generation by Learning Correct Code. SIGPLAN Not. 51, 1 (Jan. 2016), 298-312. h p://doi.acm.org/10.1145/2914770.2837617 · DOI
  22. Ken Masters. 2011. A Brief Guide To Understanding MOOCs. The Internet Journal of Medical Education 1, 2 (2011). h ps://doi.org/10.5580/1f21 · DOI
  23. Andy Nguyen, Christopher Piech, Jonathan Huang, and Leonidas Guibas. 2014. Codewebs: Scalable Homework Search for Massive Open Online Programming Courses. In Proceedings of the 23rd Inter- national Conference on World Wide Web (WWW '14). ACM, New York, NY, USA, 491-502. h ps://doi.org/10.1145/2566486.2568023 · DOI
  24. Kelly Rivers and Kenneth R. Koedinger. 2017. Data-Driven Hint Gen- eration in Vast Solution Spaces: a Self-Improving Python Program- ming Tutor. International Journal of Artificial Intelligence in Education 27, 1 (01 Mar 2017), 37-64. h ps://doi.org/10.1007/s40593-015-0070-z · DOI
  25. Reudismam Rolim, Gustavo Soares, Loris D'Antoni, Oleksandr Polo- zov, Sumit Gulwani, Rohit Gheyi, Ryo Suzuki, and Björn Hartmann. 2017. Learning Syntactic Program Transformations from Exam- ples. In Proceedings of the 39th International Conference on Software Engineering (ICSE '17). IEEE Press, Piscataway, NJ, USA, 404-415. h ps://doi.org/10.1109/ICSE.2017.44 · DOI
  26. Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. 2013. Automated Feedback Generation for Introductory Programming As- signments. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '13). ACM, New York, NY, USA, 15-26. h ps://doi.org/10.1145/2491956.2462195 · DOI
  27. Stefan Staber, Barbara Jobstmann, and Roderick Bloem. 2005. Finding and Fixing Faults. In Correct Hardware Design and Verification Meth- ods, Dominique Borrione and Wolfgang Paul (Eds.). Lecture Notes in Computer Science, Vol. 3725. Springer Berlin Heidelberg, 35-49. h ps://doi.org/10.1007/11560548_6 · DOI
  28. Ryo Suzuki, Gustavo Soares, Elena Glassman, Andrew Head, Loris D'Antoni, and Björn Hartmann. 2017. Exploring the Design Space of Automatically Synthesized Hints for Introduc- tory Programming Assignments. In Proceedings of the 2016 CHI Conference Extended Abstracts on Human Factors in Computing Systems (CHI EA '17). ACM, New York, NY, USA, 2951-2958. h ps://doi.org/10.1145/3027063.3053187 · DOI
  29. Kuo-Chung Tai. 1979. The Tree-to-Tree Correction Problem. J. ACM 26, 3 (July 1979), 422-433. h ps://doi.org/10.1145/322139.322143 · DOI
  30. Nikolai Tillmann, Judith Bishop, R. Nigel Horspool, Daniel Perelman, and Tao Xie. 2014. Code Hunt: Searching for Secret Code for Fun. Proceedings of the International Con- ference on Software Engineering (Workshops) (June 2014). h p://research.microso .com/apps/pubs/default.aspx?id=210651
  31. Nikolai Tillmann, Jonathan De Halleux, Tao Xie, Sumit Gul- wani, and Judith Bishop. 2013. Teaching and Learning Pro- gramming and Software Engineering via Interactive Gam- ing. In Proc. 35th International Conference on Software En- gineering (ICSE 2013), Software Engineering Education (SEE). h p://www.cs.illinois.edu/homes/taoxie/publications/icse13see-pex4fun.pdf
  32. Jooyong Yi, Umair Z. Ahmed, Amey Karkare, Shin Hwei Tan, and Ab- hik Roychoudhury. 2017. A Feasibility Study of Using Automated Program Repair for Introductory Programming Assignments. In Pro- ceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2017). ACM, New York, NY, USA, 740-751. h ps://doi.org/10.1145/3106237.3106262 · DOI
  33. K. Zhang and D. Shasha. 1989. Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. SIAM J. Comput. 18, 6 (Dec. 1989), 1245-1262. h ps://doi.org/10.1137/0218082 · DOI

Cited by

Sorted by citations

Authors
Gulwani, S., Radiček, I., & Zuleger, F.
Affiliations
  • Microsoft, USA
  • Vienna University of Technology, Austria
Venue
ACM SIGPLAN Notices
Publisher
Association for Computing Machinery (ACM)
Published
2018-06-11
Volume
53
Issue
4
Pages
465-480
ISSN
  • 0362-1340
  • 1558-1160
DOI
10.1145/3296979.3192387
Cited by
55
References
1
Language
en
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review