CoChat
Sign Up
Cited by 34Software Engineering ResearchInformation Retrieval and Search BehaviorSoftware Engineering Techniques and Practices

Active Inductive Logic Programming for Code Search

Open access
Sivaraman, Aishwarya, Zhang, Tianyi, Van den Broeck, Guy, Kim, Miryung·2019·2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)
DOI 10.1109/icse.2019.00044
Open this paper in CoChat — free accountOpen PDF

Abstract

Modern search techniques either cannot efficiently incorporate human feedback to refine search results or cannot express structural or semantic properties of desired code. The key insight of our interactive code search technique ALICE is that user feedback can be actively incorporated to allow users to easily express and refine search queries. We design a query language to model the structure and semantics of code as logic facts. Given a code example with user annotations, ALICE automatically extracts a logic query from code features that are tagged as important. Users can refine the search query by labeling one or more examples as desired (positive) or irrelevant (negative). ALICE then infers a new logic query that separates positive examples from negative examples via active inductive logic programming. Our comprehensive simulation experiment shows that ALICE removes a large number of false positives quickly by actively incorporating user feedback. Its search algorithm is also robust to user labeling mistakes. Our choice of leveraging both positive and negative examples and using nested program structure as an inductive bias is effective in refining search queries. Compared with an existing interactive code search technique, ALICE does not require a user to manually construct a search pattern and yet achieves comparable precision and recall with much fewer search iterations. A case study with real developers shows that ALICE is easy to use and helps express complex code patterns.

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.1109/icse.2019.00044

Cites

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?

  • ILP systems have proven effective in learning SQL queries.

    “ILP systems have proven effective in learning SQL queries (Albarghouthi et al., 2017; Sivaraman et al., 2019)”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Sivaraman et al., 2019

    The Approach section says ALICE uses ILP to learn logical Prolog queries for code search, and the Introduction reports strong code-search results. Neither establishes that ILP systems have proven effective at learning SQL queries; the only SQL-query work found appears in the References. (LLM, conf=0.83)

    Experimental — accuracy not yet measured

  • Other applications include code search, in which an ILP system interactively learns a search query from examples.

    “Other applications include code search (Sivaraman et al., 2019), in which an ILP system interactively learns a search query from examples”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Sivaraman et al., 2019

Self-check

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

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

The citation lists haven’t been fetched yet

References 81 · Cited by 34

Research works printed but not linked: 62

  1. S. Kim, K. Pan, and E. Whitehead Jr, "Memories of bug fixes," in Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering. ACM, 2006, pp. 35-45.
  2. T. T. Nguyen, H. A. Nguyen, N. H. Pham, J. Al-Kofahi, and T. N. Nguyen, "Recurring bug fixes in object-oriented programs," in Soft- ware Engineering, 2010 ACM/IEEE 32nd International Conference on, vol. 1. IEEE, 2010, pp. 315-324.
  3. J. Park, M. Kim, B. Ray, and D.-H. Bae, "An empirical study of supplementary bug fixes," in Proceedings of the 9th IEEE Working Conference on Mining Software Repositories. IEEE Press, 2012, pp. 40-49.
  4. J. R. Cordy, "The txl source transformation language," Science of Computer Programming, vol. 61, no. 3, pp. 190-210, 2006.
  5. X. Wang, D. Lo, J. Cheng, L. Zhang, H. Mei, and J. X. Yu, "Matching dependence-related queries in the system dependence graph," in Proceedings of the IEEE/ACM international conference on Automated software engineering. ACM, 2010, pp. 457-466.
  6. J. Andersen and J. L. Lawall, "Generic patch inference," Automated software engineering, vol. 17, no. 2, pp. 119-148, 2010.
  7. N. H. Pham, T. T. Nguyen, H. A. Nguyen, and T. N. Nguyen, "Detection of recurring software vulnerabilities," in Proceedings of the IEEE/ACM international conference on Automated software engi- neering. ACM, 2010, pp. 447-456.
  8. N. Meng, M. Kim, and K. S. McKinley, "Systematic editing: gen- erating program transformations from an example," ACM SIGPLAN Notices, vol. 46, no. 6, pp. 329-342, 2011.
  9. --, "Lase: locating and applying systematic edits by learning from examples," in Proceedings of the 2013 International Conference on Software Engineering. IEEE Press, 2013, pp. 502-511.
  10. R. Rolim, G. Soares, L. D'Antoni, O. Polozov, S. Gulwani, R. Gheyi, R. Suzuki, and B. Hartmann, "Learning syntactic program transfor- mations from examples," in Proceedings of the 39th International Conference on Software Engineering. IEEE Press, 2017, pp. 404- 415.
  11. T. Zhang, M. Song, J. Pinedo, and M. Kim, "Interactive code review for systematic changes," in Proceedings of the 37th International Conference on Software Engineering-Volume 1. IEEE Press, 2015, pp. 111-122.
  12. S. Muggleton and L. De Raedt, "Inductive logic programming: Theory and methods," The Journal of Logic Programming, vol. 19, pp. 629- 679, 1994.
  13. L. D. Raedt, Logical and relational learning, ser. Cognitive Technologies. Springer, 2008. [Online]. Available: https://doi.org/ 10.1007/978-3-540-68856-3 · DOI · Paper page
  14. S. Haykin, Neural Networks: A Comprehensive Foundation (3rd Edition). Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 2007.
  15. W. W. Cohen, "Recovering software specifications with inductive logic programming," in AAAI, vol. 94, 1994, pp. 1-4.
  16. D. Alrajeh, J. Kramer, A. Russo, and S. Uchitel, "Elaborating requirements using model checking and inductive learning," IEEE Transactions on Software Engineering, vol. 39, no. 3, pp. 361-383, 2013.
  17. J. Starke, C. Luce, and J. Sillito, "Working with search results," in Search-Driven Development-Users, Infrastructure, Tools and Evalua- tion, 2009. SUITE'09. ICSE Workshop on. IEEE, 2009, pp. 53-56.
  18. M. B. S. Ahmad and A. Cheung, "Automatically leveraging mapre- duce frameworks for data-intensive applications," in Proceedings of the 2018 International Conference on Management of Data. ACM, 2018, pp. 1205-1220.
  19. --, "Leveraging parallel data processing frameworks with verified lifting," arXiv preprint arXiv:1611.07623, 2016. · arXiv
  20. J. Brandt, P. J. Guo, J. Lewenstein, M. Dontcheva, and S. R. Klem- mer, "Two studies of opportunistic programming: interleaving web foraging, learning, and writing code," in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2009, pp. 1589-1598.
  21. E. Duala-Ekoko and M. P. Robillard, "Asking and answering questions about unfamiliar apis: An exploratory study," in Proceedings of the 34th International Conference on Software Engineering. IEEE Press, 2012, pp. 266-276.
  22. B. Settles, "Active learning," Synthesis Lectures on Artificial Intelli- gence and Machine Learning, vol. 6, no. 1, pp. 1-114, 2012.
  23. L. De Raedt, Logical and relational learning. Springer Science & Business Media, 2008.
  24. V. S. Costa, R. Rocha, and L. Damas, "The yap prolog system," Theory and Practice of Logic Programming, vol. 12, no. 1-2, pp. 5-34, 2012.
  25. R. K. Yin, Case Study Research: Design and Methods (Applied Social Research Methods), fourth edition. ed. Sage Publications, 2008.
  26. R. Holmes and G. C. Murphy, "Using structural context to recom- mend source code examples," in ICSE '05: Proceedings of the 27th International Conference on Software Engineering. New York, NY, USA: ACM Press, 2005, pp. 117-125.
  27. N. Sahavechaphan and K. Claypool, "Xsnippet: Mining for sample code," ACM Sigplan Notices, vol. 41, no. 10, pp. 413-430, 2006.
  28. C. McMillan, M. Grechanik, D. Poshyvanyk, Q. Xie, and C. Fu, "Portfolio: finding relevant functions and their usage," in Proceedings of the 33rd International Conference on Software Engineering. ACM, 2011, pp. 111-120.
  29. S. Thummalapenta and T. Xie, "Parseweb: a programmer assistant for reusing open source code on the web," in Proceedings of the twenty- second IEEE/ACM international conference on Automated software engineering. ACM, 2007, pp. 204-213.
  30. J. Brandt, M. Dontcheva, M. Weskamp, and S. R. Klemmer, "Example-centric programming: integrating web search into the de- velopment environment," in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2010, pp. 513-522.
  31. K. T. Stolee, S. Elbaum, and D. Dobos, "Solving the search for source code," ACM Transactions on Software Engineering and Methodology (TOSEM), vol. 23, no. 3, p. 26, 2014.
  32. S. Bajracharya, T. Ngo, E. Linstead, Y. Dou, P. Rigor, P. Baldi, and C. Lopes, "Sourcerer: a search engine for open source code supporting structure-based search," in Companion to the 21st ACM SIGPLAN symposium on Object-oriented programming systems, languages, and applications. ACM, 2006, pp. 681-682.
  33. M. White, M. Tufano, C. Vendome, and D. Poshyvanyk, "Deep learning code fragments for code clone detection," in Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering. ACM, 2016, pp. 87-98.
  34. X. Gu, H. Zhang, and S. Kim, "Deep code search," in Proceedings of the 40th International Conference on Software Engineering. ACM, 2018, pp. 933-944.
  35. C. McMillan, M. Grechanik, D. Poshyvanyk, C. Fu, and Q. Xie, "Exemplar: A source code search engine for finding highly relevant applications," IEEE Transactions on Software Engineering, vol. 38, no. 5, pp. 1069-1087, 2012.
  36. Z. Li, S. Lu, S. Myagmar, and Y. Zhou, "Cp-miner: A tool for finding copy-paste and related bugs in operating system code." in OSdi, vol. 4, no. 19, 2004, pp. 289-302.
  37. T. Kamiya, S. Kusumoto, and K. Inoue, "Ccfinder: a multilinguistic token-based code clone detection system for large scale source code," IEEE Transactions on Software Engineering, vol. 28, no. 7, pp. 654- 670, 2002.
  38. H. Sajnani, V. Saini, J. Svajlenko, C. K. Roy, and C. V. Lopes, "Sourcerercc: Scaling code clone detection to big-code," in Software Engineering (ICSE), 2016 IEEE/ACM 38th International Conference on. IEEE, 2016, pp. 1157-1168.
  39. L. Jiang, G. Misherghi, Z. Su, and S. Glondu, "Deckard: Scalable and accurate tree-based detection of code clones," in Proceedings of the 29th International Conference on Software Engineering, ser. ICSE '07. Washington, DC, USA: IEEE Computer Society, 2007, pp. 96-105. [Online]. Available: http://dx.doi.org/10.1109/ICSE.2007.30 · DOI · Paper page
  40. C. K. Roy and J. R. Cordy, "Nicad: Accurate detection of near-miss intentional clones using flexible pretty-printing and code normaliza- tion," in Program Comprehension, 2008. ICPC 2008. The 16th IEEE International Conference on. IEEE, 2008, pp. 172-181.
  41. D. Janzen and K. De Volder, "Navigating and querying code without getting lost," in Proceedings of the 2nd international conference on Aspect-oriented software development. ACM, 2003, pp. 178-187.
  42. E. Hajiyev, M. Verbaere, and O. De Moor, "Codequest: Scalable source code queries with datalog," in European Conference on Object- oriented Programming. Springer, 2006, pp. 2-27.
  43. R. Wuyts, "Declarative reasoning about the structure of object- oriented systems," in Technology of Object-Oriented Languages, 1998. TOOLS 26. Proceedings. IEEE, 1998, pp. 112-124.
  44. T. Tourwé and T. Mens, "Identifying refactoring opportunities using logic meta programming," in Software Maintenance and Reengineer- ing, 2003. Proceedings. Seventh European Conference on. IEEE, 2003, pp. 91-100.
  45. Y.-G. Guéhéneuc and H. Albin-Amiot, "Using design patterns and constraints to automate the detection and correction of inter-class design defects," in Technology of Object-Oriented Languages and Sys- tems, 2001. TOOLS 39. 39th International Conference and Exhibition on. IEEE, 2001, pp. 296-305.
  46. M. Bravenboer and Y. Smaragdakis, "Strictly declarative specification of sophisticated points-to analyses," ACM SIGPLAN Notices, vol. 44, no. 10, pp. 243-262, 2009.
  47. Y. Smaragdakis, M. Bravenboer, and O. Lhoták, "Pick your contexts well: understanding object-sensitivity," in ACM SIGPLAN Notices, vol. 46, no. 1. ACM, 2011, pp. 17-30.
  48. M. Naik, A. Aiken, and J. Whaley, Effective static race detection for Java. ACM, 2006, vol. 41, no. 6.
  49. M. Naik, C.-S. Park, K. Sen, and D. Gay, "Effective static deadlock detection," in Software Engineering, 2009. ICSE 2009. IEEE 31st International Conference on. IEEE, 2009, pp. 386-396.
  50. R. Mangal, X. Zhang, A. V. Nori, and M. Naik, "A user-guided approach to program analysis," in Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. ACM, 2015, pp. 462-473.
  51. M. Martin, B. Livshits, and M. S. Lam, "Finding application errors and security flaws using pql: a program query language," ACM SIGPLAN Notices, vol. 40, no. 10, pp. 365-383, 2005.
  52. Y. Feng, S. Anand, I. Dillig, and A. Aiken, "Apposcopy: Semantics- based detection of android malware through static analysis," in Pro- ceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 2014, pp. 576-587.
  53. C. Wang, A. Cheung, and R. Bodik, "Synthesizing highly expressive sql queries from input-output examples," in ACM SIGPLAN Notices, vol. 52, no. 6. ACM, 2017, pp. 452-466.
  54. J. Galenson, P. Reames, R. Bodik, B. Hartmann, and K. Sen, "Codehint: Dynamic and interactive synthesis of code snippets," in Proceedings of the 36th International Conference on Software Engineering. ACM, 2014, pp. 653-663.
  55. F. Li and H. V. Jagadish, "Nalir: an interactive natural language interface for querying relational databases," in Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014, pp. 709-712.
  56. M. Mayer, G. Soares, M. Grechkin, V. Le, M. Marron, O. Polozov, R. Singh, B. Zorn, and S. Gulwani, "User interaction models for disambiguation in programming by example," in Proceedings of the 28th Annual ACM Symposium on User Interface Software & Technology. ACM, 2015, pp. 291-301.
  57. S. Tong and E. Chang, "Support vector machine active learning for image retrieval," in Proceedings of the ninth ACM international conference on Multimedia. ACM, 2001, pp. 107-118.
  58. M. Arias, R. Khardon, and J. Maloberti, "Learning horn expressions with logan-h," Journal of Machine Learning Research, vol. 8, no. Mar, pp. 549-587, 2007.
  59. D. Angluin, "Queries and concept learning," Machine learning, vol. 2, no. 4, pp. 319-342, 1988.
  60. W. W. Cohen, "Inductive specification recovery: Understanding soft- ware by learning from example behaviors," Automated Software Engineering, vol. 2, no. 2, pp. 107-129, 1995.
  61. A. Gammerman, V. Vovk, and V. Vapnik, "Learning by transduction," in Proceedings of the Fourteenth conference on Uncertainty in ar- tificial intelligence. Morgan Kaufmann Publishers Inc., 1998, pp. 148-155.
  62. O. Chapelle, B. Scholkopf, and A. Zien, "Semi-supervised learning," IEEE Transactions on Neural Networks, vol. 20, no. 3, pp. 542-542, 2009.

Authors
Sivaraman, A., Zhang, T., Van den Broeck, G., & Kim, M.
Affiliations
University of California, Los Angeles (US)
ORCID
Venue
2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)
Publisher
IEEE
Published
2019-05
Pages
292-303
ISSN
0270-5257 (ISSN-L)
DOI
10.1109/icse.2019.00044
OpenAlex
W2956048495
Cited by
34
References
81
Citations by year
2026: 1 · 2025: 4 · 2024: 3 · 2023: 4 · 2022: 7 · 2021: 6 · 2020: 5 · 2019: 3
FWCI
4.18
Type
conference paper
Language
en
Open access
Licence
Locations
  • ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1633857, 1460325, 1764077, 1723773, 1837129, 1527923)
  • Defense Advanced Research Projects Agency
Topics
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Research
  • Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Techniques and Practices
Keywords
user feedback, query refinement, negative examples, code features, inductive bias, ALICE

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