Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs

Abstract

Spatial Database Management Systems (SDBMSs) aim to store, manipulate, and retrieve spatial data spatial data. SDBMSs provide spatial data types, spatial indexing, and spatial join methods, which exist as the spatial extensions or spatial build-in features in famous DBMSs. These systems can be affected by logic bugs, the cause of returning incorrect results. A common key challenge to finding logic bugs is the so-called test oracle problem. Differential testing is a potential testing methodology that compares the results of multiple SDBMSs for a common input, and flags any discrepancy as a bug. However, differential testing is limited in overlooking bugs and false alarms in this setting. In this paper, we propose AEI (Affine Equivalent Inputs), a novel metamorphic testing approach to uncover unknown logic bugs in SDBMS. To evaluate the effectiveness of AEI , we implemented a tool named Spatter (Spatial DBMSs Tester) on testing four famous SDBMSs. In total, it detected 34 real, previously unknown, unique bugs, of which 30 have been confirmed and 19 already fixed. Our work has been well-recognized by SDBMSs’ developers and we believe that AEI can help solidify SDBMS due to its generality and effectiveness.