An Experimental Analysis of Graph-Distance Algorithms for Comparing API Usages

Sebastian Nielebock, Paul Blockhaus, Jacob Krüger, Frank Ortmeier

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

Modern software development heavily relies on the reuse of functionalities through Application Programming Interfaces (APIs). However, client developers can have issues identifying the correct usage of a certain API, causing misuses
accompanied by software crashes or usability bugs. Therefore, researchers have aimed at identifying API misuses automatically by comparing client code usages to correct API usages. Some techniques rely on certain API-specific graph-based data structures to improve the abstract representation of API usages. Such techniques need to compare graphs, for instance, by computing distance metrics based on the minimal graph edit distance or the largest common subgraphs, whose computations are known to be NP-hard problems. Fortunately, there exist many abstractions for simplifying graph distance computation. However, their applicability for comparing graph representations of API usages has not been analyzed. In this paper, we provide a comparison of different distance algorithms of API-usage graphs regarding correctness and runtime. Particularly, correctness relates to the algorithms’ ability to identify similar correct API usages, but also to discriminate similar correct and false usages as well as non-similar usages. For this purpose, we systematically identified a set of eight graph-based distance algorithms and applied them on two datasets of real-world API usages and misuses. Interestingly, our results suggest that existing distance algorithms are not reliable for comparing API usage graphs. To improve on this situation, we identified and discuss the algorithms’ issues, based on which we formulate hypotheses to initiate research on overcoming them.
Originele taal-2Engels
TitelProceedings - IEEE 21st International Working Conference on Source Code Analysis and Manipulation, SCAM 2021
UitgeverijIEEE Press
Pagina's214-225
Aantal pagina's12
ISBN van elektronische versie9781665448970
DOI's
StatusGepubliceerd - 2021

Bibliografische nota

DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Vingerafdruk

Duik in de onderzoeksthema's van 'An Experimental Analysis of Graph-Distance Algorithms for Comparing API Usages'. Samen vormen ze een unieke vingerafdruk.

Citeer dit