Proceedings of ISP RAS


Lightweight Static Analysis for Data Race Detection in Operating System Kernels

P.S. Andrianov (ISP RAS, Moscow), V.S. Mutilin(ISP RAS, Moscow), A.V. Khoroshilov (ISP RAS, Moscow; MSU, Moscow; MIPT, Moscow; HSE, Moscow)

Abstract

The paper presents an approach to lightweight static data race detection called CPALockator. It takes into account the specifics of operating system kernels such as complex parallelism and kernel specifics synchronization mechanisms. The method is based on the Lockset one but it implements two heuristics that are aimed to reduce amount of false alarms: a memory model and a model of parallelism. We consider locks as synchronization primitives. The main target of our research and evaluation is operating system kernels but the approach may be applied to the other programs as well. The method is based on idea of Configurable Program Analysis (CPA) and was implemented in CPAchecker tool. The implementation of the method was done in two stages. Firstly, the set of shared data is determined for every program location, then the analysis of synchronization primitives is performed. On the second stage, information about all potential accesses to shared variables and acquired synchronization primitives is also collected. After analysis the report with results is created. The tool was applied to the kernel of Real-Time operating system. It has about 200 000 lines of source code. CPALocator found 20 new race conditions, which are confirmed by developers. Also, the tool was launched on the Linux device drivers using the LDV framework for preparing tasks for CPALockator. The future investigations will be related to development more precise thread model and integration with more precise heavyweight methods of static analysis.

Keywords

static analysis, data race, operating system kernel, shared data

Edition

Proceedings of the Institute for System Programming, vol. 27, issue 5, 2015, pp. 87-116.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(5)-6

Full text of the paper in pdf (in Russian) Back to the contents of the volume