Measuring code behavioral similarity for programming and software engineering education
The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Abstract
In recent years, online programming and software engineering education via information technology has gained a lot of popularity. Typically, popular courses often have hundreds or thousands of students but only a few course staff members. Tool automation is needed to maintain the quality of education. In this paper, we envision that the capability of quantifying behavioral similarity between programs is helpful for teaching and learning programming and software engineering, and propose three metrics that approximate the computation of behavioral similarity. Specifically, we leverage random testing and dynamic symbolic execution (DSE) to generate test inputs, and run programs on these test inputs to compute metric values of the behavioral similarity. We evaluate our metrics on three real-world data sets from the Pex4Fun platform (which so far has accumulated more than 1.7 million game-play interactions). The results show that our metrics provide highly accurate approximation to the behavioral similarity. We also demonstrate a number of practical applications of our metrics including hint generation, progress indication, and automatic grading.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“Measuring functional equivalence is not the purpose of BPlag as there are already tools that exist to measure similarity through functional equivalence (e.g.[14], [31], [32], [34], [35]).”
From Academic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity (2021) · cites this paper as [14]
Citations
Cites
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · cited 1×
“Dynamic symbolic execution (DSE) [11,23,26] is a technique that executes a program both symbolically and concretely to collect constraints from branches and systematically negates part of the collected constraints to generate new program inputs.”
BackgroundDART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065036 · Cited by 2,067
CCFinder: a multilinguistic token-based code clone detection system for large scale source code
Kamiya, T., Kusumoto, S., & Inoue, K. (2002) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2002.1019480 · Cited by 1,711
CUTE: a concolic unit testing engine for C
Sen, K., Marinov, D., & Agha, G. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081750 · Cited by 1,651
DART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065036 · Cited by 1,570
Clone detection using abstract syntax trees
Baxter, I. D., Yahin, A., Moura, L., Sant'Anna, M., & Bier, L. (2002) · Proceedings. International Conference on Software Maintenance (Cat. No. 98CB36272) · doi:10.1109/icsm.1998.738528 · Cited by 1,277
Automated Whitebox Fuzz Testing.
Godefroid, P., Levin, M. Y., & Molnar, D. A. (2008) · Cited by 1,095
Feedback-Directed Random Test Generation
Pacheco, C., Lahiri, S. K., Ernst, M. D., & Ball, T. (2007) · 29th International Conference on Software Engineering (ICSE'07) · doi:10.1109/icse.2007.37 · Cited by 863
Pex–White Box Test Generation for .NET
Tillmann, N., & de Halleux, J. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79124-9_10 · Cited by 791
Self-citationUsing Slicing to Identify Duplication in Source Code
Komondoor, R., & Horwitz, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-47764-0_3 · Cited by 527
Automated feedback generation for introductory programming assignments
Singh, R., Gulwani, S., & Solar-Lezama, A. (2013) · Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2491956.2462195 · Cited by 383
Adaptive Random Testing: The ART of test case diversity
Chen, T. Y., Kuo, F.-C., Merkel, R. G., & Tse, T. H. (2010) · Journal of Systems and Software · doi:10.1016/j.jss.2009.02.022 · Cited by 353
Differential symbolic execution
Person, S., Dwyer, M. B., Elbaum, S., & Pǎsǎreanu, C. S. (2008) · Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering · doi:10.1145/1453101.1453131 · Cited by 268
Grading student programs using ASSYST
Jackson, D., & Usher, M. (1997) · Proceedings of the twenty-eighth SIGCSE technical symposium on Computer science education · doi:10.1145/268084.268210 · Cited by 253
Incremental program testing using program dependence graphs
Bates, S., & Horwitz, S. (1993) · Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93 · doi:10.1145/158511.158694 · Cited by 222
SYMDIFF: A Language-Agnostic Semantic Diff Tool for Imperative Programs
Lahiri, S. K., Hawblitzel, C., Kawaguchi, M., & Rebêlo, H. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-31424-7_54 · Cited by 197
Semantic Diff: a tool for summarizing the effects of modifications
Jackson, & Ladd (1994) · Proceedings International Conference on Software Maintenance ICSM-94 · doi:10.1109/icsm.1994.336770 · Cited by 185
Automatic mining of functionally equivalent code fragments via random testing
Jiang, L., & Su, Z. (2009) · Proceedings of the eighteenth international symposium on Software testing and analysis · doi:10.1145/1572272.1572283 · Cited by 172
Probabilistic symbolic execution
Geldenhuys, J., Dwyer, M. B., & Visser, W. (2012) · Proceedings of the 2012 International Symposium on Software Testing and Analysis · doi:10.1145/2338965.2336773 · Cited by 144
Characteristic studies of loop problems for structural test generation via symbolic execution
Xiao, X., Li, S., Xie, T., & Tillmann, N. (2013) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2013.6693084 · Cited by 96
Self-citationUsing semantic differencing to reduce the cost of regression testing
Binkley, D. (2003) · IEEE International Conference on Software Maintenance (ICSM) · doi:10.1109/icsm.1992.242560 · Cited by 91
Teaching and learning programming and software engineering via interactive gaming
Tillmann, N., de Halleux, J., Xie, T., Gulwani, S., & Bishop, J. (2013) · doi:10.5555/2486788.2486941 · Cited by 89
Self-citationSemantic similarity-based grading of student programs
Wang, T., Su, X., Wang, Y., & Ma, P. (2006) · Information and Software Technology · doi:10.1016/j.infsof.2006.03.001 · Cited by 86
DiffGen: Automated Regression Unit-Test Generation
Taneja, K., & Xie, T. (2008) · 2008 23rd IEEE/ACM International Conference on Automated Software Engineering · doi:10.1109/ase.2008.60 · Cited by 79
Self-citationAutomated grading of DFA constructions
Alur, R., D’Antoni, L., Gulwani, S., Kini, D., & Viswanathan, M. (2013) · International Joint Conference on Artificial Intelligence · Cited by 74
XIAO: tuning code clones at hands of engineers in practice
Dang, Y., Zhang, D., Song, G., Chu, C., Qiu, Y., & Xie, T. (2012) · Annual Computer Security Applications Conference · doi:10.1145/2420950.2421004 · Cited by 64
Self-citationAn automatic grading scheme for simple programming exercises
Hext, J. B., & Winings, J. W. (1969) · Communications of the ACM · doi:10.1145/362946.362981 · Cited by 62
Linear complexity object-oriented similarity for clone detection and software evolution analyses
Merlo, E., Antoniol, G., Penta, M. D., & Rollo, V. F. (2004) · IEEE International Conference on Software Maintenance (ICSM) · doi:10.1109/icsm.2004.1357826 · Cited by 46
Code hunt: experience with coding contests at scale
Bishop, J., Horspool, R. N., Xie, T., Tillmann, N., & de Halleux, J. (2015) · doi:10.5555/2819009.2819072 · Cited by 45
Self-citationTransferring an automated test generation tool to practice: from pex to fakes and code digger
Tillmann, N., de Halleux, J., & Xie, T. (2014) · Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering · doi:10.1145/2642937.2642941 · Cited by 38
Self-citation
Research works printed but not linked: 6
- 10.5555/850947.853341 · doi:10.5555/850947.853341
- 10.5555/1792734.1792766 · doi:10.5555/1792734.1792766
- 10.5555/645543.655704 · doi:10.5555/645543.655704
- 10.5555/647170.718283 · doi:10.5555/647170.718283
- 10.5555/1018431.1021448 · doi:10.5555/1018431.1021448
- 10.5555/1792786.1792798 · doi:10.5555/1792786.1792798
Cited by
Hahn, M. G., Navarro, S. M. B., De La Fuente Valentin, L., & Burgos, D. (2021) · IEEE Access · doi:10.1109/access.2021.3100890 · Cited by 111
“These include mathematics [47], code [22], and controlled environments such as simulations [40].”
BackgroundF a C o Y: a code-to-code search engine
Kim, K., Kim, D., Bissyandé, T. F., Choi, E., Li, L., Klein, J., & Traon, Y. L. (2018) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3180155.3180187 · Cited by 117
Building a Comprehensive Automated Programming Assessment System
Mekterovic, I., Brkic, L., Milasinovic, B., & Baranovic, M. (2020) · IEEE Access · doi:10.1109/access.2020.2990980 · Cited by 74
Academic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity
Cheers, H., Lin, Y., & Smith, S. P. (2021) · IEEE Access · doi:10.1109/access.2021.3069367 · Cited by 59
“For example, analysing the functional equivalence of a program [14], [31], the use of data at runtime [32], identifying similar interactions”
BackgroundCode relatives: detecting similarly behaving software
Su, F.-H., Bell, J., Harvey, K., Sethumadhavan, S., Kaiser, G. E., & Jebara, T. (2016) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2950290.2950321 · Cited by 71
Metadata
- Authors
- Li, S., Xiao, X., Bassett, B., Xie, T., & Tillmann, N.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- NEC Laboratories America, Princeton, NJ
- Microsoft (United States) (US)
- Venue
- Proceedings of the 38th International Conference on Software Engineering Companion
- Publisher
- ACM
- Published
- 2016-05-14
- Pages
- 501-510
- ISSN
- 0270-5257 (ISSN-L)
- OpenAlex
- W2400080339
- Semantic Scholar
- e98b8b543d461b79df6c5677e9574127d152bc15
- Cited by
- 30
- References
- 30
- Citations by year
- 2025: 2 · 2024: 3 · 2023: 4 · 2022: 1 · 2021: 5 · 2020: 5 · 2019: 4 · 2018: 4 · 2017: 1 · 2016: 1
- FWCI
- 2.66
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Keywords
- behavioral similarity, online programming education, software engineering education, dynamic symbolic execution, random testing, test data generation, hint generation, automated grading
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.