Elkhound, Elsa and Cqual++: Open-Source Static Analysis for C++

Google TechTalks April 11, 2006 Scott McPeak ABSTRACT This talk will cover three pieces of infrastructure for writing static analyses for C++. All are available as open source. Elkhound is a Generalized LR (GLR) parser generator. Its input is a grammar augmented with reduction actions written in C++. The GLR algorithm works with any context-free grammar, even ambiguous grammars. The user provides additional actions to resolve ambiguities that may arise during parsing. Elsa is a C++ parser written using Elkhound. It solves many of the classic parsing challenges of C and C++ by using an ambiguous grammar, delaying much of the disambiguation until the type checking phase. Not only does this lead to a cleaner design, the use of a parsing grammar lends itself naturally to language extensions, grammar fragments that pertain to specific language dialects (for example, GCC extensions). The use of extensions is ideal in a research setting. Finally, Cqual++ is a static analysis tool built on top of Elsa. It is a port of the older Cqual tool. It takes advantage of the Elsa extension mechanisms to process Cqual++ annotations, traverse the parsed AST, and then generate qualifier constraints that are solved by a general-purpose back end. It has been used to find a number of security bugs in the Linux kernel.