Autonomous Driving Systems (ADSs) are safety-critical, and must be fully tested before being deployed on real-world roads. To comprehensively evaluate the performance of ADSs, it is essential to generate various safety-critical scenarios. Most of existing studies assess ADSs either by searching high dimensional input space, or using simple and pre-defined test scenarios, which are not efficient or not adequate. To better test ADSs, this paper proposes to automatically generate safety-critical test scenarios for ADSs by influential behavior patterns, which are mined from real traffic trajectories. Based on influential behavior patterns, a novel scenario generation technique, CRISCO, is presented to generate safety-critical scenarios for ADSs testing. CRISCO assigns participants to perform influential behavior patterns to challenge the ADS. It generates diverse test scenarios by solving a group of trajectory constraints, and improves the challenge of those non-critical scenarios by adding participants’ behavior from influential behavior patterns incrementally. We demonstrate CRISCO on an industrial-grade full-stack ADS platform, Baidu Apollo. The experiment results show that our approach can effectively and efficiently generate safety-critical scenarios to crash ADS, and it exposes 13 distinct types of safety violations in 12 hours. It also outperforms two state-of-art ADS testing techniques by exposing more 5 distinct types of safety violations on the same road.

Haoxiang Tian

Institute of Software, Chinese Academy of Sciences

China

Guoquan Wu

Institute of Software at Chinese Academy of Sciences, China

Jiren Yan

Institute of Software, Chinese Academy of Sciences

Yan Jiang

Institute of Software, Chinese Academy of Sciences

Jun Wei

Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences

China

Wei Chen

Institute of Software at Chinese Academy of Sciences, China

Shuo Li

Institute of Software, Chinese Academy of Sciences

Dan Ye

Institute of Software, Chinese Academy of Sciences

Database Management Systems (DBMSs) utilize transactions to ensure the consistency and integrity of data. Incorrect transaction implementations in DBMSs can lead to severe consequences, e.g., incorrect database states and query results. Therefore, it is critical to ensure the reliability of transaction implementations.

In this paper, we propose \emph{DT$^2$}, an approach for automatically testing transaction implementations in DBMSs. We first randomly generate a database and a group of concurrent transactions operating the database, which can support complex features in DBMSs, e.g., various database schemas and cross-table queries. We then leverage differential testing to compare transaction execution results on multiple DBMSs to find discrepancies. The effectiveness of our method is heavily impaired by the non-determinism of concurrent transactions. Therefore, we propose a transaction test protocol to ensure the deterministic execution of concurrent transactions.

We evaluate DT$^2$ on three widely-used MySQL-compatible DBMSs, i.e., MySQL, MariaDB and TiDB. In total, we have detected 10 unique transaction bugs and 88 transaction-related compatibility issues from the observed discrepancies. Our empirical study on these compatibility issues shows that DBMSs suffer from various transaction-related compatibility issues, although they claim that they are compatible. These compatibility issues can also lead to serious consequences, e.g., inconsistent database states among DBMSs.

Ziyu Cui

Institute of Software, Chinese Academy of Sciences

China

Wensheng Dou

Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences

China

Qianwang Dai

Institute of Software, Chinese Academy of Sciences

Jiansen Song

China

Wei Wang

Jun Wei

Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences

China

Dan Ye

Institute of Software, Chinese Academy of Sciences