An Automated Error Localization System for Introductory Programming Assignments

Abstract

The demand of software education is increasing world wide. However, there

is a lack of teachers and infrastructure corresponding for the demand. There-

fore, we present HONEYBEE in this paper, a new error localization algorithm

using the maximum satisability (MAX-SAT). It automatically detects the fault

locations of the program submitted by students in introductory programming

courses. The method is as follows: First, it constructs a logical expression, a

trace formula, representing the execution

ow for a student program. Second,

the trace formula is then extended by attaching the correct input and output

pair and supplemental constraints from the answer program. Third, it uses a

maximum satisability solver to nd the minimum error point which is a po-

tential fault.

We evaluate HONEYBEE in two domains. First, HONEYBEE found 87% of

the exact error locations of articial programs. Second, it also detected 80%

of the fault of real submitted codes. It shows our system works well in actual

situation. Moreover, it suggests the method using answer programs and multiple

counter examples to improve performance.