Comparing Execution Trace Using Merkle- Tree to Detect Backward Incompatibilities
Atsuhito Yamaoka, Teyon Son, Kazumasa Shimari, Takashi Ishio, Kenichi Matsumoto · 2024
The use of libraries is crucial in software development. Library users should update their libraries to address bugs and vulnerabilities that are fixed in newer versions. However, updating libraries can lead to software malfunction due to backward incompatibilities. Therefore, it is necessary to carefully examine the changes in the library, identify incompatible behavior, and modify the software accordingly when applying updates. Identifying the cause of incompatibility is challenging as updates often include changes to APIs other than the one used by the user. We propose a method to detect candidate library methods that cause backward incompatibilities in client-side library updates using Merkle tree. Our approach involves conducting unit tests on the client software, which includes library API calls, before and after the library updates. The execution traces of these tests are collected at the Java bytecode instruction level. By constructing Merkle trees for each execution trace before and after the update, we efficiently compare the control structures and return values to identify the differences indicating backward incompatibilities. To validate the effectiveness of our method, we conducted a case study on three instances of incompatibility in open-source software.