SemCluster: clustering of imperative programming assignments based on quantitative semantic features
SemCluster: clustering of imperative programming assignments based on quantitative semantic features
复制标题
DOI：
10.1145/3314221.3314629
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
D. Perry;Dohyeong Kim;R. Samanta;X. Zhang
中科院分区：
文献类型：
--
作者：
D. Perry;Dohyeong Kim;R. Samanta;X. Zhang
大规模编程作业自动推理的一个基本挑战是根据学生提交的底层算法对学生提交的内容进行聚类。最先进的聚类技术对控制结构变化很敏感，无法将有缺陷的解决方案与类似的正确解决方案聚类，并且需要昂贵的成对程序分析或培训工作。我们提出了一种新技术，可以根据算法本质对小型命令式程序进行聚类：（A）如何将输入空间划分为等价类，以及（B）如何在各个等价类中唯一地解决问题。我们将这些算法方面捕获为两个定量语义程序特征，并将其合并到程序的向量表示中。然后使用程序的向量表示对程序进行聚类。我们的第一个语义特征的计算利用模型计数来识别属于输入等价类的输入数量。我们的第二个语义特征的计算通过跟踪变量在其生命周期内唯一的连续值对的出现次数来抽象程序的数据流。对我们的工具 SemCluster 对小型编程任务的解决方案进行的基准进行综合评估表明，SemCluster (1) 生成的聚类比其他聚类技术少得多，(2) 精确地识别不同的解决方案策略，(3) 提高了基于聚类的程序修复的性能，所有这些都在合理的时间内完成。
A fundamental challenge in automated reasoning about programming assignments at scale is clustering student submissions based on their underlying algorithms. State-of-the-art clustering techniques are sensitive to control structure variations, cannot cluster buggy solutions with similar correct solutions, and either require expensive pair-wise program analyses or training efforts. We propose a novel technique that can cluster small imperative programs based on their algorithmic essence: (A) how the input space is partitioned into equivalence classes and (B) how the problem is uniquely addressed within individual equivalence classes. We capture these algorithmic aspects as two quantitative semantic program features that are merged into a program's vector representation. Programs are then clustered using their vector representations. The computation of our first semantic feature leverages model counting to identify the number of inputs belonging to an input equivalence class. The computation of our second semantic feature abstracts the program's data flow by tracking the number of occurrences of a unique pair of consecutive values of a variable during its lifetime. The comprehensive evaluation of our tool SemCluster on benchmarks drawn from solutions to small programming assignments shows that SemCluster (1) generates far fewer clusters than other clustering techniques, (2) precisely identifies distinct solution strategies, and (3) boosts the performance of clustering-based program repair, all within a reasonable amount of time.