Dynamic Neural Program Embedding for Program Repair

• Syntax-based representations miss execution order and program dependencies, while small syntactic differences can correspond to substantially different program semantics.The introduction illustrates the issue with Bubble Sort and Insertion Sort, which share many structural features but implement different algorithms.Source: §1 · pp. 1–2
• The paper introduces variable-trace, state-trace, and hybrid embeddings of runtime variable valuations, which RNNs can use to model data and control dependencies.The hybrid approach incorporates dependencies into individual variable sequences to avoid redundant variable values in program states.Source: §1 · p. 3
• Unlike Reed & De Freitas (2015), who represent traces as executed statements, this approach records program states that can capture semantic differences between algorithms.State sequences provide input-output information for each executed statement; the sorting example shows how state valuations distinguish algorithms whose modified-variable statements appear identical.Source: §1 · p. 3
• Dynamic embeddings significantly outperform token-sequence and AST embeddings at predicting student mistake types across Microsoft-DEV204.1X and two CodeHunt problems.The evaluation uses submissions to the Module 2 assignment and two additional CodeHunt problems.Source: §1 · p. 3
• The embeddings also significantly improve the efficiency of SARFGEN1 (Wang et al., 2017), and the paper identifies synthesis, fault localization, and similarity detection as potential applications.Source: §1 · p. 3

2 BACKGROUND: DYNAMIC PROGRAM ANALYSIS

• Dynamic analysis studies program executions rather than source code, modeling sequential executions as traces of statement events.The paper considers sequential rather than parallel executions.Source: §2 · pp. 3–4
• Instrumentation adds monitoring code to record statements of interest, often inserting writes after statements that change variable values.These statements provide a window for inspecting variables; insertion can be automated by traversing the program’s abstract syntax tree.Source: §2 · p. 4
• Execution traces distinguish bubble sort from insertion sort despite similar syntax, illustrating dynamic analysis’s ability to identify behavior-relevant program parts.Dynamic analysis has also supported tools such as debuggers, profilers, monitors, and explanation generators.Source: §2 · p. 4

Variable Trace Embedding

• Variable trace embedding encodes each variable’s sub-trace independently with one shared RNN, max-pools its final states into a program embedding, and uses a softmax regression layer for prediction.Each row of the trace represents a program point where a variable is updated.Source: §3 · p. 4, Figure 3 · p. 5

State Trace Embedding

• State trace embedding encodes each program state’s tuple of latest variable values with one RNN, then feeds those states to a second RNN to capture within-state dependencies and relationships across states.Variable values are encoded in a consistent order across states; the second RNN’s final state feeds a softmax regression layer.Source: §3 · p. 4, Figure 4 · p. 5

Dependency Enforcement for Variable Trace Embedding

• Dependency enforcement combines compact variable traces with explicit data and control dependencies by interleaving hidden states from separate variable-specific RNNs, then average-pooling their final states.A softmax regression layer uses the resulting program embedding for prediction.Source: §3 · pp. 4–5, Figure 5 · p. 5

4.1 VARIABLE TRACE MODEL

• The variable-trace model runs a GRU over each variable’s assigned values, max-pools the final hidden states, then predicts an error class with a linear model and softmax.For presentation simplicity and without loss of generality, the paper assumes programs take no inputs.Source: §4.1 · p. 6, §4.3 · p. 6

4.2 STATE TRACE MODEL

• The state-trace model embeds variables in each program state, then feeds the ordered state embeddings to a second RNN to form the program embedding.The two RNN encoders have hidden-layer sizes k1 and k2, respectively.Source: §4.2 · p. 6

4.3 DEPENDENCY ENFORCEMENT FOR VARIABLE TRACE EMBEDDING

• Dependency enforcement fuses latest hidden states from variable-specific RNNs according to how new variable values are produced, incorporating data and control dependencies.The model aligns traces with dynamic time wrapping, consistently renames the top-n most-used variables, and maps all others to one special variable; it enforces data dependencies in assignments, declarations, and method calls, and control dependencies in if, for, and while statements.Source: §4.3 · pp. 6–7

Evaluation data

• Training data came from Assignment 2 submissions for Microsoft-DEV204.1X and two Microsoft CodeHunt problems; errors ranged from technical issues to conceptual misunderstandings.The problems included printing a chessboard, counting nested parentheses, and generating binary digits.Source: §5 · p. 7

Evaluation setup

• To build training data, the authors split incorrect programs into single-error examples and mutated correct programs into synthetic incorrect examples, then compared dynamic and syntax-based RNN embeddings on the same test data.Syntax baselines encoded runtime syntactic traces, token sequences, or abstract syntax trees.Source: §5 · p. 7

Error prediction

• Execution-trace embeddings achieved greater than 92% accuracy, versus less than 27% for syntax-based embeddings, on student error-pattern prediction.The authors conjecture that trace embeddings canonicalize syntactic variation and expose underlying semantic differences, helping models learn error patterns from relatively little training data.Source: Table 3 · p. 8, §5 · p. 8

Repair search

• SARFGEN’s enumerative repair search was guided by dynamic-embedding correction predictions, testing the top-ranked error and repeating repairs until programs were fixed; runtime was compared with enumeration.Some predicted corrections were merely syntactic changes that did not alter program semantics and would need filtering for precise fixes.Source: §5 · pp. 8–9
• For programs requiring four or more fixes, embedding-guided search yielded more than an order-of-magnitude speedups, but gains dropped when fixes exceeded seven.Predictions became unreliable for programs with too many errors; programs with more than 10 errors were excluded because the baseline often ran out of memory.Source: Table 4 · p. 9, §5 · p. 9

6 RELATED WORK

• Existing neural repair techniques DeepFix, SynFix (Bhatia & Singh, 2016), and sk p (Pu et al., 2016) had not used dynamic embeddings, which can extend them as a new feature dimension.Source: §6 · p. 9
• Piech et al. (2015) represent programs with input-output pairs, but identical pairs can arise from different programs, and shared error patterns can yield different pairs.The paper argues this makes their approach ineffective for those scenarios.Source: §6 · p. 9
• Reed & De Freitas (2015) use instruction sequences to induce algorithms, aiming to synthesize neural controllers for low-level actions rather than learn semantic representations of high-level programs.Source: §6 · p. 9
• Socher et al. (2013), Zaremba et al. (2014), and Bowman (2013) model semantics in sentences or symbolic expressions, but target domains other than programs.Source: §6 · p. 9

7 CONCLUSION

• Dynamic program embeddings significantly outperform syntax-based embeddings in predicting student error patterns.The embeddings are learned from runtime execution traces.Source: §7 · p. 9
• More than 10x speedups over an enumerative baseline are achieved for search-based program repair.Source: §7 · p. 9
• The embeddings are used to predict error patterns in students’ online programming submissions.Source: §7 · p. 9
• The authors suggest the dynamic embeddings may also support neural program induction and synthesis.Source: §7 · p. 10

• Chessboard submissions showed symbol or case errors, reversed odd/even patterns, failure to alternate after the first row, or use of only X or O.Source: APPENDIX ERROR PATTERNS · p. 11
• Other chessboard errors included extra characters, incorrect row or column counts, and incorrect spacing to form rows.Source: APPENDIX ERROR PATTERNS · p. 11
• Parenthesis errors included treating parentheses as generic symbols, mishandling unmatched strings, counting matches instead of depth, assuming nesting, and miscounting ignored characters.Source: APPENDIX ERROR PATTERNS · p. 11
• Binary-string errors included missing the integer-zero case, interpreting digits as bytes, shift arithmetic mistakes, adding rather than concatenating digits, or omitting the most-significant-bit one.Source: APPENDIX ERROR PATTERNS · p. 11

SARFGEN’S ALGORITHM

• SARFGEN identifies correct reference programs for an incorrect submission and generates syntactic discrepancies against them.The procedure takes the incorrect program P and correct solutions Ps as inputs.Source: SARFGEN’S ALGORITHM · p. 12
• The algorithm selects discrepancy subsets from size one through |C(P, Pc)|, applies each subset as a patch, checks whether the patched program is correct, and compares its size with k.The patch-application step notes that k is updated if necessary.Source: SARFGEN’S ALGORITHM · p. 12
• The model-augmented procedure extracts the incorrect program’s dynamic execution trace and uses a pretrained model to prioritize discrepancy subsets.It takes a learned model M as an additional input while retaining the reference-program identification and discrepancy-generation steps.Source: SARFGEN’S ALGORITHM · p. 12