Programming language complexity analysis and its impact on Checkmarx activities

Abstract

Tools for Programming Languages processing, like Static Analysers (for instance, a Static Application Security Testing (SAST) tool, one of Checkmarx’s main products), must be adapted to cope with a given input when the source programming language changes. Complexity of the programming language is one of the key factors that deeply impact the time of giving support to it. This Master’s Project aims at proposing an approach for assessing language complexity, measuring, at a first stage, the complexity of its underlying context-free grammar (CFG). From the analysis of concrete case studies, factors have been identified that make the support process more time-consuming, in particular in the stages of language recognition and in the transformation to an abstract syntax tree (AST). In this sense, at a second stage, a set of language features is analysed in order to take into account the referred factors that also impact on the language processing. The main objective of the Master’s work here reported is to help development teams to improve the estimation of time and effort needed to adapt the SAST Tool in order to cope with a new programming language. In this dissertation a tool is proposed, that allows for the evaluation of the complexity of a language based on a set of metrics to classify the complexity of its grammar, along with a set of language properties. The tool compares the new language complexity so far determined with previously supported languages, to predict the effort to process the new language.

Ferramentas para processamento de Linguagens de Programação, como os Analisadores Estáticos (por exemplo, uma ferramenta de Testes Estáticos para Análise da Segurança de Aplicações, um dos principais produtos da Checkmarx), devem ser adaptadas para lidar com uma dada entrada quando a linguagem de programação de origem muda. A complexidade da linguagem de programação é um dos fatores-chave que influencia profundamente o tempo de suporte à mesma. Este projeto de Mestrado visa propor uma abordagem para avaliar a complexidade de uma linguagem de programação, medindo, numa primeira fase, a complexidade da gramática independente de contexto (GIC) subjacente. A partir da análise de casos concretos, foram identificados fatores (relacionados como facilidades específicas oferecidas pela linguagem) que tornam o processo de suporte mais demorado, em particular nas fases de reconhecimento da linguagem e na transformação para uma árvore de sintaxe abstrata (AST). Neste sentido, numa segunda fase, foi identificado um conjunto de características linguísticas de modo a ter em conta os referidos fatores que também têm impacto no processamento da linguagem. O principal objetivo do trabalho de mestrado aqui relatado é auxiliar as equipas de desenvolvimento a melhorar a estimativa do tempo e esforço necessários para adaptar a ferramenta SAST de modo a lidar com uma nova linguagem de programação. Como resultado deste projeto, tal como se descreve na dissertação, é proposta uma ferramenta, que permite a avaliação da complexidade de uma linguagem com base num conjunto de métricas para classificar a complexidade da sua gramática, e em um conjunto de propriedades linguísticas. A ferramenta compara a complexidade da nova linguagem, avaliada por aplicação do processo referido, com as linguagens anteriormente suportadas, para prever o esforço para processar a nova linguagem.